# Convergence and Error Estimate of the Steffensen Method

Authors: Xufeng Shang; Xingping Shao; Peng Wu
Journal: SRX Mathematics
 (2010)

---

## Abstract

We present the Steffensen method inRn space. The convergence theorem is established by using the technique of majorizing function. Meanwhile, an error estimate is given. It avoids the calculus of derivative but has the same convergence order 2 with Newton's method. Finally, illustrative examples are included to demonstrate the validity and applicability of the technique.


---

## Body

## 1. Introduction

LetX and  Y be real or complex Banach space, and let F:D⊂X→Y be a nonlinear Fréchet differentiable operator in some convex domain  D. The well-known iteration for solving the equation
(1)F(x)=0
is Newton's method defined as follows:
(2)xk+1=xk-F′(xk)-1F(xk),k=0,1,2,….In recent years, some authors [1–5] discuss Newton's method and some modifications and give the convergence theorem and the error estimate. In order to avoid the calculus of derivative of f(x) and avoid f′(x)=0, many authors investigate the Steffensen method:
(3)xk+1=xk-f2(xk)f(xk+f(xk))-f(xk),which is given for solving algebraic equation (only in one dimension) [6]. For example, H. t. Kung and Traub presented a class of multipoint iterative functions without derivative. Chen [7] studied a particular class of these methods which contain Steffensen method in special case, and X. Wu and H. Wu [8] studied a class of quadratic convergence iteration formulae without derivatives. Zheng et al. [9] gave a second-order parametric Steffensen-like method, which is derivative free and only uses two evaluations of the function in one step; they also suggested a variant of the Steffensen-like method which is still derivative free and uses four evaluations of the function to achieve cubic convergence. Ren et al. [10] derived a one-parameter class of fourth-order methods for solving nonlinear equations. But above all methods are given only for solving algebraic equation.Newton's method can be extended to high dimension directly, nevertheless the Steffensen method cannot. So the Steffensen method in high dimension is seldom researched. In [6], there are several kinds of forms of Steffenen method in high dimension mentioned. Resently, Amat et al. [11] generalize one form of the Steffensen method and give its convergence theorem and error estimate. Hilout [12] studies the convergence of Steffensen-type algorithms. A class of Steffensen-type algorithms for solving generalized equations on Banach spaces is proposed. Alarcon et al. [13] discussed a modified Steffensens type iterative scheme for the numerical solution of a system of nonlinear equations.In this paper, we discuss another form of the Steffensen method inRn space. The form is defined as follows:
(4)xk+1=xk-J(xk,Hk)-1F(xk),k=0,1,2,…,
where J(xk,Hk)=(F(xk+Hke1)-F(xk),…,F(xk+Hken)-F(xk))Hk-1,  k=1,2,…,  Hk= diag(f1(xk),f2(xk),…,fn(xk)), and F(x)=(f1(x),f2(x),…,fn(xk))T, where fi:Rn→R and x=(x1,x2,…,xn) is a vector.Compared with Newton's iteration, the advantage of this form avoids evaluation of the derivative but has the same convergence order. In the paper, we also establish the convergence theorem under Kantorovich condition and give the error estimate.This paper is organized as follows. In Section2, the majorizing sequence and its properties are presented. In Section 3, we establish Kantorovich-type theorem for this kind of method by using majorizing function. Moreover, an error estimate is given. In Section 4, the proof of the main theorem is presented. Finally, a numerical comparison with Newton's method is presented.


## 2. Majorizing Sequence and Its Properties

