Highly efficient family of two-step simultaneous method for all polynomial roots

1.   Introduction

Many theoretical and applied problems in different fields of study, such as physical sciences, biomedical engineering, chemistry, biological and chemical sciences, computer sciences, finance, statistics, economics and applied mathematical sciences contain symmetry, which may result a nonlinear polynomial equation

with $m$ distinct roots $\wp _{1}, ..., \wp _{m}$. There are numerous numerical iterative methods for computing the roots of polynomial equations. These methods can be classified into two types: numerical iterative methods that approximate a single root at a time and iterative numerical methods that approximate all of the roots of a nonlinear polynomial equation simultaneously.

The Newton-Raphson method given as

is one the most commonly used numerical methods to approximate a single root of Eq (1.1) at a time, thanks to its local quadratic convergence. Iterative methods, such as Eq (1.2), have a significant drawback in that they require derivative evaluation at each iteration, which incurs a significant computational cost, and diverge if $\vartheta ^{\prime }(\varkappa ^{(i)}) = 0$ or the initial guess is far from the root. See, for example, the work of Akram et al.^[1], Cordero et al.^[2], Agarwal et al. ^[3], Chicharro et al. ^[4], Behl et al.^[5], Chun et al. ^[6], Zafar et al.^[7] and many others). Simultaneous methods having global convergence property, are stable and applicable for parallel execution as well. Convergence analysis, computational efficiency and parallel implementation of simultaneous iterative techniques have been studied by McNamee ^[8], Nedzhibov ^[9], Proinov et al. ^[10], Mir et al. ^[11], Cholakov ^[12], Proinov and Vasileva ^[13], Proinov and Petkova ^[14], Sanchez et al.^[15], Ivanov ^[16], Kanno et al.^[17] as well as the references cited therein.

Weierstrass method (WDM)^[18], which approximates all the roots of Eq (1.1) simultaneously, given by

is one of the most famous iterative techniques used in comparison to Newton Raphson. The term $\frac{\vartheta (\varkappa _{t}^{(i)})}{\underset{ \underset{r = 1}{ r\neq t}}{\overset{m}{\Pi }}(\varkappa _{t}^{(i)}-\varkappa _{r}^{(i)})}$ is called Weierstrass correction. The Weierstrass method, which simultaneously approximates all roots of Eq (1.1), has local quadratic convergence. Weierstrass introduced the method in 1891, and it was rediscovered by Kerner ^[19], Durand ^[20], Dochev ^[21], and Presic ^[22]. Dochev demonstrated the first local quadratic convergence of the Weierstrass iterative technique in 1962.

Later on, in 2015, Proinov ^[23] presented the general convergence theorem for the iterative process and discussed the use of the Weierstrass root approximating technique. In 2016, Nedzibove ^[24] developed a modified version of Eq (1.3), and Marcheva et al.^[25] presented the local convergence theorem of the modified Weierstrass method in 2020. Song et al.^[26] created and verified three new derivative-free simultaneous iterative Weierstrass computational methods for calculating all polynomial problem roots.

The goal of this paper is to develop and analyze the derivative-free family of Weierstrass-type methods with accelerated convergence in order to find the roots of the above problem, which should have better convergence behavior than the Weierstrass method. We analyze the convergence behavior of the proposed method by computing CPU-time, log of residual errors, computational errors, and drawing dynamical planes while solving numerical test problems. Several graphs are plotted to demonstrate that the newly constructed method outperforms existing methods in the literature in efficiency and accuracy.

2.   Derivation and theoretical convergence analysis of the simultaneous root finding method

First, we present the third order family of the single root finding method (MS), and then we generalize this scheme to simultaneously find all the roots of Eq (1.1):

where $y^{(i)} = \varkappa ^{(i)}-\frac{\vartheta (\varkappa ^{(i)})}{ \vartheta ^{\prime }(\varkappa ^{(i)})}$ and $\alpha \in \Re$.

The convergence theorem that follows validates our assumption.

Theorem 1. Let $\overline {\rlap{-} T}$ be an open interval and $\wp \in \overline {\rlap{-} T}$ indicate the precise root of a function that is sufficiently differentiable for $\vartheta :\overline {\rlap{-} T}\subseteq \Re \longrightarrow$ $\Re$ in an open interval $\overline {\rlap{-} T}$. The following error equation is satisfied if the convergence order of the family of iterative numerical procedures is three and $\varkappa ^{(0)}$ is close to $\wp$:

