Dynamical Comparison of Several Third-Order Iterative Methods for Nonlinear Equations

Obadah Said Solaiman,Samsul Ariffin Abdul Karim and Ishak Hashim,＊

1Department of Mathematical Sciences,Faculty of Science&Technology,Universiti Kebangsaan Malaysia,Bangi Selangor,43600,Malaysia

2Department of Fundamental and Applied Sciences,Center for Smart Grid Energy Research(CSMER),Institute of Autonomous System,Universiti Teknologi PETRONAS,Bandar Seri Iskandar,Seri Iskandar,Perak DR,32610,Malaysia

Abstract:There are several ways that can be used to classify or compare iterative methods for nonlinear equations,for instance;order of convergence,informationalefficiency,and efficiency index.In this work,we use another way,namely the basins of attraction of the method.The purpose of this study is to compare several iterative schemes for nonlinear equations.All the selected schemes are of the third-order of convergence and most of them have the same efficiency index.The comparison depends on the basins of attraction of the iterative techniques when applied on several polynomials of different degrees.As a comparison,we determine the CPU time (in seconds) needed by each scheme to obtain the basins of attraction,besides,we illustrate the area of convergence of these schemes by finding the number of convergent and divergent points in a selected range for all methods.Comparisons confirm the fact that basins of attraction differ for iterative methods of different orders,furthermore,they vary for iterative methods of the same order even if they have the same efficiency index.Consequently,this leads to the need for a new index that reflects the real efficiency of the iterative scheme instead of the commonly used efficiency index.

Keywords:Nonlinear equations;iterative methods;basins of attraction;order of convergence

1 Introduction

The subject of finding the solutions of nonlinear equations is important;because many nonlinear equations result from applied sciences like physics,chemistry and engineering.This field has been studied widely,see for example [1,2]and the references therein.There are different ways to compare iterative schemes;for instance,the number of iterations required to achieve the convergence criterion,the number of functions to be evaluated at each iteration,CPU time required for the scheme to satisfy the convergence criterion,informational efficiency and efficiency index.

The well-known Newton’s method and all root-finding methods depend on at least one initial guessx0for the rootαoff(x).To confirm that the iterative scheme converges to the zeroα,it is important that the initial value is close toα.But,how close shall the initial values to the zeroα?What is the better way to select the initial guess? And how can we make a comparison between different schemes for solving nonlinear equations depending on the initial guesses? Shall specific initial guessx0always converge to the same root if we use different iterative schemes?

The field of basins of attraction firstly considered and attributed by Cayley [3]is a method to show how different starting points affect the behavior of the function.In this way,we can compare different root-finding schemes depending on the convergence area of the basins of attraction.In this sense,the iterative scheme is better if it has a larger area of convergence.Here,we mean by the area of convergent,the number of convergent points to a rootαoff(x)in a selected range.Stewart [4]used the idea of the basins of attraction to compare Newton’s scheme to the schemes proposed by Halley [5],Popovski and Laguerre.For the case of multiple zeros of nonlinear equations with known multiplicity,many researchers compared various schemes of different orders by obtaining their basins of attraction,see for example,Scott et al.[6],Neta et al.[7],Jamaludin et al.[8]and Sarmani et al.[9].Chun et al.[10]presented the basins of attraction for several third-order methods.Moreover,the basins of attraction of several optimal fourth-order methods were shown by Neta et al.[11].Also,Neta et al.[12]presented the basins of attraction of several iterative schemes of different orders.The basins of attractions of Murakami’s fifth-order family of methods were shown by Chun et al.[13].Geum [14]presented the basins of attraction of optimal third-order schemes.Cordero et al.[15]presented the basins of attraction for schemes which is Steffensen-type.Chun et al.[16]compared many eighth-order iterative methods by showing their basins of attraction.Recently,Zotos et al.[17]compared a large collection of iterative schemes of different orders by illustrating their basins of attraction.Very recently,Said Solaiman et al.[18]presented a comparison between several optimal and non-optimal iterative schemes of the order sixteen by showing their basins of attraction,they tested various examples in which optimal iterative schemes may not always the best for nonlinear equations.Many authors proposed schemes for nonlinear equations together with the basins of attraction of the proposed methods,for instance,Behl et al.[19]illustrated the basins of attraction of their proposed sixthorder iterative scheme for nonlinear models.Very recently,Sivakumar et al.[20]proposed an optimal fourth-order iterative technique for nonlinear equations with the basins of attraction of the proposed technique.Also,Said Solaiman et al.[21]constructed an iterative method of order five for solving systems of nonlinear equations with the basins of attraction of the presented method.It is concluded from the previous studies that the basins of attraction vary for iterative schemes of different orders of convergence,furthermore,they vary for schemes of equal order of convergence.

