A New Scaling for Newton's Iteration for the Polar Decomposition and its Backward Stability
A New Scaling for Newton's Iteration for the Polar Decomposition and its Backward Stability
复制标题
极分解牛顿迭代的新标度及其后向稳定性
DOI：
10.1137/070699895
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Hongguo Xu
中科院分区：
文献类型：
--
作者：
R. Byers;Hongguo Xu
我们提出了一个牛顿迭代计算极分解的缩放方案。缩放因子由简单的标量迭代生成，其中初始值仅取决于原始矩阵的极端奇异值的估计，例如，可以是矩阵及其逆的Frobenius范数。在精确算术中，对于条件数不大于$10^{16}$的矩阵，使用这种缩放方案，不需要超过9次迭代来收敛到酉极因子，收敛容限大致等于$10^{-16}$。证明了在有限精度算法中计算的矩阵逆满足前向-后向误差模型时，该数值方法是后向稳定的。证明了采用希格姆尺度或Frobenius范数尺度的Newton方法是后向稳定的。
We propose a scaling scheme for Newton's iteration for calculating the polar decomposition. The scaling factors are generated by a simple scalar iteration in which the initial value depends only on estimates of the extreme singular values of the original matrix, which can, for example, be the Frobenius norms of the matrix and its inverse. In exact arithmetic, for matrices with condition number no greater than $10^{16}$, with this scaling scheme no more than 9 iterations are needed for convergence to the unitary polar factor with a convergence tolerance roughly equal to $10^{-16}$. It is proved that if matrix inverses computed in finite precision arithmetic satisfy a backward-forward error model, then the numerical method is backward stable. It is also proved that Newton's method with Higham's scaling or with Frobenius norm scaling is backward stable.