where $\Im _{m} = \frac{\vartheta ^{m}(\wp)}{m!\vartheta ^{\prime }(\wp)}, m\geq 2.$

Proof. Let $\wp$ be a single exact-root of $\vartheta$ and $\varkappa^{(i)} = \wp +\varsigma^{(i)}$, where $e^{(i)}$ is the error at $i$th iterative step. The following is the result of expanding $\vartheta(\varkappa^{(i)})$ around $\varkappa = \wp,$ using Taylor's series with $\vartheta(\wp) = 0:$

and

Dividing (2.3) by (2.4), we have:

and

Using $\vartheta ^{\prime }(y^{(i)})$ and $\vartheta ^{\prime }(u^{(i)})$ in the 2$^{nd}$-step of (2.1), we have:

Thus,

and it becomes

Hence the theorem is proved. □

Now, we convert iterative method (2.1) to simultaneous method by using Weierstrass correction ^[8] given by

as follows:

where $y_{t}^{(i)} = \varkappa _{t}^{(i)}-\frac{\vartheta (\varkappa _{t}^{(i)})}{\underset{\underset{r = 1}{r\neq t}}{\overset{m}{\Pi }}(\varkappa _{t}^{(i)}-\widehat{\varkappa }_{r}^{(i)})}, (t, r = 1, 2, 3, ..., n)$ and $\widehat{ \varkappa }_{r}^{(i)}$ is a modified two step Steffensen-type ^[27] fourth-order convergent method, i.e., $\widehat{\varkappa }_{r}^{(i)} = y_{r}^{(i)}-\frac{\vartheta (y_{r}^{(i)})}{ \vartheta \left[\varkappa _{r}^{(i)}, y_{r}^{(i)}\right] +\vartheta \left[ y_{r}^{(i)}, t_{r}^{(i)}\right] -\vartheta \left[\varkappa _{r}^{(i)}, t_{r}^{(i)}\right] +\alpha \left(y_{r}^{(i)}-\varkappa _{r}^{(i)}\right) \left(y_{r}^{(i)}-t_{r}^{(i)}\right) }$, $y_{r}^{(i)} = \varkappa _{r}^{(i)}-\frac{\vartheta (\varkappa _{r}^{(i)})}{\vartheta \left[ \varkappa _{r}^{(i)}, t_{r}^{(i)}\right] }, t_{r}^{(i)} = \varkappa _{r}^{(i)}+\vartheta (\varkappa _{r}^{(i)})$, $\alpha \in \Re$. In this case, $\vartheta \left[., .\right]$ is the divided difference of order one and two, respectively.

Remark 1. The family of derivative-free methods (2.8) determines all distinct roots of (1.1) simultaneously and is abbreviated as MM.

2.1.   Convergence analysis

This section discusses MM convergence analysis.

Theorem 2. Let $\wp _{_{1}}, \wp _{_{2}}, ..., \wp _{\mathit{\text{m}}}$ be m simple roots of (1.1). If$\ \varkappa _{1}^{(0)},$ $\varkappa _{2}^{(0)}, ..., \varkappa _{ \mathit{\text{m}}}^{(0)}$ are, respectively, the initial estimates of the roots and close to exact roots, then MM has fifth-order convergence.

Proof. Let $\epsilon _{t} = \varkappa_{t}-\wp _{t},$ $\epsilon _{t}^{\prime } = y_{t}-\wp _{t}$ and $\epsilon _{t}^{\prime \prime } = z_{t}-\wp _{t}$ be the residual errors in $\varkappa_{t}, y_{t}$ and $z_{t}$ estimations, respectively. To simplify things, we leave out iteration index $i$. From the $1^{st}$-step of (2.8), we have:

where $\Delta(\varkappa_{t}) = \frac{\vartheta (\varkappa_{t})}{\underset{\underset{j = 1}{j\neq t}}{\overset{m }{\Pi }}(\varkappa_{i}-\widehat{u}_{j})}$ and

with

and $\widehat{\varkappa}_{j}-\wp _{j} =$O $(\epsilon ^{\; 4})$ (see ^[27]). Now, for a small enough $\epsilon$: if $\wp _{t}$ is a simple root, then $\left\vert \varkappa_{i}-\varkappa_{j}\right\vert$ is bounded away from zero, resulting in the following expression:

Then it implies that:

From (2.9), we have

Now by taking the 2$^{nd}$-step of Eq (2.8), we have:

where