Having basins of attraction with smooth convergent pattern or basins of attraction with chaotic pattern does not mean that the iterative scheme with a smooth pattern has a larger area of convergence than the scheme with chaotic basins of attraction,although this leads sometimes the algorithm converges to unwanted zero.Very few researchers have worked on finding number of convergent and divergent points in a selected range for iterative schemes when applied to numerical examples.Some questions arise from this subject are:

? Could the basins of attraction of the iterative schemes be affected by the number of steps needed in each scheme?

? If the basins of attraction of a specific iterative scheme were better than others in one example,is it necessary to be the best in all test problems?

? What are possible factors that affect the basins of attraction of the iterative schemes?

? Based on the basins of attraction of different schemes,is the current efficiency index enough to make comparisons between iterative schemes with equal order of convergence and an equal number of functions that need to be evaluated per iteration?

We shall in this work find answers to the above questions.We will compare some iterative schemes of third-order of convergence by using their basins of attraction.Some of these schemes are second-derivative free.We find out the number of convergent and divergent points on a selected range for all schemes when applied on different polynomials.The work in this paper is divided as follows:Some definitions and preliminaries related to the subject were mentioned in Section 2.In Section 3,the basins of attractions were used to compare eight iterative schemes of order three on some numerical examples.Finally,the conclusion of the paper is given in Section 4.

2 Preliminaries

Let’s start by stating some definitions and preliminaries which are related to the subject of basins of attraction.

Definition 1Let α be the exact zero of f,and en=xn?α be the error in the nth iterative step,and f:R→R be an iteration function with a root α,which defines the iterative scheme xn+1=f(xn).Iffor some p and b,then p is called the order of convergence,and b is the asymptotic error constant.

Iff(x0)=x0,thenx0is called a fixed point.Forx∈,whereis the Riemann sphere,we define its orbit as orb(x)={x,f(x),f[2](x),...,f[n](x),...},wheref[n]is thenthiterate off.x0is called a periodic point of periodnifnis the smallest number such thatf[n](x0)=x0.Ifx0is periodic of periodnthen it is a fixed point forf[n].A pointx0is said to be attracting ifrepelling ifand neutral ifMoreover,the point is called super-attracting if the derivative is zero.

The Julia setJ(f)of a nonlinear functionf(x),is the closure of the set of its repelling periodic points.The complement ofJ(f)is called the Fatou setF(f).IfOis an attracting periodic orbit of periodm,we define the basin of attraction to be the open setA∈consisting of all pointsx∈for which the successive iteratesf[m](x),f[2m](x),...converge towards some point ofO.In symbols,we can define the basin of attraction for any rootαoffto beB(α)={x0|limn→∞f[n](x0)=α}.The basin of attraction of a periodic orbit may have infinitely many components.It can be said that basin of attraction of any fixed point tends to an attractor belonging to Fatou set,and the boundaries of these basin of attraction belongs to the Julia set.

The complex polynomial of ordernwith distinct roots splits the complex plane intonregions(basins).These basins may or may not be equally divided or even connected.In an ideal situation,these basins form a Voronoi diagram displaying all points that are the nearest neighbors to the polynomial’s zero [4].

3 Numerical Examples

In this part,we study the area of convergence of eight iterative schemes of third-order of convergence by obtaining the basins of attraction of their zeros,and finding the number of convergent and divergent points in a selected region.All polynomials in the examples are of roots with multiplicity one.Some of the compared schemes were considered before,but without finding out the number of convergent and divergent points in a selected range.See Stewart [4]and Amat et al.[22].The methods we consider are:

? The modified Halley method (MH) proposed by Said Solaiman et al.[2]:

? The well-known Halley’s method [5],given by:

? Potra-Pták (PP) method [23],given by:

? Weerakon-Fernando (WF) method [24],given by:

? Frontini-Sormani (FS) method [25],given by:

? Homeier method (HM) [26],given by:

? Kou-Wang (KW) method [27],given by:

? Chun method (CM) [28],given by:

Figure 1:The basins of attraction for the zeros of f1(x)=x3?1.The top row from left to right:MH,Halley,and PP.The middle row from left to right:WF,FS,and HM.The bottom row:KW and CM respectively

Figure 2:The basins of attraction for the zeros of f2(x)=x3+2x2?3.The top row from left to right:MH,Halley,and PP.The middle row from left to right:WF,FS,and HM.The bottom row:KW and CM,respectively

The idea of the basins of attraction off(x)starts by selecting a starting point from a specific region that contains all the roots off(x).Then we apply the iterative scheme using the selected starting point with specific tolerance and a specific number of iterations considered as a convergence criterion.The iterative scheme will converge to one of the roots in the selected region if it satisfies the convergence criterion,or diverge if it fails.Finally,we color all points which are converging to a specific root using one color,and we use the black color for all points that are failing in satisfying the convergence criterion.

