ON SCALING NEWTON METHOD FOR POLAR DECOMPOSITION AND THE MATRIX SIGN FUNCTION

A tight bound is given on the speed of convergence of Newton's method with optimal scaling for the polar decomposition of a nonsingular complex matrix. Necessary and sufficient conditions are then derived that tell when an approximation to the optimal scaling value will give better results than the unscaled Newton method. For the related matrix sign problem, it is shown that optimal scaling requires complete knowledge of the eigenvalues of the original matrix. Because this is impractical, a family of scaling methods that are optimal with respect to partial eigenvalue information is derived. This family includes optimal scaling as well as a "semioptimal" scaling method based on the dominant eigenvalues of the matrix and its inverse. Semioptimal scaling can be implemented using the power method and it gives nearly optimal performance on a set of test problems. These test problems also show that a variety of other commonly used scaling strategies, including spectral scaling, determinantal scaling, and 2-norm scaling, can result in unduly slow convergence.