Assume $\epsilon _{t} = \epsilon _{j}$ are same order, say $\text{O}(\epsilon_{t})$, then it follows that

Using Eq (2.14) in Eq (2.12), we have:

Hence, the theorem is proved. □

3.   Basins of attraction

We employ the real and imaginary portions of the initial approximations across a grid of $250\times 250$ of square $[-2.5\times 2.5]^{2}\in \mathbb{C}$ in the complex plane to construct the basins of attraction of the iterative procedures used by MS, MM and the Zhang et al.^[28] method (ZPH). Due to the global convergence behavior of the simultaneous technique, the maximum number of iterations was set at 15 and the stopping criterion was $\left\vert \vartheta \left(\varkappa _{t}^{\left(i\right) }\right) \right\vert < 10^{-5}$. We employ various colors to show the root at which the iterative technique converges, and black in all other cases. Basin colors sharpness signifies fewer iterations. We consider the following two non-linear functions for the generation of basins: $\vartheta _{1}(\varkappa) = \varkappa ^{3}-1$ with exact roots -1, -0.5+0.866i, -0.5-0.866i, and $\vartheta _{2}(\varkappa) = \varkappa ^{6}-1i*\varkappa^{3}+1$ with exact roots -1.0167+0.587i, -1.1740i, 1.0167+0.587i, -0.7377-0.4259i, 0.8518i, 0.7377-0.4259i$.$ Figures 1(a, c, e, g) and 2(a, c, e, g), present the basins of attraction of numerical iterative scheme MS for various parameter values of $\alpha$ and Figures 1(b, d, f, h) and 2(b, d, f, h) show basins of attraction of simultaneous methods MM (for various parameter values of $\alpha$) and ZPH respectively for non-linear equation $\vartheta _{1}(\varkappa)$$-$$\vartheta _{2}(\varkappa)$. Table 1 and color brightness in Figure 1(b, d, f) shows the ascendancy in efficiency of MM as compared to MS and ZPH.

Table 1 clearly demonstrates that the simultaneous method MM surpasses MS and ZPH in terms of actual time and number of cycles required for convergence to the exact root of the equation $\vartheta_{1}(\varkappa)$ and $\vartheta_{2}(\varkappa)$ for any initial guessed value used to generate basins of attraction.

4.   Percentage computational efficiency

Here, we compare the computation % efficiency of Zhang et al.'s ^[28] convergence order five technique (abbreviated as ZPH), i.e.,

with our newly proposed method based on the efficiency index $E$ defined in ^[29]

where D is the cost of numerical computer calculation

and $\tau$ is the convergence order of iterative numerical schemes. Thus, (4.2) becomes:

By using (4.4) and the information in Table 2, the percentage efficiency ratio of simultaneous numerical iterative methods can be determined employing the following formula for$\rho ((MM), (ZPH))$ given by:

where $O(m) = B$. The dominance efficiency of MM over ZPH is demonstrated clearly in Figure 3(a, b).

5.   Numerical results

The ZPH and MM family of techniques were utilized to demonstrate the use and effectiveness of several nonlinear problems from biological engineering ^[12] and applied sciences ^{[29,30,31,32,33,34,35,36]} are considered in this section. All calculations utilize CAS-Maple 18 64-digit floating point arithmetic, and the process of iteration is terminated when

where $\overline{\varsigma}_{t}^{(i)}$ represents the absolute error. For simultaneous calculations of all roots of Eq (1.1), we set

as the fixed stopping criteria. In Tables 3–12, the quantity denoted CPU represents the time required to compute the root using the iterative schemes ZPH and MM, respectively. We use $\alpha = \frac{1}{3}$ and $\beta = \frac{1}{2 }$ in all numerical calculations. In Tables 4, 6, 8, 10, 12 for random initial vectors $(\overset{ (0)}{\vartheta _{1}}$-$\overset{ (0)}{\vartheta _{3}})$ taken from Appendix Table 13, MM and ZPH are represented by MM$_{\vartheta _{1}}$$-$MM3$_{\vartheta _{3}}$ and ZPH$_{\vartheta _{1}}$$-$ZPH$_{\vartheta _{3}}$, respectively.

Example 1. An engineering application.

A non-linear expression described in ^[30]

