# On a New Three-Step Class of Methods and Its Acceleration for Nonlinear Equations

Authors: T. Lotfi; K. Mahdiani; Z. Noori; F. Khaksar Haghani; S. Shateyi
Journal: The Scientific World Journal
 (2014)

---

## Abstract

A class of derivative-free methods without memory for approximating a simple zero of a nonlinear equation is presented. The proposed class uses four function evaluations per iteration with convergence order eight. Therefore, it is an optimal three-step scheme without memory based on Kung-Traub conjecture. Moreover, the proposed class has an accelerator parameter with the property that it can increase the convergence rate from eight to twelve without any new functional evaluations. Thus, we construct a with memory method that increases considerably efficiency index from8
1
/
4
≈
1.681 to 12
1
/
4
≈
1.861. Illustrations are also included to support the underlying theory.


---

## Body

## 1. Introduction

The first attempts for classifying iterative root-finding methods were done by Traub [1]. He divided iterative methods for finding zeros of a function into two sets: one-point and multipoint methods. There is a fact about how to create a new method. As Traub investigated in his book [1], and Kung and Traub mentioned in [2], construction of one-point methods is not a useful task. In other words, to construct an optimal one-point method with convergence order n, we need n functional evaluations, while for construction an optimal method without memory having convergence order 2
n; only n
+
1 function evaluations are required.To be more precise, constructing an optimal one-point method with eighth-order convergence needs eight function evaluations, while constructing an optimal three-point method without memory having the same convergence order requires four functional evaluations. As a result, many researchers have paid much attention to construct optimal multipoint iterations without memory based on the unproved conjecture due to Kung and Traub: any multipoint iteration without memory usingn
+
1 function evaluations can reach the optimal order 2
n.This work follows two main goals: frst developing a new optimal three-step derivative-free class of methods without memory and second developing the proposed class to methods with memory. In this way, it reaches convergence order 12 without any new functional evaluations. Because of the derivative-free property of the proposed class, it can be used for finding zeros of not only smooth functions but also nonsmooth ones. Moreover, as we pointed out above we can reach the convergence order 12 using the same functional evaluations (to three-step without memory iterations) and, therefore, increasing50
% convergence order is the other aspect and contribution of this work.Note that in most test problems for nonlinear equations computing derivatives are an easy exercise. However, for some practical problems computing the derivative might be a cumbersome task and we have to relay on methods free of derivatives. For further reading on this topic, one may refer to [3–6].The paper is organized as follows. First, a new without memory family of optimal order eight, consuming four function evaluations per iteration, is proposed by using two weight functions in Section2. A different way to compute the order of convergence for iterative methods that use divided differences instead of derivatives is presented in Section 3, when we derive a method with memory. The significant increase of convergence speed is achieved without additional function evaluations, which is the main advantage of such methods. Section 4 is devoted to numerical results connected to the order of the methods with and without memory. And finally, concluding remarks will be drawn in Section 5.


## 2. Construction of a New Three-Step Class

