# Higher-Order Root-Finding Algorithms and Their Basins of Attraction

Authors: Amir Naseem; M. A. Rehman; Thabet Abdeljawad
Journal: Journal of Mathematics
 (2020)

---

## Abstract

In this paper, we proposed and analyzed three new root-finding algorithms for solving nonlinear equations in one variable. We derive these algorithms with the help of variational iteration technique. We discuss the convergence criteria of these newly developed algorithms. The dominance of the proposed algorithms is illustrated by solving several test examples and comparing them with other well-known existing iterative methods in the literature. In the end, we present the basins of attraction using some complex polynomials of different degrees to observe the fractal behavior and dynamical aspects of the proposed algorithms.


---

## Body

## 1. Introduction

Most of the problems in Mathematics, Physics, and Engineering sciences are linked with the solution of nonlinear equations of the following form:(1)fx=0,where f:X⊂ℝ⟶ℝ is a scalar function defined on an open connected set X.Mostly, the roots of such equations cannot be found directly, and therefore, we need to adopt an iterative method for approximating the roots of such type of equations. In an iterative method, we start the process by choosing an initial guessx0 which is refined sequentially by means of iterations until the approximated solution is achieved. Some of the basic and classical methods are given in [1–9] and the references therein.The most famous and well-known method for finding roots of nonlinear equations is of the following form:(2)xn+1=xn−fxnf′xn,which is quadratically convergent Newton’s method [10] for the solution of nonlinear equations.To improve its convergence, a large number of iteration schemes have been proposed by means of various types of techniques such as Adomian decomposition method, Taylor’s series, perturbation method, quadrature formula, interpolation, and finite difference techniques for removing higher-order derivatives and variational iteration techniques, see [10–22] and the references therein.In this paper, we proposed three new algorithms using variational iteration technique by considering two auxiliary functionsϕx and ψx. The first one, ϕx, behaves like a predictor function having convergence order q, where q≥1 and helps to attain iterative methods of convergence order q+r, where r≥1 is the order of convergence of the second auxiliary function ψx. Using variational iteration technique, we develop some new higher order root-finding algorithms with best performance and efficiency. The variational iteration technique was introduced by Inokuti et al. [15] in 1978. Using this technique, Noor and Shah [20, 21] proposed some iterative methods for the solution of nonlinear equations. The purpose of this technique was to solve a variety of diverse problems [12–14].Now, we apply the described technique to obtain higher-order root-finding algorithms. New algorithms are very fast using less number of iterations to reach the required root, free from 3rd and higher derivatives with ninth order of convergence which raises the efficiency index of these algorithms.The rest of the paper is divided as follows. The new iteration schemes are described in Section2. In Section 3, the convergence criteria of the proposed algorithms have been discussed. In Section 4, various test examples have been solved to show their performance as compared to the other similar existing methods in the literature. The basins of attraction for some complex polynomials have been presented in Section 5 which shows the dynamical and fractal behavior of the proposed algorithms. Finally, the conclusion of the paper is given in Section 6.


## 2. Construction of Root-Finding Algorithms Using Variational Iteration Technique

In this section, we construct some new root-finding algorithms with the help of variational iteration technique. These algorithms are multistep iterative methods which involve predictor and corrector steps. The proposed algorithms possess higher order of convergence than one-step methods. By applying variational iteration technique, we derive some new root-finding algorithms of orderq+r where q,r≥1 are the orders of convergence of the auxiliary iteration functions ϕx and ψx. Now, consider the nonlinear equation of the following form:(3)fx=0.Suppose thatα is the simple root and γ is the initial guess sufficiently close to α. For better understanding and to deliver the basic idea, we suppose the approximate solution xn of (3) such that(4)fxn≠0.We considerϕx and ψx as two iteration functions of order q and r, respectively. Then(5)xn+1=ϕxn+μfψxngψxnt,where t=q/r, is a recurrence relation which generates iterative methods of order q+r and gx is any arbitrary function which later on is converted to gψxn and μ is a parameter, called the “Lagrange’s multiplier” and can be determined from (5) by using the optimality criteria as follows:(6)μ=−ϕ′xnfψxngψxn1−ttψ′xnf′ψxngψxn+fψxng′ψxn.From (5) and (6), we get(7)xn+1=ϕxn−ϕ′xntψ′xnfψxngψxnf′ψxngψxn+fψxng′ψxn.Now, we are going to apply (7) for constructing a general iterative scheme for iterative methods. For this, suppose that(8)ψxn=yn=xn−fxnf′xn−f2xnf″xn2f′3xn,which is well-known Househölder’s method with cubic convergence [7]. With the help of (7) and (8), we can write(9)xn+1=ϕxn−ϕ′xnfyngyntyn′f′yngyn+fyng′yn.Let(10)ϕxn=zn=yn−fynf′yn,where yn=xn−fxn/f′xn−f2xnf″xn/2f′3xn, which is the two-step iterative method having convergence of order six. Differentiate equation (10) w.r.t “x,” we have(11)ϕ′xn=zn′=fynf″ynf′2ynyn′,and from Taylor’s series, we can write(12)fzn≈fyn+zn−ynf′yn+zn−yn22f″yn=f2ynf″yn2f′2yn.The last expression has been obtained by putting the value ofzn−yn from (10).From (11) and (12), we have(13)ϕ′xn=2fznfynyn′,with the help of (9), (10), and (13), we get(14)xn+1=zn−2fzngyntg′ynfyn+gynf′yn,where t=6/3=2, which is according to the above described technique. Then, equation (14) becomes(15)xn+1=zn−fzngyng′ynfyn+gynf′yn.Relation (15) is the main and general iterative scheme, which we use to deduce some new root-finding algorithms by considering some particular cases of the auxiliary function g, keeping in mind that it should not be zero or small for all iterations. If g obtains zero value, then (15) reduces to xn+1=zn which is similar to (10) and we are unable to derive new algorithms.


