Next Article in Journal / Special Issue
Expanding the Applicability of a Third Order Newton-Type Method Free of Bilinear Operators
Previous Article in Journal / Special Issue
Local Convergence of an Optimal Eighth Order Method under Weak Conditions
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Fifth-Order Iterative Method for Solving Multiple Roots of the Highest Multiplicity of Nonlinear Equation

1
Department of Science, Taiyuan Institute of Technology, Taiyuan 030008, China
2
College of Information Engineering, Guizhou Minzu University, Guiyang 550025, China
3
School of Mathematics and Computer Science, Yichun University, Yichun 336000, China
*
Authors to whom correspondence should be addressed.
These authors contributed equally to this work.
Algorithms 2015, 8(3), 656-668; https://0-doi-org.brum.beds.ac.uk/10.3390/a8030656
Submission received: 8 June 2015 / Revised: 27 July 2015 / Accepted: 14 August 2015 / Published: 20 August 2015
(This article belongs to the Special Issue Numerical Algorithms for Solving Nonlinear Equations and Systems)

Abstract

:
A three-step iterative method with fifth-order convergence as a new modification of Newton’s method was presented. This method is for finding multiple roots of nonlinear equation with unknown multiplicity m whose multiplicity m is the highest multiplicity. Its order of convergence is analyzed and proved. Results for some numerical examples show the efficiency of the new method.

1. Introduction

This paper addresses the problem of multiple roots x * of nonlinear equation f ( x ) = 0 with unknown multiplicity m whose multiplicity m is the highest multiplicity, where f : [ a , b ] R R is a nonlinear differential function on [ a , b ] . In case the multiplicity m is given explicitly, there are many iterative methods established via various techniques (see [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] for more details). If the multiplicity m is not known explicitly, Traub [16] utilized a simple transformation F ( x ) = f ( x ) / f ( x ) instead of f ( x ) for computing a multiple root of f ( x ) = 0 . In this case, the aim of solving a multiple root is reduced to that of solving a simple root of the transformed equation f ( x ) = 0 , and thus any iterative method can be used to preserve the original convergence order. However, Newton’s method for this transformed equation requires evaluations of the derivatives f ( x ) and f ( x ) . In order to avoid the evaluations of these derivatives with the multiplicity m unknown, for multiple roots, King [17] proposed the secant method which does not use the function F = f / f , but rather use F = f ( x ) f ( x f ( x ) ) f ( x ) ( x f ( x ) ) x = f 2 ( x ) f ( x f ( x ) ) f ( x ) . Wu and Fu [18] further used F ( x ) = f 2 ( x ) f ( x ) f ( x f ( x ) ) and transformed the problem of solving multiple roots of f ( x ) = 0 into that of solving simple root of f ( x ) = 0 . Actually, they established the following iteration formulae:
x n + 1 = x n F 2 ( x n ) p · F 2 ( x n ) + F ( x n ) F ( x n F ( x n ) ) ,
where p R , p < . So, the sequence x n produced by the iteration Formulae (1) is at least quadratically convergent for multiple roots. Moreover, Wu et al. [19] defined a function
F ( x ) = s i g n ( f ( x ) ) f ( x ) f ( x ) 1 / m s i g n ( f ( x + s i g n ( f ( x ) ) f ( x ) 1 / m ) f ( x ) ) f ( x ) f ( x ) 1 / m + f ( x + s i g n ( f ( x ) ) f ( x ) 1 / m ) f ( x ) ,
where m is the multiplicity, and employed the modified Steffensen’s method (see [20,21])
x n + 1 = x n h n F 2 ( x n ) t · F 2 ( x n ) + F ( x n + F ( x n ) ) F ( x n ) = x n h n F ( x n ) t · F ( x n ) + ( F ( x n + F ( x n ) ) F ( x n ) ) / ( F ( x n ) )
to compute the approximate solution of the equation f ( x ) = 0 , where h n ( > 0 ) is the step size of iteration and t < . Parida and Gupta [22] suggested another transformation
F ( x ) = f 2 ( x ) δ + f ( x + f ( x ) ) f ( x ) if f ( x ) 0 , 0 if f ( x ) = 0 .
where δ = s i g n ( f ( x + f ( x ) ) f ( x ) ) f 2 ( x ) , and transform the task of solving multiple zeros of f into that of solving simple zero of F. In this case, they utilized a quadratically convergent derivative free Newton-like iterative method:
x n + 1 = x n F 2 ( x n ) p · F 2 ( x n ) + F ( x n ) F ( x n F ( x n ) )
where the parameter p should be chosen such that the denominator is the largest in magnitude. Yun [23] suggested a new transformation of f ( x ) as
H ε ( x ) = ε f 2 ( x ) f ( x + ε f ( x ) ) f ( x ) ,
took ε such that max a x b ε f ( x ) = δ , that is
ε = δ max a x b f ( x ) = δ max f ( a ) , f ( b ) ,
and proposed an iterative method as follows:
x n + 1 = x n 2 ( x n x n 1 ) H ε ( x n ) H ε ( 2 x n x n 1 ) H ε ( x n 1 ) .
Recently, for the transformed equation K ( x ) = 0 with a simple root, Yun [24] proposed a Steffensen-type iterative formula
p k + 1 = p k μ K ( p k ) 2 K ( p k + μ K ( p k ) ) K ( p k ) , k 0 ,
where K ( x ) = K ( ε ; x ) = ε f ( x ) 2 f ( x + ε f ( x ) ) f ( x ) , if f ( x ) 0 , 0 , if f ( x ) = 0 .
In this paper we construct a new modified Newton’s method. We will present the proof that the method is three-step iterative method with fifth-order convergence for nonlinear equations of multiple roots with unknown multiplicity m, whose multiplicity m is the highest multiplicity and without requiring the use of the second derivative.

