Open AccessArticle

Some Improvements to a Third Order Variant of Newton’s Method from Simpson’s Rule

Diyashvir Kreetee Rajiv Babajee

African Network for Policy Research & Actions for Sustainability (ANPRAS), Midlands, Curepipe 52501, Mauritius

Algorithms 2015, 8(3), 552-561; https://doi.org/10.3390/a8030552

Submission received: 11 May 2015 / Revised: 20 July 2015 / Accepted: 21 July 2015 / Published: 29 July 2015

(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)

Abstract

In this paper, we present three improvements to a three-point third order variant of Newton's method derived from the Simpson rule. The first one is a fifth order method using the same number of functional evaluations as the third order method, the second one is a four-point 10th order method and the last one is a five-point 20th order method. In terms of computational point of view, our methods require four evaluations (one function and three first derivatives) to get fifth order, five evaluations (two functions and three derivatives) to get 10th order and six evaluations (three functions and three derivatives) to get 20th order. Hence, these methods have efficiency indexes of 1.495, 1.585 and 1.648, respectively which are better than the efficiency index of 1.316 of the third order method. We test the methods through some numerical experiments which show that the 20th order method is very efficient.

Keywords:

Non-linear equation; Multi-point iterative methods; Simpson's rule; Efficiency Index

1. Introduction

Newton's method has remained one of the best root-finding methods for solving nonlinear scalar equation

f (x) = 0 .

In last 15 years, many higher order variants of Newton's method have been developed. One of the them is a third order variant developed by Hasanov et al. [1] by approximating an indefinite integral in the Newton theorem by Simpson's formula. This method is a three-point method requiring 1 function and 3 first derivative evaluations and has an efficiency index of

3^{1 / 4} = 1.316

which is lower than

2^{1 / 2} = 1.414

of the 1-point Newton method. Recently, the order of many variants of Newton's method have been improved using the same number of functional evaluations by means of weight functions (see [2,3,4,5,6,7] and the references therein).

In this work, we improve the order of the three-point variant from three to five using weight function. Using polynomial interpolation, we develop four-point 10th order and five-point 20th order methods. Finally, we test the efficiency of the methods through numerical experiments.

2. Developments of the Methods

Let

x_{n + 1} = ψ (x_{n})

define an Iterative Function (I.F.).

Definition 1. [8] If the sequence

{x_{n}}

tends to a limit

x^{*}

in such a way that

lim_{n \to \infty} \frac{x_{n + 1} - x^{*}}{{(x_{n} - x^{*})}^{p}} = C

for

p \geq 1

, then the order of convergence of the sequence is said to be p, and C is known as the asymptotic error constant. If

p = 1

p = 2

p = 3

, the convergence is said to be linear, quadratic or cubic, respectively.

Let

e_{n} = x_{n} - x^{*}

, then the relation

e_{n + 1} = C e_{n}^{p} + O (e_{n}^{p + 1}) = O (e_{n}^{p}) .

(1)

is called the error equation. The value of p is called the order of convergence of the method.

Definition 2. [9] The Efficiency Index is given by

E I = p^{\frac{1}{d}},

(2)

where d is the total number of new function evaluations (the values of f and its derivatives) per iteration.

Let

x_{n + 1}

be determined by new information at

x_{n}, ϕ_{1} (x_{n}), . . ., ϕ_{i} (x_{n}), i \geq 1

No old information is reused. Thus,

x_{n + 1} = ψ (x_{n}, ϕ_{1} (x_{n}), . . ., ϕ_{i} (x_{n})) .

(3)

Then ψ is called a multipoint I.F without memory.

Kung-Traub Conjecture [10]

Let ψ be an I.F. without memory with d evaluations. Then

p (ψ) \leq p_{O p t} = 2^{d - 1},

(4)

where

p_{o p t}

is the maximum order.

The second order Newton (also called Newton-Raphson) I.F. (2^ndNR) is given by

