Browse Prior Art Database

CONVERGENCE AND COMPLEXITY OF NEWTON ITERATIONFOR OPERATOR EQUATIONS

IP.com Disclosure Number: IPCOM000147947D
Original Publication Date: 1977-Mar-31
Included in the Prior Art Database: 2007-Mar-28

Publishing Venue

Software Patent Institute

Related People

Traub, J.F.: AUTHOR [+3]

Abstract

CONVERGENCE AND COMPLEXITY OF NEWTON ITERATION FOR OPERATOR EQUATIONS J. F. Traub Department of Computer Science Carnegie-Mellon University Pittsburgh, Pennsylvania 15213 H . ~o&iakowski Department of Computer Science Carnegie-Mellon University Pittsburgh, PennsylvanLa 152 13 (Visiting from the University of Warsaw) March 1977 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. ABSTRACT 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'~. 1. INTRODUCTION 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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 24

CONVERGENCE AND COMPLEXITY

OF NEWTON ITERATION FOR OPERATOR EQUATIONS
J. F. Traub

Department of Computer Science Carnegie-Mellon University Pittsburgh, Pennsylvania 15213

H
. ~o&iakowski

    Department of Computer Science Carnegie-Mellon University Pittsburgh, PennsylvanLa 152 13 (Visiting from the University of Warsaw)

March 1977

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.

[This page contains 1 picture or other non-text object]

Page 2 of 24

[This page contains 1 picture or other non-text object]

Page 3 of 24

ABSTRACT

    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'~.

[This page contains 1 picture or other non-text object]

Page 4 of 24

[This page contains 1 picture or other non-text object]

Page 5 of 24

1. INTRODUCTION

    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 [77]) 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...