---
address: 'Mathematics Department, Kansas State University, Manhattan, KS 66506-2602, USA'
author:
- 'A. G. Ramm'
title: 'Universality of Newton's method'
---

Introduction
============

In many cases one is interested in solving operator equation $$\label{eq1.1}
F(u) = h$$ where $F$ is a nonlinear operator in real Hilbert space $H$. Let us assume that equation has a solution $y$, $$\label{eq1.2}
F(y) = f,$$ that the Fréchet derivative $F'(y)$ exists and is boundedly invertible: $$\label{eq1.3}
\|[F'(y)]^{-1}\|\le m,\qquad m=const >0.$$ Let us also assume that $F'(u)$ exists in the ball $B(y,R):=\{u:\|u-y\|\le R\}$, depends continuously on $u$, and $\omega(R)$ is its modulus of continuity in the ball $B(y,R)$: $$\label{eq1.4}
\sup_{u,v\in B(y,R), \, \|u-v\|\le r} \|F'(u) - F'(v)\| = \omega(r).$$ The function $\omega(r)\ge 0$ is assumed to be continuous on the interval $[0, 2R]$, strictly increasing, and $\omega(0)=0$. A widely used method for solving equation is the Newton method: $$\label{eq1.5} u_{n+1} = u_n -
[F'(u_n)]^{-1}F(u_n), \qquad u_0=z,$$ where $z$ is an initial approximation. Sufficient condition for the convergence of the iterative scheme to the solution $y$ of equation are proposed in @D, @KA, @OR, @R499, and references therein. These conditions in most cases require a Lipschitz condition for $F'(u)$, a sufficient closeness of the initial approximation $u_0$ to the solution $y$, and other conditions ( see, for example, @D, p.157.

In @R499 a general method, the Dynamical Systems Method (DSM) is developed for solving equation .

This method consists of finding a nonlinear operator $\Phi(t,u)$ such that the Cauchy problem $$\label{eq1.6}
\dot{u} = \Phi(t,u),\qquad u(0) = u_0,$$ has a unique global solution $u=u(t;u_0)$, there exists $u(\infty) = \lim_{t\to\infty}u(t;u_0)$, and $F(u(\infty))=f$: $$\label{eq1.7}
\exists ! u(t),\quad \forall t\ge 0;\quad \exists u(\infty);
\quad F(u(\infty)) = f.$$

Many examples of the possible choices of $\Phi(t,u)$ are given in @R499. Theoretical applications of the DSM are proposed in @R489, @R575. A particular choice of $\Phi$, namely, $\Phi = - [F'(u)]^{-1}(F(u)-h)$, leads to a continuous analog of the Newton method: $$\label{eq1.8}
\dot{u}(t) = - [F'(u(t))]^{-1}(F(u(t))-h),\qquad u(0) = u_0; \qquad 
\dot{u}(t) = 
\frac{du(t)}{dt}.$$

The question of general interest is: under what assumptions on $F,h$ and $u_0$, can one establish the conclusions , that is, the global existence and uniqueness of the solution to problem , the existence of $u(\infty)$, and the relation $F(u(\infty))=h?$

The usual condition, sufficient for the local existence and uniqueness of the solution to is the local Lipschitz condition on the right-hand side of . Such condition can be satisfied if $F'(u)$ satisfies a Lipschitz condition.

Our goal is to develop a novel approach to a study of equation . This approach does not require a Lipschitz condition for $F'(u)$, and it leads to a justification of the conclusion (with $h$ replacing $f$) for the solution to problem under natural assumptions on $h$ and $u_0$.

<span>*Apparently for the first time a proof of convergence of the continuous analog of the Newton method and of the usual Newton method is given without any smoothness assumptions on $F'(u)$, only the local continuity of $F'(u)$ is assumed, see .*</span>

The Newton-type methods are widely used in theoretical, numerical and applied research, and by this reason our results are of general interest for a wide audience.

Our results demonstrate the universality of the Newton method in the following sense: we prove that any operator equation can be solved by either the usual Newton method or by the DSM Newton method , provided that conditions - hold, the initial approximation $u_0$ is sufficiently close to $y$, where $y$ is the solution of equation , and the right-hand side $h$ in is sufficiently close to $f$. Precise formulation of the results is given in three Theorems.

The basic tool in this paper is a new version of the inverse function theorem. The novelty of this version is in a specification of the region in which the inverse function exists in terms of the modulus of continuity of the operator $F'(u)$ in the ball $B(y,R)$.

In Section \[section2\] we formulate and prove this version of the inverse function theorem. The result is stated as Theorem \[theorem1\].

In Section \[section3\] we justify the DSM for equation . The result is stated in Theorem \[theorem2\].

In Section \[section4\] we prove convergence of the usual Newton method . The result is stated in Theorem \[theorem3\].

Inverse function theorem {#section2}
========================

Consider equation .

Let us make the following <span>*Assumptions A):*</span>

1.  Equation and estimates , hold in $B(y,R)$,

2.  $h\in B(f,\rho),\qquad \rho = \frac{(1-q)R}{m}, \qquad q\in (0,1),$

3.  $m\omega(R) = q,  \qquad q\in (0,1)$.

Assumption (3) defines $R$ uniquely because $\omega(r)$ is assumed to be strictly increasing. We assume that equation $m\omega(R) = q$ has a solution. This assumption is always satisfied if $q\in (0,1)$ is sufficiently small. The constant $m$ is defined in .

Our first result, Theorem 1, says that under <span>*Assumptions A)*</span> equation is uniquely solvable for any $h$ in a sufficiently small neighborhood of $f$.

\[theorem1\] If Assumptions A) hold then equation has a unique solution $u$ for any $h\in B(f,\rho)$, and $$\label{eq2.1}
\|[F'(u)]^{-1}\| \le \frac {m}{1-q},\qquad \forall u\in B(y,R).$$

Let us denote $$Q:=[F'(y)]^{-1}, \qquad \|Q\|\leq m.$$ Then equation is equivalent to $$\label{eq2.2}
u =T(u), \qquad T(u):= u - Q(F(u) - h).$$ Let us check that $T$ maps the ball $ B(y,R)$ into itself: $$\label{eq2.3}
TB(y,R) \subset B(y,R),$$ and that $T$ is a contraction mapping in this ball: $$\label{eq2.4}
\|T(u) - T(v)\| \le q \|u-v\|, \qquad \forall u,v\in B(y,R),$$ where $q\in (0,1)$ is defined in <span>*Assumptions A)*</span>.

If and are verified, then the contraction mapping principle guarantees existence and uniqueness of the solution to equation in $B(y,R)$, where $R$ is defined by condition 3) in <span>*Assumptions A)*</span>.

Let us check the inclusion . One has $$\label{eq2.5}
J_1:= \|u - y - Q(F(u) - h)\| = \|u - y - Q[F(u) -F(y) +f - h]\|,$$ and $$\label{eq2.6}
\begin{split}
F(u) - F(y) &= \int_0^1 F'(y+s(u-y)) ds (u-y) \\
&= F'(y)(u - y) 
+ \int_0^1 [F'(y+s(u-y)) - F'(y)]ds(u - y).
\end{split}$$ Note that $$\|Q(f-h)\|\le m\rho,$$ and $$\sup_{s\in [0,1]}\|F'(y+s(u-y)) - F'(y)\|\le \omega(R).$$ Therefore, for any $u\in B(y,R)$ one gets from , and the following estimate: $$\label{eq2.7}
J_1 \le m\rho + m\omega(R)R \le (1-q)R+qR=R,$$ where the inequalities $$\label{eq2.8}
\|f-h\| \le \rho, \quad \|u-y\| \le R,$$ and assumptions 2) and 3) in <span>*Assumptions A)*</span> were used.

