A theory of secant preconditioners

Martínez, José Mario

doi:10.1090/S0025-5718-1993-1176714-X

A theory of secant preconditioners
HTML articles powered by AMS MathViewer

by José Mario Martínez PDF

Math. Comp. 60 (1993), 681-698 Request permission

Abstract:

In this paper we analyze the use of structured quasi-Newton formulae as preconditioners of iterative linear methods when the inexact-Newton approach is employed for solving nonlinear systems of equations. We prove that superlinear convergence and bounded work per iteration is obtained if the preconditioners satisfy a Dennis-Moré condition. We develop a theory of Least-Change Secant Update preconditioners and we present an application concerning a structured BFGS preconditioner.

References

O. Axelsson, A survey of preconditioned iterative methods for linear systems of algebraic equations, BIT 25 (1985), no. 1, 166–187. MR 785811, DOI 10.1007/BF01934996
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
C. G. Broyden, J. E. Dennis Jr., and Jorge J. Moré, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl. 12 (1973), 223–245. MR 341853, DOI 10.1093/imamat/12.3.223

A comprehensive description of LANCELOT

A Model Trust Region Modification of Inexact Newton’s method for nonlinear two point boundary value problems

Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), no. 2, 400–408. MR 650059, DOI 10.1137/0719025

A convergence theory for the structured BFGS secant method with an application to nonlinear least squares

J. E. Dennis Jr. and Earl S. Marwil, Direct secant updates of matrix factorizations, Math. Comp. 38 (1982), no. 158, 459–474. MR 645663, DOI 10.1090/S0025-5718-1982-0645663-8
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 R. B. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Rev. 21 (1979), no. 4, 443–459. MR 545880, DOI 10.1137/1021091
John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
J. E. Dennis Jr. and Kathryn Turner, Generalized conjugate directions, Linear Algebra Appl. 88/89 (1987), 187–209. MR 882447, DOI 10.1016/0024-3795(87)90109-1
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

a set of Fortran subroutines for sparse unsymmetric linear equations

I. S. Duff, A. M. Erisman, and J. K. Reid, Direct methods for sparse matrices, Monographs on Numerical Analysis, The Clarendon Press, Oxford University Press, New York, 1986. Oxford Science Publications. MR 892734
Alan George and Esmond Ng, Symbolic factorization for sparse Gaussian elimination with partial pivoting, SIAM J. Sci. Statist. Comput. 8 (1987), no. 6, 877–898. MR 911061, DOI 10.1137/0908072
Gene H. Golub and Dianne P. O’Leary, Some history of the conjugate gradient and Lanczos algorithms: 1948–1976, SIAM Rev. 31 (1989), no. 1, 50–102. MR 986482, DOI 10.1137/1031003
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Márcia A. Gomes-Ruggiero, José Mario Martínez, and Antonio Carlos Moretti, Comparing algorithms for solving sparse nonlinear systems of equations, SIAM J. Sci. Statist. Comput. 13 (1992), no. 2, 459–483. MR 1149101, DOI 10.1137/0913025
Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 0060307, DOI 10.6028/jres.049.044
David S. Kershaw, The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations, J. Comput. Phys. 26 (1978), no. 1, 43–65. MR 488669, DOI 10.1016/0021-9991(78)90098-0
J. M. Martínez, A quasi-Newton method with a new updating for the $LDU$ factorization of the approximate Jacobian, Mat. Apl. Comput. 2 (1983), no. 2, 131–141 (English, with Portuguese summary). MR 865227
J. M. Martínez, Quasi-Newton methods with factorization scaling for solving sparse nonlinear systems of equations, Computing 38 (1987), no. 2, 133–141 (English, with German summary). MR 889958, DOI 10.1007/BF02240178
José Mario Martínez, A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 27 (1990), no. 4, 1034–1049. MR 1051122, DOI 10.1137/0727061
José Mario Martínez, Local convergence theory of inexact Newton methods based on structured least change updates, Math. Comp. 55 (1990), no. 191, 143–167. MR 1023050, DOI 10.1090/S0025-5718-1990-1023050-5
José Mario Martínez, On the relation between two local convergence theories of least-change secant update methods, Math. Comp. 59 (1992), no. 200, 457–481. MR 1136223, DOI 10.1090/S0025-5718-1992-1136223-X
J. A. Meijerink and H. A. van der Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric $M$-matrix, Math. Comp. 31 (1977), no. 137, 148–162. MR 438681, DOI 10.1090/S0025-5718-1977-0438681-4
Stephen G. Nash, Newton-type minimization via the Lánczos method, SIAM J. Numer. Anal. 21 (1984), no. 4, 770–788. MR 749370, DOI 10.1137/0721052
Stephen G. Nash, Preconditioning of truncated-Newton methods, SIAM J. Sci. Statist. Comput. 6 (1985), no. 3, 599–616. MR 791188, DOI 10.1137/0906042

A study of conjugate-gradient methods

J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Pure and Applied Mathematics, Vol. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations. MR 0359306
Florian-A. Potra and Vlastimil Pták, Sharp error bounds for Newton’s process, Numer. Math. 34 (1980), no. 1, 63–72. MR 560794, DOI 10.1007/BF01463998

The rate of convergence of Newton’s process

25

Youcef Saad, Krylov subspace methods on supercomputers, SIAM J. Sci. Statist. Comput. 10 (1989), no. 6, 1200–1232. Sparse matrix algorithms on supercomputers. MR 1025539, DOI 10.1137/0910073
Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
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
Hubert Schwetlick, Numerische Lösung nichtlinearer Gleichungen, Mathematik für Naturwissenschaft und Technik [Mathematics for Science and Technology], vol. 17, VEB Deutscher Verlag der Wissenschaften, Berlin, 1979 (German). MR 519682
Andrew H. Sherman, On Newton-iterative methods for the solution of systems of nonlinear equations, SIAM J. Numer. Anal. 15 (1978), no. 4, 755–771. MR 483382, DOI 10.1137/0715050

On secant updates for use in general constrained optimization

Yin Zhang and R. P. Tewarson, A new quasi-Newton algorithm, Appl. Math. Lett. 1 (1988), no. 1, 101–104. MR 947174, DOI 10.1016/0893-9659(88)90186-3

Sparse quasi-Newton LDU update

24

David M. Young, A historical overview of iterative methods, Comput. Phys. Comm. 53 (1989), no. 1-3, 1–17. Practical iterative methods for large scale computations (Minneapolis, MN, 1988). MR 1004694, DOI 10.1016/0010-4655(89)90145-8
Zahari Zlatev, Jerzy Wasniewski, and Kjeld Schaumburg, Y12M, Lecture Notes in Computer Science, vol. 121, Springer-Verlag, Berlin-New York, 1981. Solution of large and sparse systems of linear algebraic equations. Documentation of subroutines. MR 649777, DOI 10.1007/3-540-10874-2