Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations

0482261 - ÚI 2018 NL eng J - Journal Article
Gergelits, Tomáš - Strakoš, Zdeněk
Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations.
Numerical Algorithms. Roč. 65, č. 4 (2014), s. 759-782. ISSN 1017-1398. E-ISSN 1572-9265
Keywords : linear-systems * superlinear convergence * differential-equations * lanczos-algorithm * error estimation * recurrences * quadrature * accuracy * behavior * matrix * Conjugate gradient method * Stieltjes moment problem * Chebyshev * semi-iterative method * Composite polynomial * convergence bounds * Finite precision computations * Clusters of eigenvalues
Impact factor: 1.417, year: 2014

The conjugate gradient method (CG) for solving linear systems of algebraic equations represents a highly nonlinear finite process. Since the original paper of Hestenes and Stiefel published in 1952, it has been linked with the Gauss-Christoffel quadrature approximation of Riemann-Stieltjes distribution functions determined by the data, i.e., with a simplified form of the Stieltjes moment problem. This link, developed further by Vorobyev, Brezinski, Golub, Meurant and others, indicates that a general description of the CG rate of convergence using an asymptotic convergence factor has principal limitations. Moreover, CG is computationally based on short recurrences. In finite precision arithmetic its behaviour is therefore affected by a possible loss of orthogonality among the computed direction vectors. Consequently, any consideration concerning the CG rate of convergence relevant to practical computations must include analysis of effects of rounding errors. Through the example of composite convergence bounds based on Chebyshev polynomials, this paper argues that the facts mentioned above should become a part of common considerations on the CG rate of convergence. It also explains that the spectrum composed of small number of well separated tight clusters of eigenvalues does not necessarily imply a fast convergence of CG or other Krylov subspace methods.
Permanent Link: http://hdl.handle.net/11104/0277643