Abstract
In this paper, we consider the use of bounded-deterioration quasi-Newton methods implemented in floating-point arithmetic to find solutions to F(x)=0 where only inaccurate F-values are available. Our analysis is for the case where the relative error in F is less than one. We obtain theorems specifying local rates of improvement and limiting accuracies depending on the nearness to Newton’s method of the basic algorithm, the accuracy of its implementation, the relative errors in the function values, the accuracy of the solutions of the linear system for the Newton steps, and the unit-rounding errors in the addition of the Newton steps.
Research sponsored by DOE DE-AS05-82ER13016, ARO DAAG-79-C-0124, NSF MCS81-16779. This work was supported in part by the International Business Machine Corporation, Palo Alto Scientific Center, Palo Alto, CA.
Research sponsored by DOE DE-AS05-82ER13016.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
C.G. Broyden, J.E. Dennis Jr and J.J. Moré, “On the local and superlinear convergence of quasi-Newton methods”, Journal of the Institute of Mathematics and its Applications 34 (1973) 223–245.
L. Collatz, Functional analysis and numerical analysis (Academic Press, New York, 1966).
J.E. Dennis Jr. and R.B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations (Prentice-Hall, Englewood Cliffs, 1983).
J.E. Dennis Jr. and H.F. Walker, “Convergence theorems for least-change secant update methods”, SIAM Journal on Numerical Analysis 18 (1981) 949–987.
J.J. Dongarra, J.R. Bunch, C.B. Moler and G.W. Stewart, LINPACK users’ guide (SIAM Publications, Philadelphia, 1979).
T. Glad and A. Goldstein, “Optimization of functions whose values are subject to small errors”, BIT: Nordisk Tidskrift for Informations-behandling 17 (1977) 160–169.
P. Lancaster, “Error analysis for the Newton-Raphson method”, Numerische Mathematik 9 (1966) 55–68.
C.B. Moler, “Iterative refinement in floating-point”, Journal of the Association for Computing Machinery 14 (1967) 316–321.
J.M. Ortega and W.C. Rheinboldt, Iterative solution of nonlinear equations in several variables (Academic Press, New York, 1970).
G.W. Stewart, Introduction to matrix computations (Academic Press, New York, 1973).
M. Urabe, “Error estimation in numerical solution of equations by iterations process”, Journal of Science of Hiroshima University 19 (1956) 479–489
J.H. Wilkinson, Rounding errors in algebraic processes (Prentice-Hall, Englewood Cliffs, 1963).
J.H. Wilkinson, The algebraic eigenvalue problem (Oxford University Press, Oxford, 1965).
P. Young, “Optimization in the presence of noise—a guided tour”, in: L.C.W. Dixon, ed., Optimization in action (Academic Press, London, 1976) pp. 517–573.
T.J. Ypma, “The effect of rounding errors on Newton-like methods”, Institute of Mathematics and its Applications Journal for Numerical Analysis 3 (1983) 109–118.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1984 The Mathematical Programming Society, Inc.
About this chapter
Cite this chapter
Dennis, J.E., Walker, H.F. (1984). Inaccuracy in quasi-Newton methods: Local improvement theorems. In: Korte, B., Ritter, K. (eds) Mathematical Programming at Oberwolfach II. Mathematical Programming Studies, vol 22. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121009
Download citation
DOI: https://doi.org/10.1007/BFb0121009
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00914-3
Online ISBN: 978-3-642-00915-0
eBook Packages: Springer Book Archive