# Solving Nondifferentiable Nonlinear Equations by New Steffensen-Type Iterative Methods with Memory

Authors: J. P. Jaiswal
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

It is attempted to present two derivative-free Steffensen-type methods with memory for solving nonlinear equations. By making use of a suitable self-accelerator parameter in the existing optimal fourth- and eighth-order without memory methods, the order of convergence has been increased without any extra function evaluation. Therefore, its efficiency index is also increased, which is the main contribution of this paper. The self-accelerator parameters are estimated using Newton’s interpolation. To show applicability of the proposed methods, some numerical illustrations are presented.


---

## Body

## 1. Introduction

Finding the root of a nonlinear equation frequently occurs in scientific computation. Newton’s method is the most well-known method for solving nonlinear equations and has quadratic convergence. However, the existence of the derivative in the neighborhood of the required root is compulsory for convergence of Newton’s method, which restricts its applications in practice. To overcome this difficulty, Steffensen replaced the first derivative of the function in Newton’s iterate by forward finite difference approximation. This method also possesses the quadratic convergence and the same efficiency just like Newton’s method. Some nice applications of iterative methods can be found in the literature; one can see [1–8].Kung and Traub are pioneers in constructing optimal general multistep methods without memory. They discussed two generaln-step methods based on interpolation. Moreover, they conjectured that any multistep method without memory using n function evaluations may reach the convergence order at most 2
n
-
1 [9]. Thus, both Newton’s and Steffensen’s methods are optimal in the sense of Kung and Traub. But the superiority of Steffensen’s method over Newton’s method is that it is derivative-free. So, it can be applied to nondifferentiable equations also. To compare iterative methods theoretically, Owtrowski [10] introduced the idea of efficiency index given by r
1
/
θ
f, where r is the order of convergence and θ
f is the number of function evaluations per iteration. In other words, we can say that an iterative method with higher efficiency index is more efficient. To improve convergence order as well as efficiency index without any new function evaluations, Traub in his book introduced the method with memory. In fact, he changed Steffensen’s method slightly as follows (see [11, pp. 185–187]): x
0, γ
0 are given suitably
(1)
γ
k
=
-
x
k
-
x
k
-
1
f
x
k
-
f
x
k
-
1
for
k
≥
1
,
x
k
+
1
=
x
k
-
γ
k
f
x
k
2
f
x
k
+
γ
k
f
x
k
-
f
x
k
,
k
=
0,1
,
2
,
…
.
The parameter γ
n is called self-accelerator and method (1) has R-order convergence 2.414. The possibility to increase the convergence order cannot be denied by using more suitable parameters. Many authors during the last few years tried to construct iterative methods without memory which support this conjecture with optimal order; one can see [12–21] and many more. Although construction of optimal methods without memory is still an active field, the authors are shifting their attentions to develop more efficient methods with memory since the last year; for example, see [22–25].In the convergence analysis of the new method, we employ the notation used in Traub’s book [11]: if m
k and n
k are null sequences and m
k
/
n
k
→
C, where C is a nonzero constant, we will write m
k
=
O
(
n
k
) or m
k
~
C
n
k. We also use the concept of R-order of convergence introduced by Ortega and Rheinboldt [5]. Let x
k be a sequence of approximations generated by an iterative method (IM). If this sequence converges to a zero ξ of function f with the R-order O
R
(
(
IM
)
,
ξ
)
≥
α, we will write
(2)
e
k
+
1
~
D
k
,
α
e
k
α
,
where D
k
,
α tends to the asymptotic error constant D
α of the iterative method (IM) when k
→
∞.The rest of the paper is organized as follows. In Section2, we describe the existing two- and three-point Steffensen-type iterative schemes and then their convergence orders are accelerated from four to six and from eight to twelve, respectively, without any extra evaluation. The proposed methods are obtained by using previous values as well as a suitable parameter. The parameter is calculated using Newton’s interpolations. The numerical study was also presented in the next section to confirm the theoretical results. Finally, we give the concluding remarks.


