# Numerical Algorithms for Finding Zeros of Nonlinear Equations and Their Dynamical Aspects

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

---

## Abstract

In this paper, we developed two new numerical algorithms for finding zeros of nonlinear equations in one dimension and one of them is second derivative free which has been removed using the interpolation technique. We derive these algorithms with the help of Taylor’s series expansion and Golbabai and Javidi’s method. The convergence analysis of these algorithms is discussed. It is established that the newly developed algorithms have sixth order of convergence. Several numerical examples have been solved which prove the better efficiency of these algorithms as compared to other well-known iterative methods of the same kind. Finally, the comparison of polynomiographs generated by other well-known iterative methods with our developed algorithms has been made which reflects their dynamical aspects.


---

## Body

## 1. Introduction

One of the major problems in applied mathematics and engineering sciences is to solve the nonlinear equation of the form:(1)fx=0,where f is a real-valued function whose domain is an open connected set.The solution of such type of nonlinear equations cannot be found directly except in special cases. Therefore, we have to adopt iterative methods for solving such type of equations. In iterative methods, we start with an initial guessx0 which is improved step by step by means of iterations.We assume thatα is a simple zero of equation (1) and x0 is an initial guess sufficiently close to α.Using Taylor’s series aroundx0 for equation (1), we have(2)fx0+x−x0f′x0+x−x022!f″x0+⋯=0.Iff ′(x0) ≠ 0, we can evaluate the above expression as follows:(3)fx0+x−x0f′x0=0.If we choosexk+1 the root of equation, then we have(4)xk+1=xk−fxkf′xk.This is so-called Newton’s method [1, 2] for root-finding of nonlinear functions, which converges quadratically. From equation (2), one can evaluate(5)xk+1=xk−2fxkf′xk2f′2xk−fxkf″xk.This is so-called Halley’s method [3] for root-finding of nonlinear functions, which converges cubically. Simplification of equation (2) yields another iterative method as follows:(6)xk+1=xk−fxkf′xk−f2xkf″xk2f′3xk.This is known as Househölder’s method [4] for solving nonlinear equations in one variable, which converges cubically.In recent years, a large number of iterative methods have been developed using different techniques such as decomposition method, Taylor’s series, perturbation method, quadrature formula, and variational iteration techniques [5–13] and the references therein.For improving convergence, various modified methods have been developed in the literature. Some of them are given in [14–18] and the references therein.In the twentieth century, Ostrowski [19] took Newton’s method as a predictor step and proposed a two-step iterative method having fourth convergence order. After that, Traub [12] suggested an iterative scheme in which he took Newton’s method as a predictor and corrector step and proved that the proposed method has convergence of fourth order. Noor and Noor, in 2007 [13], developed the two-step Halley’s method in which Newton’s method was taken as a predictor step and Halley’s method as a corrector step and then proved that the suggested method has sixth order of convergence and then removing its second derivative using finite difference scheme and established a new algorithm having fifth order of convergence. In 2018, Kumar et al. [20] established a parameter-based family of algorithm which has sixth convergence order for solving nonlinear equations.In this paper, we proposed and analyzed two new predictor-corrector type iterative methods, namely, Algorithms1 and 2 in which we take Newton’s method as a predictor step. We proved that these newly developed algorithms have sixth order of convergence and are most efficient as compared to other well-known iterative methods of the same kind. The proposed algorithms applied to solve some test examples in order to assess its validity and accuracy. In the last section, we generate the polynomiographs of complex polynomials of different degrees through our proposed algorithms and compare it with other methods of the same category. The presented polynomiographs have very interesting and aesthetic patterns which reflects different properties of the polynomials.


## 2. Main Results