LetK, β, and η be nonnegative numbers, and let h be a majorant function defined by
(5)h(t)=12Kt2-1βt+ηβ.Applying the iteration (2) to  h, we can get the real sequences {tk}:
(6)tk+1=tk-h(tk)h′(tk),k=0,1,…,t0=0.
First, we have the following lemmas.Lemma 1.
Whenα=Kβη≤1/2, the real function h has two positive roots
(7)t*=1-1-2ααη,t**=1+1-2ααη.Lemma 2.
Under the assumptions of previous Lemma, the real sequence{tn} is monotonically increasing and tending to the root t* of h.Lemma 3.
Suppose that the sequencetk is produced by the iteration (6). If α=Kβη≤1/2, then
(8)t*-tk≤θ2k1-θ2k(t**-t*),
where
(9)θ=1-1-2α1+1-2α.Proof.
Letak=t*-tk, bk=t**-tk. Then
(10)h(tk)=K2akbk,h′(tk)=-K2(ak+bk).
Thus, we have
(11)ak+1=ak-akbkak+bk=ak2ak+bk,bk+1=bk-akbkak+bk=bk2ak+bk.
By (11), we get
(12)akbk=(ak-1bk-1)2=⋯=(a0b0)2k=(t*t**)2k=(θ)2k.
Since bk=t**-t*+ak, it is easy to solve ak from (12). The lemma follows.


## 3. Main Result

LetF:D⊂Rn→Rn be a nonlinear Frechet differentiable operator in some convex domain  D and satisfy
(13)∥F′(x)-F′(y)∥≤M∥x-y∥,∀x∈D.
For the iteration form (4), we have the following lemma and theorem.Lemma 4.
LetF:Rn→Rn, and F satisfies the iteration (4), then one has
(14)∥J(xk,Hk)-F′(xk)∥≤M2∥F(xk)∥,∀xk∈D0.Proof.
LetF(x)=(f1(x),…,fn(x))T and H=diag(f1(x),…,fn(x)). Then
(15)J(xk,Hk)=(F(xk+Hke1)-F(xk),…,F(xk+Hken)-F(xk))Hk-1=(∫01F′(xk+tHke1)dtHke1,…,∫01F′(xk+tHken)dtHken)Hk-1=(∫01F′(xk+tHke1)e1dt,…,∫01F′(xk+tHken)endt)HkHk-1=(∫01F′(xk+tHke1)e1dt,…,∫01F′(xk+tHken)endt),
so
(16)∥J(xk,Hk)-F′(xk)∥=∥(∫01F′(xk+tHke1)e1dt,…,∫01F′(xk+tHken)endt)-∫01F′(xk)dt∥=∥(∫01F′(xk+tHke1)e1dt,…,∫01F′(xk+tHken)endt)-(∫01F′(xk)e1dt,…,∫01F′(xk)endt)∥≤(∫01tM∥Hke1∥dt,∫01tM∥Hke2∥dt,…,∫01tM∥Hken∥dt)≤M2∥F(xk)∥.Thisendstheproof.For an initial valuex0∈D, suppose that F′(x0)-1 exists and F satisfies
(17)∥F′(x0)-1∥≤β,∥F′(x0)-1F(x0)∥≤η,
where β and  γ are positive constants. Then we have the following theorem.Theorem 1.
IfF satisfies the conditions (13), (14), and (17), and α=Kηβ≤1/2, K≥M+M/β, then the sequence xk produced by the iteration (4) with the initial value x0  is well defined and converges the unique root x*∈S(x0,t*) of F. Moreover
(18)∥xk-x*∥≤t*-tk≤θ2k1-θ2k(t**-t*),k=0,1,…,
where S(x0,r)={x∣∥x-x0∥≤r}, θ=(1-1-2α)/(1+1-2α).


## 4. Proof of the Main Theorem

