Backward error analysis of the shift-and-invert Arnoldi algorithm.
Backward error analysis of the shift-and-invert Arnoldi algorithm.
复制标题
DOI：
10.1007/s00211-015-0759-9
复制
发表时间：
2016
影响因子：
2.1
通讯作者：
Taslaman L
中科院分区：
文献类型：
--
作者：
Schröder C;Taslaman L
我们进行向后误差分析的不精确的移位和反转Arnoldi算法。我们认为，在所产生的线性系统的解决方案中的不精确性，以及在正交归一化步骤，并考虑计算Krylov基础的非正交。我们证明了计算基和Hessenberg矩阵满足一个精确的移位和逆Krylov关系的扰动矩阵，我们给出的扰动界。证明了在小Hessenberg矩阵的条件数不太大的情况下，移位求逆Arnoldi算法是后向稳定的。然后使用隐式重新启动来放松此条件。此外，我们给出了厄米的情况下，考虑厄米向后错误的笔记，最后，我们用我们的分析，推导出一个合理的崩溃条件。
We perform a backward error analysis of the inexact shift-and-invert Arnoldi algorithm. We consider inexactness in the solution of the arising linear systems, as well as in the orthonormalization steps, and take the non-orthonormality of the computed Krylov basis into account. We show that the computed basis and Hessenberg matrix satisfy an exact shift-and-invert Krylov relation for a perturbed matrix, and we give bounds for the perturbation. We show that the shift-and-invert Arnoldi algorithm is backward stable if the condition number of the small Hessenberg matrix is not too large. This condition is then relaxed using implicit restarts. Moreover, we give notes on the Hermitian case, considering Hermitian backward errors, and finally, we use our analysis to derive a sensible breakdown condition.