### 2.1. Case 1

Letgxn=exp−βxn, then g′xn=−βgxn. Using these values in (15), we obtain the following algorithm.Algorithm 1.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(16)yn=xn−fxnf′xn−f2xnf″xn2f′3xn,n=0,1,2,…,zn=yn−fynf′yn,xn+1=zn−fznf′yn−βfyn.


### 2.2. Case 2

Letgxn=exp−βfxn, then g′xn=−βf′xngxn. Using these values in (15), we obtain the following algorithm.Algorithm 2.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(17)yn=xn−fxnf′xn−f2xnf″xn2f′3xn,n=0,1,2,…,zn=yn−fynf′yn,xn+1=zn−fznf′yn−βfynf′yn.


### 2.3. Case 3

Letgxn=exp−βxn2, then g′xn=−2βxngxn. Using these values in (15), we obtain the following algorithm.Algorithm 3.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(18)yn=xn−fxnf′xn−f2xnf″xn2f′3xn,n=0,1,2,…,zn=yn−fynf′yn,xn+1=zn−fznf′yn−2βynfyn.
To obtain best results in all above algorithms, always choose that values ofβ which makes the denominator nonzero and largest in magnitude.


## 2.1. Case 1

Letgxn=exp−βxn, then g′xn=−βgxn. Using these values in (15), we obtain the following algorithm.Algorithm 1.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(16)yn=xn−fxnf′xn−f2xnf″xn2f′3xn,n=0,1,2,…,zn=yn−fynf′yn,xn+1=zn−fznf′yn−βfyn.


## 2.2. Case 2

Letgxn=exp−βfxn, then g′xn=−βf′xngxn. Using these values in (15), we obtain the following algorithm.Algorithm 2.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(17)yn=xn−fxnf′xn−f2xnf″xn2f′3xn,n=0,1,2,…,zn=yn−fynf′yn,xn+1=zn−fznf′yn−βfynf′yn.


## 2.3. Case 3

Letgxn=exp−βxn2, then g′xn=−2βxngxn. Using these values in (15), we obtain the following algorithm.Algorithm 3.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(18)yn=xn−fxnf′xn−f2xnf″xn2f′3xn,n=0,1,2,…,zn=yn−fynf′yn,xn+1=zn−fznf′yn−2βynfyn.
To obtain best results in all above algorithms, always choose that values ofβ which makes the denominator nonzero and largest in magnitude.


## 3. Convergence Analysis

