Approximating solutions of equations
using Newton’s method with a modified Newton’s method iterate as a starting point

Abstract.

In this study we are concerned with the problem of approximating a locally unique solution of an equation in a Banach space setting using Newton’s and modified Newton’s methods. We provide weaker convergence conditions for both methods than before [6]–[8]. Then, we combine Newton’s with the modified Newton’s method to approximate locally unique solutions of operator equations in a Banach space setting. Finer error estimates, a larger convergence domain, and a more precise information on the location of the solution are obtained under the same or weaker hypotheses than before [6]–[8]. Numerical examples are also provided.

1. Introduction

In this study we are concerned with the problem of approximating a locally unique solution $x^{\ast }$ of nonlinear equation

(1) $$F(x)=0,$$

where $F$ is a Fréchet-differentiable operator defined on an open convex subset $D$ of a Banach space $X$ with values in a Banach space $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). Except 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 methods for approximation $x^{\ast }$ are undoubtedly Newton’s method

(2) $$x_{n+1}=x_n-F^{\prime }{(x_n)}^{-1}F(x_n)(n\ge 0),(x_0\in D),$$

and the modified Newton’s method

(3) $$y_{n+1}=y_n-F^{\prime }{(y_0)}^{-1}F(y_n)(n\ge 0),(y_0=x_0).$$

There is an extensive literature on the semilocal as well as the local convergence results for both methods under various hypotheses. Such results can be found in [4], [6], [7], and the references there.

The most popular hypotheses are of Newton–Kantorovich type [4], [6], [7]. Indeed, let $x_0\in D$. Assume there exist constants $\eta >0$, $\mathrm{\ell }>0$ such that

(4) $F^{\prime }{(x_0)}^{-1}\in L(Y,X),$

(5) $\Vert F^{\prime }{(x_0)}^{-1}F(x_0)\Vert \le \eta ,$

(6) $\Vert F^{\prime }{(x_0)}^{-1}[F^{\prime }(x)-F^{\prime }(y)]\Vert \le \mathrm{\ell }\Vert x-y\Vert \text{for all }x,y\in D,$

(7) $h=\mathrm{\ell }\eta \le {\displaystyle \frac{1}{2}},$

and

(8) $$\overline{U}(x_0,s^{\ast })=\{x\in X\mid \Vert x-x_0\Vert \le s^{\ast }\}\subseteq D,$$

where,

(9) $$s^{\ast }=\frac{1-\sqrt{1-2h}}{\mathrm{\ell }}.$$

Estimate (7) is the crucial non-optimum sufficient condition for the semilocal convergence of both methods [4], [6], [7] (see also Theorem 1).

Under condition (7) method (2) converges quadratically to $x^{\ast }$ (if (7) holds as a strict inequality) whereas method (3) converges linearly to $x^{\ast }$. There are examples in the literature where both methods converge to $x^{\ast }$ but condition (7) is violated. Therefore one would expect that there may be conditions weaker than (7). This is the motivation for our study. Note that in view of the Lipschitz condition (6) it follows that there exists ${\mathrm{\ell }}_0>0$ such that the center-Lipschitz condition

(10) $$\Vert F^{\prime }{(x_0)}^{-1}[F^{\prime }(x)-F^{\prime }(x_0)]\Vert \le {\mathrm{\ell }}_0\Vert x-x_0\Vert \text{for all }x\in D$$

holds.

In general

(11) $${\mathrm{\ell }}_0\le \mathrm{\ell },$$

holds true, and $\frac{\mathrm{\ell }}{{\mathrm{\ell }}_0}$ can be arbitrarily large [2]–[4].

Recently, in [3, pp. 387, Case 3, for ${\delta }_0=\delta$], we showed that condition (7) can always be replaced by the weaker

(12) $$h_1={\mathrm{\ell }}_1\eta \le \frac{1}{2},{\mathrm{\ell }}_1=\frac{1}{8}(\mathrm{\ell }+4{\mathrm{\ell }}_0+\sqrt{{\mathrm{\ell }}^2+8{\mathrm{\ell }}_0\mathrm{\ell }}),$$

in the case of Newton’s method (2) (see also, Examples 9–11).

Here, we show that in the case of the modified method (3), for convergence, condition (7) can be replaced by

(13) $$h_0={\mathrm{\ell }}_0\eta \le \frac{1}{2},$$

and (6) by weaker condition (10). Finer error estimates on the distances involved, a larger convergence domain, and a more precise information on the location of the solution than in earlier results [6] are also obtained this way (see Theorem 3 for method (2), and Theorem 5 for method (3)).

