Local convergence of Newton’s method using Kantorovich convex majorants

Ioannis K. Argyros\(^\ast \)

December 23, 2007.

\(^\ast \) Cameron University, Department of Mathematics Sciences, Lawton, OK 73505, USA, e-mail: iargyros@cameron.edu

We are concerned with the problem of approximating a solution of an operator equation using Newton’s method. Recently in the elegant work by Ferreira and Svaiter [ 6 ] a semilocal convergence analysis was provided which makes clear the relationship of the majorant function with the operator involved. However these results cannot provide information about the local convergence of Newton’s method in their present form. Here we have rectified this problem by using two flexible majorant functions. The radius of convergence is also found. Finally, under the same computational cost, we show that our radius of convergence is larger, and the error estimates on the distances involved is finer than the corresponding ones [ 1 ] , [ 11 ] – [ 13 ] .

MSC. 65G99, 65K10, 47H17, 49M15, 90C30.

Keywords. Newton’s method, Banach space, Kantorovich’s majorants, convex function, local/semilocal convergence, Fréchet–derivative, radius of convergence.

1 Introduction

In this study we are concerned with the problem of approximating a solution \(x^\star \) of equation

\begin{equation} \label{1.1} F(x) =0, \end{equation}

1.1

where \(F\) is a continuously Fréchet–differentiable operator defined on a convex subset \(\mathcal D\) of a Banach space \(\mathcal X\) with values in a Banach space \(\mathcal Y\).

A large number of problems in applied mathematics and also in engineering are solved by finding the solutions of certain equations. For example, dynamic systems are mathematically modeled by difference or differential equations, and their solutions usually represent the states of the systems. For the sake of simplicity, assume that a time–invariant system is driven by the equation \(\dot{x} =Q(x)\), for some suitable operator \(Q\), where \(x\) is the state. Then the equilibrium states are determined by solving equation (1.1). Similar equations are used in the case of discrete systems. The unknowns of engineering equations can be functions (difference, differential, and integral equations), vectors (systems of linear or nonlinear algebraic equations), or real or complex numbers (single algebraic equations with single unknowns). Excpet in special cases, the most commonly used solution methods are iterative–when starting from one or several initial approximations a sequence is constructed that converges to a solution of the equation. Iteration methods are also applied for solving optimization problems. In such cases, the iteration sequences converge to an optimal solution of the problem at hand. Since all of these methods have the same recursive structure, they can be introduced and discussed in a general framework.

The most popular method for generating a sequence \(\{ x_n \} \) approximating \(x^\star \) is undoubtedly Newton’s method:

\begin{equation} \label{1.2} x_0 \in \mathcal D,\qquad x_{n+1}=x_n - F'(x_n)^{-1}\, F(x_n) \quad (n \geq 0). \end{equation}

1.2