## 2. Development and Construction with Memory

Two-step and three-step repeated Newton’s method is given by(3)
y
k
=
x
k
-
f
x
k
f
′
x
k
,
x
k
+
1
=
y
k
-
f
y
k
f
′
y
k
,
(4)
y
k
=
x
k
-
f
x
k
f
′
x
k
,
u
k
=
y
k
-
f
y
k
f
′
y
k
,
x
k
+
1
=
u
k
-
f
u
k
f
′
u
k
.
The order of convergence of the methods (3) and (4) is four and eight, respectively. By repeating in the same way, one can get more higher-order methods. Definitely these methods have higher convergence order as compared to the standard Newton’s method. But there is no improvement in its efficiency index. For example, the efficiency indexes of the above two methods are 4
1
/
4
=
1.4142 and 8
1
/
6
=
1.4142, which are the same as the efficiency index of the original Newton’s method 2
1
/
2
=
1.4142. To improve the efficiency index, Cordero et al. in [26] have reduced the number of function evaluations by approximating the derivatives in terms of functions. For this first, they have approximated the derivatives f
′
(
x
k
) by forward difference given by
(5)
f
′
x
k
≈
f
x
k
+
f
x
k
-
f
x
k
f
x
k
.
Then, to approximate the other two derivatives, they used rational approximation. In fact, f
′
(
y
k
) is approximated by the rational approximation of the first degree and f
′
(
u
k
) is approximated by the rational approximation of the second degree and they derived that
(6)
f
′
y
k
≈
f
x
k
,
y
n
f
y
k
,
z
k
f
x
k
,
z
k
,
f
′
u
k
≈
b
2
-
b
1
b
4
,
where
(7)
b
4
=
f
[
y
k
,
u
k
,
x
k
]
-
f
y
k
,
u
k
,
z
k
f
[
y
k
,
z
k
]
-
f
y
k
,
x
k
,
b
3
=
f
y
k
,
u
k
,
z
k
+
b
4
f
y
k
,
z
k
,
b
2
=
f
y
k
,
u
k
-
b
3
y
k
-
u
+
f
y
k
b
4
,
b
1
=
f
u
k
,
z
k
=
x
k
+
f
x
k
.
By using these approximations of the derivatives in (3) and (4), they have shown that their methods have the same order of convergence but with reduced number of function evaluations and thus efficiency index has been increased. In fact, the efficiency index becomes 4
1
/
3
=
1.5874 and 8
1
/
4
=
1.6818, respectively. For more detail, one can see [26]. One more advantage of these methods is that it can be applied to nonsmooth functions also. Now one natural question arises:is it possible to find more efficient methods? Main aim of our paper is to find the answer of this question.For this purpose, we first introduce a nonzero real parameter inz
n and consider the following two methods with its error expression.Method I. For the suitably given x
0,
(8)
z
k
=
x
k
+
p
f
x
k
,
k
=
0,1
,
2
,
…
,
y
k
=
x
k
-
f
x
k
f
x
k
,
z
k
,
x
k
+
1
=
y
k
-
f
y
k
f
x
k
,
z
k
f
x
k
,
y
k
f
y
k
,
z
k
,
and its error expression is given by
(9)
e
k
+
1
=
1
+
p
c
1
2
c
2
2
c
2
2
-
c
1
c
3
c
1
3
e
k
4
+
O
e
k
5
.Method II. For the suitably given x
0,
(10)
z
k
=
x
k
+
q
f
x
k
,
k
=
0,1
,
2
,
…
,
y
k
=
x
k
-
f
x
k
f
x
k
,
z
k
,
u
k
=
y
k
-
f
y
k
f
x
k
,
z
k
f
x
k
,
y
k
f
y
k
,
z
k
,
x
k
+
1
=
u
k
-
f
u
k
b
2
-
b
1
b
4
,
and its error expression is given by
(11)
e
k
+
1
=
1
+
q
c
1
4
c
2
2
c
2
2
-
c
1
c
3
2
c
2
4
-
c
1
c
2
2
c
3
-
c
1
2
c
3
2
+
c
1
2
c
2
c
4
c
1
7
×
e
k
8
+
O
e
k
9
,
where b
1, b
2, b
3, and b
4 are defined as in (7) and c
i
=
f
(
i
)
(
ξ
)
/
i
!.Now we are concerned with the extension of the above schemes in methods with memory, since its error equations contain the parameter which can be approximated in such a way that it increases the local order convergence. For this purpose, we putp
=
p
k and q
=
q
k, where p
k
=
-
1
/
c
1
~ and q
k
=
-
1
/
c
1
¯. Here, c
1
~ and c
1
¯ are two different approximations of c
1 and given by
(12)
c
1
~
=
N
3
′
x
k
,
(13)
c
1
¯
=
N
4
′
x
k
,
where
(14)
N
3
′
x
k
=
d
d
t
N
3
t
x
=
x
k
=
d
d
t
N
3
t
;
x
k
,
y
k
-
1
,
x
k
-
1
,
z
k
-
1
x
=
x
k
=
d
d
t
f
x
k
+
f
x
k
,
y
k
-
1
t
-
x
k
+
f
x
k
,
y
k
-
1
,
x
k
-
1
t
-
x
k
t
-
y
k
-
1
+
f
x
k
,
y
k
-
1
,
x
k
-
1
,
z
k
-
1
t
-
x
k
×
t
-
y
k
-
1
t
-
x
k
-
1
d
d
t