In this section, we discuss the convergence criteria of the general iteration scheme described in relation (15).Theorem 1.
Assume thatα∈I be the simple root of the differentiable function f:I⊂ℝ⟶ℝ on an open interval I. If the initial guess x0 is sufficiently close to α, then the convergence order of the main and general iteration scheme described in relation (15) is at least nine.Proof.
To prove the convergence of the main and general iteration scheme described in relation (15), we assume that α is the simple root of the equation fx=0 and en be the error at nth iteration, then en=xn−α and by using Taylor series about x=α, we have(19)fxn=f′αen+12!f′αen2+13!f‴αen3+14!fivαen4+15!fvαen5+16!fviαen6+⋯+Oen10,(20)fxn=f′αen+c2en2+c3en3+c4en4+c5en5+c6en6+⋯+Oen10,where(21)cn=1n!fnαf′α,(22)f′xn=f′α1+2c2en+3c3en2+4c4en3+5c5en4+6c6en5+7c7en6+⋯+Oen10,(23)f″xn=f′α2c2+6c3en+12c4en2+20c5en3+30c6en4+42c7en5+56c8en6+⋯+Oen10.With the help of (20)–(23), we get(24)yn=α+−c3+2c22en3+12c2c3−9c23−3c4en4+15c32−63c3c22+30c24+24c2c4−6c5en5+10c6+40c2c5+55c4c3−112c4c22−136c2c32+251c3c23−88c25en6+⋯+Oen10,(25)fyn=f′α−c3+2c22en3+12c2c3−9c23−3c4en4+15c32−63c3c22+30c24+24c2c4−6c5en5+−10c6+40c2c5+55c4c3−112c4c22−135c2c32+247c3c23−84c25en6+⋯+Oen10,(26)f′yn=f′α1+−2c2c3+4c23en3+24c3c22−18c24−6c2c4en4+30c2c32−126c3c23+60c25+48c4c22−12c2c5en5+−20c2c6+80c22c5+110c2c4c3−224c4c23−284c22c32+514c3c24−176c26+3c33en6+⋯+Oen10,(27)gyn=gα+g′α−c3+2c22en3+g′α12c2c3−9c23−3c4en4+g′α15c32−63c3c22+30c24+24c2c4−6c5en5+g′α−10c6+40c2c5+55c4c3−112c4c22−136c2c32+251c3c23−88c25+2g″α−c32+c222en6+⋯+Oen10,(28)g′yn=g′α+g″α−c3+2c22en3+g″α12c2c3−9c23−3c4en4+g″α15c32−63c3c22+30c24+24c2c4−6c5en5+g″α−10c6+40c2c5+55c4c3−112c4c22−136c2c32+251c3c23−88c25+2g″α−c32+c222en6+⋯+Oen10.
With the help of (24)–(26), we have(29)zn=α+4c25−4c3c23+c2c32en6+⋯+Oen10,(30)fzn=f′α4c25−4c3c23+c2c32en6+⋯+Oen10.
Using equations (20)–(38) in general iteration scheme (15), we get the same result as follows:(31)xn+1=α+16c22−c3/23gαc2+1/2g′αc2gαen9+Oen10,which implies that(32)en+1=16c22−c3/23gαc2+1/2g′αc2gαen9+Oen10,which shows that the main and general iteration scheme (15) is of ninth order of convergence and all algorithms deduced from it have also the same order of convergence.


## 4. Numerical Results

In this section, we included some nonlinear functions to demonstrate the performance of newly proposed algorithms forβ=1. We compare these algorithms with the following well-known iterative methods:


### 4.1. Newton’s Method (NM)

For a givenx0, compute the approximate solution xn+1 by the following iterative scheme:(33)xn+1=xn−fxnf′xn,which is well-known Newton’s method [10] for finding zeros of nonlinear functions, having quadratic order of convergence.


### 4.2. Halley’s Method (HM)

For a givenx0, compute the approximate solution xn+1 by the following iterative scheme:(34)xn+1=xn−2fxnf′xn2f2xn−fxnf″xn.This is so called Halley’s method [2] for root-finding of nonlinear functions, which converges cubically.


### 4.3. Traub’s Method (TM)

For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(35)yn=xn−fxnf′xn,xn+1=yn−fynf′yn,which is known as Traub’s method [10] for finding roots of nonlinear functions and possesses fourth order of convergence.


### 4.4. Modified Halley’s Method (MHM)

