On Meinardus' examples for the conjugate gradient method
On Meinardus' examples for the conjugate gradient method
复制标题
DOI：
10.1090/s0025-5718-07-01922-9
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Ren-Cang Li
中科院分区：
文献类型：
--
作者：
Ren-Cang Li
.共轭梯度法（CG）是求解N阶正定线性方程组Ax = B的常用方法。众所周知，CG的第k次近似解（初始近似x 0 = 0）的相对残差上界为2[k k +-k k ] -1，其中k=√k+1 √k-1，其中K = K（A）= A 2 A-1 2是A的谱条件数。1963年，Meinardus（Numer.数学、《明史》卷5（1963），列传第120。14-23）给出了一个例子，以实现这个界限k = N - 1，但没有说任何其他1 < k < N - 1。这个例子可以通过构造例子来证明对于任何给定的k，该界是尖锐的，但是这样的例子依赖于k，并且对于它们，第（k + 1）个残差恰好为零。因此，了解是否存在CG相对残差与所有1 ≤ k < N - 1的界相当的任何示例将是有趣的。本文的主要贡献有两点：（1）在Meinardus的例子上，得到了CG残差的封闭公式，特别是它意味着CG残差的界总是在实际残差的-λ 2倍之内;（2）给出了极正线性系统的第k个CG残差达到界的完整刻画。
. The conjugate gradient (CG) method is widely used to solve a positive definite linear system Ax = b of order N. It is well known that the relative residual of the kth approximate solution by CG (with the initial approximation x 0 = 0) is bounded above by 2[∇ k k +∇ -k k ] -1 with ∇k=√k+1 √k-1 where K = K ( A) = ∥A∥ 2 ∥A -1 ∥ 2 is A's spectral condition number. In 1963, Meinardus (Numer. Math., 5 (1963), pp. 14-23) gave an example to achieve this bound for k = N - 1 but without saying anything about all other 1 < k < N - 1. This very example can be used to show that the bound is sharp for any given k by constructing examples to attain the bound, but such examples depend on k and for them the (k + 1)th residual is exactly zero. Therefore it would be interesting to know if there is any example on which the CG relative residuals are comparable to the bound for all 1 ≤ k < N - 1. There are two contributions in this paper: (1) A closed formula for the CG residuals for all 1 ≤ k < N- 1 on Meinardus' example is obtained, and in particular it implies that the bound is always within a factor of -√2 of the actual residuals; (2) A complete characterization of extreme positive linear systems for which the kth CG residual achieves the bound is also presented.