depicts the minute modification of nitrogen hydrogen (NH) supply at 250 atm and 227 K. The exact roots of Eq (5.1) are $\wp _{1} = 3.9485+0.3161i, \wp _{2} = 3.9485-0.31610i, \wp _{3} = -0.38410, \wp _{4} = 0.2778.$ The initial guessed values for calculating $\vartheta _{3}(\varkappa)$ are taken as equal to $\overset{ (0)}{\varkappa _{1}} = 3.50+0.30i,$ $\overset{ (0)} {\varkappa _{2}} = 3.50-0.30i,$ $\overset{ (0)}{\varkappa } _{3} = -0.30+0.010i, \overset{ (0)}{\varkappa }_{4} = 1.80+0.010i.$

On the basis of efficiency achieved after five iterations, Table 3 unequivocally shows that the MM technique outperforms the ZPH method. Table 1 displays the global convergence behavior of the proposed numerical schemes on various randomly generated initial guesses (see Appendix Table 13).

In Table 4, ZPH$_{\vartheta _{1}}$$-$ZPH$_{\vartheta _{3}}$ and MM$_{\vartheta _{1}}$$-$MM$_{\vartheta _{3}}$ the numerical scheme ZPH and MM outputs for random initial vectors generated by the MATLAB computing tool. Numerical results of Table 4 clearly indicate numerical schemes are far better than ZPH for solving (5.1) and more complex engineering problems. The number of iterations and CPU time significantly increase when compared to the numerical results obtained in Table 3. Table 4 shows that for any initial vector choice, the method MM converges to exact roots with greater efficiency than ZPH.

Example 2. Predator-prey model (PPM).

Consider PPM in which predication rate ^[7] is denoted by

where $\varkappa$ is the amount of aphids as victims ^[31] and female microbes as a predator. Malthusian Model holds $G(\varkappa) = r\varkappa,$ as the growth rate of aphids. For solution of the PPM we take $\overline{P} (\varkappa) = \overline{G}(\varkappa)$. This implies

Taking $\overline{k} = 30$ (the way pests are devoured), $\overline{a} = 20$ (amount of bugs) and $i = 2^{\frac{-1}{3}}$ (hourly amount) in (5.3), we get:

The exact roots of Eq (5.4) are $\wp _{1} = 25.198, \; \wp _{2} = 25.198, \; \wp _{3} = 12.84.$ The initial guessed estimates for $\vartheta _{4}(\varkappa)$ are selected as:

After seventeen iterations, Table 5 clearly shows that the MM methodology outperforms the ZPH method in terms of efficiency. Table 6 displays the global convergence behavior of the proposed numerical schemes on various randomly generated initial guesses (see Appendix Table 13).

Table 6 shows the numerical schemes ZPH$_{\vartheta _{1}}$$-$ZPH$_{\vartheta _{3}}$ and MM$_{\vartheta _{1}}$$-$MM$_{\vartheta _{3}}$ outputs for random initial vectors generated by the MATLAB computing tool. The numerical results of the table clearly show that the proposed numerical schemes are superior to ZPH for solving (5.4) and more difficult engineering problems. The number of iterations and CPU time significantly increase when compared to the numerical results obtained in Table 5. Table 6 shows that for any initial vector choice, the method MM converges to exact roots with greater efficiency than ZPH on iteration 37.

Example 3. Beam positioning problem.

In this example, we look at a beam positioning problem ^[32], which yields a nonlinear function

The exact roots of Eq (5.5) are

The initial estimates for $\vartheta _{3}(\varkappa)$ are

On the basis of efficiency achieved after six iterations, Table 7 unequivocally shows that the MM technique outperforms the ZPH method. Table 8 displays the global convergence behavior of the proposed numerical schemes on various randomly generated initial guesses (see Appendix Table 13).

Table 8 shows the numerical schemes ZPH$_{\vartheta _{1}}$$-$ZPH$_{\vartheta _{3}}$ and MM$_{\vartheta _{1}}$$-$MM$_{\vartheta _{3}}$ outputs for random initial vectors generated by the MATLAB computing tool. The numerical results of the Table 8 clearly show that the proposed numerical schemes are superior to ZPH for solving (5.5) and more difficult engineering problems. The number of iterations and CPU time significantly increase when compared to the numerical results obtained in Table 7. Table 8 shows that for any initial vector choice, the method MM converges to exact roots with greater efficiency than ZPH on iteration 11.

Example 4. ^[33] Nuclear boiler.

Consider a nuclear boiler, with the substances $\breve{A}\breve{A }$ and $\check{R}\check{R}$, breastfed to the apparatus at rates of $\widehat{Q}$ and q-$\widehat{Q}$, respectively. The following are the results of the multifaceted reaction system produced in the container:

