Applied and Computational Mathematics
Volume 5, Issue 6, December 2016, Pages: 247-251

Variants of Chebyshev’s Method with Eighth-Order Convergence for Solving Nonlinear Equations

Muhamad Nizam Muhaijir*, M. Imran, Moh Danil Hendry Gamal

Department of Mathematics, University of Riau, Pekanbaru, Indonesia

Email address:

(M. N. Muhaijir)
(M. Imran)
(M. D. H. Gamal)

*Corresponding author

To cite this article:

Muhamad Nizam Muhaijir, M. Imran, Moh Danil Hendry Gamal. Variants of Chebyshev’s Method with Eighth-Order Convergence for Solving Nonlinear Equations. Applied and Computational Mathematics. Vol. 5, No. 6, 2016, pp. 247-251. doi: 10.11648/j.acm.20160506.13

Received: October 26, 2016; Accepted: January 7, 2017; Published: February 3, 2017


Abstract: This paper develops the variants of Chebyshev’s method by applying Lagrange interpolation and finite difference to eliminate the second derivative appearing in the Chebyshev’s method. The results of this research show that the modified eight-order method has the efficiency index 1.5157. Numerical simulations show that the effectiveness and performance of the new method in solving nonlinear equations are encouraging.

Keywords: Chebyshev’s Method, Finite Differences, Lagrange Interpolation, Nonlinear Equations, Order of Convergence


1. Introduction

The solution of nonlinear equations is very important problem in numerical analysis. One of the problems in nonlinear equations is to determine the roots of the equation f(x) = 0 so that the sophisticated iteration method to solve it is in need. Many iteration methods can be used to solve the problem. Newton’s method is the oldest and widely used method written as

(1)

To accelerate the convergence of (1) many authors have modified it as we can see in [6, 8, 10, 11]. If we expand  about x = xn using Taylor expansion and ignoring the term of containing the third order, we obtain Chebyshev’s method in the form of

(2)

which has third-order convergence [1, 3]. Kou et al. [7] proposed a method which is free from second-derivative by approximating  in (2) by a finite difference as follows

(3)

(4)

This method has a third-order convergence [8]. The other methods modified from (2) having a four-order convergence can be seen in [2,4,5].

In this paper, we present the combination of Newton’s method and Chebyshev’s method into a three-step iteration method. We also incorporate finite difference to approximate the second derivative in second step and Lagrange interpolation to approximate the first derivative in the third step. The discussion of the new method and their convergence and analysis are carried out in Section 2. Then, in Section 3 we perform numerical simulations using some test functions, and compare the new method with some other methods, such as Newton’s method, Halley’s method, and Chebyshev’s method.

2. Proposed Methods

In this section, for construction of the new iterative method, we use the iterative methods given by equations (1) and (2). We consider the following three-step method

(5)

(6)

(7)

which requires one evaluation of the second derivative of the function. To remove this derivative, firstly we replace  in (6) with a finite difference [10], that is

(8)

where yn is equation (1).

Secondly, we approximate f’(zn) by a derivative of Lagrange interpolation polynomial L2(x) passing the points (xn, f(xn)), (yn, f(yn)), and (zn, f(zn)), that is

(9)

Simplifying equation (9) yields

(10)

where

(11)

(12)

(13)

Let , and substituting equation (8) into (6) and (10) into (7), we get

(14)

(15)

(16)

We can see that the new scheme (14), (15), and (16) are free from second derivative. For the method defined by scheme (14), (15), and (16), we have the following analysis of convergence.

Theorem 1 Assume that function f is sufficiently differentiable and f has a simple root . If the initial point x0 is sufficiently close to , then the method of iteration in equations (14)-(16) has eighth-order convergence and satisfying the following error equation:

where  and .

Proof. Let  be a simple root of the equation, then . Furthermore, using Taylor expansion of the  about , we obtain

(17)

Because  equation (17) can be rewritten in the form of

(18)

where .

Similarly, carrying out the Taylor expansion again for  about , after simplification, we obtain

(19)

Dividing (18) by (19) gives us

(20)

Substituting (20) into (14), we get

(21)

Moreover, the Taylor expansion of  about respectively are given by

(22)

Repeating the above process, we can find approximation to  as follows:

(23)

Now dividing (22) by (23), we obtain

(24)

From (18), (19), (22) and (23), we get

(25)

Using (18) and (22), we obtain

(26)

Furthermore, dividing (25) by (26), we have

(27)

Substituting (21), (24) and (27) into (15), we obtain

(28)

Applying Taylor expansion of  about , we get

(29)

To obtain the , we substitute (18), (28) and (29) into (11), that is

(30)

Using the same strategy,  can be obtained by substituting (21), (22), (28) and (29) into (12), that is

(31)

To obtain , we substitute (18), (21) and (22) into (13), that is

(32)

Using the equations (30), (31) and (32), we get

(33)

Dividing (29) by (33), we have

(34)

Substituting equations (28) and (34) into (16), we obtain

(35)

Putting , then from equation (35) we get

(36)