For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(36)yn=xn−fxnf′xn,xn+1=yn−2fxnfynf′yn2fxnf′2yn−f′2xnfyn+f′xnf′ynfyn,which is modified Halley’s method [23] for finding the solution of nonlinear functions, having fifth order of convergence.In order to make numerical comparison of the above described methods with the newly developed algorithms, the following test examples have been solved:(37)f1x=x3+4x2−10,x0=−0.3,f2x=x−13−2,x0=0.1,f3x=x+2ex−1,x0=3.1,f4x=xex2−sin2x+3cosx+5,x0=−2,f5x=sin2x−x2+1,x0=5,as shown in Table 1.Table 1
Comparison of NM, HM, TM, MHM, and Algorithms1–3.
MethodNfxn+1xn+1COCf1x, x0=−0.3NM548.127500e−301.365230013414096845760806828982158252HM586.815871e−251.365230013414096845760806870256456403TM278.127500e−301.365230013414096845760806828982158254MHM222.439119e−361.365230013414096845760806828981666085Algorithm167.091332e−181.365230013414096846190235813184599989Algorithm256.372651e−341.365230013414096845760806828981666129Algorithm354.284994e−421.365230013414096845760806828981666089f2x, x0=0.1NM133.733284e−272.259921049894873164767210608062168882HM96.698145e−332.259921049894873164767210607278229763TM72.322902e−542.259921049894873164767210607278228354MHM71.851813e−152.259921049894873553623531427112621575Algorithm122.424093e−192.259921049894873164818113380693010359Algorithm235.354563e−752.259921049894873164767210607278228359Algorithm331.555712e−622.259921049894873164767210607278228359f3x, x0=3.1NM94.410873e−15−0.442854401002385897189122320418631572HM53.594315e−16−0.442854401002388364269506843689904223TM58.240223e−30−0.442854401002388583141327999994319034MHM51.172300e−56−0.442854401002388583141327999999336825Algorithm135.050188e−47−0.442854401002388583141327999999336829Algorithm242.382120e−52−0.442854401002388583141327999999336829Algorithm341.515125e−87−0.442854401002388583141327999999336829f4x, x0=−2.0NM85.538944e−20−1.207647827130918927012144306541687562HM46.330594e−16−1.207647827130918958183226772517198393TM45.538944e−20−1.207647827130918927012144306541687564MHM414.223498e−29−1.207647827130918927009416758358163885Algorithm131.388738e−39−1.207647827130918927009416758356084109Algorithm232.255420e−25−1.207647827130918927009416769462473759Algorithm321.733403e−25−1.207647827130918927009416766891900049f5x, x0=5.0NM71.502508e−221.404491648215341226035147342445886482HM42.649470e−381.404491648215341226035086817786868083TM47.125700e−451.404491648215341226035086817786868084MHM34.868406e−351.404491648215341226035086817786868105Algorithm122.062348e−201.404491648215341226026779182117958549Algorithm236.624520e−761.404491648215341226035086817786868089Algorithm331.970835e−561.404491648215341226035086817786868089Table1 shows the numerical comparison of our developed algorithms (for β=1) with Newton’s method, Halley’s method, Traub’s method, and modified Halley’s method. The columns represent the number of iterations N, the magnitude fx of fx at the final estimate xn+1, the approximate root xn+1, and the computational order of convergence (COC) that can be expressed mathematically using the following formula:(38)COC≈lnxn+1−xn/xn−xn−1lnxn−xn−1/xn−1−xn−2,which was suggested by Cordero and Torregrosa in (2007) [24].When we look at the numerical results of Table1, we come to know that our proposed algorithms are showing best performance as compared to the other ones. For example, in first test example f1 of Table 1, Algorithm 3 is the best as it took less number of iterations among the all other compared methods with great precision. In second, third, and fifth test examples, Algorithm 1 performed better than the other ones. In the fourth one, Algorithm 3 looks superior to the other methods. In short, we can say that the proposed algorithms are best in terms of accuracy, speed, number of iterations, and computational order of convergence as compared to the other well-known iterative methods. All numerical examples have been solved using the computer program Maple 13 by taking the accuracy ε=10−15 for the following stopping criteria:(39)xn+1−xn<ε.Table2 shows the comparison of the number of iterations required for different iterative methods with our developed algorithms (for β=1) to approximate the root of the given nonlinear function with the accuracy ε=10−100. The columns represent the number of iterations for different functions along with initial guess x0.Table 2
Comparison of number of iterations required for different iterative methods for ε = 10–100.
Methodf1xf2xf3xf4xf5xx0=−0.3x0=0.1x0=3.1x0=−2.0x0=5.0NM5615121110HM6011765TM288665MHM2396424Algorithm173443Algorithm264534Algorithm364534The numerical results as shown in Table2 again certified the fast and best performance of the proposed algorithms in terms of number of iterations for the above defined stopping criteria with the given accuracy. In all test examples, the proposed algorithms consumed less number of iterations as compared to the other iterative methods. All calculations have been carried out using the computer program Maple 13.Table3 shows the effect of parameter on the proposed algorithms by taking three different values of β. We applied the proposed algorithms on different test examples and the obtained results showing that the numeric behavior of the proposed algorithms changes with the change of the parameter β. A major change can be seen in first test example f1 of Table 3. Here, the Algorithm 1 took six iterations for β=1, thirty-two iterations for β=0.10, and thirteen iterations for β=0.25. Similar changes can be observed from the other examples of Table 3. By looking at the overall results of Table 3, we can conclude that β=1 is the best choice of parameter for the proposed algorithms, which we have already used in Tables 1 and 2.Table 3
The effect of parameterβ on the proposed algorithms.
MethodNumber of iterationsForβ=1Forβ=0.10Forβ=0.25f1x, x0=−0.3Algorithm163213Algorithm2555Algorithm3545f2x, x0=0.1Algorithm1233Algorithm2323Algorithm3322f3x, x0=3.1Algorithm1343Algorithm2444Algorithm3433f4x, x0=−2.0Algorithm1333Algorithm2333Algorithm3233f5x, x0=5.0Algorithm1233Algorithm2333Algorithm3332


