# On a New Iterative Scheme without Memory with Optimal Eighth Order

Authors: M. Sharifi; S. Karimi Vanani; F. Khaksar Haghani; M. Arab; S. Shateyi
Journal: The Scientific World Journal
 (2014)

---

## Abstract

The purpose of this paper is to derive and discuss a three-step iterative expression for solving nonlinear equations. In fact, we derive a derivative-free form for one of the existing optimal eighth-order methods and preserve its convergence order. Theoretical results will
be upheld by numerical experiments.


---

## Body

## 1. Introduction

Assume thatf
:
D
⊆
R
→
R is sufficiently smooth and that α
∈
D is its simple zero; that is, f
(
α
)
=
0. This paper concerns with numerical solution of nonlinear scalar equations by iterative expressions. Considering a known optimal eighth-order method with derivative and the conjecture of Cordero and Torregrosa [1], we construct a family of derivative-free methods without memory for solving a nonlinear equation.To shortly review the literature, we remind readers of the following. Kung and Traub in [2] have provided a class of n-step derivative-involved methods including n evaluations of the function and one of its first derivatives per full iteration to reach the convergence rate 2
n. They also have given a n-step derivative-free family of one parameter (consuming n
+
1 evaluations of the function) to again achieve the optimal convergence rate 2
n.Remark 1 (Kung-Traub’s conjecture [2]).
Multipoint iterative methods without memory, requiringd
+
1 function evaluations per iteration, have the order of convergence at most 2
d. Multipoint methods which satisfy the Kung-Traub conjecture (still unproved) are called optimal methods.Some well-known methods with eighth order of convergence can be found at [3]. As another example, Liu and Wang [4] suggested some optimal eighth-order methods using four evaluations per full cycle (
β
1
,
β
2
∈
R
) in what follows:
(1)
y
n
=
x
n
-
f
(
x
n
)
f
′
(
x
n
)
,
z
n
=
y
n
-
f
(
y
n
)
f
′
(
x
n
)
4
f
(
x
n
)
-
f
(
y
n
)
4
f
(
x
n
)
-
9
f
(
y
n
)
,
x
n
+
1
=
z
n
-
f
(
z
n
)
f
′
(
x
n
)
[
8
f
(
y
n
)
4
f
(
x
n
)
-
11
f
(
y
n
)
+
(
1
+
f
(
z
n
)
3
f
(
y
n
)
-
β
1
f
(
z
n
)
)
3
+
4
f
(
z
n
)
f
(
x
n
)
+
β
2
f
(
z
n
)
]
,
where the efficiency index is 1.682. Reference [4] also suggested the following three-step approach (
α
1
,
α
2
∈
R
) with the same number of evaluations and efficiency index:
(2)
y
n
=
x
n
-
f
(
x
n
)
f
′
(
x
n
)
,
z
n
=
y
n
-
f
(
y
n
)
f
′
(
x
n
)
f
(
x
n
)
f
(
x
n
)
-
2
f
(
y
n
)
,
x
n
+
1
=
z
n
-
f
(
z
n
)
f
′
(
x
n
)
[
(
f
(
x
n
)
-
f
(
y
n
)
f
(
x
n
)
-
2
f
(
y
n
)
)
2
+
f
(
z
n
)
f
(
y
n
)
-
α
1
f
(
z
n
)
+
4
f
(
z
n
)
f
(
x
n
)
+
α
2
f
(
z
n
)
(
f
(
x
n
)
-
f
(
y
n
)
f
(
x
n
)
-
2
f
(
y
n
)
)
2
]
.In what follows, in Section2, the main derivation is provided to design a new derivative-free family with optimal eighth-order convergence for nonlinear equations. Therein, we confirm the conjecture of Cordero-Torregrosa as well. Section 3 illustrates the accuracy of the new obtained three-step family of iterative methods by comparing the results for some nonlinear test functions. Finally, in Section 4, a conclusion will be drawn.


