| Newton's Iteration is a fundamental algorithm of numerical and algebraic computing. We focus on its application to the approximation of the inverse or Moore-Penrose generalized inverse of a matrix. This application was studied by Schultz in 1933 and since then by many authors. The algorithm is strongly stable numerically (in fact it is self-correcting) and converges quadratically, provided that an initial approximation to the (generalized) inverse is available.; An initial approximation can be crude, but must have a residual norm less than 1, and some known recipes (see in particular [PS91]) give approximations with the initial norms slightly below 1. Most effective, however, are applications of Newton's iteration where the input matrices are structured (celebrated examples are the Toeplitz, Henkel, Vandermonde, and Cauchy matrices), and in this case approximations obtained based on the above recipes is generally too crude. The computation by N.I. is reduced essentially to repeatedly performing matrix multiplication, and this operation can be performed very effectively, in nearly linear time, when the matrices are structured (versus cubic time for general matrices). The structure, however, tends to deteriorate gradually as N.I. progresses. Special techniques for preserving the structure have been proposed in [P92], [PBRZ99], (PRWa]. These techniques, however, require sufficiently close initial approximations, substantially closer than those supplied by the known recipes, including the recipes of [PS91]. The problem can be solved, however, based on a new homotopic approach which is our subject in the thesis.; We apply this approach to general input matrices. The resulting homotopic version of N.I. turns out to be competitive with non-homotopic version for Hermitian (or real symmetric) input matrices. For the homotopic version, the computational cost is roughly the same as for the non-homotopic one where the input matrix is positive definite and is substantially less where it is indefinite. We also study application of this approach to structured matrices, in which case each iteration step is dramatically accelerated and is performed in nearly linear time, because some special techniques preserve the structure during the entire iterative process. Numerical experiments reported in [PKRCa] confirm the effectiveness of the resulting algorithms in the case of Toeplitz input matrices. |
