A Methodology for Obtaining the Different Convergence Orders of Numerical Method under Weaker Conditions

Abstract

A process for solving an algebraic equation was presented by Newton in 1669 and later by Raphson in 1690. This technique is called Newton’s method or Newton–Raphson method and is even today a popular technique for solving nonlinear equations in abstract spaces. The objective of this article is to update developments in the convergence of this method. In particular, it is shown that the Kantorovich theory for solving nonlinear equations using Newton’s method can be replaced by a finer one with no additional and even weaker conditions. Moreover, the convergence order two is proven under these conditions. Furthermore, the new ratio of convergence is at least as small. The same methodology can be used to extend the applicability of other numerical methods. Numerical experiments complement this study.

1. Introduction

Given Banach spaces $\mathcal{U},\mathcal{V}$. Let $L(\mathcal{U},\mathcal{V})$ stand for the space of all continuous linear operators mapping $\mathcal{U}$ into $\mathcal{V}.$ Consider differentiable as per Fréchet operator $\mathcal{L}:D\subseteq \mathcal{U}⟶\mathcal{V}$ and its corresponding nonlinear equation

$$\mathcal{L}\left(x\right)=0,$$

(1)

with D denoting a nonempty open set. The task of determining a solution $x^{*}\in D$ is very challenging but important, since applications from numerous computational disciplines are brought in form (1) [1,2]. The analytic form of $x^{*}$ is rarely attainable. That is why mainly numerical methods are used generating approximations to solution $x^{*}$. Most of them are based on Newton’s method [3,4,5,6,7]. Moreover, authors developed efficient high-order and multi-step algorithms with derivative [8,9,10,11,12,13] and divided differences [14,15,16,17,18].

Among these processes the most widely used is Newton’s and its variants. In particular, Newton’s Method (NM) is developed as

$$x_0\in D,x_{n+1}=x_n-{\mathcal{L}}^{\prime }{\left(x_n\right)}^{-1}\mathcal{L}\left(x_n\right)\forall n=0,1,2,\dots .$$

(2)

There exists a plethora of results related to the study of NM [3,5,6,7,19,20,21]. These papers are based on the theory inaugurated by Kantorovich and its variants [21]. Basically, the conditions (K) are used in non-affine or affine invariant form. Suppose (K1) ∃ point $x_0\in D$ and parameter $s\ge 0:$${\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}\in L(\mathcal{V},\mathcal{U}),$ and

$$\parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}\mathcal{L}\left(x_0\right)\parallel \le s,$$

(K2) ∃ parameter $M_1>0:$ Lipschitz condition

$$\parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}({\mathcal{L}}^{\prime }\left(w_1\right)-{\mathcal{L}}^{\prime }\left(w_2\right))\parallel \le M_1\parallel w_1-w_2\parallel$$

holds $\forall w_1\in D$ and $w_2\in D,$

(K3)

$$s\le {\displaystyle \frac{1}{2M_1}}$$

and

(K4) $B[x_0,\rho ]\subset D,$ where parameter $\rho >0$ is given later.

Denote $B[x_0,r]:=\{x\in D:\parallel x-x_0\parallel \le r\}$ for $r>0.$ Set $\rho =r_1={\displaystyle \frac{1-\sqrt{1-2M_{1}s}}{M_1}}.$

There are many variants of Kantorovich’s convergence result for NM. One of these results follows [4,7,20].

Theorem 1.

Under conditions (K) for $\rho =r_1;$ NM is contained in $B(x_0,r_1),$ convergent to a solution $x^{*}\in B[x_0,r_1]$ of Equation (1), and

$$\parallel x_{n+1}-x_n\parallel \le u_{n+1}-u_n.$$

Moreover, the convergence is linear if $s={\displaystyle \frac{1}{2M_1}}$ and quadratic if $s<{\displaystyle \frac{1}{2M_1}}.$ Furthermore, the solution is unique $B[x_0,r_1]$ in the first case and in $B(x_0,r_2)$ in the second case where $r_2={\displaystyle \frac{1+\sqrt{1-2M_{1}s}}{M_1}}$ and scalar sequence $\left\{u_n\right\}$ is given as

$$u_0=0,u_1=s,u_{n+1}=u_n+{\displaystyle \frac{M_1{(u_n-u_{n-1})}^2}{2(1-M_1{u}_n)}}.$$

A plethora of studies have used conditions (K) [3,4,5,19,21,22,23].

Example 1.

Consider the cubic polynomial

$$c\left(x\right)=x^3-a$$

for $D=B(x_0,1-a)$ and parameter $a\in (0,{\displaystyle \frac{1}{2}}).$ Select initial point $x_0=1.$ Conditions (K) give $s={\displaystyle \frac{1-a}{3}}$ and $M_1=2(2-a).$ It follows that estimate

$${\displaystyle \frac{1-a}{3}}>{\displaystyle \frac{1}{4(2-a)}}$$

holds $\forall a\in (0,{\displaystyle \frac{1}{2}}).$ That is condition (K3) is not satisfied. Therefore convergence is not assured by this theorem. However, NM may converge. Hence, clearly, there is a need to improve the results based on the conditions K.

By looking at the crucial sufficient condition (K3) for the convergence, (K4) and the majorizing sequence given by Kantorovich in the preceding Theorem 1 one sees that if the Lipschitz constants $M_1$ is replaced by a smaller one, say $L>0$, than the convergence domain will be extended, the error distances $\parallel x_{n+1}-x_n\parallel$, $\parallel x_n-x^{*}\parallel$ will be tighter and the location of the solution more accurate. This replacement will also lead to fewer Newton iterates to reach a certain predecided accuracy (see the numerical Section). That is why with the new methodology, a new domain is obtained inside D that also contains the Newton iterates. However, then, L can replace $M_1$ in Theorem 1 to obtain the aforementioned extensions and benefits.

In this paper several avenues are presented for achieving this goal. The idea is to replace Lipschitz parameter $M_1$ by smaller ones.

(K5) Consider the center Lipschitz condition

$$\parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}({\mathcal{L}}^{\prime }\left(w_1\right)-{\mathcal{L}}^{\prime }\left(x_0\right))\parallel \le M_0\parallel w_1-x_0\parallel \forall w_1\in D,$$