## 4.1. Newton’s Method (NM)

For a givenx0, compute the approximate solution xn+1 by the following iterative scheme:(33)xn+1=xn−fxnf′xn,which is well-known Newton’s method [10] for finding zeros of nonlinear functions, having quadratic order of convergence.


## 4.2. Halley’s Method (HM)

For a givenx0, compute the approximate solution xn+1 by the following iterative scheme:(34)xn+1=xn−2fxnf′xn2f2xn−fxnf″xn.This is so called Halley’s method [2] for root-finding of nonlinear functions, which converges cubically.


## 4.3. Traub’s Method (TM)

For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(35)yn=xn−fxnf′xn,xn+1=yn−fynf′yn,which is known as Traub’s method [10] for finding roots of nonlinear functions and possesses fourth order of convergence.


## 4.4. Modified Halley’s Method (MHM)

For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(36)yn=xn−fxnf′xn,xn+1=yn−2fxnfynf′yn2fxnf′2yn−f′2xnfyn+f′xnf′ynfyn,which is modified Halley’s method [23] for finding the solution of nonlinear functions, having fifth order of convergence.In order to make numerical comparison of the above described methods with the newly developed algorithms, the following test examples have been solved:(37)f1x=x3+4x2−10,x0=−0.3,f2x=x−13−2,x0=0.1,f3x=x+2ex−1,x0=3.1,f4x=xex2−sin2x+3cosx+5,x0=−2,f5x=sin2x−x2+1,x0=5,as shown in Table 1.Table 1
Comparison of NM, HM, TM, MHM, and Algorithms1–3.
MethodNfxn+1xn+1COCf1x, x0=−0.3NM548.127500e−301.365230013414096845760806828982158252HM586.815871e−251.365230013414096845760806870256456403TM278.127500e−301.365230013414096845760806828982158254MHM222.439119e−361.365230013414096845760806828981666085Algorithm167.091332e−181.365230013414096846190235813184599989Algorithm256.372651e−341.365230013414096845760806828981666129Algorithm354.284994e−421.365230013414096845760806828981666089f2x, x0=0.1NM133.733284e−272.259921049894873164767210608062168882HM96.698145e−332.259921049894873164767210607278229763TM72.322902e−542.259921049894873164767210607278228354MHM71.851813e−152.259921049894873553623531427112621575Algorithm122.424093e−192.259921049894873164818113380693010359Algorithm235.354563e−752.259921049894873164767210607278228359Algorithm331.555712e−622.259921049894873164767210607278228359f3x, x0=3.1NM94.410873e−15−0.442854401002385897189122320418631572HM53.594315e−16−0.442854401002388364269506843689904223TM58.240223e−30−0.442854401002388583141327999994319034MHM51.172300e−56−0.442854401002388583141327999999336825Algorithm135.050188e−47−0.442854401002388583141327999999336829Algorithm242.382120e−52−0.442854401002388583141327999999336829Algorithm341.515125e−87−0.442854401002388583141327999999336829f4x, x0=−2.0NM85.538944e−20−1.207647827130918927012144306541687562HM46.330594e−16−1.207647827130918958183226772517198393TM45.538944e−20−1.207647827130918927012144306541687564MHM414.223498e−29−1.207647827130918927009416758358163885Algorithm131.388738e−39−1.207647827130918927009416758356084109Algorithm232.255420e−25−1.207647827130918927009416769462473759Algorithm321.733403e−25−1.207647827130918927009416766891900049f5x, x0=5.0NM71.502508e−221.404491648215341226035147342445886482HM42.649470e−381.404491648215341226035086817786868083TM47.125700e−451.404491648215341226035086817786868084MHM34.868406e−351.404491648215341226035086817786868105Algorithm122.062348e−201.404491648215341226026779182117958549Algorithm236.624520e−761.404491648215341226035086817786868089Algorithm331.970835e−561.404491648215341226035086817786868089Table1 shows the numerical comparison of our developed algorithms (for β=1) with Newton’s method, Halley’s method, Traub’s method, and modified Halley’s method. The columns represent the number of iterations N, the magnitude fx of fx at the final estimate xn+1, the approximate root xn+1, and the computational order of convergence (COC) that can be expressed mathematically using the following formula:(38)COC≈lnxn+1−xn/xn−xn−1lnxn−xn−1/xn−1−xn−2,which was suggested by Cordero and Torregrosa in (2007) [24].When we look at the numerical results of Table1, we come to know that our proposed algorithms are showing best performance as compared to the other ones. For example, in first test example f1 of Table 1, Algorithm 3 is the best as it took less number of iterations among the all other compared methods with great precision. In second, third, and fifth test examples, Algorithm 1 performed better than the other ones. In the fourth one, Algorithm 3 looks superior to the other methods. In short, we can say that the proposed algorithms are best in terms of accuracy, speed, number of iterations, and computational order of convergence as compared to the other well-known iterative methods. All numerical examples have been solved using the computer program Maple 13 by taking the accuracy ε=10−15 for the following stopping criteria:(39)xn+1−xn<ε.Table2 shows the comparison of the number of iterations required for different iterative methods with our developed algorithms (for β=1) to approximate the root of the given nonlinear function with the accuracy ε=10−100. The columns represent the number of iterations for different functions along with initial guess x0.Table 2
Comparison of number of iterations required for different iterative methods for ε = 10–100.
Methodf1xf2xf3xf4xf5xx0=−0.3x0=0.1x0=3.1x0=−2.0x0=5.0NM5615121110HM6011765TM288665MHM2396424Algorithm173443Algorithm264534Algorithm364534The numerical results as shown in Table2 again certified the fast and best performance of the proposed algorithms in terms of number of iterations for the above defined stopping criteria with the given accuracy. In all test examples, the proposed algorithms consumed less number of iterations as compared to the other iterative methods. All calculations have been carried out using the computer program Maple 13.Table3 shows the effect of parameter on the proposed algorithms by taking three different values of β. We applied the proposed algorithms on different test examples and the obtained results showing that the numeric behavior of the proposed algorithms changes with the change of the parameter β. A major change can be seen in first test example f1 of Table 3. Here, the Algorithm 1 took six iterations for β=1, thirty-two iterations for β=0.10, and thirteen iterations for β=0.25. Similar changes can be observed from the other examples of Table 3. By looking at the overall results of Table 3, we can conclude that β=1 is the best choice of parameter for the proposed algorithms, which we have already used in Tables 1 and 2.Table 3
The effect of parameterβ on the proposed algorithms.
MethodNumber of iterationsForβ=1Forβ=0.10Forβ=0.25f1x, x0=−0.3Algorithm163213Algorithm2555Algorithm3545f2x, x0=0.1Algorithm1233Algorithm2323Algorithm3322f3x, x0=3.1Algorithm1343Algorithm2444Algorithm3433f4x, x0=−2.0Algorithm1333Algorithm2333Algorithm3233f5x, x0=5.0Algorithm1233Algorithm2333Algorithm3332


