Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations
Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations
复制标题
DOI：
10.1007/s11075-013-9713-z
复制
发表时间：
2014-04
影响因子：
2.1
通讯作者：
T. Gergelits;Z. Strakoš
中科院分区：
文献类型：
--
作者：
T. Gergelits;Z. Strakoš
解线性代数方程组的共轭梯度法是一个高度非线性的有限元过程。自从1952年Hestenes和Stiefel的原始论文发表以来，它一直与由数据确定的Riemann-Stieltjes分布函数的Gauss-Christoffel求积近似相联系，即与Stieltjes矩问题的简化形式相联系。由Vorobyev，Brezinski，Golub，Meurant等人进一步发展的这一联系表明，使用渐近收敛因子来描述CG收敛速度的一般描述具有主要局限性。此外，CG在计算上是基于短递归的。因此，在有限精度算术中，其行为受到计算的方向向量之间可能失去正交性的影响。因此，任何关于与实际计算相关的CG收敛速度的考虑都必须包括对舍入误差的影响的分析。通过基于切比雪夫多项式的复合收敛界的例子，本文认为上述事实应该成为关于CG收敛速度的共同考虑的一部分。它还解释了由少量分离良好的紧特征值簇组成的谱并不一定意味着CG或其他Krylov子空间方法的快速收敛。
The conjugate gradient method (CG) for solving linear systems of algebraic equations represents ahighly 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 theStieltjes 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 onshort recurrences. In finite precision arithmetic its behaviour is therefore affected by a possible loss of orthogonality among the computed direction vectors. Consequently,anyconsideration 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.