Abstract:This paper presents a new context for using the sparse Broyden update method to solve systems of nonlinear equations. The setting for this work is that a Newton-like algorithm is assumed to be available which incorporates a workable strategy for improving poor initial guesses and providing a satisfactory Jacobian matrix approximation whenever required. The total cost of obtaining each Jacobian matrix, or the cost of factoring it to solve for the Newton step, is assumed to be sufficiently high to make it attractive to keep the same Jacobian approximation for several steps. This paper suggests the extremely convenient and apparently effective technique of applying the sparse Broyden update directly to the matrix factors in the iterations between reevaluations in the hope that fewer fresh factorizations will be required. The strategy is shown to be locally and q-superlinearly convergent, and some encouraging numerical results are presented.
- K. W. Brodlie, A. R. Gourlay, and J. Greenstadt, Rank-one and rank-two corrections to positive definite matrices expressed in product form, J. Inst. Math. Appl. 11 (1973), 73–82. MR 331770
- C. G. Broyden, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comp. 25 (1971), 285–294. MR 297122, DOI 10.1090/S0025-5718-1971-0297122-5
- A. K. Cline, C. B. Moler, G. W. Stewart, and J. H. Wilkinson, An estimate for the condition number of a matrix, SIAM J. Numer. Anal. 16 (1979), no. 2, 368–375. MR 526498, DOI 10.1137/0716029 A. R. Curtis, M. J. D. Powell & J. K. Reid, "On the estimation of sparse Jacobian matrices," J. Inst. Math. Appl., v. 13, 1974, pp 117-119.
- J. E. Dennis Jr., A brief introduction to quasi-Newton methods, Numerical analysis (Proc. Sympos. Appl. Math., Atlanta, Ga., 1978) Proc. Sympos. Appl. Math., XXII, Amer. Math. Soc., Providence, R.I., 1978, pp. 19–52. MR 533049
- J. E. Dennis Jr. and Jorge J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549–560. MR 343581, DOI 10.1090/S0025-5718-1974-0343581-1
- J. E. Dennis Jr. and Jorge J. Moré, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), no. 1, 46–89. MR 445812, DOI 10.1137/1019005
- J. E. Dennis Jr. and Homer F. Walker, Convergence theorems for least-change secant update methods, SIAM J. Numer. Anal. 18 (1981), no. 6, 949–987. MR 638993, DOI 10.1137/0718067 J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart, LINPACK User’s Guide, SIAM, Philadelphia, Pa., 1979. I. S. Duff, "A survey of sparse matrix research," Proc. IEEE, v. 65, 1977, pp. 500-535.
- A. M. Erisman and J. K. Reid, Monitoring the stability of the triangular factorization of a sparse matrix, Numer. Math. 22 (1973/74), 183–186. MR 345395, DOI 10.1007/BF01436966
- P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders, Methods for modifying matrix factorizations, Math. Comp. 28 (1974), 505–535. MR 343558, DOI 10.1090/S0025-5718-1974-0343558-6 A. Hindmarsh, private communication, 1978. A. Lucia, Thesis, Dept. of Chem. Engr., University of Connecticut, Storrs, 1980. J. J. Moré, B. Garbow & K. Hillstrom, User Guide for MINPACK-1, Report ANL-80-74, Argonne National Laboratories, 1980.
- J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
- L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 258276, DOI 10.1090/S0025-5718-1970-0258276-9 C. Van Loan, private communication, 1978.
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422 M. Wheeler & T. Potempa, private communication, 1980.
- © Copyright 1982 American Mathematical Society
- Journal: Math. Comp. 38 (1982), 459-474
- MSC: Primary 65H10
- DOI: https://doi.org/10.1090/S0025-5718-1982-0645663-8
- MathSciNet review: 645663