ALGORITHMS FOR SOLVING SPARSE NONLINEAR SYSTEMS OF EQUATIONS
Doctor of Philosophy
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.