LetF satisfy the conditions (13), (14), and (17). To prove Theorem 1, we need to prove some useful Lemmas.Lemma 5.
If the sequencexk  produced by the iteration  (4), then
(19)F(xk+1)=(F′(xk)-J(xk,Hk))(xk+1-xk)+∫01(F′(xk+t(xk+1-xk))-F′(xk))dt(xk+1-xk).Proof.
By (4) and Talyor expansion, the lemma can be verified directly.Lemma 6.
Ifα≤1/2 and  K≥M+M/β, then(a)
xk∈S(x0,t*),(b)
∥xk+1-xk∥≤tk+1-tk,(c)
∥F(xk)∥≤h(tk),(d)
J(xk,Hk)-1  exists, and ∥J(xk,Hk)-1∥≤-1/h′(tk),where the sequence {tk} is produced by the iteration (6).Proof.
The conclusions  (a), (b), and  (c) are obviously true fork=0. Now assume that they remain valid while k≤n. At first, by  (b), we can see
(20)∥xn+1-x0∥≤∑j=0n∥(xj+1-xj)∥≤∑j=0n(tj+1-tj)=tn+1≤t*.
Thus, xn+1∈S(x0,t*).
By Lemma5 and inductive assumptions, we have
(21)∥F(xn+1)∥=∥∫01-J(xn,Hn)(xn+1-xn)+F′(xn)(xn+1-xn)+∫01(F′(xn+t(xn+1-xn))-F′(xn))dt(xn+1-xn)∥≤(M2)∥F(xn)∥∥xn+1-xn∥+(M2)∥xn+1-xn∥2≤M2h(tn)(tn+1-tn)+M2(tn+1-tn)2=-M2h′(tn)(tn+1-tn)2+M2(tn+1-tn)2≤-M2h′(t0)(tn+1-tn)2+M2(tn+1-tn)2=(M2β+M2)(tn+1-tn)2≤K2(tn+1-tn)2=h(tn+1).
So  (c) is valid for k=n+1.
Since∥F′(x0)-1∥≤β and ∥x-x0∥<1/(Kβ), by Lemma 4 and iteration (6), we have
(22)∥J(xk,Hk)-F′(x0)∥≤∥J(xk,Hk)-F′(xk)∥+∥F′(xk)-F′(x0)∥≤(M2)∥F(xk)∥+M∥xk-x0∥≤(M2)h(tk)+M∥xk-x0∥≤(M2)h(tk-1)+Mtk≤-(M2)h′(tk-1)(tk-tk-1)+Mtk≤-(M2)h′(t0)tk+Mtk≤(M(2β)+M)tk≤Ktk=h′(tk)+1β<1β.
Hence, by Banach lemma, J(xk,Hk)-1 exists and
(23)∥J(xk,Hk)-1∥≤∥f′(x0)-1∥1-∥f′(x0)-1∥(h′(tk)+1/β)≤-1h′(tk).
Therefore
(24)∥xn+2-xn+1∥≤-h(tn+1)h′(tn+1)=tn+2-tn+1.
So  (b) is also valid for k=n+1.Proof of Theorem1.
By  (b) in Lemma6, we have that {xn} is a Cauchy sequence. Let x* be the limit of xn, as n→∞, we have
(25)∥x*-xn∥≤t*-tn.
It yields F(x*)=0. This completes the proof of Theorem 1.


## 5. Numerical Examples