## 2. A New Derivative-Free Family

There are a number of papers (see, e.g., [1] and the references therein) about the idea of removing derivatives from the iteration function in order to avoid defining new functions and calculate iterates only by using the function that describes the problem and also trying to preserve the convergence order. The interest of these methods is to be applied on nonlinear equations when there are many problems for obtaining and evaluating the derivatives involved or when there is no analytical function to derive.Hence, our focus in this work is to derive a method without the use of derivatives for nonlinear equations.Remark 2 (Cordero and Torregrosa’s conjecture [1]).
Every time that one applies the approximation of the derivativef
′
(
x
n
)
≈
f
[
x
n
,
w
n
], with w
n
=
x
n
+
β
f
(
x
n
)
l, on an optimal method with the order 2
q, one needs l
≥
q for preserving the order of convergence.We begin by reminding the readers of the three-step iterative method without memory proposed in [5] with optimal eighth order of convergence:
(3)
y
n
=
x
n
-
f
(
x
n
)
f
′
(
x
n
)
,
z
n
=
x
n
-
(
f
(
x
n
)
f
′
(
x
n
)
f
(
x
n
)
f
(
x
n
)
-
f
(
y
n
)
)
×
(
1
+
(
f
(
y
n
)
f
(
x
n
)
)
2
+
3
(
f
(
y
n
)
f
(
x
n
)
)
3
)
,
x
n
+
1
=
z
n
-
(
f
(
z
n
)
f
[
z
n
,
y
n
]
+
f
[
z
n
,
x
n
,
x
n
]
(
z
n
-
y
n
)
)
×
(
1
+
2
f
(
z
n
)
f
(
x
n
)
-
18
(
f
(
y
n
)
f
(
x
n
)
)
4
+
(
f
(
z
n
)
f
(
y
n
)
)
3
)
.The main aim is to follow Remark2 and to present a derivative-free form of (3) with optimal eighth order of convergence. Therefore, using the approximation w
n
=
x
n
+
β
f
(
x
n
)
3, we present the following formulation (β
∈
R
∖
{
0
}):
(4)
y
n
=
x
n
-
f
(
x
n
)
f
[
x
n
,
w
n
]
,
w
n
=
x
n
+
β
f
(
x
n
)
3
,
z
n
=
x
n
-
(
f
(
x
n
)
f
[
x
n
,
w
n
]
f
(
x
n
)
f
(
x
n
)
-
f
(
y
n
)
)
×
(
1
+
(
f
(
y
n
)
f
(
x
n
)
)
2
+
3
(
f
(
y
n
)
f
(
x
n
)
)
3
)
,
x
n
+
1
=
z
n
-
(
f
(
z
n
)
f
[
z
n
,
y
n
]
+
φ
z
n
,
x
n
,
x
n
(
z
n
-
y
n
)
)
×
(
1
+
2
f
(
z
n
)
f
(
x
n
)
-
18
(
f
(
y
n
)
f
(
x
n
)
)
4
+
(
f
(
z
n
)
f
(
y
n
)
)
3
)
,
wherein
(5)
φ
z
n
,
x
n
,
x
n
=
f
[
z
n
,
x
n
]
-
f
[
x
n
,
w
n
]
z
n
-
x
n
.We shall see that the order of convergence for (4) reaches to the optimal case, that is, 8, with only four function evaluations per full iteration, which means that the proposed uniparametric family of derivative-free methods possesses the high efficiency index 1.682 and can be viewed as the derivative-free formulation of (3).Theorem 3.
Letα
∈
D be a simple zero of a sufficiently differentiable function f
:
D
⊂
R
→
R for an open interval D, which includes x
0 as an initial approximation of α. Then, the family of derivative-free methods (4) is of optimal order eight.Proof.
To find the asymptotic error constant of (4) where c
j
=
f
(
j
)
(
α
)
/
j
!, j
≥
1, we expand any terms of (4) around the simple root α in the nth iterate. Thus, we write
(6)
f
(
x
n
)
=
c
1
e
n
+
c
2
e
n
2
+
c
3
e
n
3
+
c
4
e
n
4
+
c
5
e
n
5
+
c
6
e
n
6
+
c
7
e
n
7
+
c
8
e
n
8
+
O
(
e
n
9
)
,
where e
n
=
x
n
-
α and
(7)
f
(
w
n
)
=
c
1
b
n
+
c
2
b
n
2
+
c
3
b
n
3
+
c
4
b
n
4
+
c
5
b
n
5
+
c
6
b
n
6
+
c
7
b
n
7
+
c
8
b
n
8
+
O
(
b
n
9
)
,
wherein b
n
=
w
n
-
α. Hence, we obtain
(8)
x
n
-
f
(
x
n
)
f
[
x
n
,
w
n
]
-
α
=
c
2
e
n
2
c
1
+
2
(
-
c
2
2
+
c
1
c
3
)
e
n
3
c
1
2
+
⋯
+
O
(
e
n
9
)
.
In the same vein, we have
(9)
f
(
y
n
)
=
c
2
e
n
2
+
(
-
2
c
2
2
c
1
+
2
c
3
)
e
n
3
+
⋯
+
O
(
e
n
9
)
,
and for the second substep, we have
(10)
z
n
-
α
=
-
c
2
c
3
c
1
2
e
n
4
+
(
-
β
c
1
5
c
2
2
+
9
c
2
4
+
2
c
1
c
2
2
c
3
-
2
c
1
2
(
c
3
2
+
c
2
c
4
)
)
c
1
4
e
n
5
+
⋯
+
O
(
e
n
9
)
.
At this time, Taylor’s series expansion of f
(
z
n
) around the root is needed. We find that
(11)
f
(
z
n
)
=
-
c
2
c
3
e
n
4
c
1
+
(
-
β
c
1
5
c
2
2
+
9
c
2
4
+
2
c
1
c
2
2
c
3
-
2
c
1
2
(
c
3
2
+
c
2
c
4
)
)
c
1
3
e
n
5
+
⋯
+
O
(
e
n
9
)
,
and subsequently
(12)
φ
z
n
,
x
n
,
x
n
=
c
2
+
2
c
3
e
n
+
(
β
c
1
3
c
2
+
3
c
4
)
e
n
2
+
3
β
c
1
2
(
c
2
2
+
c
1
c
3
)
e
n
3
+
⋯
+
O
(
e
n
9
)
.
Considering these Taylor’s series expansions in the last step of (4) will result in the following final error equation:
(13)
e
n
+
1
=
-
c
2
2
c
3
(
c
2
(
β
c
1
4
-
2
c
3
)
+
c
1
c
4
)
c
1
5
e
n
8
+
O
(
e
n
9
)
.
This shows that the iterative family of derivative-free methods without memory (4) is of optimal order eight. The proof is complete.Remark 4.
Theorem3 clearly supports the conjecture of Cordero-Torregrosa for providing low-complexity derivative-free iterative methods without memory out of optimal methods with derivative.Note that each method of (4) reaches the efficiency index 8
4
≈
1.682, which is greater than 4
3
≈
1.587 of optimal fourth-order techniques and 2
2
≈
1.424 of optimal Newton’s method. It has also the same computational efficiency index with (1), (2), and (3).Remark 5.
It must be remarked that, firstly, the paper [6] studied the multipoint iterative schemes using divided differences for self-acceleration of classical methods.We here state that the free nonzero parameterβ in (4) gives us the ability to increase the convergence R-order of (4) more. Such an acceleration in R-order is known as with memorization (see, e.g., [7]) according the classification of Traub [8] for nonlinear solvers. To be more precise, choosing
(14)
β
=
2
c
2
c
3
-
c
1
c
4
c
1
4
c
2
would yield an acceleration of convergence.Anyhow, since the simple zeroα and subsequently c
j are not known, one should give an approximation for (14) using an approximation polynomial A
(
t
)
≈
f
(
t
) in the domain D. Toward this goal, if we consider A
(
t
) to be Newton’s interpolatory polynomial of fourth degree passing through the five available nodes x
n
-
1, w
n
-
1, y
n
-
1, z
n
-
1, and x
n at the end of each cycle, then one has the following approximation:
(15)
β
n
=
4
A
(
3
)
(
x
n
)
-
A
′
(
x
n
)
A
(
4
)
(
x
n
)
/
A
′′
(
x
n
)
12
A
′
(
x
n
)
4
,
using a suitable β
0. Consequently, one is able to derive the following accelerated iterative method with memory:
(16)
β
n
=
4
A
(
3
)
(
x
n
)
-
A
′
(
x
n
)
A
(
4
)
(
x
n
)
/
A
′′
(
x
n
)
12
A
′
(
x
n
)
4
,
y
n
=
x
n
-
f
(
x
n
)
f
[
x
n
,
w
n
]
,
w
n
=
x
n
+
β
n
f
(
x
n
)
3
,
z
n
=
x
n
-
(
f
(
x
n
)
f
[
x
n
,
w
n
]
f
(
x
n
)
f
(
x
n
)
-
f
(
y
n
)
)
×
(
1
+
(
f
(
y
n
)
f
(
x
n
)
)
2
+
3
(
f
(
y
n
)
f
(
x
n
)
)
3
)
,
x
n
+
1
=
z
n
-
(
f
(
z
n
)
f
[
z
n
,
y
n
]
+
φ
z
n
,
x
n
,
x
n
(
z
n
-
y
n
)
)
×
(
1
+
2
f
(
z
n
)
f
(
x
n
)
-
18
(
f
(
y
n
)
f
(
x
n
)
)
4
+
(
f
(
z
n
)
f
(
y
n
)
)
3
)
.Obviously, if fewer nodes are used for the interpolating polynomial, slower acceleration is achieved. An increase of convergence is achieved in this way without additional functional evaluations, making the proposed root solvers (16) efficient. This acceleration will be seen in Section 3.Theorem 6.
Let the functionf
(
x
) be sufficiently differentiable in a neighborhood of its simple zero α. If an initial approximation x
0 is sufficiently close to α, then the R-order of convergence of (16) is at least 4
+
17.Proof.
Let{
x
n
} be a sequence of approximations generated by an iterative method with order p. The error relation with the self-accelerating parameter β
=
β
n for (16) is in what follows:
(17)
e
n
+
1
=
x
n
+
1
-
α
~
c
n
,
8
e
n
8
,
wherein c
n
,
8 is the asymptotic error constant. Using a symbolic computation and (13), we attain that
(18)
2
c
2
c
3
-
c
1
c
4
c
1
4
c
2
~
e
n
-
1
.
Substituting the value of (
2
c
2
c
3
-
c
1
c
4
)
/
(
c
1
4
c
2
) from (18) in (17), one may obtain
(19)
e
n
+
1
~
e
n
-
1
e
n
8
.
Thus, it is easy to obtain
(20)
e
n
p
~
A
-
1
/
p
C
e
n
8
+
1
/
p
,
wherein A and C are two constants and subsequently
(21)
p
=
8
+
1
p
,
with two solutions {
4
-
17
,
4
+
17
}. Clearly the value for p
=
4
+
17
≈
8.12311 is acceptable and would be the convergence R-order of the method (16) with memory. The proof is complete.