Let us establish inequality : $$\label{eq2.9}
J_2 := \|T(u) - T(v)\| = \|u - v - Q(F(u) - F(v))\|$$

$$\label{eq2.10}
F(u) - F(v) = F'(y)(u - v) 
+ \int_0^1 [F'(v+s(u-v)) - F'(y)]ds(u - v).$$

Note that $$\|v+s(u-v)-y\|= \|(1-s)(v-y)+s(u-y)\|\leq (1-s)R+sR=R.$$ Thus, from and one gets $$\label{eq2.11}
J_2\le m \omega(R)\|u-v\| \le q\|u-v\|,\qquad \forall u,v\in 
B(y,R).$$ Therefore, both conditions and are verified. Consequently, the existence of the unique solution to in $B(y,R)$ is proved. $\Box$

Let us prove estimate . One has $$\label{eq2.12}
\begin{split}
[F'(u)]^{-1} & = [F'(y) + F'(u) - F'(y)]^{-1}\\
& = [I + (F'(y))^{-1}(F'(u) - F'(y))]^{-1}[F'(y)]^{-1},
\end{split}$$ and $$\label{eq2.13}
\|(F'(y))^{-1}(F'(u) - F'(y))\| \le m \omega(R) \le q,\qquad 
u\in B(y,R).$$ It is well known that if a linear operator $A$ satisfies the estimate $\|A\|\le q$, where $q\in (0,1)$, then the inverse operator $(I+A)^{-1}$ does exist, and $\|(I+A)^{-1}|\le \frac 1 {1-q}$. Thus, the operator $[I + (F'(y))^{-1}(F'(u) - F'(y))]^{-1}$ exists and its norm can be estimated as follows: $$\label{eq2.14}
\|[I + (F'(y))^{-1}(F'(u) - F'(y))]^{-1}\| \le \frac {1}{1-q}.$$ Consequently, and imply .$\Box$

Theorem \[theorem1\] is proved.

\[remark1\] If $h=h(t)\in C^1([0,T])$, then the solution $u=u(t)$ of equation is $C^{1}([0,T])$ provided that Assumptions A) hold.

Indeed, if $h=h(t)$, then a formal differentiation of equation with respect to $t$ yields: $$\label{eq2.15}
F'(u(t))\dot{u}(t) = \dot{h}(t).$$ Since $u(t)\in B(y,R)$, the operator $F'(u(t))$ is boundedly invertible and depends continuously on $t$ because $u(t)$ does. Thus, $$\dot{u}(t) = [F'(u(t))]^{-1}\dot{h}(t),$$ so $\dot{u}(t)$ depends on $t$ continuously.

The formal differentiation is justified if one proves that $u(t)$ is differentiable at any $t\in [0,T]$, that is, $$\label{eq2.16}
u(t+k) - u(t) = A(t)k + o(k),\qquad k\to 0, \qquad t\in [0,T],$$ where $A(t)\in H$ does not depend on $k$ and at the ends of the interval $[0,T]$ the derivatives are understood as one-sided.

To establish relation one uses equation and the assumption $h\in C^1([0,T])$. One has: $$\label{eq2.17}
F(u(t+k)) - F(u(t)) = h(t+k) - h(t) = \dot{h}(t)k + o(k), \qquad k\to 0,$$ and $$\label{eq2.18}
F(u(t+k)) - F(u(t)) = \int_0^1 F'(u(t) + s(u(t+k)-u(t)))ds (u(t+k) - u(t)).$$ The operator $\int_0^1 F'\bigg{(}u(t)+ s(u(t+k) - u(t))\bigg{)}ds$ is boundedly invertible (uniformly with respect to $k\in(0,k_0)$, where $0<k_0$ is a sufficiently small number) as long as $$\sup_{s\in[0,1]}\|u(t)+s(u(t+k)-u(t))-y\|\leq R,$$ see . This inequality holds, as one can easily check: $$\|u(t)+s(u(t+k)-u(t))-y\|=\|(1-s)(u(t)-y)+s(u(t+k)-y)\|\leq 
(1-s)R+sR=R.$$ Therefore, follows from and . Remark \[remark1\] is proved. $\Box$

Convergence of the DSM  {#section3}
=======================

Consider the following equation $$\label{eq3.1}
F(u) = h + v(t),$$ where $$\label{eq3.2}
u = u(t),\quad v(t) = e^{-t} v_0,\quad v_0:= F(u_0) - h,\quad r = \|v_0\|.$$ At $t=0$ equation has a unique solution $u_0$.

Let us make the following <span>*Assumptions B)*</span>:

1.  <span>*Assumptions A)*</span> hold,

2.  $h\in B(f,\delta),\qquad \delta +r\le \rho:=\frac{(1-q)R}{m}.$

\[theorem2\] If Assumptions B) hold, then conclusions , with $f$ replaced by $h$, hold for the solution of problem .

<span>*1. Proof of the global existence and uniqueness of the solution to problem* </span>.

One has $$\|h+v(t) - f\|\le\|h-f\|+\|v_0e^{-t}\|\le \delta+r\leq \rho, \qquad 
  \forall  t\ge 0.$$ Thus, it follows from Theorem \[theorem1\] that equation has a unique solution $$u=u(t)\in B(y,R)$$ defined on the interval $t\in[0,\infty)$, and $u(t)\in C^1([0,\infty))$.

Differentiation of with respect to $t$ yields $$\label{eq3.3}
F'(u)\dot{u} = \dot{v} = -v = - (F(u(t)) - h).$$ Since $u(t)\in B(y,R)$, the operator $F'(u(t))$ is boundedly invertible, so equation is equivalent to . The initial condition $u(0)=u_0$ is satisfied, as was mentioned below . Therefore, the existence of the unique global solution to is proved. $\Box$

<span>*2. Proof of the existence of $u(\infty)$.*</span>

From , , , and it follows that $$\label{eq3.4}
\|\dot{u}\| \le \frac{mr}{1-q}e^{-t}, \qquad q\in (0,1).$$ This and the Cauchy criterion for the existence of the limit $u(\infty)$ imply that $u(\infty)$ exists. $\Box$

Integrating , one gets $$\label{eq3.5}
\|u(t) - u_0\| \le \frac{mr}{1-q},$$ and $$\label{eq3.6}
\|u(\infty) - u(t)\| \le \frac{mr}{1-q} e^{-t}.$$

<span>*3. Proof of the relation $F(u(\infty)) = h$.*</span>

Let us now prove that $$\label{eq3.7}
F(u(\infty)) = h.$$ Relation follows from and as $t\to\infty$, because $v(\infty) = 0$, $u(t)\in B(y,R)$, and $F$ is continuous in $B(y,R)$. $\Box$

Theorem \[theorem2\] is proved.

\[remark2\] Let us explain why there is no assumption on the location of $u_0$ in Theorem \[theorem2\]. The reason is simple: in the proof of Theorem \[theorem2\] it was established that $u(t)\in B(y,R)$ for all $t\geq 0$. Therefore, $u(0)\in B(y,R)$.

The Newton method {#section4}
=================

The main goal in this Section is to prove convergence of the Newton method $$\label{eq4.1}
u_{n+1} = u_n - [F'(u_n)]^{-1}(F(u_n) - f),\qquad u_0 = z,$$ to the solution $y$ of equation . By $z\in H$ we denote an initial approximation.

\[theorem3\] Assume that – and <span>*Assumptions A)*</span> hold, and that $$\label{eq4.2}
m\omega(R)=q\in (0, \frac 1 2), \qquad q_1\|z-y\|\leq R, \qquad q_1:=\frac 
{q}{1-q}.$$ Then process converges to $y$.

One has $$\label{eq4.3}
\begin{split}
u_{n+1} - y &= u_n - y - [F'(u_n)]^{-1}\int_0^1 F'(y+s(u_n-y))ds(u_n - 
y)\\
&= - [F'(u_n)]^{-1}\int_0^1 [F'(y+s(u_n-y)) - F'(u_n)]ds(u_n - y)
\end{split}$$ Let $$a_n := \|u_n - y\|, \qquad a_0=\|z - y\|.$$ Then , and imply $$\label{eq4.4}
a_{n+1} \le \frac {m\omega(R)}{1-q}a_n \le \frac {q}{1-q} a_n:=q_1 a_n.$$ From the assumption $q\in (0, \frac 1 2)$ one derives that $q_1\in (0,1)$. Thus, using , one gets: $$\|u_1 - y\|:=a_1\leq q_1a_0\leq R.$$ By induction one obtains: $$\|u_n - y\|\le R, \qquad  \forall n=1,2,3,.....$$ Consequently, $u_n\in B(y,R)$ for all $n$, and estimates and are applicable for all $n$. Therefore, implies $$\label{eq4.5}
a_n \le q_1^{n-1} R, \qquad \forall n=1,2,3,.....  .$$ Therefore, $$\lim_{n\to \infty}a_n=0.$$ Theorem \[theorem3\] is proved.

<span>99</span> K. Deimling, <span>*Nonlinear functional analysis*</span>, Springer-Verlag, Berlin, 1985. L. Kantorovich, G. Akilov, <span>*Functional analysis*</span>, Pergamon Press, New York, 1982.

J. Ortega, W. Rheinboldt, <span>*Iterative solution of nonlinear equations in several variables*</span>, SIAM, Philadelphia, 2000.

A. G. Ramm, <span>*Dynamical systems method for solving operator equations*</span>, Elsevier, Amsterdam, 2007. A. G. Ramm, <span>*Inverse problems*</span>, Springer, New York, 2005.

A. G. Ramm, Dynamical systems method and a homeomorphism theorem, <span>*Amer. Math. Monthly*</span>, 113, N10, (2006), 928-933.

A. G. Ramm, Implicit function theorem via the DSM, <span>*Nonlinear Analysis: Theory, Methods and Appl.,*</span> doi:10.1016/j.na.2009.09.032

A. G. Ramm, Dynamical systems method for solving operator equations, <span>*Communic. in Nonlinear Sci. and Numer. Simulation*</span>, 9, N2, (2004), 383-402.

A. G. Ramm, Dynamical systems method (DSM) and nonlinear problems, in the book: <span>*Spectral Theory and Nonlinear Analysis*</span>, World Scientific Publishers, Singapore, 2005, 201-228. (ed J. Lopez-Gomez).

{'source': 'arXiv_out/0911'}