Here \(F'(x) \in \mathcal L(\mathcal X, \mathcal Y)\), the space of bounded linear operators from \(\mathcal X\) into \(\mathcal Y\), denotes the Fréchet–derivative of operator \(F\) [ 4 ] , [ 8 ] .

There is an extensive literature on local as well as semilocal convergence theorems for Newton’s method, see, e.g. [ 1 ] – [ 4 ] , and the references there.

In particuar, we are motivated by the elegant work of Ferreira and Svaiter [ 6 ] where a semilocal convergence was provided for Kantorovich’s theorem [ 8 ] which makes clear the relationship of the majorant function and operator \(F\). However the main result (see Theorem 2 in [ 6 ] ) cannot provide in its present form information about the local convergence of Newton’s method. Here, we rectify this problem. We introduce two flexible majorant functions to provide a local convergence for Newton’s method (1.2). The radius of convergence is also given.

Finally, under the same computational cost we show that for special choices of the majorants functions involved, our radius of convergence is larger, and the error estimates on the distances involved is finer than the corresponding ones [ 1 ] , [ 11 ] – [ 13 ] .

2 Local convergence analysis of Newton’s method (1.2)

We need a result from convex analysis [ 9 ] , [ 10 ] :

Proposition 2.1

Let \(\mathcal I\subset (-\infty , +\infty ) \) be an interval, and \(g:\, \mathcal I\longrightarrow (-\infty , +\infty ) \) be convex.

For any \(s_0 \in {\rm int}\, (\mathcal I)\), the correspondence \( \displaystyle s \longrightarrow \displaystyle \tfrac {g(s_0) -g(s)}{s_0 - s}\), \(s \in I\), \(s \neq s_0\), is increasing, and there exist in \((-\infty , +\infty )\)

\[ \begin{array}{lll} D^{-}g(s_0)= \displaystyle \lim _{s \rightarrow s_0^-} \displaystyle \tfrac {g(s_0) -g(s)}{s_0 - s}= \displaystyle \sup _{s {\lt} s_0} \displaystyle \tfrac {g(s_0) -g(s)}{s_0 - s}. \end{array} \]
If \(s,v,t \in \mathcal I\), \(s {\lt} t\), and \(s \leq t \leq v\), then

\[ g(t) -g(s) \leq (g(v)- g(s)) \, \, \displaystyle \tfrac {t-s}{v-s}. \]

We now state a portion of a theorem (see Theorem 2 in [ 6 ] ) due to Ferreira and Svaiter, needed for what follows:

Theorem 2.2

Let \(F\, : \, \, \mathcal D\subseteq \mathcal X\longrightarrow \mathcal Y\) be a continuous operator, continuously Fréchet–differentiable on \( {\rm int} \, \, (\mathcal D) \). Take \(x_0 \in {\rm int} \, \, (\mathcal D) \) with \(F'(x_0)^{-1} \in \mathcal L(\mathcal Y, \mathcal X)\). Suppose there exist \(R{\gt}0\), and a continuously differentiable function \(f \, : \, [0,R)\longrightarrow (-\infty ,+\infty )\), such that \( U(x_0 , R ) =\{ x \in \mathcal X, \, :\, \parallel x -x_0 \parallel {\lt} R \} \linebreak \subset \mathcal D\), and

\(\parallel F'(x_0)^{-1} \, \, (F'(y)\! -\! F'(x))\parallel \leq f'(\parallel y\! -\! x \parallel \! +\! \parallel x\! -\! x_0 \parallel ) \! -\! f'(\parallel x \! -\! x_0 \parallel ), \, \, \\ \hspace*{1cm} {\rm for} \, \, x, y \in U(x_0 , R ) ,\quad \parallel x -x_0 \parallel + \parallel y - x \parallel {\lt} R,\)
\(\parallel F'(x_0)^{-1} \, \, F(x_0) \parallel \leq f(0),\)
\(f(0) {\gt} 0,\)
\(f'(0) = -1,\)
\(f'\, \, {\rm is \, \, convex \, \, and \, \, strictly \, \, increasing \, \, and}\, \, f(t)=0\, \, {\rm for \, \, some }\, \, t \in (0,R).\)

Then \(f\) has a smallest zero \(t_{\star }\) in \((0,R)\), the sequences generated by Newton’s method (1.2) for solving \(f(t)=0\), and \(F(x)=0\) with starting point \(t_0 =0\) and \(x_0\), respectively,

\[ t_{n+1} = t_n - f'(t_n)^{-1} \, \, f(t_n),\qquad x_{n+1} = x_n - F'(x_n) ^{-1} \, \, F(x_n),\quad n\geq 0 \]

are well defined, \(\{ t_n \} \) is strictly increasing, is contained in \([0, t_{\star } )\), and converges to \(t_{\star } \), \(\{ x _n \} \) is contained in \(U(x_0 , t_{\star } )\), and converges to a point \(x^\star \) in \(\overline{U} (x_0 , t_{\star } )\), which is the unique zero of \(F\) in \(\overline{U} (x_0 , t_{\star } )\).

Theorem 2.2 provides a semilocal convergence result for Newton’s method, and cannot give us information about the local convergence of Newton’s
method in this form. Indeed for e.g. when \(x_0 =x^\star \), hypotheses (\({{\mathcal H}2}\)) and (\({ {\mathcal H}3}\)) are contradicting each other. In what follows we rectify this problem.

We state the main local convergence result for Newton’s method (1.2):

Theorem 2.3

Let \(F\, : \, \, \mathcal D\subseteq \mathcal X\longrightarrow \mathcal Y\) be a continuous operator, continuously Fréchet–differentiable on \( {\rm int} \, \, (\mathcal D) \). Suppose that there exist:
\(x^\star \in {\rm int} \, \, (\mathcal D)\) with \(F'(x^\star )^{-1} \in \mathcal L(\mathcal Y, \mathcal X)\), and \(F(x^\star )=0\);
\(R{\gt}0\), and continuously differentiable function \(f_0\), and \(f \, : \, [0,R)\longrightarrow \linebreak (-\infty ,+\infty )\), such that \( U(x^\star , R ) \subset \mathcal D\),
and

\begin{equation} \label{2.1} \parallel F'(x^\star )^{-1} \, \, (F'(x) -F'(x^\star ))\parallel \leq f_0'(\parallel x- x^\star \parallel ) -f_0'( 0), \end{equation}

2.1

\begin{equation} \label{2.2} \parallel F'(x^\star )^{-1} \, \, (F'(y) -F'(x))\parallel \leq f'(\parallel y- x \parallel + \parallel x- x^\star \parallel ) -f'( \parallel x- x^\star \parallel ), \end{equation}

2.2

for \(x, y \in U(x^\star , R )\), and \(\parallel x -x^\star \parallel + \parallel y - x \parallel {\lt} R\);
functions \(f_0'\) and \(f'\) are convex and strictly increasing with

\begin{equation} \label{2.3} f_0' (0) = f'(0) =-1, \end{equation}

2.3

\begin{equation} \label{2.4} f_0' (t) \leq f'(t) \leq 0,\quad t \in [0,R]; \end{equation}

2.4

let \(x, y \in {U}(x^\star , R )\), and \(0 \leq t {\lt} v {\lt} R\), then for all \(x \in \overline{U}(x^\star , R )\), \(\parallel y -x \parallel \leq v -t\), define function \( r_{\displaystyle f_0, f}\, : \, [0,R)^4 \longrightarrow [0, +\infty )\) by

\begin{equation} \label{2.5} r_{\displaystyle f_0, f} = r_{\displaystyle f_0,f} (t, v, \parallel y -x \parallel , \parallel x - x^\star \parallel ) = - \displaystyle \tfrac {e(t,v)\, \, \parallel y - x \parallel }{(v-t)^2 \, \, f_0’(\parallel x - x^\star \parallel )}, \end{equation}

2.5

and set

\begin{equation} \label{2.6} t^\star = \sup \{ t\in [0,R]\, : \, r_{\displaystyle f_0, f} \leq 1\} , \end{equation}

2.6

where

\begin{equation} \label{2.7} e(t,v) = f(v) - f(t) - f'(t) \, (v-t). \end{equation}

2.7

Then, sequence \(\{ x_n \} \) generated by Newton’s method (1.2), is well defined, remains in \( {U} (x^\star , t^\star )\) for all \(n \geq 0\), and converges to \(x^\star \) Q–linearly, so that

\begin{equation} \label{2.8} \parallel x_{n+1} - x^\star \parallel \leq \displaystyle \tfrac {1}{2} \, \parallel x_n - x^\star \parallel , \end{equation}

2.8

provided that \(x_0 \in {U} (x^\star , t^\star ) \).

Moreover, if

\begin{equation} \label{2.9} f_0 '(t^\star ) < 0, \end{equation}

2.9

then the following estimate holds for all \(n \geq 0\)

\begin{equation} \label{2.10} \parallel x_{n+1} - x^\star \parallel \leq \displaystyle \tfrac {D^- f’(t^\star )}{- 2 \, f_0 ’ (t^\star )} \, \parallel x_n - x^\star \parallel ^2 . \end{equation}

2.10

Furthermore, \(x^\star \) is the unique zero of \(F\) in \({U} (x^\star , t^\star ) \).

From now one we assume hypotheses of Theorem 2.3 hold, with the exception of (2.9), which will be considered to hold only when explicitly stated.

We shall show Theorem 2.3 through a series of lemmas:

Lemma 2.4

If \( x\in \overline{U}(x^\star , t)\), \(t\in [0, t^\star )\), then

\[ F'(x)^{-1} \in L(\mathcal Y, \mathcal X), \]

and

\begin{equation} \label{2.11} \parallel F'(x )^{-1} \, \, F'(x^\star ) \parallel \leq -\displaystyle \tfrac {1}{f _0 ’(\parallel x- x^\star \parallel )} \leq - \displaystyle \tfrac {1}{ f’(t)} . \end{equation}

2.11

Proof â–¼

Let \( x\in \overline{U}(x^\star , t)\), \(t\in [0, t^\star )\).

Using hypotheses (2.1), (2.3), and (2.4), we obtain in turn

\begin{equation} \label{2.12} \begin{array}{lll} \parallel F’(x^\star )^{-1} \, \, (F’(x ) -F’(x^\star )) \parallel & \leq & f _0’(\parallel x - x^\star \parallel ) -f_0’(0) \\ & \leq & f _0’(\parallel x - x^\star \parallel ) +1 \\ & \leq & f _0’( t ) +1 < 1. \end{array} \end{equation}

2.12

It follows from (2.12), and the Banach Lemma on invertible operators [ 4 ] , [ 8 ] that \( F'(x)^{-1} \in L(\mathcal Y, \mathcal X)\), so that (2.11) holds true.

That completes the proof of Lemma 2.4.

Lemma 2.5

Let \( x, y \in {U}(x^\star , R)\), and \(0 \leq t {\lt} v {\lt} R\).

If \( x \in \overline{U}(x^\star , t) \), and \(\parallel y - x \parallel \leq v- t\), then for

\[ E(z,w) = F(w) - F(z) - F'(z) \, (w - z), \, \, z \in {U}(x^\star , t), w \in \mathcal D, \]

we have the following estimates

\begin{equation} \label{2.13} \parallel F'(x^\star )^{-1} \, \, E(x,y) \parallel \leq e(t,v) \, \displaystyle \tfrac {\parallel y - x \parallel ^2 }{(v-t) ^2}, \end{equation}

2.13

and

\begin{equation} \label{2.14} r_{\displaystyle f_0, f} \leq 1, \end{equation}

2.14

where funtion \(r_{\displaystyle f_0, f} \) is given by (2.5).

Proof â–¼

Using the convexity of \(f'\), hypothesis (2.2), and the definition of operator \(E\) we obtain in turn:

\begin{align} \label{2.15} & \parallel F’(x^\star )^{-1} \, E(x,y) \parallel \leq \\ & \leq \displaystyle \int _0 ^1 \parallel F’(x^\star )^{-1} \, {\bigg(} F’(x + \theta \, (y-x)) - F’(x){\bigg)} \parallel \, \parallel y -x \parallel \, \, {\rm d} \theta \nonumber \\ & \leq \displaystyle \int _0 ^1 {\bigg(} f’(\parallel x - x^\star \parallel + \theta \, \parallel y - x \parallel ) - f’(\parallel x - x^\star \parallel ){\bigg)} \, \, \parallel y - x \parallel \, \, {\rm d} \theta \nonumber \\ & \leq \displaystyle \int _0 ^1 {\bigg(} f’ (t + \theta \, (v-t)) - f’(t) {\bigg)} \, \, \displaystyle \tfrac {\parallel y - x \parallel }{v -t} \, \, {\rm d} \theta \nonumber , \end{align}

which implies estimates (2.13).

In view of hypothesis (2.4), we get

\begin{equation} \label{2.16} \displaystyle \tfrac { \displaystyle \int _0 ^1 {\bigg(} f’ (t + \theta \, (v-t)) - f’(t) {\bigg)} \, {\rm d}\theta }{- f_0 ’(t)} \leq 1 \end{equation}

2.16

which together with (2.5) imply (2.14). That completes the proof of Lemma 2.5. As in [ 6 ] let us denote by \( \eta _{\displaystyle f_0, f} \) and \(N_F\) the maps:

\begin{equation} \label{2.17} \begin{array}{rrr} \eta _{\displaystyle f_0, f} \, \, : \, \, [0, t^\star ) \times (t,R) & \longrightarrow & (- \infty , + \infty )\\ (t,v) & \longrightarrow & t - \displaystyle \tfrac {e(t,v)}{f_0’(t)}, \end{array} \end{equation}

2.17

and

\begin{equation} \label{2.18} \begin{array}{rrl} N_F \, \, : \, \, U(x^\star , t^\star ) & \longrightarrow & \mathcal Y\\ x & \longrightarrow & x - F’(x)^{-1} \, \, F(x). \end{array} \end{equation}

2.18

According to (2.4) and Lemma 2.4, we have: \(f_0'(t) \neq 0\), \(F'(x) ^{-1} \in \mathcal L(\mathcal Y, \mathcal X)\) respectively.

Let \(x \in U(x^\star , t^\star )\), then \(N_F (x)\) may not belong to \( {U} (x^\star , t^\star )\) or even not belong in the domain of \(F\). That is, we can only guarantee, on \( {U} (x^\star , t^\star )\), well definedness of only the first iteration. Therefore, we need additional results to guarantee that Newton iterations can be repeated indefinitely.

Let us define subsets of \(U(x^\star , t^\star )\) on which Newton’s method (2.18) is “well behaved":

\begin{equation} \label{2.19} \begin{array}{l} K(t) = K(t,v) = \{ x \in \overline{U} (x^\star , t) ,\, \, t \in [0, t^\star ], \, \, v \in (t,R), \, \, \\ y \in \overline{U} (x, v-t)\, : \, \, \parallel F’(y) ^{-1} \, E(x,y) \parallel \leq r_{f_0, f} \, \parallel x- y \parallel \} , \end{array} \end{equation}

2.19

and

\begin{equation} \label{2.20} K = \displaystyle \cup _{t \in [0, t^\star ]}^{} K(t) . \end{equation}

2.20

Lemma 2.6

If \(t\in [0, t^\star )\), \(v \in (t,R)\), then the following hold true:

\[ K(t) \subset U(x^\star , t^\star ), \]

and

\[ N_F(K(t)) \subset K(\eta _{f_0, f} (t)). \]

Proof â–¼

Simply replace \(x_0\) by \(x^\star \) in the proof of Lemma 8 in [ 6 ] (see also Proposition 4 in [ 6 ] ). That completes the proof of Lemma 2.6. In view of (1.2) and (2.18) we have:

\begin{equation} \label{2.21} x_{n+1} = N_F(x_n)\qquad (n \geq 0). \end{equation}

2.21

Proof of Theorem 2.3. According to Lemmas 2.4–2.6, it is only left to show \(x_n \in U(x^\star , t^\star )\) (\(n \geq 1\)), \(\displaystyle \lim _{n \rightarrow \infty } x_n = x^\star \), so that estimates (2.8) and (2.10) hold true for all \(n \geq 0\).

By hypothesis \(x_0 \in U(x^\star , t^\star )\). Let us assume \(x_k \in U(x^\star , t^\star )\) for all \(k \leq n\). We shall show \(x_{k+1} \in U(x^\star , t^\star )\). Using (2.21), and Lemma 2.5 for \(y = x^\star \), \(x = x_n\), we get

\begin{equation} \label{2.22} \parallel x_{k+1} - x^\star \parallel \leq \parallel x_{k} - x^\star \parallel < t^\star , \end{equation}

2.22

which show \(x_{k+1} \in U(x^\star , t^\star )\), and \(\displaystyle \lim _{k \rightarrow \infty } x_k = x^\star \).

The proof of estimates (2.8) and (2.10) is given as in [ 6 ] with function \(f_0'\) replacing \(f'\) in the denominator of the estimates involved.

Finally, to show uniqueness in \( {U}(x^\star , t^\star )\), let \(y ^\star \) be a zero of \(F\) in \( {U}(x^\star , t^\star ) \). Define linear operator \(\mathcal{M}\) by

\begin{equation} \label{2.23} {\mathcal M} = \displaystyle \int _0 ^1 F' ( x^\star + \theta \, (y^\star - x^\star ) ) \, {\rm d}\theta , \end{equation}

2.23

Using (2.1), and the estimate (2.12) for \( x^\star + \theta \, (y^\star - x^\star ) \in {U}(x^\star , t^\star ) \), replacing \(x\), we conclude \({\mathcal M}^{-1} \) exists. It then follows from the identity

\begin{equation} \label{2.24} F( y^\star ) - F(x^\star ) = \displaystyle {\mathcal M} \, (y ^\star -x^\star ), \end{equation}

2.24

that \(x^\star = y^\star \). That completes the proof of Theorem 2.3.

3 Applications

Example 3.1

Let us assume there exist \(L {\gt}0\) such that the Lipschitz condition

\begin{equation} \label{3.1} \parallel F'(x^\star ) ^{-1}\, (F'(y) - F'(x)) \parallel \leq L\, \parallel x-y \parallel \ {\rm holds \, \, for \, \, all} x, y \in \overline{U} (x_0, R) \subseteq \mathcal D. \end{equation}

3.1

Define scalar majorant function \(f \, \, : \, \, [0,R] \longrightarrow (-\infty , + \infty ) \) by

\begin{equation} \label{3.2} f(t) = \displaystyle \tfrac {L}{2} \, t^2 - t + \beta \qquad {\rm for \, \, some} \, \, \, \beta \geq 0, \end{equation}

3.2

and set

\begin{equation} \label{3.3} f_0(t) = f(t) \qquad t \in [0,R]. \end{equation}

3.3

It then follows from (2.16) that we can set:

\begin{equation} \label{3.4} t_R ^\star =R = \displaystyle \tfrac {2}{3\, L}, \end{equation}

3.4

which is the radius of convergence obtained by Rheinboldt [ 11 ] , [ 4 ] .

It follows from (3.1) that there exists \(L_0 {\gt} 0\) such that:

\begin{equation} \label{3.5} \parallel F'(x^\star ) ^{-1}\, (F'(x) - F'(x^\star )) \parallel \leq L _0 \, \parallel x-x^\star \parallel , \quad {\rm for \, \, all} \quad x \in \overline{U} (x_0, R) . \end{equation}

3.5

Clearly

\begin{equation} \label{3.6} L_0 \leq L \end{equation}

3.6

holds and \(\displaystyle \tfrac {L}{L_0}\) can be arbitrarily large [ 2 ] – [ 4 ] .

Let us define function \(f_0\) by

\begin{equation} \label{3.7} f_0(t) = \displaystyle \tfrac {L_0}{2} \, t^2 - t + \beta . \end{equation}

3.7

It then follows from (2.16) that we can set:

\begin{equation} \label{3.8} t_A ^\star =R = \displaystyle \tfrac {2}{2\, L_0 + L}. \end{equation}

3.8

By comparing (3.4) with (3.8) we conclude:

\begin{equation} \label{3.9} t_R ^\star \leq t_A ^\star . \end{equation}

3.9

Note that if strict inequality holds in (3.6), then so does in (3.9).

Example 3.2

Let \(f \, : \, [0,R) \longrightarrow (-\infty , + \infty )\) be a twice continuously differentiable function with \(f'\) convex. Then \(F\) satisfies (2.2) if and only if:

\begin{equation} \label{3.10} \parallel F'(x^\star ) ^{-1} \, \, F''(x) \parallel \leq f''(\parallel x - x^\star \parallel ) \quad {\rm for \, \, all} \, \, x\in \mathcal D, \quad {\rm such \, \, that } \, \, x \in U(x^\star , R) \end{equation}

3.10

(see Lemma 14 in [ 6 ] or [ 13 ] ).

Let us define function \(f\) on \([0,R)\) by

\begin{equation} \label{3.11} f(t) = \displaystyle \tfrac {\gamma \, t^2}{1 - \gamma \, t} \ - t + \beta . \end{equation}

3.11

where \(R {\lt}\displaystyle \tfrac {1}{\gamma } \), for some \(\gamma {\gt}0\).

If for example \(F\) is an analytic operator, then (3.10) is satisfied for

\begin{equation} \label{3.12} \gamma ^\star = \displaystyle \sup _{k\geq 2} \parallel \displaystyle \tfrac {F’(x^\star ) ^{-1} F^{(k)} (x^\star ) }{k!} \parallel ^{ \tfrac {1}{k-1}} . \end{equation}

3.12

Smale [ 12 ] , and Wang [ 13 ] have used (3.11) to provided a convergence analysis for Newton’s method (1.2).

In particular Wang [ 13 ] showed convergence for \(F\) being only twice Fréchet continuously differentiable for \(\gamma \) satisfying

\begin{equation} \label{3.13} \gamma ^\star \leq \gamma . \end{equation}

3.13

We have also used (3.11) to provide a convergence analysis for the Secant method [ 5 ] (see also [ 4 ] ).

Let us also define function \(f_0\) by

\begin{equation} \label{3.14} f_0(t) = f(t)\qquad t \in [0,R). \end{equation}

3.14

By solving (2.16) we obtain for analytic operators \(F\) Smale’s radius of convergence [ 12 ] :

\begin{equation} \label{3.15} t_S ^\star = \displaystyle \tfrac {5 - \sqrt{13}}{6\, \gamma ^\star }, \end{equation}

3.15

and for twice Fréchet continuously differentiable operator \(F\) Wang’s [ 13 ] :

\begin{equation} \label{3.16} t_W ^\star = \displaystyle \tfrac {5 - \sqrt{13}}{6\, \gamma }. \end{equation}

3.16

In what follows we shall show that we can enlarge radii given by (3.15) and (3.16).

We can see that for function \(f\) given by (3.11), condition (3.10) or equivalently (2.2) imply that there exists \(\gamma _0 {\gt} 0\) satisfying

\begin{equation} \label{3.17} \gamma _0 \leq \gamma , \end{equation}

3.17

so that function \(f_0 \, : \, [0, \displaystyle \tfrac {1}{\gamma _0}) \longrightarrow (-\infty , + \infty )\) satisfies condition (2.1) for \(R \in [0, \displaystyle \tfrac {1}{\gamma _0}) \).

Note also that \(\displaystyle \tfrac {\gamma }{\gamma _0}\) can be arbitrarily large [ 2 ] – [ 4 ] . It follows by (3.17) that there exists \(a \in [0,1]\) such that

\begin{equation} \label{3.18} \gamma _0 = a\, \gamma . \end{equation}

3.18

Set

\begin{equation} \label{3.19} b =1-a , \end{equation}

3.19

and define scalar polynomial \(P_a\) by

\begin{equation} \label{3.20} P_a(t) = 3 \, a^2 \, t^3 + a \, (6 \, b - a) \, t^2 + (3 \, b^2 - 2 \, a \, b -1) \, t - b^2. \end{equation}

3.20

By the definition of polynomial \(P_a\) and for fixed \(a\), we get

\begin{equation} \label{3.21} P_a(0) = -b^2 \leq 0, \qquad {\rm and} \quad P_a(1)=1. \end{equation}

3.21

Using (3.21) and the intermediate value theorem we conclude that there exists \(t_a \in [0,1)\) such that \(P_a (t_a)=0\). Let us denote by \(t_a\) the minimal number in \([0,1)\) satisfying \(P_a(t_a)=0\).

Define

\begin{equation} \label{3.22} t_a ^\star = \displaystyle \tfrac {1 - t_a}{ \gamma }. \end{equation}

3.22

In particular for \(a=1\), \(t_1 = \displaystyle \tfrac {1+ \sqrt{13}}{6}\), and consequently

\begin{equation} \label{3.23} t_a ^\star = \displaystyle \tfrac {5 - \sqrt{13}}{6\, \gamma }= t_W^\star . \end{equation}

3.23

It is simple algebra to show that for all \(a \in [0,1]\), \(P_a(t_1) \geq 0\), which implies

\begin{equation} \label{3.24} t_a \leq t_1 . \end{equation}

3.24

and

\begin{equation} \label{3.25} t_1 ^\star \leq t_a ^\star . \end{equation}

3.25

We also note that strict inequality holds in (3.24), and (3.25) for \(a\neq 1\).

As an example, let \(a = \displaystyle \tfrac {1}{2}\). Then we obtain

\[ t_{1/2} =.65185 {\lt} t_1 = \displaystyle \tfrac {1 + \sqrt{13}}{6} = .76759 , \]

and

\begin{equation} \label{3.26} t_1 ^\star = \displaystyle \tfrac {.23241}{\gamma } < \displaystyle \tfrac {.34815}{\gamma }= t_{1/2} ^\star . \end{equation}

3.26

Finally note that clearly if strict inequality holds in (2.4), i.e., in (3.6) or (3.17), then our estimates on \(\parallel x _{n+1} - x^\star \parallel \) (\(n\geq 0\)) are finer (more precise) than the corresponding ones in [ 1 ] , [ 11 ] , [ 13 ] (see e.g. (2.10)).

These results are also obtained under the same computational cost since in practice the evaluation of \(L\) (or \(\gamma \)) requires that \(L_0\) (or \(\gamma _0\)).

Remark 3.3

As noted in [ 1 ] , [ 5 ] , [ 6 ] , [ 7 ] , [ 10 ] , [ 12 ] the local results obtained here can be used for projection method such us Arnold’s, the generalized minimum residual method (GMRES), the generalized conjugate residual method (GCR), for combined Newton/finite projection methods, and in connection with the mesh independence principle to develop the cheapest and most efficient mesh refinement strategies.

Remark 3.4

The local results obtained can also be used to solve equation of the form \(F(x)=0\), where \(F'\) satisfies the autonomous differential equation [ 4 ] , [ 8 ] :

\begin{equation} \label{3.27} F'(x) =T(F(x)), \end{equation}

3.27

where \(T\, :\, \mathcal Y\longrightarrow \mathcal X\) is a known continuous operator.

Since \(F'(x^\star )=T(F(x^\star )) =T(0)\), we can apply our results without actually knowing the solution of \(x^\star \) of equation \(F(x)=0\).

As an example, let \(\mathcal X= \mathcal Y= (-\infty , + \infty )\), \(\mathcal D= \overline{U} (0,1)\), and define function \(F\) on \(\mathcal D\) by

\begin{equation} \label{3.28} F(x) = {\rm e}^x -1. \end{equation}

3.28

Then, for \(x^\star =0\), we can set \(T(x) = x+1\) in (3.27).

Bibliography

1: J. Appel, E. De Pascale, J.V. Lysenko and P.P. Zabrejko, New results on Newton–Kantorovich approximations with applications to nonlinear integral equations, Numer. Funct. Anal. and Optimiz., 18, pp. 1–17, 1997.
2: I.K. Argyros, On the Newton–Kantorovich hypothesis for solving equations, J. Comput. Appl. Math., 169, pp. 315–332, 2004.
3: I.K. Argyros, A unifying local–semilocal convergence analysis and applications for two–point Newton–like methods in Banach space, J. Math. Anal. and Appl., 298, pp. 374–397, 2004.
4: I.K. Argyros, Computational theory of iterative methods, Studies in Computational Mathematics, 15, Elsevier, 2007, New York, U.S.A.
5: I.K. Argyros, On the convergence of the Secant method under the gamma condition, Cent. Eur. J. Math., 5, pp. 205–214, 2007.
6: O.P. Ferreira and B.F. Svaiter , Kantorovich’s majorants principle for Newton’s method, Comput. Optim. and Appl., 2007, in press.
7: J.M. Gutiérrez, M.A. Hernánadez and M.A. Salanova, Accessibility of solutions by Newton’s method, Inter. J. Comput. Math., 57, pp. 239–247, 1995.
8: L.V. Kantorovich and G.P. Akilov, Functional analysis in normed spaces, Pergamon Press, Oxford, 1982.
9: Y. Nesterov and A. Nemirovskii, Interior–point polynomial algorithms in convex programming, SIAM Studies in Appl. Math., 13, Philadelphia, PA, 1994.
10: F.A. Potra, The Kantorovich theorem and interior point methods, Mathematical Programming, 102, pp. 47–50, 2005.
11: W.C. Rheinboldt, An adaptive continuation process for solving systems of nonlinear equations, Banach Center Publ., 3, pp. 129–142, 1975.
12: S. Smale, Newton method estimates from data at one point. The merging of disciplines: new directions in pure, applied and computational mathematics, (R. Ewing, K. Gross, C. Martin, eds), Springer–Verlag, New York, pp. 185–196, 1986.
13: X. Wang, Convergence on Newton’s method and inverse function theorem in Banach space, Math. Comput., 68, pp. 169–186, 1999.
14: T.J. Ypma, Local convergence of inexact Newton Methods, SIAM J. Numer. Anal., 21, pp. 583–590, 1984.