INEXACT PRECONDITIONED CONJUGATE GRADIENT METHOD WITH INNER-OUTER ITERATION
INEXACT PRECONDITIONED CONJUGATE GRADIENT METHOD WITH INNER-OUTER ITERATION
复制标题
DOI：
10.1137/s1064827597323415
复制
发表时间：
1999-01-01
影响因子：
3.1
通讯作者：
Ye, Qiang
中科院分区：
文献类型：
--
作者：
Golub, Gene H.;Ye, Qiang
预条件共轭梯度算法的一个重要变化是由内外迭代实现的不精确预条件[G]。H. Golub和M. L. Overton，数值分析，数学讲义，912，施普林格，柏林，纽约，1982]，其中预条件通过内部迭代求解到规定的精度。本文给出了对称正定系统的非精确预条件共轭梯度算法，并分析了其收敛性。利用残差模的局部关系建立了一个线性收敛结果。利用全局方程对该算法进行了分析，证明了该算法在内部迭代求解精度较高时可能具有超线性收敛性。分析结果与所观察到的算法数值行为一致。特别地，它建议启发式地选择内部迭代的停止阈值。数值算例表明了这种选择的有效性，并对其收敛界进行了比较。
An important variation of preconditioned conjugate gradient algorithms is inexact preconditioner implemented with inner-outer iterations [G. H. Golub and M. L. Overton, Numerical Analysis, Lecture Notes in Math. 912, Springer, Berlin, New York, 1982], where the preconditioner is solved by an inner iteration to a prescribed precision. In this paper, we formulate an inexact preconditioned conjugate gradient algorithm for a symmetric positive definite system and analyze its convergence property. We establish a linear convergence result using a local relation of residual norms. We also analyze the algorithm using a global equation and show that the algorithm may have the superlinear convergence property when the inner iteration is solved to high accuracy. The analysis is in agreement with observed numerical behavior of the algorithm. In particular, it suggests a heuristic choice of the stopping threshold for the inner iteration. Numerical examples are given to show the effectiveness of this choice and to compare the convergence bound.