x
=
x
k
=
f
x
k
,
y
k
-
1
+
f
x
k
,
y
k
-
1
,
x
k
-
1
x
k
-
y
k
-
1
+
f
x
k
,
y
k
-
1
,
x
k
-
1
,
z
k
-
1
x
k
-
y
k
-
1
x
k
-
x
k
-
1
,
N
4
′
x
k
=
d
d
t
N
4
t
x
=
x
k
=
d
d
t
N
4
t
;
x
k
,
u
k
-
1
,
y
k
-
1
,
x
k
-
1
,
z
k
-
1
x
=
x
k
=
d
d
t
f
x
k
+
f
x
k
,
u
k
-
1
t
-
x
k
+
f
x
k
,
u
k
-
1
,
y
k
-
1
t
-
x
k
t
-
u
k
-
1
+
f
x
k
,
u
k
-
1
,
y
k
-
1
,
x
k
-
1
t
-
x
k
×
t
-
u
k
-
1
t
-
y
k
-
1
+
f
x
k
,
u
k
-
1
,
y
k
-
1
,
x
k
-
1
,
z
k
-
1
t
-
x
k
×

t
-
u
k
-
1
t
-
y
k
-
1
t
-
x
k
-
1
d
d
t

x
=
x
k
=
f
[
x
k
,
u
k
-
1
]
+
f
x
k
,
u
k
-
1
,
y
k
-
1
x
k
-
u
k
-
1
+
f
x
k
,
u
k
-
1
,
y
k
-
1
,
x
k
-
1
x
k
-
u
k
-
1
x
k
-
y
k
-
1
+
f
x
k
,
u
k
-
1
,
y
k
-
1
,
x
k
-
1
,
z
k
-
1
x
k
-
u
k
-
1
×
x
k
-
y
k
-
1
x
k
-
x
k
-
1
are Newton’s interpolatory polynomial of degrees three and four, respectively. Now, the theoretical order of convergence of the methods is given by the following theorem.Theorem 1.
If an initial approximationx
0 is sufficiently close to a simple zero ξ of f
(
x
) and the parameters p
k and q
k in the iterative scheme (8) and (10) are recursively calculated by the forms given in (12) and (13), respectively, then the R-order of convergence of methods (8) and (10) with memory is at least six and twelve, respectively.Proof.
Before going to show the main result, we first prove the following two results, which we will use later.
Claim I. Consider
(15)
1
+
p
k
c
1
~
c
4
c
1
e
k
-
1
,
y
e
k
-
1
,
z
e
k
-
1
.
Claim II. Consider
(16)
1
+
q
k
c
1
~
-
c
5
c
1
e
k
-
1
,
u
e
k
-
1
,
y
e
k
-
1
,
z
e
k
-
1
.
For this, suppose that there are s nodes t
0
,
t
1
,
…
,
t
s from the interval D
=
[
a
,
b
], where a is the minimum and b is the maximum of these nodes, respectively. Then, for some ζ
∈
D, the error expression of Newton’s interpolation polynomial N
s
(
t
) of degree s is given by
(17)
f
t
-
N
s
t
=
f
(
s
+
1
)
ζ
s
+
1
!
∏
j
=
0
s
‍
t
-
t
j
.
For s
=
3, the above equation assumes the form (keeping in the mind t
0
=
x
k, t
1
=
y
k
-
1, t
2
=
x
k
-
1, and t
3
=
z
k
-
1)
(18)
f
t
-
N
3
t
=
f
4
ζ
3
4
!
t
-
x
k
t
-
y
k
-
1
t
-
x
k
-
1
t
-
z
k
-
1
.
Differentiating (18) with respect to t and putting t
=
x
k, we get
(19)
f
′
x
k
-
N
3
′
x
k
=
f
4
ζ
3
4
!
x
k
-
y
k
-
1
x
k
-
x
k
-
1
x
k
-
z
k
-
1
.
Now,
(20)
x
k
-
y
k
-
1
=
x
k
-
ξ
-
y
k
-
1
-
ξ
=
e
k
-
e
k
-
1
,
y
.
Similarly,
(21)
x
k
-
x
k
-
1
=
e
k
-
e
k
-
1
,
x
k
-
z
k
-
1
=
e
k
-
e
k
-
1
,
z
.
Using these relations in (19) and simplifying, we get
(22)
N
3
′
x
k
~
c
1
+
2
c
2
e
k
+
c
4
e
k
-
1
,
y
e
k
-
1
,
z
e
k
-
1
.
And thus
(23)
1
+
p
k
c
1
=
1
-
c
1
N
3
′
x
k
~
1
-
c
1
c
1
+
2
c
2
e
k
+
c
4
e
k
-
1
,
y
e
k
-
1
,
z
e
k
-
1
,
or
(24)
1
+
p
k
c
1
~
c
4
c
1
e
k
-
1
,
y
e
k
-
1
,
z
e
k
-
1
,
which shows the first part. Similarly, taking s
=
4 in (17) and proceeding as in the above manner, we can prove the second relation. Now, we will prove the main result. To do this, we first assume that the R-order of convergence of sequences x
k, z
k, y
k, and u
k is at least α, α
1, α
2, and α
3, respectively. Hence,
(25)
e
k
+
1
~
D
k
,
α
e
k
α
~
D
k
,
α
D
k
-
1
,
α
e
k
-
1
α
α
~
D
k
,
α
D
k
-
1
,
r
α
e
k
-
1
α
2
.
Similarly,
(26)
e
k
,
z
~
D
k
,
α
1
D
k
-
1
,
α
α
1
e
k
-
1
α
α
1
,
(27)
e
k
,
y
~
D
k
,
α
2
D
k
-
1
,
α
α
2
e
k
-
1
α
α
2
,
(28)
e
k
,
u
~
D
k
,
α
3
D
k
-
1
,
α
α
3
e
k
-
1
α
α
3
.
Method I. For method (8), it can be derived that
(29)
e
k
,
z
~
1
+
p
k
c
1
e
k
,
e
k
,
y
~
M
1
1
+
p
k
c
1
e
k
2
,
where
M
1
=
c
2
c
1
,
e
k
+
1
~
M
2
1
+
p
k
c
1
2
e
k
4
,
where
M
2
=
c
2
2
c
2
2
-
c
1
c
3
c
1
3
.
Using the expression of Claim (I) in (29), we have
(30)
e
k
,
z
~
c
4
c
1
D
k
-
1
,
α
2
D
k
-
1
,
α
1
D
k
-
1
,
α
e
k
-
1
α
2
+
α
1
+
α
+
1
,
(31)
e
k
,
y
~
c
4
c
1
M
1
D
k
-
1
,
α
2
D
k
-
1
,
α
1
D
k
-
1
,
α
2
e
k
-
1
α
2
+
α
1
+
2
α
+
1
,
(32)
e
k
+
1
~
c
4
c
1
2
M
2
D
k
-
1
,
α
2
2
D
k
-
1
,
α
1
2
D
k
-
1
,
α
4
e
k
-
1
2
α
2
+
2
α
1
+
4
α
+
1
.
Now comparing the equal powers of e
k
-
1 in (26)–(30), (27)–(31), and (25)–(32), we get the following nonlinear system:
(33)
α
α
1
-
α
2
-
α
1
-
α
-
1
=
0
,
α
α
2
-
α
2
-
α
1
-
2
α
-
1
=
0
,
α
2
-
2
α
2
-
2
α
1
-
4
α
-
2
=
0
.
After solving these equations, we get α
=
6, α
2
=
3, and α
1
=
2, which confirm the convergence of method (8).
Method II. For method (10), it can be derived that
(34)
e
k
,
z
~
1
+
q
k
c
1
e
k
,
e
k
,
y
~
M
1
1
+
q
k
c
1
e
k
2
,
where
M
1
=
c
2
c
1
,
e
k
,
u
~
M
2
1
+
q
k
c
1
2
e
k
4
,
where
M
2
=
c
2
2
c
2
2
-
c
1
c
3
c
1
3
,
e
k
+
1
~
M
3
1
+
q
k
c
1
4
e
k
8
,
where
M
3
=
c
2
2
c
2
2
-
c
1
c
3
2
c
2
4
-
c
1
2
c
2
2
c
3
-
c
1
2
c
3
2
+
c
1
c
2
c
4
c
1
3
.
Using the expression of Claim (II) in (34), we have
(35)
e
k
,
z
~
-
c
5
c
1
D
k
-
1
,
α
3
D
k
-
1
,
α
2
D
k
-
1
,
α
1
×
D
k
-
1
,
α
e
k
-
1
α
3
+
α
2
+
α
1
+
α
+
1
,
(36)
e
k
,
y
~
-
c
5
c
1
M
1
D
k
-
1
,
α
3
D
k
-
1
,
α
2
D
k
-
1
,
α
1
×
D
k
-
1
,
α
2
e
k
-
1
α
3
+
α
2
+
α
1
+
2
α
+
1
,
(37)
e
k
,
u
~
-
c
5
c
1
2
M
2
D
k
-
1
,
α
3
2
D
k
-
1
,
α
2
2
D
k
-
1
,
α
1
2
×
D
k
-
1
,
α
4
e
k
-
1
2
α
3
+
2
α
2
+
2
α
1
+
4
α
+
1
,
(38)
e
k
+
1
~
-
c
5
c
1
4
M
3
D
k
-
1
,
α
3
4
D
k
-
1
,
α
2
4
D
k
-
1
,
α
1
4
×
D
k
-
1
,
α
8
e
k
-
1
4
α
3
+
4
α
2
+
4
α
1
+
8
α
+
1
.
Again comparing the equal powers of e
k
-
1 in (26)–(35), (27)–(36), and (28)–(37) and (25)–(38), we get the following nonlinear system:
(39)
α
α
1
-
α
3
-
α
2
-
α
1
-
α
-
1
=
0
,
α
α
2
-
α
3
-
α
2
-
α
1
-
2
α
-
1
=
0
,
α
α
3
-
2
α
3
-
2
α
2
-
2
α
1
-
4
α
-
2
=
0
,
α
2
-
4
α
3
-
4
α
2
-
4
α
1
-
8
α
-
4
=
0
.
After solving these equations, we get α
=
12, α
3
=
6, α
2
=
3, and α
1
=
2 and hence we have the second part. Thus, the proof is completed.