2. Iterative Method with Fifth-Order Convergence for Solving Multiple Roots

We consider the simple transformation (see [16,25]):
F ( x ) = f ( x ) f ( x ) , if f ( x ) 0 , 0 , if f ( x ) = 0 ,
and use a Newton-like iterative method:
y n = x n F ( x n ) F ( x n ) , z n = y n F ( y n ) F ( y n ) , x n + 1 = z n F ( z n ) F ( z n ) .
In order to avoid computing the first derivatives of function F ( x n ) , F ( y n ) and F ( z n ) , we approximate them as follows:
F ( x n ) F ( x n + F ( x n ) ) F ( x n ) F ( x n ) = g 1 ( x n ) ,
F ( y n ) 2 ( F ( y n ) F ( x n ) ) y n x n g 1 ( x n ) = g 2 ( x n )
F ( z n ) F [ z n , y n ] + F [ z n , x n , x n ] ( z n y n ) = F ( z n ) F ( y n ) z n y n + F ( z n ) F ( x n ) z n x n g 1 ( x n ) z n x n ( z n y n ) = g 3 ( x n )
(See [25,26,27,28] for the detail discussions of Equations (11)–(13) respectively.) Substituting the approximations of F ( x n ) , F ( y n ) and F ( z n ) given by Equations (11)–(13) in Equation (10), we establish the following new iterative method:
y n = x n F ( x n ) g 1 ( x n ) , z n = y n F ( y n ) g 2 ( x n ) , x n + 1 = z n F ( z n ) g 3 ( x n ) .
We give the following convergence theorem for the proposed method Equation (14) as follows.
Theorem 1. Suppose that f C 1 ( D ) ( D R R ) has multiple roots x * D , whose multiplicity m is the highest multiplicity of nonlinear equation, where D is an open interval. If the initial point x 0 is sufficiently close to x * , the iterative method defined by (14) has fifth-order convergence.
Proof. Without loss of generality, we assume that f ( x ) has two multiple roots
f ( x ) = ( x x * ) m ( x x 1 ) n h ( x )
where x * is a multiple root of Equation (15) with multiplicity m and x 1 is a multiple root of Equation (15) with multiplicity n ( m > n ) , h ( x ) is a continuous function with h ( x * ) 0 and h ( x 1 ) 0 . According to Equation (15), we have
f ( x ) = m ( x x * ) m 1 ( x x 1 ) n h ( x ) + n ( x x * ) m ( x x 1 ) n 1 h ( x ) + ( x x * ) m ( x x 1 ) n h ( x ) .
Dividing Equation (15) by Equation (16), we get
F ( x ) = f ( x ) f ( x ) = ( x x * ) ( x x 1 ) h ( x ) m ( x x 1 ) h ( x ) + n ( x x * ) h ( x ) + ( x x * ) ( x x 1 ) h ( x )
From Equation (17), we can see that the problem of computing multiple roots of f ( x ) = 0 can be reduced to the equivalent problem of computing simple root x * of F ( x ) = 0 .
Using Taylor’s expansion, we have
h ( x n ) = h ( x * ) [ 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 + o ( e n 7 ) ]
where b k = h ( k ) ( x * ) k ! h ( x * ) , k = 1 , 2 , . . . , and e n = x n x * .
By Equation (18), we obtain
h ( x n ) = h ( x * ) [ 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 + o ( e n 6 ) ] .
Substituting Equations (18) and (19) into Equation (17), we get
F ( x n ) = e n h ( x n ) m h ( x n ) + e n h ( x n ) = c 1 e n + c 2 e n 2 + c 3 e n 3 + c 4 e n 4 + o ( e n 5 )
where
c 1 = 1 m , c 2 = ( a b ) b 1 + n m 2 ( a b )
c 3 = 1 ( a b ) 2 m 3 ( ( a b ) 2 b 1 2 m + a 2 b 1 2 2 a 2 b 2 m 2 a b b 1 2 + 4 a b b 2 m + b 2 b 1 2 2 b 2 b 2 m + 2 a b 1 n 2 b b 1 n + m n + n 2 )
c 4 = 1 m 4 ( a b ) 3 ( a 3 b 1 3 m 2 3 a 2 b b 1 3 m 2 + 3 a b 2 b 1 3 m 2 b 3 b 1 3 m 2 + 2 a 3 b 1 3 m 3 a 3 b 1 b 2 m 2 6 a 2 b b 1 3 m + 9 a 2 b b 1 b 2 m 2 + 6 a b 2 b 1 3 m 9 a b 2 b 1 b 2 m 2 2 b 3 b 1 3 m + 3 b 3 b 1 b 2 m 2 + a 3 b 1 3 4 a 3 b 1 b 2 m + 3 a 3 b 3 m 2 3 a 2 b b 1 3 + 12 a 2 b b 1 b 2 m 9 a 2 b b 3 m 2 + 2 a 2 b 1 2 m n + 3 a b 2 b 1 3 12 a b 2 b 1 b 2 m + 9 a b 2 b 3 m 2 4 a b b 1 2 m n b 3 b 1 3 + 4 b 3 b 1 b 2 m 3 b 3 b 3 m 2 + 2 b 2 b 1 2 m n + 3 a 2 b 1 2 n 4 a 2 b 2 m n 6 a b b 1 2 n + 8 a b b 2 m n + 3 b 2 b 1 2 n 4 b 2 b 2 m n + 2 a b 1 m n + 3 a b 1 n 2 2 b b 1 m n 3 b b 1 n 2 + m 2 n + 2 m n 2 + n 3 )
Substituting Equation (20) into Equation (11), we obtain
g 1 ( x n ) = c 1 + c 2 ( 2 + c 1 ) e n + ( 3 c 3 + 3 c 1 c 3 + c 1 2 c 3 + c 2 2 ) e n 2 + ( 4 c 2 c 3 + 2 c 1 c 2 c 3 + 4 c 4 + 6 c 1 c 4 + 4 c 1 2 c 4 + c 1 3 c 4 ) e n 3 + ( 5 c 5 + 10 c 1 c 5 + 5 c 1 3 c 5 + 10 c 1 2 c 5 + 2 c 3 2 c 1 + c 2 2 c 3 + 7 c 2 c 4 + c 1 4 c 5 + 3 c 3 2 + 3 c 1 2 c 2 c 4 + 8 c 1 c 2 c 4 ) e n 4 + o ( e n 5 )
Substituting Equation (20) and Equation (24) into the first formula of Equation (14), we have
y n = x * + c 2 ( 1 + c 1 ) c 1 e n 2 + 1 c 1 2 ( 2 c 2 2 + 2 c 1 c 3 + 3 c 1 2 c 3 + c 1 3 c 3 2 c 1 c 2 2 c 1 2 c 2 2 ) e n 3 + 1 c 1 3 ( 3 c 1 2 c 4 + 6 c 1 3 c 4 + 4 c 1 4 c 4 + c 1 5 c 4 + 5 c 1 c 2 3 + 3 c 1 2 c 2 3 + c 1 3 c 2 3 + 4 c 2 3 10 c 1 2 c 2 c 3 7 c 1 c 2 c 3 7 c 1 3 c 2 c 3 2 c 1 4 c 2 c 3 ) e n 4 + o ( e n 5 )
With Equation (25), we get
F ( y n ) = c 2 ( 1 + c 1 ) e n 2 + 1 c 1 ( 2 c 2 2 + 2 c 1 c 3 + 3 c 1 2 c 3 + c 1 3 c 3 2 c 1 c 2 2 c 1 2 c 2 2 ) e n 3 + 1 c 1 2 ( 3 c 1 2 c 4 + 6 c 1 3 c 4 + 4 c 1 4 c 4 + c 1 5 c 4 + 7 c 1 c 2 3 + 4 c 1 2 c 2 3 + c 1 3 c 2 3 + 5 c 2 3 10 c 1 2 c 2 c 3 7 c 1 c 2 c 3 7 c 1 3 c 2 c 3 2 c 1 4 c 2 c 3 ) e n 4 + o ( e n 5 )
Thereby, with Equations (20) and (24)–(26), we obtain
g 2 ( x n ) = c 1 c 1 c 2 e n 1 c 1 ( c 1 c 3 + 3 c 1 2 c 3 + c 1 3 c 3 c 1 c 2 2 2 c 2 2 ) e n 2 1 c 1 2 ( 2 c 1 2 c 4 + 6 c 1 3 c 4 + 4 c 1 4 c 4 + c 1 5 c 4 + 4 c 1 c 2 3 + 2 c 1 2 c 2 3 + 4 c 2 3 4 c 1 2 c 2 c 3 6 c 1 c 2 c 3 ) e n 3 1 c 1 3 ( 10 c 1 4 c 5 3 c 1 3 c 3 2 + 3 c 1 3 c 5 4 c 1 2 c 3 2 8 c 2 4 + c 2 c 4 c 1 5 + 20 c 2 2 c 1 2 c 3 + 15 c 3 c 1 3 c 2 2 + 16 c 1 c 2 2 c 3 + 4 c 1 4 c 2 2 c 3 + 10 c 5 c 1 5 + 5 c 5 c 1 6 + c 5 c 1 7 10 c 1 c 2 4 6 c 1 2 c 2 4 2 c 2 4 c 1 3 7 c 2 c 4 c 1 3 8 c 2 c 4 c 1 2 ) e n 4 + o ( e n 5 )
From Equations (25)–(27), it follows that
z n = x * c 2 2 ( 1 + c 1 ) c 1 e n 3 c 2 c 1 3 ( 3 c 2 2 c 1 2 c 2 2 c 1 2 c 2 2 + 6 c 3 c 1 2 + c 3 c 1 + 7 c 3 c 1 3 + 2 c 1 4 c 3 ) e n 4 1 c 1 4 ( 9 c 3 2 c 1 3 + 2 c 3 2 c 1 2 + 4 c 2 2 + 16 c 1 4 c 2 c 4 + 2 c 1 6 c 2 c 4 + 9 c 2 c 4 c 1 5 21 c 1 2 c 2 2 c 3 10 c 1 3 c 2 2 c 3 8 c 1 c 2 2 c 3 + 7 c 1 c 2 4 + 3 c 1 2 c 2 4 + 2 c 1 3 c 2 4 + 11 c 2 c 4 c 1 3 + 2 c 2 c 4 c 1 2 + 12 c 1 4 c 3 2 + 6 c 1 5 c 3 2 + c 1 6 c 3 2 + c 1 4 c 2 4 ) e n 5 + o ( e n 6 )
It is similar to Equation (26), we have
F ( z n ) = c 2 2 ( 1 + c 1 ) e n 3 c 2 c 1 2 ( 3 c 2 2 c 1 c 2 2 c 1 2 c 2 2 + 6 c 1 2 c 3 + c 3 c 1 + 7 c 3 c 1 3 + 2 c 3 c 1 4 ) e n 4 + o ( e n 5 )
Moreover, substituting Equations (20), (24)–(26), (28) and (29) into Equation (13), we get
g 3 ( x n ) = c 1 c 2 2 ( 1 + c 1 ) e n 2 c 2 c 1 ( 2 c 3 c 1 3 + 7 c 3 c 1 2 + 7 c 3 c 1 + 2 c 2 2 c 1 + c 2 2 + 2 c 3 ) e n e + o ( e n 4 )
Substituting Equations (28)–(30) into the third formula of Equation (14), we get
x n + 1 = z n F ( z n ) g 3 ( x n ) = x * + ( 1 + 2 c 1 + c 1 2 ) c 2 4 c 1 2 e n 5 + o ( e n 6 )
which just means that the iterative method defined by Equation (14) has fifth-order convergence. The proof is completed.
We further consider how to find the highest multiplicity of the root x * in the iterative method. If x n is the n-th iteration computed by an iterative method applied to f, then from Equation (9), we have
f n ( x n x * ) ( x n x 1 ) h ( x n ) m ( x n x 1 ) h ( x n ) + n ( x n x * ) h ( x n ) + ( x n x * ) ( x n x 1 ) h ( x n ) = ε n ( x n x 1 ) h ( x n ) m ( x n x 1 ) h ( x n ) + n ε n h ( x n ) + ε n ( x n x 1 ) h ( x n ) ,
where f n = f ( x n ) . Because ε n is small, we get f n ε n m . Similarly, we can compute that f n + 1 ε n + 1 m . Furthermore ε n + 1 ε n = x n + 1 x n . Consequently, when the iteration becomes closer to the root x * , we can estimate its multiplicity by computing
m x n + 1 x n f n + 1 f n .
In the practical computing root x * process, some iteration number is no more than two by using Equation (14). According to this case, we compute the root x * by using Equation (14), then we select the initial value near the root x * , and we use Newton iterative method to compute the highest multiplicity. Therefore, m is approximately the reciprocal of the divided difference of f for successive iteration x n and x n + 1 .