We establish a theorem of convergence for the iteration (4). The best property of this method is that it does not use any derivative but has the same good properties of convergence with Newton's method. The following example can give the enough explanation. The computations associated with the examples were performed using Maple 9.Example 1.
We consider the following equation in 2D:(26)f1=x1-0.7sin(x1)-0.2cos(x2)=0,f2=x2-0.7cos(x1)+0.2sin(x2)=0.
The initial vector is(1/2,1/2)T. We solve the above equations by Newton's method and the Steffensen method, respectively. The numerical comparison of the methods is displayed in Table 1. From Table 1, we can find the Steffensen method has the same convergence rate with Newton's method.Table 1
The numerical comparison between Newton's method and Steffensen method.
StepSteffensen methodNewton's method∥F(x*)∥∥F(x*)∥13.3324e-033.3324e-0356.6813e-056.6737e-05106.8111e-076.7586e-07Example 2.
We consider the following nonlinear boundary value problem of second order  [14]:
(27)d2x(t)dt2=ex(t),x(0)=0=x(1).
To solve this problem by finite differences, we start by drawing the usual grid line withtj=jh, where h=1/n and n is an integer. Note that x0 and xn are given by the boundary conditions, then x0=0=xn. We first approximate the second derivative at these points:
(28)x′′≈xj-1-2xj+xj+1h2,j=1,2,3,…,n-1.
By substituting this expression into the differential equation, we have the following system of nonlinear equations:
(29)xj-1-2xj+xj+1-h2exj=0,j=1,2,3,…,n-1.
We therefore have an operator F:Rn-1→Rn-1 such that F(x)=H(x)-h2g(x),  where
(30)H=(-210⋯01-21⋯001-2⋯0⋮⋮⋮⋱⋮000⋯-2),x=(x1x2⋮xn-1),g(x)=(ex1ex2⋮exn-1).
Now we apply the Steffensen method and Newton's method to approximate the solution of F(x)=0. We choose n=12, then (29) gives eleven equations. For the initial iterate values chosen as xj(0)=tj(tj-1), j=1,2,…,11, after two iterates, the Steffensen method is better than Newton's method (see Table 2).Table 2
The numerical comparison between Newton's method and Steffensen method of∥F(x(n))∥.
nSteffensen methodNewton's method11.4449e-0091.9878e-00921.9665e-0174.5194e-017Example 3.
We consider the following nonlinear boundary value problem of Burgers-Huxley equation:(31)ut+uux-uxx=u(1-u)(u-0.4),u(0,t)=0.2-0.2tanh(0.12t),(x∈(0,1),t∈(0,1])u(1,t)=0.2-0.2tanh(0.2+0.12t),u(x,0)=0.2-0.2tanh(0.2x).
This equation's exact solution is(32)u(x,t)=0.2(1-tanh(0.2x+0.12t)).
By finite differences replacing the derivative, we get the following system of nonlinear equations:
(33)(I+0.01An(Un))Un=Un-1+0.01F(Un),u0,n=0.2-0.2tanh(0.0012n),u100,n=0.2-0.2tanh(0.2+0.0012t),ui,0=0.2-0.2tanh(0.002i),1≤i≤99,
where I is identity matrix, Un=(u1,n,u2,n,…,u98,n,u99,n)T, tanh(x)=(ex-e-x)/(ex+e-x),   An(Un)=tridiag[-(10000+50(ui,n+|ui,n|)),2(10000+50|ui,n|),-(10000-50(ui,n-|ui,n|))]. Also we have
(34)F(Un)=[f(u1,n)+(10000+50(u1,n+|u1,n|))u0,n,f(u2,n),…,f(u98,n),f(u99,n)+(10000-50(u99,n-|u99,n|))u100,n],
where f(ui,n)=ui,n(1-ui,n)(ui,n-0.4), i=1,2,…,100.
We solve system (33) by Newton's method and Steffensen method, respectively, and U0=(u1,0,u2,0,…,u99,0) is initial value. We choose the same iterative stop conditions:
(35)∥Unk+1-Unk∥∞<1.0e-10.
By the computer's calculus, in Table 3 the data represent Steffensen method's advantage.Table 3
The error of the approximation solutionUn  and the exact solution U*.
MethodStepErrorSteffensen7∥Un-U*∥≤1.231e-7Newton10∥Un-U*∥≤1.231e-7


## 6. Conclusion

The derivatives may prevent the application of the methods especially when they are not easy to find. In this paper, we show that the Steffensen method only uses evaluations of the function but maintains quadratic convergence and can converge. The new iterative method seems to work well in our numerical results, since we have obtained optimal order of convergence without any stability problem. With the different choice ofHk in the iteration (4), we will get different iterations without any derivative. Discussing these iterations is the future work to do.



---

*Source: 674539-2009-09-28.xml*