Let the scalar functionf
:
D
⊂
R
→
R and f
(
α
)
=
0
≠
f
′
(
α
)
=
c
1. In other words, α is a simple zero of f
(
x
)
=
0. In this section, we start with the three-step scheme:
(1)
y
k
=
x
k
-
f
(
x
k
)
f
′
(
x
k
)
,
z
k
=
y
k
-
f
(
y
k
)
f
′
(
y
k
)
,
x
k
+
1
=
z
k
-
f
(
z
k
)
f
′
(
z
k
)
,wherek
=
0,1
,
…, is the iteration indicator. The order of convergence for (1) is eight but its computational efficiency is low. We substitute derivatives in all three steps by suitable approximations that use available data; thus we introduce the following approximations:
(2)
hhhhh
f
′
(
x
k
)
≈
f
[
x
k
,
w
k
]
,
where
w
k
=
x
k
+
β
f
(
x
k
)
,
f
′
(
y
k
)
≈
f
[
y
k
,
w
k
]
H
(
u
k
,
v
k
)
,
u
k
=
f
(
y
k
)
f
(
x
k
)
,
v
k
=
f
(
y
k
)
f
(
w
k
)
,
f
′
(
z
k
)
≈
f
[
y
k
,
z
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
W
(
s
k
)
,
hihhhhhhhhhhhhhhhhhhhhhhh
s
k
=
f
(
z
k
)
f
(
x
k
)
,in the first, second, and third steps of (1), where H and W are weight functions. The following iterative family of three-step methods is obtained:
(3)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
f
(
x
k
)
,
hhhhhhhhhhhhhhhhhhhhhhhhhih
β
∈
R
,
z
k
=
y
k
-
H
(
u
k
,
v
k
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hhhhhhhhhhhhhhhhhhhhhhhih
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
W
(
s
k
)
hhhhhh
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhhhhhhh
s
k
=
f
(
z
k
)
f
(
x
k
)
.In the following theorem, we state suitable conditions for deriving a new optimal class without memory according to the Kung and Traub conjecture [2] (also known as K-T hypothesis).Theorem 1.
Letf
:
D
⊂
R
→
R be a scalar function which has a simple root α in the open interval D, and also the initial approximation x
0 is sufficiently close to the simple zero. Then, the three-step iterative method (3) has eighth-order under the conditions W
(
0
)
=
W
′
(
0
)
=
1, H
(
0,0
)
=
H
u
(
0,0
)
=
H
u
u
(
0,0
)
=
1, H
v
(
0,0
)
=
H
v
v
(
0,0
)
=
0, and H
u
v
(
0,0
)
=
2 and satisfies the following error equation:
(4)
e
k
+
1
=
(
1
+
β
f
′
(
α
)
)
4
c
2
2
c
3
×
(
(
9
+
β
f
′
(
α
)
(
7
+
β
f
′
(
α
)
)
)
c
2
3
s
s
s
s
s
s
+
2
c
2
c
3
-
c
4
(
9
+
β
f
′
(
α
)
(
7
+
β
f
′
(
α
)
)
)
β
f
′
)
e
k
8
+
O
(
e
k
9
)
.Proof.
By using Taylor’s expansion off
(
x
) around α and taking into account that f
(
α
)
=
0, we obtain
(5)
f
(
x
)
=
f
′
(
α
)
(
(
e
k
9
)
e
k
+
c
2
e
k
2
+
c
3
e
k
3
+
c
4
e
k
4
s
s
+
c
5
e
k
5
+
c
6
e
k
6
+
c
7
e
k
7
+
c
8
e
k
8
+
O
(
e
k
9
)
)
,
where e
k
=
x
k
-
α, e
k
,
w
=
w
k
-
α, e
k
,
y
=
y
k
-
α, e
k
,
z
=
z
k
-
α, and c
k
=
f
(
k
)
(
α
)
/
k
!
f
′
(
α
). Therefore,
(6)
e
k
,
w
=
(
1
+
β
f
′
(
α
)
)
e
k
+
β
f
′
(
α
)
c
2
e
k
2
+
β
f
′
(
α
)
c
3
e
k
3
+
β
f
′
(
α
)
c
4
e
k
4
+
β
f
′
(
α
)
c
5
e
k
5
+
β
f
′
(
α
)
c
6
e
k
6
+
β
f
′
(
α
)
c
7
e
k
7
+
β
f
′
(
α
)
c
8
e
k
8
+
O
(
e
k
9
)
,
(7)
f
(
w
k
)
=
f
′
(
α
)
(
1
+
f
′
(
α
)
β
)
e
k
+
f
′
(
α
)
(
1
+
f
′
(
α
)
β
(
3
+
f
′
(
α
)
β
)
)
c
2
e
k
2
+
⋯
+
O
(
e
k
9
)
.
Note that we used ⋯ in order to avoid writing further terms of the Taylor expansions due to symbolic computations. By using (5) and (7), we obtain
(8)
f
[
x
k
,
w
k
]
=
f
′
(
α
)
(
(
3
+
β
f
′
(
α
)
)
)
1
+
(
2
+
β
f
′
(
α
)
)
)
c
2
e
k
ssssss
+
f
′
(
α
)
(
(
3
+
β
f
′
(
α
)
)
)
β
f
′
(
α
)
c
2
2
+
(
(
3
+
β
f
′
(
α
)
)
)
3
+
β
f
′
(
α
)
ssssssss
×
(
3
+
β
f
′
(
α
)
)
)
c
3
)
e
k
2
+
⋯
+
O
(
e
k
8
)
.
Dividing (5) by (8) gives us
(9)
f
(
x
k
)
f
[
x
k
,
w
k
]
=
e
k
-
(
1
+
β
f
′
(
α
)
)
c
2
e
k
2
+
(
(
2
+
β
f
′
(
α
)
(
2
+
β
f
′
(
α
)
)
)
c
2
2
s
-
(
1
+
β
f
′
(
α
)
)
(
2
+
β
f
′
(
α
)
)
c
3
(
2
+
β
f
′
(
α
)
(
2
+
β
f
′
(
α
)
)
)
)
e
k
3
+
⋯
+
O
(
e
k
9
)
.
And thus,
(10)
e
k
,
y
=
-
(
1
+
β
f
′
(
α
)
)
2
c
2
c
3
e
k
4
+
⋯
+
O
(
e
k
9
)
.
Subsequently, we have
(11)
f
[
y
k
,
w
k
]
=
f
′
(
α
)
+
f
′
(
α
)
(
1
+
β
f
′
(
α
)
)
c
2
e
k
+
f
′
(
α
)
(
(
β
f
′
(
α
)
)
2

(
1
+
2
β
f
′
(
α
)
)
c
2
2
ssssssssss
+
(
1
+
β
f
′
(
α
)
)
2
c
3
)
e
k
2
+
⋯
+
O
(
e
k
8
)
.
Thus,
(12)
h
(
u
k
,
v
k
)
f
(
y
k
)
f
[
y
k
,
w
k
]
=
(
1
+
β
f
′
(
α
)
)
c
2
e
k
2
+
(
-
(
2
+
β
f
′
(
α
)
(
2
+
β
f
′
(
α
)
)
)
c
2
2
s
+
(
1
+
β
f
′
(
α
)
)
(
2
+
β
f
′
(
α
)
)
c
3
(
2
+
β
f
′
(
α
)
(
2
+
β
f
′
(
α
)
)
)
)
×
e
k
3
+
⋯
+
O
(
e
k
9
)
,
f
[
w
k
,
y
k
,
z
k
]
=
f
′
(
α
)
c
2
+
f
′
(
α
)
(
1
+
β
f
′
(
α
)
)
c
3
e
k
+
f
′
(
α
)
(
(
β
f
′
(
α
)
)
2
(
1
+
2
β
f
′
(
α
)
)
c
2
c
3
+
(
1
+
β
f
′
(
α
)
)
2
c
4
)
e
k
2
+
⋯
+
O
(
e
k
9
)
.
Therefore, we attain
(13)
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
=
-
(
1
+
β
f
′
(
α
)
)
2
c
2
c
3
e
k
4
+
⋯
+
O
(
e
k
9
)
.
Finally, according to the above analysis, the general error equation is given by
(14)
e
k
+
1
=
e
k
,
z
-
W
(
s
k
)
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
=
(
1
+
β
f
′
(
α
)
)
4
c
2
2
c
3
×
(
(
9
+
β
f
′
(
α
)
(
7
+
β
f
′
(
α
)
)
)
c
2
3
s
+
2
c
2
c
3
-
c
4
(
9
+
β
f
′
(
α
)
(
7
+
β
f
′
(
α
)
)
)
)
e
k
8
+
O
(
e
k
9
)
,
so that the proof of the theorem is finished.We provide some specific weight functions that satisfy the conditions of Theorem1 as follows:
(15)
H
1
(
u
k
,
v
k
)
=
1
+
u
k
+
2
u
k
v
k
+
u
k
2
,
H
2
(
u
k
,
v
k
)
=
1
1
-
u
k
-
2
u
k
v
k
,
W
1
(
s
k
)
=
cos
⁡
⁡
(
s
k
)
+
sin
⁡
(
s
k
)
,
W
2
(
s
k
)
=
1
1
-
s
k
,
W
3
(
s
k
)
=
1
+
s
k
,
W
4
(
s
k
)
=
e
s
k
.We consider these weight functions in, without and with memory methods, (3) and (18) in the forthcoming sections.There are some measures for comparing various iterative techniques. Traub [1] introduced the informational efficiency and efficiency index, which can be expressed in terms of the order (r) of the method and the number of function (and derivative) evaluations (ρ). In fact, the efficiency index (or computational efficiency) is given by E
=
r
1
/
ρ.Clearly, the efficiency index of the proposed optimal class of method is8
1
/
4
≈
1.682 which is optimal in the sense of K-T hypothesis and is higher than two- or one-step methods without memory.It is worth emphasizing that the maximal order of convergence is not the only goal in constructing root-finding methods and, consequently, the ultimate measure of efficiency of the designed method. Complexity of the formulae involved, often called combinatorial cost, makes another important parameter, which should be taken into account. Hence, we wish to construct a new method with memory possessing a high order 12 requiring only 4 functional evaluations (just like (3)).In the next section, we will modify the proposed method and introduce a new method. We use an accelerator parameter to increase the order of convergence significantly.


