Self-accelerating two-step Steffensen-type methods with
memory and their applications on the solution of nonlinear
BVPs
Quan Zheng, Xiuhui Guo, Fengxi Huang
College of Sciences, North China University of Technology, Beijing 100144, China
[e-mail] (Q. Zheng)
Abstract—In this paper, seven self-accelerating iterative methods with memory are derived from an optimal two-step
Steffensen-type method without memory for solving nonlinear equations, their orders of convergence are proved to be increased
from 4 to
26 ,
(517) / 2
,5 and
(533) / 2
, numerical examples are demonstrat-ed demonstrated to verify the theoretical results, and
applications for solving systems of nonlinear equations and BVPs of nonlinear ODEs are illustrated.
Keywords-Nonlinear equation; Newton's method; Steffensen-type method; Derivative free; Super convergence
1. Introduction
Considering iterative methods to solve a nonlinear equation
() 0fx , the most famous method is Newton’s method (NM, see
[1]):
1
()
,1, 2,...,
()
n
nn
n
fn
f
x
xx x


c
(1)
where
0
x
is an initial guess of the root. If the derivative
()
n
fx
c
is
replaced by the divided difference
(())()
()
[, ()]
fx fxfx
nn n
fx
n
fx xfx
nn n


,
Newton's method becomes Steffensen’s method (SM, see [1]).
Steffensen’s method is a tough competitor of Newton’s method
since it is derivative free. Because Kung and Traub conjectured
in 1974 that a multipoint iteration based on m evaluations with-
out memory has optimal order
1
2m of convergence (see [2]),
NM and SM are one-step methods of optimal order without
memory. The efficiency index of them is 2 1.4142 .
Further, a parametric Steffensen’s method (PSM) was
suggested in Section 8.4 in [3]:
1
() ,0,1, 2,...
[, ()]
n
nn
nnnn
fx
xx n
fx xfx
E
 

(2)
 convergent with the
asymptotic convergence constant
(1( ))( )
2()
fa f a
n
fa
E
ccc

c
. If
1
()
,
nfa
E | c
PSM can have smaller error. Therefore, by defining
1111
1/ [,()]
nnnnn
fx xfx EE


at the previous iteration recursively as
the iteration proceeds, a self-accelerating Steffensen’s method
(SASM) was proposed in Section 8.6 in [3]:
1
()
[, ()]
1
[,]
11
,
,
nn
n
fx
n
fx xfx
nnn n
fx z
nn
xx
E
E



 
°
°
®
° 
°
¯
(3)
where
00
(())sign fx E
c

, or
00 0
1/ [ ,( )]fx xfx
, etc.
SASM is a derivative-free one-step method with memory. It
only uses two new evaluations of the function per step to
achieve convergence of order 2 1 2.4142| , and has efficiency
index
2 1 1.5538|
.
Some other optimal multipoint Steffensen-type methods
without memory were derived in [4-7]. General optimal
derivative-free iterative methods for solving nonlinear
equations were introduced in [2] and [7]. Two-step self-
accelerating Steffensen-type methods were investigated in [8-
10]. Steffensen-type methods and their applications in the
solution of non-linear systems and nonlinear differential equa-
tions were discussed in the literature (see [1, 3, 4, 8, 9]).
This work suggests seven self-accelerating iterative
methods with memory for solving nonlinear equations in
section 2, proves their high orders of super convergence in
section 3, demonstrates examples and applications in section 4,
and makes conclusions in section 5.
2. The self-accelerating methods
By using second-order Newtonian interpolation
2()Nx
after
an iteration of SM to approximate ()fx
and find the root of
2
() 0Nx
to approximate the exact root, we obtain a parametric
Steffensen-type method (PSTM):
1
()
[,]
()
[, ][,][,]
,
.
nn
nn
fx
n
fx z
nn
fy
n
fx yfy zfxz
nnnnnn
yx
xy


 
°
°
®
° 
°
¯
(4)
where
()
nnnn
zx fx E 
. PSTM is an optimal two-step meth-od
without memory (see [5, 7]).
Supported by Beijing Natural Science Foundation (No. 1122014).
Open Journal of Applied Sciences
Supplement：2012 world Congress on Engineering and Technology
70 Cop
y
ri
g
ht © 2012 SciRes.

