# A General Class of Derivative Free Optimal Root Finding Methods Based on Rational Interpolation

Authors: Fiza Zafar; Nusrat Yasmin; Saima Akram; Moin-ud-Din Junjua
Journal: The Scientific World Journal
 (2015)

---

## Abstract

We construct a new general class of derivative freen-point iterative methods of optimal order of convergence 2
n
-
1 using rational interpolant. The special cases of this class are obtained. These methods do not need Newton’s iterate in the first step of their iterative schemes. Numerical computations are presented to show that the new methods are efficient and can be seen as better alternates.


---

## Body

## 1. Introduction

The problem of root finding has been addressed extensively in the last few decades. In 1685, the first scheme to find the roots of nonlinear equations was published by John Wallis. Its simplified description was published in 1690 by Joseph Raphson and was called Newton-Raphson method. In 1740, Thomas Simpson was the first to introduce Newton’s method as an iterative method for solving nonlinear equations. The method is quadratically convergent but it may not converge to real root if the initial guess does not lie in the vicinity of root andf
′
(
x
) is zero in the neighborhood of the real root. This method is a without-memory method. Later, many derivative free methods were defined, for example, Secant’s and Steffensen’s methods. However, most of the derivative free iterative methods are with-memory methods; that is, they require old and new information to calculate the next approximation. Inspite of the drawbacks of Newton’s method, many multipoint methods for finding simple root of nonlinear equations have been developed in the recent past using Newton’s method as the first step. However, many higher order convergent derivative free iterative methods have also appeared most recently by taking Steffensen type methods at the first step. A large number of optimal higher order convergent iterative methods have been investigated recently up to order sixteen [1–3]. These methods used different interpolating techniques for approximating the first derivative.In the era of 1960–1965, many authors used rational function approximation for finding the root of nonlinear equation, for example, Tornheim [4], Jarratt, and Nudds [5].In 1967, Jarratt [6] effectively used rational interpolation of the form
(1)
y
=
x
-
a
b
x
2
+
c
x
+
d
,
to approximate f
(
x
) for constructing a with-memory scheme involving first derivative. The order of the scheme was 2.732 and its efficiency was 0.2182.In 1987, Cuyt and Wuytack [7] described a with-memory iterative method involving first derivative based on rational interpolation and they also discussed two special cases of their scheme having order 1.84 with efficiency 0.1324 and order 2.41 with efficiency 0.1910.In 1990, Field [8] used rational function to approximate the root of a nonlinear equation as follows:
(2)
x
i
+
1
=
x
i
+
d
i
,
where d
i, the correction in each iterate, is the root of the numerator of the Pade approximant to the Taylor series:
(3)
f
x
=
∑
j
=
0
∞
‍
f
j
x
i
j
!
x
-
x
i
j
.He proved thatx
i converges to the root ξ with order m
+
n
+
1, where m and n are degrees of the denominator and numerator of the Pade approximant.In 1974, Kung and Traub [9] conjectured that a multipoint iterative scheme without memory for finding simple root of nonlinear equations requiring n functional evaluations for one complete cycle can have maximum order of convergence 2
n
-
1 with maximal efficiency index 2
(
n
-
1
)
/
n. Multipoint methods with this property are usually called optimal methods. Several researchers [1–3, 10] developed optimal multipoint iterative methods based on this hypothesis.In 2011, Soleymani and Sharifi [10] developed a four-step without-memory fourteenth order convergent iterative method involving first derivative having an efficiency index of 1.6952. The first derivative at the fourth step is approximated using rational interpolation as follows:
(4)
w
n
=
ϕ
8
x
n
,
y
n
,
z
n
x
n
+
1
=
w
n
-
1
+
b
4
w
n
-
x
n
2
f
′
x
n
+
b
3
w
n
-
x
n
2
+
b
4
w
n
-
x
n
f
w
n
,
where ϕ
8 is an optimal eighth order convergent method and the rational interpolant is given as:
(5)
m
t
=
b
+
b
2
t
-
x
+
b
3
t
-
x
2
1
+
b
4
t
-
x
.In 2012, Soleymani et al. [3] developed a three-step derivative free eighth order method using rational interpolation as follows:
(6)
z
n
=
ϕ
4
x
n
,
y
n
,
w
n
,
x
n
+
1
=
z
n
-
1
+
a
3
z
n
-
x
n
2
a
1
-
a
0
a
3
+
2
a
2
z
n
-
x
n
+
a
2
a
3
z
n
-
x
n
2
f
z
n
,
where ϕ
4 is any two-step fourth order convergent derivative free iterative method. They used the same rational interpolant as given in (5). The constants are determined using the interpolating conditions.In 2012, Soleymani et al. [2] added his contribution by developing a sixteenth order four-point scheme using Pade approximation. The scheme required four evaluations of functions and one evaluation of first derivative and achieved optimal order of sixteen and and an efficiency index 1.741. The scheme was of the form
(7)
w
n
=
ϕ
8
x
n
,
y
n
,
z
n
,
x
n
+
1
=
w
n
-
1
+
b
5
w
n
-
x
n
2
f
w
n
×
f
′
x
n
+
2
b
3
w
n
-
x
n
+
3
b
4
+
b
3
b
5
w
n
-
x
n
2
+
2
b
4
b
5
w
n
-
x
n
3
-
1
,
where ϕ
8 is eighth order optimal method. They used the rational interpolant of the following form:
(8)
p
t
=
b
1
+
b
2
t
-
x
+
b
3
t
-
x
2
+
b
4
t
-
x
3
1
+
b
5
t
-
x
.Recently in 2013, Sharma et al. [1] developed a three-step eighth order method and its extension to four-step sixteenth order method using rational interpolation. In the scheme, the first three steps are any arbitrary eight order convergent method. The fourth step is the root of the numerator of the method, which is given as
(9)
t
n
=
ϕ
8
x
n
,
z
n
,
w
n
,
x
n
+
1
=
x
n
-
P
1
f
z
n
,
w
n
+
Q
1
f
x
n
,
w
n
+
R
f
t
n
,
w
n
P
1
L
+
Q
1
M
+
R
N
f
x
n
,
where,
(10)
L
=
f
w
n
f
x
n
,
z
n
-
f
z
n
f
x
n
,
w
n
w
n
-
z
n
,
M
=
f
w
n
f
′
x
n
-
f
x
n
f
x
n
,
w
n
w
n
-
x
n
,
N
=
f
w
n
f
x
n
,
t
n
-
f
t
n
f
x
n
,
w
n
w
n
-
t
n
,
P
1
=
x
n
-
t
n
f
x
n
f
t
n
,
Q
1
=
t
n
-
z
n
f
t
n
f
z
n
,
R
=
z
n
-
x
n
f
z
n
f
x
n
,
and rational polynomial of the following form:
(11)
p
4
x
=
x
-
x
i
+
λ
μ
x
-
x
i
3
+
ν
x
-
x
i
2
+
ξ
x
-
x
i
+
η
.
The efficiency index of the above sixteenth order method is 1.741. The method involves one derivative evaluation.In this paper, we present a general class of derivative freen-point iterative method which satisfies Kung and Tarub’s Hypothesis [9]. Proposed schemes require n functional evaluations to acquire the convergence order 2
n
-
1 and efficiency index can have 2
(
n
-
1
)
/
n. The contents of the paper are summarized as follows. In Section 2, we present a general class of n-point iterative scheme and its special cases with second, fourth, eighth, and sixteenth order convergence. Section 3 consists of the convergence analysis of the iterative methods discussed in Section 2. In the last section of the paper, we give concluding remarks and some numerical results to show the effectiveness of the proposed methods.


