Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A theory of secant preconditioners


Author: José Mario Martínez
Journal: Math. Comp. 60 (1993), 681-698
MSC: Primary 65H10
DOI: https://doi.org/10.1090/S0025-5718-1993-1176714-X
MathSciNet review: 1176714
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] O. Axelsson, A survey of preconditioned iterative methods for linear systems of algebraic equations, BIT 25 (1985), 166-187. MR 785811 (86e:65047)
  • [2] C. G. Broyden, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comp. 25 (1971), 285-294. MR 0297122 (45:6180)
  • [3] C. G. Broyden, J. E. Dennis, Jr., and J. J. Moré, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl. 12 (1973), 223-245. MR 0341853 (49:6599)
  • [4] A. R. Conn, N. Gould, and Ph. L. Toint, A comprehensive description of LANCELOT, Technical Rep. Hatfield Polytechnique Center, 1990.
  • [5] 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.
  • [6] R. S. Dembo, S. C. Eisenstat, and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 14 (1982), 400-408. MR 650059 (83b:65056)
  • [7] 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.
  • [8] J. E. Dennis and E. S. Marwil, Direct secant updates of matrix factorizations, Math. Comp. 38 (1982), 459-476. MR 645663 (83d:65159)
  • [9] J. E. Dennis and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549-560. MR 0343581 (49:8322)
  • [10] -, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), 46-89. MR 0445812 (56:4146)
  • [11] J. E. Dennis and R. B. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Rev. 21 (1979), 443-459. MR 545880 (80j:65021)
  • [12] -, Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall, Englewood Cliffs, NJ, 1983. MR 702023 (85j:65001)
  • [13] J. E. Dennis and K. Turner, Generalized conjugate directions, Linear Algebra Appl. 88/89 (1986), 187-209. MR 882447 (89c:90094)
  • [14] J. E. Dennis and H. F. Walker, Convergence theorems for least-change secant update methods, SIAM J. Numer. Anal. 18 (1981), 949-987. MR 638993 (83a:65052a)
  • [15] I. S. Duff, MA28--a set of Fortran subroutines for sparse unsymmetric linear equations, AERE R8730, Her Majesty's Stationery Office, London, 1977.
  • [16] I. S. Duff, A. M. Erisman, and J. K. Reid, Direct methods for sparse matrices, Clarendon Press, Oxford, 1986. MR 892734 (88f:65043)
  • [17] A. George and E. Ng, Symbolic factorization for sparse Gaussian elimination with partial pivoting, SIAM J. Sci. Statist. Comput. 8 (1987), 877-898. MR 911061 (89a:65046)
  • [18] G. H. Golub and D. P. O'Leary, Some history of the Conjugate Gradient and Lanczos Algorithms: 1948-1976, SIAM Rev. 31 (1989), 50-102. MR 986482 (90b:65003)
  • [19] G. H. Golub and Ch. F. Van Loan, Matrix computations, The Johns Hopkins Univ. Press, Baltimore and London, 1989. MR 1002570 (90d:65055)
  • [20] M. A. Gomes-Ruggiero, J. M. Martínez, and A. C. Moretti, Comparing algorithms for solving sparse nonlinear systems of equations, SIAM J. Sci. Statist. Comput. 13 (1992), 459-483. MR 1149101 (92j:65077)
  • [21] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards B49 (1952), 409-436. MR 0060307 (15:651a)
  • [22] D. S. Kershaw, The incomplete Cholesky-Conjugate Gradient method for the iterative solution of systems of linear equations, J. Comput. Phys. 26 (1978), 43-65. MR 0488669 (58:8190)
  • [23] 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), 131-142. MR 865227 (87j:65059)
  • [24] -, Quasi-Newton methods with factorization scaling for solving sparse nonlinear systems of equations, Computing 38 (1987), 133-141. MR 889958 (89b:65125)
  • [25] -, A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 27 (1990), 1034-1049. MR 1051122 (91h:65084)
  • [26] -, Local convergence theory of inexact Newton methods based on structured least-change updates, Math. Comp. 55 (1990), 143-168. MR 1023050 (90m:65108)
  • [27] -, On the relation between two local convergence theories of least-change secant update methods, Math. Comp. 59 (1992), 457-481. MR 1136223 (93a:65088)
  • [28] 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. 3 (1977), 148-162. MR 0438681 (55:11589)
  • [29] S. G. Nash, Newton-type minimization via the Lanczos method, SIAM J. Numer. Anal. 21 (1984), 770-787. MR 749370 (86h:65092)
  • [30] -, Preconditioning of truncated-Newton methods, SIAM J. Sci. Statist. Comput. 6 (1985), 599-616. MR 791188 (86i:65035)
  • [31] L. Nazareth and J. Nocedal, A study of conjugate-gradient methods, Report SOL 78-29, Dept. of Operations Res., Stanford University, Stanford, CA, 1978.
  • [32] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
  • [33] A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Academic Press, New York, 1973. MR 0359306 (50:11760)
  • [34] F. A. Potra and V. Pták, Sharp error bounds for Newton's process, Numer. Math. 34 (1980), 63-72. MR 560794 (81c:65027)
  • [35] V. Pták, The rate of convergence of Newton's process, Numer. Math. 25 (1976), 279-285.
  • [36] Y. Saad, Krylov subspace methods of supercomputers, SIAM J. Sci. Statist. Comput. 10 (1989), 1200-1232. MR 1025539 (90k:65113)
  • [37] Y. Saad and M. H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), 856-869. MR 848568 (87g:65064)
  • [38] L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27-30. MR 0258276 (41:2923)
  • [39] H. Schwetlick, Numerische Lösung nichtlinearer Gleichungen, Deutscher Verlag der Wissenschaften, Berlin, 1978. MR 519682 (80f:65061)
  • [40] A. H. Sherman, On Newton-iterative methods for the solution of systems of nonlinear equations, SIAM J. Numer. Anal. 15 (1978), 755-771. MR 0483382 (58:3388)
  • [41] 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.
  • [42] R. P. Tewarson, A new quasi-Newton algorithm, Appl. Math. Lett. 1 (1988), 101-104. MR 947174 (89f:90161)
  • [43] R. P. Tewarson and Y. Zhang, Sparse quasi-Newton LDU update, Internat. J. Numer. Methods Engrg. 24 (1987), 1093-1100.
  • [44] D. M. Young, A historical overview of iterative methods, Comput. Phys. Comm. 53 (1989), 1-18. MR 1004694 (90e:65047)
  • [45] Z. Zlatev, J. Wasniewski, and K. Schaumburg, Y12M. Solution of large and sparse systems of linear algebraic equations, Lecture Notes in Comput. Sci., vol. 121, Springer-Verlag, Berlin and New York, 1981. MR 649777 (83e:65008)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H10

Retrieve articles in all journals with MSC: 65H10


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1176714-X
Keywords: Nonlinear systems, inexact-Newton methods, quasi-Newton methods, preconditioners
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society