Letf: X ⟶ R, X ⊆ R is a scalar function, then by using the basic idea of modified homotopy perturbation method, Golbabai and Javidi [21] derive the following method: (7)x=x0−fx0f′x0−f2x0f″x02f′3x0−fx0f′x0f″x0.In iterative form:(8)xn+1=xn−fxnf′xn−f2xnf″xn2f′3xn−fxnf′xnf″xn,which is known as Golbabai and Javidi’s method [21] having cubic order of convergence.After simplification of equation (2), one can obtain(9)x=x0−fx0f′x0−x−x02f″x02f′x0.Now from Golbabai and Javidi’s method in equation (7),(10)x−x0=−fx0f′x0−f2x0f″x02f′3x0−fx0f′x0f″x0.With the help of equations (9) and (10), we obtain(11)x=x0−fx0f′x0−f2x0f″x02f′2x0−fx0f″x028f′3x0f′2x0−fx0f″x0.Rewriting the above equation with Newton’s method as a predictor gives us a new algorithm as follows.Algorithm 1.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(12)yn=xn−fxnf′xn,n=0,1,2,...,xn+1=yn−fynf′yn−f2ynf″yn2f′2yn−fynf″yn28f′3ynf′2yn−fynf″yn,which is the modification of Golbabai and Javidi's method with Newton’s method as a predictor.
In order to find the solution of the given nonlinear equation, we have to calculate the first as well as the second derivative of the functionf(x). But in several cases, we face such a situation where the second derivative of the function does not exist and our method fails to find the solution.
To overcome this difficulty, we use interpolation technique for approximating the second derivative as follows:
Consider the function(13)Ds=a+bs−yn+cs−yn2+ds−yn3,where a, b, c, and d are unknowns to be found with the following interpolation conditions:(14)fxn=Dxn,fwn=Dwn,f′xn=D′xn,f′wn=D′wn,f″wn=D″wn.
A system of four linear equations of four variables is obtained from the above conditions. Solving this system gives(15)f″yn=6fxn−fyn−2xn−yn2f′yn+f′xnxn−yn2=Dxn,yn.
Using the above equation in Algorithm1, we derive a new algorithm free from second derivative as follows.Algorithm 2.
For a givenx0, compute the approximate solution xn+1 by the following iterative schemes:(16)yn=xn−fxnf′xn,n=0,1,2,...,xn+1=yn−fynf′yn−f2ynDxn,yn2f′2yn−fynDxn,yn28f′3ynf′2yn−fynDxn,yn,which is a new two-step iterative method free from second derivative, having Newton’s method as a predictor step. With the help of this method, we can solve such type of nonlinear equations in which second derivative does not exist. Also this requires only two evaluations of the function and one of its derivatives which shows better efficiency of this method as compared to those which require second derivative. Several examples are given which proved best performance of this method as compared to other well-known iterative methods of the same kind.


## 3. Convergence Analysis