## 2. Higher Order Derivative Free Optimal Methods

In this section, we give a general class ofn-point iterative method involving n functional evaluations having order of convergence 2
n
-
1. Thus, the scheme is optimal in the sense of the conjecture of Kung and Traub [9].Consider a rational polynomial of degreen
-
1 as follows:
(12)
r
n
-
1
t
=
p
1
t
q
n
-
2
t
,
where,
(13)
p
1
t
=
a
0
+
a
1
t
-
x
,
q
n
-
2
t
=
1
+
b
1
t
-
x
+
⋯
+
b
n
-
2
t
-
x
n
-
2
,
n
≥
2
,
q
0
≡
1
.We approximatef
(
x
) by rational function given by (12) to construct a general class of n-point iterative scheme. Then, the root of nonlinear equation f
(
x
)
=
0 is the root of the numerator of the rational interpolant of degree n
-
1 for the n-point method. The unknowns a
0
,
a
1
,
b
1
,
…
,
b
n
-
1 are determined by the following interpolating conditions:
(14)
r
n
-
1
x
=
f
x
,
r
n
-
1
w
k
=
f
w
k
,
k
=
1
,
…
,
n
-
1
,
n
≥
2
.Then, the generaln-point iterative method is given by
(15)
w
1
=
x
+
β
f
x
,
⋮
w
n
=
x
-
a
0
a
1
,
n
≥
2
.
Now, we are going to derive its special cases. For n
=
2 in (14)-(15),
(16)
r
1
t
=
a
0
+
a
1
t
-
x
.
We find a
0 and a
1 such that
(17)
r
1
x
=
f
x
,
r
1
w
1
=
f
w
1
.
So, the two-point iterative scheme becomes
(18)
w
1
=
x
+
β
f
x
,
w
2
=
x
-
f
x
f
w
1
,
x
.
The iterative scheme (18) is the same as given by Steffensen [11] for β
=
1; thus, is a particular case of our scheme given by (14)-(15).Forn
=
3, we have
(19)
r
2
t
=
a
0
+
a
1
t
-
x
1
+
b
1
t
-
x
.We finda
0, a
1, and b
1 using the following conditions:
(20)
r
2
x
=
f
x
,
r
2
w
1
=
f
w
1
,
r
2
w
2
=
f
w
2
.
By using conditions (20), we have
(21)
a
0
=
f
x
,
a
1
=
f
w
2
,
x
+
b
1
f
w
2
,
b
1
=
f
w
1
,
x
-
f
w
2
,
x
f
w
2
-
f
w
1
.
Now, using (21), we have the following three-point iterative scheme:
(22)
w
1
=
x
+
β
f
x
,
w
2
=
x
-
f
x
f
w
1
,
x
,
w
3
=
x
-
f
x
f
w
2
-
f
w
1
f
w
2
f
w
1
,
x
-
f
w
1
f
w
2
,
x
.
For n
=
4, we have the following rational interpolant:
(23)
r
3
t
=
a
0
+
a
1
t
-
x
1
+
b
1
t
-
x
+
b
2
t
-
x
2
,
such that
(24)
r
3
x
=
f
x
,
r
3
w
1
=
f
w
1
,
r
3
w
2
=
f
w
2
,
r
3
w
3
=
f
w
3
.
The conditions (24) are used to determine the unknowns a
0, a
1, b
1, and b
2. Thus, we attain a four-point iterative method as follows:
(25)
w
1
=
x
+
β
f
x
,
w
2
=
x
-
f
x
f
w
1
,
x
,
w
3
=
x
-
f
x
f
w
2
-
f
w
1
f
w
2
f
w
1
,
x
-
f
w
1
f
w
2
,
x
,
w
4
=
x
-
f
x
h
1
+
h
2
+
h
3
h
1
f
w
1
,
x
+
h
2
f
w
2
,
x
+
h
3
f
w
3
,
x
,
where,
(26)
h
1
=
f
w
2
f
w
3
w
3
-
w
2
,
h
2
=
f
w
1
f
w
3
w
1
-
w
3
,
h
3
=
f
w
1
f
w
2
w
2
-
w
1
.
For n
=
5, we have the following five-point iterative scheme:
(27)
w
1
=
x
+
β
f
x
,
w
2
=
x
-
f
x
f
w
1
,
x
,
w
3
=
x
-
f
x
f
w
2
-
f
w
1
f
w
2
f
w
1
,
x
-
f
w
1
f
w
2
,
x
,
w
4
=
x
-
f
x
h
1
+
h
2
+
h
3
h
1
f
w
1
,
x
+
h
2
f
w
2
,
x
+
h
3
f
w
3
,
x
,
w
5
=
x
-
a
0
a
1
,
where,
(28)
r
4
t
=
a
0
+
a
1
t
-
x
1
+
b
1
t
-
x
+
b
2
t
-
x
2
+
b
3
t
-
x
3
,
such that
(29)
r
4
x
=
f
x
,
r
4
w
1
=
f
w
1
,
r
4
w
2
=
f
w
2
,
r
4
w
3
=
f
w
3
,
r
4
w
4
=
f
w
4
.
The interpolating conditions (29) yield
(30)
a
0
=
f
x
,
a
1
=
m
1
f
w
1
,
x
+
m
2
f
w
2
,
x
+
m
3
f
w
3
,
x
+
m
4
f
w
4
,
x
m
1
+
m
2
+
m
3
+
m
4
-
1
,
where,
(31)
m
1
=
f
w
2
f
w
3
f
w
4
×
-
w
3
-
x
w
4
-
x
w
4
-
w
3
+
w
2
-
x
w
4
-
x
w
4
-
w
2
-
w
2
-
x
w
3
-
x
h
1
f
w
4
m
2
=
f
w
1
f
w
3
f
w
4
×
w
3
-
x
w
4
-
x
w
4
-
w
3
-
w
1
-
x
w
4
-
x
w
4
-
w
1
-
w
1
-
x
w
3
-
x
h
2
f
w
4
m
3
=
f
w
1
f
w
2
f
w
4
×
-
w
2
-
x
w
4
-
x
w
4
-
w
2
+
w
1
-
x
w
4
-
x
w
4
-
w
1
-
w
1
-
x
w
2
-
x
h
3
f
w
4
m
4
=
f
w
1
f
w
2
f
w
3
×
w
2
-
x
w
3
-
x
w
3
-
w
2
-
w
1
-
x
w
3
-
x
w
3
-
w
1
+
w
1
-
x
w
2
-
x
h
3
f
w
3
,
and h
1, h
2, h
3 are given as in (26). Hence, we obtain the following iterative method:
(32)
w
1
=
x
+
β
f
x
,
w
2
=
x
-
f
x
f
w
1
,
x
,
w
3
=
x
-
f
x
f
w
2
-
f
w
1
f
w
2
f
w
1
,
x
-
f
w
1
f
w
2
,
x
,
w
4
=
x
-
f
x
h
1
+
h
2
+
h
3
h
1
f
w
1
,
x
+
h
2
f
w
2
,
x
+
h
3
f
w
3
,
x
,
w
5
=
x
-
f
x
m
1
+
m
2
+
m
3
+
m
4
×
m
1
f
w
1
,
x
+
m
2
f
w
2
,
x
+
m
3
f
w
3
,
x
+
m
4
f
w
4
,
x
-
1
.
We, now, give the convergence analysis of the proposed iterative methods (18), (22), (25), and (32).


