# Convergence Behavior for Newton-Steffensen’s Method underγ-Condition of Second Derivative

Authors: Yonghui Ling; Xiubin Xu; Shaohua Yu
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

The present paper is concerned with the semilocal as well as the local convergence problems of Newton-Steffensen’s method to solve nonlinear operator equations in Banach spaces. Under the assumption that the second derivative of the operator satisfiesγ-condition, the convergence criterion and convergence ball for Newton-Steffensen’s method are established.


---

## Body

## 1. Introduction

LetX and Y be real or complex Banach spaces, let D⊂X be an open subset, and let F:D⊂X→Ybe the Fréchet differentiable nonlinear operator. Approximating a solution of a nonlinear equation
(1)F(x)=0
is widely studied in both theoretical and applied areas of mathematics.One of the most famous methods to solve this problem is Newton’s method defined by(2)xn+1=xn-F′(xn)-1F(xn),n=0,1,2,…,
where x0∈D is an initial point. Usually, the study about convergence issue of Newton’s method includes local and semilocal convergence analyses. The local convergence issue is, based on the information around a solution, to seek estimates of the radii of convergence balls, while the semilocal one is, based on the information around an initial point, to give criteria ensuring the convergence. Among the semilocal convergence results on Newton’s method, one of the famous results is Smale’s point estimate theory which gives a convergence criterion of Newton’s method only based on the information at the initial point for analytic functions; see for example, [1–6]. To extend and improve Smale’s theory, Wang and Han proposed in [7, 8] the notion ofγ-condition, which is weaker than Smale’s assumption in [5] for analytic operators.There are several kinds of cubic generalizations for Newton’s method. The most important family is the Euler-Halley family and its variations which include Chebyshev’s method and Halley’s method as special cases; see for example, [9–16] and references therein. However, the disadvantage of this family is that the evaluation of the second derivative of the operatorFis required at every step, the operation cost of which may be very large in fact. To reduce the operation cost but also retain the cubic convergence, Sharma in [17] proposed the following Newton-Steffensen’s method which avoids the computation of the second Fréchet derivative. Letf:ℝ→ℝ. The method is defined as follows:
(3)yn=xn-f(xn)f′(xn),xn+1=xn-f(xn)g(xn),n=0,1,…,
whereg(xn)=((f(yn)-f(xn))/(yn-xn)). The author obtained cubic convergence for (3) under the assumption thatfis sufficiently smooth in the neighborhood of the solution.Motivated by the work mentioned above, we extend this method to Banach spaces and present its semilocal and local convergence. The extension is described as follows:(4)yn=xn-F′(xn)-1F(xn),xn+1=xn-[yn,xn;F]-1F(xn),n=0,1,…,
where the divided difference operator is defined by
(5)[yn,xn;F]=∫01‍F′(xn+t(yn-xn))dt.In Section2, we introduce some preliminary notions and important majorizing functions with properties. In Sections 3 and 4, we study the semilocal convergence and local convergence results of Newton-Steffensen’s method underγ-condition, respectively. We obtain the uniqueness ball and the convergence ball.


## 2. Notations and Preliminary Results