the set $D_0=B[x_0,{\displaystyle \frac{1}{M_0}}]\cap D$ and the Lipschitz-2 condition

(K6)

$$\parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}({\mathcal{L}}^{\prime }\left(w_1\right)-{\mathcal{L}}^{\prime }\left(w_2\right))\parallel \le M\parallel w_1-w_2\parallel \forall w_1,w_2\in D_0.$$

These Lipschitz parameters are related as

$$M_0\le M_1,$$

(3)

$$M\le M_1$$

(4)

since

$$D_0\subset D.$$

(5)

Notice also since parameters $M_0$ and M are specializations of parameter $M_1,M_1=M_1\left(D\right)$, $M_0=M_0\left(D\right),$ but $M=M\left(D_0\right)$. Therefore, no additional work is required to find $M_0$ and M (see also [22,23]). Moreover the ratio ${\displaystyle \frac{M_0}{M}}$ can be very small (arbitrarily). Indeed,

Example 2.

Define scalar function

$$F\left(t\right)=b_{0}t+b_1+b_{2}sin{e}^{b_{3}t},$$

for $t_0=0,$ where $b_j,j=0,1,2,3$ are real parameters. It follows by this definition that for $b_3$ sufficiently large and $b_2$ sufficiently small, ${\displaystyle \frac{M_0}{M_1}}$ can be small (arbitrarily), i.e., ${\displaystyle \frac{M_0}{M_1}}⟶0.$

Then, clearly there can be a significant extension if parameters $M_1$ and $M_0$ or M and $M_0$ can be replace $M_1$ in condition (K3). Looking at this direction the following replacements are presented in a series of papers [19,22,23], respectively

$$\left(\mathrm{N}2\right) s\le {\displaystyle \frac{1}{q_2}},$$

$$\left(\mathrm{N}3\right) s\le {\displaystyle \frac{1}{q_3}},$$

and

$$\left(\mathrm{N}4\right) s\le {\displaystyle \frac{1}{q_4}},$$

where $q_1=2M_1,q_2=M_1+M_0,q_3={\displaystyle \frac{1}{4}}(4M_0+M_1+\sqrt{M_1^2+8M_1{M}_0})$ and $q_4={\displaystyle \frac{1}{4}}(4M_0+\sqrt{M_1^2+8M_0{M}_1}+\sqrt{M_1{M}_0}).$ These items are related as follows:

$$q_4\le q_3\le q_2\le q_1,$$

$$\left(\mathrm{N}2\right)\Rightarrow \left(\mathrm{N}3\right)\Rightarrow \left(\mathrm{N}4\right),$$

and as relation ${\displaystyle \frac{M_0}{M_1}}⟶0,$

$${\displaystyle \frac{q_2}{q_1}}⟶{\displaystyle \frac{1}{2}},{\displaystyle \frac{q_3}{q_2}}⟶{\displaystyle \frac{1}{4}},{\displaystyle \frac{q_4}{q_3}}⟶0$$

and

$${\displaystyle \frac{q_4}{q_2}}⟶0.$$

Preceding items indicate the times (at most) one is improving the other. These are the extensions given in this aforementioned references. However, it turns out that parameter L can replace $M_1$ in these papers (see Section 3). Denote by $\tilde{N},\tilde{q}$ the corresponding items. It follows

$${\displaystyle \frac{{\tilde{q}}_1}{q_1}}={\displaystyle \frac{M}{M_1}}⟶0,{\displaystyle \frac{{\tilde{q}}_2}{q_2}}⟶0,{\displaystyle \frac{{\tilde{q}}_3}{q_3}}⟶0$$

for ${\displaystyle \frac{M_0}{M_1}}⟶0$ and ${\displaystyle \frac{M}{M_1}}⟶0.$ Hence, the new results also extend the ones in the aforementioned references. Other extensions involve tighter majorizing sequences for NM (see Section 2) and improved uniqueness report for solution $x^{*}$ (Section 3). The applications appear in Section 4 followed by conclusions in Section 5.

2. Majorizations

Let $K_0,M_0,K,M$ be given positive parameters and s be a positive variable. The real sequence $\left\{t_n\right\}$ defined for $t_0=0,t_1=s,t_2=t_1+{\displaystyle \frac{K{(t_1-t_0)}^2}{2(1-K_0{t}_1)}}$ and $\forall n=0,1,2,\dots$ by

$$t_{n+2}=t_{n+1}+{\displaystyle \frac{M{(t_{n+1}-t_n)}^2}{2(1-M_0{t}_{n+1})}}$$

(6)

plays an important role in the study of NM, we adopted the notation $t_n\left(s\right)=t_n$$\forall n=1,2,\dots .$ That is why some convergence results for it are listed in what follows next in this study.

Lemma 1.

Suppose conditions

$$K_0{t}_1<1and{t}_{n+1}<{\displaystyle \frac{1}{M_0}}$$

(7)

hold $\forall n=1,2,\dots .$ Then, the following assertions hold

$$t_n<t_{n+1}<{\displaystyle \frac{1}{M_0}}$$

(8)

and $\exists t^{*}\in [s,{\displaystyle \frac{1}{M_0}}]$ such that $\underset{n\to \infty }{lim}{t}_n=t^{*}.$

Proof. 

The definition of sequence $\left\{t_n\right\}$ and the condition (7) implies (8). Moreover, increasing sequence $\left\{t_n\right\}$ has ${\displaystyle \frac{1}{M_0}}$ as an upper bound. Hence, it is convergent to its (unique) least upper bound $t^{*}.$ □

Next, stronger convergence criteria are presented. However, these criteria are easier to verify than conditions of Lemma 1. Define parameter $\delta$ by

$$\delta ={\displaystyle \frac{2M}{M+\sqrt{M^2+8M_{0}M}}}.$$

(9)

This parameter plays a role in the following results.

Case:$K_0=M_0$ and $K=M.$

Part (i) of the next auxiliary result relates to the Lemma in [19].

Lemma 2.

Suppose condition

$$s\le {\displaystyle \frac{1}{2M_2}}$$

(10)

holds, where

$$M_2={\displaystyle \frac{1}{4}}(M+4M_0+\sqrt{M^2+8M_{0}M}).$$

(11)

