Direct secant updates of matrix factorizations

Dennis, J. E.; Marwil, Earl S.

doi:10.1090/S0025-5718-1982-0645663-8

Direct secant updates of matrix factorizations
HTML articles powered by AMS MathViewer

by J. E. Dennis and Earl S. Marwil PDF

Math. Comp. 38 (1982), 459-474 Request permission

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.

References

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

J. Inst. Math. Appl.

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

LINPACK User’s Guide, SIAM

Proc. IEEE

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

User Guide for MINPACK

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
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422