Computer Geometries for Finding All Real Zeros of Polynomial Equations Simultaneously

Naila Rafiq,Saima Akram,Mudassir Shamsand Nazir Ahmad Mir

1Department of Mathematics,NUML,Islamabad,44000,Pakistan

2Centre for Advanced Studies in Pure&Applied Mathematics,Bahauddin Zakariya University,Multan

3Department of Mathematics and Statistics,Riphah International University I-14,Islamabad,44000,Pakistan

Abstract:In this research article,we construct a family of derivative free simultaneous numerical schemes to approximate all real zero of non-linear polynomial equation.We make a comparative analysis of the newly constructed numerical schemes with a well-known existing simultaneous method for determining all the distinct real zeros of polynomial equations using computer algebra system Mat Lab.Lower bound of convergence of simultaneous schemes is calculated using Mathematica.Global convergence property of the numerical schemes is presented by taking random starting initial approximation and their convergence history are graphically presented.Some real life engineering applications along with some higher degree polynomials are considered as numerical test problems to show performance and efficiency of the derivative free family of numerical methods with comparison of an existing method of same order in literature.Local computationalorder of convergence,CPU time,graph of computational order of convergence and residual error graphs elaborate efficiency,robustness and authentication of the suggested family of numerical methods in its domain.

Keywords:Polynomials;simultaneous iterative methods;random initial guesses;lower bound;local computational order;CAS-mathematica and mat lab

1 Introduction

One of the most primal problem of science and engineering is locating the zeros of polynomial of degreekwith arbitrary real coefficient.

Letξ1,...,ξkdenote all the simple zeros of Eq.(1).According to Abel’s impossibility theorem [1]“There is no solution in radical to general polynomial with arbitrary co-efficient of degree five or higher” we therefore look toward numerical schemes to approximate zeros of polynomial Eq.(1).

There exist a lot of numerical schemes in literature which approximate single zeros at a time(see,e.g.,[2-4]).Here,we consider the following family of numerical schemes [5]:

The numerical scheme Eq.(2) approximate single zero of Eq.(1) at a time.

Beside these single roots finding methods,mathematicians and engineers are interested in simultaneous numerical schemes which approximate all roots simultaneously.More detail on simultaneous methods,their global convergence and parallel implementation on computer algebra system (CAS) and stability are found in [6,7]and reference cite there in [8-14].

Therefore,the main aim of this research article is to construct a derivative free numerical scheme which approximates all real zero of Eq.(1).Using CAS-Mathematica,we find the lower bound of convergence to verify convergence order theoretically.Computational order of convergence [15]and convergence history for random initial approximations are graphed to show the efficiency and performance of numerical schemes as compared to other existing methods of same order.Log of residual graph,graphs of computational order of convergence and local computational order of convergence [16]support the global convergence behavior of our newly constructed numerical scheme for estimating all real zeros of Eq.(1).

2 Construction of Numerical Scheme

Corresponding to numerical schemes

for approximating all zeros of Eq.(1),the numerical method is

This numerical method is well known Weierstrass method [17]for approximating all zeros of polynomial Eq.(1) having local quadratic convergence.Using in analogical way as above,we convert Eq.(2) into simultaneous method as:

Nedzhibov et al.[18]in 2005,present the following cubic convergence derivative free family of simultaneous numerical schemes (abbreviated as ND) as:

2.1 Convergence Analysis

Here,we prove the convergence order of the suggested derivative free family of numerical schemes.

Theorem:Let algebraic polynomial Eq.(1)has k number of simple zeros ξ1,...,ξk and for suffi-ciently close initial guesses,...,scheme MD has third order convergence.

Iterative schemes Eq.(5) can be written as:

Substitution in Eq.(5),we have:

Then,for ?Gi,we have:

The following relation holds true:

If we assume that,absolute values of all errors are of the same order,say |εi|=|εj|=O(|ε|),then

Thus,

Hence,the theorem is proved.

2.2 Using CAS-Mathematica for Finding Lower Bound of Convergence

Consider

and the first componentH(x(n))of iterative scheme Eq.(5) to find zeros of Eq.(15),simultaneously.In order to find lower bound of convergence,we have to express the differential of an operatorH(x(n))in terms of their partial derivate of its component asHi(x):

and to so on.

The lower bound of the convergence is obtained until the first non-zero element of row is found zero (see [19]).The Mathematica program is given for each of the considered method as:

· MD method

In[1]:=D[H1[x1,x2,x3],x1]/.{x1→φ1,x2→φ2,x3→φ3}

Out[1]:=0

In[2]:=D[H1[x1,x2,x3],x2]/.{x1→φ1,x2→φ2,x3→φ3}]

Out[2]:=0

In[2]:=D[H1[x1,x2,x3],x2]/.{x1→φ1,x2→φ2,x3→φ3}]

Out[2]:=0

In[34]:=Simplify[D[H1[x1,x2,x3],x1,x1,x1,x2]/.{x1→φ1,x2→φ2,x3→φ3}]

· ND method

3 Numerical Results

Here,some numerical examples from [20,21]are considered with and without random initial approximation to estimate all real zeros of polynomial equation of higher degree.All the computations are performed using Mat Lab R@2011 with 64 digits floating point arithmetic.We take∈=10-30as tolerance and use the following stopping criteria