## 5. Basins of Attraction

An attractor’s basin of attraction is the region of the phase space, over which iterations are defined, such that any point (any initial condition) in that region will eventually be iterated into the attractor. Equations or systems that are nonlinear can give rise to a richer variety of behavior than can linear systems. The basins of attraction describe the dynamical aspects and characteristics of an iterative method that is being under consideration over a large number of examples and sets of parameter values, see [25, 26] and references cited therein. The basin of attraction for complex Newton’s method was first considered and attributed by Cayley [27]. The aim of this section is to represent the basins for the proposed algorithms by using graphical tools. In order to represent the basins of attraction via different computer programmes, we have to choose an initial rectangle R which contains the roots of the considered polynomial. Then, for every point z0 in the region, we run an iterative method and then color the point corresponding to z0 which is depended upon the approximate convergence of the truncated orbit to a root, or lack thereof. The resolution of the image depends upon our discretization of the rectangle R. For example, if we discretize R into a 2000 by 2000 grid, then the result would be a high-resolution image.The basins of attraction using different algorithms have various applications in different fields such as Mathematics, Science, Education, Art, and Design. From the Fundamental Theorem of Algebra, any complex polynomial with complex coefficientsbn,bn−1,…,b1,bo:(40)pz=bnzn+bn−1zn−1+⋯+b1z+bo,or by its zeros (roots) z1,z2,…,zn−1,zn:(41)pz=z−z1z−z2…z−zn,of degree n has exactly n roots which may be distinct or repeated. The polynomial’s degree illustrates the number of basins of attraction and placing roots on the complex plane. The localization of basins can be controlled manually. Usually, the colors of basins of attraction depend upon the considered iterative method and the total number of iterations required to attain the approximate solution of some polynomials with a given accuracy. The detailed study of basins of attraction, its theoretical background, and interesting applications are discussed in [28–36].