In this section, we discuss the convergence order of the purposed iterative methods.Theorem 1.
Suppose thatα is a root of the equation f(x) = 0. If f(x) is sufficiently smooth in the neighborhood of α, then the order of convergence of Algorithm 1 is six.Proof.
To analyze the convergence of Algorithm1, suppose that α is a root of the equation f(x) = 0 and en be the error at nth iteration, then en = xn − α, and by using Taylor series expansion, we have (17)fxn=f′αen+12!f″αen2+13!f‴αen3+14!fivαen4+15!fvαen5+16!fviαen6+Oen7,fxn=f′αen+c2en2+c3en3+c4en4+c5en5+c6en6+Oen7,(18)f′xn=f′α1+2c2en+3c3en2+4c4en3+5c5en4+6c6en5+7c7en6+Oen7,where cn=fnα/n!f′α.
With the help of equations (17) and (18), we get(19)yn=α+c2en2+2c3−c22en3+3c4−7c3c2+4c23en4+−6c33+20c3c22−10c2c4+4c5−8c24en5+−17c3c4+28c4c22−13c2c5+5c6+33c2c33−52c3c23+16c25en6+Oen7,(20)fyn=f′αc2en2+2c3−c22en3+5c23−7c3c2+3c4en4+24c3c22−12c24−10c2c4+4c5−6c32en5+−73c3c23+34c4c22+28c25+37c2c32−17c4c3−13c2c5+5c66en6+Oen7,(21)f′yn=f′α1+2c22en2+4c3c2−c23en3+6c2c4−11c3c22+8c24en4+28c3c23−20c4c22+8c2c5−16c25en5+−16c3c2c4+12c33+60c23c4−26c5c22+10c2c6+32c26en6+Oen7,(22)f″yn=f′α2c2+6c3c2en2+12c32−c3c22en3+−42c2c32+18c4c3+24c3c23+12c4c22en4+−12c3c2c4+24c5c3−36c33+120c22c32−48c3c24−48c4c23en5+−78c2c5c3+30c3c6−54c4c32−96c3c4c22+198c2c33−312c32c23+96c25c3+72c2c42+144c4c24+20c5c23en6+Oen7.
Using equations (19)─(22) in Algorithm 1, we get(23)xn+1=α+−c3c23en6+Oen7,which implies that(24)en+1=−c3c23en6+Oen7.
The above equation shows that the order of convergence of Algorithm1 is six.Theorem 2.
Suppose thatα is a root of the equation f(x) = 0. If f(x) is sufficiently smooth in the neighborhood of α, then the order of convergence of Algorithm 2 is six.Proof.
With the help of equations (17)─(21) along with the same assumptions of the previous theorem, we have(25)Dxn,yn=f′α2c2+6c3c2−2c4en2+12c32−12c3c22+4c2c4−4c5en3+2c2c5+26c4c3−42c2c32+24c3c23+2c4c22−6c6en4+−48c3c2c4+12c42−24c4c23+28c5c3+4c5c22+120c32c22−48c3c24−8c7−36c33en5+−60c2c5c3+28c4c3c22−2c2c7+22c5c4−10c5c23+30c6c3+6c6c22+20c2c42−86c4c32+88c4c24+198c2c33−312c32c23+96c3c25−10c8en6+Oen7.
Using equations (20), (21), and (25) in Algorithm 2, we get(26)xn+1=α+−c3c23+c4c22en6+Oen7,which implies that(27)en+1=−c3c23+c4c22en6+Oen7.
The above equation shows that the order of convergence of Algorithm2 is six.


## 4. Numerical Examples