Throughout this paper, we assume thatX and Y are two Banach spaces. Let D⊂X be an open subset and let F:D⊂X→Y be a nonlinear operator with the continuous twice Fréchet derivative. Forx∈Xandr>0, we useB(x,r)andB(x,r)¯to denote the open ball with radiusrand centerxand its closure, respectively. Letx¯∈Dbe such that F′(x¯)-1exists andB(x¯,r)¯⊂D.Letγbe some positive constant and0<r⩽(1/γ). We say thatFsatisfiesγ-condition onB(x¯,r)if the following relation holds:
(6)∥F′(x¯)-1F′′(x)∥⩽2γ(1-γ∥x-x¯∥)3,x∈B(x¯,r).For simplicity, we write(7)r0=(1-12)1γ.The lemma below is useful in the next two sections.Lemma 1.
Suppose thatr⩽r0and thatFsatisfiesγ-condition (6) onB(x¯,r). Then for anyx∈B(x¯,r),F′(x)-1exists and the following inequality holds:
(8)∥F′(x)-1F′(x¯)∥⩽(1-γ∥x-x¯∥)22(1-γ∥x-x¯∥)2-1.Proof.
We can derive the following relation:(9)I-F′(x¯)-1F′(x)=-∫01‍F′(x¯)-1F′′(x¯+t(x-x¯))(x-x¯)dt.
For anyx∈B(x¯,r), it follows fromγ-condition andr⩽r0that
(10)∥I-F′(x¯)-1F′(x)∥⩽∫01‍2γ∥x-x¯∥(1-γ∥x-x¯∥t)3dt=1(1-γ∥x-x¯∥)2-1<1.
Then, by Banach lemma, one has thatF′(x)-1exists and the following inequality holds:
(11)∥F′(x)-1F′(x¯)∥⩽11-[(1/(1-γ∥x-x¯∥)2)-1]=(1-γ∥x-x¯∥)22(1-γ∥x-x¯∥)2-1.Letβ>0be some positive constant. The following majorizing functionhintroduced by Wang and Han in [18] will be used to obtain a Smale-type semilocal convergence criterion:
(12)h(t)=β-t+γt21-γt,t∈[0,1γ).Let{sn}and{tn}denote the corresponding sequences generated by Newton-Steffensen’s method for the majorizing functionhwith the initial pointt0=0; that is,
(13)sn=tn-h(tn)h′(tn),tn+1=tn-(h(sn)-h(tn)sn-tn)-1h(tn),n=0,1,….The following lemma taken from [19] describes some useful properties abouth.Lemma 2.
Suppose that(14)α≔βγ⩽3-22.
Thenhhas two zeros in[0,1/γ)denoted byt*andt**. They satisfy the following relations:
(15)β⩽t*⩽r0⩽t**⩽12γ.
Moreover,his decreasing monotonically in interval[0,r0], while it is increasing monotonically in interval[r0,1/(2γ)].The lemma below describes the convergence property of the sequences{sn}and{tn}, which is crucial for the semilocal convergence analysis of Newton-Steffensen’s method (4) underγ-condition.Lemma 3.
Suppose that (14) holds. Let{sn}and{tn}be the sequences generated by (13). Then
(16)0⩽tn<sn<tn+1<t*∀n⩾0.
Moreover,{sn}and{tn}converge increasingly to the same pointt*.Proof.
To show that (16) holds forn=0, we note that0=t0<s0=βand thatt1=(β(1-γβ)/(1-2γβ)). By (15), we have
(17)1-γβ1-2γβ>1.
This implies thatt1>β=s0. It remains to show thatt1<t*for the casen=0. To this end, we define a real function as
(18)Φ(t)=1-γt1-γt,t∈[0,+∞).
It is clear thatΦ(t)=-(h(t)-β)/tand thatΦ(t)is decreasing monotonically in[0,+∞). It follows from (15) thatΦ(β)>Φ(t*). In view of the fact thatt*is the unique zero ofhin[0,r0], we obtainβ/t*=Φ(t*)<Φ(β). This is equivalent to
(19)t*>β1-(γβ/(1-γβ))=t1.
Hence (16) holds forn=0.
Now we assume that(20)0⩽tn-1<sn-1<tn<t*forsomen⩾1.
From Lemma 2, we haveh(t)⩾0, for eacht∈[0,t*], andh(tn)/h′(tn)<0. The later one implies thatsn>tn. Define function
(21)N(t)=t-h(t)h′(t),t∈[0,t*].
Then,N′(t)=h(t)h′′(t)/h′(t)2>0, which implies thatNis increasing monotonically in[0,t*]. Hence, we have
(22)sn=tn-h(tn)h′(tn)<t*-h(t*)h′(t*)=t*.
Sincehis convex in[0,t*], we geth′(tn)<(h(sn)-h(tn))/(sn-tn)and sosn<tn+1.
Furthermore, we claim that(23)t′-(h(t)-h(t′)t-t′)-1h(t′)<t′′-(h(t′′)-h(t)t′′-t)-1h(t′′)
for allt′, t, t′′∈[0,t*]andt′<t<t′′. Indeed, it follows from the convexity ofhthat
(24)-h(t′′)h′(t)⩽-(h(t′′)-h(t)t′′-t)-1h(t′′)⩽-h(t′′)h′(t′′),-h(t′)h′(t′)⩽-(h(t)-h(t′)t-t′)-1h(t′)⩽-h(t′)h′(t),
from which we have
(25)(t′′-t′)+h(t′)-h(t′′)h′(t)⩽(t′′-t′)+(T′′-T′)⩽(t′′-t′)-h(t′′)h′(t′′)+h(t′)h′(t′),
where
(26)T′=-(h(t)-h(t′)t-t′)-1h(t′),T′′=-(h(t′′)-h(t)t′′-t)-1h(t′′).
Noting that-1<h′(t)<0for allt∈[0,t*], we obtain
(27)(t′′-t′)+h(t′)-h(t′′)h′(t)>(t′′-t′)+[h(t′′)-h(t′)]⩾0.
Then (23) follows. By (23), we conclude that
(28)tn+1=tn-(h(sn)-h(tn)sn-tn)-1h(tn)<t*-(h(t*)-h(sn)t*-sn)-1h(t*)=t*.
Therefore, (16) holds for alln⩾0. The inequlities in (16) imply that{sn}and{tn}converge increasingly to some same points, sayτ. Clearlyτ∈[0,t*]andτis a zero ofhin[0,t*]. Noting thatt*is the unique zero ofhin[0,r0], one has thatτ=t*. The proof is complete.