### 5.1. Applications

In a numerical algorithm that is purely based on an iterative process, we always require stopping criteria for the whole process, i.e., a test which provides us information that the process has converged or it is very close to the solution. Such type of test is called a convergence test having the following standard form:(42)zn+1−zn<ε,where zn+1 and zn are two consecutive points in the iteration process and ε>0 is a given accuracy. In this paper, we also use the stopping criteria (42). Using newly developed algorithms, we presented basins of attractions of various polynomials that were much attractive, colorful, and aesthetic ones. The different colors of an image was based on the number of iterations required to approximate the root with the defined accuracy ε. A large number of such images can be generated by giving different values to the parameter k, where k represents the upper bound of the number of iterations.Here, we present the basins of attractions using the following complex polynomials of different degrees:(43)p1z=z3−1,p2z=z3−12,p3z=z4−1,p4z=z4−12,p5z=z5−1,p6z=z5−12.All the figures have been generated using the computer program Mathematica 10.0 by takingε=0.01, A=−2,2×−2,2, and k=15, where ε shows the accuracy of the given root, A represents the area in which we draw the basins of attraction, and k represents the upper bound of the number of iterations.Example 1.
Basins of attraction using the complex polynomialp1z for proposed algorithms.Example 2.
Basins of attraction using the complex polynomialp2z for proposed algorithms.Example 3.
Basins of attraction using the complex polynomialp3z for proposed algorithms.Example 4.
Basins of attraction using the complex polynomialp4z for proposed algorithms.Example 5.
Basins of attraction using the complex polynomialp5z for proposed algorithms.Example 6.
Basins of attraction using the complex polynomialp6z for proposed algorithms.
In Examples1–6, basins of attraction for the complex polynomials of different degrees through our proposed algorithms (for β=1) have been shown.
In the first experiment, we have run all the proposed algorithms to obtain the simple zeros of the cubic polynomialp1z. The results of the basin of attractions are given in Figure 1. For each distinct root of the considered polynomial, there exists a unique color on the corresponding basins of attraction, so there exists three unique colors, namely, brown, yellow, and red that can be easily seen from Figure 1. In the next experiment, we consider the polynomial p2z which has three distinct roots with multiplicity 2. The basins of attraction are presented in Figure 2. Three unique colors corresponding to the distinct roots can be seen in Figure 2. The repeated roots appeared with the same colors on the basins of attraction. In Examples 3 and 4, we ran the proposed algorithms for the complex polynomials p3z and p4z. The results are given in Figures 3 and 4. Both the polynomials have four distinct roots, and the corresponding four colors can be easily seen in Figures 3 and 4, respectively. The later polynomial p4z has all roots with multiplicity 2. The basins of attraction for the complex polynomials p5z and p6z through our proposed algorithms have been presented in Figures 5 and 6, respectively. These polynomials have five distinct roots, but the zeros of the later polynomial p6z are not simple and have multiplicity 2. The five unique colors corresponding to these roots appeared on the basins of attraction that can be seen from Figures 5 and 6.
When we look at the generated images, we can read two important characteristics. One of them is the convergence speed of the considered algorithm, which can be depicted by the shade of the color. The darkness of the colors shows less number of iterations of the considered algorithm and vice versa. The second one is the dynamical aspects of the algorithm. Low dynamics are in those specific areas which contain small variation of colors, whereas in areas having large variation of colors, the dynamics are high. The black color in images locates those places where the solution cannot be achieved for the given number of iterations. The areas with the same colors in above figures indicate the same number of iterations needed to approximate the solution and give similar look to the contour lines on the map.Figure 1
Basins of attraction associated with the polynomialp1z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 2
Basins of attraction associated with the polynomialp2z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 3
Basins of attraction associated with the polynomialp3z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 4
Basins of attraction associated with the polynomialp4z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 5
Basins of attraction associated with the polynomialp5z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 6
Basins of attraction associated with the polynomialp6z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)


## 5.1. Applications