Then, the following assertions hold

(i)

Estimates

$$t_{n+1}-t_n\le \delta (t_n-t_{n-1})$$

(12)

$$t_n<{\displaystyle \frac{1-{\delta }^{n+1}}{1-\delta }}s<{\displaystyle \frac{s}{1-\delta }}$$

(13)

hold. Moreover, conclusions of Lemma 1 are true for sequence $\left\{t_n\right\}.$ The sequence, $\left\{t_n\right\}$ converges linearly to $t^{*}\in (0,{\displaystyle \frac{s}{1-\delta }}].$ Furthermore, if for some $\mu >0$

$$s<{\displaystyle \frac{\mu }{(1+\mu )M_2}}.$$

(14)

Then, the following assertions hold

(ii)

$$t_{n+1}-t_n\le {\displaystyle \frac{M}{2}}(1+\mu ){(t_n-t_{n-1})}^2$$

(15)

and

$$t_{n+1}-t_n\le {\displaystyle \frac{1}{\alpha }}{\left(\alpha s\right)}^{2^n},$$

(16)

where $\alpha ={\displaystyle \frac{M}{2}}(1+\mu )$ and the conclusions of Lemma 1 for sequence $\left\{t_n\right\}$ are true. The sequence, $\left\{t_n\right\}$ converges quadratically to $t^{*}.$

Proof. 

(i)

It is given in [19].

(ii)

Notice that condition (14) implies (11) by the choice of parameter $\mu .$ Assertion (15) holds if estimate

$$0<{\displaystyle \frac{M}{2(1-M_0{t}_{n+1})}}\le {\displaystyle \frac{M}{2}}(1+\mu )$$

(17)

is true. This estimate is true for $n=1,$ since it is equivalent to $M_{0}s\le {\displaystyle \frac{\mu }{1+\mu }}.$ But this is true by $M_0\le 2M_2,$ condition (11) and inequality ${\displaystyle \frac{\mu M_0}{(1+\mu )2M_2}}\le {\displaystyle \frac{\mu }{1+\mu }}.$ Then, in view of estimate (13), estimate (17) certainly holds provided that

$$(1+\mu )M_0(1+\delta +\dots +{\delta }^{n+1})s-\mu \le 0.$$

(18)

This estimate motivates the introduction of recurrent polynomials $p_n$ which are defined by

$$p_n\left(t\right)=(1+\mu )M_0(1+t+\dots +t^{n+1})s-\mu ,$$

(19)

$\forall t\in [0,1).$ In view of polynomial $p_n$ assertion (18) holds if

$$p_n\left(t\right)\le 0att=\delta .$$

(20)

The polynomials $p_n$ are connected:

$$p_{n+1}\left(t\right)-p_n\left(t\right)=(1+\mu )M_0{t}^{n+2}s>0,$$

so

$$p_n\left(t\right)<p_{n+1}\left(t\right)\forall t\in [0,1).$$

(21)

Define function $p_{\infty }:[0,1)⟶\mathbb{R}$ by

$$p_{\infty }\left(t\right)=\underset{n⟶\infty }{lim}{p}_n\left(t\right).$$

(22)

It follows by definitions (19) and (20) that

$$p_{\infty }\left(t\right)={\displaystyle \frac{(1+\mu )M_{0}s}{1-t}}-\mu .$$

(23)

Hence, assertion (20) holds if

$$p_{\infty }\left(t\right)\le 0att=\delta ,$$

(24)

or equivalently

$$M_{0}s\le {\displaystyle \frac{\mu }{1+\mu }}{\displaystyle \frac{\sqrt{M^2+8M_{0}M}-M}{\sqrt{M^2+8M_{0}M}+M}},$$

which can be rewritten as condition (14). Therefore, the induction for assertion (17) is completed. That is assertion (15) holds by the definition of sequence $\left\{t_n\right\}$ and estimate (15). It follows that

$$\begin{array}{ccc}\hfill \alpha (t_{n+1}-t_n)& \le & {\alpha }^2(t_n-t_{n-1})={\left(\alpha (t_n-t_{n-1})\right)}^2,\hfill \\ & \le & {\alpha }^2{\left(\alpha (t_{n-1}-t_{n-2})\right)}^2\hfill \\ & \le & {\alpha }^2{\alpha }^2{(t_{n-1}-t_{n-2})}^{2^2}\hfill \\ & \le & {\alpha }^2{\alpha }^2{\alpha }^2{(t_{n-2}-t_{n-3})}^{2^3}\hfill \\ & ⋮\end{array}$$

so

$$\begin{array}{ccc}\hfill t_{n+1}-t_n& \le & {\alpha }^{1+2+2^2+\dots +2^{n-1}}{s}^{2^n}\hfill \\ & =& {\displaystyle \frac{1}{\alpha }}{\left(\alpha s\right)}^{2^n}.\hfill \end{array}$$

Notice also that $M\mu <4M_2,$ then ${\displaystyle \frac{\mu }{(1+\mu )M_1}}<{\displaystyle \frac{2}{M(1+\mu )}},$ so $\alpha s<\mu .$ □

Remark 1.

(1)

The technique of recurrent polynomials in part (i) is used: to produce convergence condition (11) and a closed form upper bound on sequence $\left\{t_n\right\}$ (see estimate (13)) other than ${\displaystyle \frac{1}{M_0}}$ and $t^{*}$ (which is not given in closed form). This way we also established the linear convergence of sequence $\left\{t_n\right\}.$ By considering condition (14) but being able to use estimate (13) we establish the quadratic convergence of sequence $\left\{t_n\right\}$ in part (ii) of Lemma 2.

(2)

If $\mu =1,$ then (14) is the strict version of condition (10).

(3)

Sequence $\left\{t_n\right\}$ is tighter than the Kantorovich sequence $\left\{u_n\right\}$ since $M_0\le M_1$ and $M\le M_1.$ Concerning the ration of convergence $\alpha s$ this is also smaller than $r={\displaystyle \frac{2M_{1}s}{{(1-\sqrt{1-2M_{1}s})}^2}}$ given in the Kantorovich Theorem [19]. Indeed, by these definitions $\alpha s<r$ provided that $\mu \in (0,{\mu }_1),$ where ${\mu }_1={\displaystyle \frac{4M_1}{M{(1+\sqrt{1-2M_{1}s})}^2}}-1.$ Notice that