Using (13) (whenever (7) (or (12) do not hold), we can employ method (3) for a finite number of steps, say $N$ until condition (7) (or (12)) is satisfied for $x_0=y_N$. Then faster method (2) takes over from method (3).

The above advantages extend to the local convergence of methods (2) and (3) (see Theorems 10 and 11). Numerical examples are also provided. The technique introduced here can extend to other Newton-type iterative methods [1], [3], [4], [5].

2. Semilocal Convergence Analysis

The following semilocal convergence result for methods (2) and (3) can be found in [7]:

Theorem 1.

Let $F:D\subseteq X\to Y$ be a differentiable operator.

Assume there exist $x_0\in D$, and constants $\mathrm{\ell }>0$, $\eta >0$ such that

$F^{\prime }{(x_0)}^{-1}\in L(Y,X),$

$\Vert F^{\prime }{(x_0)}^{-1}F(x_0)\Vert \le \eta ,$

$\Vert F^{\prime }{(x_0)}^{-1}[F^{\prime }(x)-F^{\prime }(y)]\Vert \le \mathrm{\ell }\Vert x-y\Vert \text{for all }x,y\in D,$

$h=\mathrm{\ell }\eta \le {\displaystyle \frac{1}{2}},$

and

$$\overline{U}(x_0,s^{\ast })\subseteq D,$$

where

$$s^{\ast }=\frac{1-\sqrt{1-2\mathrm{\ell }\eta }}{\mathrm{\ell }}.$$

Then sequences $\{y_n\}$, $\{x_n\}$ are well defined, remain in $\overline{U}(x_0,s^{\ast })$ for all $n\ge 0$ and converge to a unique solution $x^{\ast }$ of equation $F(x)=0$ in $\overline{U}(x_0,s^{\ast })$. Moreover the following estimates hold:

$\Vert y_{n+1}-y_n\Vert$ $\le$ $q^n\Vert y_1-y_0\Vert \le q^n\eta ,$

$\Vert y_n-x^{\ast }\Vert$ $\le$ ${\displaystyle \frac{q^n}{1-q}}\eta ,$

$\Vert x_{n+2}-x_{n+1}\Vert$ $\le$ ${\displaystyle \frac{\mathrm{\ell }{(s_{n+1}-s_n)}^2}{2(1-\mathrm{\ell }{s}_{n+1})}},$

and

$$\Vert x_n-x^{\ast }\Vert \le s^{\ast }-s_n,s^{\ast }=\underset{n\to \mathrm{\infty }}{lim}{s}_n,$$

where,

$$s_0=0,s_1=\eta ,s_{n+2}=s_{n+1}+\frac{\mathrm{\ell }{(s_{n+1}-s_n)}^2}{2(1-\mathrm{\ell }{s}_{n+1})}(n\ge 0),$$

and

(14) $$q=1-\sqrt{1-2\mathrm{\ell }h}.$$

Remark 2.

There is a plethora of estimates on the distances $\Vert x_{n+1}-x_n\Vert$, $\Vert x_n-x^{\ast }\Vert$, $\Vert y_{n+1}-y_n\Vert$, $\Vert y_n-x^{\ast }\Vert$ $(n\ge 0)$ [4], [6], [7]. However we decided to list only the estimates related to what we need in this study. In the case of Newton’s method (2) we showed in [2], [3] the following improvement of Theorem 1.∎

Theorem 3.

[2], [3]. Let $F:D\subseteq X\to Y$ be a differentiable operator.

Assume there exist $x_0\in D$, and constants ${\mathrm{\ell }}_0>0$, $\mathrm{\ell }>0,$ $\eta \ge 0$ such that

$F^{\prime }{(x_0)}^{-1}\in L(Y,X),$

$\Vert F^{\prime }{(x_0)}^{-1}F(x_0)\Vert \le \eta ,$

$\Vert F^{\prime }{(x_0)}^{-1}[F^{\prime }(x)-F^{\prime }(x_0)]\Vert \le {\mathrm{\ell }}_0\Vert x-x_0\Vert \text{for all }x\in D,$

$\Vert F^{\prime }{(x_0)}^{-1}[F^{\prime }(x)-F^{\prime }(y)]\Vert \le \mathrm{\ell }\Vert x-y\Vert \text{for all }x,y\in D,$

$h_1={\mathrm{\ell }}_1\eta \le {\displaystyle \frac{1}{2}},$

$\overline{U}(x_0,t^{\ast })\subseteq D,$

where,

$$t_0=0,t_1=\eta ,t_{n+2}=t_{n+1}+\frac{\mathrm{\ell }{(t_{n+1}-t_n)}^2}{2(1-{\mathrm{\ell }}_0{t}_{n+1})}(n\ge 0),$$

and

$$t^{\ast }=\underset{n\to \mathrm{\infty }}{lim}{t}_n\le \frac{2\eta }{2-{\mathrm{\ell }}_2}=t_0^{\ast },{\mathrm{\ell }}_2=\frac{-\frac{\mathrm{\ell }}{{\mathrm{\ell }}_0}+\sqrt{{\left(\frac{\mathrm{\ell }}{{\mathrm{\ell }}_0}\right)}^2+\frac{8\mathrm{\ell }}{{\mathrm{\ell }}_0}}}{2}.$$

Then sequence $\{x_n\}$ $(n\ge 0)$ generated by Newton’s method (2) is well defined, remains in $\overline{U}(x_0,t^{\ast })$ for all $n\ge 0$ and converges to a unique solution $x^{\ast }$ of equation $F(x)=0$ in $\overline{U}(x_0,t^{\ast })$.

Moreover the following estimates hold for all $n\ge 0$:

$\Vert x_{n+1}-x_n\Vert$ $\le$ $t_{n+1}-t_n,$

$\Vert x_n-x^{\ast }\Vert$ $\le$ $t^{\ast }-t_n,$

(15) $t_n$ $\le$ $s_n,$

(16) $t_{n+1}-t_n$ $\le$ $s_{n+1}-s_n,$

and

(17) $$t^{\ast }-t_n\le s^{\ast }-s_n.$$

Remark 4.

Note also that (15) and (16) hold as strict inequalities if [2]–[4]. Moreover we have:

(18) $$h\le \frac{1}{2}\Rightarrow h_1\le \frac{1}{2},$$

but not vice versa unless if ${\mathrm{\ell }}_0=\mathrm{\ell }$. That is under the same computational cost we managed to weaken (7) since in practice the computation of $\mathrm{\ell }$ also requires the computation of ${\mathrm{\ell }}_0$. Furthermore, in Example 9, we show that (12) holds but condition (7) is violated.∎

Concerning the semilocal convergence of the modified Newton’s method we show that (13) replaces condition (7).

Theorem 5.

Let $F:D\subseteq X\to Y$ be a differentiable operator.

Assume there exist $x_0\in D$ and constants ${\mathrm{\ell }}_0>0$, $\eta >0$, such that

$F^{\prime }{(x_0)}^{-1}\in L(Y,X),$

$\Vert F^{\prime }{(x_0)}^{-1}F(x_0)\Vert \le \eta ,$

$\Vert F^{\prime }{(x_0)}^{-1}[F^{\prime }(x)-F^{\prime }(x_0)]\Vert \le {\mathrm{\ell }}_0\Vert x-x_0\Vert \text{for all }x\in D,$

and

(19) $$\overline{U}(x_0,s_0^{\ast })\subseteq D,$$

where,

$$s_0^{\ast }=\frac{1-\sqrt{1-2{\mathrm{\ell }}_0\eta }}{{\mathrm{\ell }}_0}.$$

Then sequence $\{y_n\}$ $(n\ge 0)$ generated by the modified Newton’s method (3) is well defined, remains in $\overline{U}(x_0,s_0^{\ast })$ for all $n\ge 0$ and converges to a unique solution $x^{\ast }$ of equation $F(x)=0$ in $\overline{U}(x_0,s_0^{\ast })$.

Moreover the following estimates hold for all $n\ge 0$:

$$\Vert y_{n+1}-y_n\Vert \le q_0^n\Vert y_1-y_0\Vert$$

and

$$\Vert y_n-x^{\ast }\Vert \le \frac{q_0^n}{1-q_0}\eta ,$$

where

$$q_0=1-\sqrt{1-2{\mathrm{\ell }}_0\eta }.$$

Proof.

We shall show that the assumptions of the contraction mapping principle are satisfied for the operator

(20) $$P(x)=x-F^{\prime }{(x_0)}^{-1}F(x)\text{on}\overline{U}(x_0,s_0^{\ast }).$$

Let $x,y\in \overline{U}(x_0,s_0^{\ast })$. Then we can obtain the identity

$P(x)-P(y)$ $=$ $x-y-F^{\prime }{(x_0)}^{-1}(F(x)-F(y))$

$=$ $F^{\prime }{(x_0)}^{-1}{\displaystyle {\int }_0^1}\{F^{\prime }(x_0)-F^{\prime }[y+t(x-y)]\}(x-y)dt.$

This identity together with (10) implies the estimate

(21) $\Vert P(x)-P(y)\Vert$ $\le$ ${\mathrm{\ell }}_0{\displaystyle {\int }_0^1}[(1-t)\Vert x-x_0\Vert +t\Vert y-x_0\Vert ]dt\Vert x-y\Vert$

$\le$ ${\mathrm{\ell }}_0{s}_0^{\ast }\Vert x-y\Vert =q_0\Vert x-y\Vert .$

Consequently, $P$ is a contraction operator in the ball $\overline{U}(x_0,s_0^{\ast })$. To complete the proof, it remains to show that

$$P\overline{U}(x_0,s_0^{\ast })\subseteq \overline{U}(x_0,s_0^{\ast }).$$

Let $x\in \overline{U}(x_0,s_0^{\ast })$. Then by (20) we can obtain in turn

$\Vert P(x)-x_0\Vert$ $\le$ $\Vert P(x)-P(x_0)\Vert +\Vert P(x_0)-x_0\Vert$

$\le$ $\Vert F^{\prime }{(x_0)}^{-1}{\displaystyle {\int }_0^1}\{F^{\prime }(x_0)-F^{\prime }[x_0+t(x-x_0)]\}(x-x_0)dt\Vert +\eta$

$\le$ ${\mathrm{\ell }}_0{\displaystyle {\int }_0^1}tdt{\Vert x-x_0\Vert }^2+\eta \le {\displaystyle \frac{{\mathrm{\ell }}_0}{2}}{(s_0^{\ast })}^2+\eta =s_0^{\ast },$

by the choice of $s_0^{\ast }$. That completes the proof of Theorem 5. ∎

Remark 6.

Note that by (21) the operator $P$ satisfies a Lipschitz condition with constant $q_0$ in the ball $\overline{U}(x_0,s_0^{\ast })$. The modified Newton’s method thus converges at the rate of a geometric progression with quotient $q_0$.∎

The above analysis of method (3) relates to the simplest case. More subtle arguments (see, e.g. Kantorovich and Akilov [6]) show that Theorem 5 remains valid if the sign in (19) is replace by $\le$. Therefore from now on we can replace (19) by (13) in Theorem 5.

Remark 7.

If ${\mathrm{\ell }}_0=\mathrm{\ell }$ Theorems 3 and 5 reduce to Theorem 1. Otherwise these theorems constitute improvements of it. Indeed see (15)–(18), and notice that

and

Notice also that (7) (or (12)) implies (13) and if $t^{\ast }\le s_0^{\ast }$ the quadratic convergence of method (2) is guaranteed. Moreover $s_0^{\ast }$ given in closed form can then in practice replace $t^{\ast }$. Furthermore if then there exists $N>1$ such that $x_n\in \overline{U}(x_0,s_0^{\ast })$ for $n\ge N$ and then again $s_0^{\ast }$ can replace $t^{\ast }$.∎

Next we show that we can start with method (3) and after a finite number of steps continue with faster method (2):

Proposition 8.

Under hypotheses (4)–(6), (10), (13), and (19), for $x_0=y_0$, define

$$\alpha =\frac{1}{1-{\mathrm{\ell }}_0{s}_0^{\ast }},$$

$$L=\alpha \mathrm{\ell },$$

for a fixed integer $N$

$${\mathrm{\ell }}_2=\underset{x\in \overline{U}(y_N,r_N)}{sup}\frac{\Vert F^{\prime }{(y_0)}^{-1}[F^{\prime }(x)-F^{\prime }(y_N)]\Vert }{\Vert x-y_N\Vert },$$

$$L_0=\alpha {\mathrm{\ell }}_2\le L,$$

$$N=\left[-\frac{\ln 2\overline{L}{\alpha }^2\eta }{\ln q_0}\right]+1,$$

$${\eta }_N=\alpha q_0^N\eta ,$$

and

$$L_{2N}=\frac{-\frac{L}{L_0}+\sqrt{{\left(\frac{L}{L_0}\right)}^2+\frac{8L}{L_0}}}{2},\mathrm{for}{L}_0\ne 0,$$

where $[r]$ denotes the integer part of real number $r$.

Set

$$\overline{x_0}=y_N.$$

Moreover, assume:

(22) $$\overline{U}(y_N,r_N)\subseteq D.$$

Then the following hold:

(23) $$\Vert F^{\prime }{(y_N)}^{-1}F(y_N)\Vert \le {\eta }_N,$$

(24) $$\Vert F^{\prime }{(y_N)}^{-1}[F^{\prime }(x)-F^{\prime }(y)]\Vert \le L\Vert x-y\Vert ,$$

(25) $$\Vert F^{\prime }{(y_N)}^{-1}[F^{\prime }(x)-F^{\prime }(y_N)]\Vert \le L_0\Vert x-y_N\Vert ,$$

(26) $$H_N=\overline{L}{\eta }_N\le \frac{1}{2};$$

Newton’s method (2), starting at $x_0=\overline{x_0}$ converges to a unique solution $x^{\ast \ast }$ of equation $F(x)=0$ in $\overline{U}(y_N,r_N)$,

and

$$N_0\le N_1,$$

where

$$N_0=N\mathrm{for}{L}_0=L,$$

and

Moreover, if the inclusion

(27) $$\overline{U}(y_N,r_N)\subseteq \overline{U}(y_0,s_0^{\ast }),$$

hold, then

$$x^{\ast }=x^{\ast \ast }.$$

Note that parameter $L_0$ is independent of $N$ if $L_0=L$, and the inclusion (27) holds if and only if

$$\Vert y_N-y_0\Vert +r_N\le s_0^{\ast }.$$

If $\Vert y_N-y_0\Vert \le s_0^{\ast }$, then by the definition of $r_N$, there exists an integer $N_0$, such that (27) holds. In this case $N^{\ast }=\{N,N_0\}$ should replace $N$ in the Proposition. Hypothesis (22) can now be dropped, since it follows from (19) and (27).

Proof.

Using Theorem 5, and the estimates

we obtain

$$H_N=\overline{L}{\eta }_N={\alpha }^2\overline{L}{q}_0^N\eta \le \frac{1}{2}$$

and

$$N_0\le N_1,$$

by the choice of $N$.

It follows by Theorems 1 and 3, with $L_0$, $L$, ${\eta }_N$, $r_N$, $r_N$ replacing ${\mathrm{\ell }}_0$, $\mathrm{\ell }$, $\eta$, $s^{\ast }$, $t_0^{\ast }$ respectively, that there exists a unique solution $x^{\ast \ast }$ of equation $F(x)=0$ in $\overline{U}(y_N,r_N)$.

Moreover, if inclusion (27) holds by the uniqueness of the solution $x^{\ast }$ in $\overline{U}(y_0,s_0^{\ast })$, we deduce $x^{\ast }=x^{\ast \ast }$.

That completes the proof of Proposition 8. ∎

Let us provide an example.

Example 9.

Let $X=Y=𝐑$, $D=[a,2-a]$, $a\in [0,\frac{1}{2})$ and define scalar function $F$ on $D$ by

(28) $$F(x)=x^3-a.$$

Choose $y_0=1$. Using (5), (6), (10) and (28), we obtain

(29) $$\eta =\frac{1}{3}(1-a),{\mathrm{\ell }}_0=3-a\text{and}\mathrm{\ell }=2(2-a).$$

The Newton–Kantorovich hypothesis (7) becomes

(30) $$h=\frac{2}{3}(1-a)(2-a)>\frac{1}{2}$$

for all $a\in [0,\frac{1}{2})$. That is according to Theorem 1 there is no guarantee that either methods (2) or (3) starting at $x_0=y_0=1$ converge to $x^{\ast }$.

However according to Theorem 3 condition (12) becomes:

(31) $$h_1\le \frac{1}{2},$$

provided that

(32) $$a\in [.450339002,\frac{1}{2}).$$

Using condition (13) we can do even better since

(33) $$h_0=\frac{1}{3}(1-a)(3-a)\ge \frac{1}{2}$$

provided that

(34) $$a\in [\frac{4-\sqrt{10}}{2},\frac{1}{2})$$

which improves the choice for $a$ given by (32). However only linear and not quadratic convergence is guaranteed.

Let us now use $a=.49$. In particular (7) does not hold since for $\eta =.17$, $\mathrm{\ell }=3.02$

$$h_1=.5134>\frac{1}{2}.$$

However (13) holds since for ${\mathrm{\ell }}_0=2.51$:

$$h_0=.4267\le \frac{1}{2}.$$

We get

$$q_0=.617116205,\alpha =2.61175848,s_0^{\ast }=.24586303,$$

(35) $$N=[4.0325]+1=5.$$

Moreover we obtain

$${\overline{x}}_0=y_4=.78911736.$$

Finally note that $x^{\ast }=.788373516$.

Our motivation for introducing condition (10) instead of (6) for the convergence modified Newton’s method (3) can also be seen in the following examples.

Example 10.

Let $X=Y=𝐑$, $D=[0,\mathrm{\infty })$, $x_0=1$ and define function $F$ on $D$ by

(36) $$F(x)=\frac{x^{1+\frac{1}{i}}}{1+\frac{1}{i}}+c_{1}x+c_2,$$

where $c_1,c_2$ are real parameters and $i>2$ an integer. Then $F^{\prime }(x)=x^{\frac{1}{i}}+c_1$ is not Lipschitz on $D$. However, center Lipschitz condition (10) holds for ${\mathrm{\ell }}_0={(1+c_1)}^{-1}$ $(c_1\ne -1)$.

Indeed, we have

$\Vert F^{\prime }{(x_0)}^{-1}[F^{\prime }(x)-F^{\prime }(x_0)]\Vert$ $=$ ${(1+c_1)}^{-1}\left|x^{\frac{1}{i}}-x_0^{\frac{1}{i}}\right|$

$=$ $\frac{{(1+c_1)}^{-1}|x-x_0|}{x_0^{\frac{i-1}{i}}+\mathrm{\cdots }+x^{\frac{i-1}{i}}}$

$\le$ ${\mathrm{\ell }}_0|x-x_0|.$

Example 11.

We consider the integral equation

(37) $$u(s)=f(s)+\lambda {\int }_a^{b}G(s,t)u{(t)}^{1+\frac{1}{n}}dt,n\in 𝐍.$$

Here, $f$ is a given continuous function satisfying $f(s)>0$, $s\in [a,b]$, $\lambda$ is a real number, and the kernel $G$ is continuous and positive in $[a,b]\times [a,b]$.

For example, when $G(s,t)$ is the Green kernel, the corresponding integral equation is equivalent to the boundary value problem

$u^{\prime \prime }$ $=$ $\lambda u^{1+\frac{1}{n}},$

$u(a)$ $=$ $f(a),u(b)=f(b).$

These type of problems have been considered in [2]–[7].

Equations of the form (37) generalize equations of the type

(38) $$u(s)={\int }_a^{b}G(s,t)u{(t)}^{n}dt$$

studies in [4], [6], [7].

Instead of (37) we can try to solve the equation $F(u)=0$ where

$$F:\mathrm{\Omega }\subseteq C[a,b]\to C[a,b],\mathrm{\Omega }=\{u\in C[a,b]:u(s)\ge 0,s\in [a,b]\},$$

and

$$F(u)(s)=u(s)-f(s)-\lambda {\int }_a^{b}G(s,t)u{(t)}^{1+\frac{1}{n}}dt.$$

The norm we consider is the max-norm.

The derivative $F^{\prime }$ is given by

$$F^{\prime }(u)v(s)=v(s)-\lambda \left(1+\frac{1}{n}\right){\int }_a^{b}G(s,t)u{(t)}^{\frac{1}{n}}v(t)dt,v\in \mathrm{\Omega }.$$

First of all, we notice that $F^{\prime }$ does not satisfy a Lipschitz-type condition in $\mathrm{\Omega }$. Let us consider, for instance, $[a,b]=[0,1]$, $G(s,t)=1$ and $y(t)=0$. Then $F^{\prime }(y)v(s)=v(s)$ and

$$\Vert F^{\prime }(x)-F^{\prime }(y)\Vert =|\lambda |\left(1+\frac{1}{n}\right){\int }_0^{1}x{(t)}^{\frac{1}{n}}dt.$$

If $F^{\prime }$ were a Lipschitz function, then

$$\Vert F^{\prime }(x)-F^{\prime }(y)\Vert \le L_1\Vert x-y\Vert ,$$

or, equivalently, the inequality

(39) $${\int }_0^{1}x{(t)}^{\frac{1}{n}}dt\le L_2\underset{x\in [0,1]}{\max }x(s),$$

would hold for all $x\in \mathrm{\Omega }$ and for a constant $L_2$. But this is not true. Consider, for example, the functions

$$x_j(t)=\frac{t}{j},j\ge 1,t\in [0,1].$$

If these are substituted into (39)

$$\frac{1}{j^{1/n}\left(1+\frac{1}{n}\right)}\le \frac{L_2}{j}\iff j^{1-\frac{1}{n}}\le L_2\left(1+\frac{1}{n}\right),\forall j\ge 1.$$

This inequality is not true when $j\to \mathrm{\infty }$.

Therefore, condition (6) fails in this case. However, condition (10) holds. To show this, let $x_0(t)=f(t)$ and $\alpha =\underset{s\in [a,b]}{\min }f(s)$, $\alpha >0$. Then, for $v\in \mathrm{\Omega }$,

$\Vert [F^{\prime }(x)-F^{\prime }(x_0)]v\Vert$

$=|\lambda |\left(1+{\displaystyle \frac{1}{n}}\right)\underset{s\in [a,b]}{\max }\left|{\displaystyle {\int }_a^b}G(s,t)\left(x{(t)}^{\frac{1}{n}}-f{(t)}^{\frac{1}{n}}\right)v(t)dt\right|$

$\le |\lambda |\left(1+{\displaystyle \frac{1}{n}}\right)\underset{s\in [a,b]}{\max }{\displaystyle \frac{G(s,t)|x(t)-f(t)|}{x{(t)}^{(n-1)/n}+x{(t)}^{(n-2)/n}f{(t)}^{1/n}+\mathrm{\cdots }+f{(t)}^{(n-1)/n}}}\mathrm{d}t\Vert v\Vert .$

Hence,

$\Vert F^{\prime }(x)-F^{\prime }(x_0)\Vert$ $\le$ ${\displaystyle \frac{|\lambda |\left(1+\frac{1}{n}\right)}{{\alpha }^{(n-1)/n}}}\underset{s\in [a,b]}{\max }{\displaystyle {\int }_a^b}G(s,t)dt\Vert x-x_0\Vert$

$\le$ $K\Vert x-x_0\Vert ,$

where $K=\frac{|\lambda |(1+\frac{1}{n})}{{\alpha }^{(n-1)/n}}N$, $N=\underset{s\in [a,b]}{\max }{\int }_a^{b}G(s,t)dt$, and ${\mathrm{\ell }}_0=\Vert F^{\prime }{(x_0)}^{-1}K\Vert$. Finally note that condition (13) is satisfied for sufficiently small $\lambda$.

3. Local Convergence Analysis

In order for us to cover the local convergence of methods (2) and (3) we start the theorem [7]:

Theorem 12.

Let $F:D\subseteq X\to Y$ be a differentiable operator. Assume there exist $x^{\ast }\in D$ and a constant $K>0$ such that:

(40) $F^{\prime }{(x^{\ast })}^{-1}\in L(Y,X),F(x^{\ast })=0,$

(41) $\Vert F^{\prime }{(x^{\ast })}^{-1}[F^{\prime }(x)-F^{\prime }(y)]\Vert \le K\Vert x-y\Vert \text{for all }x,y\in D,$

and

(42) $$\overline{U}(x^{\ast },r_{RN})\subseteq D$$

where,

(43) $$r_{RN}=\frac{2}{3K}.$$

Then

1. sequence $\{x_n\}$ generated by Newton’s method (2) is well defined, remains in $\overline{U}(x^{\ast },r_{RN})$ for all $n\ge 0$, converges to $x^{\ast }$ provided that $x_0\in U(x^{\ast },r_{RN})$ and

   (44) $$\Vert x_{n+1}-x^{\ast }\Vert \le \frac{K{\Vert x_n-x^{\ast }\Vert }^2}{2(1-K\Vert x_n-x^{\ast }\Vert )}(n\ge 0).$$

   If (58) is replaced by

   (45) $$\overline{U}(x^{\ast },r_{RM})\subseteq D,$$

   where,

   (46) $$r_{RM}=\frac{2}{5K},$$

   then

2. sequence $\{y_n\}$ generated by modified Newton’s method (3) is well defined, remains in $\overline{U}(x^{\ast },r_{RM})$ for all $n\ge 0$, converges to $x^{\ast }$ provided that $x_0\in U(x^{\ast },r_{RM})$, and

   (47) $$\Vert y_{n+1}-x^{\ast }\Vert \le \frac{K\left[\Vert x^{\ast }-y_0\Vert +\frac{1}{2}\Vert y_n-x^{\ast }\Vert \right]}{1-K\Vert x^{\ast }-y_0\Vert }\Vert y_n-x^{\ast }\Vert (n\ge 0).$$

Proof.

The proof of (a) can be found in [8], whereas the proof of (b) is a special case of part (b) in our Theorem 11 that follows.

It follows from condition (41) that there exists $K_0\in (0,K)$ such that:

(48) $$\Vert F^{\prime }{(x^{\ast })}^{-1}[F^{\prime }(x)-F^{\prime }(x^{\ast })]\Vert \le K_0\Vert x-x^{\ast }\Vert \text{for all }x\in D.$$

Then using a combination of conditions (41) and (48) for method (2), and only condition (48) for method (3) we can show: ∎

Theorem 13.

Let $F:D\subseteq X\to Y$ be a differentiable operator.

Assume there exist $x^{\ast }\in D$ and constants $K_0>0$, $K>0$ such that:

$F^{\prime }{(x^{\ast })}^{-1}\in L(Y,X),F(x^{\ast })=0,$

$\Vert F^{\prime }{(x^{\ast })}^{-1}[F^{\prime }(x)-F^{\prime }(x^{\ast })]\Vert \le K_0\Vert x-x^{\ast }\Vert \text{for all }x\in D,$

$\Vert F^{\prime }{(x^{\ast })}^{-1}[F^{\prime }(x)-F^{\prime }(y)]\Vert \le K\Vert x-y\Vert \text{for all }x,y\in D,$

and

(49) $$\overline{U}(x^{\ast },r_{AN})\subseteq D$$

where,

(50) $$r_{AN}=\frac{2}{2K_0+K}.$$

1. Then sequence $\{x_n\}$ generated by Newton’s method (2) is well defined, remains in $\overline{U}(x^{\ast },r_{AN})$ for all $n\ge 0$, converges to $x^{\ast }$ provided that $x_0\in U(x^{\ast },r_{AN})$ and

   (51) $$\Vert x_{n+1}-x^{\ast }\Vert \le \frac{K{\Vert x_n-x^{\ast }\Vert }^2}{2(1-K_0\Vert x_n-x^{\ast }\Vert )}(n\ge 0).$$

   Using only the center-Lipschitz condition, and if (49) is replaced by

   (52) $$\overline{U}(x^{\ast },r_{AM})\subseteq D,$$

   and (48), where,

   (53) $$r_{AM}=\frac{2}{5K_0},$$

   then,

2. sequence $\{y_n\}$ generated by the modified Newton’s method (3) is well defined, remains in $\overline{U}(x^{\ast },r_{AM})$ for all $n\ge 0$, converges to $x^{\ast }$ provided that $x_0\in U(x^{\ast },r_{AM})$,

   and

   (54) $$\Vert y_{n+1}-x^{\ast }\Vert \le \frac{K_0\left[\Vert x^{\ast }-y_0\Vert +\frac{1}{2}\Vert y_n-x^{\ast }\Vert \right]\Vert y_n-x^{\ast }\Vert }{1-K_0\Vert x^{\ast }-y_0\Vert }(n\ge 0).$$

Proof.

(a) The proof can be found in [2].

(b) Let $x\in \overline{U}(x^{\ast },r_{AM})$. Then using (48) we get

(55)

by the choice of $r_{AM}$. It follows from (55) and the Banach Lemma on invertible operators [4], [6] that $F^{\prime }{(x)}^{-1}$ exists, and

(56) $$\Vert F^{\prime }{(x)}^{-1}{F}^{\prime }(x^{\ast })\Vert \le \frac{1}{1-K_0\Vert x-x^{\ast }\Vert }\le \frac{1}{1-K_0{r}_{AM}}.$$

In particular by hypothesis $y_0\in U(x^{\ast },r_{AM})\subseteq \overline{U}(x^{\ast },r_{AM})$.

Let us assume $y_k\in \overline{U}(x^{\ast },r_{AM})$ for $k=0,1,\mathrm{\dots },n$. Then using (3), (48) and (53) we obtain in turn

(57) $y_{n+1}-x^{\ast }$ $=$ $y_n-x^{\ast }-F^{\prime }{(y_0)}^{-1}F(y_n)$

$=$ $F^{\prime }{(y_0)}^{-1}[F^{\prime }(y_0)(y_n-x^{\ast })-F(y_n)]$

$=$ $-F^{\prime }{(y_0)}^{-1}[F(y_n)-F(x^{\ast })-F^{\prime }(y_0)(y_n-x^{\ast })]$

$=$ $-F^{\prime }{(y_0)}^{-1}{F}^{\prime }(x^{\ast })F^{\prime }{(x^{\ast })}^{-1}\{{\displaystyle {\int }_0^1}[F^{\prime }(x^{\ast }+t(y_n-x^{\ast }))-F^{\prime }(x^{\ast })]$

$+[F^{\prime }(x^{\ast })-F^{\prime }(y_0)]\}(y_n-x^{\ast })\mathrm{d}t,$

and

(58) $\Vert y_{n+1}-x^{\ast }\Vert$ $\le$ ${\displaystyle \frac{K_0{\int }_0^1[\Vert x^{\ast }-y_0\Vert +t\Vert y_n-x^{\ast }\Vert ]}{1-K_0\Vert x^{\ast }-y_0\Vert }}\Vert y_n-x^{\ast }\Vert \mathrm{d}t$

$=$ ${\displaystyle \frac{K_0\left[\Vert x^{\ast }-y_0\Vert +\frac{1}{2}\Vert y_n-x^{\ast }\Vert \right]}{1-K_0\Vert x^{\ast }-y_0\Vert }}\Vert y_n-x^{\ast }\Vert$

$\Vert y_n-x^{\ast }\Vert \le r_{AM}$

which shows (54), and $\underset{n\to \mathrm{\infty }}{lim}{y}_n=x^{\ast }$.

That completes the proof of Theorem 13. ∎

Remark 14.

In general

(59) $$K_0\le K$$

holds and $\frac{K}{K_0}$ can be arbitrarily large. If $K_0=K$ Theorem 13 reduces to Theorem 10. Otherwise Theorem 13 improves Theorem 12 under the same hypotheses for method (2), and the same or less computational cost for method (3); finer estimates on the distances $\Vert x_n-x^{\ast }\Vert$ $(n\ge 0)$ are obtained and the radius of convergence is enlarged. In particular, we have

(60) $r_{RN}$ $r_{AN}$

(61) $r_{RM}$ $r_{AM}.$

Moreover, since

(62)

iterates from method (3) cannot be used to find the initial guess $x_0$ for faster method (2).

Examples where estimate (59) holds as in strict inequality can be found in [2]–[4]. However using Theorem 13 we can achieve this as follows: Let $p\in (0,1)$ be the desired rate of convergence for method (3). Then by (54) we have for $\Vert y_0-x^{\ast }\Vert \le \frac{2p}{3K_0+2p{K}_0}$ that:

$$\Vert y_{n+1}-x^{\ast }\Vert \le p\Vert y_n-x^{\ast }\Vert .$$

Choose:

(63) $$M=\left[\frac{\ln \frac{5K_0}{2K_0+K}}{\ln p}\right]+1,$$

then it can easily be seen that

$$p^M{r}_{AM}\le r_{AN}$$

and consequently according to (a) of Theorem 11 we can set

$$x_0=y_M.$$

In case of $K_0=K$ according to (a) of Theorem 10 we can set

$$x_0=y_{M_1},$$

where,

$$M_1=\left[\frac{\ln \frac{5}{3}}{\ln p}\right]+1$$

(simply set $K_0=K$ in (63)). Note that

$$M\le M_1.$$

Finally we observe

if

$$\frac{K}{K_0}>\frac{5}{3},$$

which can hold, since $\frac{K}{K_0}$ can be arbitrarily large [2]. ∎

The ideas presented here can be extended to other Newton-type iterative methods [1], [3], [4], [5] along the same lines.

4. Conclusion

The famous for its simplicity and clarity Newton–Kantorovich hypothesis (7) is the crucial sufficient semilocal convergence condition for both the quadratically convergent Newton’s method (2), and the linearly convergent modified Newton’s method (3) [6]. There exist simple numerical examples to show that both methods converge even when condition (7) is violated [4], [6]. In fact, it is common practice even condition (7) is violated for a certain initial guess, to still use Newton’s method (2) for a few iterates until condition (7) is satisfied. However, this approach is considered a shot in the dark, and it is not working in general [4], [7]. Here we have introduced a certain approach that works in case condition (7)is violated. First, we showed that condition (13) is a weaker sufficient convergence hypothesis for the modified Newton’s method (3) than (7). That is we extended the convergence region of method (3). Then, if (7) is violated but (13) holds, we start with slower method (3) until we reach, (after a finite number of steps) a certain iterate for which condition (7) also holds true. We then continue with faster method (2) using this iterate.