In this section, we include some nonlinear functions to illustrate the efficiency of our newly developed numerical algorithms. We compare these algorithms with Noor’s method one (NR1) [22], Noor’s method two (NR2) [22], Ostrowski’s method (OM) [19], Traub’s method (TM) [12], and modified Halley’s method (MHM) [13].For this purpose, the following numerical examples have been solved:(28)f1x=x3+4x2−10,f2x=ex+cosπx,f3x=x2+sinx5−14,f4x=xex−1,f5x=x3−10,f6x=cosx−x,f7x=tan−1x+x.Here, we takeε=10−15 in the following stopping criteria xn+1−xn<ε. The numerical examples have been solved using the computer program Maple 13.Tables1–7 show the numerical comparisons of our developed algorithms with Noor's method one (NR1), Noor’s method two (NR2), Ostrowski's method (OM), Traub's method (TM), and modified Halley’s method (MHM). The columns represent the number of iterations N, the magnitude fx of fx at the final estimate xn+1, the approximate root xn+1, the difference between two consecutive approximations xn+1−xn of the equation and the computational order of convergence (COC) which can be approximated using the following formula:(29)COC≈lnxn+1−xn/xn−xn−1lnxn−xn−1/xn−1−xn−2,which was introduced by Weerakoon and Fernando in (2000) [23].Table 1
Comparison of various iterative methods.
MethodNfxn+1xn+1σ=xn+1−xnCOCf1x,x0=−0.4NR1273.710177e−281.365230013414096845806.769715e−152NR241.813409e−367.403402e−133OM57.395989e−458.442974e−124TM841.071491e−431.531881e−114MHM237.392887e−384.595974e−085Algorithm143.518283e−463.794720e−086Algorithm243.518283e−463.794720e−086Table 2
Comparison of various iterative methods.
MethodNfxn+1xn+1σ=xn+1−xnCOCf2x,x0=−1.9NR1173.818521e−23−0.522480772810545489147.695727e−122NR2909.891015e−413.435165e−143OM887.511035e−251.017176e−064TM188.259938e−205.124588e−054MHM91.268356e−484.262132e−115Algorithm181.013204e−251.409549e−046Algorithm231.837741e−825.335861e−146Table 3
Comparison of various iterative methods.
MethodNfxn+1xn+1σ=xn+1−xnCOCf3x,x0=2NR153.163807e−170.409992017989137131625.629386e−092NR2453.382231e−181.512669e−063OM46.783183e−561.630792e−144TM46.063382e−561.586231e−144MHM34.499472e−421.880726e−085Algorithm121.658501e−151.059288e−026Algorithm221.670194e−151.059787e−026Table 4
Comparison of various iterative methods.
MethodNfxn+1xn+1σ=xn+1−xnCOCf4x,x0=1NR144.418933e−190.567143290409783873004.418705e−102NR249.674661e−391.596435e−133OM38.984315e−401.921047e−104TM32.130596e−336.120512e−094MHM31.116440e−682.540557e−145Algorithm125.068654e−206.667718e−046Algorithm222.535508e−214.396326e−046Table 5
Comparison of various iterative methods.
MethodNfxn+1xn+1σ=xn+1−xnCOCf5x,x0=0.5NR11007.261452e−182.154434690031883721801.059948e−092NR2114.753110e−352.385814e−123OM55.537625e−304.942045e−084TM54.893426e−161.369225e−044MHM44.922706e−192.732126e−045Algorithm132.129060e−181.663953e−036Algorithm232.129060e−181.663953e−036Table 6
Comparison of various iterative methods.
MethodNfxn+1xn+1σ=xn+1−xnCOCf6x,x0=2.5NR164.872692e−210.739085133215160641666.769715e−102NR243.229578e−297.403402e−093OM32.576412e−268.442974e−074TM32.617193e−351.531881e−094MHM31.154792e−544.595974e−115Algorithm128.918884e−213.794720e−036Algorithm221.374491e−183.794720e−036Table 7
Comparison of various iterative methods.
MethodNfxn+1xn+1σ=xn+1−xnCOCf7x,x0=2NR142.455690e−160.000000000000000000009.031605e−062NR243.424681e−401.271327e−133OM32.704322e−411.194704e−084TM37.907266e−1225.282400e−144MHM31.556811e−666.000887e−105Algorithm122.674407e−218.437184e−036Algorithm223.197382e−153.593740e−026Tables8 shows the comparison of the number of iterations required for different iterative methods with our developed algorithms to approximate the root of the given nonlinear function for the stopping criteria ε=10−100. The columns represent the number of iterations for different functions along with initial guess x0. All calculations have been carried out using the computer program Maple 13.Table 8
Comparison of the number of iterations required for different iterative methods forε=10−100.
MethodsFunctionsf1xx0=−0.4f2xx0=−1.9f3xx0=2.0f4xx0=1.0f5xx0=0.5f6xx0=2.5f7xx0=2.0NR129208710396NR2591651265OM68954644TM852054743MHM241044644Algorithm15943433Algorithm25443433


## 5. Polynomiography

