Direct secant updates of matrix factorizations
Authors:
J. E. Dennis and Earl S. Marwil
Journal:
Math. Comp. 38 (1982), 459474
MSC:
Primary 65H10
MathSciNet review:
645663
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 Newtonlike 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 qsuperlinearly convergent, and some encouraging numerical results are presented.
 [1]
K.
W. Brodlie, A.
R. Gourlay, and J.
Greenstadt, Rankone and ranktwo corrections to positive definite
matrices expressed in product form, J. Inst. Math. Appl.
11 (1973), 73–82. MR 0331770
(48 #10102)
 [2]
C.
G. Broyden, The convergence of an algorithm for
solving sparse nonlinear systems, Math.
Comp. 25 (1971),
285–294. MR 0297122
(45 #6180), http://dx.doi.org/10.1090/S00255718197102971225
 [3]
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 (80g:65048), http://dx.doi.org/10.1137/0716029
 [4]
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 117119.
 [5]
J.
E. Dennis Jr., A brief introduction to quasiNewton 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
(80d:65003)
 [6]
J.
E. Dennis Jr. and Jorge
J. Moré, A characterization of superlinear
convergence and its application to quasiNewton methods, Math. Comp. 28 (1974), 549–560. MR 0343581
(49 #8322), http://dx.doi.org/10.1090/S00255718197403435811
 [7]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [8]
J.
E. Dennis Jr. and Homer
F. Walker, Convergence theorems for leastchange secant update
methods, SIAM J. Numer. Anal. 18 (1981), no. 6,
949–987. MR
638993 (83a:65052a), http://dx.doi.org/10.1137/0718067
 [9]
J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart, LINPACK User's Guide, SIAM, Philadelphia, Pa., 1979.
 [10]
I. S. Duff, "A survey of sparse matrix research," Proc. IEEE, v. 65, 1977, pp. 500535.
 [11]
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 0345395
(49 #10131)
 [12]
P.
E. Gill, G.
H. Golub, W.
Murray, and M.
A. Saunders, Methods for modifying matrix
factorizations, Math. Comp. 28 (1974), 505–535. MR 0343558
(49 #8299), http://dx.doi.org/10.1090/S00255718197403435586
 [13]
A. Hindmarsh, private communication, 1978.
 [14]
A. Lucia, Thesis, Dept. of Chem. Engr., University of Connecticut, Storrs, 1980.
 [15]
J. J. Moré, B. Garbow & K. Hillstrom, User Guide for MINPACK1, Report ANL8074, Argonne National Laboratories, 1980.
 [16]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 [17]
L.
K. Schubert, Modification of a quasiNewton method
for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 0258276
(41 #2923), http://dx.doi.org/10.1090/S00255718197002582769
 [18]
C. Van Loan, private communication, 1978.
 [19]
J.
H. Wilkinson, The algebraic eigenvalue problem, Clarendon
Press, Oxford, 1965. MR 0184422
(32 #1894)
 [20]
M. Wheeler & T. Potempa, private communication, 1980.
 [1]
 K. W. Brodlie, A. R. Gourlay & J. Greenstadt, "Rankone and ranktwo corrections to positive definite matrices expressed in product form," J. Inst. Math. Appl., v. 11, 1973, pp. 7382. MR 0331770 (48:10102)
 [2]
 C. G. Broyden, "The convergence of an algorithm for solving sparse nonlinear systems," Math. Comp., v. 25, 1971, pp. 285294. MR 0297122 (45:6180)
 [3]
 A. K. Cline, C. B. Moler, G. W. Stewart & J. H. Wilkinson, "An estimate for the condition number of a matrix," SIAM J. Numer. Anal., v. 16, 1979, pp. 368375. MR 526498 (80g:65048)
 [4]
 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 117119.
 [5]
 J. E. Dennis, Jr., "A brief introduction to quasiNewton methods" in Numerical Analysis (Edited by G. Golub and J. Oliger), Proc. Sympos. Appl. Math., vol. 22, Amer. Math. Soc., Providence, R. I., 1978. MR 533049 (80d:65003)
 [6]
 J. E. Dennis, Jr. & J. J. Moré, "A characterization of superlinear convergence and its application to quasiNewton methods," Math. Comp., v. 28, 1974, pp. 549560. MR 0343581 (49:8322)
 [7]
 J. E. Dennis, Jr & J. J. Moré, "QuasiNewton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 4689. MR 0445812 (56:4146)
 [8]
 J. E. Dennis, Jr. & H. F. Walker, "Convergence theorems for leastchange secant update methods," SIAM J. Numer. Anal., v. 18, 1981, pp 949987. MR 638993 (83a:65052a)
 [9]
 J. J. Dongarra, J. R. Bunch, C. B. Moler & G. W. Stewart, LINPACK User's Guide, SIAM, Philadelphia, Pa., 1979.
 [10]
 I. S. Duff, "A survey of sparse matrix research," Proc. IEEE, v. 65, 1977, pp. 500535.
 [11]
 A. M. Erisman & J. K. Reid, "Monitoring the stability of the triangular factorization of a sparse matrix," Numer. Math., v. 22, 1974, pp. 183186. MR 0345395 (49:10131)
 [12]
 P. E. Gill, G. Golub, W. Murray & M. A. Saunders, "Methods for modifying matrix factorizations," Math. Comp., v. 28, 1974, pp. 505535. MR 0343558 (49:8299)
 [13]
 A. Hindmarsh, private communication, 1978.
 [14]
 A. Lucia, Thesis, Dept. of Chem. Engr., University of Connecticut, Storrs, 1980.
 [15]
 J. J. Moré, B. Garbow & K. Hillstrom, User Guide for MINPACK1, Report ANL8074, Argonne National Laboratories, 1980.
 [16]
 J. M. Ortega & W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
 [17]
 L. K. Schubert, "Modification of a quasiNewton method for nonlinear equations with a sparse Jacobian," Math. Comp., v. 24, 1970, pp. 2730. MR 0258276 (41:2923)
 [18]
 C. Van Loan, private communication, 1978.
 [19]
 J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 0184422 (32:1894)
 [20]
 M. Wheeler & T. Potempa, private communication, 1980.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65H10
Retrieve articles in all journals
with MSC:
65H10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198206456638
PII:
S 00255718(1982)06456638
Article copyright:
© Copyright 1982
American Mathematical Society
