Backward stability of iterations for computing the polar decomposition (Q2910965)

The authors prove backward stability of a general iteration for computing the polar decomposition, under two assumptions: (a) each iterate is obtained from the previous one in a mixed backward-forward stable way in floating point arithmetic; (b) no singular value of an iterate significantly decreases relative to the largest singular value from one iteration to the next, which is a condition on the iteration function.NEWLINENEWLINEThe analysis is generally applicable since it makes no direct reference to acceleration parameters or implementation details of the iteration. It is used to prove backward stability of the QR-based dynamically weighted Halley algorithm under the assumption that column pivoting and either row pivoting or row sorting are used in the QR factorization. The backward error bound involves a growth factor that can be exponentially large in \(n\) but is known to be small in practice. It is shown that the algorithm can be rarely unstable without pivoting.NEWLINENEWLINEIn addition, the authors prove in a short and simple way that the scaled Newton iteration is backward stable; give insight into why the scaled inverse Newton iteration is not backward stable; and show that the (scaled) Newton-Schulz iteration is backward stable if the starting matrix has 2-norm safely less than \(\sqrt{3}\) but can be unstable if the norm is close to \(\sqrt{3}\) (which is the boundary of the region of convergence).