For the purpose of comparison,the CPU time (in sec) needed to obtain the basins of attraction has been computed,see Fig.6.Moreover,the number of convergent points (NCP) and divergent points (NDP) for each scheme in a selected range have been counted,see Tab.1.To cover all the zeros of the selected polynomial,4×4 region is centered at the origin.Thus,a 401×401=160801 points in a uniform grid are selected as initial points for the iterative schemes to generate the basins of attraction.Each point in the grid is colored depending on the number of iterations required for convergence and the zero it converges to.The exact roots were assigned as black dots on the graph.If the scheme needs less number of iterations to converge to a specific root,then the region of that roots appears darker.The convergence criterion selected is a tolerance of 10?3with a maximum of 100 iterations.

All calculations have been performed on Intel Core i3-2330M CPU@2.20 GHz with 4 GB RAM,using Microsoft Windows 10,64 bit based on X64-based processor.Mathematica 9 has been used to produce all graphs and computations.

Example 1Consider the polynomialf1(x)=x3?1 which has roots 1,?0.5±0.866025i.

The basins of attraction for the eight iterative schemes have been showed in Fig.1.As it can be clearly seen,Halley’s method attains smooth basins of attraction when compared to the others.But,Tab.1 shows that all iterative schemes except WF and FS have the same area of convergence.From Fig.6 it is clear that the CPU time needed to attain the basins of attraction is less for MH,Halley,and HM from the remaining schemes.The black areas that appeared in the basins of attraction of WF and FS represent points of divergence.

Figure 3:The basins of attraction for the zeros of f3(x)=x4?1.The top row from left to right:MH,Halley,and PP.The middle row from left to right:WF,FS,and HM.The bottom row:KW and CM,respectively

Example 2Now,consider the polynomialf2(x)=x3+2x2?3 which has three simple real rootsx=1,?1.5±0.866025i.Looking at Fig.2 and Tab.1,one can conclude that WF and FS show a lot of divergent points.The rest of the schemes have better basins of attraction with close CPU time needed to view the graphs as it’s clear from Fig.6.

Example 3The four roots of unity polynomialf3(x)=x4?1 has the rootsx=±1,±i.Even it seems from Fig.3 that Halley’s method has almost ideal basins of attraction,but we found that it has 112 points of divergent,see Tab.1.Almost all these 112 points exist on the two main diagonals of the graph.Besides,one can conclude from Tab.1 that CM is the best for this example as it has the minimum number of points of divergent,even though its basins of attraction has some complexity.So,for this example,we can consider CM as the best regarding the area of the convergence,although it needs little bit more CPU time as it appears from Fig.6,Halley,MH and HM have also a good area of convergence.The other schemes attain a lot of divergent points.

Example 4Next considerwhich has the rootsx=±1.5,±i.See Fig.4 for the basins of attraction of all iterative schemes.In this example all schemes have the same number of convergent points in the selected range,except WF and FS,see Tab.1.The CPU time needed to display the basins of attraction is less for Halley,MH,and HM from the other schemes,see Fig.6.

Example 5Finally,considerf5(x)=x5?1 which has the rootsx=1,?0.809017 ±0.587785i,0.309017±0.951057i.From Fig.5,PP,WF,FS,and KW show clear areas of divergence.These areas resulted from the huge number of divergent points,see Tab.1.The best scheme in this test problem is MH,HM followed by Halley based on their convergent points in the selected range as it’s clear in Tab.1.Regarding the required CPU time,Halley is the best followed by HM and MH.See Fig.6.

Figure 5:The basins of attraction for the zeros of f5(x)=x5?1.The top row from left to right:MH,Halley,and PP.The middle row from left to right:WF,FS,and HM.The bottom row:KW and CM respectively

Figure 6:CPU time in seconds

Table 1:Number of convergent (NCP) and divergent points (NDP) for f1(x)?f5(x)

The last set in Fig.6 shows the average CPU time needed for each scheme when applied to the five test problems.Overall,Halley,MH,and HM need less time to display the basins of attraction of their zeros,followed by CM,PP,KW,FS and WF.

4 Conclusion

We have compared several iterative schemes for nonlinear equations by visualizing their basins of attraction and finding out the number of convergent and divergent points for the iterative schemes in a selected region.Although all iterative schemes in this work have been selected of equal order of convergence and most of them have an equal number of function evaluations at each iteration,but clear differences have been noted in their behaviors.One can easily note that being an iterative scheme with smooth basins of attraction does not mean that the scheme has a larger area of convergence.In addition,we can conclude that it’s not necessary that a onestep iterative scheme is better than a two-step iterative scheme of the same order.Hence,it is not easy to determine if a specific iterative scheme is better than the other.Finally,even though all the iterative schemes used in this work have the same efficiency index,however,the results show that there are sometimes big differences in their basins of attraction and hence their area of convergence.These results force the need of proposing another index that reflects the real accuracy and efficiency of the iterative schemes.

Funding Statement:We are grateful for the financial support from UKM’s research Grant GUP-2019-033.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.