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. R. Conn, N. Gould, and Ph. L. Toint, A comprehensive description of LANCELOT, Technical Rep. Hatfield Polytechnique Center, 1990. E. J. Dean, A Model Trust Region Modification of Inexact Newton’s method for nonlinear two point boundary value problems, TR No. 85-6, Dept. of Math. Sci., Rice University, Houston, Texas, 1985.
- 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 J. E. Dennis, H. J. Martínez, and R. A. Tapia, A convergence theory for the structured BFGS secant method with an application to nonlinear least squares, Technical Rep. 87-15, Dept. of Math. Sci., Rice University, Houston, Texas, 1988.
- 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 I. S. Duff, MA28—a set of Fortran subroutines for sparse unsymmetric linear equations, AERE R8730, Her Majesty’s Stationery Office, London, 1977.
- 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 L. Nazareth and J. Nocedal, A study of conjugate-gradient methods, Report SOL 78-29, Dept. of Operations Res., Stanford University, Stanford, CA, 1978.
- 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 V. Pták, The rate of convergence of Newton’s process, Numer. Math. 25 (1976), 279-285.
- 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 R. A. Tapia, On secant updates for use in general constrained optimization, Technical Rep. 84-3, Dept. of Math. Sci., Rice University, Houston, Texas, 1987.
- 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 R. P. Tewarson and Y. Zhang, Sparse quasi-Newton LDU update, Internat. J. Numer. Methods Engrg. 24 (1987), 1093-1100.
- 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
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 60 (1993), 681-698
- MSC: Primary 65H10
- DOI: https://doi.org/10.1090/S0025-5718-1993-1176714-X
- MathSciNet review: 1176714