BACKWARD STABILITY OF ITERATIONS FOR COMPUTING THE POLAR DECOMPOSITION
BACKWARD STABILITY OF ITERATIONS FOR COMPUTING THE POLAR DECOMPOSITION
复制标题
DOI：
10.1137/110857544
复制
发表时间：
2012-01-01
影响因子：
1.5
通讯作者：
Higham, Nicholas J.
中科院分区：
文献类型：
--
作者：
Nakatsukasa, Yuji;Higham, Nicholas J.
在许多可用于计算极分解的迭代中，最实用的是比例牛顿迭代和最近提出的动态加权Hley迭代。扩展这些迭代和其他迭代的有效方法是已知的，但对其数值稳定性的了解要少得多。在这项工作中，我们证明了计算酉极因子的一般迭代Xk+1=f(X-k)在两个条件下是后向稳定的。第一个条件要求迭代是以混合后向-向前稳定的方式实现的，第二个条件要求映射f不显著地减小任何奇异值相对于最大奇异值的大小。利用这一结果，我们证明了当使用具有列旋转和行旋转或行排序的HouseholdQR分解实现动态加权Hley迭代时，它是向后稳定的。我们还证明了在矩阵逆是以混合的向后-向前稳定的方式计算的假设下，尺度牛顿迭代的向后稳定性；我们的证明比Kielbasinski和Zietak的证明要短得多。我们还利用我们的分析解释了逆牛顿迭代的不稳定性，并证明了牛顿-舒尔茨迭代只是条件稳定的。这项工作表明，通过仔细地将摄动分析与舍入误差分析相结合，有可能产生一个一般性的结果，该结果可以证明极分解的向后稳定性，或者预测或解释极分解的各种实际有趣的迭代的不稳定性(视情况而定)。
Among the many iterations available for computing the polar decomposition the most practically useful are the scaled Newton iteration and the recently proposed dynamically weighted Halley iteration. Effective ways to scale these and other iterations are known, but their numerical stability is much less well understood. In this work we show that a general iteration Xk+1 = f(X-k) for computing the unitary polar factor is backward stable under two conditions. The first condition requires that the iteration is implemented in a mixed backward-forward stable manner and the second requires that the mapping f does not significantly decrease the size of any singular value relative to the largest singular value. Using this result we show that the dynamically weighted Halley iteration is backward stable when it is implemented using Householder QR factorization with column pivoting and either row pivoting or row sorting. We also prove the backward stability of the scaled Newton iteration under the assumption that matrix inverses are computed in a mixed backward-forward stable fashion; our proof is much shorter than a previous one of Kielbasinski and Zietak. We also use our analysis to explain the instability of the inverse Newton iteration and to show that the Newton-Schulz iteration is only conditionally stable. This work shows that by carefully blending perturbation analysis with rounding error analysis it is possible to produce a general result that can prove the backward stability or predict or explain the instability (as the case may be) of a wide range of practically interesting iterations for the polar decomposition.