## 3. Convergence Criterion

Throughout this subsection, letx0∈Dbe the initial point such that the inverseF′(x0)-1exists and letB(x0,r0)⊂D, wherer0is defined by (7). Moreover, we assume thatFsatisfiesγ-condition onB(x0,r0); that is, the following relation holds:(29)
∥
F
′
(
x
0
)
-
1
F
′′
(
x
)
∥
⩽
2
γ
(
1
-
γ
∥
x
-
x
0
∥
)
3
,
x
∈
B
(
x
0
,
r
0
)
.
Then, for anyx∈B(x0,r0), it follows from Lemma 1 thatF′(x)-1exists and the following inequality holds:
(30)∥F′(x)-1F′(x0)∥⩽(1-γ∥x-x0∥)22(1-γ∥x-x0∥)2-1.Below we list two useful lemmas.Recall that the divided difference operator[y,x;F]is defined by (5). The following lemma gives the expressions of some desired estimates in the proof of Lemma 5.Lemma 4.
Letx∈B(x0,r0). Define
(31)y≔x-F′(x)-1F(x),x¯≔x-[y,x;F]-1F(x).
Then the following formulas hold: (i)
[y,x;F]-F′(x0)=∫01‍∫01‍F′′(x0+s[(x-x0)+t(y-x)])[(x-x0)+t(y-x)]dsdt.(ii)
x¯-y=-F′(x)-1∫01‍∫01‍F′′(x+st(y-x))(y-x)(x¯-x)tdsdt.(iii)
F(x¯)=∫01‍∫01‍F′′(x+t(y-x)+st(x¯-y))(x¯-x)(x¯-y)tdsdt.Proof.
For (i), we notice that(32)[y,x;F]-F′(x0)=∫01‍[F′(x+t(y-x))-F′(x0)]dt=∫01‍∫01‍F′′(x0+s[(x-x0)+t(y-x)])×[(x-x0)+t(y-x)]dsdt.
As for (ii), one has
(33)x¯-y=F′(x)-1F(x)-[y,x;F]-1F(x)=F′(x)-1[F′(x)-∫01‍F′(x+t(y-x))dt]×(x¯-x)=-F′(x)-1×∫01‍∫01‍F′′(x+st(y-x))(y-x)(x¯-x)tdsdt.
Similarly, we obtain
(34)F(x¯)=F(x¯)-F(x)-[y,x;F](x¯-x)=∫01‍F′(x+t(x¯-x))(x¯-x)dt-∫01‍F′(x+t(y-x))(x¯-x)dt=∫01‍∫01‍F′′(x+t(y-x)+st(x¯-y))×(x¯-x)(x¯-y)tdsdt.
The proof is complete.Lemma 5.
Suppose that (14) holds. Then the sequence{xn}generated by (4) with the initial pointx0is well defined and the following estimates hold for any natural numbern⩾1: (i)
∥yn-1-xn-1∥⩽sn-1-tn-1,∥xn-xn-1∥⩽tn-tn-1,∥xn-yn-1∥⩽tn-sn-1.(ii)
∥[yn-1,xn-1;F]-1F′(x0)∥⩽-((sn-1-tn-1)/(h(sn-1)-h(tn-1))).(iii)
∥F′(x0)-1F(xn)∥⩽h(tn)(∥xn-xn-1∥/(tn-tn-1))2(∥yn-1-xn-1∥/(sn-1-tn-1)).Proof.
For the casen=1in (i), it is clear that∥y0-x0∥⩽β=s0-t0. By Lemma 4 and (29), we have
(35)∥F′(x0)-1([y0,x0;F]-F′(x0))∥=∥∫01‍F′(x0)-1×∫01‍∫01‍F′′(x0+st(y0-x0))(y0-x0)tdsdt∥⩽∫01‍∫01‍2γ(s0-t0)t[1-γ(s0-t0)st]3dsdt=h(s0)-h(t0)s0-t0+1.
In view of the monotonicity ofh, one has that(h(s0)-h(t0))/(s0-t0)<0. Hence, we get from Banach lemma that[y0,x0;F]-1exists and satisfies
(36)∥[y0,x0;F]-1F′(x0)∥⩽11-(((h(s0)-h(t0))/(s0-t0))+1)=-s0-t0h(s0)-h(t0).
Combining (36) inequality with the definitions of{sn}and{tn}given in (13), one has
(37)∥x1-x0∥⩽∥[y0,x0;F]-1F′(x0)∥∥F′(x0)-1F(x0)∥⩽-s0-t0h(s0)-h(t0)h(t0)=t1-t0.
As for the estimate∥x1-y0∥, by Lemma 4, we have
(38)x1-y0=-F′(x0)-1×∫01‍∫01‍F′′(x0+st(y0-x0))×(y0-x0)(x1-x0)tdsdt.
This together with the obtained bounds∥y0-x0∥,∥x1-x0∥and (29) yields that
(39)∥x1-y0∥⩽∫01‍∫01‍2γ(s0-t0)(t1-t0)(1-γ(s0-t0)st)3tdsdt×(∥y0-x0∥s0-t0)(∥x1-x0∥t1-t0)=(t1-s0)(∥y0-x0∥s0-t0)(∥x1-x0∥t1-t0).
This implies that statement (i) holds forn=1.
Statement (ii) for the casen=1is justified by (36). Below, we consider the casen=1for (iii). First we have the following expression ofF(x1)due to Lemma 4:
(40)F(x1)=∫01‍∫01‍F′′(x0+t(y0-x0)+st(x1-y0))×(x1-x0)(x1-y0)tdsdt,
from which we obtain that
(41)∥F′(x0)-1F(x1)∥⩽∫01‍∫01‍2γ(t1-t0)(t1-s0)t[1-γ(t(s0-t0)+st(t1-s0))]3dsdt×(∥x1-x0∥t1-t0)2(∥y0-x0∥s0-t0)=h(t1)(∥x1-x0∥t1-t0)2(∥y0-x0∥s0-t0).
Therefore statement (iii) holds forn=1.
Assume that statements (i)–(iii) are true forn=k(⩾1). Below, we will show that they also hold forn=k+1. First, by statement (i), we have
(42)∥xk-x0∥⩽∑i=0k-1‍∥xi+1-xi∥⩽∑i=0k-1‍(ti+1-ti)=tk<t*<r0.
Hence,F′(xk)-1exists by Lemma 1.
Note that(43)∥F′(x0)-1F(xk)∥⩽h(tk)
by the inductive hypotheses of (i) and (iii). Then it follows from (30) and (13) that
(44)∥yk-xk∥⩽∥F′(xk)-1F′(x0)∥∥F′(x0)-1F(xk)∥⩽-h(tk)h′(tk)=sk-tk.
Hence by (29), (44), Lemma 4, and the inductive hypothesis of (i), we have
(45)∥F′(x0)-1([yk,xk;F]-F′(x0))∥=∥F′(x0)-1∫01‍∫01‍F′′(x0+s[(xk-x0)+t(yk-xk)])×[(xk-x0)+t(yk-xk)]dsdt∫01‍∥⩽∫01‍∫01‍2γ[1-γs(tk+t(sk-tk))]3×[tk+t(sk-tk)]dsdt=∫01‍(1[1-γ(tk+t(sk-tk))]2-1)dt=h(sk)-h(tk)sk-tk+1<1.
It follows from Banach lemma that[yk,xk;F]-1F′(x0)exists and satisfies
(46)
∥
[
y
k
,
x
k
;
F
]
-
1
F
′
(
x
0
)
∥
⩽
1
1
-
(
(
(
h
(
s
k
)
-
h
(
t
k
)
)
/
(
s
k
-
t
k
)
)
+
1
)
=
-
s
k
-
t
k
h
(
s
k
)
-
h
(
t
k
)
.
Hence, (ii) holds forn=k+1.
Combining (46) with the inductive hypothesis (iii), one has
(47)∥xk+1-xk∥⩽∥[yk,xk;F]-1F′(x0)∥∥F′(x0)-1F(xk)∥⩽-(h(sk)-h(tk)sk-tk)-1h(tk)×(∥xk-xk-1∥tk-tk-1)2(∥yk-1-xk-1∥sk-1-tk-1)=(tk+1-tk)×(∥xk-xk-1∥tk-tk-1)2(∥yk-1-xk-1∥sk-1-tk-1),
which implies that∥xk+1-xk∥⩽tk+1-tk.
On the other hand, by (29), (30), (44), and Lemma 4, we conclude that
(48)∥xk+1-yk∥⩽∫01‍∫01‍∥F′(xk)-1F′′(xk+st(yk-xk))∥×∥yk-xk∥∥xk+1-xk∥tdsdt⩽∥F′(xk)-1F′(x0)∥×∫01‍∫01‍2γ∥yk-xk∥∥xk+1-xk∥t[1-γ(∥xk-x0∥+st∥yk-xk∥)]3dsdt⩽(1-γtk)22(1-γtk)2-1×∫01‍∫01‍2γ(sk-tk)(tk+1-tk)t[1-γ(tk+st(sk-tk))]3dsdt×(∥yk-xk∥∥xk+1-xk∥(sk-tk)(tk+1-tk))=-1h′(tk)(tk+1-tk)(h(sk)-h(tk)sk-tk-h′(tk))×(∥yk-xk∥∥xk+1-xk∥(sk-tk)(tk+1-tk))=(tk+1-sk)(∥yk-xk∥∥xk+1-xk∥(sk-tk)(tk+1-tk)),
which leads to∥xk+1-yk∥⩽tk+1-sk. Thus, (i) holds forn=k+1.
Next, we will show that (iii) also holds forn=k+1. In fact, by using Lemma 4, (29), (44), and (48), we obtain
(49)∥F′(x0)-1F(xk+1)∥⩽∫01‍∫01‍2γ(tk+1-tk)(tk+1-sk)[1-γ(tk+t(sk-tk)+st(tk+1-sk))]3tdsdt·(∥xk+1-xk∥tk+1-tk)2(∥yk-xk∥sk-tk)=(h(tk+1)-h(tk)-tk+1-tksk-tk(h(sk)-h(tk)))·(∥xk+1-xk∥tk+1-tk)2(∥yk-xk∥sk-tk)⩽h(tk+1)(∥xk+1-xk∥tk+1-tk)2(∥yk-xk∥sk-tk).
Therefore statement (iii) holds forn=k+1. Hence (i)–(iii) hold for alln⩾0. Furthermore, by statement (i), one has, for anyn⩾0,∥xn-x0∥⩽tn<t*<r0. Thus by Lemma 1 we know thatF′(xn)-1exists for eachn⩾1;thatis,{xn}is well defined. The proof is complete.Recall that{sn}and{tn}are defined in (13). Based on the preceding useful lemmas, we are now ready to prove a Smale-type semilocal convergence theorem for Newton-Steffensen’s method (4) underγ-condition.Theorem 6.
Suppose that (14) holds. Then the sequence{xn}generated by (4) with the initial pointx0is well defined and converges to a solutionx*∈B(x0,t*¯)of (1) with Q-cubic rate, and this solutionx*is unique inB(x0,r)¯, wheret*⩽r<t**. Moreover, the following error bounds
(50)∥x*-xn∥⩽(t*-tn)(∥x*-xm∥t*-tm)3n-m∀n⩾m⩾0
are valid, wheret*andt**are defined in Lemma 2.Proof.
The uniqueness ball can be obtained by Theorem  5.2 in [19]. It follows from Lemma 1 that{xn}is well defined. In addition, from Lemmas 3 and 5 (i), we can see that{xn}is convergent to a limit, sayx*. Below, we show thatx*is a solution of (1). It follows from Lemma 5 (iii) that
(51)∥F′(x0)-1F(xn)∥⩽h(tn)∀n⩾0.
Lettingn→∞in the preceding relation gives that the limitx*is a solution of (1). Moreover, we have
(52)∥x*-xn∥⩽t*-tn.
Next, we verify that estimate (62) is true. By (29) and Lemma 5, one has
(53)∥x*-yn∥=∥∫01‍F′(xn)-1×[∫01‍F′(xn)(x*-xn)dt+F(xn)-F(x*)]∥=∥∫01‍F′(xn)-1×∫01‍∫01‍F′′(xn+st(x*-xn))(x*-xn)2tdsdt∥⩽∥F′(xn)-1F′(x0)∥×∥∫01‍∫01‍F′(x0)-1F′′(xn+st(x*-xn))×(x*-xn)2tdsdt∫01‍∥⩽(1-γ∥xn-x0∥)22(1-γ∥xn-x0∥)2-1×∫01‍∫01‍2γ(t*-tn)2t[1-γ(∥xn-x0+st(x*-xn)∥)]3dsdt⩽(t*-sn)(∥x*-xn∥t*-tn)2.
In order to estimate∥xn+1-x*∥, we first notice that
(54)
[
y
n
,
x
n
;
F
]
(
x
n
+
1
-
x
*
)
=
∫
0
1
‍
∫
0
1
‍
F
′′
(
x
n
+
z
n
s
,
t
)
(
x
*
-
y
n
)
(
x
*
-
x
n
)
t
d
s
d
t
,
wherezns,t=t(yn-xn)+st(x*-yn). This together with Lemma 5(i), (29), (52), and (53) gives that
(55)∥F′(x0)-1[yn,xn;F](xn+1-x*)∥⩽∫01‍∫01‍2γ∥x*-yn∥∥x*-xn∥t[1-γ(∥xn-x0∥+t∥yn-xn∥+st(x*-yn))]3dsdt⩽∫01‍∫01‍2γ(t*-sn)(t*-tn)t[1-γ(tn+t(sn-tn)+st(t*-sn))]3dsdt×(∥x*-xn∥t*-tn)3=(-h(tn)-h(sn)-h(tn)sn-tn(t*-tn))(∥x*-xn∥t*-tn)3=(tn+1-t*)(h(sn)-h(tn)sn-tn)(∥x*-xn∥t*-tn)3.
Combining the above inequality with (46), we have
(56)∥xn+1-x*∥⩽∥[yn,xn;F]-1F′(x0)∥×∥F′(x0)-1[yn,xn;F](xn+1-x*)∥⩽-(h(sn)-h(tn)sn-tn)-1(tn+1-t*)×(h(sn)-h(tn)sn-tn)(∥x*-xn∥t*-tn)3⩽(t*-tn+1)(∥x*-xn∥t*-tn)3.
Therefore, the error estimate (62) follows. Also, from the previous inequality, we know that the convergence rate of{xn}tox*is Q-cubic. This completes the proof.One typical and important class of examples satisfyingγ-condition is the one of analytic functions. Smale [5] studied the convergence and error estimation of Newton’s method (2) under the hypotheses thatFis analytic and satisfies
(57)∥F′(x¯)-1F(n)(x¯)∥⩽n!γn-1,n⩾2,
wherex¯is a fixed point inDandγis defined by
(58)γ≔supn>1∥F′(x¯)-1F(n)(x¯)n!∥1/(n-1).The following lemma taken from [20] shows that an analytic operator satisfiesγ-condition.Lemma 7.
Letr0andγbe defined by (7) and (86), respectively. Suppose thatFis analytic and satisfies (85). ThenFsatisfiesγ-condition
(59)∥F′(x¯)-1F′′(x)∥⩽2γ(1-γ∥x-x¯∥)3
onB(x¯,r0).According to this lemma, we can conclude that the semilocal results obtained in Theorem6 also hold whenFis an analytic operator.Corollary 8.
Suppose that (14) holds. Suppose thatFis analytic and satisfies
(60)∥F′(x0)-1F(n)(x0)∥⩽n!γn-1,n⩾2,
where γ is defined by
(61)γ:=supn>1∥F′(x0)-1F(n)(x0)n!∥1/(n-1).
Then the sequence{xn}generated by (4) with the initial pointx0is well defined and converges to a solutionx*∈B(x0,t*¯)of (1) with Q-cubic rate and this solutionx*is unique inB(x0,r)¯, wheret*⩽r<t**. Moreover, the following error bounds
(62)∥x*-xn∥⩽(t*-tn)(∥x*-xm∥t*-tm)3n-m∀n⩾m⩾0
are valid, wheret*andt**are defined in Lemma 2.