3. Numerical Results

We employ the proposed modification of Newton’s method with three-step Equation (14) (MNM) to solve some nonlinear equations. All the computations were done by using Visual C++ 6.0 and were satisfied the condition such that | f ( x n ) | < 1 . E 17 , | x n x * | < 1 . E 17 . In order to show the effectiveness of our iterative method, we provide at least three different initial iterative values. From different initial iterative values, they can be convergent to the same iterative solution whose multiplicity is the highest multiplicity of nonlinear equation. We used the following test functions and obtained the approximate zeros x * round up to the 17-th decimal place:
g 1 ( x ) = ( x 5 ) 7 ( x 3 ) 4 ( x 1 ) 2 + 1 , x 0 = 12 . 0 , 23 . 0 , 1 . 9 , m = 7 , n = 4 , x * = 2 . 236067977499790
g 2 ( x ) = ( sin ( x ) 2 2 x + 1 ) 5 ( x 2 ) 3 , x 0 = 23 , 23 , 1 . 5 , 1 . 7 , m = 5 , n = 3 , x * = 0 . 71483582544138924
g 3 ( x ) = ( 8 x exp ( x 2 ) 2 x 3 ) 8 ( x 2 ) 5 , x 0 = 20 , 20 , 0 . 0 , 1 . 5 , m = 8 , n = 5 , x * = 1 . 7903531791589544
g 4 ( x ) = ( 2 x cos ( x ) + x 2 3 ) 10 ( x 3 ) 8 ( x 2 + 1 ) , x 0 = 23 , 23 , 3 . 1 , 2 . 99 , m = 10 , n = 8 , x * = 2 . 9806452794385368
g 5 ( x ) = ( exp ( x 2 + x + 3 ) x + 2 ) 9 ( x 13 5 ) 6 , x 0 = 18 , 18 , 2 . 5 , 2 . 55 , m = 9 , n = 6 , x * = 2 . 4905398276083051
g 6 ( x ) = ( exp ( x ) + 2 sin ( x ) ) 4 ( x 2 ) 3 , x 0 = 4 . 0 , 2 . 5 , m = 4 , n = 3 , x * = 3 . 1627488709263654
g 7 ( x ) = ( ln ( x 2 + 3 x + 5 ) 2 x + 7 ) 15 ( x 37 ) 10 , x 0 = 34 , 5 , 5 . 8 , m = 15 , n = 10 , x * = 5 . 4690123359101421
g 8 ( x ) = ( x 2 + 2 x + 5 2 sin ( x ) x 2 + 3 ) 20 ( x 7 ) 11 , x 0 = 9 , 2 , 3 , m = 20 , n = 11 , x * = 2 . 3319676558839640
g 9 ( x ) = ( x 2 ) 7 ( x 5 ) 8 ( x 1 ) 2 + 1 , x 0 = 12 , 12 , 2 . 1 , 2 . 5 , m = 8 , n = 7 , x * = 2 . 2360679774997897
g 10 ( x ) = ( x 5 2 ) 15 4 exp ( x ) ( x 2 ) 2 , x 0 = 13 , 2 . 4 , 2 . 1 , m = 15 4 , n = 2 , x * = 2 . 50000000000
g 11 ( x ) = ( x x 1 ) 11 ( x 3 ) 5 , x 0 = 11 , 2 . 0 , 1 . 8 , m = 11 , n = 5 , x * = 2 . 147899035704787
g 12 ( x ) = ( ln ( x ) + x 5 ) 15 ( x 8 ) 10 , x 0 = 23 , 9 , 7 , 8 . 1 , m = 15 , n = 10 , x * = 8 . 309432694231572
g 13 ( x ) = ( sin ( x ) cos ( x ) x 3 + 1 ) 9 ( x 3 2 ) 3 , x 0 = 5 , 0 , 1 . 4 , 1 . 8 , m = 9 , n = 3 , x * = 1 . 117078770687451
g 14 ( x ) = ( x 7 ) 5 e x ( x 2 ) 2 , x 0 = 7 , 3 , 1 . 8 , m = 5 , n = 2 , x * = 2 . 6457513110645906
g 15 ( x ) = ( ln ( x ) + x 4 + 1 2 ) 7 ( x 3 2 ) 6 , x 0 = 5 , 1 . 5 , 1 , 0 . 5 , m = 7 , n = 6 , x * = 1 . 222813963628973
g 16 ( x ) = ( ln ( x ) + x 4 + 1 2 ) 8 ( x 3 2 ) 4 ( x 4 3 ) 2 , x 0 = 12 , 4 , 1 . 3 , 1 . 2 , m = 8 , n = 4 , x * = 1 . 222813963628973
g 17 ( x ) = ( x 7 ) 5 ( x 2 ) 2 ( x 3 2 ) , x 0 = 11 , 11 , 1 . 8 , 0 . 5 , m = 5 , n = 2 , x * = 2 . 6457513110645906
g 18 ( x ) = ( ln ( x ) + x 4 + 1 2 ) 10 ( x 3 2 ) 10 ( x 1 ) , x 0 = 12 , 2 , 1 . 5 , 1 . 3 , m = 10 , n = 10 , x * = 1 . 222813963628973
The computational results indicate that our proposed iterative method can converge to multiple roots whose multiplicity is the highest multiplicity of nonlinear equation. In the next section, for the special case which the multiplicity of the roots of nonlinear equation is a single multiplicity, we present the analysis result for comparison with previous methods.
Remark 1. The method of the Formula (14) can also solve the problem of Euler equation for higher-order linear ordinary differential equation with variable coefficients. We consider a Euler equation
x 8 y ( 8 ) + x 7 y ( 7 ) 2 x 5 y ( 5 ) x 4 y ( 4 ) + 8 x 2 y ( 2 ) + y = 0 ,
where a 1 = 1 , a 2 = 0 , a 3 = 2 , a 4 = 1 , a 5 = 0 , a 6 = 8 , a 7 = 0 , a 8 = 1 . It is not difficult to know that the corresponding characteristic equation of Equation (34) is the following,
p ( K ) = K ( K 1 ) ( K 2 ) ( K 3 ) ( K 4 ) ( K 5 ) ( K 6 ) ( K 7 ) + K ( K 1 ) ( K 2 ) ( K 3 ) ( K 4 ) ( K 5 ) ( K 6 ) 2 K ( K 1 ) ( K 2 ) ( K 3 ) ( K 4 ) K ( K 1 ) ( K 2 ) ( K 3 ) + 8 K ( K 1 ) + 1 = K 8 27 K 7 + 301 K 6 178 K 5 + 6053 K 4 11572 K 3 + 11401 K 2 4370 K + 1 = 0
Using iterative Formula (14), the real roots of characteristic Equation (35) are K 1 = 0.0002289696985655638, K 2 = 0.9983856337914987, K 3 = 2.111134535386187, K 4 = 2.659996979882180, K 5 = 4.396978604791156, K 6 = 7.038659857754116, respectively. So the general solution of the Euler Equation (34) is y ( x ) = C 1 x K 1 + C 2 x K 2 + C 3 x K 3 + C 4 x K 4 + C 5 x K 5 + C 6 x K 6 , where C 1 , C 2 , C 3 , C 4 , C 5 , C 6 are different constants.

