ALGORITHMS FOR SOLVING SPARSE NONLINEAR SYSTEMS OF EQUATIONS

[摘要] In this thesis, we present four algorithms for solving sparse nonlinear systems of equations: the partitioned secant algorithm, the CM-successive displacement algorithm, the modified CM-successive displacement algorithm and the combined secant algorithm. The partitioned secant algorithm is a combination of a finite difference algorithm and a secant algorithm which requires one less function evaluation at each iteration than Curtis, Powell and Reid;;s algorithm (the CPR algorithm). The combined secant algorithm is a combination of the partitioned secant algorithm and Schubert;;s algorithm which incorporates the advantages of both algorithms by considering some special structure of the Jacobians to futher reduce the number of function evaluations. The CM-successive displacement algorithm is based on Coleman and More;;s partitioning algorithm and a column update algorithm, and it needs only two function values at each iteration. The modified CM-successive displacement algorithm is a combination of the CM-successive displacement algorithm and Schubert;;s algorithm. It also needs only two function values at each iteration, but it uses the information at every step more effectively. The locally q-superlinear convergence results, the r-convergence order estimates and the Kantorovich-type analyses show that these four algorithms have good local convergence properties. The numerical results indicate that the partitioned secant algorithm and the modified CM-successive displacement algorithm are probably more efficient that the CPR algorithm and Schubert;;s algorithm. In addition to the four algorithms, we give a local convergence result for the CPR algorithm, and we sharpen error estimates and improve Kantorovich-type analyses for both Broyden;;s algorithm and Schubert;;s algorithm.

[发布机构] Rice University