Douglas et al. ^[34] tested this issue in order to create straightforward feedback control systems as:

or

where $\hat{H}_{\Im }$ denotes the proportional controller's gain. This control system is stable for all values of $\hat{H}_{\Im }$ that yield transfer function roots with negative real parts. Taking $\hat{H}_{\Im } = 0$ in (5.7), we have:

$\vartheta _{6}\left(\varkappa \right)$ has the four negative real roots listed below:

We take the root as $\wp = -4.45$ and

are chosen as initial estimates for finding all roots of (5.8) simultaneously.

On the basis of efficiency achieved after seventh iterations, Table 9 unequivocally shows that the MM technique outperforms the ZPH method.

Table 10 displays the global convergence behavior of the proposed numerical schemes on various randomly generated initial guesses (see appendix Table 13).

Table 10 shows the numerical schemes ZPH$_{\vartheta _{1}}$$-$ZPH$_{\vartheta _{3}}$ and MM$_{\vartheta _{1}}$$-$MM$_{\vartheta _{3}}$ outputs for random initial vectors generated by the MATLAB computing tool. The numerical results of Table 10 clearly show that the proposed numerical schemes are superior to ZPH for solving (5.8) and more difficult engineering problems. The number of iterations and CPU time significantly increase when compared to the numerical results obtained in Table 9. Table 10 shows that for any initial vector choice, the method MM converges to exact roots with greater efficiency than ZPH on iteration 10.

Example 5. ^[27,35,36] Polynomial of higher degree.

Consider

with exact roots:

The initial approximations of (5.9) have been taken as:

On the basis of efficiency achieved after sixth iterations, Table 11 unequivocally shows that the MM technique outperforms the ZPH method. Table 12 displays the global convergence behavior of the proposed numerical schemes on various randomly generated initial guesses (see Appendix Table 13).

Table 12 shows the numerical schemes ZPH$_{\vartheta _{1}}$$-$ZPH$_{\vartheta _{3}}$ and MM$_{\vartheta _{1}}$$-$MM$_{\vartheta _{3}}$ outputs for random initial vectors generated by the MATLAB computing tool. The numerical results of the Table 12 clearly show that the proposed numerical schemes are superior to ZPH for solving (5.9) and more difficult engineering problems. The number of iterations and CPU time significantly increase when compared to the numerical results obtained in Table 11. Table 12 shows that for any initial vector choice, the method MM converges to exact roots with greater efficiency than ZPH on iteration 35.

6.   Conclusions and observation

● In comparison to the well-known Weierstrass-type method ZPH, our newly developed methods is more efficient and stable.

● The results of the numerical test problems from Tables 3-12, computational efficiency from Figure 3, residual error graphs from Figure 4(a-e), and dynamical planes from Figures 1(a-h) and 2(a-h) show that the proposed family of iterative techniques MM outperforms ZPH in terms of efficiency and convergence behavior.

● Furthermore, the elapsed time of iterative technique MM from Table 1 is faster than ZPH.

● This paper proposes a family of Weierstrass-type derivative-free simultaneous techniques of order five. Tables 1–12 and Figures 1–4 show that our MM techniques outperform the Weierstrass-type method ZPH in terms of efficiency, CPU time, basins of attraction, and residual errors. Color brightness inspection in the basins reveals that MM requires fewer iteration steps than the simultaneous method ZPH. The results of the numerical test examples in terms of CPU-time and residual errors demonstrate the effectiveness and rapid convergence of our proposed derivative-free family of iterative algorithms, MM, in comparison to ZPH.

In summary, the comprehensive empirical results establish that these novel MM techniques outperform ZPH in terms of efficiency, CPU time, basins of attraction, and residual errors. Examination of the color brightness in the basins reveals MM requires fewer iteration steps than ZPH. Overall, the test examples clearly demonstrate the effectiveness, rapid convergence, and computational advantages of the proposed MM algorithms over ZPH.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The work is supported by Provincia autonoma di Bolzano/Alto Adigeâ euro Ripartizione Innovazione, Ricerca, Universitá e Musei (contract nr. 19/34). Bruno Carpentieri is a member of the Gruppo Nazionale per it Calcolo Scientifico (GNCS) of the Istituto Nazionale di Alta Matematia (INdAM) and this work was partially supported by INdAM-GNCS under Progetti di Ricerca 2022.

Conflict of interest

All authors declare no conflicts of interest in this paper.

Appendix