## 3. Convergence Analysis

Theorem 1.
Let us considerω
∈
I as the simple root of sufficiently differentiable function f
:
I
⊆
R
→
R in the neighborhood of the root for interval I. If x is sufficiently close to ω, then, for every β
∈
R
∖
{
-
1
}, the iterative methods defined by (18) and (22) are second and fourth order convergent, respectively, with the error equations given by
(33)
e
n
+
1
=
c
2
1
+
β
e
n
2
+
O
e
n
3
,
e
n
+
1
=
c
2
3
-
c
2
c
3
+
2
c
2
3
β
+
c
2
3
β
2
-
2
c
2
c
3
β
-
c
2
c
3
β
2
e
n
4
+
O
e
n
5
,
respectively, where,
(34)
c
k
=
1
k
!
f
k
ω
f
′
ω
,
k
=
2,3
,
…Proof.
Letx
=
ω
+
e
n, where ω is the root of f and e
n is the error at n
th step. Now, using Taylor expansion of f
(
x
) about the root ω, we have
(35)
f
x
=
f
′
ω
e
n
+
c
2
e
n
2
+
c
3
e
n
3
+
c
4
e
n
4
11111111
+
⋯
+
c
8
e
n
8
+
O
e
n
9
,
where c
k is defined by (34). Taylor’s expansions for w
1 and f
(
w
1
) are
(36)
w
1
=
e
n
+
ω
+
β
e
n
+
c
2
e
n
2
+
c
3
e
n
3
+
c
4
e
n
4
+
c
5
e
n
5
+
O
e
n
6
,
(37)
f
w
1
=
f
′
ω
1
+
β
e
n
+
3
β
c
2
+
c
2
+
c
2
β
2
e
n
2
1111111111
+
2
c
2
2
β
+
2
c
2
2
β
2
+
c
3
+
4
β
c
3
1111111111111
+
3
c
3
β
2
+
c
3
β
3
e
n
3
1111111111
+
5
c
2
β
c
3
+
8
c
2
β
2
c
3
+
3
c
3
β
3
1111111111111
+
c
4
+
5
β
c
4
+
6
β
2
c
4
+
4
c
4
β
3
1111111111111
+
c
4
β
4
+
c
2
3
β
2
e
n
4
1111111111
+
c
5
+
6
β
c
5
+
10
c
5
β
2
+
10
c
5
β
3
+
5
c
5
β
4
111111111111
+
c
5
β
5
+
6
c
2
β
c
4
+
14
c
2
c
4
β
2
+
12
c
4
c
2
β
3
111111111111
+
4
c
4
c
2
β
4
+
5
c
2
2
c
3
β
2
+
3
c
3
2
β
+
6
c
3
2
β
2
111111111111
+
3
c
3
β
3
c
2
2
+
3
c
3
2
β
3
e
n
5
+
O
e
n
6
.
Using (35), (36), and (37), we have
(38)
w
2
=
ω
+
c
2
1
+
β
e
n
2
+
-
2
c
2
2
-
2
c
2
2
β
+
2
c
3
+
3
β
c
3
+
c
3
β
2
-
c
2
2
β
2
e
n
3
+
4
c
2
3
+
5
c
2
3
β
-
7
c
2
c
3
-
10
c
2
β
c
3
-
7
c
2
β
2
c
3
+
3
c
2
3
β
2
-
2
c
3
β
3
c
2
+
3
c
4
+
6
β
c
4
+
4
c
4
β
2
+
c
4
β
3
+
c
2
3
β
3
e
n
4
+
O
e
n
5
,
which shows that the method (18) is quadratically convergent for all β
∈
R
∖
{
-
1
}. Again using Taylor expansion of f
(
w
2
), we have
(39)
f
w
2
=
f
′
ω
c
2
1
+
β
e
n
2
1111111111111
+
-
2
c
2
2
-
2
c
2
2
β
+
2
c
3
1111111111111111
+
3
β
c
3
+
c
3
β
2
-
c
2
2
β
2
e
n
3
1111111111111
+
5
c
2
3
+
7
c
2
3
β
-
7
c
2
c
3
-
10
c
2
β
c
3
1111111111111111
-
7
c
2
β
2
c
3
+
4
c
2
3
β
2
1111111111111111
-
2
c
3
β
3
c
2
+
3
c
4
+
6
β
c
4
1111111111111111
+
4
c
4
β
2
+
c
4
β
3
+
c
2
3
β
3
e
n
4
+
O
e
n
5
.
Now, using (35)–(39), we see that the order of convergence of the method (22) is four and the error equation is given by
(40)
e
n
+
1
=
c
2
3
+
2
c
2
3
β
-
c
2
c
3
-
2
c
2
c
3
β
-
c
2
c
3
β
2
+
c
2
3
β
2
e
n
4
+
O
e
n
5
.Theorem 2.
Let us considerω
∈
I as the simple root of sufficiently differentiable function f
:
I
⊆
R
→
R in the neighborhood of the root for interval I. If x is sufficiently close to ω, then for all β
∈
R
∖
{
-
1
}, the iterative methods defined by (25) and (32) are eighth and sixteenth order convergent, respectively, with the error equations given by
(41)
e
n
+
1
=
c
2
2
c
2
5
β
4
-
3
c
3
c
2
3
β
4
+
4
c
2
5
β
3
+
c
4
c
2
2
β
4
+
2
c
3
2
c
2
β
4
-
12
c
3
c
2
3
β
3
+
6
c
2
5
β
2
-
c
4
c
3
β
4
+
4
c
4
c
2
2
β
3
+
8
c
3
2
c
2
β
3
-
18
c
3
c
2
3
β
2
+
4
c
2
5
β
-
4
c
4
c
3
β
3
+
6
c
4
c
2
2
β
2
+
12
c
3
2
c
2
β
2
-
12
c
3
c
2
3
β
+
c
2
5
-
6
c
4
c
3
β
2
+
4
c
4
c
2
2
β
+
8
β
c
2
c
3
2
-
3
c
2
3
c
3
-
4
β
c
3
c
4
+
c
2
2
c
4
+
2
c
2
c
3
2
-
c
3
c
4
e
n
8
+
O
e
n
9
,
e
n
+
1
=
4
c
2
5
c
3
c
5
-
c
3
2
c
4
c
5
+
2
c
2
c
3
2
c
4
2
+
2
c
2
c
3
3
c
5
-
4
c
2
3
c
3
c
4
2
-
5
c
2
3
c
3
2
c
5
-
c
2
4
c
4
c
5
+
18
c
2
4
c
3
2
c
4
-
13
c
2
6
c
3
c
4
-
9
c
2
2
c
3
3
c
4
+
2
c
2
5
c
4
2
+
c
3
4
c
4
-
2
c
2
c
3
5
-
c
2
7
c
5
-
7
c
2
9
c
3
+
3
c
2
8
c
4
+
11
c
2
3
c
3
4
-
21
c
2
5
c
3
3
+
18
c
2
7
c
3
2
+
2
c
2
2
c
3
c
4
c
5
+
c
2
11
c
2
4
β
8
+
⋯
+
4
c
2
5
c
3
c
5
-
c
3
2
c
4
c
5
+
2
c
2
c
3
2
c
4
2
+
2
c
2
c
3
3
c
5
-
4
c
2
3
c
3
c
4
2
-
5
c
2
3
c
3
2
c
5
-
c
2
4
c
4
c
5
+
18
c
2
4
c
3
2
c
4
-
13
c
2
6
c
3
c
4
-
9
c
2
2
c
3
3
c
4
+
2
c
2
5
c
4
2
+
c
3
4
c
4
-
2
c
2
c
3
5
-
c
2
7
c
5
-
7
c
2
9
c
3
+
3
c
2
8
c
4
+
11
c
2
3
c
3
4
-
21
c
2
5
c
3
3
+
18
c
2
7
c
3
2
+
2
c
2
2
c
3
c
4
c
5
+
c
2
11
c
2
4
e
n
16
+
O
e
n
17
,
where,
(42)
c
k
=
1
k
!
f
k
ω
f
′
ω
,
k
=
2,3
,
…Proof.
Letx
=
ω
+
e
n, where ω is the root of f and e
n is the error in the approximation at n
th iteration. We will use (35), (37), (39), and (40) up to O
(
e
n
30
) in this result and set
(43)
w
3
=
ω
+
c
2
3
+
2
c
2
3
β
-
c
2
c
3
-
2
c
2
c
3
β
-
c
2
c
3
β
2
+
c
2
3
β
2
e
n
4
+
4
c
3
β
3
c
2
2
-
2
c
2
4
β
3
-
c
3
2
β
3
-
c
4
β
3
c
2
-
4
c
2
β
2
c
4
+
14
c
2
2
β
2
c
3
-
6
c
2
4
β
2
-
4
c
3
2
β
2
+
18
c
2
2
β
c
3
-
5
c
2
β
c
4
-
8
c
2
4
β
-
5
c
3
2
β
-
4
c
2
4
-
2
c
2
c
4
+
8
c
2
2
c
3
-
2
c
3
2
e
n
5
+
⋯
+
O
e
n
30
.
Again, using Taylor expansion of f
(
w
3
), we have
(44)
f
w
3
=
f
′
ω
c
2
3
+
2
c
2
3
β
-
c
2
c
3
-
2
c
2
c
3
β
111111111111111
-
c
2
c
3
β
2
+
c
2
3
β
2
e
n
4
11111111111111
+
4
c
3
β
3
c
2
2
-
2
c
2
4
β
3
-
c
3
2
β
3
-
c
4
β
3
c
2
11111111111111111
-
4
c
2
β
2
c
4
+
14
c
2
2
β
2
c
3
-
6
c
2
4
β
2
-
4
c
3
2
β
2
11111111111111111
+
18
c
2
2
β
c
3
-
5
c
2
β
c
4
-
8
c
2
4
β
-
5
c
3
2
β
11111111111111111
-
4
c
2
4
-
2
c
2
c
4
+
8
c
2
2
c
3
-
2
c
3
2
e
n
5
11111111111111
+
⋯
+
O
e
n
30
.
Now, using (35)–(39), (43), and (44), we see that the method (25) has eighth order convergence with the error equation
(45)
e
n
+
1
=
c
2
2
c
2
5
β
4
-
3
c
3
c
2
3
β
4
+
4
c
2
5
β
3
+
c
4
c
2
2
β
4
+
2
c
3
2
c
2
β
4
-
12
c
3
c
2
3
β
3
+
6
c
2
5
β
2
-
c
4
c
3
β
4
+
4
c
4
c
2
2
β
3
+
8
c
3
2
c
2
β
3
-
18
c
3
c
2
3
β
2
+
4
c
2
5
β
-
4
c
4
c
3
β
3
+
6
c
4
c
2
2
β
2
+
12
c
3
2
c
2
β
2
-
12
c
3
c
2
3
β
+
c
2
5
-
6
c
4
c
3
β
2
+
4
c
4
c
2
2
β
+
8
β
c
2
c
3
2
-
3
c
2
3
c
3
-
4
β
c
3
c
4
+
c
2
2
c
4
+
2
c
2
c
3
2
-
c
3
c
4
e
n
8
+
O
e
n
9
.
To find the error equation of (32), we use (45) up to O
(
e
n
30
) and set
(46)
w
4
=
c
2
2
c
2
5
β
4
-
3
c
3
c
2
3
β
4
+
4
c
2
5
β
3
+
c
4
c
2
2
β
4
+
2
c
3
2
c
2
β
4
-
12
c
3
c
2
3
β
3
+
6
c
2
5
β
2
-
c
4
c
3
β
4
+
4
c
4
c
2
2
β
3
+
8
c
3
2
c
2
β
3
-
18
c
3
c
2
3
β
2
+
4
c
2
5
β
-
4
c
4
c
3
β
3
+
6
c
4
c
2
2
β
2
+
12
c
3
2
c
2
β
2
-
12
c
3
c
2
3
β
+
c
2
5
-
6
c
4
c
3
β
2
+
4
c
4
c
2
2
β
+
8
β
c
2
c
3
2
-
3
c
2
3
c
3
-
4
β
c
3
c
4
+
c
2
2
c
4
+
2
c
2
c
3
2
-
c
3
c
4
e
n
8
+
⋯
+
O
e
n
30
.
Taylor expansion of f
(
w
4
) is
(47)
f
w
4
=
f
′
ω
c
2
7
β
4
+
c
2
4
c
4
+
c
2
7
+
c
4
β
4
c
2
4
-
c
2
2
c
4
c
3
-
c
4
c
3
β
4
c
2
2
+
8
c
2
3
c
3
2
β
3
+
2
β
4
c
3
2
c
2
3
+
8
c
2
3
β
c
3
2
+
12
c
2
3
β
2
c
3
2
-
18
c
2
5
c
3
β
2
-
12
c
2
5
c
3
β
-
3
β
4
c
2
5
c
3
+
6
c
2
4
c
4
β
2
+
4
c
2
4
c
4
β
3
+
4
c
2
4
c
4
β
-
12
c
2
5
c
3
β
3
+
6
c
2
7
β
2
+
4
c
2
7
β
3
+
4
c
2
7
β
-
3
c
2
5
c
3
+
2
c
2
3
c
3
2
-
6
c
3
β
2
c
4
c
2
2
-
4
c
2
2
c
4
β
c
3
-
4
c
4
c
2
2
c
3
β
3
e
n
8
+
⋯
+
O
e
n
30
.
Hence, using (35)–(39), (43), (44), (46), and (47), we see that iterative method (32) is sixteenth order convergent with the error equation given by
(48)
e
n
+
1
=
4
c
2
5
c
3
c
5
-
c
3
2
c
4
c
5
+
2
c
2
c
3
2
c
4
2
+
2
c
2
c
3
3
c
5
11111111
-
4
c
2
3
c
3
c
4
2
-
5
c
2
3
c
3
2
c
5
-
c
2
4
c
4
c
5
11111111
+
18
c
2
4
c
3
2
c
4
-
13
c
2
6
c
3
c
4
-
9
c
2
2
c
3
3
c
4
+
2
c
2
5
c
4
2
11111111
+
c
3
4
c
4
-
2
c
2
c
3
5
-
c
2
7
c
5
-
7
c
2
9
c
3
11111111
+
3
c
2
8
c
4
+
11
c
2
3
c
3
4
-
21
c
2
5
c
3
3
+
18
c
2
7
c
3
2
11111111
+
2
c
2
2
c
3
c
4
c
5
+
c
2
11
c
2
4
β
8
1111111
+
⋯
+
4
c
2
5
c
3
c
5
-
c
3
2
c
4
c
5
+
2
c
2
c
3
2
c
4
2
+
2
c
2
c
3
3
c
5
11111111111111
-
4
c
2
3
c
3
c
4
2
-
5
c
2
3
c
3
2
c
5
-
c
2
4
c
4
c
5
+
18
c
2
4
c
3
2
c
4
11111111111111
-
13
c
2
6
c
3
c
4
-
9
c
2
2
c
3
3
c
4
+
2
c
2
5
c
4
2
+
c
3
4
c
4
-
2
c
2
c
3
5
11111111111111
-
c
2
7
c
5
-
7
c
2
9
c
3
+
3
c
2
8
c
4
+
11
c
2
3
c
3
4
11111111111111
-
21
c
2
5
c
3
3
+
18
c
2
7
c
3
2
+
2
c
2
2
c
3
c
4
c
5
11111111111111
+
c
2
11
c
2
4
e
n
16
+
O
e
n
17
.Remark 3.
From Theorems1 and 2, it can be seen that the iterative schemes (18), (22), (25), and (32) are second, fourth, eighth, and sixteenth order convergent requiring two, three, four, and five functional evaluations, respectively. Hence, the proposed iterative schemes (18), (22), (25), and (32) are optimal in the sense of the hypothesis of Kung and Traub [9] with the efficiency indices 1.414, 1.587, 1.681, 1.741. Also, it is clear that (14)-(15) is a general n-point scheme with optimal order of convergence 2
n
-
1. The efficiency index of this scheme is 2
(
n
-
1
)
/
n.