This means that the method defined by scheme (14), (15), and (16) has eighth-order convergence. The proof is completed.

Schemes (14), (15), and (16) require three evaluations of the functions and two of their first derivative per iteration. So that, if we consider the definition of eficiency index as , where p is the order of the method and m is the number of functional evalations per iteration required by the method. We have that the method obtained by schemes (14), (15), and (16) has the efficiency index equal to , which is better than the Newton’s method having the efficiency index, Halley’s method  and Chebyshev’s method .

3. Numerical Expriments

In this section some numerical simulations are performed to compare Chebyshev-Lagrange method to some other methods, such as Newton’s method, Halley’s method, and Chebyshev’s method. The functions used are as follows:

 

 

     

 

 

We also calculate the computational order of convergence (COC) of the method using the following equation:

(37)

The calculation is carried out using software with 800 digits accuracy and tolerance . The stoping criteria of the iteration are  and . The value  is taken as the exact root .

In Table 1, we give initial value (x0), number of iterations (N), and the computational order of convergence (COC). An asterisk (*) on the number of iterations indicates that the method converges to different roots. Table 1 shows a comparison of the number of iterations and COC several methods to resolve the above functions including Newton’s method (NM), Halley’s method (HM), Chebyshev’s method (CM), and Chebyshev-Lagrange method (CLM) for some given initial values.

Based on Table 1 it is generally known that the CLM has the number of iterations less when compared to the other methods. This means that CLM has a better efficiency in computing process than other methods. From Table 1 we observe that the COC perfectly coincides with the theoretical results at Theorem 1. The results presented in Table 1 show that the CLM has higher convergence order compared to the other methods.

Tabel 1. Comparison of the number of iterations and COC.

N COC
NM HM CM CLM NM HM CM CLM

0.9 9 6 5 3 2.0000 3.0000 3.0000 8.0029
1.3 8 5 5 3 2.0000 3.0000 3.0000 8.0000
1.5 7 5 5 3 2.0000 3.0000 3.0000 8.0000
2.0 8 5 6 3 2.0000 3.0000 3.0000 8.0000

0.5 12 6 32 4 2.0000 3.0000 3.0000 8.0008
1.0 9 5 6 3 2.0000 3.0000 3.0000 7.9999
1.5 7 5 5 3 2.0000 3.0000 3.0000 8.0000
2.0 9 6 6 3 2.0000 3.0000 3.0000 8.0001

0.4 8 5 7 3 2.0000 3.0000 3.0000 8.0000
1.6 7 5 5 3 2.0000 3.0000 3.0000 8.0000
1.0 8 5 5 3 2.0000 3.0000 3.0000 8.0000
1.4 8 5 6 3 2.0000 3.0000 3.0000 8.0000

0.4 12 7 12* 4 2.0000 3.0000 3.0000 7.9997
0.8 9 6 5* 3 2.0000 3.0000 3.0000 7.9973
1.6 7 5 5 3 2.0000 3.0000 3.0000 8.0000
2.0 8 5 6 3 2.0000 3.0000 3.0000 8.0000

-1.0 11 7 6 4 2.0000 3.0000 3.0000 8.0000
0.0 8 5 6 3 2.0000 3.0000 3.0000 8.0000
1.0 7 5 5 3 2.0000 3.0000 3.0000 8.0000
2.0 7 5 6 3 2.0000 3.0000 3.0000 8.0000

1.7 11 6 6* 4 2.0000 3.0000 3.0000 8.0000
1.9 8 5 5 3 2.0000 3.0000 3.0000 8.0000
2.4 9 6 6 3 2.0000 3.0000 3.0000 8.0029
2.6 10 6 7 4 2.0000 3.0000 3.0000 7.9996

Table 2 shows a comparison of the absolute difference  and absolute value of the functions  of several methods to resolve the above functions including Newton’s method, Halley’s method, Chebyshev’s method, and Chebyshev-Lagrange method for some given initial values.

Tabel 2. Comparison  and .

NM HM CM CLM NM HM CM CLM

0.9 6.85e-85 4.85e-53 1.73e-82 4.22e-40 1.24e-168 2.65e-157 2.51e-245 1.82e-317
1.3 3.41e-81 6.03e-40 9.81e-36 2.19e-44 3.07e-161 5.12e-118 4.59e-105 9.59e-352
1.5 1.46e-54 2.46e-65 3.09e-57 2.24e-67 5.61e-108 3.46e-194 1.43e-169 1.13e-533
2.0 2.71e-55 1.76e-42 2.43e-45 2.12e-36 1.94e-109 1.27e-125 7.00e-134 7.45e-288

0.5 2.08e-67 6.37e-58 8.17e-36 1.50e-18 1.71e-132 4.72e-171 3.27e-104 6.90e-142
1.0 5.50e-97 7.04e-50 7.37e-56 6.82e-26 1.19e-191 6.38e-147 2.40e-164 1.25e-200
1.5 2.30e-53 5.69e-80 5.14e-62 5.09e-57 2.08e-104 3.37e-237 8.17e-183 1.21e-449
2.0 1.53e-77 2.77e-99 2.17e-63 5.33e-26 9.19e-153 3.88e-295 6.12e-187 1.76e-201