## 3. Numerical Testing

The objective of this section is to provide a comparison between the presented schemes and the already known methods in the literature.For numerical reports here, we have used the optimal eighth-order three-step method (1) as (LW8) with β
1
=
β
2
=
0, the optimal eighth-order three-step method (3) as (SM8), our optimal three-step eighth-order method (4) with β
=
-
0.0001, and the accelerated method with memory (16) denoted by (APM) with β
0
=
-
0.0001.The results are summarized in Tables1 and 2 after some full iterations. As they show, novel schemes are comparable with all of the methods. All numerical instances were performed by Mathematica 8 using 1000 fixed floating point arithmetic [9].Table 1
Results of comparisons for Example7.
Methods
|
f
(
x
1
)
|
|
f
(
x
2
)
|
|
f
(
x
3
)
|
|
f
(
x
4
)
|
COC
LW8
0.85460
4.8410
×
1
0
-
7
2.8515
×
1
0
-
57
4.1317
×
1
0
-
459
8.00000
SM8
0.85215
1.4818
×
1
0
-
8
3.3414
×
1
0
-
70
2.2345
×
1
0
-
563
8.00000
PM
0.64289
2.2594
×
1
0
-
9
9.7768
×
1
0
-
77
1.2017
×
1
0
-
615
8.00000
APM
0.64289
1.2590
×
1
0
-
9
2.0944
×
1
0
-
79
2.9252
×
1
0
-
646
8.12358Table 2
Results of comparisons for Example8.
Methods
|
f
(
x
1
)
|
|
f
(
x
2
)
|
|
f
(
x
3
)
|
|
f
(
x
4
)
|
COC
LW8
0.080790
4.3442
×
1
0
-
14
6.3406
×
1
0
-
112
1.3057
×
1
0
-
894
8.00000
SM8
2.0294
2.2403
×
1
0
-
9
1.1696
×
1
0
-
74
6.4533
×
1
0
-
597
8.00000
PM
2.0357
2.2049
×
1
0
-
9
1.0295
×
1
0
-
74
2.3266
×
1
0
-
597
8.00000
APM
2.0357
9.1086
×
1
0
-
10
7.2327
×
1
0
-
78
1.3852
×
1
0
-
631
8.13093We have computed the root of each test function for the initial guessx
0 while the iterative schemes were stopped when |
f
(
x
n
)
|
≤
1
0
-
150. As can be seen, the obtained results in Tables 1 and 2 are in harmony with the analytical procedure given in Section 2.The computational order of convergence (COC) has also been computed by(22)
COC
=
ln
⁡
|
f
(
x
n
)
/
f
(
x
n
-
1
)
|
ln
⁡
|
f
(
x
n
-
1
)
/
f
(
x
n
-
2
)
|
.Example 7.
In this test, we compare the behavior of different methods for finding the complex solution of the following nonlinear equation:(23)
f
(
x
)
=
(
-
1
+
2
I
)
+
1
x
+
x
+
sin
(
x
)
,
using the initial approximation x
0
=
1
-
3
I where α
=
0.28860
⋯
-
1.24220
⋯
I. The results for this test are given in Table 1.Example 8.
We here compare the behavior of different methods for finding the solution of(24)
g
(
x
)
=
(
-
2
+
x
)
sin
(
tanh
(
x
)
)
,
using the initial approximation x
0
=
1.0 where α
=
2. The results for this test are given in Table 2.It should be mentioned that our method (4) cannot be easily extended for nonlinear systems. The reason is that the weight functions used in (4) do not contain a finite difference operator in the denominators. Such an extension might be pursued for future studies. However, a simple extended version of (4) for the N-dimensional case can be written in what follows:
(25)
y
(
n
)
=
x
(
n
)
-
J
x
,
w
-
1
F
(
x
(
n
)
)
,
n
=
0,1
,
2
,
…
,
z
(
n
)
=
y
(
n
)
-
[
J
x
,
y
-
1
J
x
,
w
-
I
]
[
J
x
,
w
-
1
F
(
x
(
n
)
)
]
,
x
(
n
+
1
)
=
z
(
n
)
-
J
y
,
z
-
1
F
(
z
(
n
)
)
,
wherein w
(
n
)
=
x
(
n
)
+
F
(
x
(
n
)
) and it possesses only fifth order of convergence. Note that the extended version of Steffensen’s method has been written by
(26)
x
(
n
+
1
)
=
x
(
n
)
-
J
x
,
w
-
1
F
(
x
(
n
)
)
,
n
=
0,1
,
2
,
…
,
wherein
(27)
J
x
,
w
=
J
(
x
(
n
)
,
β
H
(
n
)
)
=
(
F
(
x
(
n
)
+
H
(
n
)
e
1
)
-
F
(
x
(
n
)
)
,
…
,
F
(
x
(
n
)
+
H
(
n
)
e
N
)
-
F
(
x
(
n
)
)
)
H
(
n
)
-
1
,
with H
(
n
)
=
diag
⁡
(
β
f
1
(
x
(
n
)
)
,
…
,
β
f
N
(
x
(
n
)
)
). Now we apply (25) to solve a nonlinear integral equation, and keeping the rate of convergence at eight will remain as an open problem for future works.Example 9.
Consider the mixed Hammerstein integral equation [10]:
(28)
x
(
s
)
=
1
+
1
5
∫
0
1
‍
G
(
s
,
t
)
x
(
t
)
3
d
t
,
where x
∈
C
[
0,1
], s
,
t
∈
[
0,1
], and the kernel G is given by
(29)
G
(
s
,
t
)
=
{
(
1
-
s
)
t
,
t
≤
s
,
s
(
1
-
t
)
,
t
>
s
.In order to solve this nonlinear integral equation, we transform the above equation into a finite-dimensional problem by using Gauss-Legendre quadrature formula given as(30)
∫
0
1
‍
f
(
t
)
d
t
≈
∑
j
=
1
t
w
j
f
(
t
j
)
,
where the abscissas t
j and the weights w
j are determined for t
=
10 by Gauss-Legendre quadrature formula. Denoting the approximation of x
(
t
i
) by x
i
(
i
=
1,2
,
⋯
,
t
), we obtain the system of nonlinear equations
(31)
f
(
x
1
,
…
,
x
t
)
=
5
x
i
-
5
-
∑
j
=
1
t
‍
a
i
j
x
j
3
=
0
,
where, for i
=
1,2
,
…
,
t, we have
(32)
a
i
j
=
{
w
j
t
j
(
1
-
t
i
)
,
if
j
≤
i
,
w
j
t
i
(
1
-
t
j
)
,
if
i
<
j
,
wherein the abscissas t
j and the weights w
j are known.Using the initial approximationx
(
0
)
=
(
0.5
,
…
,
0.5
)
T, we apply the proposed method (25) denoted by PMS with β
=
0.001 which is multiplication-rich to find the final solution vector of the nonlinear integral equation (31). Table 3 shows the residuals in l
2 norm, when t
=
10 is the size of the nonlinear system of equations.Table 3
Results of comparisons for Example9.
Methods
∥
f
(
x
1
)
∥
∥
f
(
x
2
)
∥
∥
f
(
x
3
)
∥
∥
f
(
x
4
)
∥
COC
PMS
23.6907
2.05639
×
1
0
-
8
6.73602
×
1
0
-
48
2.554
×
1
0
-
245
4.99994


## 4. Concluding Remarks

Solving nonlinear equations is a classical problem which has interesting applications in various branches of science and engineering (see, e.g., [11]). In this study, we have described an iterative method without memory to find a simple root α of a nonlinear equation f
(
x
)
=
0 on an open interval D.The derived scheme was developed by applying the conjecture of Cordero-Torregrosa and it was proved that it converges to the simple zero of a nonlinear equation with optimal eighth order of convergence. This shows that it has the optimal efficiency index 1.682. We, furthermore, discussed how to increase theR-order of convergence via with memorization. Some examples have also been included to support the theoretical parts.



---

*Source: 727490-2014-08-28.xml*