## 3. Construction of a Method with Memory

Error equation (14) indicates that the order of convergence for class (3) is equal to eight. This section is concerned with extracting an efficiency with memory method from (3) since its error equation contains the parameter β which can be approximated in such a way that increases the local order of convergence.We setβ
=
β
k as the iteration proceeds by the formula β
k
=
-
1
/
f
′
¯
(
α
) for k
=
1,2
,
…, where f
′
¯
(
α
) is an approximation of f
′
(
α
). We have a method via the following forms of β
k:
(16)
β
k
=
-
1
f
′
¯
(
α
)
=
-
1
N
4
′
(
x
k
)
.The key idea that provides the order acceleration lies in a special form of the error relation and a convenient choice of a free parameter. We define a self-accelerating parameter, which is calculated during the iterative process using Newton’s interpolating polynomial.Hence, we consider Newton’s interpolation as the method for approximatingf
′
(
α
), where N
4
(
t
) is Newton’s interpolation polynomial of fourth degree, set through five available approximations x
k
,
z
k
-
1
,
y
k
-
1
,
w
k
-
1
,
x
k
-
1 as follows:
(17)
N
4
′
(
x
k
)
=
[
d
d
t
N
4
(
t
)
]
t
=
x
k
=
[
d
d
t
(
f
(
x
k
)
+
f
[
x
k
,
z
k
-
1
]
(
t
-
x
k
)
ssssss
+
f
[
x
k
,
z
k
-
1
,
y
k
-
1
]
(
t
-
x
k
)
ssssss

×

(
t
-
z
k
-
1
)

+

f
[
x
k
,
z
k
-
1
,
y
k
-
1
,
x
k
-
1
]
(
t
-
x
k
)
ssssss
×
(
t
-
z
k
-
1
)
(
t
-
y
k
-
1
)
ssssss
+
f
[
x
k
,
z
k
-
1
,
y
k
-
1
,
x
k
-
1
,
w
k
-
1
]
ssssss
×
(
t
-
x
k
)
(
t
-
z
k
-
1
)
(
t
-
y
k
-
1
)
ssssss
×
(
t
-
x
k
-
1
)
)
d
d
t
]
t
=
x
k
=
f
[
x
k
,
z
k
-
1
]
+
f
[
x
k
,
z
k
-
1
,
y
k
-
1
]
(
x
k
-
z
k
-
1
)
+
f
[
x
k
,
z
k
-
1
,
y
k
-
1
,
x
k
-
1
]
(
x
k
-
z
k
-
1
)
(
x
k
-
y
k
-
1
)
+
f
[
x
k
,
z
k
-
1
,
y
k
-
1
,
x
k
-
1
,
w
k
-
1
]
(
x
k
-
z
k
-
1
)
×
(
x
k
-
y
k
-
1
)
(
x
k
-
x
k
-
1
)
.Here, the with memory development of (3) can be presented as follows:
(18)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
H
(
u
k
,
v
k
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hhhhhhhhhhhhhhhhhihhhihhhh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
W
(
s
k
)
hh
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
hhhhhhhhhhhhhhhhhhhiih
s
k
=
f
(
z
k
)
f
(
x
k
)
.We attempt to prove that the method with memory (18) has convergence order twelve provided that we use accelerator β
k as in (16). It should be remarked that we have applied the Herzberger’s matrix method [7].Theorem 2.
If an initial approximationx
0 is sufficiently close to the zero α of f
(
x
) and the parameter β
k in the iterative scheme (18) is recursively calculated by the forms given in (16), then the order of convergence is twelve.Proof.
We will use Herzberger’s matrix method to determine the order of convergence. Note that the lower bound of order for a single-steps-point method x
k
=
G
(
x
k
-
1
,
x
k
-
2
,
…
,
x
k
-
s
) is the spectral radius of a matrix M
(
s
)
=
(
m
i
j
), associated to the method with elements:
(19)
m
1
,
j
=
amount
of
information
required
at
point
x
k
-
j
hhhhhhhhhhhhhhhhhhhhhhhhhhhhh
j
=
1,2
,
…
,
s
,
m
i
,
i
-
1
=
1
(
i
=
2,3
,
…
,
s
)
,
m
i
,
j
=
0
,
otherwise
.
On the other hand, the lower bound of order of ans-step method G
=
G
1
∘
G
2
∘
⋯
∘
G
s is the spectral radius of the product of matrices M
=
M
1
·
M
2
⋯
M
s.
We can express each approximationx
k
+
1, z
k, y
k, and w
k as a function of available information f
(
z
k
), f
(
y
k
), f
(
w
k
), and f
(
x
k
) from the kth iteration and f
(
z
k
-
1
), f
(
y
k
-
1
), f
(
w
k
-
1
), and f
(
x
k
-
1
) from the previous iteration, depending on the accelerating technique. Now, we determine the order of convergence for (18) applied for the calculation of β
k.
Method (N4). We use the following matrices to express informational dependence:
(20)
x
k
+
1
=
φ
1
(
z
k
,
y
k
,
w
k
,
x
k
,
z
k
-
1
)
⟶
M
1
=
[
1
1
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
]
,
z
k
=
φ
2
(
y
k
,
w
k
,
x
k
,
z
k
-
1
,
y
k
-
1
)
⟶
M
2
=
[
1
1
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
]
,
y
k
=
φ
3
(
w
k
,
x
k
,
z
k
-
1
,
y
k
-
1
,
w
k
-
1
)
⟶
M
3
=
[
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
]
,
w
k

=

φ
4
(
x
k
,
z
k
-
1
,
y
k
-
1
,
w
k
-
1
,
x
k
-
1
)
⟶
M
4

=

[
1
1
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
]
.
Hence, it is easy to derive(21)
M
(
N
4
)
=
M
1
M
2
M
3
M
4
=
[
8
4
4
4
4
4
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
0
0
0
0
]
,
with the eigenvalues {
12,0
,
0,0
,
0
}. Consequently, the order of the method with memory (18)-(N4) is at least twelve. The proof of Theorem 2 is finished.Clearly, the proposed with memory scheme possesses a high computational efficiency index1
2
1
/
4
≈
1.861, which makes it interesting for practical problems.


## 4. Numerical Examples

In this section, we test our proposed methods and compare their results with some other methods of the same order of convergence. The errors|
x
k
-
α
| denote approximations to the sought zeros, and a
(
-
b
) stands for a
×
1
0
-
b. Moreover, coc indicates computational order of convergence and is computed by
(22)
coc
=
log
⁡
(
|
f
(
x
k
)
/
f
(
x
k
-
1
)
|
)
log
⁡
(
|
f
(
x
k
-
1
)
/
f
(
x
k
-
2
)
|
)
.The calculated value coc estimates the theoretical order of convergence well when “pathological behavior” of the iterative method (for instance, slow convergence at the beginning of the implemented iterative method, “oscillating” behavior of approximations, etc.) does not exist.We have used 1000-fixed floating point arithmetic so as to minimize the effect of round-off errors.By using weight functions (15), we introduce some concrete methods based on the proposed class. Note that it is assumed that the initial estimate β
0 should be chosen before starting the iterative process and also x
0 is given suitably.Concrete method 1:(23)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
+
u
k
+
2
u
k
v
k
+
u
k
2
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hhhhhhhhihh
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
cos
⁡
(
s
k
)
+
sin
(
s
k
)
)
hh
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhhh
s
k
=
f
(
z
k
)
f
(
x
k
)
.Concrete method 2:(24)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
+
u
k
+
2
u
k
v
k
+
u
k
2
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hhhhhhhhhhi
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
1
1
-
s
k
)
hh
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhhih
s
k
=
f
(
z
k
)
f
(
x
k
)
.Concrete method 3:(25)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
+
u
k
+
2
u
k
v
k
+
u
k
2
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hhhhhhhhhhi
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
1
+
s
k
)
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhhi
s
k
=
f
(
z
k
)
f
(
x
k
)
.Concrete method 4:(26)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
+
u
k
+
2
u
k
v
k
+
u
k
2
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hhhhhhhhhhi
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
e
s
k
)
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhhii
s
k
=
f
(
z
k
)
f
(
x
k
)
.Concrete method 5:(27)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
1
-
u
k
-
2
u
k
v
k
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hhhhhhiih
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
cos
⁡
(
s
k
)
+
sin
(
s
k
)
)
hh
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
hhhhhhhhhhhhhhhhhhhhh
s
k
=
f
(
z
k
)
f
(
x
k
)
.Concrete method 6:(28)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
1
-
u
k
-
2
u
k
v
k
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hhhhhhhhi
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
1
1
-
s
k
)
h
h
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhhi
w
k
=
f
(
z
k
)
f
(
x
k
)
.Concrete method 7:(29)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
1
-
u
k
-
2
u
k
v
k
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hihhhhhhh
u
k
=
f
(
y
k
)
f
(
x
k
)
,
h
h
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
1
+
s
k
)
hh
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhhh
w
k
=
f
(
z
k
)
f
(
x
k
)
.Concrete method 8:(30)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
k
f
(
x
k
)
,
z
k
=
y
k
-
(
1
1
-
u
k
-
2
u
k
v
k
)
f
(
y
k
)
f
[
y
k
,
w
k
]
,
hhhhhhhh
u
k
=
f
(
y
k
)
f
(
x
k
)
,
hh
v
k
=
f
(
y
k
)
f
(
w
k
)
,
x
k
+
1
=
z
k
-
(
e
s
k
)
h
h
×
f
(
z
k
)
f
[
z
k
,
y
k
]
+
f
[
w
k
,
y
k
,
z
k
]
(
z
k
-
y
k
)
,
hhhhhhhhhhhhhhhhhhhih
w
k
=
f
(
z
k
)
f
(
x
k
)
.Several iterative methods (IM) of optimal order eight, which also require four function evaluations, for comparisons with our proposed methods have been chosen.Three-step method by Wang et al. [8]:
(31)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
f
(
x
k
)
,
z
k
=
y
k
-
f
(
y
k
)
f
[
y
k
,
w
k
]
H
(
t
k
)
,
t
k
=
f
(
y
k
)
f
(
x
k
)
,
x
k
+
1
=
z
k
-
f
(
z
k
)
f
[
z
k
,
w
k
]
G
(
t
k
,
s
k
)
,
s
k
=
f
(
z
k
)
f
(
y
k
)
,where functionsH and G are following H
1
(
t
)
=
1
+
t, G
1
(
t
,
s
)
=
1
+
t
+
s
+
2
t
s
-
(
1
+
λ
)
t
3, and  λ
=
1
/
(
1
+
β
f
[
x
,
w
]
).Three-step method by Lotfi and Tavakoli [9]:
(32)
y
n
=
x
n
-
f
(
x
n
)
f
[
x
n
,
w
n
]
,
z
n
=
y
n
-
H
(
t
n
,
u
n
)
f
(
y
n
)
f
[
y
n
,
w
n
]
,
hh
t
n
=
f
(
y
)
f
(
x
)
,
hhhhhhhhhhhhhhhhhhhhhhhhh
u
n
=
f
(
w
)
f
(
x
)
,
x
k
+
1
=
z
n
-
G
(
t
n
,
s
n
)
W
(
v
n
,
s
n
)
f
(
z
n
)
f
[
z
n
,
w
n
]
,
hhhhhhhhhhhhh
s
n
=
f
(
z
)
f
(
y
)
,
hh
v
n
=
f
(
z
)
f
(
x
)
,where(33)
W
(
s
n
,
v
n
)
=
1
+
s
n
2
+
v
n
2
,
G
(
t
n
,
s
n
)
=
1
+
t
n
+
s
n
+
2
t
n
s
n
+
(
-
1
-
ϕ
n
)
t
n
3
,
hhihhhhhhihhhh
(
ϕ
n
=
1
1
+
β
n
f
[
x
n
,
w
n
]
)
,
H
(
t
n
,
u
n
)
=
1
+
t
n
.Derivative-free Kung-Traub’s family [2]:
(34)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
f
(
x
k
)
,
z
k
=
y
k
-
f
(
y
k
)
f
(
w
k
)
[
f
(
w
k
)
-
f
(
y
k
)
]
f
[
x
k
,
y
k
]
,
x
k
+
1
=
z
k
-
f
(
y
k
)
f
(
w
k
)
(
y
k
-
x
k
+
f
(
x
k
)
/
f
[
x
k
,
z
k
]
)
[
f
(
y
k
)
-
f
(
z
k
)
]
[
f
(
w
k
)
-
f
(
z
k
)
]
+
f
(
y
k
)
f
[
y
k
,
z
k
]
.Three-step methods made by Zheng et al. [10]:
(35)
y
k
=
x
k
-
f
(
x
k
)
f
[
x
k
,
w
k
]
,
w
k
=
x
k
+
β
f
(
x
k
)
,
z
k
=
y
k
-
f
(
y
k
)
f
[
y
k
,
w
k
]
+
f
[
y
k
,
x
k
,
w
k
]
(
y
k
-
x
k
)
,
x
k
+
1
=
z
k
-
(
(
z
k
-
x
k
)
)
-
1
f
(
z
k
)
×
(
(
z
k
-
x
k
)
f
[
z
k
,
y
k
]
+
f
[
z
k
,
y
k
,
x
k
]
(
z
k
-
y
k
)
+
f
[
z
k
,
y
k
,
x
k
,
w
k
]
(
z
k
-
y
k
)
×
(
z
k
-
x
k
)
)
-
1
)
.In Tables1, 3, and 5 our without memory proposed method by different weight functions (23)–(30) has been compared with optimal three-point methods (34) and (35), and we observe that all these methods behave very well practically and confirm their theoretical results.Table 1
Considerf
1
(
x
)
=
sin
⁡
⁡
(
π
x
)
e
(
x
2
+
x
cos
⁡
(
x
)
-
1
)
+
x
log
⁡
(
x
sin
⁡
⁡
(
x
)
+
1
), α
=
0, x
0
=
0.6, β
=
-
0.01.
Methods without memory
|
x
1
-
α
|
|
x
2
-
α
|
|
x
3
-
α
|
coc
Our method (23)
5.3810
(
-
3
)
5.5392
(
-
25
)
6.9091
(
-
201
)
8.0003
Our method (24)
2.1802
(
-
3
)
3.9973
(
-
28
)
5.0816
(
-
226
)
8.0001
Our method (25)
4.2865
(
-
3
)
8.9612
(
-
26
)
3.2420
(
-
207
)
8.0002
Our method (26)
3.1912
(
-
3
)
8.4384
(
-
27
)
2.0042
(
-
215
)
8.0002
Our method (27)
5.7030
(
-
3
)
4.9625
(
-
25
)
1.6203
(
-
201
)
8.0002
Our method (28)
2.3293
(
-
3
)
3.8278
(
-
28
)
2.0304
(
-
226
)
8.0001
Our method (29)
5.7030
(
-
3
)
4.9625
(
-
25
)
1.6203
(
-
201
)
8.0002
Our method (30)
4.5488
(
-
3
)
8.1186
(
-
26
)
8.3149
(
-
208
)
8.0002
(34), β
=
-
0.01
9.7732
(
-
3
)
4.3543
(
-
24
)
6.6317
(
-
195
)
8.0002
(35), β
=
-
0.01
1.7342
(
-
2
)
1.1724
(
-
21
)
3.5692
(
-
175
)
8.0085Also Tables2, 4, and 6 present numerical results for our with memory classes (23)–(30). It is also clear that all these methods behave very well practically and confirm their relevant theories. They all provide wherea bout twelve of convergence order.Table 2
Considerf
1
(
x
)
=
sin
⁡
⁡
(
π
x
)
e
(
x
2
+
x
cos
⁡
(
x
)
-
1
)
+
x
log
⁡
(
x
sin
⁡
⁡
(
x
)
+
1
), α
=
0, x
0
=
0.6, β
0
=
-
0.01.
Methods with memory
|
x
1
-
α
|
|
x
2
-
α
|
|
x
3
-
α
|
coc
Our method (23)
5.3810
(
-
3
)
2.7788
(
-
35
)
1.8668
(
-
426
)
12.1156
Our method (24)
2.1802
(
-
3
)
3.0336
(
-
38
)
5.3469
(
-
462
)
12.1571
Our method (25)
4.2865
(
-
3
)
5.2041
(
-
36
)
3.4739
(
-
435
)
12.1273
Our method (26)
3.1912
(
-
3
)
5.6445
(
-
37
)
9.2065
(
-
447
)
12.1411
Our method (27)
5.7030
(
-
3
)
4.6138
(
-
35
)
8.1591
(
-
424
)
12.1138
Our method (28)
2.3293
(
-
3
)
5.4580
(
-
38
)
6.1228
(
-
459
)
12.1556
Our method (29)
4.5488
(
-
3
)
8.7828
(
-
36
)
1.8467
(
-
432
)
12.1256
Our method (30)
3.3939
(
-
3
)
9.7470
(
-
37
)
6.4438
(
-
444
)
12.1395
(31), β
=
-
1
2.1170
(
-
3
)
1.1077
(
-
41
)
3.4407
(
-
501
)
12.0035
(32), β
=
-
1
5.7578
(
-
3
)
2.7125
(
-
39
)
1.4859
(
-
474
)
11.9819Table 3
Considerf
2
(
x
)
=
e
-
5
x
(
x
-
2
)
(
x
10
+
x
+
2
)
,
α
=
2
,
x
0
=
2.2
,
β
=
-
1.
Methods without memory
|
x
1
-
α
|
|
x
2
-
α
|
|
x
3
-
α
|
coc
Our method (23)
5.4211
(
-
6
)
7.6321
(
-
54
)
1.1776
(
-
436
)
8.0000
Our method (24)
5.4981
(
-
6
)
8.5429
(
-
54
)
2.9020
(
-
436
)
8.0000
Our method (25)
5.4468
(
-
6
)
7.9261
(
-
54
)
1.5935
(
-
436
)
8.0001
Our method (26)
5.4725
(
-
6
)
8.2301
(
-
54
)
2.1533
(
-
436
)
8.0000
Our method (27)
3.2606
(
-
6
)
1.3070
(
-
55
)
8.7125
(
-
451
)
8.0000
Our method (28)
3.3757
(
-
6
)
1.7249
(
-
55
)
8.0153
(
-
450
)
8.0000
Our method (29)
3.2991
(
-
6
)
1.4354
(
-
55
)
1.8434
(
-
450
)
8.0000
Our method (30)
3.3375
(
-
6
)
1.5747
(
-
55
)
3.8666
(
-
450
)
8.0000
(34), β
=
-
1
8.0552
(
-
6
)
1.4131
(
-
52
)
1.2677
(
-
456
)
8.0000
(35), β
=
-
0.01
3.9453
(
-
6
)
1.2705
(
-
59
)
5.0021
(
-
491
)
8.0085Table 4
Considerf
2
(
x
)
=
e
-
5
x
(
x
-
2
)
(
x
10
+
x
+
2
)
,
α
=
2
,
x
0
=
2.2
,
β
0
=
-
1.
Methods with memory
|
x
1
-
α
|
|
x
2
-
α
|
|
x
3
-
α
|
coc
Our method (23)
5.4211
(
-
6
)
2.1857
(
-
80
)
4.4911
(
-
970
)
11.9590
Our method (24)
5.4981
(
-
6
)
2.4529
(
-
80
)
1.7931
(
-
969
)
11.9587
Our method (25)
5.4468
(
-
6
)
2.2719
(
-
80
)
7.1443
(
-
970
)
11.9589
Our method (26)
5.4725
(
-
6
)
2.3611
(
-
80
)
9.2065
(
-
969
)
11.9588
Our method (27)
5.4981
(
-
6
)
2.4529
(
-
80
)
1.7931
(
-
969
)
11.9587
Our method (28)
3.3757
(
-
6
)
7.7624
(
-
82
)
1.8084
(
-
987
)
11.9732
Our method (29)
3.2991
(
-
6
)
6.4445
(
-
82
)
1.9393
(
-
988
)
11.9737
Our method (30)
3.3375
(
-
6
)
7.0781
(
-
82
)
5.9748
(
-
988
)
11.9735
(31), β
=
-
1
4.9425
(
-
5
)
1.5275
(
-
69
)
4.1256
(
-
874
)
12.0535
(32), β
=
-
1
4.0518
(
-
6
)
8.2730
(
-
77
)
2.4267
(
-
861
)
11.0982Table 5
Considerf
3
(
x
)
=
e
x
3
-
x
-
cos
⁡
(
x
2
-
1
)
+
x
3
+
1
,
α
=
-
1
,
x
0
=
-
1.65
,
β
=
-
1.
Methods without memory
|
x
1
-
α
|
|
x
2
-
α
|
|
x
3
-
α
|
coc
Our method (23)
6.0256
(
-
3
)
4.0898
(
-
24
)
1.8272
(
-
193
)
8.0001
Our method (24)
5.9797
(
-
3
)
3.8471
(
-
24
)
1.1202
(
-
193
)
8.0001
Our method (25)
6.0104
(
-
3
)
4.0081
(
-
24
)
1.5548
(
-
193
)
8.0001
Our method (26)
5.9952
(
-
3
)
3.9278
(
-
24
)
1.3225
(
-
193
)
8.0001
Our method (27)
5.3628
(
-
3
)
1.6071
(
-
24
)
1.0388
(
-
196
)
8.0001
Our method (28)
5.3357
(
-
3
)
1.5431
(
-
24
)
7.5042
(
-
197
)
8.0001
Our method (29)
5.3537
(
-
3
)
1.5856
(
-
24
)
9.3292
(
-
197
)
8.0001
Our method (30)
5.3448
(
-
3
)
1.5644
(
-
24
)
8.3766
(
-
197
)
8.0001
(34), β
=
-
1
2.9152
(
-
4
)
5.3239
(
-
34
)
6.5827
(
-
272
)
8.0000
(35), β
=
-
0.01
6.4036
(
-
5
)
4.4335
(
-
44
)
2.4457
(
-
357
)
7.9995Table 6
Considerf
3
(
x
)
=
e
x
3
-
x
-
cos
⁡
(
x
2
-
1
)
+
x
3
+
1
,
α
=
-
1
,
x
0
=
-
1.65
,
β
0
=
-
1.
Methods with memory
|
x
1
-
α
|
|
x
2
-
α
|
|
x
3
-
α
|
coc
Our method (23)
6.0256
(
-
3
)
4.7294
(
-
38
)
3.8067
(
-
459
)
11.9952
Our method (24)
5.9797
(
-
3
)
4.4345
(
-
38
)
1.7580
(
-
459
)
11.9955
Our method (25)
6.0104
(
-
3
)
4.6300
(
-
38
)
2.9502
(
-
459
)
11.9953
Our method (26)
5.9959
(
-
3
)
4.5324
(
-
38
)
2.2850
(
-
459
)
11.9954
Our method (27)
5.3628
(
-
3
)
9.5497
(
-
39
)
1.7425
(
-
467
)
11.9929
Our method (28)
5.3357
(
-
3
)
9.1483
(
-
39
)
1.0410
(
-
467
)
11.9931
Our method (29)
5.3538
(
-
3
)
9.4151
(
-
39
)
1.4696
(
-
467
)
11.9929
Our method (30)
5.3448
(
-
3
)
9.2821
(
-
39
)
1.2391
(
-
467
)
11.9930
(31), β
=
-
1
1.3000
(
-
2
)
5.5214
(
-
33
)
1.2114
(
-
401
)
12.1381
(32), β
=
-
1
1.0937
(
-
2
)
3.5221
(
-
34
)
1.7174
(
-
415
)
12.1081


## 5. Concluding Remarks

We have constructed a class of methods without and with memory. Our proposed methods do not need any derivative and therefore are applicable to nonsmooth functions too. Another advantage of the proposed methods is that their without memory versions are optimal in the sense of K-T conjecture. In addition, it contains an accelerator parameter which rises convergence order from eight to twelve without any new functional evaluations. In other words, the efficiency index of the with memory class is1
2
1
/
4
≈
1.861.We finalize this work by suggesting some outlines for future research: first developing the proposed methods for computing multiple roots and second exploring its dynamic or basins of attractions, and finally we wonder why not to use an adaptive arithmetic in each step of the iterative method instead of using a fixed precision, since this higher precision is only necessary in the last step of the iterative process.



---

*Source: 134673-2014-09-03.xml*