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:
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 = x_{n} 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 y_{n} is equation (1).
Secondly, we approximate f’(z_{n}) by a derivative of Lagrange interpolation polynomial L_{2}(x) passing the points (x_{n}, f(x_{n})), (y_{n}, f(y_{n})), and (z_{n}, f(z_{n})), 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 x_{0} 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 (x_{0}), 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.
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