4. Comparison with Previous Methods

In this section, we use the proposed modification of Newton’s method with three-step (14) (MNM) (the Formula (14) in our paper) to solve some nonlinear equations which the multiplicity of the roots is a single multiplicity, and compare them with King’s method [17] (KM, (4), (13)) ( G = f ( x ) f ( x f ( x ) ) f ( x ) ( x f ( x ) ) x = f 2 ( x ) f ( x f ( x ) ) f ( x ) (4), x 2 = x 1 ( x 0 x 1 ) G 1 G 0 G 1 (13)), the high-order convergence iteration methods without employing derivatives given in [18] (WFM, (6)) ( x n + 1 = x n F 2 ( x n ) p · F 2 ( x n ) + F ( x n ) F ( x n F ( x n ) ) (6)), the improved method for finding multiple roots and itąŕs multiplicity of nonlinear equations given in [22] (PGM, ((6), (11))) ( G ( x ) = f 2 ( x ) δ + f ( x + f ( x ) ) f ( x ) , i f f ( x ) 0 0 , i f f ( x ) = 0 , where δ = s i g n ( f ( x + f ( x ) ) f ( x ) ) f 2 ( x ) (6), x n + 1 = x n G 2 ( x n ) p G 2 ( x n ) + G ( x n ) G ( x n G ( x n ) ) (11)), the derivative free iterative method for finding multiple roots of nonlinear equations given in [23] (YM, ((7), (10))) ( H ε ( x ) = ε f ( x ) 2 f ( x + ε f ( x ) ) f ( x ) (7), x k + 1 = x k 2 ( x k x k 1 ) H ε ( x k ) H ε ( 2 x k x k 1 ) H ε ( x k 1 ) (10)), transformation methods for finding multiple roots of nonlinear equations [24] (YM, ((10), (12))) ( K ( x ) = ε f ( x ) 2 f ε ( x ) , i f f ( x ) 0 0 , i f f ( x ) = 0 . , where f ε ( x ) ε f ( x ) f ( x ) (10), p k + 1 = p k μ K ( p k ) 2 K ( p k + μ K ( p k ) ) K ( p k ) (12)), as well as Newton’s first order method(NM) x k + 1 = x k f ( x k ) f ( x k ) ). Displayed in Table 1 are the number of iterations satisfied such that | f ( x n ) | < 1 . E 17 , | x n x * | < 1 . E 17 . All the computations were done by using Visual C++ 6.0. Since King’s method and Yun’s method require two starting values, we have used x 1 = x 0 0 . 1 . We used the following test functions and obtained the approximate zeros x * round up to the 17th decimal place:
f 1 ( x ) = ( x 5 ) 4 ( x 1 ) 2 + 1 , m = 4 , x * = 2 . 236067977499790
f 2 ( x ) = ( sin 2 ( x ) 2 x + 1 ) 5 , m = 5 , x * = 0 . 71483582544138924
f 3 ( x ) = ( 8 x e x 2 2 x 3 ) 8 , m = 8 , x * = 1 . 7903531791589544
f 4 ( x ) = ( 2 x cos ( x ) + x 2 3 ) 10 ( x 2 + 1 ) , m = 10 , x * = 2 . 9806452794385368
f 5 ( x ) = ( e x 2 + x + 3 x + 2 ) 9 , m = 9 , x * = 2 . 4905398276083051
f 6 ( x ) = ( e x + 2 sin ( x ) ) 4 , m = 4 , x * = 3 . 1627488709263654
f 7 ( x ) = ( ln ( x 2 + 3 x + 5 ) 2 x + 7 ) 8 , m = 8 , x * = 5 . 4690123359101421
f 8 ( x ) = ( x 2 + 2 x + 5 2 sin ( x ) x 2 + 3 ) 5 , m = 5 , x * = 2 . 3319676558839640
f 9 ( x ) = ( x 2 ) 4 / ( ( x 1 ) 2 + 1 ) , m = 4 , x * = 2 . 0000000000000000
f 10 ( x ) = ( x 2 . 5 ) 15 4 e x , m = 15 4 , x * = 2 . 500000000000000
f 11 ( x ) = ( x 1 x 1 ) 7 , m = 7 , x * = 2 . 147899035704787
f 12 ( x ) = ( ln ( x ) + x 5 ) 3 , m = 3 , x * = 8 . 309432694231572
f 13 ( x ) = ( sin ( x ) · cos ( x ) x 3 + 1 ) 9 , m = 9 , x * = 1 . 117078770687451
f 14 ( x ) = ( ( x 3 ) exp ( x ) ) 5 , m = 5 , x * = 3 . 0000000000000000
f 15 ( x ) = ( ln ( x ) + x 4 + 1 2 ) 7 , m = 7 , x * = 1 . 222813963628973
Note that we used NC in Table 1 to mean that the method does not converge to the root. And these methods can converge to root by using closer initial values. The computational results in Table 1 demonstrate that our proposed iterative method (MNM) requires less number of iterations than those of KM, WFM, PGM, YM, and NM. Therefore, it is significant and applicable and can compete with other existing methods.
Table 1. Comparison of various aiterative methods for the case of single multiplicity.
Table 1. Comparison of various aiterative methods for the case of single multiplicity.
f ( x ) MNMKM [17]WFM [18]PGM [22]YM [23]YM [24]
Parameters x 1 = x 0 0 . 1 p = 1 p = 1 ε = 10 8 ε = 10 8
x 1 = x 0 0 . 1 μ = 1
f 1 , x 0 = 3 . 0 246432
f 2 , x 0 = 1 . 5 2NCNC4NC5
f 3 , x 0 = 1 . 1 2NCNCNC33
f 4 , x 0 = 3 . 2 23328NCNC
f 5 , x 0 = 3 . 0 2NC6643NC
f 6 , x 0 = 3 . 5 254NC32
f 7 , x 0 = 6 . 5 2NC3522
f 8 , x 0 = 2 . 7 2NCNC933
f 9 , x 0 = 2 . 5 144643
f 10 , x 0 = 2 . 8 2632032
f 11 , x 0 = 2 . 5 2333NC2
f 12 , x 0 = 9 . 0 134443
f 13 , x 0 = 1 . 4 2NCNCNCNC4
f 14 , x 0 = 3 . 4 259NCNC46
f 15 , x 0 = 1 . 7 2NCNC3242