$${(1+\sqrt{1-2M_{1}s})}^2<{(1+1)}^2=4\le {\displaystyle \frac{4M_1}{M}},$$

so ${\mu }_1>0.$

Part (i) of the next auxiliary result relates to a Lemma in [19]. The case $M_0=M$ has been studied in the introduction. So, in the next Lemma we assume $M_0\ne M$ in part (ii).

Lemma 3.

Suppose condition

$$s\le {\displaystyle \frac{1}{2M_3}}$$

(25)

holds, where

$$M_3={\displaystyle \frac{1}{8}}(4M_0+\sqrt{M_{0}M+8M_0^2}+\sqrt{M_{0}M}).$$

Then, the following assertions hold

(i)

$$t_{n+1}-t_n\le \delta (t_n-t_{n-1})\le {\displaystyle \frac{{\delta }^{n-1}{M}_0{s}^2}{2(1-M_{0}s)}}$$

(26)

and

$$t_{n+2}\le s+{\displaystyle \frac{1-{\delta }^{n+1}}{1-\delta }}(t_2-t_1)<t^{**}=s+{\displaystyle \frac{t_2-t_1}{1-\delta }}s,\forall n=1,2,\dots .$$

(27)

Moreover, conclusions of Lemma 1 are true for sequence $\left\{t_n\right\}.$ The sequence $\left\{t_n\right\}$ converges linearly to $t^{*}\in (0,t^{**}].$ Define parameters $h_0$ by

$$h_0={\displaystyle \frac{2(\sqrt{M_{0}M+8M_0^2}+\sqrt{M_{0}M})}{M(\sqrt{M_{0}M+8M_0^2}+\sqrt{M_{0}M}+4M_0)}},{\overline{M}}_3={\displaystyle \frac{h_0}{2}},$$

$$\gamma =1+\mu ,\beta ={\displaystyle \frac{\mu }{1+\mu }},d=2(1-\delta )$$

and

$$\mu ={\displaystyle \frac{M_0}{2M_3-M_0}}.$$

(ii)

Suppose

$$M_0<M\le {\displaystyle \frac{M_0}{\theta }}$$

(28)

and (25) hold, where $\theta \approx 0.6478$ is the smallest solution of scalar equation $2z^4+z-1=0.$ Then, the conclusions of Lemma 2 also hold for sequence $\left\{t_n\right\}.$ The sequence converges quadratically to $t^{*}\in (0,t^{**}].$

(iii)

Suppose

$$M\ge {\displaystyle \frac{1}{\theta }}{M}_{0}ands<{\displaystyle \frac{1}{2{\overline{M}}_3}}$$

(29)

hold. Then, the conclusions of Lemma 2 are true for sequence $\left\{t_n\right\}.$ The sequence $\left\{t_n\right\}$ converges quadratically to $t^{*}\in (0,t^{**}].$

(iv)

$M_0>M$ and (25) hold. Then, ${\overline{M}}_3\le M_3$ and the conclusions of Lemma 2 are true for sequence $\left\{t_n\right\}.$ The sequence $\left\{t_n\right\}$ converges quadratically to $t^{*}\in (0,t^{**}].$

Proof. 

(i)

It is given in Lemma 2.1 in [23].

(ii)

As in Lemma 2 but using estimate (27) instead of (13) to show

$${\displaystyle \frac{M}{2(1-M_0{t}_{n+1})}}\le {\displaystyle \frac{M\gamma }{2}}.$$

It suffices

$$\gamma M_0\left(s+{\displaystyle \frac{1-{\delta }^n}{1-\delta }}(t_2-t_1)\right)+1-\gamma \le 0$$

or

$$p_n\left(t\right)\le 0att=\delta ,$$

(30)

where

$$p_n\left(t\right)=\gamma M_0(1+t+\dots +t^{n-1})(t_2-t_1)+\gamma M_{0}s+1-\gamma .$$

Notice that

$$p_{n+1}\left(t\right)-p_n\left(t\right)=\gamma M_0{t}^n(t_2-t_1)>0.$$

Define function $p_{\infty }:[0,1)⟶\mathbb{R}$ by

$$p_{\infty }\left(t\right)=\underset{n⟶\infty }{lim}{p}_n\left(t\right).$$

It follows that

$$p_{\infty }\left(t\right)={\displaystyle \frac{\gamma M_0(t_2-t_1)}{1-t}}+\gamma M_{0}s+1-\gamma .$$

So, (30) holds provided that

$$p_{\infty }\left(t\right)\le 0att=\delta .$$

(31)

By the definition of parameters $\gamma ,d,\beta$ and for $M_{0}s=x,$ (31) holds if

$${\displaystyle \frac{x^2}{2(1-x)(1-\delta )}}+x\le \beta$$

or

$$(d-1)x^2+(1+\beta )x-\beta \le 0$$

or

$$x\le {\displaystyle \frac{1+\beta -\sqrt{{(1-\beta )}^2+4\beta d}}{2(1-d)}}$$

or

$$s\le {\displaystyle \frac{1+\beta -\sqrt{{(1-\beta )}^2+4\beta d}}{2(1-d)}}.$$

(32)

Claim. The right hand side of assertion (31) equals ${\displaystyle \frac{1}{M_2}}.$ Indeed, this is true if

$$1+\beta -\sqrt{{(1-\beta )}^2+4\beta d}={\displaystyle \frac{2M_0(1-d)}{M_2}}$$

or

$$1+\beta -{\displaystyle \frac{2M_0(1-d)}{2M_3}}=\sqrt{{(1-\beta )}^2+4\beta d}$$

or by squaring both sides

$$1+{\beta }^2+{\displaystyle \frac{4M_0^2{(1-d)}^2}{4M_3^2}}+2\beta -{\displaystyle \frac{4M_0(1-d)}{2M_3}}-{\displaystyle \frac{4\beta M_0(1-d)}{2M_3}}=1+{\beta }^2-2\beta +4\beta d$$

or

$$\beta \left(1-{\displaystyle \frac{M_0(1-d)}{2M_3}}-d\right)={\displaystyle \frac{M_0(1-d)}{2M_3}}\left(1-{\displaystyle \frac{M_0}{2M_3}}\right)$$

