Open AccessArticle

An Optimal Order Method for Multiple Roots in Case of Unknown Multiplicity

Jai Prakash Jaiswal

^1,2,3

Department of Mathematics, Maulana Azad National Institute of Technology, Bhopal 462051, India

Faculty of Science, Barkatullah University, Bhopal, M.P. 462026, India

Regional Institute of Education, Bhopal, M.P. 462013, India

Algorithms 2016, 9(1), 10; https://doi.org/10.3390/a9010010

Submission received: 20 October 2015 / Revised: 7 January 2016 / Accepted: 18 January 2016 / Published: 22 January 2016

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

Download Versions Notes

Abstract

In the literature, recently, some three-step schemes involving four function evaluations for the solution of multiple roots of nonlinear equations, whose multiplicity is not known in advance, are considered, but they do not agree with Kung–Traub’s conjecture. The present article is devoted to the study of an iterative scheme for approximating multiple roots with a convergence rate of eight, when the multiplicity is hidden, which agrees with Kung–Traub’s conjecture. The theoretical study of the convergence rate is investigated and demonstrated. A few nonlinear problems are presented to justify the theoretical study.

Keywords:

nonlinear equations; iterative method; multiple root; unknown multiplicity; optimal convergence rate

1. Introduction

In the present report, we discuss an iterative scheme for calculating the approximate value of a multiple root ξ of a nonlinear equation

ψ (x) = 0

, in

R

. The modified Newton’s scheme [1] is probably the first method for calculating the estimated value of the multiple root when multiplicity m is available in advance, with a convergence rate twice that in some open set around ξ, under suitable regularity assumptions. For the same case, various schemes are presented in the literature by using numerous modes (one can see [2,3,4,5,6,7,8,9,10,11,12,13] for a few of them).

For the second case, i.e., when the multiplicity m is not available in advance, for calculating the multiple root of

ψ (x) = 0

, Traub [14] used the relation