Polynomials are one of the most significant objects in many fields of mathematics. Polynomial root-finding has played a key role in the history of mathematics. It is one of the oldest and most deeply studied mathematical problems. The last interesting contribution to the polynomials root-finding history was made by Kalantari [24], who introduced the polynomiography. As a method which generates nice-looking graphics, it was patented by Kalantari in USA in 2005 [25]. Polynomiography is defined to be “the art and science of visualization in approximation of the zeros of complex polynomials, via fractal, and nonfractal images created using the mathematical convergence properties of iteration functions” [24]. An individual image is called a “polynomiograph”. Polynomiography combines both art and science aspects. Polynomiography gives a new way to solve the ancient problem by using new algorithms and computer technology. Polynomiography is based on the use of one or an infinite number of iteration methods formulated for the purpose of approximation of the roots of polynomials, e.g., Newton’s method and Halley’s method.The word “fractal,” which partially appeared in the definition of polynomiography, was coined by the famous mathematician Benoit Mandelbrot [26]. Both fractal images and polynomiographs can be obtained via different iterative schemes. Fractals are self-similar having typical structure and independent of scale. On the other hand, polynomiographs are quite different. The “polynomiographer” can control the shape and design in a more predictable way by using different iteration methods to the infinite variety of complex polynomials. Generally, fractals and polynomiographs belong to different classes of graphical objects. Polynomiography has diverse applications in Mathematics, Science, Education, Art, and Design.According to the fundamental theorem of algebra, any complex polynomial with complex coefficients(30)pz=a0+a1z+a2z2+⋯+an−1zn−1+anzn,or by its zeros r1,r2,r3,…,rn−1,rn(31)pz=z−r1z−r2,…,z−rn−1z−rn,of degree n has n zeros which may or may not be distinct. The degree of polynomial describes the number of basins of attraction and localization of basins can be controlled by placing roots on the complex plane manually. Usually, polynomiographs are colored based on the number of iterations needed to obtain the approximation of some polynomial root with a given accuracy and a chosen iteration method. The description of polynomiography, its theoretical background, and artistic applications are described in [7, 8, 24–29].


## 6. Applications