or

$$\beta \left(1-{\displaystyle \frac{M_0}{2M_3}}\right)(1-d)=\left(1-{\displaystyle \frac{M_0}{2M_3}}\right)(1-d){\displaystyle \frac{M_0}{2M_3}}$$

or

$$\beta ={\displaystyle \frac{M_0}{2M_3}}$$

or

$${\displaystyle \frac{\mu }{1+\mu }}={\displaystyle \frac{M_0}{2M_3}}$$

or

$$\mu ={\displaystyle \frac{M_0}{2M_3-M_0}},$$

which is true. Notice also that

$$\begin{array}{ccc}\hfill 2M_3-M_0& =& {\displaystyle \frac{1}{4}}(4M_0+\sqrt{M_{0}M}+\sqrt{M_{0}M+8M_0^2})\hfill \\ & =& {\displaystyle \frac{1}{4}}(\sqrt{M_{0}M}+\sqrt{M_{0}M+8M_0^2})>0\hfill \end{array}$$

and $2M_3-2M_0>0,$ since $2M_3-M_0={\displaystyle \frac{\sqrt{M_{0}M}+\sqrt{M_{0}M+8M_0^2}-4M_0}{4}},$$M_0<\sqrt{M_{0}M}$ and $3M_0<\sqrt{M_{0}M+8M_0^2}$ (by condition (25)). Thus, $\mu \in (0,1)$. It remains to show

$$\alpha ={\displaystyle \frac{M}{2}}(1+\mu )s<1$$

or by the choice of $\mu$ and $M_2$

$${\displaystyle \frac{M_2}{2}}\left(1+{\displaystyle \frac{M_0}{2M_3-M_0}}\right)s<1$$

or

$$s<{\displaystyle \frac{1}{2{\overline{M}}_3}}.$$

(33)

Claim.${\overline{M}}_3\le M_3.$ By the definition of parameters $M_2$ and ${\overline{M}}_3$ it must be shown that