## 4. Numerical Results

In this section, we present some test functions to demonstrate the performance of the newly developed sixteenth order scheme (32) (FNMS-16). For the sake of comparison, we consider the existing higher order convergent methods based on rational interpolation. We consider the fourteenth order method of Soleymani and Sharifi (4) (SS-14), the sixteenth order method of Soleymani et al.(7) (SSS-16), and the sixteenth order method of Sharma et al.(9) (SGG-16). All the computations for the above-mentioned methods are performed using Maple 16 with 4000 decimal digits precision. The test functions given in Table 1 are taken from [1, 2, 10]. We used almost all types of nonlinear functions, polynomials, and transcendental functions to test the new methods. Table 2 shows that the newly developed sixteenth order methods are comparable with the existing methods of this domain in terms of significant digits and number of function evaluations per iteration. In many examples, the newly developed methods perform better than the existing methods. It can also be seen from the tables that, for the choice of initial guess, near to the exact root or far from the exact root, the performance of the new methods is better.Table 1
Test functions and exact roots.
Numerical example
Exact roots
f
1
(
x
)
=
x
4
+
8
sin
⁡
⁡
(
π
/
(
x
2
+
2
)
)
+
x
3
/
(
x
4
+
1
)
-
6
+
8
/
17
ω
1
=
-
2
f
2
(
x
)
=
sin
⁡
⁡
(
x
)
-
x
/
100
ω
2
=
0
f
3
(
x
)
=
(
1
/
3
)
x
4
-
x
2
-
(
1
/
3
)
x
+
1
ω
3
=
1
f
4
(
x
)
=
e
sin
⁡
⁡
(
x
)
-
1
-
x
/
5
ω
4
=
0
f
5
(
x
)
=
x
e
x
2
-
(
sin
⁡
⁡
(
x
)
)
2
+
3
cos
⁡
(
x
)
+
5
ω
5
≈
-
1.207647827130919
f
6
(
x
)
=
e
-
x
+
cos
⁡
(
x
)
ω
6
≈
1.746139530408013
f
7
(
x
)
=
10
x
e
-
x
2
-
1
ω
7
≈
1.679630610428450
f
8
(
x
)
=
x
3
+
4
x
2
-
15
ω
8
≈
1.631980805566063Table 2
Comparison of various iterative methods.
f
(
x
), x
0
(SS-14)
(SGG-16)
(SSS-16)
(FNMS-16)
f
1
,
x
0
=
-
1.2
|
f
1
(
x
1
)
|
.
3
e
-
13
.1e
-
15
.1e
-
13
.1e
-
15
|
f
1
(
x
2
)
|
.1e
-
181
.6e
-
248
.1e
-
211
.5e
-
245
|
f
1
(
x
3
)
|
.6e
-
2538
.6e
-
3751
.7e
-
3379
.6e
-
3916
f
1
,
x
0
=
-
3
|
f
1
(
x
1
)
|
.1e
-
5
.3e
-
6
.3e
-
7
.
2
e
-
8
|
f
1
(
x
2
)
|
.4e
-
75
.1e
-
96
.2e
-
113
.1e
-
132
|
f
1
(
x
3
)
|
.1e
-
1050
.3e
-
1545
.2e
-
1812
.5e
-
2123
f
2
,
x
0
=
1.5
|
f
2
(
x
1
)
|
.95
.95
.64
.3e
-
4
|
f
2
(
x
2
)
|
.1e
-
10
.1e
-
4
.3e
-
6
.5e
-
100
|
f
2
(
x
3
)
|
.2e
-
88
.5e
-
90
.1e
-
111
.4e
-
1632
f
2
,
x
0
=
3
|
f
2
(
x
1
)
|
.2e
-
24
.1e
-
25
.3e
-
27
.2e
-
44
|
f
2
(
x
2
)
|
.8e
-
358
.8e
-
425
.2e
-
452
.9e
-
743
|
f
2
(
x
3
)
|
0
0
0
0
f
3
,
x
0
=
0.5
|
f
3
(
x
1
)
|
.5e
-
8
.6e
-
9
.3e
-
9
.9e
-
10
|
f
3
(
x
2
)
|
.8e
-
114
.3e
-
144
.4e
-
149
.6e
-
238
|
f
3
(
x
3
)
|
.2e
-
1595
.1e
-
2307
.1e
-
2386
0
f
3
,
x
0
=
1.5
|
f
3
(
x
1
)
|
.2e
-
11
.2e
-
13
.2e
-
11
.1e
-
11
|
f
3
(
x
2
)
|
.2e
-
158
.6e
-
214
.1e
-
179
.6e
-
183
|
f
3
(
x
3
)
|
.3e
-
2218
.8e
-
3423
.2e
-
2869
.
6
e
-
2935
f
4
,
x
0
=
5
|
f
4
(
x
1
)
|
.8e
-
1
.25
.8e
-
1
.1e
-
2
|
f
4
(
x
2
)
|
.4e
-
15
.1e
-
6
.3e
-
16
.3e
-
56
|
f
4
(
x
3
)
|
.1e
-
213
.7e
-
109
.9e
-
262
.1e
-
914
f
4
,
x
0
=
4
|
f
4
(
x
1
)
|
.92
.9e
-
1
2.51
.
1
e
-
17
|
f
4
(
x
2
)
|
.4e
-
5
.1e
-
25
.6e
-
3
.
3
e
-
295
|
f
4
(
x
3
)
|
.
1
e
-
73
.1e
-
423
.6e
-
49
0
f
5
,
x
0
=
-
1
|
f
5
(
x
1
)
|
.1e
-
3
.1e
-
7
.8e
-
4
.7e
-
5
|
f
5
(
x
2
)
|
.2e
-
66
.5e
-
144
.9e
-
80
.4e
-
92
|
f
5
(
x
3
)
|
.4e
-
946
.8e
-
2327
.1e
-
1294
.6e
-
1488
f
5
,
x
0
=
-
0.6
|
f
5
(
x
1
)
|
.2e
44770
.4e
-
1
.2e
44770
.1
|
f
5
(
x
2
)
|
.4e
44769
.4e
-
40
.7e
44768
.3e
-
23
|
f
5
(
x
3
)
|
.5e
44767
.4e
-
664
.2e
44767
.8e
-
386
f
6
,
x
0
=
0.5
|
f
6
(
x
1
)
|
.6e
-
7
.9e
-
9
.3e
-
8
.1e
-
14
|
f
6
(
x
2
)
|
.8e
-
116
.1e
-
152
.7e
-
145
.1e
-
254
|
f
6
(
x
3
)
|
.1e
-
1748
.7e
-
2456
.9e
-
2332
.1e
-
3999
f
6
,
x
0
=
3
|
f
6
(
x
1
)
|
.7
.53
.79
0.7e
-
8
|
f
6
(
x
2
)
|
.9e
-
5
.4e
-
16
.2e
-
5
.2e
-
145
|
f
6
(
x
3
)
|
.7e
-
102
.1e
-
269
.5e
-
125
0.3e
-
2345
f
7
,
x
0
=
0
|
f
7
(
x
1
)
|
.1e
-
6
.2e
-
9
.1e
-
5
.8e
-
12
|
f
7
(
x
2
)
|
.5e
-
99
.3e
-
161
.6e
-
98
.1e
-
199
|
f
7
(
x
3
)
|
.3e
-
1394
.6e
-
2562
.5e
-
1575
.3e
-
3205
f
7
,
x
0
=
2.2
|
f
7
(
x
1
)
|
1
.9e
-
2
1
.8e
-
8
|
f
7
(
x
2
)
|
1
.6e
-
40
D
.9e
-
136
|
f
7
(
x
3
)
|
D
.5e
-
651
D
.4e
-
2183
f
8
,
x
0
=
0.5
|
f
8
(
x
1
)
|
.1e
7
.97
.1e
7
1.0
|
f
8
(
x
2
)
|
16856.81
.2e
-
25
16856.81
.8e
-
15
|
f
8
(
x
3
)
|
183.46
.3e
-
435
183.46
.1e
-
256
f
8
,
x
0
=
1
|
f
8
(
x
1
)
|
.2e
-
2
.5e
-
5
.2e
-
2
.6e
-
3
|
f
8
(
x
2
)
|
.2e
-
65
.1e
-
109
.2e
-
65
.7e
-
67
|
f
8
(
x
3
)
|
.6e
-
1073
.1e
-
1782
.6e
-
1073
.1e
-
1089
*D stands for divergence.