In the numerical algorithms that are based on the iterative processes, we need a stopping criterion for the process, that is, a test that tells us that the process has converged or it is very near to the solution. This type of test is called a convergence test. Usually, in the iterative process that use a feedback, like the root-finding methods, the standard convergence test has the following form:(32)zn+1−zn<ε,where zn+1 and zn are two successive points in the iteration process and ε >0 is a given accuracy. In this paper, we also use stopping criterion (32). The different colors of an image depend on the number of iterations to reach a root with given accuracy ε. One can obtain infinitely many nice-looking polynomiographs by changing parameter k, where k is the upper bound of the number of iterations.Here, we present some examples of the following complex polynomials using our developed algorithms and compare it with the polynomiographs obtained by using other well-known two-step iterative methods:(33)p1z=z2−1,p2z=z2−12,p3z=z3−1,p4z=z3−12,p5z=z4−1,p6z=z4−12.In Figures1–6, polynomiographs of different complex polynomials for Noor’s method one (NR1), Noor’s method two (NR2), Ostrowski’s method (OM), Traub’s method (TM), modified Halley’s method (MHM), and our developed algorithms have been shown which describe the regions of convergence of these polynomials. When we look at the generated images, we can read two important characteristics. The first one is the speed of convergence of the algorithm, i.e., the color of each point gives us information on how many iterations were performed by the algorithm to reach the root. The second characteristic is the dynamics of the algorithm. Low dynamics is in areas where the variation of colors is small, whereas in areas with a large variation of colors, the dynamics is high. The black color in images shows that places where the solution cannot be achieved for the given number of iterations. The areas of the same colors in the above figures indicate the same number of iterations required to determine the solution and they look similar to the contour lines on the map.Figure 1
Polynomiographs for the polynomialp1z using various iterative methods. (a)Polynomiograph for the polynomial p1z using NR1. (b) Polynomiograph for the polynomial p1z using NR2. (c) Polynomiograph for the polynomial p1z using OM. (d) Polynomiograph for the polynomial p1z using TM. (e) Polynomiograph for the polynomial p1z using MHM. (f)Polynomiograph for the polynomial p1z using Algorithm 1. (g) Polynomiograph for the polynomial p1z using Algorithm 2.
(a)(b)(c)(d)(e)(f)(g)Figure 2
Polynomiographs for the polynomialp2z using various iterative methods. (a) Polynomiograph for the polynomial p2z using NR1. (b) Polynomiograph for the polynomial p2z using NR2. (c) Polynomiograph for the polynomial p2z using OM. (d) Polynomiograph for the polynomial p2z using TM. (e) Polynomiograph for the polynomial p2z using MHM. (f) Polynomiograph for the polynomial p2z using Algorithm 1. (g) Polynomiograph for the polynomial p2z using Algorithm 2.
(a)(b)(c)(d)(e)(f)(g)Figure 3
Polynomiographs for the polynomialp3z using various iterative methods. (a) Polynomiograph for the polynomial p3zusing NR1. (b) Polynomiograph for the polynomial p3zusing NR2. (c) Polynomiograph for the polynomial p3z using OM. (d) Polynomiograph for the polynomial p3z using TM. (e) Polynomiograph for the polynomial p3z using MHM. (f) Polynomiograph for the polynomial p3z using Algorithm 1. (g) Polynomiograph for the polynomial p3z using Algorithm 2.
(a)(b)(c)(d)(e)(f)(g)Figure 4
Polynomiographs for the polynomialp4z using various iterative methods. (a) Polynomiograph for the polynomial p4z using NR1. (b) Polynomiograph for the polynomial p4z using NR2. (c) Polynomiograph for the polynomial p4z using OM. (d) Polynomiograph for the polynomial p4z using TM. (e) Polynomiograph for the polynomial p4z using MHM. (f) Polynomiograph for the polynomial p4z using Algorithm 1. (g) Polynomiograph for the polynomial p4z using Algorithm 2.
(a)(b)(c)(d)(e)(f)(g)Figure 5
Polynomiographs for the polynomialp5z using various iterative methods. (a) Polynomiograph for the polynomial p5z using NR1. (b) Polynomiograph for the polynomial p5z using NR2. (c) Polynomiograph for the polynomial p5z using OM. (d) Polynomiograph for the polynomial p5z using TM. (e) Polynomiograph for the polynomial p5z using MHM. (f) Polynomiograph for the polynomial p5z using Algorithm 1. (g) Polynomiograph for the polynomial p5z using Algorithm 2.
(a)(b)(c)(d)(e)(f)(g)Figure 6
Polynomiographs for the polynomialp6z using various iterative methods. (a) Polynomiograph for the polynomial p6z using NR1. (b) Polynomiograph for the polynomial p6z using NR2. (c) Polynomiograph for the polynomial p6z using OM. (d) Polynomiograph for the polynomial p6z using TM. (e) Polynomiograph for the polynomial p6z using MHM. (f) Polynomiograph for the polynomial p6z using Algorithm 1. (g) Polynomiograph for the polynomial p6z using Algorithm 2.
(a)(b)(c)(d)(e)(f)(g)All these figures have been generated using the computer program Mathematica10.0 by taking ε=10−03 and k=15 where ε shows the accuracy of the given root and k represents the upper bound of the number of iterations.


## 7. Conclusions

Two new numerical algorithms for finding zeros of nonlinear equations have been developed, having convergence of order six. By using some test examples, the performance of the proposed algorithms is also discussed. The numerical results uphold the analysis of the convergence which can be seen in Tables1–8. Both algorithms show better results in terms of the number of iterations, efficiency, and convergence order in comparison with other well-known two-step iterative methods of the same kind. Polynomiographs of complex polynomials of different degrees using two-step iterative methods and our proposed algorithms have been generated. The presented polynomiographs are rich and colorful and have very interesting and aesthetic patterns, which reflects the dynamical aspects of our proposed algorithms.



---

*Source: 2816843-2020-09-30.xml*