$${\displaystyle \frac{M(\sqrt{M_{0}M}+\sqrt{M_{0}M+8M_0^2}+4M_0}{2(\sqrt{M_{0}M}+\sqrt{M_{0}M+8M_0^2})}}\le {\displaystyle \frac{\sqrt{M_{0}M}+\sqrt{M_{0}M+8M_0^2}+4M_0}{4}}$$

or if for $y={\displaystyle \frac{M_0}{M}}$

$$2-\sqrt{y}\le \sqrt{y+8y^2}.$$

(34)

By (28) $2-\sqrt{y}>0,$ so estimate (34) holds if $2y^2+\sqrt{y}-1\ge 0$ or

$$2z^4+z-1\ge 0forz=\sqrt{y}.$$

However, the last inequality holds by (28). The claimed is justified. So, estimate (33) holds by (25) and this claim.

(iii)

It follows from the proof in part (ii). However, this time $M_2\le {\overline{M}}_2$ follows from (29). Notice also that according to part (ii) condition (25) implies (29). Moreover, according to part (iii) condition (29) implies (25).

(iv)

As in case (ii) estimate (34) must be satisfied. If $M_0\ge 4M,$ then the estimate (34) holds, since $2-\sqrt{y}\le 0.$ If $M<M_0<4M$ then again $M_0>\theta M,$ so estimate (34) or equivalently $2z^2+z-1>0$ holds.

□

Comments similar to Remark 1 can follow for Lemma 3.

Case. Parameters $K_0$ and K are not equal to $M_0.$ Comments similar to Remark 1 can follow for Lemma 3.

It is convenient to define parameter ${\delta }_0$ by

$${\delta }_0={\displaystyle \frac{K(t_2-t_1)}{2(1-K_0{t}_2)}}$$

and the quadratic polynomial $\phi$ by

$$\phi \left(t\right)=(MK+2\delta M_0(K-2K_0))t^2+4\delta (M_0+K_0)t-4\delta .$$

The discriminant ∆ of polynomial q can be written as

$$∆=16\delta {\left(\delta (M_0-K_0)\right)}^2+(M+2\delta M_0)K>0.$$

It follows that the root ${\displaystyle \frac{1}{h_1}}$ given by the quadratic formula can be written as

$${\displaystyle \frac{1}{2h_1}}={\displaystyle \frac{2}{\delta (M_0+K_0)+\sqrt{{\left(\delta (M_0+K_0)\right)}^2+\delta (MK+2\delta M_0)(K-2K_0)}}}.$$

Denote by ${\displaystyle \frac{1}{h_2}}$ the unique positive zero of equation

$$M_0(K-2K_0)t^2+2M_{0}t-1=0.$$

This root can be written as

$${\displaystyle \frac{1}{2h_2}}={\displaystyle \frac{1}{M_0+\sqrt{M^2+M_0(K-2K_0)}}}.$$

Define parameter $M_4$ by

$${\displaystyle \frac{1}{M_4}}=min\left\{{\displaystyle \frac{1}{h_1}},{\displaystyle \frac{1}{h_2}}\right\}.$$

(35)

Part (i) of the next auxiliary result relates to Lemma 2.1 in [22].

Lemma 4.

Suppose

$$s\le {\displaystyle \frac{1}{2M_4}}$$

(36)

holds, where parameter $M_4$ is given by Formula (35). Then, the following assertions hold

(i)

Estimates

$$t_{n+2}-t_{n+1}\le {\delta }_0{\delta }^{n-1}{\displaystyle \frac{K{s}^2}{2(1-K_{0}s)}},$$

and

$$t_{n+2}\le s+\left(1+{\delta }_0{\displaystyle \frac{1-{\delta }^n}{1-\delta }}\right)(t_2-t_1)\le \overline{t}=s+\left(1+{\displaystyle \frac{{\delta }_0}{1-\delta }}\right)(t_2-t_1).$$

Moreover, conclusions of Lemma 2 are true for sequence $\left\{t_n\right\}.$ The sequence $\left\{t_n\right\}$ converges linearly to $t^{*}\in (0,\overline{t}].$

(ii)

Suppose

$$M_0\left({\displaystyle \frac{{\delta }_0(t_2-t_1)}{1-\delta }}+s\right)\le \beta ,$$

(37)

$$s<{\displaystyle \frac{2}{(1+\mu )M}}$$

(38)

and (36) hold for some $\mu >0.$ Then, the conclusions of Lemma 3 are true for sequence $\left\{t_n\right\}.$ The sequence $\left\{t_n\right\}$ converges quadratically to $t^{*}\in (0,\overline{t}].$

Proof. 

(i)

It is given in Lemma 2.1 in [22].

(ii)

Define polynomial $p_n$ by

$$p_n\left(t\right)=\gamma M_0{\delta }_0(1+t+\dots +t^{n-1})(t_2-t-1)+\gamma M_{0}s+1-\gamma .$$

By this definition it follows

$$p_{n+1}\left(t\right)-p_n\left(t\right)=\gamma M_0{\delta }_0(t_2-t_1)t^n>0.$$

As in the proof of Lemma 3 (ii), estimate

$${\displaystyle \frac{M}{2(1-M_0{t}_{n+1})}}\le {\displaystyle \frac{M}{2}}\gamma$$

holds provided that

$$p_n\left(t\right)\le 0att=\delta .$$

(39)

Define function $p_{\infty }:[0,1)⟶\mathbb{R}$ by

$$p_{\infty }\left(t\right)=\underset{n⟶\infty }{lim}{p}_n\left(t\right).$$

It follows by the definition of function $p_{\infty }$ and polynomial $p_n$ that

$$p_{\infty }\left(t\right)={\displaystyle \frac{\gamma M_0{\delta }_0(t_2-t_1)}{1-t}}+\gamma M_{0}s-\gamma .$$

Hence, estimate (39) holds provided that

$$p_{\infty }\left(t\right)\le 0att=\delta .$$

However, this assertion holds, since $\mu \in (0,1)$. Moreover, the definition of $\alpha$ and condition (38) of the Lemma 4 imply

$$\alpha s={\displaystyle \frac{M}{2}}(1+\mu ).$$

Hence, the sequence $\left\{t_n\right\}$ converges quadratically to $t^{*}.$ □

Remark 2.

Conditions (36)–(38) can be condensed and a specific choice for μ can be given as follows: Define function $f:\left[0,{\displaystyle \frac{1}{K_0}}\right)⟶\mathbb{R}$ by

$$f\left(t\right)=1-M_0\left({\displaystyle \frac{{\delta }_0\left(t\right)(t_2\left(t\right)-t_1\left(t\right))}{1-\delta }}+t\right).$$

It follows by this definition

$$f\left(0\right)=1>0,f\left(t\right)⟶-\infty ast⟶{{\displaystyle \frac{1}{K_0}}}^{-}.$$

Denote by ${\mu }_2$ the smallest solution of equation $f\left(t\right)=0$ in $\left(0,{\displaystyle \frac{1}{K_0}}\right).$ Then, by choosing $\mu ={\mu }_2$ conditions (37) holds as equality. Then, if follows that if we solve the first condition in (37) for “s", then conditions (36)–(38) can be condensed as

$$s\le s_{1}min\left\{{\displaystyle \frac{1}{M_4}},{\displaystyle \frac{2}{(2+{\mu }_2)M}}\right\}.$$

(40)

If $s_1={\displaystyle \frac{2}{(2+{\mu }_2)M}},$ then condition (40) should hold as a strict inequality to show quadratic convergence.

3. Semi-Local Convergence

Sequence $\left\{t_n\right\}$ given by (6) was shown to be majorizing for $\left\{x_n\right\}$ and tighter than $\left\{u_n\right\}$ under conditions of Lemmas in [19,22,23], respectively. These Lemmas correspond to part (i) of Lemma 1, Lemma 3 and Lemma 4, respectively. However, by asking the initial approximation s to be bounded above by a slightly larger bound the quadratic order of convergence is recovered. Hence, the preceding Lemmas can replace the order ones, respectively in the semi-local proofs for NM in these references. The parameter $K_0$ and K are connected to $x_0$ and ${\mathcal{L}}^{\prime }$ as follows

(K7) ∃ parameter $K_0>0$ such that for $x_1=x_0-{\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}\mathcal{L}\left(x_0\right)$

$$\parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}({\mathcal{L}}^{\prime }\left(x_1\right)-{\mathcal{L}}^{\prime }\left(x_0\right))\parallel \le K_0\parallel x_1-x_0\parallel ,$$

(K8) ∃ parameter K such that $\forall \xi \in [0,1],\forall x,y\in D_0,$

$$∥{\int }_0^1{\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}({\mathcal{L}}^{\prime }(x+\xi (y-x))-{\mathcal{L}}^{\prime }\left(x\right))d\xi ∥\le {\displaystyle \frac{K}{2}}\parallel y-x\parallel .$$

Note that $K_0\le M_0$ and $K\le M.$ The convergence criteria in Lemmas 1, 3 and 4 do not necessarily imply each other in each case. That is why we do not only rely on Lemma 4 to show the semi-local convergence of NM. Consider the following three sets of conditions:

• (A1): (K1), (K4), (K5), (K6) and conditions of Lemma 1 hold for $\rho =t^{*},$ or
• (A2): (K1), (K4) (K5), (K6), conditions of Lemma 2 hold with $\rho =t^{*},$ or
• (A3): (K1), (K4) (K5), (K6), conditions of Lemma 3 hold with $\rho =t^{*},$ or
• (A4): (K1), (K4) (K5), (K6), conditions of Lemma 4 hold with $\rho =t^{*}.$

The upper bounds of the limit point given in the Lemmas and in closed form can replace $\rho$ in condition (K4). The proof are omitted in the presentation of the semi-local convergence of NM since the proof is given in the aforementioned references [19,20,22,23] with the exception of quadratic convergence given in part (ii) of the presented Lemmas.

Theorem 2.

Suppose any of conditions $Ai,i=1,2,3,4$ hold. Then, sequence $\left\{x_n\right\}$ generated by NM is well defined in $B[x_0,\rho ],$ remains in $B[x_0,\rho ]\forall n=0,1,2,\dots$ and converges to a solution $x^{*}\in B[x_0,\rho ]$ of equation $\mathcal{L}\left(x\right)=0.$ Moreover, the following assertion hold $\forall n=0,1,2,\dots$

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

