Abstract
A mesh independent bound is given for the superlinear convergence of the CGM for preconditioned self-adjoint linear elliptic problems using suitable equivalent operators. The results rely on K-condition numbers and related estimates for compact Hilbert-Schmidt operators in Hilbert space.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
O. Axelsson: Iterative Solution Methods. Cambridge University Press, Cambridge, 1994.
O. Axelsson, I. Kaporin: 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 (2000), 1–22.
O. Axelsson, J. Karatson: On the rate of convergence of the conjugate gradient method for linear operators in Hilbert space. Numer. Funct. Anal. Optmization 23 (2002), 285–302.
O. Axelsson, J. Karatson: Superlinearly convergent CG methods via equivalent preconditioning for nonsymmetric elliptic operators. Numer. Math. 99 (2004), 197–223. SpringerLink DOI: 10.1007/s00211-004-0557-2 (electronic).
R. E. Bank, D. J. Rose: Marching algorithms for elliptic boundary value problems. I. The constant coefficient case. SIAM J. Numer. Anal. 14 (1977), 792–829.
R. E. Bank: Marching algorithms for elliptic boundary value problems. II. The variable coefficient case. SIAM J. Numer. Anal. 14 (1977), 950–970.
B. Beckermann, A. B. J. Kuijlaars: Superlinear convergence of conjugate gradients. SIAM J. Numer. Anal. 39 (2001), 300–329. Electronic.
P. Concus, G. H. Golub: Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations. SIAM J. Numer. Anal. 10 (1973), 1103–1120.
J. W. Daniel: The conjugate gradient method for linear and nonlinear operator equations. SIAM J. Numer. Anal. 4 (1967), 10–26.
H. C. Elman, M. H. Schultz: Preconditioning by fast direct methods for nonself-adjoint nonseparable elliptic equations. SIAM J. Numer. Anal. 23 (1986), 44–57.
V. Faber, T. Manteuffel, and S. V. Parter: On the theory of equivalent operators and application to the numerical solution of uniformly elliptic partial differential equations. Adv. Appl. Math. 11 (1990), 109–163.
I. Farago, J. Karatson: Numerical solution of nonlinear elliptic problems via preconditioning operators. Theory and applications. Advances in Computation, Vol. 11. NOVA Science Publishers, Huntington, 2002.
Z. Fortuna: Some convergence properties of the conjugate gradient method in Hilbert space. SIAM J. Numer. Anal. 16 (1979), 380–384.
I. Gohberg, S. Goldberg, and M. A. Kaashoek: Classes of linear operators, Vol. I. Operator Theory: Advances and Applications, Vol. 49. Birkhauser-Verlag, Basel, 1990.
R. M. Hayes: Iterative methods of solving linear problems in Hilbert space. Natl. Bur. Stand.; Appl. Math. Ser. 39 (1954), 71–103.
M. R. Hestenes, E. Stiefel: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand., Sect. B 49 (1952), 409–436.
J. Kadlec: 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. Czechoslovak Math. J. 14(89) (1964), 386–393. (In Russian.)
J. Karatson, I. Farago: Variable preconditioning via quasi-Newton methods for nonlinear problems in Hilbert space. SIAM J. Numer. Anal. 41 (2003), 1242–1262.
T. Manteuffel, J. Otto: Optimal equivalent preconditioners. SIAM J. Numer. Anal. 30 (1993), 790–812.
J. W. Neuberger: Sobolev gradients and differential equations. Lecture Notes in Math., No. 1670. Springer-Verlag, Berlin, 1997.
T. Rossi, J. Toivanen: A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension. SIAM J. Sci. Comput. 20 (1999), 1778–1793.
T. Rossi, J. Toivanen: Parallel fictitious domain method for a non-linear elliptic Neumann boundary value problem. Czech-US Workshop in Iterative Methods and Parallel Computing, Part I (Milovy, 1997). Numer. Linear Algebra Appl. 6 (1999), 51–60.
W. Rudin: Functional Analysis. McGraw-Hill, New York, 1991.
F. Riesz, B. Sz.-Nagy: Vorlesungen uber Funktionalanalysis. VEB Deutscher Verlag der Wissenschaften, Berlin, 1982.
L. Simon, E. Baderko: Linear Partial Differential Equations of Second Order. Tankonyvkiado, Budapest, 1983. (In Hungarian.)
P. N. Swarztrauber: 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 (1977), 490–501.
Yu. V. Vorobyev: Methods of Moments in Applied Mathematics. Gordon and Breach, New York, 1965.
R. Winter: Some superlinear convergence results for the conjugate gradient method. SIAM J. Numer. Anal. 17 (1980), 14–17.
Author information
Authors and Affiliations
Additional information
This research was supported by the Hungarian National Research Fund OTKA under grant No. T043765.
Rights and permissions
About this article
Cite this article
Karatson, J. Mesh independent superlinear convergence estimates of the conjugate gradient method for some equivalent self-adjoint operators. Appl Math 50, 277–290 (2005). https://doi.org/10.1007/s10492-005-0017-z
Issue Date:
DOI: https://doi.org/10.1007/s10492-005-0017-z