Projected Newton for the Symmetric Eigenvalue Problem has Order 1+sqrt(2)
Whitley, David L.
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 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 we establish the surprising result that the 2-norm formulation gives a convergence rate of 1+sqrt(2), significantly superior to that given by the Peters and Wilkinson formulation.
Citable link to this pagehttps://hdl.handle.net/1911/101625
MetadataShow full item record
- CAAM Technical Reports