CONVERGENCE AND COMPLEXITY OF NEWTON ITERATIONFOR OPERATOR EQUATIONS
Original Publication Date: 1977-Mar-31
Included in the Prior Art Database: 2007-Mar-28
Software Patent Institute
Traub, J.F.: AUTHOR [+3]
AbstractCONVERGENCE AND COMPLEXITY OF NEWTON ITERATION FOR OPERATOR EQUATIONS J. F. Traub
CONVERGENCE AND COMPLEXITY
OF NEWTON ITERATION FOR OPERATOR EQUATIONS
J. F. Traub
Department of Computer Science Carnegie-Mellon University Pittsburgh, Pennsylvania 15213
Department of Computer Science Carnegie-Mellon University Pittsburgh, PennsylvanLa 152 13 (Visiting from the University of Warsaw)
This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N0014-76- C-0370, NR 044-422.
An optimal convergence condition for Newton iteration in a Banach space is established. There exist problems for which the iteration converges but the complexity is unbounded. We show what stronger condition must be imposed to also assure "good c~mplexity'~.
Numerous papers have analyzed sufficient conditions for the convergence of algorithms for the solution of non-linear problems. In addition to con- vergence, we consider another fundamental question. What stronger conditions must be imposed to assure "good complexityt1? This is clearly one of the crucial issues (in addition to stability) if one is interested in actual com- putation. Ve believe it is also a most interesting theoretical question.
We consider Newton iteration for a simple zero of a non-linear operator in a Banach space of finite or infinite dimension. We establish the optimal radius of tlhe ball of convergence with respect to a certain functional. There exist problems where the iteration converges but the complexity increases log- arithmically to infinity as the initial iterate approaches the boundary of
the ball of convergence. (This phenomenon does not occur in the Kantorovich theory of operator equations; see Section 3.) W e establish the optimal radius of the ball of good complexity.
In this paper we l i m i t ourselves to the important case of Newton iteration. In other papers (Traub and ~okiakowski [76b] and ) we study optimal con- vergence and complexity for classes of iterations.
We summarize the results of this paper. Definitions and theorems con- cerning the optimal ball of convergence are given in Section 2. We conclude this section by giving conditions under which the radius of the ball of con- vergence is a constant fraction of the radius of the ball of analyticity of the operator.
Complexity of Newton iteration is studied in Section 3. We show that Newton iteration may converge but have arbitrarily high complexity and conjec- ture this is a general phenomenon. W e establish the radius of the ball of
good complexity as well as a lower bound...