and

$$\parallel x^{*}-x_n\parallel \le t^{*}-t_n.$$

The convergence ball is given next. Notice, however that we do not use all conditions $Ai.$

Proposition 1.

Suppose: there exists a solution $x^{*}\in B(x_0,{\rho }_0)$ of equation $\mathcal{L}\left(x\right)=0$ for some ${\rho }_0>0;$ condition (K5) holds and $\exists {\rho }_1\ge {\rho }_0$ such that

$${\displaystyle \frac{M_0}{2}}({\rho }_0+{\rho }_1)<1.$$

(41)

Set $D_1=D\cap B[x_0,{\rho }_1].$ Then, the only solution of equation $\mathcal{L}\left(x\right)=0$ in the set $D_1$ is $x^{*}.$

Proof. 

Let $x_{*}\in D_1$ be a solution of equation $\mathcal{L}\left(x\right)=0.$ Define linear operator $J={\int }_0^1{\mathcal{L}}^{\prime }(x^{*}+\tau (x_{*}-x^{*}))d\tau .$ Then, using (K5) and (41)

$$\begin{array}{ccc}\hfill \parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}({\mathcal{L}}^{\prime }\left(x_0\right)-J)\parallel & \le & M_0{\int }_0^1((1-\tau )\parallel x_0-x^{*}\parallel +\tau \parallel x_0-x_{*}\parallel )d\tau \hfill \\ \hfill & \le & {\displaystyle \frac{M_0}{2}}({\rho }_0+{\rho }_1)<1.\hfill \end{array}$$

(42)

Therefore, $x^{*}=x_{*}$ is implied by the invertability of J and

$$J(x^{*}-x_{*})=\mathcal{L}\left(x^{*}\right)-\mathcal{L}\left(x_{*}\right)=0.$$

If conditions of Theorem 2 hold, set ${\rho }_0=\rho .$ □

4. Numerical Experiments

Two experiments are presented in this Section.

Example 3.

Recall Example 1 (with $\mathcal{L}\left(x\right)=c\left(x\right)$). Then, the parameters are $s={\displaystyle \frac{1-a}{3}}$, $K_0={\displaystyle \frac{a+5}{3}},M_0=3-a,M_1=2(2-a).$ It also follows $D_0=B(1,1-a)\cap B\left[1,{\displaystyle \frac{1}{M_0}}\right]=B\left[1,{\displaystyle \frac{1}{M_0}}\right],$ so $K=M=2\left(1+{\displaystyle \frac{1}{3-a}}\right).$ Denote by $T_i,i=1,2,3,4$ the set of values a for which conditions $\left(K3\right),\left(N2\right)-\left(N4\right)$ are satisfied. Then, by solving these inequalities for $a:$$T_1=\varnothing ,T_2=[0.4648,0.5),T_3=[0.4503,0.5),$ and $T_4=[0.4272,0.5),$ respectively.

The domain can be further extended. Choose $a=0.4,$ then, ${\displaystyle \frac{1}{M_0}}=0.3846.$ The following

Table 1. Sequence (6) for Example 1.

n	1	2	3	4	5	6	7	8
$t_n$	0.2000	0.2865	0.3272	0.3425	0.3455	0.3456	0.3456	0.3456

shows, that the conditions of Lemma 1, since $K_{0}t<1$ and $M_0{t}_{n+1}<1$$\forall n=1,2,\dots$.

Example 4.

Let $\mathcal{U}=\mathcal{V}={\mathrm{I}\mathrm{R}}^3$, $D=B(x_0,0.5)$ and

$$\mathcal{L}\left(x\right)={\left(e^{x_1}-1,x_2^3+x_2,x_3\right)}^T.$$

The equation $\mathcal{L}\left(x\right)=0$ has the solution $x^{*}={(0,0,0)}^T$ and ${\mathcal{L}}^{\prime }\left(x\right)=diag(e^{x_1},3x_2^2+1,1)$.

Let $x_0={(0.1,0.1,0.1)}^T$. Then $s=\parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}\mathcal{L}\left(x_0\right){\parallel }_{\infty }\approx 0.1569$,

$$M_0=max\left\{{\displaystyle \frac{e^{0.6}}{e^{0.1}}},{\displaystyle \frac{3(0.6+0.1)}{1.03}}\right\}\approx 2.7183,$$

$$M_1=max\left\{{\displaystyle \frac{e^{0.6}}{e^{0.1}}},{\displaystyle \frac{3(0.6+0.6)}{1.03}}\right\}\approx 3.49513.$$

It also follows that ${\displaystyle \frac{1}{M_0}}\approx 0.3679$, $D_0=D\cap B[x_0,{\displaystyle \frac{1}{M_0}}]=B[0.1,0.3679]$ and

$$K_0=max\left\{{\displaystyle \frac{e^{p_1}}{e^{0.1}}},{\displaystyle \frac{3(p_2+0.1)}{1.03}}\right\}\approx 2.3819,$$

$$M=K=max\left\{{\displaystyle \frac{e^{p_1}}{e^{0.1}}},{\displaystyle \frac{6p_1}{1.03}}\right\}\approx 2.7255,$$

where $p_1=0.1+{\displaystyle \frac{1}{M_0}}\approx 0.4679$, $p_2\approx 0.0019$.

Notice that $M_0<M_1$ and $M<M_1.$ The Kantorovich convergence condition (K3) is not fulfilled, since $2M_{1}s\approx 1.0968>1.$ Hence, convergence of converge NM is not assured by the Kantorovich criterion. However, the new conditions (N2)–(N4) are fulfilled, since $q_{2}s\approx 0.9749<1$, $q_{3}s\approx 0.9320<1$, $q_{4}s\approx 0.8723<1$.

The following

Table 2. Sequence (6) for Example 4.

n	1	2	3	4	5	6
$t_n$	0.1569	0.2154	0.2266	0.2271	0.2271	0.2271

shows, that the conditions of Lemma 1 are fulfilled, since $K_{0}t<1$ and $M_0{t}_{n+1}<1$$\forall n=1,2,\dots$.

Example 5.