## 3. Application to Nonlinear Equations

In this section, we apply the proposed methods to solve some smooth as well as nonsmooth nonlinear equations. Here, we demonstrate the convergence behavior of the methods with and without memory. Numerical computations reported here have been carried out in a Mathematica 8.0 environment. Table1 shows the absolute value of the difference of the exact root ξ and approximated root x
k, where the exact root is computed with 1000 significant digits (digits ∶
= 1000). To check the theoretical order of convergence, we calculate the computational order of convergence (COC) using the following formula:
(40)
COC
=
ln
⁡
f
x
k
/
f
x
k
-
1
ln
⁡
f
x
k
-
1
/
f
x
k
-
2
.
For this purpose, we consider the following three test functions (taken from [25, 26]):
(41)
f
1
x
=
e
(
x
2
-
3
x
)
·
sin
x
+
log
⁡
x
2
+
1
,
f
2
x
=
e
(
x
2
+
x
cos
⁡
(
x
)
-
1
)
sin
π
x
+
x
log
⁡
x
sin
x
+
1
,
f
3
x
=
x
x
+
1
,
x
<
0
-
2
x
x
-
1
,
x
≥
0
.
In the table, A
e
h stand for A
×
1
0
h and I is indeterminate. It is obvious from the table that the proposed methods give better results.Table 1
Numerical results for nonlinear equations.
Method
Function
|
x
1
-
ξ
|
|
x
2
-
ξ
|
|
x
3
-
ξ
|
COC
x
0
=
0.35
p
0
=
0.01
ξ
=
0
(8) without memory
f
1
(
x
)
0.85173
e
-
2
0.12817
e
-
6
0.57565
e
-
26
4.0057
(10) without memory
0.12355
e
-
2
0.13471
e
-
20
0.25710
e
-
164
8.0016
(8) with memory
0.55455
e
-
2
0.47078
e
-
16
0.13739
e
-
95
5.6543
(10) with memory
0.54176
e
-
3
0.18424
e
-
36
0.69332
e
-
436
11.934
x
0
=
0.6
p
0
=
0.01
ξ
=
0
(8) without memory
f
2
(
x
)
0.49825
e
+
2
I
I
—
(10) without memory
0.49825
e
+
2
I
I
—
(8) with memory
0.79599
e
-
1
0.63127
e
-
7
0.67966
e
-
44
6.0933
(10) with memory
0.52381
e
-
1
0.17004
e
-
15
0.90974
e
-
186
11.734
x
0
=
5.0
p
0
=
0.01
ξ
=
1
(8) without memory
f
3
(
x
)
0.14237
e
+
1
0.56969
e
+
0
0.41903
e
-
1
0.65246
(10) without memory
0.38340
e
+
0
0.32526
e
+
0
0.32330
e
-
4
9.9985
(8) with memory
0.75481
e
+
0
0.94847
e
-
2
0.13693
e
-
11
4.5983
(10) with memory
0.22702
e
+
0
0.51445
e
-
8
0.13746
e
-
98
11.712


## 4. Conclusion

In this paper, the efficiency of the existing method has been improved by employing information from the current and previous iteration without any additional evaluation of the function. The efficiency index of the proposed methods is6
1
/
3
=
1.8171 and 1
2
1
/
4
=
1.8612 which are higher than efficiency index 4
1
/
3
=
1.5874 and 8
1
/
4
=
1.6818 of the existing methods, respectively. The proposed methods are also tested on some numerical examples. The numerical results show that proposed method is very useful to find an acceptable approximation of the exact solution of nonlinear equations.



---

*Source: 795628-2014-12-21.xml*