5. Efficiency of Iterative Methods

In the following we compare the efficiency of methods mentioned in Section 1 whose the multiplicity of the roots of nonlinear equation is a single multiplicity. We consider the definition of efficiency index [29,30,31] as EFF = r 1 θ , where r is the order of the method and θ is number of function (and derivatives) evaluations per iteration required by the method. These results are presented in Table 2. In Table 2, we listed the methods according to decreasing order of efficiency index, and multiplicity m of roots with all methods under the row of King’s method (including King’s method) are unknown. For unknown multiplicity m, our new method comes second, next to King’s method.
Table 2. Comparison the efficiency of various iterative methods for the case of single multiplicity.
Table 2. Comparison the efficiency of various iterative methods for the case of single multiplicity.
MethodReferencerθEFF
N e t a [8] (49) m 3 2.73221.653
N e t a [8] (51)2.73221.653
N e t a a n d J o h n s o n [10] m = 2 431.587
N e t a [8] (39)331.442
N e t a [8] (29) m 3 331.442
C h u n a n d N e t a [7] (22)331.442
C h u n , B a e , a n d N e t a [9] (14)331.442
V i c t o r y a n d N e t a [4] (3)331.442
H a n s e n a n d P a t r i c k [2] (8.1)331.442
H a l l e y [12]331.442
L a g u e r r e [13]331.442
D o n g [14] (7), (8)331.442
D o n g [5] (9), (10)331.442
O s a d a [6]331.442
E . S c h r ö d e r [1]221.414
N e t a a n d J o h n s o n [10] m 2 441.414
N e t a [11]441.414
N e t a [8] (32) m = 3 231.259
W e r n e r [15] (16) m = 2 1.531.145
K i n g [17]1.61821.272
O u r m e t h o d This paper581.223
X i n y u a n W u [18]241.190
X i n y u a n W u [19]241.190
P . K . P a r i d a [22]241.190
B e o n g I n Y u n [23]241.190
B e o n g I n Y u n [24]241.190