## 4. Convergence Ball

Now we begin to study the local convergence properties for Newton-Steffensen’s method (4) underγ-condition. Recall thatr0is defined by (7). Throughout this section, suppose thatx*∈Dsuch thatF(x*)=0,B(x*,r0)⊂D, and the inverseF′(x*)-1exists. Moreover, we assume thatFsatisfies theγ-condition onB(x*,r0); that is, the following relation holds:
(63)∥F′(x*)-1F′′(x)∥⩽2γ(1-γ∥x-x*∥)3,x∈B(x*,r0).
Then, for anyx∈B(x*,r0), it follows from Lemma 1 that
(64)∥F′(x)-1F′(x*)∥⩽(1-γ∥x-x*∥)22(1-γ∥x-x*∥)2-1.Let(65)r1≔(5-17)(4γ).
Define functionGas follows:
(66)G(t)=γt1-4γt+2γ2t2,t∈(0,r1).
It is clear thatr1∈(0,r0)and thatG(r1)=1. Moreover,Gincreases monotonically in(0,r1).Theorem 9.
Letr1be defined in (65). Then, for anyx0∈B(x*,r1), the sequence{xn}generated by (4) converges tox*and satisfies that
(67)∥xn-x*∥⩽q3n-1∥x0-x*∥,n=0,1,…,
where
(68)q=G(t0)<1,t0=∥x0-x*∥.Proof.
Forn=0,1,…, we writetn=∥xn-x*∥. It is sufficient to show that
(69)tn+1⩽tn,∥xn+1-x*∥⩽(G(tn)tn)2∥xn-x*∥3,n=0,1,….
In fact, by noticing the monotonicity ofG/t, we have
(70)
∥
x
n
+
1
-
x
*
∥
⩽
(
G
(
t
n
)
t
n
)
2
∥
x
n
-
x
*
∥
3
⩽
(
G
(
t
0
)
t
0
)
2
∥
x
n
-
x
*
∥
3
=
(
q
t
0
)
2
∥
x
n
-
x
*
∥
3
,
n
=
0,1
,
…
.
From this we can easily establish (67) by mathematical induction.
We now prove (69). First we get the following expression ofxn+1-x*:
(71)xn+1-x*=[yn,xn;F]-1×[∫01‍F′(xn+t(yn-xn))(xn-x*)dt-(F(xn)-F(x*))∫01‍]=[yn,xn;F]-1×∫01‍∫01‍F′′(x*+(1-t)(xn-x*)+st(yn-x*))×(yn-x*)(xn-x*)tdsdt.
Similarly, we also have
(72)yn-x*=xn-F′(xn)-1F′(xn)-x*=F′(xn)-1×[F(x*)-F(xn)+F′(xn)(xn-x*)]=F′(xn)-1×∫01‍[F′(xn+t(x*-xn))-F′(xn)]×(x*-xn)dt=F′(xn)-1×∫01‍∫01‍F′′(xn+st(x*-xn))(x*-xn)2tdsdt.
This together with (63) and (64) yields
(73)∥yn-x*∥⩽∥F′(xn)-1F′(x*)∥×∥∫01‍∫01‍F′(x*)-1F′′(xn+st(x*-xn))tdsdt∥×∥x*-xn∥2⩽(1(1-γ∥x*-xn∥)2-2)×∫01‍∫01‍2γ[1-γ∥xn+st(x*-xn)-x*∥]3dsdt×∥x*-xn∥2=(1(1-γtn)2-2)×∫01‍∫01‍2γ[1-γ(1-st)tn]3dsdt×∥x*-xn∥2=γ1-4γtn+2γ2tn2∥x*-xn∥2=(G(tn)tn)∥x*-xn∥2.
On the other hand, we notice that(74)F′(x*)-1([yn,xn;F]-F′(x*))=F′(x*)-1×∫01‍∫01‍F′′(x*+s(1-t)(xn-x*)+st(yn-x*))×[(1-t)(xn-x*)+t(yn-x*)]dsdt.
It follows from (63) that
(75)∥F′(x*)-1([yn,xn;F]-F′(x*))∥⩽∫01‍∫01‍2γ[(1-t)∥xn-x*∥+t∥yn-x*∥][1-γ(s(1-t)∥xn-x*∥+st∥yn-x*∥)]3dsdt.
For the casen=0, by (88) and (73), we get
(76)∥y0-x*∥⩽G(t0)∥x*-x0∥⩽∥x*-x0∥.
Combining Lemma 2 with (75) and (76), we obtain
(77)∥F′(x*)-1([y0,x0;F]-F′(x*))∥⩽∫01‍∫01‍2γ[(1-t)∥x0-x*∥+t∥y0-x*∥][1-γ(s(1-t)∥x0-x*∥+st∥y0-x*∥)]3dsdt⩽∫01‍∫01‍2γ[(1-t)t0+tt0][1-γ(s(1-t)t0+stt0)]3dsdt=1(1-γt0)2-1<1.
It follows from Banach lemma that
(78)∥[y0,x0;F]-1F′(x*)∥⩽11-((1/(1-γt0)2)-1)=(1-γt0)22(1-γt0)2-1.
This together with (63), (71) and (76) yields
(79)∥x1-x*∥⩽∥[y0,x0;F]-1F′(x*)∥×∥F′(x*)-1×∫01‍∫01‍F′′(x*+(1-t)(x0-x*)+st(y0-x*))tdsdt(x*)-1∥×∥y0-x*∥∥x0-x*∥⩽(1-γt0)22(1-γt0)2-1×∫01‍∫01‍2γ[1-γ((1-t)t0+stt0)]3tdsdt×G(t0)∥x*-x0∥3=(1-γt0)22(1-γt0)2-11t0(1(1-γt0)2-1(1-γt0))×G(t0)∥x*-x0∥3=(G(t0)t0)2∥x*-x0∥3.
Hence (69) holds forn=0.
Now assume that the inequalities in (69) hold for up to somen⩾1. Then by (73), one has
(80)∥yn+1-x*∥=G(tn+1)tn+1⩽G(t0)tn+1⩽tn+1.
Thus (75) can be further reduced to
(81)∥F′(x*)-1([yn+1,xn+1;F]-F′(x*))∥⩽∫01‍∫01‍2γ[(1-t)tn+1+ttn+1][1-γ(s(1-t)tn+1+sttn+1)]3dsdt=1(1-γtn+1)2-1<1.
Using Banach lemma again, one has
(82)∥[yn+1,xn+1;F]-1F′(x*)∥⩽(1-γtn+1)22(1-γtn+1)2-1.
This together with (63), (71), and (73) yields
(83)∥xn+2-x*∥⩽∥[yn+1,xn+1;F]-1F′(x*)∥×∥F′(x*)-1·∫01‍∫01‍F′′(x*+(1-t)(xn+1-x*)+st(yn+1-x*))tdsdt(x*)-1∥×∥yn+1-x*∥∥xn+1-x*∥⩽(1-γtn+1)22(1-γtn+1)2-1×∫01‍∫01‍2γ[1-γ((1-t)tn+1+sttn+1)]3tdsdt×G(tn+1)∥x*-x0∥3=(1-γtn+1)22(1-γtn+1)2-1×1tn+1(1(1-γtn+1)2-1(1-γtn+1))×G(tn+1)∥x*-x0∥3=(G(tn+1)tn+1)2∥x*-xn+1∥3.
Thus
(84)tn+2≤G(tn+1)2tn+1≤G(t0)2tn+1≤tn+1.
This and (83) show that the inequalities in (69) hold forn+1and hence they hold for eachn. The proof is complete.Applying Lemma7 to the above theorem, we get the following corollary:Corollary 10.
Suppose thatFis analytic and satisfies
(85)∥F′(x*)-1F(n)(x*)∥⩽n!γn-1,n⩾2,
where γ is defined by
(86)γ≔supn>1∥F′(x*)-1F(n)(x*)n!∥1/(n-1).
Letr1andGbe defined by (65) and (66), respectively. Then, for anyx0∈B(x*,r1), the sequence{xn}generated by (4) converges tox*and satisfies that
(87)∥xn-x*∥⩽q3n-1∥x0-x*∥,n=0,1,…,
where
(88)q=G(t0)<1,t0=∥x0-x*∥.



---

*Source: 682167-2013-11-07.xml*