Convergence and Complexity of Newton Iteration for Operator Equations

Abstract

An optmaal convergence condmon for Newton ~teratmn m a Banach space ts estabhshed It ~s shown that there exist problems for whtch the ~teraUon converges but the complextty ts unbounded Thus for actual computation convergence ~s not enough What stronger condmon must be unposed to also assure "good complextty" ~s shown CR CATEGORIES 5 15, 5 25 1. Introductwn Numerous papers have analyzed sufficient conditions for the convergence of algonthms for the solution of nonlinear problems. In addRion to convergence, we consider another fundamental question. What stronger conditions must be imposed to assure "good com- plexity?" This is deafly one of the crucial issues (m addmon to stability) if one is interested in actual computation. We beheve it is also a most interesting theoretical quesUon. We consider Newton iteration for a simple zero of a nonlinear operator in a Banach space of finite or infmite dimension. We establish the opUmal radius of the ball of convergence with respect to a certain functional. There exist problems where the iteration converges but the complexity increases logarithmically 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.) We estabhsh the optimal radius of the ball of good complexity. In this paper we limit ourselves to the important case of Newton iteration. In other papers (8-10) we study optimal convergence and complexRy for classes of iterations. We summarize the results of this paper. Definitions and theorems concerning 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 convergence is a constant fraction of the radius of the ball of analytioty of the operator. Complexity of Newton iteration ~s studied in Secuon 3. We show that Newton iteration may converge but have arbitrarily high complexity and conjecture that thts is a general phenomenon. We establish the radms of the ball of good complexity as well as a lower bound on the complexity of Newton iteration.