## 5. Attraction Basins

Letω
i be the roots of the complex polynomial p
n
(
x
), n
≥
1, x
∈
C, where i
=
1,2
,
3
,
…
,
n. We use two different techniques to generate basins of attraction on MATLAB software. We take a square box of -
2,2
×
[
-
2,2
]
∈
C in the first technique. For every initial guess x
0, a specific color is assigned according to the exact root, and dark blue is assigned for the divergence of the method. We use f
(
x
k
)
<
1
0
-
5 as the stopping criteria for convergence and the maximum number of iterations are 30. “Jet” is chosen as the colormap here. For the second technique, the same scale is taken but each initial guess is assigned a color depending upon the number of iterations for the method to converge to any of the roots of the given function. We use 25 as the maximum number of iterations; the stopping criteria are the same as above and colormap is selected as “hot.” The method is considered divergent for that initial guess if it does not converge in the maximum number of iterations and this case is displayed by black color.We take three test examples to obtain basins of attraction, which are given asp
3
(
x
)
=
x
3
-
1,p
4
(
x
)
=
x
4
-
10
x
2
+
9, and p
5
(
x
)
=
x
5
-
1. The roots of p
3
(
x
) are 1.0, -
0.5000
+
0.86605
I, and -
0.5000
-
0.86605
I, the roots of p
4
(
x
) are -
3, 3, -
1, 1, and for p
5
(
x
) roots are 1.0, 0.3090
+
0.95105
I, -
0.8090
+
0.58778
I, -
0.8090
-
0.58778
I, and 0.30902
-
0.95105
I.We compare the results of our newly constructed method (32) with some existing methods (7) and (9), as given in Section 1. Figures 1, 2, 3, 4, 5, 6, 7, 8, and 9 show the dynamics of the methods (7), (9), and (32) for the polynomials x
3
-
1, x
4
-
1, and x
5
-
1. Two types of attraction basins are given in all figures. One can easily see that the appearance of darker region shows that the method consumes a fewer number of iterations. Color maps for both types are given with each figure which shows the root to which an initial guess converges and the number of iterations in which the convergence occurs.Figure 1
Basins of attraction of method (7) for p
3
(
x
).Figure 2
Basins of attraction of method (9) for p
3
(
x
).Figure 3
Basins of attraction of method (32) for p
3
(
x
).Figure 4
Basins of attraction of method (7) for p
4
(
x
).Figure 5
Basins of attraction of method (9) for p
4
(
x
).Figure 6
Basins of attraction of method (32) for p
4
(
x
).Figure 7
Basins of attraction of method (7) for p
5
(
x
).Figure 8
Basins of attraction of (9) for p
5
(
x
).Figure 9
Basins of attraction of (32) for p
5
(
x
).



---

*Source: 934260-2015-01-28.xml*