ψ_{2^{n d} N R} (x) = x - u (x), u (x) = \frac{f (x)}{f^{'} (x)} .

(5)

The 2^ndNR I.F. is a is 1-point I.F. with 2 functions evaluations and it satisfies the Kung-Traub conjecture

d = 2

Thus,

E I_{2^{n d} N R} = 1.414

The Newton I.F. can be constructed from its local linear model, of the function

f (x)

, which is the tangent drawn to the function

f (x)

at the current point x. The local linear model at x is

L (x) = f (x) + f^{'} (x) (ψ - x) .

(6)

This local linear model can be interpreted from the viewpoint of the Newton Theorem:

f (ψ) = f (x) + I_{N T}, where I_{N T} = \int_{x}^{ψ} f^{'} (υ) d υ .

(7)

Weerakoon and Fernando [11] showed that if the indefinite integral

I_{N T}

is approximated by the rectangle:

I_{N T} \approx f^{'} (x) (ψ - x)

, the Newton I.F. is obtained by setting

L (x) = 0

.Hasanov et al. [1] obtained a new linear model

L_{1} (x) = f (x) + \frac{1}{6} (f^{'} (x) + 4 f^{'} (\frac{x + ψ}{2}) + f^{'} (ψ)) (ψ - x)

(8)

by approximating

I_{N T}

by Simpson's formula:

I_{N T} \approx \frac{1}{6} (f^{'} (x) + 4 f^{'} (\frac{x + ψ}{2}) + f^{'} (ψ))

Solving the new linear model, they obtained the implicit I.F.

ψ (x) = x - \frac{6 f (x)}{f^{'} (x) + 4 f^{'} (\frac{x + ψ (x)}{2}) + f^{'} (ψ (x))} .

(9)

Using the Newton I.F. to estimate

ψ (x)

in the first derivative by

ψ_{2^{n d} N R} (x)

, they obtained the

3^{r d} 3 p V S

I.F.:

ψ_{3^{r d} 3 p V S} (x) = x - \frac{f (x)}{D (x)}, D (x) = \frac{1}{6} (f^{'} (x) + 4 f^{'} (\frac{x + ψ_{2^{n d} N R} (x)}{2}) + f^{'} (ψ_{2^{n d} N R} (x)))

(10)

The

3^{r d} 3 p V S

I.F. is a special case of the Frontini-Sormani family of third order I.F.s from quadrature rule [12]. It was extended to systems of equations in [13]. However this I.F. is considered as inefficient. According to Kung-Traub conjecture, the optimal order of the I.F. with

d = 4

is eight. In fact, we can have optimal three-point eighth order I.F.s with 4 function evaluations or with 3 function and 1 first derivative evaluations (see [5,14] and the references therein).

However, we can achieve only a maximum of sixth order with I.F.s with 2 function and 2 first derivative evaluations. The question we now pose: What is the maximum order we can achieve with I.F.s with 1 function and 3 first derivative evaluations?

Let us define

τ = \frac{f^{'} (ψ_{2^{n d} N R} (x))}{f^{'} (x)}

. We improve the

3^{r d} 3 p V S

I.F. using weight function to obtain a three-point fifth order I.F. (

5^{t h} 3 p V S

ψ_{5^{t h} 3 p V S} (x) = x - \frac{f (x)}{D (x)} \times H (τ), H (τ) = 1 + \frac{1}{4} {(τ - 1)}^{2} - \frac{3}{8} {(τ - 1)}^{3}

(11)

It is remarkable that with the same number of functional evaluations we have improved the efficiency index from

I E_{3^{r d} 3 p V S} = 1.316

I E_{5^{t h} 3 p V S} = 5^{1 / 4} = 1.495

. However, the maximum order we could achieve I.F.s with 1 function and 3 first derivative evaluations is five. Babajee [2] developed a technique to improve the order of old methods.

Theorem 3 (Babajee's theorem for improving the order of old methods). [2] Let a sufficiently smooth function

f : D \subset ℝ \to ℝ

has a simple root

x^{*}

in the open interval D. Let

ψ_{o l d} (x)

be an Iteration Function (I.F.) of order p. Then the I.F. defined as

ψ_{n e w} (x) = ψ_{o l d} (x) - G \times f (ψ_{o l d} (x))

is of local convergence of order

p + q

if G is a function satisfying the error equation

G = \frac{1}{f^{'} (x^{*})} (1 + C_{G} e^{q} + O (e^{q + 1})),

where

C_{G}

is a constant.

Suppose that the error equation of the old I.F. is given by

e_{o l d} = ψ_{o l d} (x) - x^{*} = C_{o l d} e^{p} + . . .

Then, the error equation of the new I.F. is given by

e_{n e w} = ψ_{n e w} (x) - x^{*} = - C_{G} C_{o l d} e^{p + q} - c_{2} {C_{o l d}}^{2} e^{2 p} + . . .,

(12)

where

c_{j} = \frac{f^{(j)} (x^{*})}{j! f^{'} (x^{*})}, j = 1, 2, 3 . .

Usually, G is a weight function or an approximation to

\frac{1}{f^{'} (ψ_{o l d} (x))}

obtained from polynomial interpolation.

Using Babajee's theorem and applying Newton I.F., we obtain a 10th order I.F. (10^thVS):

ψ_{10^{t h} V S} (x) = ψ_{5^{t h} 3 p V S} (x) - \frac{f (ψ_{5^{t h} 3 p V S} (x))}{f^{'} (ψ_{5^{t h} 3 p V S} (x))}

However, we need to compute two more function evaluations. So we estimate

f^{'} (ψ_{5^{t h} 3 p V S} (x))

by the following polynomial:

q_{1} (t) = f (x) + f^{'} (x) (t - x) + a_{1} {(t - x)}^{2} + a_{2} {(t - x)}^{3} + a_{3} {(t - x)}^{4} .

(13)

which satisfies the following conditions

\begin{matrix} q_{1} (ψ_{5^{t h} 3 p V S} (x)) = f (ψ_{5^{t h} 3 p V S} (x)), q_{1}^{'} (ψ_{2^{n d} N R} (x)) = f^{'} (ψ_{2^{n d} N R} (x)), \\ q_{1}^{'} (\frac{x + ψ_{2^{n d} N R} (x)}{2}) = f^{'} (\frac{x + ψ_{2^{n d} N R} (x)}{2}) . \end{matrix}

(14)

Let

\begin{matrix} A_{1} = ψ_{5^{t h} 3 p V S} (x) - x, A_{2} = ψ_{2^{n d} N R} (x) - x, A_{3} = \frac{x + ψ_{2^{n d} N R} (x)}{2} - x, \\ B_{1} = f [ψ_{5^{t h} 3 p V S} (x), x, x], B_{2} = f^{'} [ψ_{2^{n d} N R} (x), x], B_{3} = f^{'} [\frac{x + ψ_{2^{n d} N R} (x)}{2}, x], \end{matrix}

where we define the divided differences:

f [y, x] = \frac{f (y) - f (x)}{y - x}, f^{'} [y, x] = \frac{f^{'} (y) - f^{'} (x)}{y - x}, f [y, x, x] = \frac{f [y, x] - f^{'} (x)}{y - x}

Equation (14) reduces, after using the divided differences, to a system of 3 linear equations in matrix form:

(\begin{matrix} 1 & A_{1} & {A_{1}}^{2} \\ 2 & 3 A_{2} & 4 {A_{2}}^{2} \\ 2 & 3 A_{3} & 4 {A_{3}}^{2} \end{matrix}) (\begin{matrix} a_{1} \\ a_{2} \\ a_{3} \end{matrix}) = (\begin{matrix} B_{1} \\ B_{2} \\ B_{3} \end{matrix})

whose solutions are given by

\begin{matrix} a_{1} & = \frac{1}{2} \frac{- 3 {A_{1}}^{2} A_{3} B_{2} + 3 {A_{1}}^{2} A_{2} B_{3} + 4 A_{1} {A_{3}}^{2} B_{2} - 4 A_{1} {A_{2}}^{2} B_{3} - 12 A_{2} {A_{3}}^{2} B_{1} + 12 {A_{2}}^{2} A_{3} B_{1}}{- 4 A_{1} {A_{2}}^{2} + 3 {A_{1}}^{2} A_{2} + 4 A_{1} {A_{3}}^{2} - 3 {A_{1}}^{2} A_{3} - 6 A_{2} {A_{3}}^{2} + 6 {A_{2}}^{2} A_{3}}, \\ a_{2} & = \frac{{A_{1}}^{2} B_{2} - {A_{1}}^{2} B_{3} - 2 {A_{3}}^{2} B_{2} - 4 B_{1} {A_{2}}^{2} + 2 {A_{2}}^{2} B_{3} + 4 B_{1} {A_{3}}^{2}}{- 4 A_{1} {A_{2}}^{2} + 3 {A_{1}}^{2} A_{2} + 4 A_{1} {A_{3}}^{2} - 3 {A_{1}}^{2} A_{3} - 6 A_{2} {A_{3}}^{2} + 6 {A_{2}}^{2} A_{3}}, \\ a_{3} & = - \frac{1}{2} \frac{2 A_{1} B_{2} - 2 A_{1} B_{3} + 6 B_{1} A_{3} - 3 A_{3} B_{2} - 6 B_{1} A_{2} + 3 A_{2} B_{3}}{- 4 A_{1} {A_{2}}^{2} + 3 {A_{1}}^{2} A_{2} + 4 A_{1} {A_{3}}^{2} - 3 {A_{1}}^{2} A_{3} - 6 A_{2} {A_{3}}^{2} + 6 {A_{2}}^{2} A_{3}} . \end{matrix}

So,

q_{1}^{'} (ψ_{5^{t h} 3 p V S} (x)) = f^{'} (x) + 2 a_{1} (ψ_{5^{t h} 3 p V S} (x) - x) + 3 a_{2} {(ψ_{5^{t h} 3 p V S} (x) - x)}^{2} + 4 a_{3} {(ψ_{5^{t h} 3 p V S} (x) - x)}^{3}

Using Babajee's theorem with

p = q = 5

, we can obtain a four-point 10th-order I.F.s (10^th4pVS):

\begin{matrix} ψ_{10^{t h} 4 p V S} (x) = ψ_{5^{t h} 3 p V S} (x) - G_{1} \times f (ψ_{5^{t h} 3 p V S} (x)), G_{1} = \frac{1}{q_{1}^{'} (ψ_{5^{t h} 3 p V S} (x))} \end{matrix}

(15)

The efficiency index has now increased since

I E_{10^{t h} 4 p V S} = 10^{1 / 5} = 1.585

with 2 function and 3 first derivative evaluations. We point out that the optimal order of a four-point I.F. with 5 functional evaluations is 16 but this can be achieved with either 5 function evaluations or 4 function and 1 first derivative evaluations (see [5,14] and the references therein).

Using a similar approach to estimate

f^{'} (ψ_{10^{t h} 4 p V S} (x))

by the following polynomial:

q_{2} (t) = f (x) + f^{'} (x) (t - x) + b_{1} {(t - x)}^{2} + b_{2} {(t - x)}^{3} + b_{3} {(t - x)}^{4} + b_{4} {(t - x)}^{5}

(16)

which satisfies the following conditions

\begin{matrix} q_{2} (ψ_{5^{t h} 3 p V S} (x)) = f (ψ_{5^{t h} 3 p V S} (x)), q_{2} (ψ_{10^{t h} 4 p V S} (x)) = f (ψ_{10^{t h} 4 p V S} (x)), \\ q_{2}^{'} (ψ_{2^{n d} N R} (x)) = f^{'} (ψ_{2^{n d} N R} (x)), q_{2}^{'} (\frac{x + ψ_{2^{n d} N R} (x)}{2}) = f^{'} (\frac{x + ψ_{2^{n d} N R} (x)}{2}) . \end{matrix}

(17)

Furthermore, let

A_{4} = ψ_{10^{t h} 3 p V S} (x) - x, B_{4} = f [ψ_{10^{t h} 4 p V S} (x), x, x]

. Equation (17) reduces, after using the divided differences, to a system of 4 linear equations in matrix form:

(\begin{matrix} 1 & A_{1} & {A_{1}}^{2} & {A_{1}}^{3} \\ 2 & 3 A_{2} & 4 {A_{2}}^{2} & 5 {A_{2}}^{3} \\ 2 & 3 A_{3} & 4 {A_{3}}^{2} & 5 {A_{3}}^{3} \\ 1 & A_{4} & {A_{4}}^{2} & {A_{4}}^{3} \end{matrix}) (\begin{matrix} b_{1} \\ b_{2} \\ b_{3} \\ b_{4} \end{matrix}) = (\begin{matrix} B_{1} \\ B_{2} \\ B_{3} \\ B_{4} \end{matrix})

whose solutions are given by

\begin{matrix} b = - 10 A_{1} {A_{4}}^{2} {A_{2}}^{3} + 10 A_{1} {A_{4}}^{2} {A_{3}}^{3} - 10 {A_{1}}^{2} A_{4} {A_{3}}^{3} + 15 {A_{1}}^{2} A_{2} {A_{3}}^{3} - 6 {A_{1}}^{2} A_{2} {A_{4}}^{3} - 8 {A_{2}}^{2} A_{4} {A_{1}}^{3} \\ + 20 {A_{2}}^{2} A_{4} {A_{3}}^{3} - 20 {A_{2}}^{2} A_{1} {A_{3}}^{3} + 8 {A_{2}}^{2} A_{1} {A_{4}}^{3} + 12 {A_{2}}^{2} A_{3} {A_{1}}^{3} - 12 {A_{2}}^{2} A_{3} {A_{4}}^{3} + 6 {A_{4}}^{2} A_{2} {A_{1}}^{3} \\ - 15 {A_{4}}^{2} A_{2} {A_{3}}^{3} + 10 {A_{1}}^{2} A_{4} {A_{2}}^{3} + 6 {A_{1}}^{2} A_{3} {A_{4}}^{3} - 15 {A_{1}}^{2} A_{3} {A_{2}}^{3} + 8 {A_{3}}^{2} A_{4} {A_{1}}^{3} + 12 {A_{3}}^{2} A_{2} {A_{4}}^{3} \\ - 20 {A_{3}}^{2} A_{4} {A_{2}}^{3} - 8 {A_{3}}^{2} A_{1} {A_{4}}^{3} + 20 {A_{3}}^{2} A_{1} {A_{2}}^{3} - 12 {A_{3}}^{2} A_{2} {A_{1}}^{3} - 6 {A_{4}}^{2} A_{3} {A_{1}}^{3} + 15 {A_{4}}^{2} A_{3} {A_{2}}^{3}, \end{matrix}

\begin{matrix} b_{2} = \frac{1}{b} (4 {A_{3}}^{2} {A_{4}}^{3} B_{2} - 8 {A_{3}}^{2} {A_{4}}^{3} B_{1} - 5 {A_{3}}^{3} {A_{4}}^{2} B_{2} + 10 {A_{3}}^{3} {A_{4}}^{2} B_{1} - 4 {A_{2}}^{2} {A_{4}}^{3} B_{3} + 8 {A_{2}}^{2} {A_{4}}^{3} B_{1} \\ + 20 B_{4} {A_{2}}^{2} {A_{3}}^{3} - 20 B_{1} {A_{2}}^{2} {A_{3}}^{3} + 5 {A_{2}}^{3} {A_{4}}^{2} B_{3} - 10 {A_{2}}^{3} {A_{4}}^{2} B_{1} - 20 {A_{2}}^{3} {A_{3}}^{2} B_{4} \\ + 20 {A_{2}}^{3} {A_{3}}^{2} B_{1} + 2 {A_{1}}^{2} {A_{4}}^{3} B_{3} - 2 {A_{1}}^{2} {A_{4}}^{3} B_{2} - 10 {A_{1}}^{2} {A_{3}}^{3} B_{4} + 5 {A_{1}}^{2} {A_{3}}^{3} B_{2} + 10 {A_{1}}^{2} {A_{2}}^{3} B_{4} \\ - 5 {A_{1}}^{2} {A_{2}}^{3} B_{3} - 2 {A_{1}}^{3} {A_{4}}^{2} B_{3} + 2 {A_{1}}^{3} {A_{4}}^{2} B_{2} + 8 {A_{1}}^{3} {A_{3}}^{2} B_{4} \\ - 4 {A_{1}}^{3} {A_{3}}^{2} B_{2} - 8 {A_{1}}^{3} {A_{2}}^{2} B_{4} + 4 {A_{1}}^{3} {A_{2}}^{2} B_{3}), \\ b_{3} = \frac{1}{b} (- 3 A_{3} {A_{4}}^{3} B_{2} + 6 A_{3} {A_{4}}^{3} B_{1} + 5 {A_{3}}^{3} A_{4} B_{2} - 10 {A_{3}}^{3} A_{4} B_{1} + 3 A_{2} {A_{4}}^{3} B_{3} - 6 A_{2} {A_{4}}^{3} B_{1} \\ - 15 A_{2} B_{4} {A_{3}}^{3} + 15 B_{1} A_{2} {A_{3}}^{3} - 5 {A_{2}}^{3} A_{4} B_{3} + 10 {A_{2}}^{3} A_{4} B_{1} + 15 {A_{2}}^{3} A_{3} B_{4} - 15 {A_{2}}^{3} A_{3} B_{1} \\ - 2 A_{1} {A_{4}}^{3} B_{3} + 2 A_{1} {A_{4}}^{3} B_{2} + 10 A_{1} {A_{3}}^{3} B_{4} - 5 A_{1} {A_{3}}^{3} B_{2} - 10 A_{1} {A_{2}}^{3} B_{4} + 5 A_{1} {A_{2}}^{3} B_{3} \\ + 2 {A_{1}}^{3} A_{4} B_{3} - 2 {A_{1}}^{3} A_{4} B_{2} - 6 {A_{1}}^{3} A_{3} B_{4} + 3 {A_{1}}^{3} A_{3} B_{2} + 6 {A_{1}}^{3} A_{2} B_{4} - 3 {A_{1}}^{3} A_{2} B_{3}), \\ b_{4} = \frac{1}{b} (- 3 {A_{4}}^{2} A_{2} B_{3} - 8 {A_{2}}^{2} A_{4} B_{1} - 2 {A_{1}}^{2} A_{4} B_{3} - 3 {A_{1}}^{2} A_{3} B_{2} + 8 {A_{2}}^{2} A_{1} B_{4} + 4 {A_{2}}^{2} A_{4} B_{3} \\ - 4 {A_{2}}^{2} A_{1} B_{3} - 6 {A_{1}}^{2} A_{2} B_{4} + 12 {A_{2}}^{2} A_{3} B_{1} + 2 {A_{1}}^{2} A_{4} B_{2} + 2 A_{1} {A_{4}}^{2} B_{3} + 3 {A_{1}}^{2} A_{2} B_{3} \\ - 12 {A_{2}}^{2} A_{3} B_{4} + 6 {A_{4}}^{2} A_{2} B_{1} - 2 A_{1} {A_{4}}^{2} B_{2} + 6 {A_{1}}^{2} A_{3} B_{4} + 8 {A_{3}}^{2} A_{4} B_{1} - 4 {A_{3}}^{2} A_{4} B_{2} \\ + 12 {A_{3}}^{2} A_{2} B_{4} + 4 B_{2} A_{1} {A_{3}}^{2} - 8 {A_{3}}^{2} A_{1} B_{4} - 12 B_{1} A_{2} {A_{3}}^{2} - 6 {A_{4}}^{2} A_{3} B_{1} + 3 {A_{4}}^{2} A_{3} B_{2}) . \end{matrix}

So,

\begin{matrix} q_{2}^{'} (ψ_{10^{t h} 4 p V S} (x)) & = f^{'} (x) + 2 b_{1} (ψ_{10^{t h} 4 p V S} (x) - x) + 3 b_{2} {(ψ_{10^{t h} 4 p V S} (x) - x)}^{2} \\ + 4 b_{3} {(ψ_{10^{t h} 4 p V S} (x) - x)}^{3} + 5 b_{4} {(ψ_{10^{t h} 4 p V S} (x) - x)}^{4} . \end{matrix}

Furthermore, using Babajee's theorem with

p = q = 10

, we can obtain a five-point 20th-order I.F.s (20^th5pVS):

\begin{matrix} ψ_{20^{t h} 5 p V S} (x) = ψ_{10^{t h} 4 p V S} (x) - G_{2} \times f (ψ_{10^{t h} 4 p V S} (x)), G_{2} = \frac{1}{q_{2}^{'} (ψ_{10^{t h} 4 p V S} (x))} \end{matrix}

(18)

The efficiency index has now increased to

I E_{20^{t h} 5 p V S} = 20^{1 / 6} = 1.648

with 2 function and 3 first derivative evaluations.

3. Convergence Analysis

In this section, we prove the convergence analysis of the three I.F.s (11), (15) and (18).

Theorem 4. Let a sufficiently smooth function

f : D \subset ℝ \to ℝ

has a simple root

x^{*}

in the open interval D which contains

x_{0}

as an initial approximation to

x^{*}

. Then the

5^{t h} 3 p V S

I.F (11) is of local fifth-order convergence , the

10^{t h} 4 p V S

I.F (15) is of local 10th-order convergence and the

20^{t h} 5 p V S

I.F (18) is of local 20th-order convergence.

Proof. Let

e_{n} = x - x^{*}

Using the Taylor series and the symbolic software such as Maple we have

f (x) = f^{'} (x^{*}) [e_{n} + c_{2} e_{n}^{2} + c_{3} e_{n}^{3} + c_{4} e_{n}^{4} + ...]

(19)

and

f^{'} (x) = f^{'} (x^{*}) [1 + 2 c_{2} e_{n} + 3 c_{3} e_{n}^{2} + 4 c_{4} e_{n}^{3} + ...]

so that

u (x) = e_{n} - c_{2} e_{n}^{2} + 2 (c_{2}^{2} - c_{3}) e_{n}^{3} + (7 c_{2} c_{3} - 4 c_{2}^{3} - 3 c_{4}) e_{n}^{4} + ... .

Now

ψ_{2^{n d} N R} (x) = x^{*} + c_{2} {e_{n}}^{2} + (2 c_{3} - 2 {c_{2}}^{2}) {e_{n}}^{3} + (3 c_{4} - 7 c_{2} c_{3} + 4 {c_{2}}^{3}) {e_{n}}^{4} + ...,

so that

τ = \frac{f^{'} (ψ_{2^{n d} N R} (x))}{f^{'} (x)} = 1 - c_{2} e_{n} + (6 {c_{2}}^{2} - 3 c_{3}) {e_{n}}^{2} + (16 c_{2} c_{3} - 16 {c_{2}}^{3} - 4 c_{4}) {e_{n}}^{3} + O ({e_{n}}^{4}),

\begin{matrix} H (τ) & = 1 + {c_{2}}^{2} {e_{n}}^{2} + (3 c_{2} c_{3} - 3 {c_{2}}^{3}) {e_{n}}^{3} + O ({e_{n}}^{4}) \end{matrix}

(20)

and

\begin{matrix} D (x) & = f^{'} (x^{*}) (1 + c_{2} e_{n} + ({c_{2}}^{2} + c_{3}) {e_{n}}^{2} + (3 c_{2} c_{3} - 2 {c_{2}}^{3} + c_{4}) {e_{n}}^{3} + O ({e_{n}}^{4})) . \end{matrix}

(21)

Substituting Equations (19), (20) and (21) into Equation (11), we obtain, after simplifications,

\begin{matrix} ψ_{5^{t h} 3 p V S} (x) - x^{*} = C_{5^{t h} 3 p V S} {e_{n}}^{5} + O ({e_{n}}^{6}), C_{5^{t h} 3 p V S} = - \frac{1}{4} {c_{3}}^{2} - \frac{1}{2} c_{3} {c_{2}}^{2} + 9 {c_{2}}^{4} . \end{matrix}

(22)

Now, using Maple, we have

G_{1} = \frac{1}{f^{'} (x^{*})} (1 + C_{G_{1}} {e_{n}}^{2} + O ({e_{n}}^{3})), C_{G_{1}} = - 18 {c_{2}}^{5} + c_{3} {c_{2}}^{3} + 1 / 2 c_{2} {c_{3}}^{2} .

Using Babajee's theorem with

p = q = 5

, we have

\begin{matrix} ψ_{10^{t h} 4 p V S} (x) - x^{*} \\ = (- C_{G_{1}} C_{5^{t h} 3 p V S} - c_{2} C_{5^{t h} 3 p V S}^{2}) {e_{n}}^{10} + O ({e_{n}}^{11}) \\ = C_{10^{t h} 4 p V S} {e_{n}}^{10} + O ({e_{n}}^{11}), C_{10^{t h} 4 p V S} = - \frac{17}{4} {c_{3}}^{2} {c_{2}}^{5} - 9 c_{3} {c_{2}}^{7} + \frac{1}{4} {c_{3}}^{3} {c_{2}}^{3} + 81 {c_{2}}^{9} + \frac{1}{16} c_{2} {c_{3}}^{4} . \end{matrix}

(23)

Using Maple,

\begin{matrix} G_{2} & = \frac{1}{f^{'} (x^{*})} (1 + C_{G_{2}} {e_{n}}^{10} + O ({e_{n}}^{11})), \\ C_{G_{2}} & = - 162 {c_{2}}^{10} + 18 c_{3} {c_{2}}^{8} + \frac{17}{2} {c_{3}}^{2} {c_{2}}^{6} - \frac{1}{2} {c_{3}}^{3} {c_{2}}^{4} - \frac{1}{8} {c_{3}}^{4} {c_{2}}^{2} . \end{matrix}

Using Babajee's theorem with

p = q = 10

, we have

\begin{matrix} ψ_{20^{t h} 5 p V S} (x) - x^{*} \\ = (- C_{G_{2}} C_{10^{t h} 4 p V S} - c_{2} C_{10^{t h} 4 p V S}^{2}) {e_{n}}^{20} + O ({e_{n}}^{21}) \\ = C_{20^{t h} 5 p V S} {e_{n}}^{20} + O ({e_{n}}^{21}), \\ C_{20^{t h} 5 p V S} = 6561 {c_{2}}^{19} - 1458 c_{3} {c_{2}}^{17} - \frac{1215}{2} {c_{3}}^{2} {c_{2}}^{15} + 117 {c_{3}}^{3} {c_{2}}^{13} + \frac{379}{16} {c_{3}}^{4} {c_{2}}^{11} - \frac{13}{4} {c_{3}}^{5} {c_{2}}^{9} \\ - \frac{15}{32} {c_{3}}^{6} {c_{2}}^{7} + \frac{1}{32} {c_{3}}^{7} {c_{2}}^{5} + \frac{1}{256} {c_{3}}^{8} {c_{2}}^{3} \end{matrix}

(24)

4. Numerical Examples

In this section, we give numerical results on some test functions to compare the efficiency of the proposed methods (5^th3pVS, 10^th4pVS and 20^th5pVS) with 3^rd3pVS and Newton's method (2^ndNR). Numerical computations have been carried out in the MATLAB software rounding to 1000 significant digits. Depending on the precision of the computer, we use the stopping criteria for the iterative process

E_{n} = | x_{n} - x_{n - 1} | < ϵ

where

ϵ = 10^{- 100}

. Let N be the number of iterations required for convergence. The test functions and their simple zeros are given below:

\begin{matrix} f_{1} (x) & = sin (2 cos x) - 1 - x^{2} + e^{sin (x^{3})}, x^{*} = - 0.7848959876612125352 . . . \\ f_{2} (x) & = x^{3} + 4 x^{2} - 10, x^{*} = 1.3652300134140968457 . . . \\ f_{3} (x) & = (x + 2) e^{x} - 1, x^{*} = - 0.4428544010023885831 . . . \\ f_{4} (x) & = \sqrt{x} - cos x, x^{*} = 0.6417143708728826583 . . . \end{matrix}

Table 1 shows the corresponding results for

f_{1} (x)

f_{4} (x)

. It can be found that the 20^th5pVS I.F. converge in less iterations with the least error

E_{N}

for the functions and their starting points considered. This I.F. takes at most half the number of iterations than that of the

2^{n d} N R

I.F. to converge. The number of iterations and the error are smaller when we choose a starting point close to the root.

Table 1. Results for the 5^th3pVS, 10^th4pVS and 20^th5pVS Iterative Functions (I.F.s) for

f_{1} (x)

f_{4} (x)

along with

2^{n d} N R

and 3^rd3pVS I.F.s

**Table 1.** Results for the 5^th3pVS, 10^th4pVS and 20^th5pVS Iterative Functions (I.F.s) for $f_{1} (x)$ - $f_{4} (x)$ along with $2^{n d} N R$ and 3^rd3pVS I.F.s
$f (x)$	$x_{0}$	$2^{n d} N R$		$3^{r d} 3 p V S$		$5^{t h} 3 p V S$		$10^{t h} 4 p V S$		$20^{t h} 5 p V S$
		N	$E_{N}$	N	$E_{N}$	N	$E_{N}$	N	$E_{N}$	N	$E_{N}$
$f_{1} (x)$	$- 0.7$	7	1.09e-074	5	2.58e-094	4	1.04e-111	3	6.96e-077	3	3.31e-299
	$- 1$	7	9.07e-061	5	1.65e-076	4	9.04e-095	3	8.96e-068	3	5.99e-249
$f_{2} (x)$	$1.6$	7	7.80e-063	5	2.07e-079	4	5.53e-097	3	2.53e-080	3	9.88e-324
	$2.5$	8	3.21e-053	6	1.29e-100	5	1.01e-173	4	2.57e-302	3	1.024e-125
$f_{3} (x)$	$- 0.3$	7	7.80e-066	5	3.63e-083	4	1.62e-102	3	4.90e-071	3	1.18e-282
	$- 0.8$	8	4.34e-073	6	6.08e-138	5	2.24e-144	4	7.38 e-190	3	3.88e-092
$f_{4} (x)$	$0.7$	6	1.41e-067	4	5.59e-057	4	9.12e-222	3	1.08e-108	3	0
	2	7	1.52e-062	5	8.42e-087	4	1.38e-069	4	9.78e-238	3	3.70e-123

5. Conclusion

In this work, we have developed three-point fifth order, four-point 10th order and five-point 20th order methods using weight functions and polynomial interpolation. It is clear that our proposed methods require only four evaluations per iterative step to obtain fifth order method, five evaluations per iterative step to get 10th order and six evaluations per iterative step to get 20th order. We have thus increased the order of convergence to five, 10 and 20 compared to the third order method suggested in [1] with efficiency indexes EI =1.495, EI =1.585 and EI = 1.648, respectively. Our proposed methods are better than Newton's method in terms of efficiency index (EI =1.4142). Numerical results show that the five-point 20th order method is the most efficient.

Acknowledgments

The author is thankful to the anonymous reviewers for their valuable comments to improve the readability of the paper.

Conflicts of Interest

The author declares no conflict of interest.

References

Hasanov, V.I.; Ivanov, I.G.; Nedzhibov, G.H. A new modification of Newton's method. Appl. Math. Eng. 2002, 27, 278–286. [Google Scholar]
Babajee, D.K.R. Several improvements of the 2-point third order midpoint iterative method using weight functions. Appl. Math. Comput. 2012, 218, 7958–7966. [Google Scholar] [CrossRef]
Babajee, D.K.R. On a two-parameter Chebyshev-Halley-like family of optimal two-point fourth order methods free from second derivatives. Afr. Mat. 2014. [Google Scholar] [CrossRef]
Babajee, D.K.R.; Jaunky, V.C. Applications of higher-order optimal Newton Secant iterative methods in ocean acidification and investigation of long-run implications of CO₂ emissions on alkalinity of seawater. ISRN Appl. Math. 2013. [Google Scholar] [CrossRef]
Babajee, D.K.R.; Thukral, R. On a 4-point sixteenth-order King family of iterative methods for solving nonlinear equations. Int. J. Math. Math. Sci. 2012. [Google Scholar] [CrossRef]
Sharifi, M.; Babajee, D.K.R.; Soleymani, F. Finding solution of nonlinear equations by a class of optimal methods. Comput. Math. Appl. 2012, 63, 764–774. [Google Scholar] [CrossRef]
Soleymani, F.; Khratti, S.K.; Karimi Vanani, S. Two new classes of optimal Jarratt-type fourth-order methods. Appl. Math. Lett. 2011, 25, 847–853. [Google Scholar] [CrossRef]
Wait, R. The Numerical Solution of Algebraic Equations; John Wiley & Sons: New York, NY, USA, 1979. [Google Scholar]
Ostrowski, A.M. Solutions of Equations and System of Equations; Academic Press: San Diego, CA, USA, 1960. [Google Scholar]
Kung, H.T.; Traub, J.F. Optimal order of one-point and multipoint iteration. J. Assoc. Comput. Mach. 1974, 21, 643–651. [Google Scholar] [CrossRef]
Weerakoon, S.; Fernando, T.G.I. A variant of Newton's method with accelerated third order convergence. Appl. Math. Lett. 2000, 13, 87–93. [Google Scholar] [CrossRef]
Frontini, M.; Sormani, E. Some variants of Newton's method with third-order convergence. Appl. Math. Comput. 2003, 140, 419–426. [Google Scholar] [CrossRef]
Cordero, A.; Torregrosa, J.R. Variants of Newton's method using fifth-order quadrature formulas. Appl. Math. Comput. 2007, 190, 686–698. [Google Scholar] [CrossRef]
Cordero, A.; Hueso, J.L.; Martinez, E.; Torregrosa, J.R. Generating optimal derivative free iterative methods for nonlinear equations by using polynomial interpolation. Appl. Math. Comput. 2013, 57, 1950–1956. [Google Scholar] [CrossRef]

© 2015 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Babajee, D.K.R. Some Improvements to a Third Order Variant of Newton’s Method from Simpson’s Rule. Algorithms 2015, 8, 552-561. https://doi.org/10.3390/a8030552

AMA Style

Babajee DKR. Some Improvements to a Third Order Variant of Newton’s Method from Simpson’s Rule. Algorithms. 2015; 8(3):552-561. https://doi.org/10.3390/a8030552

Chicago/Turabian Style

Babajee, Diyashvir Kreetee Rajiv. 2015. "Some Improvements to a Third Order Variant of Newton’s Method from Simpson’s Rule" Algorithms 8, no. 3: 552-561. https://doi.org/10.3390/a8030552

APA Style

Babajee, D. K. R. (2015). Some Improvements to a Third Order Variant of Newton’s Method from Simpson’s Rule. Algorithms, 8(3), 552-561. https://doi.org/10.3390/a8030552

Article Menu

Some Improvements to a Third Order Variant of Newton’s Method from Simpson’s Rule

Abstract

1. Introduction

2. Developments of the Methods

3. Convergence Analysis

4. Numerical Examples

5. Conclusion

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI