Sparse Quasi-Newton Methods and the Continuation Problem.
Abstract
The problem of tracing a smooth path arises in many engineering problems, the solution of parametric differential equations and eigenvalue problems; it also finds application in the solution of nonlinear systems of equations by homotopy techniques. In many instances, the path is defined implicitly as the solution of a system of equations whose Jacobian matrix is large and sparse. Robust simplicial path-following techniques cannot be applied to large problems since the work involved rises rapidly with increasing dimension. This dissertation addresses the numerical problems involved in tracing the path for large sparse systems by the use of a predictor-corrector algorithm. We investigate the use of sparse quasi-Newton techniques to reduce the expense of the convector phase of the predictor-corrector algorithm inherent in Newton's method. In order to avoid the drawbacks of the sparse Broyden method - the need for a matrix factorization on each iterate and the need to store both the Jacobian matrix and its factors - we examine techniques for directly updating the LU factors of the approximation to the Jacobian matrix. Under reasonable assumptions on the systems of equations to be solved, a proof of local Q-superlinear convergence is presented for two sparse updating techniques. A predictor-corrector algorithm employing these sparse updating techniques is implemented in a Fortran code and numerical results are obtained demonstrating the advantages to be gained from the use of quasi-Newton methods for the large sparse continuation problem.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1985
- Accession Number
- ADA157587
Entities
People
- F. F. Chadee
Organizations
- Stanford University