Let $\mathcal{U}=\mathcal{V}=C[0,1]$ be the domain of continuous real functions defined on the interval $[0,1].$ Set $D=B[x_0,3],$ and define operator $\mathcal{L}$ on D as

$$\mathcal{L}\left(v\right)\left(v_1\right)=v\left(v_1\right)-y\left(v_1\right)-{\int }_0^{1}N(v_1,t)v^3\left(t\right)dt,v\in C[0,1],v_1\in [0,1],$$

(43)

where y is given in $C[0,1],$ and N is a kernel given by Green’s function as

$$N(v_1,t)=\left\{\begin{array}{cc}(1-v_1)t,& t\le v_1\\ v_1(1-t),& v_1\le t.\end{array}\right.$$

(44)

By applying this definition the derivative of $\mathcal{L}$ is

$$\left[{\mathcal{L}}^{\prime }\left(v\right)\left(z\right)\right]\left(v_1\right)=z\left(v_1\right)-3{\int }_0^{1}N(v_1,t)v^2\left(t\right)z\left(t\right)dt$$

(45)

$z\in C[0,1],v_1\in [0,1].$ Pick $x_0\left(v_1\right)=y\left(v_1\right)=1.$ The norm-max is used. It then follows from (43)–(45) that ${\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}\in L(B_2,B_1),$

$$\parallel I-{\mathcal{L}}^{\prime }\left(x_0\right)\parallel <0.375,\parallel {\mathcal{L}}^{\prime }{\left(x_0\right)}^{-1}\parallel \le 1.6,$$

$$s=0.2,M_0=2.4,M_1=3.6,$$

and $D_0=B(x_0,3)\cap B[x_0,0.4167]=B[x_0,0.4167],$ so $M=1.5.$ Notice that $M_0<M_1$ and $M<M_1.$ Choose $K_0=K=M_0.$ The Kantorovich convergence condition (K3) is not fulfilled, since $2M_{1}s=1.44>1.$ Hence, convergence of converge NM is not assured by the Kantorovich criterion. However, new condition (36) is fulfilled, since $2M_{4}s=0.6<1.$

Example 6.

Let $\mathcal{U}=\mathcal{V}=\mathrm{I}\mathrm{R}$, $D=(-1,1)$ and

$$\mathcal{L}\left(x\right)=e^x+2x-1.$$

The equation $\mathcal{L}\left(x\right)=0$ has the solution $x^{*}=0$. The parameters are $s=\left|{\displaystyle \frac{e^{x_0}+2x_0-1}{e^{x_0}+2}}\right|$, $M_0=M_1=e$, $K_0=K=M=e^{x_0+\frac{1}{e}}$ and

$$D_0=(-1,1)\cap \left[x_0-\frac{1}{e},x_0+\frac{1}{e}\right]=\left[x_0-\frac{1}{e},x_0+\frac{1}{e}\right].$$

Let us choose $x_0=0.15$. Then, $s\approx 0.1461$. Conditions (K3) and (N2) are fulfilled. The majorizing sequences $\left\{t_n\right\}$ (6) and $\left\{u_n\right\}$ from Theorem 1 are:

$$\left\{t_n\right\}=\{0,0.1461,0.1698,0.1707,0.1707,0.1707,0.1707\},$$

$$\left\{u_n\right\}=\{0,0.1461,0.1942,0.2008,0.2009,0.2009,0.2009,0.2009\}.$$

In

Table 3. Results for $x_0=0.15$ for Example 6.

n	$|{\mathit{x}}_{\mathit{n}+1}-{\mathit{x}}_{\mathit{n}}|$	$|{\mathit{t}}_{\mathit{n}+1}-{\mathit{t}}_{\mathit{n}}|$	$|{\mathit{u}}_{\mathit{n}+1}-{\mathit{u}}_{\mathit{n}}|$
0	1.4607 × 10${}^{-1}$	1.4607 × 10${}^{-1}$	1.4607 × 10${}^{-1}$
1	3.9321 × 10${}^{-3}$	2.3721 × 10${}^{-2}$	4.8092 × 10${}^{-2}$
2	2.5837 × 10${}^{-6}$	8.7693 × 10${}^{-4}$	6.6568 × 10${}^{-3}$
3	1.1126 × 10${}^{-12}$	1.2039 × 10${}^{-6}$	1.3262 × 10${}^{-4}$
4	0	2.2688× 10${}^{-12}$	5.2681× 10${}^{-8}$

, there are error bounds. Notice that the new error bounds are tighter, than the ones in Theorem 1.

Let us choose $x_0=0.2$. Then, $s\approx 0.1929$. In this case condition (K3) is not held, but (N2) holds. The majorizing sequence $\left\{t_n\right\}$ (6) is:

$$\left\{t_n\right\}=\{0,0.1929,0.2427,0.2491,0.2492,0.2492,0.2492,0.2492\}.$$

Table 4. Results for $x_0=0.2$ for Example 6.

n	$|{\mathit{x}}_{\mathit{n}+1}-{\mathit{x}}_{\mathit{n}}|$	$|{\mathit{t}}_{\mathit{n}+1}-{\mathit{t}}_{\mathit{n}}|$
0	1.929 × 10${}^{-1}$	1.929 × 10${}^{-1}$
1	7.0934 × 10${}^{-3}$	4.9769 × 10${}^{-2}$
2	8.4258 × 10${}^{-6}$	6.4204 × 10${}^{-3}$
3	1.1832 × 10${}^{-11}$	1.1263 × 10${}^{-4}$
4	0	3.4690 × 10${}^{-8}$

shows the error bounds from Theorem 2.

5. Conclusions

We developed a comparison between results on the semi-local convergence of NM. There exists an extensive literature on the convergence analysis of NM. Most convergence results are based on recurrent relations, where the Lipschitz conditions are given in affine or non-affine invariant forms.The new methodology uses recurrent functions. The idea is to construct a domain included in the one used before which also contains the Newton iterates. That is important, since the new results do not require additional conditions. This way the new sufficient convergence conditions are weaker in the Lipschitz case, since they rely on smaller constants. Other benefits include tighter error bounds and more precise uniqueness of the solution results. The new constants are special cases of earlier ones. The methodology is very general making it suitable to extend the usage of other numerical methods under Hölder or more generalized majorant conditions. This will be the topic of our future work.