Estimating the attainable accuracy of recursively computed residual methods
Estimating the attainable accuracy of recursively computed residual methods
复制标题
DOI：
10.1137/s0895479895284944
复制
发表时间：
1997-07-01
影响因子：
1.5
通讯作者：
Greenbaum, A
中科院分区：
文献类型：
--
作者：
Greenbaum, A
许多解线性方程组Ax=b的类共轭梯度法不是直接计算残差，而是使用递推公式来更新残差。对于这种方法，证明了有限精度算法产生的实际残差和更新的近似残差向量之间的差取决于机器精度和迭代的最大范数除以真解的范数。通常可以从数值上观察到，有时可以证明，更新后的近似残差向量的范数收敛到零，或者至少变得比机器精度小几个数量级。在这种情况下，实际剩余范数达到迭代范数与真解范数的最大值之比的水平。利用精确的算术理论来限定迭代的大小，我们给出了一些算法的最终残差大小的先验估计。
Many conjugate gradient-like methods for solving linear systems Ax = b use recursion formulas for updating residual vectors instead of computing the residuals directly. For such methods it is shown that the difference between the actual residuals and the updated approximate residual vectors generated in finite precision arithmetic depends on the machine precision epsilon and on the maximum norm of an iterate divided by the norm of the true solution. It is often observed numerically, and can sometimes be proved, that the norms of the updated approximate residual vectors converge to zero or, at least, become orders of magnitude smaller than the machine precision. In such cases, the actual residual norm reaches the level epsilon\\A\\ \\x\\ times the maximum ratio of the norm of an iterate to that of the true solution. Using exact arithmetic theory to bound the size of the iterates, we give a priori estimates of the size of the final residual for a number of algorithms.