Projected Newton Method Has Order 1 + Square Root of 2 for the Symmetric Eigenvalue Problem.

摘要

In their study of the classical inverse iteration algorithm, Peters and Wilkinson considered the closely related algorithm that consists of applying Newton's method, followed by a 2-norm normalization, to the nonlinear system of equations consisting of the eigenvalue-eigenvector equation and an equation requiring the eigenvector to have the square of its 2-norm equal to one. They argue that, in practice, the infinity-norm is easier to work with, and they therefore replace the 2-norm normalization equation with a linear equation requiring that a particular component of the eigenvector be equal to one (effectively an infinity-norm normalization). Next, they observe that, because of the linearity of the normalization equation, the normalization step is automatically satisfied; the algorithm thus reduces to Newton's method and quadratic convergence follows from standard theory. Peters and Wilkinson choose to dismiss the 2-norm formulation in favor of the infinity-norm formulation; one factor in their choice seems to be that quadratic convergence is not so immediate for the 2-norm formulation. In this work, the authors establish the surprising result that the 2-norm formulation gives a convergence rate of 1+ the square root of 2, significantly superior to that given by the Peters and Wilkinson formulation.