Approximating the extreme Ritz values and upper bounds for the A-norm of the error in CG
Approximating the extreme Ritz values and upper bounds for the A-norm of the error in CG
复制标题
近似 CG 中误差 A 范数的极限 Ritz 值和上限
DOI：
10.1007/s11075-018-0634-8
复制
发表时间：
2018
影响因子：
2.1
通讯作者：
Petr Tichý
中科院分区：
文献类型：
--
作者：
G. Meurant;Petr Tichý
在实际共轭梯度 (CG) 计算中，监控 Ax=b 近似解的质量非常重要，以便在达到所需精度时停止 CG 算法。相关的收敛特性，例如误差的 A 范数或范数后向误差，无法轻易计算。然而，它们是可以估计的。这种估计通常取决于 A 的最小或最大特征值的近似值。在本文中，我们引入了与 Gauss-Radau 上限密切相关的误差 A 范数的新上限，并讨论了选择代表 A 最小特征值下界的参数 µ 的问题。新界有几个实际优点，最重要的一个是它可以用作误差 A 范数的近似值，即使 µ 不完全是 A 的最小特征值的下界。在这种情况下，μ可以被选择为例如最小的Ritz值或其近似值。我们还描述了一种基于增量范数估计技术的非常便宜的算法，该算法允许在 CG 计算期间估计最小和最大 Ritz 值。提高这些极端 Ritz 值估计的准确性是可能的，但代价是存储 CG 系数并在每次 CG 迭代时用三对角矩阵求解线性系统。最后，我们讨论如何廉价地近似标准化后向误差。数值实验证明了极端 Ritz 值估计的效率，并展示了它们在 CG 误差估计中的实际用途。
In practical conjugate gradient (CG) computations, it is important to monitor the quality of the approximate solution toAx=bso that the CG algorithm can be stopped when the required accuracy is reached. The relevant convergence characteristics, like theA-norm of the error or the normwise backward error, cannot be easily computed. However, they can be estimated. Such estimates often depend on approximations of the smallest or largest eigenvalue ofA. In the paper, we introduce a new upper bound for theA-norm of the error, which is closely related to the Gauss-Radau upper bound, and discuss the problem of choosing the parameterµwhich should represent a lower bound for the smallest eigenvalue ofA. The new bound has several practical advantages, the most important one is that it can be used as an approximation to theA-norm of the error even ifµis not exactly a lower bound for the smallest eigenvalue ofA. In this case,µcan be chosen, e.g., as the smallest Ritz value or its approximation. We also describe a very cheap algorithm, based on the incremental norm estimation technique, which allows to estimate the smallest and largest Ritz values during the CG computations. An improvement of the accuracy of these estimates of extreme Ritz values is possible, at the cost of storing the CG coefficients and solving a linear system with a tridiagonal matrix at each CG iteration. Finally, we discuss how to cheaply approximate the normwise backward error. The numerical experiments demonstrate the efficiency of the estimates of the extreme Ritz values, and show their practical use in error estimation in CG.
影响因子：
2.1
作者：
通讯作者：
--