论文标题
Hessenberg的全局收敛移动QR III：通过倒数迭代的近似Ritz值
Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration
论文作者
论文摘要
我们根据转移的反迭代给出了一个独立的随机算法，该算法可证明计算任意矩阵$ m \ in \ mathbb {c}^{c}^{n \ times n} $的特征值$ to backward Error $ o（n^4+n^3 \ log^2（n/δ）+\ log（n/δ）^2 \ log \ log \ log \ log \ log \ log（n/δ））$ floing point Operations使用$ o（\ log^2（n/δ））$精度的位。虽然$ O（n^4）$复杂性对于大型矩阵而言是过敏的，但该算法很简单，并且可能使用受控的精确性，特别是对于在移位QR算法中计算ritz值的小矩阵的特征值很有用，如在（Banks，Garza-vargas，srivastava，Srivastava，20222222）。
We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix $M\in\mathbb{C}^{n\times n}$ up to backward error $δ\|M\|$ in $O(n^4+n^3\log^2(n/δ)+\log(n/δ)^2\log\log(n/δ))$ floating point operations using $O(\log^2(n/δ))$ bits of precision. While the $O(n^4)$ complexity is prohibitive for large matrices, the algorithm is simple and may be useful for provably computing the eigenvalues of small matrices using controlled precision, in particular for computing Ritz values in shifted QR algorithms as in (Banks, Garza-Vargas, Srivastava, 2022).
