Backward stability of iterations for computing the polar decomposition

Yuji Nakatsukasa, Nicholas J. Higham

    Research output: Contribution to journalArticlepeer-review

    44 Downloads (Pure)

    Abstract

    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 X k+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 Kiełlbasiński and Zi̧etak. 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. © 2012 Society for Industrial and Applied Mathematics.
    Original languageEnglish
    Pages (from-to)460-479
    Number of pages19
    JournalSIAM Journal on Matrix Analysis and Applications
    Volume33
    Issue number2
    DOIs
    Publication statusPublished - 2012

    Keywords

    • Backward error analysis
    • Column pivoting
    • Dynamically weighted Halley iteration
    • Inverse Newton iteration
    • Newton iteration
    • Newton-Schulz iteration
    • Numerical stability
    • Polar decomposition
    • QR factorization
    • Rounding error analysis
    • Row pivoting
    • Row sorting

    Fingerprint

    Dive into the research topics of 'Backward stability of iterations for computing the polar decomposition'. Together they form a unique fingerprint.

    Cite this