Theorem 2.1 (see [7]) Let
:fD Ro
be a sufficiently different-
iable function with a simple root
,aDDR be an open set,
0
x
be close enough to a , then the method (4) is at least of
fourth-order, and satisfies the error equation
22 4 5
1223
(1( ))[]()
nn nn
efaccceOe E
c

, (5)
where
()
()
!()
,,0,1, 2,...
k
knn
fa
kfa
cexan
c

From PSTM and its error equation, in order to achieve
super fourth-order convergence, the free parameters
n
E
should
tend to 1/( )fa
c

.Therefore, we propose six self-accelerating
Steffensen-type methods (SASTMs) with memory as follows:
compute (4) with
1
11
1
() [,]
nn
nn
ifx z EE

{  (SASTM1) (6)
2
11
1
() [, ]
nn
nn
ii fx y EE

{ 
(SASTM2) (7)
3
11
1
() [,]
nn
nn
iii fy z EE

{  (SASTM3) (8)
4
1
1
() [,]
nn
nn
iv fxx EE

{  (SASTM4) (9)
5
1
1
() [,]
nn
nn
vfz x EE

{  (SASTM5) (10)
6
1
1
() [,]
nn
nn
vi fy x EE

{  (SASTM6) (11)
By Newton’s interpolation formula on points
n
x
,
1n
y

and
1n
x

as
Follows:
1111
()( )[ ,]()[ ,,]()()
nnnnnnnnn
Nxfxfx yxxfx yxxxxy


using 1/( )
nn
Nx E c 
we propose the seventh self-accelerating
Steffensen-type methods: compute (4) with
7
1111
1
() [,][, ][, ]
nn
nnnnnn
vii fx yfxxfyx EE

{ 
.
(SASTM7) (12)
3. The convergence
Theorem 3.1. Let
:fD Ro
be sufficiently differentiable near
a simple root
,aDDR
be an open set,
0
x
be close enough
to a
, then SASTM1, SASTM2 and SASTM4 achieve the
convergence of order 26 , SASTM3 and SASTM5 achieve
the convergence of order (517) / 2 ,SASTM6 achieves fifth-
order convergence, and SASTM7 achieves the convergence of
order (533) / 2
.
Proof. Using Taylor formula and denoting
z
nn
eza  and
y
nn
eya  , for SASTM1, we have
(1())()
z
nnnn
efaeoe E
c

,
()
[,] ()(2())()
2
nnnnn
fa
fxzfaf aeoe E
cc
cc 
.
Hence,
11
121 1
1[1(2())]()
()
nnnn
face oe
fa
EE

c 
c
.
By substituting it into Eq. (5), we obtain
12324224
1122311
(2( ))[]()
nn nnnn
efaccceeoee E
 
c 
.
For SASTM2, we have
22
2
(1( ))()
y
nn nn
efaceoe E
c

,
()
1()
2
[, ]()
nnn n
o fafx yfaee 
cc
c

,
2
21 1
1
()
[1]()
nnn
fa
ce oe E

c

.
By substituting
2
n
E into Eq. (5), we obtain
32 4224
1223 11
[] ()
nnnnn
eccceeoee


.
For SASTM4, we have
111
()
1()
2
[,] ()
nnn n
o fafxxfaee


cc
c
 ,
and obtain the same error equation as the above. By solving
2
42rr  , the convergence of order
26 4.4495|
is proved
for SASTM1, 2 and 4.
For SASTM3 and 5, if
n
z converges to a with order p and
n
x
Converges to a
with order
r
as:
()
zpp
nnn n
eCeoe 
and
1
()
rr
nnnn
eDeoe


,
then
111
()
zp rprp
nnnnn
eCDeoe
 

,
22
1111
()
rrr
nnnn n
eDDeoe


.
So, we have
1
[,][,,] ,
[,] [,]
[,]
[, ][, ,]()
yz
nn nn
nn nn
nn nn
y
ynn
nn
nnnnn nn
fx aefxza
ee ee
fx zfx z
fyae
ee
fx yfx yzyx



Cop
y
ri
g
ht © 2012 SciRes.71

2
[,,]
[,]
[, ,][, ,]()
[, ][, ,]()
[, ,][,,,]
[, ][, ,]()
[,,]
[,]
[, ,][, ,,]
[
()
y
n
y
n
z
nn
fx z a
nn
fx z
nn
y
fx yafx y zee
nnnnn nn
y
fx yfx y zee
nnnnn nn
yz
fx y zefx y zaee
nnnnnnn nn
y
fx yfx y zee
nnnnn nn
fx z a
nn
fx z
nn
fx yz fxyza
nnn nnn
f
e
e
ee





u
,] [,,]()
.
y
xyfxyz ee
nnnnn nn

For SASTM3,
21 1
21111
[,][,]
11
[,]
11
()
(),
z
nn
zz
nn nn
pr pr
nnn n
fyzfx a
n
nn
fyz
nn
ee
ce eoe e
cCD eoe


 





2222 24
122111 231
3224 2424
2231111
()()()
() ().
pr pr
nnnn n
pr pr
nnn n
eccCDeccoe
cc cCDeoe

 

 


For SASTM5, we have the same results
21111
()
zprpr
nnnn n
ecCDeoe

 
 ,
3224 2424
1223111 1
() ()
pr pr
nnnnn
ecccCDe oe


 .
Comparing the exponents of
1n
e in the expression of
z
n
e
and
1n
e respectively, we have
respectively, we have
2
,
24.
rpp r
rpr


® 
¯
From its non-trivial solution (117 )/ 2p  and (517) / 2,r 
we prove that SASTM3 and 5 achieve the same convergence of
order (517)/ 24.5616| .
For SASTM6 and 7, if
()
ypp
nnnn
eCeoe 
and
1()
rr
nnnn
eDeoe
 
,
then
22
11 1
1111
(),
().
yp rprp
nnnnn
rr r
nnnn n
eCDe oe
eDDeoe
 



So, for SASTM6,
21111
222 2
2111 1
(),
(),
zprpr
nnnnn
yprpr
nnnn n
ecCDe oe
ecCDe oe

 

 


3224 2424
1223111 1
() (),
pr pr
nnnnn
ecccCDe oe



and establish
2
2,
24.
rp pr
rpr
 
® 
¯
From its non-trivial solution 5/2p and 5,r we prove that
SASTM6 achieves fifth-order convergence.
For SASTM7, we have
11111
1111
1111 11
1111
11
3111 1
[, ,][, ,]()
[,][, ][, ]
[, ,][, ,,]
[,][, ][, ]
(),
yy
znnnnn nn n
n n
nnnnn n
y
nn nnnnnnn
n
nnnnn n
pr pr
nnnn
fx yaefx yxee
ee
fxyfxxfyx
fx yxefx yxaeee
fxyfxxfyx
cCD eoe
e


 

 






22121
231111
222 4242242
12323 1111
(),
() (),
yprpr
nnnnn
pr pr
nnnnn
ccCD eoe
eccccCDe oe
 

 



and establish
2
21,
242.
rp pr
rpr


® 
¯
From its non-trivial solution (533) / 4p 
and
(533) / 25.3723r |
, we
prove that SASTM7 achieves the convergence of order (533) / 2
.
Each of SASTMs is a two-step derivative-free method with
memory and only uses three new evaluations of the function
per step to achieve super fourth-order convergence. SASTM1,
2 and 4 have the same efficiency index
3261.6448|
. SASTM3
and 5 have the same efficiency index
3(517) / 21.6585|
. SASTM 6
and 7 have the efficiency indices
3
5 1.7100|
and
3(533)/ 21.7514,|
respectively. Whereas, two self-accelerating methods proposed
-- uses three new evaluations
of the function per iteration to achieve the super fourth-order
convergence of order
26
and its efficiency index is only
3
261.6448| .
4. Numerical examples
In the examples,NM,SM,PSM,SASM, PSTM and SASTMs
are compared with each other. The computational order of
convergence is defined as:
1
12
log(|| / ||).
log(|| / ||)
nn
nn
ee
COC ee


where
0
1, 1,2,...,7.
i
i E
Example 1. Numerical results in Table I agree with
theoretical results in the theorems.
TABLE I.
2
0
( )31,0,0.2
x
fxx exax


Method n 1 2 3 4
NM
||
n
e
COC
.533e-2 .356e-5 .158e-11 .312e-24
2.01691 2.00030 2.00000
SM ||
n
e
COC
.282e-1 .513e-3 .165e-6 .170e-13
2.04367 2.00830 2.00009
72 Cop
y
ri
g
ht © 2012 SciRes.

PSM
(1)
n
E {
||
n
e
COC
.134e-1 .677e-4 .172e-8 .111e-17
1.95757 2.00059 2.00000
SASM ||
n
e
COC
.282e-1 .160e-4 .131e-12 .433e-32
3.81335 2.49109 2.40945
PSTM
(1)
n
E {
||
n
e
COC
.468e-4 .389e-18 .186e-74 .977e-300
3.87748 4.00000 4.00000
PSTM
(1)
n
E {
||
n
e
COC
.595e-4 .366e-18 .525e-75 .222e-302
4.02926 4.00000 4.00000
SASTM1 ||
n
e
COC
.468e-4 .414e-21 .441e-98 .331e-440
4.69620 4.51372 4.44480
SASTM2 ||
n
e
COC
.468e-4 .135e-22 .371e-104 .175e-467
5.10548 4.39945 4.45460
SASTM3
||
n
e
COC
.468e-4 .317e-21 .228e-100 .956e-462
4.72820 4.60962 4.56612
SASTM4 ||
n
e
COC
.468e-4 .104e-22 .132e-104 .166e-469
5.13642 4.39102 4.45547
SASTM5 ||
n
e
COC
.468e-4 .302e-21 .180e-100 .324e-462
4.73383 4.60889 4.56606
SASTM6
||
n
e
COC
.468e-4 .195e-24 .691e-127 .384e-639
5.61230 5.02717 5.00000
SASTM7 ||
n
e
COC
.468e-4 .810e-27 .207e-148 .679e-802
6.26819 5.34210 5.37438
Example 2. Consider to solve a boundary-value problem of
ODEs as the following:
2
1
1
2
1,
(0)1, (1)().
yy
yyee

cc c

°
® 
°
¯
Let
4N
and use the methods to solve the nonlinear system
() 0Fs
G
with
00s
G
by the multiple shooting method (see [4, 9]).
The numerical results are showed in Table II.
TABLE II. FOR THE MULTIPLE SHOOTING METHOD
Method n 1 2 3 4
SM
||() ||
n
Fs
G
|| ||
n
yy
|| ||
n
yy
cc

.560e-1 .149e-3 .994e-10 .203e-21
.283e-1 .584e-4 .326e-5 .326e-5
.585e-1 .143e-3 .459e-5 .458e-5
PSTM
||() || n Fs
G
|| ||
n
yy
|| ||
n
yy
cc

.271e-3 .124e-17 .219e-76 .336e-311
.142e-3 .326e-5 .326e-5 .326e-5
.346e-3 .459e-5 .459e-5 .458e-5
SASTM1 ||() || n Fs
G
|| ||
n
yy
|| ||
n
yy cc 
.271e-3 .154e-4 .280e-9 .301e-15
.142e-3 .230e-5 .326e-5 .326e-5
.346e-3 .129e-4 .458e-5 .458e-5
SASTM2
||() || n Fs
G
|| ||
n
yy
|| ||
n
yy
cc

.271e-3 .135e-21 .289e-99 .118e-446
.142e-3 .326e-5 .326e-5 .326e-5
.346e-3 .459e-5 .459e-5 .458e-5
SASTM3 ||() || n Fs
G
|| ||
n
yy
|| ||
n
yy cc 
.271e-3 .764e-20 .236e-95 .121e-439
.142e-3 .326e-5 .326e-5 .326e-5
.346e-3 .459e-5 .459e-5 .458e-5
SASTM4
||() || n Fs
G
|| ||
n
yy
|| ||
n
yy
cc

.271e-3 .446e-22 .131e-102 .711e-462
.142e-3 .326e-5 .326e-5 .326e-5
.346e-3 .459e-5 .459e-5 .458e-5
SASTM5 ||() || n Fs
G
|| ||
n
yy
|| ||
n
yy
cc

.271e-3 .996e-20 .897e-95 .564e-437
.142e-3 .326e-5 .326e-5 .326e-5
.346e-3 .459e-5 .459e-5 .458e-5
SASTM6 ||()|| n Fs
G
|| ||
n
yy
|| ||
n
yy
cc

.271e-3 .135e-21 .289e-99 .118e-446
.142e-3 .326e-5 .326e-5 .326e-5
.346e-3 .459e-5 .459e-5 .458e-5
SASTM7
||() ||
n
Fs
G
|| ||
n
yy
|| ||
n
yy
cc

.271e-3 .446e-22 .131e-102 .711e-462
.142e-3 .326e-5 .326e-5 .326e-5
.346e-3 .458e-5 .458e-5 .458e-5
5. Conclusions
In this work, we derive seven self-accelerating Steffensen-
type methods with memory for solving nonlinear equations and
establish the comparative advantage of high efficiency
theoretically and numerically. The suggested self-accelerating
methods without derivative are convenient to be applied in the
multiple shooting method for solving boundary-value problems
of nonlinear ODEs, where derivatives are difficult to be
obtained.
REFERENCES
[1] J.M. Ortega, W.G. Rheinboldt, Iterative Solution of Nonlinear
Equations in Several Variables, Academic Press, New York,
1970.
[2] H.T. Kung, J.F. Traub, Optimal order of one-point and multipoint
iteration, J. Assoc. Comput. Math. 21 (1974) 634-651.
[3] J.F. Traub, Iterative Methods for the Solution of Equations,
Prentice-Hall, Englewood Cliffs, New Jersey, 1964.
[4] -fensen’s
type method in Banach spaces with applications on boundary-
value problems, J. Comput. Appl. Math. 216 (2008) 243-250.
[5] W. Bi, H. Ren, Q. Wu, A class of two-step Steffensen type
methods with fourth-order convergence, Appl. Math. Comput.
209 (2009) 206-210.
[6] F. Soleymani, S.K. Vanani, Optimal Steffensen-type meth-ods
with eighth order of convergence, Comput. Math. Appl. 62 (2011)
4619-4626.
[7] Q. Zheng, J. Li, F. Huang, An optimal Steffensen-type family for
solving nonlinear equations, Appl. Math. Comput. 217 (2011)
9592-9597.
[8] Q. Zheng, J. Wang, P. Zhao, L. Zhang, A Steffensen-like method
and its higher-order variants, Appl. Math. Comput. 214 (2009)
10-16.
[9] Q. Zheng, P. Zhao, L. Zhang, W. Ma, Variants of Steffensen-
secant method and applications, Appl. Math. Comput. 216 (2010)
3486-3496.
[10] -point
methods with and without memory for solving nonlinear
equations, Appl. Math. Comput. 217 (2010) 1887-1895.
Cop
y
ri
g
ht © 2012 SciRes.73