A Schur–Newton Method for the Matrix {}th Root and its Inverse

Newton’s method for the inverse matrix pth root, A-1/p, has the attraction that it involves only matrix multiplication. We show that if the starting matrix is c⁻¹I for c⁺ then the iteration converges quadratically to A-1/p if the eigenvalues of A lie in a wedge‐shaped convex set containing the disc : |z-cᵖ| < cᵖ\. We derive an optimal choice of c for the case where A has real, positive eigenvalues. An application is described to roots of transition matrices from Markov models, in which for certain problems the convergence condition is satisfied with $c=1$. Although the basic Newton iteration is numerically unstable, a coupled version is stable and a simple modification of it provides a new coupled iteration for the matrix pth root. For general matrices we develop a hybrid algorithm that computes a Schur decomposition, takes square roots of the upper (quasi‐) triangular factor, and applies the coupled Newton iteration to a matrix for which fast convergence is guaranteed. The new algorithm can be used to compute either A1/p or A-1/p, and for large p that are not highly composite it is more efficient than the method of Smith based entirely on the Schur decomposition.