Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Superlinearly convergent CG methods via equivalent preconditioning for nonsymmetric elliptic operators

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Summary.

The convergence of the conjugate gradient method is studied for preconditioned linear operator equations with nonsymmetric normal operators, with focus on elliptic convection-diffusion operators in Sobolev space. Superlinear convergence is proved first for equations whose preconditioned form is a compact perturbation of the identity in a Hilbert space. Then the same convergence result is verified for elliptic convection-diffusion equations using different preconditioning operators. The convergence factor involves the eigenvalues of the corresponding operators, for which an estimate is also given. The above results enable us to verify the mesh independence of the superlinear convergence estimates for suitable finite element discretizations of the convection-diffusion problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ashby, S.F., Manteuffel, T.A., Saylor, P.E.: A taxonomy for conjugate gradient methods. SIAM J. Numer. Anal. 27(6), 1542–1568 (1990)

    MATH  Google Scholar 

  2. Axelsson, O.: A generalized conjugate gradient least square method. Numer. Math. 51, 209–227 (1987)

    MATH  Google Scholar 

  3. Axelsson, O.: Iterative Solution Methods. Cambridge: Cambridge University Press, 1994

  4. Axelsson, O., Barker, V.A.: Finite Element Solution of Boundary Value Problems. Academic Press, 1984

  5. Axelsson, O., Gololobov, S.V.: A combined method of local Green’s functions and central difference method for singularly perturbed convection-diffusion problems. J. Comput. Appl. Math. 161(2), 245–257 (2003)

    Article  MATH  Google Scholar 

  6. Axelsson, O., Kaporin, I.: On the sublinear and superlinear rate of convergence of conjugate gradient methods. Mathematical journey through analysis, matrix theory and scientific computation (Kent, OH, 1999). Numer. Algorithms 25(1–4), 1–22 (2000)

  7. Axelsson, O., Karátson J.: On the rate of convergence of the conjugate gradient method for linear operators in Hilbert space. Numer. Funct. Anal. 23(3–4), 285–302 (2002)

    Google Scholar 

  8. Axelsson, O., Karátson J.: Symmetric part preconditioning for the conjugate gradient method in Hilbert space. Numer. Funct. Anal. 24(5–6), 455–474 (2003)

    Google Scholar 

  9. Axelsson, O., Lindskog, G.: On the rate of convergence of the preconditioned conjugate gradient method. Numer. Math. 48(5), 499–523 (1986)

    MATH  Google Scholar 

  10. Bank, R.E., Rose, D.J.: Marching algorithms for elliptic boundary value problems. I. The constant coefficient case. SIAM J. Numer. Anal. 14(5), 792–829 (1977)

    MATH  Google Scholar 

  11. Ciarlet, P.G.: The finite element method for elliptic problems. North-Holland, Amsterdam, 1978

  12. Ciarlet, Ph.G., Lions J.-L.; (eds.): Handbook of numerical analysis, Vol. II. Finite element methods, Part 1, North-Holland, Amsterdam, 1991

  13. Concus, P., Golub, G.H.: Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations. SIAM J. Numer. Anal. 10, 1103–1120 (1973)

    MATH  Google Scholar 

  14. Daniel, J.W.: The conjugate gradient method for linear and nonlinear operator equations. SIAM J. Numer. Anal. 4(1), 10–26 (1967)

    Google Scholar 

  15. Faber, V., Manteuffel, T., Parter, S.V.: On the theory of equivalent operators and application to the numerical solution of uniformly elliptic partial differential equations. Adv. Appl. Math. 11, 109–163 (1990)

    MATH  Google Scholar 

  16. Fortuna, Z.: Some convergence properties of the conjugate gradient method in Hilbert space. SIAM J. Numer. Anal. 16(3), 380–384 (1979)

    MATH  Google Scholar 

  17. Gohberg, I., Goldberg, S., Kaashoek, M.A.: Classes of linear operators, Vol. I. Operator Theory: Advances and Applications, 49, Birkhäuser Verlag, Basel, 1990

  18. Goldstein, C.I., Manteuffel, T.A., Parter, S. V.: Preconditioning and boundary conditions without H2 estimates: L2 condition numbers and the distribution of the singular values. SIAM J. Numer. Anal. 30(2), 343–376 (1993)

    MATH  Google Scholar 

  19. Hackbusch, W.: Multigrid methods and applications. Springer Series in Computational Mathematics 4, Springer, Berlin, 1985

  20. Hackbusch, W.: Elliptic differential equations. Theory and numerical treatment. Springer Series in Computational Mathematics 18, Springer, Berlin, 1992

  21. Hayes, R.M.: Iterative methods of solving linear problems in Hilbert space. Nat. Bur. Standards Appl. Math. Ser 39, 71–104 (1954)

    MATH  Google Scholar 

  22. Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards. Sect. B, 49(6), 409–436 (1952)

    Google Scholar 

  23. Kadlec, J.: On the regularity of the solution of the Poisson problem on a domain with boundary locally similar to the boundary of a convex open set. Czechosl. Math. J. 14(89), 386–393 (1964)

    MATH  Google Scholar 

  24. Karátson J.: Mesh independence of the superlinear convergence of the conjugate gradient method. Submitted

  25. Manteuffel, T., Otto, J.: Optimal equivalent preconditioners. SIAM J. Numer. Anal. 30, 790–812 (1993)

    MATH  Google Scholar 

  26. Manteuffel, T., Parter, S.V.: Preconditioning and boundary conditions. SIAM J. Numer. Anal. 27(3), 656–694 (1990)

    MATH  Google Scholar 

  27. Nevanlinna, O.: Convergence of iterations for linear equations. Birkhäuser, Basel, 1993

  28. Rossi, T., Toivanen, J.: A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension. SIAM J. Sci. Comput. 20(5), 1778–1796 (1999) (electronic)

    Article  MATH  Google Scholar 

  29. Riesz F., Sz.-Nagy B.: Vorlesungen über Funktionalanalysis. Verlag H. Deutsch, 1982

  30. Saad, Y., Schultz, M.H.: Conjugate gradient-like algorithms for solving nonsymmetric linear systems. Math. Comput. 44, 417–424 (1985)

    MATH  Google Scholar 

  31. Swarztrauber, P.N.: The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson’s equation on a rectangle. SIAM Rev. 19(3), 490–501 (1977)

    MATH  Google Scholar 

  32. Winter, R.: Some superlinear convergence results for the conjugate gradient method. SIAM J. Numer. Anal. 17, 14–17 (1980)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Nijmegen, 6525ED, Nijmegen, The Netherlands

    O. Axelsson

  2. Department of Applied Analysis, ELTE University, 1117, Budapest, Hungary

    J. Karátson

Authors
  1. O. Axelsson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Karátson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. Karátson.

Additional information

Mathematics Subject Classification (2000): 65J10, 65F10, 65N15

The second author was supported by the Hungarian Research Grant OTKA No. T. 043765.

Dedicated to David M. Young on the occasion of his 80th birthday.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Axelsson, O., Karátson, J. Superlinearly convergent CG methods via equivalent preconditioning for nonsymmetric elliptic operators. Numer. Math. 99, 197–223 (2004). https://doi.org/10.1007/s00211-004-0557-2

Download citation

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-004-0557-2

Keywords

Search

Navigation