In a numerical algorithm that is purely based on an iterative process, we always require stopping criteria for the whole process, i.e., a test which provides us information that the process has converged or it is very close to the solution. Such type of test is called a convergence test having the following standard form:(42)zn+1−zn<ε,where zn+1 and zn are two consecutive points in the iteration process and ε>0 is a given accuracy. In this paper, we also use the stopping criteria (42). Using newly developed algorithms, we presented basins of attractions of various polynomials that were much attractive, colorful, and aesthetic ones. The different colors of an image was based on the number of iterations required to approximate the root with the defined accuracy ε. A large number of such images can be generated by giving different values to the parameter k, where k represents the upper bound of the number of iterations.Here, we present the basins of attractions using the following complex polynomials of different degrees:(43)p1z=z3−1,p2z=z3−12,p3z=z4−1,p4z=z4−12,p5z=z5−1,p6z=z5−12.All the figures have been generated using the computer program Mathematica 10.0 by takingε=0.01, A=−2,2×−2,2, and k=15, where ε shows the accuracy of the given root, A represents the area in which we draw the basins of attraction, and k represents the upper bound of the number of iterations.Example 1.
Basins of attraction using the complex polynomialp1z for proposed algorithms.Example 2.
Basins of attraction using the complex polynomialp2z for proposed algorithms.Example 3.
Basins of attraction using the complex polynomialp3z for proposed algorithms.Example 4.
Basins of attraction using the complex polynomialp4z for proposed algorithms.Example 5.
Basins of attraction using the complex polynomialp5z for proposed algorithms.Example 6.
Basins of attraction using the complex polynomialp6z for proposed algorithms.
In Examples1–6, basins of attraction for the complex polynomials of different degrees through our proposed algorithms (for β=1) have been shown.
In the first experiment, we have run all the proposed algorithms to obtain the simple zeros of the cubic polynomialp1z. The results of the basin of attractions are given in Figure 1. For each distinct root of the considered polynomial, there exists a unique color on the corresponding basins of attraction, so there exists three unique colors, namely, brown, yellow, and red that can be easily seen from Figure 1. In the next experiment, we consider the polynomial p2z which has three distinct roots with multiplicity 2. The basins of attraction are presented in Figure 2. Three unique colors corresponding to the distinct roots can be seen in Figure 2. The repeated roots appeared with the same colors on the basins of attraction. In Examples 3 and 4, we ran the proposed algorithms for the complex polynomials p3z and p4z. The results are given in Figures 3 and 4. Both the polynomials have four distinct roots, and the corresponding four colors can be easily seen in Figures 3 and 4, respectively. The later polynomial p4z has all roots with multiplicity 2. The basins of attraction for the complex polynomials p5z and p6z through our proposed algorithms have been presented in Figures 5 and 6, respectively. These polynomials have five distinct roots, but the zeros of the later polynomial p6z are not simple and have multiplicity 2. The five unique colors corresponding to these roots appeared on the basins of attraction that can be seen from Figures 5 and 6.
When we look at the generated images, we can read two important characteristics. One of them is the convergence speed of the considered algorithm, which can be depicted by the shade of the color. The darkness of the colors shows less number of iterations of the considered algorithm and vice versa. The second one is the dynamical aspects of the algorithm. Low dynamics are in those specific areas which contain small variation of colors, whereas in areas having large variation of colors, the dynamics are high. The black color in images locates those places where the solution cannot be achieved for the given number of iterations. The areas with the same colors in above figures indicate the same number of iterations needed to approximate the solution and give similar look to the contour lines on the map.Figure 1
Basins of attraction associated with the polynomialp1z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 2
Basins of attraction associated with the polynomialp2z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 3
Basins of attraction associated with the polynomialp3z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 4
Basins of attraction associated with the polynomialp4z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 5
Basins of attraction associated with the polynomialp5z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)Figure 6
Basins of attraction associated with the polynomialp6z for β=1. (a) Stands for Algorithm 1, (b) for Algorithm 2, and (c) for Algorithm 3.
(a)(b)(c)


## 6. Concluding Remarks

Using variational iteration technique, three new root-finding algorithms for the solution of nonlinear equations in one variable have been established, having ninth order of convergence. By using some test examples, the performance and efficiency of the proposed algorithms have been analyzed. Tables1 and 2 show the best performance of the proposed algorithms in terms of accuracy, speed, number of iterations, and computational order of convergence as compared to other well-known existing iterative methods. We have also presented the basins of attraction using some complex polynomials through newly developed algorithms which describe the fractal behavior and dynamical aspects of the proposed algorithms. The variational iteration technique can be applied to derive a broad range of new algorithms for solving a system of nonlinear equations in one dimension.



---

*Source: 5070363-2020-11-30.xml*