whereeirepresents the absolute error.We compare our iterative schemes MD with ND of the same convergence order.In all numerical calculations,we takeβ=2.

Example 1:Consider a stirred tank reactor (SCRT) in which two items A and R are feed in reactor at Q and q-Q rate respectively.A complex reaction

a+r→b;b+r→c;c+r→r;c+r→e,develops the following function

We obtained an algebraic polynomial equation of degree 4 by taking ?c=0 in Eq.(16)

f1(x)=x4+11.5x3+47.49x2+83.06325x+51.32366875=0 with exact roots:

ζ1=-1.45,ζ2=-2.85,ζ3=-2.85,ζ4=-4.45

Convergence history and computational order of convergence graph (Figs.1,4,7 and 10) of numerical schemes ND,MD are obtained by taking the following random initial guessed valued in our computer program i.e.,

X1=[0.032601;0.5612;0.88187;0.66918],

where X1=[x(0)i,i=1,...,4].Using random initial guessed value X1,the iterative scheme MD converges to exact zeros after 100 iteration by consuming 16.848368 s CPU time while ND converges after 155 iterations and consumes 37.249147 s.

Figure 1:Shows convergence history of numerical scheme MD for polynomial equation f1(x)

Convergence rates increase by taking the following initial guessed value:

Figure 2:Shows convergence history of numerical scheme MD for polynomial equation f2(x)

Figure 3:Shows convergence history of numerical scheme MD for polynomial equation f3(x)

The numerical results are presented in Tabs.1-6.In all Tabs.1-6,CO presents convergence order,CPU,presents CPU time and local computational order of convergence (LCOC) byσ.

Example 2:Consider

with exact roots:

ζ1=1,ζ2=-2,ζ3=3,ζ4=-4,ζ5=5.

Figure 4:Shows convergence history of numerical scheme ND for polynomial equation f1(x)

Figure 5:Shows convergence history of numerical scheme ND for polynomial equation f2(x)

For convergence history and computational order of convergence graph (Figs.2,5,8 and 11)of numerical schemes ND,MD,we used the following initial guessed valued in our computer program i.e.,

X2=[0.81472;0.90579;0.12699;0.91338;0.63236]

where X2=[x(0)i,i=1,...,5].Using random initial guessed values X2,the iterative scheme MD converges to exact zeros after 92 iteration by consuming 27.056098 s CPU time while ND converges after 98 iterations and consumes 31.444833 s.

Figure 6:Shows convergence history of numerical scheme ND for polynomial equation f3(x)

Figure 7:Shows computational order of convergence of numerical scheme MD for polynomial equation f1(x)

Convergence rates increase by taking the following initial guessed value:

Example 3:Consider

with exact roots:

ζ1=-1,ζ2=1,ζ3=3,ζ4=4,ζ5=7,ζ6=5,ζ7=8.

Figure 8:Shows computational order of convergence of numerical scheme MD for polynomial equation f2(x)

Figure 9:Shows computational order of convergence of numerical scheme MD for polynomial equation f3(x)

For convergence history and computational order of convergence graph (Figs.3,6,9 and 12)of numerical schemes ND,MD are obtained by taking the following initial guessed valued in our computer program i.e.,

X3=[0.77029;0.35022;0.66201;0.41616;0.84193;0.83193;0.83292;0.25644],

where X3=[,i=1,...,7].Using random initial guessed value X3,the iterative scheme MD converges to exact zero after 19 iterations by consuming 13.7714 s CPU time while ND converges after 23 iterations and consumes 18.120062 s.

Figure 10:Shows computational order of convergence of numerical scheme ND for polynomial equation f1(x)

Table 1:Simultaneous determination of all zeros of polynomial f1(x)

Table 2:Local computational order of convergence for polynomial f1(x)

Table 3:Simultaneous determination of all zeros of polynomial f2(x)

Table 4:Local computational order of convergence for polynomial f2(x)

Table 5:Simultaneous determination of all zeros of polynomial f3(x)

Table 6:Local computational order of convergence for polynomial f3(x)

Figure 11:Shows computational order of convergence of numerical scheme ND for polynomial equation f2(x)

Figure 12:Shows computational order of convergence of numerical scheme ND for polynomial equation f3(x)

Figure 13:Shows residual fall for iterative method MD and ND for polynomial f1(x) respectively

Convergence rates increase by taking the following initial guessed value:

Figure 14:Shows residual fall for iterative method MD and ND for polynomial f2(x) respectively

Figure 15:Shows residual fall for iterative method MD and ND for polynomial f3(x) respectively

4 Conclusions

Here,we have developed a family of derivative free method for approximating all real zeros of polynomial.Lower bound of convergence of iterative methods MD and ND are calculated using CAS-Mathematica.Using Mat Lab,we graph convergence history and computational order of convergence.From Tabs.1-6 and Figs.1-15,we observe that our method MD is much better in terms of convergence history,computational order of convergence,numerical results,log of residual and local computational order of convergence as compared to ND method.

Funding Statement:The authors received no specific funding for this study.

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