Abstract
A quadratically convergent algorithm based on a Newton-type iteration is defined to approximate roots of operator equations in Banach spaces. Fréchet derivative operator invertibility is not required; approximate right inverses are used in a neighborhood of the root. This result, which requires an initially small residual, is sufficiently robust to yield existence; it may be viewed as a generalized version of the Kantorovich theorem. A second algorithm, based on continuation via single, Euler-predictor-Newton-corrector iterates, is also presented. It has the merit of controlling the residual until the homotopy terminates, at which point the first algorithm applies. This method is capable of yielding existence of a solution curve as well. An application is given for operators described by compact perturbations of the identity.
Similar content being viewed by others
References
M. Altman (1980):Iterative methods of contractor directions. Nonlinear Anal.,4:761–772.
P. Anselone (1971): Collectively Compact Operator Approximation Theory. Englewood Cliffs, New Jersey: Prentice-Hall.
R. Bank, D. Rose (1981):Global approximate Newton methods. Numer. Math.,37:279–295.
R. Bank, D. Rose, W. Fichtner (1983):Numerical methods for semiconductor simulation. SIAM J. Sci. Stat. Comp.,4:416–435.
T. Chan, H. Keller (1982):Arc-length continuation and multi-grid techniques for nonlinear elliptic eigenvalue problems. SIAM J. Sci. Stat. Comp.,3:173–194.
S. Chow, J. Mallet-Paret, J. Yorke (1978):Finding zeros of maps: Homotopy methods that are constructive with probability one. Math. Comput.,32:887–899.
R. Dembo, S. Eisenstat, T. Steihaug (1982):Inexact Newton methods. SIAM J. Numer. Anal.,19:400–408.
C. Den Heijer, W. Rheinboldt (1981):On steplength algorithms for a class of continuation methods. SIAM J. Numer. Anal.,18:925–948.
J. Dennis, Jr. (1968):On Newton-like methods. Numer. Math.,11:324–330.
J. Dennis, Jr. (1969):On the Kantorovich hypothesis for Newton's method. SIAM J. Numer. Anal.,6:493–507.
J. Fink, W. Rheinboldt (1983):On the discretization error of parametrized nonlinear equations. SIAM J. Numer. Anal.,20:732–746.
W. Gragg, R. Tapia (1974):Error bounds for the Newton-Kantorovich theorem. SIAM J. Numer. Anal.,11:10–13.
J. Jerome (1984): An Adaptive Newton Algorithm Based on Numerical Inversion: Regularization as Postconditioner. Minneapolis: Institute for Mathematics and Its Applications (IMA Preprint Series No. 76, June 1984). Numer. Math., in press.
J. Jerome (1984):Fixed point and implicit function theorems and their applications. In: Proceedings, Anniversary Volume on Approximation Theory and Functional Analysis (P. Butzer, R. Stens, B. Szokefalvi-Nagy, eds.). Basel: Birkhäuser-Verlag, pp. 495–509.
J. Jerome (in press):A criterion for isolated solution structure and global computability for operator equations. Freud commemorative issue, J. Approx. Theory.
L. Kantorovich (1952): Functional Analysis and Applied Mathematics (C. Benster, transl.). Washington, D.C.: National Bureau of Standards (National Bureau of Standards Report 1509).
L. Kantorovich, G. Akilov (1964): Functional Analysis in Normed Spaces. New York: Pergamon Press.
R. Kellogg, T. Li, J. Yorke (1976):A constructive proof of the Brouwer fixed-point theorem and computational results. SIAM J. Numer. Anal.,13:473–483.
M. Krasnosel'skii, Ya. Rutickii (1961):Some approximate methods of solving nonlinear operator equations based on linearization. Soviet Math. Doklady2:1542–1546.
L. Nirenberg (1973–1974): Topics in Nonlinear Functional Analysis. New York: Courant Institute of Mathematical Sciences, New York University.
J. Ortega (1968):The Newton-Kantorovich Theorem. Amer. Math. Monthly,75:658–660.
J. Ortega, W. Rheinboldt (1970): Iterative Solution of Nonlinear Equations in Several Variables. New York: Academic Press.
A. Ostrowski (1960): Solution of Equations and Systems of Equations. New York: Academic Press.
L. Rall, R. Tapia (1970): The Kantorovich Theorem and Error estimates for Newton's Method. Madison, Wisconsin: (Mathematics Research Center Tech. Summary Report 1043).
W. Rheinboldt (1968):A unified convergence theory for a class of iterative processes. SIAM J. Numer. Anal.,5:42–63.
W. Rheinboldt (1980):Solution fields of nonlinear equations and continuation methods. SIAM J. Numer. Anal.,17:221–237.
R. Tapia (unpublished manuscript):Remarks on the Kantorovich theorem.
R. Tapia (1971):The Kantorovich theorem for Newton's method. Amer. Math. Monthly,78:389–392.
A. Taylor (1961): Introduction to Functional Analysis. New York: John Wiley & Sons.
L. Watson (1979):A globally convergent algorithm for computing fixed points of C 2 maps. Appl. Math. Comput.,5:297–311.
L. Watson, D. Fenner (1980):Chow-Yorke algorithm for fixed points or zeros of C 2 maps. ACM TAMS,6:252–259.
A. Wouk (1969): A Course of Applied Functional Analysis. New York: John Wiley & Sons.
Author information
Authors and Affiliations
Additional information
Communicated by William B. Gragg.
Rights and permissions
About this article
Cite this article
Jerome, J.W. Approximate Newton methods and homotopy for stationary operator equations. Constr. Approx 1, 271–285 (1985). https://doi.org/10.1007/BF01890035
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01890035