6. Conclusions

A new iterative method with fifth-order convergence has been developed as a modification of Newton’s method for finding multiple roots with unknown multiplicity m whose multiplicity m is the highest multiplicity of nonlinear equation. Several numerical examples demonstrate that the proposed iterative method is efficient. For the special case which the multiplicity of the roots of nonlinear equation is a single multiplicity, our method is more efficient and performs better than classical Newton’s method and many other existing methods.

Acknowledgments

We take the opportunity to thank the reviewers for their thoughtful and meaningful comments. This work was supported by National Natural Science Foundation of China (61263034), Scientific and Technology Foundation Funded Project of Guizhou Province ([2014] 2092, [2014] 2093), Scientific and Technology Joint Foundation Funded Project of Guizhou Province ([2011] 18, [2013] 20), National Bureau of statistics Foundation Funded Project (2014LY011), Key Laboratory of Pattern Recognition and Intelligent System of Construction Project of Guizhou Province ([2009] 4002), Information Processing and Pattern Recognition for Graduate Education Innovation Base of Guizhou Province.

Author Contributions

The idea for this research work is proposed by Xiaowu Li and Mingsheng Zhang, numerical solution of nonlinear dynamic system is done by Juan Liang, the code procedure realization is achieved by Zhinan Wu and Feng Pan, theorem proof is done by Lin Wang, and the paper writing is completed by Juan Liang and Xiaowu Li.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Schröder, E. Über unendlich viele Algorithmen zur Auflösung der Gleichungen. Math. Ann. 1870, 2, 317–365. [Google Scholar] [CrossRef]
  2. Hansen, E.; Patrick, M. A family of root finding methods. Numer. Math. 1977, 27, 257–269. [Google Scholar] [CrossRef]
  3. 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]
  4. 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]
  5. 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]
  6. Osada, N. An optimal multiple root-finding method of order three. J. Comput. Appl. Math. 1994, 51, 131–133. [Google Scholar] [CrossRef]
  7. 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]
  8. Neta, B. New third order nonlinear solvers for multiple roots. Appl. Math. Comput. 2008, 202, 162–170. [Google Scholar] [CrossRef] [Green Version]
  9. 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]
  10. Neta, B.; Johnson, A.N. High-order nonlinear solver for multiple roots. Comput. Math. Appl. 2008, 55, 2012–2017. [Google Scholar] [CrossRef] [Green Version]
  11. Neta, B. Extension of Murakami’s High order nonlinear solver to multiple roots. Int. J. Comput. Math. 2010, 87, 1023–1031. [Google Scholar] [CrossRef]
  12. Halley, E. A new, exact and easy method of finding the roots of equations generally and that without any previous reduction. Philos. Trans. R. Soc. Lond. 1694, 18, 136–148. [Google Scholar] [CrossRef]
  13. Laguerre, E.N. Sur une méthode pour obtener par approximation les racines d’une équation algébrique qui a toutes ses racines réelles. 2e séries. Nouv. Ann. Math. 1880, 19, 88–103. [Google Scholar]
  14. Dong, C. A basic theorem of constructing an iterative formula of the higher order for computing multiple roots of an equation. Math. Numer. Sin. 1982, 11, 445–450. [Google Scholar]
  15. Werner, W. Iterationsverfahren höherer Ordnung zur Lösung nicht linearer Gleichungen. Z. Angew. Math. Mech. 1981, 61, T322–T324. [Google Scholar]
  16. Traub, J.F. Iterative Methods for the Solution of Equations; Prentice Hall: Englewood, IL, USA, 1964. [Google Scholar]
  17. King, R.F. A secant method for multiple roots. BIT 1977, 17, 321–328. [Google Scholar] [CrossRef]
  18. 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]
  19. 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] [CrossRef]
  20. Steffensen, I.F. Remark on Iteration. Skand. Aktuarietidskr 1933, 16, 64–72. [Google Scholar] [CrossRef]
  21. Wu, X.Y. A new continuation Newton-like method and its deformation. Appl. Math. Comput. 2000, 112, 75–78. [Google Scholar] [CrossRef]
  22. 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]
  23. Yun, B.I. A derivative free iterative method for finding multiple roots of nonlinear equations. Appl. Math. Lett. 2009, 22, 1859–1863. [Google Scholar] [CrossRef]
  24. Yun, B.I. Transformation methods for finding multiple roots of nonlinear equations. Appl. Math. Comput. 2010, 217, 599–606. [Google Scholar] [CrossRef]
  25. 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]
  26. Wang, X.; Liu, L. Modified Ostrowski’s method with eighth-order convergence and high efficiency index. Appl. Math. Lett. 2010, 23, 549–554. [Google Scholar] [CrossRef]
  27. Bi, W.; Ren, H.; Wu, Q. New family of seventh-order methods for nonlinear equations. Appl. Math. Comput. 2008, 203, 408–412. [Google Scholar] [CrossRef]
  28. Bi, W.; Ren, H.; Wu, Q. Three-step iterative methods with eighth-order convergence for solving nonlinear equations. J. Comput. Appl. Math. 2009, 225, 105–112. [Google Scholar] [CrossRef]
  29. Gautschi, W. Numerical Analysis: An Introduction; Birkhäuser: Boston, MA, USA, 1997. [Google Scholar]
  30. Neta, B. On a family of multipoint methods for non-linear equations. Int. J. Comput. Math. 1981, 9, 353–361. [Google Scholar] [CrossRef]
  31. Li, X.; Mu, C.; Ma, J.; Wang, C. Sixteenth-order method for nonlinear equations. Appl. Math. Comput. 2010, 215, 3754–3758. [Google Scholar] [CrossRef]

Share and Cite

MDPI and ACS Style

Liang, J.; Li, X.; Wu, Z.; Zhang, M.; Wang, L.; Pan, F. Fifth-Order Iterative Method for Solving Multiple Roots of the Highest Multiplicity of Nonlinear Equation. Algorithms 2015, 8, 656-668. https://0-doi-org.brum.beds.ac.uk/10.3390/a8030656

AMA Style

Liang J, Li X, Wu Z, Zhang M, Wang L, Pan F. Fifth-Order Iterative Method for Solving Multiple Roots of the Highest Multiplicity of Nonlinear Equation. Algorithms. 2015; 8(3):656-668. https://0-doi-org.brum.beds.ac.uk/10.3390/a8030656

Chicago/Turabian Style

Liang, Juan, Xiaowu Li, Zhinan Wu, Mingsheng Zhang, Lin Wang, and Feng Pan. 2015. "Fifth-Order Iterative Method for Solving Multiple Roots of the Highest Multiplicity of Nonlinear Equation" Algorithms 8, no. 3: 656-668. https://0-doi-org.brum.beds.ac.uk/10.3390/a8030656

Article Metrics

Back to TopTop