Sparse Quasi-Newton Methods and the Continuation ProblemStanford University, 1985 - 127 pages 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. |
Common terms and phrases
Ak+1 approximation classical continuation computational continuation methods continuation problem convergence corrector sequence corrector steps corrector technique curve D₁ defined Dennis and Marwil Denote differential equations E₁ Eaves estimate Figure Final Iterates finite difference fixed point Function Evaluations Garcia and Zangwill Gaussian elimination Hence homotopy problem hyperplane IL(x implicit function theorem Iterates at Level Jacobian matrix k₁ k₂ Lemma linear LU decomposition LU factors Math Newton step Newton's method nonlinear nonsingular numerical obtain optimization path path-following techniques permutation matrix pivoting strategy polynomial predictor step predictor-corrector algorithm Predictor-Corrector Cycles predictor-corrector method Proof quasi-Newton methods Rheinboldt Sard's Theorem satisfies SIAM simplicial techniques smooth one-dimensional manifold solution solve SPARSE MATRIX sparsity pattern Stanford steplength control steplength strategy subspace systems of equations tangent directions Theorem tracing triangulation Type of Update Update Dimension updating techniques Wacker Watson Y₁ zero