0.4 5.76e-58 6.70e-35 2.20e-44 1.52e-43 9.86e-115 8.30e-103 5.47e-131 7.07e-345
1.6 1.52e-63 4.03e-78 7.81e-65 1.99e-86 6.88e-126 1.81e-232 2.46e-192 6.11e-688
1.0 2.55e-95 1.15e-57 7.42e-50 2.06e-56 1.94e-189 4.19e-171 2.11e-147 8.33e-448
1.4 5.52e-62 4.21e-35 5.77e-88 5.06e-36 9.08e-123 2.05e-103 9.95e-262 1.08e-284

0.4 1.07e-88 1.16e-45 8.26e-44 1.08e-26 2.23e-176 2.02e-135 1.60e-129 2.48e-210
0.8 5.17e-54 4.14e-68 2.22e-43 3.10e-20 5.20e-107 9.27e-203 3.09e-128 1.17e-158
1.6 2.00e-56 3.19e-72 1.11e-61 1.65e-72 7.82e-112 4.25e-215 3.84e-183 7.71e-577
2.0 6.51e-65 3.47e-39 4.47e-96 7.10e-44 8.24e-129 5.47e-116 2.52e-286 8.91e-348

-1.0 1.76e-71 2.68e-71 2.54e-78 5.11e-58 1.15e-142 3.75e-213 4.51e-234 5.61e-463
0.0 1.80e-83 1.62e-43 2.54e-78 1.68e-40 1.19e-166 8.23e-130 4.51e-234 7.65e-323
1.0 1.80e-83 4.42e-87 5.05e-83 1.05e-77 1.19e-166 1.68e-260 3.56e-248 1.86e-620
2.0 5.63e-96 1.48e-35 6.67e-97 3.88e-75 1.17e-191 6.30e-106 8.18e-290 6.30e-600

1.7 3.21e-66 2.08e-66 8.52e-36 1.32e-38 1.54e-130 1.58e-196 3.40e-104 1.42e-300
1.9 3.63e-72 9.81e-62 4.00e-36 9.39e-39 1.97e-142 1.65e-182 3.52e-105 9.46e-302
2.4 1.64e-53 2.80e-71 1.31e-42 1.41e-15 4.06e-105 3.82e-211 1.24e-124 2.41e-116
2.6 2.74e-62 3.37e-45 5.85e-71 1.28e-21 1.13e-122 6.72e-133 1.10e-209 1.13e-164

The computational results presented in Table 2 show that in almost all of cases, the CLM has the absolute values of the function smaller when compared to Newton’s method, Halley’s method, and Chebyshev’s method.

4. Conclusions

In this paper we present the variants of Chebyshev’s method by removing the second derivative using finite difference. This method requires three functions and two first derivative evaluations per iteration. We have that the order convergence of this method is eight. Analysis of the efficiency shows that this method is better than Newton’s method, Halley’s method, and Chebyshev’s method.


References

  1. S. Amat, S. Busquier, J. M. Guiterres and M. A. Hernandes, On the global convergence of Chebyshev's iterative method, Journal of Computational and Applied Mathematics, 220 (2008), 17-21.
  2. R. Behl and V. Kanwar, Variant of Chebyshev's methods with optimal order convergence, Tamsui Oxford Journal of Information and Mathematical Sciences, 29 (2013), 39-53.
  3. V. Candela and A. Marquina, Recurance relations for rational cubic method, Computing, 45 (1990), 355-367.
  4. H. Esmaeili and A. N. Rezaei, A uniparametric family of modifications for Chebyshev's method, Lecturas Matematicas, 33 (2012), 95-106.
  5. J. Jayakumar and P. Jayasilan, Second derivative free modification with parameter for Chebyshev's method, International Journal of Computational Engineering Research, 03 (2013), 38-42.
  6. V. Kanwar, A family of third order multipoint methods for solving nonlinear equations, Applied Mathematics and Computation, 176 (2006), 409-413.
  7. J. Kou, L. Yitian and W. Xiuhua, A uniparametric Chebyshev-type method free from second derivatives, Applied Mathematics and Computation. 179 (2006), 296-300.
  8. J. Kou, L. Yitian and W. Xiuhua, Third-order modification of Newton's method, Journal of Computational and Applied Mathematics, 205 (2007), 1-5.
  9. M. A. Noor, W. A. Khan and A. Husain, A new modifed Halley method without second derivatives for nonlinear equation, Applied Mathematics and Computation, 189 (2007), 1268-1273.
  10. A. Y. Ozban, Some new variants of Newton's method, Applied Mathematics Letters 13 (2004), 87-93.
  11. S. Weerakoon and T. G. I. Fernando, A variant of Newton's methods with accelarated third order convergence, Applied Mathematics Letters, 1 (2000), 87-93.

Article Tools
  Abstract
  PDF(204K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931