Newton’s method for the matrix square root

Higham, Nicholas J.

doi:10.1090/S0025-5718-1986-0829624-5

Newton’s method for the matrix square root
HTML articles powered by AMS MathViewer

by Nicholas J. Higham PDF

Math. Comp. 46 (1986), 537-549 Request permission

Abstract:

One approach to computing a square root of a matrix A is to apply Newton’s method to the quadratic matrix equation $F(X) \equiv {X^2} - A = 0$. Two widely-quoted matrix square root iterations obtained by rewriting this Newton iteration are shown to have excellent mathematical convergence properties. However, by means of a perturbation analysis and supportive numerical examples, it is shown that these simplified iterations are numerically unstable. A further variant of Newton’s method for the matrix square root, recently proposed in the literature, is shown to be, for practical purposes, numerically stable.

References

Comm. ACM

Ȧke Björck and Sven Hammarling, A Schur method for the square root of a matrix, Linear Algebra Appl. 52/53 (1983), 127–140. MR 709347, DOI 10.1016/0024-3795(83)80010-X
Eugene D. Denman, Roots of real matrices, Linear Algebra Appl. 36 (1981), 133–139. MR 604336, DOI 10.1016/0024-3795(81)90226-3
Eugene D. Denman and Alex N. Beavers Jr., The matrix sign function and computations in systems, Appl. Math. Comput. 2 (1976), no. 1, 63–94. MR 393075, DOI 10.1016/0096-3003(76)90020-5

The Theory of Matrices

G. H. Golub, S. Nash, and C. Van Loan, A Hessenberg-Schur method for the problem $AX+XB=C$, IEEE Trans. Automat. Control 24 (1979), no. 6, 909–913. MR 566448, DOI 10.1109/TAC.1979.1102170
Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
Robert T. Gregory and David L. Karney, A collection of matrices for testing computational algorithms, Wiley-Interscience [A division of John Wiley & Sons, Inc.], New York-London-Sydney, 1969. MR 0253538
Nicholas J. Higham, Computing real square roots of a real matrix, Linear Algebra Appl. 88/89 (1987), 405–430. MR 882456, DOI 10.1016/0024-3795(87)90118-2
Nicholas J. Higham, Computing the polar decomposition—with applications, SIAM J. Sci. Statist. Comput. 7 (1986), no. 4, 1160–1174. MR 857788, DOI 10.1137/0907079

IEEE Trans. Automat. Control

W. D. Hoskins and D. J. Walton, A faster, more stable method for computing the $p$th roots of positive definite matrices, Linear Algebra Appl. 26 (1979), 139–163. MR 535683, DOI 10.1016/0024-3795(79)90176-9
Pentti Laasonen, On the iterative solution of the matrix equation $AX^{2}-I=0$, Math. Tables Aids Comput. 12 (1958), 109–116. MR 99107, DOI 10.1090/S0025-5718-1958-0099107-4
James M. Ortega, Numerical analysis. A second course, Computer Science and Applied Mathematics, Academic Press, New York-London, 1972. MR 0403154
G. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
Carl-Erik Fröberg, Introduction to numerical analysis, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0245168
Peter Henrici, Elements of numerical analysis, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR 0166900