# Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

## A characterization of superlinear convergence and its application to quasi-Newton methodsHTML articles powered by AMS MathViewer

by J. E. Dennis and Jorge J. Moré
Math. Comp. 28 (1974), 549-560 Request permission

## Abstract:

Let F be a mapping from real n-dimensional Euclidean space into itself. Most practical algorithms for finding a zero of F are of the form \[ {x_{k + 1}} = {x_k} - B_k^{ - 1}F{x_k},\] where \$\{ {B_k}\}\$ is a sequence of nonsingular matrices. The main result of this paper is a characterization theorem for the superlinear convergence to a zero of F of sequences of the above form. This result is then used to give a unified treatment of the results on the superlinear convergence of the Davidon-Fletcher-Powell method obtained by Powell for the case in which exact line searches are used, and by Broyden, Dennis, and Moré for the case without line searches. As a by-product, several results on the asymptotic behavior of the sequence \$\{ {B_k}\}\$ are obtained. An interesting aspect of these results is that superlinear convergence is obtained without any consistency conditions; i.e., without requiring that the sequence \$\{ {B_k}\}\$ converge to the Jacobian matrix of F at the zero. In fact, a modification of an example due to Powell shows that most of the known quasi-Newton methods are not, in general, consistent. Finally, it is pointed out that the above-mentioned characterization theorem applies to other single and double rank quasi-Newton methods, and that the results of this paper can be used to obtain their superlinear convergence.
References
K. M. Brown & J. E. Dennis, Jr., "A new algorithm for nonlinear least-squares curve fitting," in Mathematical Software, John R. Rice, Editor, Academic Press, New York, 1971, pp. 391-396. C. G. Broyden, J. E. Dennis & J. J. Moré, On the Local and Superlinear Convergence of Quasi-Newton Methods, Cornell Computer Science Technical Report 72-137, 1972; J. Inst. Math. Appl. (To appear.) R. Fletcher, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317-322.
• A. A. Goldstein and J. F. Price, An effective algorithm for minimization, Numer. Math. 10 (1967), 184–189. MR 217995, DOI 10.1007/BF02162162
• H. Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, J. Optim. Theory Appl. 5 (1970), 405–423. MR 288939, DOI 10.1007/BF00927440
• Garth P. McCormick and Klaus Ritter, Methods of conjugate directions versus quasi-Newton methods, Math. Programming 3 (1972), 101–116. MR 302204, DOI 10.1007/BF01584978
• J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
• M. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl. 7 (1971), 21–36. MR 279977
• M. J. D. Powell, Private communication, 1972. K. Ritter, "Superlinearly convergent methods for unconstrained minimization problems," Proc. ACM, Boston, 1972, pp. 1137-1145. R. Voigt, Rates of Convergence for Iterative Methods for Nonlinear Systems of Equations, Ph.D. Thesis, University of Maryland, College Park, Md., 1969.
Similar Articles
• Retrieve articles in Mathematics of Computation with MSC: 65H05
• Retrieve articles in all journals with MSC: 65H05