f (x) = ψ (x) / ψ^{'} (x)

. In this stage, the problem of finding multiple roots of

ψ (x) = 0

is equivalent to calculating the simple root of

f (x) = 0

. However, for this substitution, Newton’s method involved the first and second derivatives also. To fend off these evaluations, King [15] used finite difference approximation.

Working with a parallel idea, Iyengar and Jain [16] developed two iterative methods of order three and four for approximating the multiple roots. The cubic convergence order scheme is as:

\begin{matrix} x_{n + 1} = x_{n} - \frac{f (x_{n})}{g (x_{n})} - \frac{f (x_{n} - \frac{f (x_{n})}{g (x_{n})})}{g (x_{n})} \end{matrix}

(1)

and the fourth-order method is expressed as:

\begin{matrix} x_{n + 1} = x_{n} - \frac{f (x_{n})}{g (x_{n})} - \frac{f (x_{n} - \frac{f (x_{n})}{g (x_{n})})}{g (x_{n})} - \frac{f (x_{n} - \frac{f (x_{n})}{g (x_{n})} - \frac{f (x_{n} - \frac{f (x_{n})}{g (x_{n})})}{g (x_{n})})}{g (x_{n})} \end{matrix}

(2)

where

g (x_{n}) = \frac{f (x_{n} + β f (x_{n})) - f (x_{n})}{β f (x_{n})}

Wu and Fu [17] also used a similar transformation and presented a uni-parametric scheme of second order for handling similar type problems. In addition, Wu et al. [18] prescribed another transformation given by:

\begin{matrix} f (x) = \frac{s i g n (ψ (x)) ρ}{s i g n (ψ (x + {s i g n (ψ (x)) | ψ (x) |}^{1 / m} {) - ψ (x)) ρ + ψ (x + s i g n (ψ (x)) | ψ (x) |}^{1 / m}) - ψ (x)} \end{matrix}

(3)

where

ρ = {ψ (x) | ψ (x) |}^{1 / m}

and m represents the multiplicity, and engaged the modified Steffensen’s method (see [19,20]):

\begin{matrix} x_{n + 1} = x_{n} - h_{n} \frac{f^{2} (x_{n})}{t f^{2} (x_{n}) + f (x_{n} + f (x_{n})) - f (x_{n})} \end{matrix}

(4)

for evaluating the estimated root of

f (x) = 0

, where

h_{n} (> 0)

is the iteration step size and

| t | < \infty

. Parida and Gupta [21] implied a different conversion:

\begin{matrix} f (x) & = & \frac{ψ^{2} (x)}{δ + ψ (x + ψ (x)) - ψ (x)}, & i f ψ (x) \neq 0 \\ = & 0, & i f ψ (x) = 0 \end{matrix}

(5)

where

δ = s i g n (ψ (x + ψ (x)) - ψ (x)) ψ^{2} (x)

, for converting the assignment of calculating multiple roots of ψ to find the simple root of f.

Yun [22] gave a new conversion of

ψ (x)

, which is expressed as follows:

\begin{matrix} H_{ϵ} (x) = x_{n} - \frac{ϵ ψ^{2} (x)}{ψ (x + ϵ ψ (x)) - ψ (x)} \end{matrix}

(6)

and considered ϵ in such a way that

m a x_{a \leq x \leq b} | ϵ ψ (x) | = δ

, as well as presented the iterative scheme of the following form:

\begin{matrix} x_{n + 1} = x_{n} - \frac{2 (x_{n + 1} - x_{n}) H_{ϵ} (x_{n})}{H_{ϵ} (2 x_{n} - x_{n - 1}) - H_{ϵ} (x_{n - 1})} \end{matrix}

(7)

To get a higher order method, Li et al. [23] proposed an iterative scheme for approximating multiple roots of

f (x) = 0

with fifth-order convergence, by using the transformation

f (x) = ψ (x_{n}) / ψ^{'} (x_{n})

, which is given as:

\begin{matrix} y_{n} & = & x_{n} - \frac{f^{2} (x_{n})}{f (x_{n} + f (x_{n})) - f (x_{n})} \\ u_{n} & = & y_{n} - \frac{f (y_{n}) f (x_{n})}{f (x_{n} + f (x_{n})) - f (x_{n})} \\ x_{n + 1} & = & u_{n} - \frac{f (u_{n})}{f [u_{n}, y_{n}] + f [z_{n}, x_{n}, x_{n}] (z_{n} - y_{n})} \end{matrix}

(8)

where

f [., .]

and

f [., ., .]

represent the first- and second-order divided differences of f, respectively.

More recently, by using the same transformation, Sharma and Bahl [24] proposed an iterative scheme with a convergence rate of six and expressed as:

\begin{matrix} y_{n} & = & x_{n} - \frac{f^{2} (x_{n})}{f (x_{n} + f (x_{n})) - f (x_{n})} \\ u_{n} & = & y_{n} - \frac{f (y_{n}) f (x_{n})}{f (x_{n} + f (x_{n})) - f (x_{n})} \\ x_{n + 1} & = & u_{n} - \frac{f (u_{n}) f [x_{n}, y_{n}]}{f [x_{n}, u_{n}] f [y_{n}, u_{n}]} \end{matrix}

(9)

The above mentioned fifth- and sixth-order methods involved four function evaluations

[f (x_{n}), f (x_{n} + f (x_{n})), f (y_{n}), f (u_{n})]

, and by Kung and Traub’s [25] conjecture, the optimal order should be eight. Motivated by this theory, we are going to present an optimal eighth-order method for multiple roots in case of unknown multiplicity: to our best knowledge, this is the first method of the optimal eighth order. Theoretically, its local rate of convergence is proven and finally supported by numerical testing.

2. Scheme and Analysis of the Local Convergence Rate

In this paper, we deal with the below mentioned conversion [14,26]:

\begin{matrix} f (x) & = & \frac{ψ (x)}{ψ^{'} (x)}, & i f ψ (x) \neq 0 \\ = & 0, & i f ψ (x) = 0 \end{matrix}

(10)

and employ a three-step Newton’s scheme given by:

\begin{matrix} y_{n} & = & x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})} \\ u_{n} & = & y_{n} - \frac{f (y_{n})}{f^{'} (y_{n})} \\ x_{n + 1} & = & u_{n} - \frac{f (u_{n})}{f^{'} (u_{n})} \end{matrix}

(11)

To escape the computations of primary differentiations of

f (x)

f (y (x))

and

f (u (x))

, we estimate them as mentioned below:

\begin{matrix} f^{'} (x_{n}) \approx \frac{f (z_{n}) - f (x_{n})}{f (x_{n})} = g_{1} (x_{n}, z_{n}) \end{matrix}

(12)

where

z_{n} = x_{n} + f (x_{n})

\begin{matrix} f^{'} (y_{n}) \approx \frac{f [x_{n}, y_{n}] f [y_{n}, z_{n}]}{f [x_{n}, z_{n}]} = g_{2} (x_{n}, y_{n}, z_{n}) \end{matrix}

(13)

and:

\begin{matrix} f^{'} (u_{n}) \approx b_{2} - b_{1} b_{4} = g_{3} (x_{n}, y_{n}, z_{n}, u_{n}) \end{matrix}

(14)

where

b_{1} = f (u_{n})

b_{4} = \frac{f [y_{n}, u_{n}, x_{n}] - f [y_{n}, u_{n}, z_{n}]}{f [y_{n}, z_{n}] - f [y_{n}, x_{n}]}

b_{3} = f [y_{n}, u_{n}, z_{n}] + b_{4} f [y_{n}, z_{n}]

b_{2} = f [y_{n}, u_{n}] - b_{3} (y_{n} - u_{n}) + f (y_{n}) b_{4}

(for more details, one can follow Equations (6) and (19), respectively, of [27]). Using these estimates of

f^{'} (x_{n})

f^{'} (y_{n})

and

f^{'} (u_{n})

, given by Equations (12)–(14), respectively, in the scheme Equation (11), we have the scheme given by:

\begin{matrix} y_{n} & = & x_{n} - \frac{f (x_{n})}{g_{1} (x_{n}, z_{n})} \\ u_{n} & = & y_{n} - \frac{f (y_{n})}{g_{2} (x_{n}, z_{n}, y_{n})} \\ x_{n + 1} & = & u_{n} - \frac{f (u_{n})}{g_{3} (x_{n}, z_{n}, y_{n}, u_{n})} \end{matrix}

(15)

In order to discuss the convergence analysis of the scheme defined by Equation (15), we are moving to validate the following result:

Theorem 1.

Assume that

f \in C^{8} (D)

(D \subseteq R \to R)

, and contains only one root

ξ \in D

, where D is an open subset of R and s is sufficiently large. If the starting guess

x_{0}

is near enough to ξ, the iterative scheme defined by Equation (15) has an optimal convergence rate of eight.

Proof of Theorem 1.

Let us suppose that

ψ (x)

can be expressed as:

\begin{matrix} ψ (x) = {(x - ξ)}^{m} h (x) \end{matrix}

(16)

where ξ is a multiple zero of

ψ (x) = 0

, with multiplicity m and

h (ξ) \neq 0

. According to Equation (16), we can write:

\begin{matrix} ψ^{'} (x) = m {(x - ξ)}^{m - 1} h (x) + {(x - ξ)}^{m} h^{'} (x) \end{matrix}

(17)

After taking the ratio of Equation (16) and (17), this can be written as:

\begin{matrix} f (x) = \frac{ψ (x)}{ψ^{'} (x)} = \frac{(x - ξ) h (x)}{m h (x) + (x - ξ) h^{'} (x)} \end{matrix}

(18)

It is clear from the above Equation (18) that the task of approximating the multiple zero of

ψ (x) = 0

is identical to the effort of estimating the simple root ξ of

f (x) = 0

. By virtue of Taylor’s series expansion, we can write:

\begin{matrix} h (x_{n}) = h (ξ) [1 + b_{1} e_{n} + b_{2} e_{n}^{2} + b_{3} e_{n}^{3} + b_{4} e_{n}^{4} + b_{5} e_{n}^{5} + b_{6} e_{n}^{6} + b_{7} e_{n}^{7} + b_{8} e_{n}^{8} + b_{9} e_{n}^{9} + o (e_{n}^{10})] \end{matrix}

(19)

where

b_{k} = \frac{h^{(k)} (ξ)}{k! h (ξ)}

k = 1, 2, \dots

and

e_{n} = x_{n} - ξ

. By Equation (19), we attain:

\begin{matrix} h^{'} (x_{n}) = h (ξ) [b_{1} + 2 b_{2} e_{n} + 3 b_{3} e_{n}^{2} + 4 b_{4} e_{n}^{3} + 5 b_{5} e_{n}^{4} + 6 b_{6} e_{n}^{5} + 7 b_{7} e_{n}^{6} + 8 b_{8} e_{n}^{7} + 9 b_{9} e_{n}^{8} + o (e_{n}^{9})] \end{matrix}

(20)

Using the expression Equations (19) and (20) in Equation (18) and then using symbolic computation software, Mathematica [28], we get:

\begin{matrix} f (x_{n}) & = \frac{e_{n} h (x_{n})}{m h (x_{n}) + e_{n} h^{'} (x_{n})} \\ = D_{1} e_{n} + D_{2} e_{n}^{2} + D_{3} e_{n}^{3} + D_{4} e_{n}^{4} + D_{5} e_{n}^{5} + D_{6} e_{n}^{6} + D_{7} e_{n}^{7} + D_{8} e_{n}^{8} + o (e_{n}^{9}) \end{matrix}

(21)

where:

\begin{matrix} D_{1} = \frac{1}{m}, D_{2} = \frac{- b_{1}}{m^{2}}, D_{3} = \frac{b_{1}^{2} + m b_{1}^{2} - 2 m b_{2}}{m^{2}} \end{matrix}

\begin{matrix} D_{4} = \frac{- b_{1}^{3} - 2 m b_{1}^{3} - m^{2} b_{1}^{3} + 4 m b_{1} b_{2} + 3 m^{2} b_{1} b_{2} - 3 m^{2} b_{3}}{m^{4}} \end{matrix}

\begin{matrix} D_{5} & = & \frac{1}{m^{5}} {{(1 + m)}^{3} b_{1}^{4} - 2 m (1 + m (3 + 2 m) b_{1}^{2} b_{2} + 2 m^{2} (3 + 2 m) b_{1} b_{3} \\ + 2 m^{2} ((2 + m) b_{2}^{2} - 2 m b_{4})} \end{matrix}

\begin{matrix} D_{6} & = & \frac{1}{m^{6}} {{- (1 + m)}^{4} b_{1}^{5} + m {(1 + m)}^{2} (8 + 5 m) b_{1}^{3} b_{2} - m^{2} (1 + m) (9 + 5 m) b_{1}^{2} b_{3} \\ + m^{2} b_{1} (- (2 + m) (6 + 5 m) b_{2}^{2} + m (8 + 5 m) b_{4}) + m^{3} ((12 + 5 m) b_{2} b_{3} - 5 m b_{5})} \end{matrix}

\begin{matrix} D_{7} & = & \frac{1}{m^{7}} {{(1 + m)}^{5} b_{1}^{6} - 2 m {(1 + m)}^{3} (5 + 3 m) b_{1}^{4} b_{2} + 6 m^{2} {(1 + m)}^{2} (2 + m) b_{1}^{3} b_{3} \\ + 3 m^{2} (1 + m) (2 + m) b_{1}^{2} ((4 + 3 m) b_{2}^{2} - 2 m b_{4}) \\ + 2 m^{3} b_{1} (- 2 (9 + m (11 + 3 m)) b_{2} b_{3} + m (5 + 3 m) b_{5}) \\ + m^{3} (- 2 {(2 + m)}^{2} b_{2}^{3} + 2 m (8 + 3 m) b_{2} b_{4} + 3 m ((3 + m) b_{3}^{2} - 2 m b_{6}))} \end{matrix}

\begin{matrix} D_{8} = \frac{1}{m^{8}} {{- (1 + m)}^{6} b_{1}^{7} + m {(1 + m)}^{4} (12 + 7 m) b_{1}^{5} b_{2} - m^{2} {(1 + m)}^{3} (15 + 7 m) b_{1}^{4} b_{3} \\ + m^{2} {(1 + m)}^{2} b_{1}^{3} (- 2 (2 + m) (10 + 7 m) b_{2}^{2} + m (16 + 7 m) b_{4}) \\ + m^{3} (1 + m) b_{1}^{2} (3 (24 + m (27 + 7 m)) b_{2} b_{3} - m (15 + 7 m) b_{5}) \\ + m^{3} b_{1} {((2 + m)}^{2} (8 + 7 m) b_{2}^{3} - 2 m (24 + 7 m (4 + m)) b_{2} b_{4} \\ + m (- (3 + m) (9 + 7 m) b_{3}^{2} + m (12 + 7 m) b_{6})) \\ + m^{4} (- (2 + m) (18 + 7 m) b_{2}^{2} b_{3} + m (20 + 7 m) b_{2} b_{5} + m ((24 + 7 m) b_{3} b_{4} - 7 m b_{7}))} \end{matrix}

By virtue of the relation Equation (21), we can obtain the Taylor’s series expansion for

f (z_{n})

, and then, using its expressions together with

f (x_{n})

, in the first sub-step of scheme Equation (15) and after simplifying, we have:

\begin{matrix} y_{n} = ξ + F_{2} e_{n}^{2} + F_{3} e_{n}^{3} + F_{4} e_{n}^{4} + F_{5} e_{n}^{5} + F_{6} e_{n}^{6} + F_{7} e_{n}^{7} + F_{8} e_{n}^{8} + o (e_{n}^{9}) \end{matrix}

(22)

where:

\begin{matrix} F_{2} = - \frac{(1 + m) b_{1}}{m^{2}}, F_{3} = \frac{((2 + 3 m + 2 m^{2}) b_{1}^{2} - 2 (1 + 3 m + 2 m^{2}) b_{2})}{m^{3}} \end{matrix}

\begin{matrix} F_{4} & = & \frac{1}{m^{4}} {- (3 + 6 m + 5 m^{2} + 3 m^{3}) b_{1} + (5 + 16 m + 16 m^{2} + 9 m^{3}) b_{1} b_{2} - 3 (1 + 4 m + 6 m^{2} + 3 m^{3}) b_{3}} \end{matrix}

\begin{matrix} F_{5} = \frac{1}{m^{5}} {(2 + 5 m + 5 m^{2} + 3 m^{3} + 2 m^{4}) b_{1}^{4} - (4 + 15 m + 19 m^{2} + 13 m^{3} + 8 m^{4}) b_{1}^{2} b_{2} \\ + (- 1 + m + 6 m^{2} + 6 m^{3} + 4 m^{4}) b_{2}^{2} + (5 + 16 m + 23 m^{2} + 17 m^{3} + 8 m^{4}) b_{1} b_{3} \\ - 2 (1 + 5 m + 10 m^{2} + 10 m^{3} + 4 m^{4}) b_{4}} \end{matrix}

\begin{matrix} F_{6} & = & \frac{1}{m^{6}} {- (5 + 15 m + 18 m^{2} + 11 m^{3} + 5 m^{4} + 5 m^{5}) b_{1}^{5} \\ + (10 + 46 m + 71 m^{2} + 52 m^{3} + 28 m^{4} + 25 m^{5}) b_{1}^{3} b_{2} \\ - (20 + 58 m + 85 m^{2} + 72 m^{3} + 42 m^{4} + 25 m^{5}) b_{1}^{2} b_{3} \\ + (- 7 - 18 m - 3 m^{2} + 28 m^{3} + 33 m^{4} + 25 m^{5}) b_{2} b_{3} \\ + b_{1} (- (- 9 - 2 m + 29 m^{2} + 36 m^{3} + 27 m^{4} + 25 m^{5}) b_{2}^{2} \\ + (17 + 70 m + 115 m^{2} + 108 m^{3} + 63 m^{4} + 25 m^{5}) b_{4}) \\ - 5 (1 + 6 m + 15 m^{2} + 20 m^{3} + 15 m^{4} + 5 m^{5}) b_{5}} \end{matrix}

\begin{matrix} F_{7} & = & \frac{1}{m^{7}} {(6 + 21 m + 30 m^{2} + 21 m^{3} + 6 m^{4} + m^{5} + 6 m^{6}) b_{1}^{6} \\ - 2 (5 + 30 m + 57 m^{2} + 47 m^{3} + 15 m^{4} + 5 m^{5} + 18 m^{6}) b_{1}^{4} b_{2} \\ - 2 (1 - 3 m - 3 m^{2} + m^{3} - m^{4} + m^{5} + 6 m^{6}) b_{2}^{3} \\ + 2 (15 + 42 m + 61 m^{2} + 53 m^{3} + 27 m^{4} + 15 m^{5} + 18 m^{6}) b_{1}^{3} b_{3} \\ + 2 (- 5 - 15 m - 17 m^{2} - 3 m^{3} + 17 m^{4} + 23 m^{5} + 18 m^{6}) b_{2} b_{4} \\ + b_{1}^{2} ((- 24 - 30 m + 30 m^{2} + 58 m^{3} + 18 m^{4} + 15 m^{5} + 54 m^{6}) b_{2}^{2} \\ - 2 (21 + 78 m + 118 m^{2} + 107 m^{3} + 66 m^{4} + 33 m^{5} + 18 m^{6}) b_{4}) \\ + 2 b_{1} ((19 + 54 m + 56 m^{2} + 19 m^{3} - 4 m^{4} - 22 m^{5} - 36 m^{6}) b_{2} b_{3} \\ + (13 + 66 m + 138 m^{2} + 155 m^{3} + 110 m^{4} + 53 m^{5} + 18 m^{6}) b_{5}) \\ + 3 ((- 2 - 14 m - 30 m^{2} - 28 m^{3} - 10 m^{4} + 3 m^{5} + 6 m^{6}) b_{3}^{2} \\ - 2 (1 + 7 m + 21 m^{2} + 35 m^{3} + 35 m^{4} + 21 m^{5} + 6 m^{6}) b_{6})} \end{matrix}

\begin{matrix} F_{8} & = & \frac{1}{m^{8}} {(7 + 28 m + 47 m^{2} + 40 m^{3} + 13 m^{4} - 7 m^{5} - 7 m^{6} + 7 m^{7}) b_{1}^{7} \\ - (7 + 66 m + 161 m^{2} + 163 m^{3} + 42 m^{4} - 61 m^{5} - 44 m^{6} + 49 m^{7}) b_{1}^{5} b_{2} \\ + (35 + 94 m + 125 m^{2} + 95 m^{3} + 10 m^{4} - 49 m^{5} - 18 m^{6} + 49 m^{7}) b_{1}^{4} b_{3} \\ + (11 + 4 m - 74 m^{2} - 128 m^{3} - 136 m^{4} - 128 m^{5} - 36 m^{6} + 49 m^{7}) b_{2}^{2} b_{3} \\ + (17 + 136 m + 416 m^{2} + 640 m^{3} + 542 m^{4} + 232 m^{5} + 8 m^{6} - 49 m^{7}) b_{3} b_{4} \\ - b_{1}^{3} ((49 + 107 m + 32 m^{2} - 53 m^{3} + 44 m^{4} + 164 m^{5} + 86 m^{6} - 98 m^{7}) b_{2}^{2} \\ + (77 + 274 m + 395 m^{2} + 320 m^{3} + 160 m^{4} + 50 m^{5} + 33 m^{6} + 49 m^{7}) b_{4}) \\ - (- 13 - 44 m - 44 m^{2} - 8 m^{3} + 20 m^{4} + 52 m^{5} + 66 m^{6} + 49 m^{7}) b_{2} b_{5} \\ - b_{1}^{2} ((- 119 - 384 m - 573 m^{2} - 514 m^{3} - 402 m^{4} - 306 m^{5} - 75 m^{6} + 147 m^{7}) b_{2} b_{3} \\ - (77 + 354 m + 679 m^{2} + 712 m^{3} + 480 m^{4} + 234 m^{5} + 101 m^{6} + 49 m^{7}) b_{5}) \\ - ((13 - 20 m - 44 m^{2} - 20 m^{3} - 50 m^{4} - 100 m^{5} - 46 m^{6} + 49 m^{7}) b_{2}^{3} \\ + (38 + 241 m + 515 m^{2} + 583 m^{3} + 410 m^{4} + 190 m^{5} + 23 m^{6} - 49 m^{7}) b_{3}^{2} \\ + 2 (32 + 102 m + 161 m^{2} + 178 m^{3} + 132 m^{4} + 60 m^{5} - 14 m^{6} - 49 m^{7}) b_{2} b_{4} \\ + (37 + 224 m + 574 m^{2} + 812 m^{3} + 700 m^{4} + 404 m^{5} + 166 m^{6} + 49 m^{7}) b_{6}) \\ + (7 + 56 m + 196 m^{2} + 392 m^{3} + 490 m^{4} + 392 m^{5} + 196 m^{6} + 49 m^{7}) b_{7}} \end{matrix}

In a similar way to the first sub-step, the Taylor’s series for

f (y_{n})

can be derived using Equation (22), and then, using the involved expressions from the above relations, we can write:

\begin{matrix} u_{n} = ξ + H_{4} e_{n}^{4} + H_{5} e_{n}^{5} + H_{6} e_{n}^{6} + H_{7} e_{n}^{7} + H_{8} e_{n}^{8} + o (e_{n}^{9}) \end{matrix}

(23)

where:

\begin{matrix} H_{4} = \frac{1}{m^{5}} {{(1 + m)}^{2} b_{1} (- 1 + m) b_{1}^{2} - 2 m b_{2}) e^{4}} \end{matrix}

\begin{matrix} H_{5} = - \frac{1}{m^{6}} {(1 + m) ((- 5 - 5 m + 4 m^{3}) b_{1}^{4} + (6 + 7 m - 9 m^{2} - 14 m^{3}) b_{1}^{2} b_{2} \\ + 4 m (1 + 3 m + 2 m^{2}) b_{2}^{2} + 3 m (1 + 3 m + 2 m^{2}) b_{1} b_{3}} \end{matrix}

\begin{matrix} H_{6} = \frac{1}{m^{7}} {(- 18 - 49 m - 50 m^{2} - 18 m^{3} + 9 m^{4} + 10 m^{5}) b_{1}^{5} \\ + (39 + 129 m + 140 m^{2} + 30 m^{3} - 65 m^{4} - 47 m^{5}) b_{1}^{3} b_{2} \\ + (- 9 - 23 m - 4 m^{2} + 52 m^{3} + 75 m^{4} + 33 m^{5}) b_{1}^{2} b_{3} \\ - 6 m {(1 + m)}^{2} (2 + 7 m + 7 m^{2}) b_{2} b_{3} \\ + 2 (1 + m) b_{1} ((- 6 - 19 m - 7 m^{2} + 22 m^{3} + 24 m^{4}) b_{2}^{2} - 2 m (1 + 4 m + 6 m^{2} + 3 m^{3}) b_{4})} \end{matrix}

\begin{matrix} H_{7} = \frac{1}{m^{9}} {(- 1 + 51 m + 179 m^{2} + 254 m^{3} + 182 m^{4} + 56 m^{5} - 14 m^{6} - 20 m^{7}) b_{1}^{6} \\ + (2 - 158 m - 659 m^{2} - 1044 m^{3} - 782 m^{4} - 206 m^{5} + 126 m^{6} + 116 m^{7}) b_{1}^{4} b_{2} \\ + m (66 + 243 m + 360 m^{2} + 206 m^{3} - 72 m^{4} - 188 m^{5} - 96 m^{6}) b_{1}^{3} b_{3} \\ + m b_{1}^{2} ((102 + 544 m + 1015 m^{2} + 813 m^{3} + 149 m^{4} - 253 m^{5} - 174 m^{6}) b_{2}^{2} \\ + (- 12 - 39 m - 18 m^{2} + 91 m^{3} + 192 m^{4} + 170 m^{5} + 60 m^{6}) b_{4}) \\ + m (1 + m) (4 (- 2 - 14 m - 27 m^{2} - 16 m^{3} + 5 m^{4} + 10 m^{5}) b_{2}^{3} \\ - 9 m (1 + 6 m + 14 m^{2} + 15 m^{3} + 6 m^{4}) b_{3}^{2} - 8 m (2 + 11 m + 24 m^{2} + 25 m^{3} + 10 m^{4}) b_{2} b_{4}) \\ + m (1 + m) b_{1} ((- 36 - 129 m - 115 m^{2} + 122 m^{3} + 304 m^{4} + 208 m^{5}) b_{2} b_{3} \\ - 5 m (1 + 5 m + 10 m^{2} + 10 m^{3} + 4 m^{4}) b_{5})} \end{matrix}

\begin{matrix} H_{8} = \frac{1}{m^{10}} {(9 - 113 m - 530 m^{2} - 960 m^{3} - 947 m^{4} - 541 m^{5} - 153 m^{6} + 14 m^{7} + 35 m^{8}) b_{1}^{7} \\ + (- 27 + 446 m + 2426 m^{2} + 4908 m^{3} + 5221 m^{4} + 3091 m^{5} + 828 m^{6} - 173 m^{7} - 240 m^{8}) b_{1}^{5} b_{2} \\ + (3 - 294 m - 1304 m^{2} - 2526 m^{3} - 2633 m^{4} - 1417 m^{5} - 150 m^{6} + 333 m^{7} + 214 m^{8}) b_{1}^{4} b_{3} \\ + b_{1}^{3} ((16 - 428 m - 2914 m^{2} - 6922 m^{3} - 8196 m^{4} - 5129 m^{5} - 1298 m^{6} + 479 m^{7} + 478 m^{8}) b_{2}^{2} \\ + m (99 + 431 m + 744 m^{2} + 599 m^{3} + 43 m^{4} - 393 m^{5} - 408 m^{6} - 163 m^{7}) b_{4}) \\ + m b_{1}^{2} ((333 + 1927 m + 4528 m^{2} + 5351 m^{3} + 2921 m^{4} - 127 m^{5} - 1258 m^{6} - 663 m^{7}) b_{2} b_{3} \\ + (- 15 - 59 m - 48 m^{2} + 141 m^{3} + 405 m^{4} + 485 m^{5} + 320 m^{6} + 95 m^{7}) b_{5}) \\ + 2 m (1 + m) ((- 18 - 140 m - 379 m^{2} - 446 m^{3} - 179 m^{4} + 90 m^{5} + 116 m^{6}) b_{2}^{2} b_{3} \\ - 6 m (2 + 14 m + 41 m^{2} + 63 m^{3} + 51 m^{4} + 17 m^{5}) b_{3} b_{4} \\ - 5 m (2 + 13 m + 35 m^{2} + 50 m^{3} + 39 m^{4} + 13 m^{5}) b_{4} b_{5} \\ - m b_{1} (2 (- 50 - 421 m - 1244 m^{2} - 1728 m^{3} - 1206 m^{4} - 326 m^{5} + 134 m^{6} + 121 m^{7}) b_{2}^{3} \\ - 2 (- 24 - 127 m - 224 m^{2} - 55 m^{3} + 386 m^{4} + 682 m^{5} + 544 m^{6} + 182 m^{7}) b_{2} b_{4} \\ - 3 (1 + m) ((- 9 - 36 m - 46 m^{2} + 23 m^{3} + 125 m^{4} + 144 m^{5} + 73 m^{6}) b_{3}^{2} \\ - 2 m (1 + 6 m + 15 m^{2} + 20 m^{3} + 15 m^{4} + 5 m^{5}) b_{6}))} \end{matrix}

Finally, we obtain the Taylor’s series expansion of

f (u_{n})

, with the help of just the previous equation, and using the required relations obtained above, in the last sub-step of scheme Equation (15), we get the final error expression as follows:

\begin{matrix} e_{n + 1} & = & \frac{{(1 + m)}^{4} b_{1} ((- 1 + m) b_{1}^{2} - 2 m b_{2}) (- (- 1 + m) b_{1}^{4} + m (2 + m) b_{1}^{2} b_{2} - 4 m^{2} b_{2}^{2} + 3 m^{2} b_{1} b_{3}}{m^{11}} e_{n}^{8} \\ + o (e_{n}^{9}) \end{matrix}

(24)

Thus, the proof is completed. ☐

We further discuss the procedure for approximating the multiplicity of the zero ξ calculated by the discussed iterative scheme. If

x_{n}

is the n-th estimate of the multiple root computed by using scheme Equation (15), then in view of Equation (21), we get:

\begin{matrix} f (x_{n}) \approx \frac{(x_{n} - ξ) h (x_{n})}{m h (x_{n}) + (x_{n} - ξ) h^{'} (x_{n})} = \frac{e_{n} h (x_{n})}{m h (x_{n}) + e_{n} h^{'} (x_{n})} \end{matrix}

By the fact that

e_{n}

is small, we have

f (x_{n}) \approx \frac{e_{n}}{m}

. Similarly, we can find that

f (x_{n + 1}) \approx \frac{e_{n + 1}}{m}

. Moreover,

e_{n + 1} - e_{n} = x_{n + 1} - x_{n}

. Thus, we can write:

\begin{matrix} m \approx \frac{x_{n + 1} - x_{n}}{f (x_{n + 1}) - f (x_{n})} \end{matrix}

Hence, m may be approximated by the reverse of the first-order divided difference of f for consecutive estimates

x_{n}

and

x_{n + 1}

(see [15,21]).

For comparing different iterative schemes abstractly, the concept of the efficiency index is presented by Owtrowski [29] and given by

d^{1 / n}

, where d is the convergence rate and n is the total evaluations involved in each iteration. That means an iterative scheme with a greater efficiency index is more adequate. By using this formula, the efficiency index of the considered scheme is

8^{1 / 4} = 1.8618

, which is more than

6^{1 / 4} = 1.5651

M M 6

and

5^{1 / 4} = 1.4953

M M 5

3. Numerical Testing with the Conclusion

In this portion, we employ the proposed three-step method Equation (15) (MM8) for solving five nonlinear equations and scrutinize them by the methods given by Sharma and Bahl Equation (9) (MM6), in [24], and the Li et al. Equation (8) (MM5), in [23]. Displayed in Table 1, Table 2 and Table 3 are the absolute error in the root, the absolute value of the function and the absolute error in the approximation of unknown multiplicity, for three iterations. All of the computations were done by using Mathematica 8. We mention below five test equations along with their exact roots ξ (the functions, as well as initial guesses are taken from [23]):

\begin{matrix} 1 . f_{1} = \frac{{(x - 5^{1 / 2})}^{4}}{{(x - 1)}^{2} + 1}, m = 4, ξ = 2.2360 \dots, \\ 2 . f_{2} = {(8 x e^{- x^{2}} - 2 x - 3)}^{8}, m = 8, ξ = 1.7903 \dots, \\ 3 . f_{3} = {(l n (x^{2} + 3 x + 5) - 2 x + 7)}^{8}, m = 8, ξ = 5.4690 \dots, \\ 4 . f_{4} = \frac{{(x - 2)}^{4}}{{(x - 1)}^{2} + 1}, m = 4, ξ = 2.000 \dots, \\ 5 . f_{5} = {(x^{1 / 2} - \frac{1}{x} - 1)}^{7}, m = 7, ξ = 2.1478 \dots . \end{matrix}

Table 1. Numerical results for

M M 8

**Table 1.** Numerical results for $M M 8$ .
f	n	$\| x_{n} - ξ \|$	$\| f (x_{n}) \|$	$\| m - m_{n} \|$
$f_{1}$	1	3.0654e−4	7.6640e−4	1.1458e+0
	2	4.4333e−32	1.1083e−32	2.9976e−4
	3	8.4937e−255	2.1234e−255	4.3356e−32
$f_{2}$	1	2.1643e−3	2.7085e−4	3.5724e−1
	2	3.9285e−23	4.9107e−24	9.1312e−3
	3	4.6110e−181	5.7638e−182	1.6577e−22
$f_{3}$	1	5.7113e−9	7.1391e−10	1.4907e−1
	2	2.4732e−77	3.0916e−78	4.5992e−10
	3	3.0587e−624	3.8234e−625	1.9917e−78
$f_{4}$	1	4.4515e−5	1.1129e−5	1.0345e+0
	2	1.6081e−38	4.0203e−39	4.45154e−5
	3	4.6651e−306	1.1663e−306	1.6081e−38
$f_{5}$	1	4.7605e−4	6.8015e−5	1.7797e+0
	2	2.7073e−30	3.8675e−31	8.3970e−4
	3	2.9694e−240	4.2420e−241	4.7766e−30

Table 2. Numerical results for

M M 6

**Table 2.** Numerical results for $M M 6$ .
f	n	$\| x_{n} - ξ \|$	$\| f (x_{n}) \|$	$\| m - m_{n} \|$
$f_{1}$	1	7.6409e−3	1.9138e−3	1.1487e+0
	2	1.7779e−15	4.4447e−16	7.4627e−3
	3	2.8524e−92	7.1310e−92	1.7387e−15
$f_{2}$	1	4.8261e−3	6.0480e−4	3.5708e−1
	2	3.1700e−15	3.9625e−16	2.0356e−2
	3	2.5528e−88	3.1910e−89	1.3377e−14
$f_{3}$	1	1.2583e−7	1.5729e−8	1.4907e−1
	2	1.6225e−50	2.0282e−51	1.0133e−8
	3	7.4567e−308	9.3209e−309	1.3066e−51
$f_{4}$	1	4.1460e−3	1.0376e−3	1.0366e+0
	2	3.9308e−17	9.8270e−18	4.1460e−3
	3	2.8495e−101	7.1237e−102	3.9308e−17
$f_{5}$	1	4.4860e−3	6.4158e−4	1.7819e+0
	2	9.8136e−17	1.4019e−17	7.8955e−3
	3	1.0975e−98	1.5679e−99	1.7315e−16

Table 3. Numerical results for

M M 5

**Table 3.** Numerical results for $M M 5$ .
f	n	$\| x_{n} - ξ \|$	$\| f (x_{n}) \|$	$\| m - m_{n} \|$
$f_{1}$	1	7.1979e−3	1.8026e−3	1.1485e+0
	2	5.9419e−14	1.4855e−14	70306e−3
	3	2.3260e−69	5.8149e−70	5.8109e−14
$f_{2}$	1	4.7520e−3	5.9550e−4	3.5708e−1
	2	6.2369e−14	7.7961e−15	2.0043e−2
	3	2.4558e−68	3.0697e−69	2.6318e−13
$f_{3}$	1	2.2101e−7	2.7627e−8	1.4907e−1
	2	1.8202e−42	2.2753e−43	1.7798e−8
	3	6.8964e−218	8.6205e−219	1.4658e−42
$f_{4}$	1	3.5022e−3	8.7632e−4	1.0363e+0
	2	1.8093e−15	4.5231e−16	3.5022e−3
	3	6.6558e−77	1.6639e−77	1.8093e−15
$f_{5}$	1	4.7515e−3	6.7960e−4	1.7821e+0
	2	3.6795e−15	5.2564e−16	8.3616e−3
	3	1.0884e−75	1.5548e−76	6.4920e−15

The numerical values in Table 1, Table 2 and Table 3 validate that the presented scheme MM8 performs better, not only for the absolute error in the root and the absolute value of the function as compared to MM6 and MM5, but also in the approximation of unknown multiplicity. The techniques explained in this note could also be adapted to new high order methods designed recently (see [30] and the references therein): we will explore this matter in future research.

Acknowledgments

The author would like to pay his sincere thanks to the reviewers and editor for their valuable comments and suggestions, which led to a significant improvement of the paper.

Conflicts of Interest

The author declares no conflict of interest.

References

Schröder, E. Über unendlich viele Algorithmen zur Auflosung der Gleichungen. Math. Ann. 1870, 2, 317–365. [Google Scholar] [CrossRef]
Hansen, E.; Patrick, M. A family of root finding methods. Numer. Math. 1977, 27, 257–269. [Google Scholar] [CrossRef]
Li, S.G.; Cheng, L.Z.; Neta, B. Some fourth-order nonlinear solvers with closed formulae for multiple roots. Comput. Math. Appl. 2010, 59, 126–135. [Google Scholar] [CrossRef] [Green Version]
Victory, H.D.; Neta, B. A higher order method for multiple zeros of nonlinear functions. Int. J. Comput. Math. 1983, 12, 329–335. [Google Scholar] [CrossRef]
Dong, C. A family of multipoint iterative functions for finding multiple roots of equations. Int. J. Comput. Math. 1987, 21, 363–367. [Google Scholar] [CrossRef]
Osada, N. An optimal multiple root-finding method of order three. J. Comput. Appl. Math. 1994, 51, 131–133. [Google Scholar] [CrossRef]
Chun, C.; Neta, B. A third-order modification of Newton’s method for multiple roots. Appl. Math. Comput. 2009, 211, 474–479. [Google Scholar] [CrossRef] [Green Version]
Neta, B. New third order nonlinear solvers for multiple roots. Appl. Math. Comput. 2008, 202, 162–170. [Google Scholar] [CrossRef] [Green Version]
Chun, C.; Bae, H.J.; Neta, B. New families of nonlinear third-order solvers for finding multiple roots. Comput. Math. Appl. 2009, 57, 1574–1582. [Google Scholar] [CrossRef]
Neta, B.; Johnson, A.N. High-order nonlinear solver for multiple roots. Comput. Math. Appl. 2008, 55, 2012–2017. [Google Scholar] [CrossRef] [Green Version]
Neta, B. Extension of Murakami’s high order nonlinear solver to multiple roots. Int. J. Comput. Math. 2010, 87, 1023–1031. [Google Scholar] [CrossRef]
Behl, R.; Cordero, A.; Motsa, S.S.; Torregrosa, J.R.; Kanwar, V. An optimal fourth-order family of methods for multiple roots and its dynamics. Numer. Algorithms 2015. [Google Scholar] [CrossRef]
Singh, A.; Jaiswal, J.P. An efficient family of optimal fourth-order iterative methods for finding multiple roots of nonlinear equations. Proc. Natl. Acad. Sci. India Sect. A Phys. Sci. 2015, 85, 439–450. [Google Scholar] [CrossRef]
Traub, J.F. Iterative Methods for the Solution of Equations; Prentice Hall, Inc.: Englewood Cliffs, NJ, USA, 1964. [Google Scholar]
King, R.F. A secant method for multiple roots. BIT 1977, 17, 321–328. [Google Scholar] [CrossRef]
Iyengar, S.R.K.; Jain, R.K. Derivative free multipoint iterative methods for simple and multiple roots. BIT 1986, 26, 93–99. [Google Scholar] [CrossRef]
Wu, X.Y.; Fu, D.S. New higher-order convergence iteration methods without employing derivatives for solving nonlinear equations. Comput. Math. Appl. 2001, 41, 489–495. [Google Scholar] [CrossRef]
Wu, X.Y.; Xia, J.L.; Shao, R. Quadratically convergent multiple roots finding method without derivatives. Comput. Math. Appl. 2001, 42, 115–119. [Google Scholar]
Steffensen, I.F. Remark on iteration. Skand. Aktuarietidskr. 1933, 16, 64–72. [Google Scholar] [CrossRef]
Wu, X.Y. A new continuation Newton-like method and its deformation. Appl. Math. Comput. 2000, 112, 75–78. [Google Scholar] [CrossRef]
Parida, P.K.; Gupta, D.K. An improved method for finding multiple roots and it’s multiplicity of nonlinear equations in R. Appl. Math. Comput. 2008, 202, 498–503. [Google Scholar] [CrossRef]
Yun, B.I. A derivative free iterative method for finding multiple roots of nonlinear equations. Appl. Math. Lett. 2008, 22, 1859–1863. [Google Scholar] [CrossRef]
Li, X.; Mu, C.; Ma, J.; Hou, L. Fifth order iterative method for finding multiple roots of nonlinear equations. Numer. Algorithms 2011, 57, 389–398. [Google Scholar] [CrossRef]
Sharma, R.; Bahl, A. A sixth order transformation method for finding multiple roots of nonlinear equations and basin attractors for various methods. Appl. Math. Comput. 2015, 269, 105–117. [Google Scholar] [CrossRef]
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]
Kioustelidis, J.B. A derivative-free transformation preserving the order of convergence of iteration methods in case of multiple zeros. Numer. Math. 1979, 33, 385–389. [Google Scholar] [CrossRef]
Cordero, A.; Huesoa, J.L.; Martínez, E.; Torregrosa, J.R. A new technique to obtain derivative-free optimal iterative methods for solving nonlinear equations. J. Comput. Appl. Math. 2013, 252, 95–102. [Google Scholar] [CrossRef]
Wolfram, S. The Mathematica Book, 5th ed.; Wolfram Media, Inc.: Champaign, IL, USA, 2003. [Google Scholar]
Owtrowski, A.M. Solution of Equations and Systems of Equations; Academic Press: New York, NY, USA, 1960. [Google Scholar]
Ullah, M.Z.; Serra-Capizzano, S.; Ahmad, F. An efficient multistep iterative method for computing the numerical solution of systems of nonlinear equations associated with ODEs. Appl. Math. Comput. 2015, 250, 249–259. [Google Scholar] [CrossRef]

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

Share and Cite

MDPI and ACS Style

Jaiswal, J.P. An Optimal Order Method for Multiple Roots in Case of Unknown Multiplicity. Algorithms 2016, 9, 10. https://doi.org/10.3390/a9010010

AMA Style

Jaiswal JP. An Optimal Order Method for Multiple Roots in Case of Unknown Multiplicity. Algorithms. 2016; 9(1):10. https://doi.org/10.3390/a9010010

Chicago/Turabian Style

Jaiswal, Jai Prakash. 2016. "An Optimal Order Method for Multiple Roots in Case of Unknown Multiplicity" Algorithms 9, no. 1: 10. https://doi.org/10.3390/a9010010

APA Style

Jaiswal, J. P. (2016). An Optimal Order Method for Multiple Roots in Case of Unknown Multiplicity. Algorithms, 9(1), 10. https://doi.org/10.3390/a9010010

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

An Optimal Order Method for Multiple Roots in Case of Unknown Multiplicity

Abstract

1. Introduction

2. Scheme and Analysis of the Local Convergence Rate

3. Numerical Testing with the Conclusion

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI