Optimal inequality factor
for Durand–Kerner’s and Tanabe’s methods

Octavian Cira\(^\ast \) Cristian Mihai Cira\(^\S \)

April 11, 2011

\(^\ast \)Department of Mathematics and Informatics, “Aurel Vlaicu" University, Bulevardul Revoluţiei, no. 75, Arad, România, e-mail: octavian.cira@uav.ro

\(^\S \)Auburn University, Samuel Ginn College of Engineering, Auburn, AL 36849, e-mail: cmc0031@auburn.edu

The convergence condition for the simultaneous inclusion methods is \(w^{(0)}{\lt}c(a,b,n)d^{(0)}\), where \(w^{(0)}\) is the maximum Weierstrass factor \(W^{(0)}_k\), \(k\in I_n\), and \(d^{(0)}\) is the minimum distance between \(z^{(0)}_1\), \(z^{(0)}_2\), …\(z^{(0)}_n\), the distinct approximations of the simple roots of the polynomial \(\zeta _1\), \(\zeta _2\), …\(\zeta _n\). The i-factor (inequality-factor) is the positive real function \(c(a,b,n)=\tfrac {1}{an+b}\). The article presents the optimum i-factor for the simultaneous inclusion methods Durand–Kerner and Tanabe.

MSC. 65H10

Keywords. Root-finding methods; Polynomial zeros; Simultaneous inclusion methods; Durand–Kerner’s method, Tanabe’s method, Convergence; Computational efficiency

1 Introduction

Let

\begin{equation} \label{PComplex} P(z)=z^n+a_{n-1}z^{n-1}+\cdots +a_1z+a_0,\ a_k\in \mathbb {C}~ ,\ k\in I^*_{n-1}~ , \end{equation}

be a polynomial, where \(I^*_{n-1}=\left\{ 0,1,\ldots ,n-1\right\} \) and let

\begin{equation} \label{EcuatiaAlgebrica} P(z)=0~ , \end{equation}

be its attached algebraic equation.

Abel’s impossibility theorem states that: “In general, polynomial equations higher than fourth degree are incapable of algebraic solution in terms of a finite number of additions, subtractions, multiplications, divisions, and root extractions”, [ 1 ] . This was also shown by Ruffini in 1813, [ 11 , pp. 59 ] .

Galois theorem states the same thing, namely that: “An algebraic equation is algebraically solvable necessary and sufficient its group is solvable. In order that an irreducible equation of prime degree be solvable by radicals, it is necessary and sufficient that all its roots be rational functions of two roots", [ 18 , 27 ] .

Modern softwares such as Maple, Mathematica, Mathcad or Matlab solve the algebraic equation of degree 2, 3 and 4 using symbolic computation and classical formulas for the second degree equation or Cardano’s formulas, [ 14 , pp. 282-284 ] and Ferrari–Cardano, [ 14 , pp. 284-287 ] for the \(3^{rd}\) and \(4^{th}\) degree equations. This methods always give the exact solutions but have the disadvantage that, sometimes, the solutions have a complicated representation.

Arbitrary-precision calculus in Mathcad prints the solution with up to 250 decimals, while Mathematica, [ 33 ] permits the display of any number of decimals for a result. Computing a result with \(n\) exact decimals is equivalent to finding the solution of the equation (2) with a numerical method with the precision \(10^{-n}\).

Therefore obtaining the solutions for an algebraic equation of degree 2, 3 and 4 is a solved problem. According to Abel’s impossibility theorem, in general for equation of degree greater than 4, we need to apply a numerical method to approximate the solutions.

Let us denote by \(\mathbf{d}_n=\left\{ n,n+1,\ldots \right\} \), \(n\in \mathbb {N}\) the polynomial degree greater or equal \(n\).

2 Simultaneous methods with corrections

Since \(k\in I_n=\left\{ 1,2,\ldots ,n\right\} \) we denote

\[ \sum \tfrac {W_j}{\widehat{z}_k-z_j}=\sum _{j=1}^n\tfrac {W_j}{\widehat{z}_k-z_j},\ \prod _{j\ne k}(z_k-z_j)=\prod _{j=1\atop {k\ne j}}^n (z_k-z_j), \]

\[ \max \left\vert W_k\right\vert =\max _{k\in I_n}\left\vert W_k\right\vert ,\ \min _{k{\lt}j}\left\vert z_k-z_j\right\vert =\min _{k,j\in I_n\atop k{\lt}j}\left\vert z_k-z_j\right\vert ,\ \]

Weierstrass correction factor is denoted by

\begin{equation} \label{FactorulWeierstrass} W_k=W(z_k)=\tfrac {P(z_k)}{\displaystyle \prod _{j\ne k}(z_k-z_j)}, \end{equation}

where \(z_k\) is the approximation for the simple zero \(\zeta _k\) of the polynomial (1), \(w\) is the absolute maximum value of the Weierstrass correction factors and \(d\) the minimum distance between two approximations \(z_1\), \(z_2\), …, \(z_n\).

\[ w=\max \left\vert W_k\right\vert ~ ,\ \ d=\min _{k{\lt}j}\left\vert z_k-z_j\right\vert . \]

We will also note by \(z\), \(w\), \(d\), \(W\) the current iteration \(z^{(m)}\), \(w^{(m)}\), \(d^{(m)}\), \(W^{(m)}\) and by \(\widehat{z}\), \(\widehat{w}\), \(\widehat{d}\), \(\widehat{W}\) the next iteration \(z^{(m+1)}\), \(w^{(m+1)}\), \(d^{(m+1)}\), \(W^{(m+1)}\).

We will consider a class \(C\) of simultaneous method with corrections, \(C(z)=P(z)/F(z)\), with \(F(z)\ne 0\) for any zero \(\zeta _k\) with \(k\in I_n\), of polynomial \(P\), and for any approximation \(z^{(m)}_k\) with \(k\in I_n\) and \(m=0,1,\ldots \) obtained by the iterative process. We will denote by

\begin{equation} \label{FormaCorectiilor} C^{(m)}_k=C_k(z^{(m)}_1,z^{(m)}_2,\ldots ,z^{(m)}_k), \end{equation}

the correction factor for the \(m^{th}\) iteration. The vast majority of the iterative methods that simultaneously approximate the simple zeros of an polynomial can be expressed as:

\begin{equation} \label{MetodaCorectii} z^{(m+1)}_k=z^{(m)}_k-C^{(m)}_k,\ \ k\in I_n\, \ m=0,1,\ldots , \end{equation}

where \(z^{(m)}_1\), \(z^{(m)}_2\), \(\ldots \), \(z^{(m)}_n\) are distinct approximations of the simple zeros \(\zeta _1\), \(\zeta _2\), …, \(\zeta _n\).

We try to find a convergence condition of the form \(w{\lt}c(n)d\), where \(c(n)\) is a real positive function that depends on \(n\) (the polynomial degree) asymptotic to the function \(\phi (n)=1/(n+2\sqrt{n-1})\) or \(\psi (n)=1/(2n)\). We consider the initial condition satisfied

\begin{equation} \label{ConditiaInitiala} w^{(0)} < c(n)d^{(0)}. \end{equation}

The function \(c(n)\) is called the i-factor (inequality factor) in [ 20 ] , [ 31 ] and many other works, and it depends on the degree \(n\) of the polynomial. For the choice of \(c(n)\), Petković and its collaborators propose that \(c(n)\) has the form:

\begin{equation} \label{I-FactorPetkovic} c(n)=c(a,b,n)=\tfrac {1}{an+b}~ \ \textnormal{with}\ a,b\in \mathbb R_+. \end{equation}

Theorem 1

Let \(\eta _k=z_k-W_k\in \mathbb {C}\backslash \left\{ z_1,z_2,\ldots ,z_n\right\} \) and set

\[ \gamma _k=\left\vert W_k\right\vert \cdot \max _{j\neq k}\left\vert z_j-\eta _k\right\vert ^{-1},\ \sigma _k=\sum _{j\neq k}\tfrac {\left\vert W_j\right\vert }{\left\vert z_j-\sigma _k\right\vert },\ \ k\in I_n. \]

If \(\sqrt{1+\gamma _k}{\gt}\sqrt{\gamma _k}+\sqrt{\sigma _k}\), then there is exactly one zero of \(P\) in the disk centered in \(\eta _k\) and of radius

\[ \left\vert W_k\right\vert \cdot \left(1-\tfrac {2(1-2\sigma _k-\gamma _k)}{1-\sigma _k-2\gamma _k+\sqrt{(1-\sigma _k-2\gamma _k)^2+ 4\sigma _k(1-2\sigma _k-\gamma _k)^2}}\right). \]

\begin{equation} \label{InegaliatiGammaSigma} \sqrt{1+\gamma _k}>\sqrt{\gamma _k}+\sqrt{\sigma _k}\ \textnormal{and}\ \gamma _k+2\sigma _k<1, \end{equation}

then there is exactly one zero of \(P\), in disk centered in \(\eta _k\) and of radius

\[ \left\vert W_k\right\vert \tfrac {\gamma _k+\sigma _k}{1-\sigma _k}. \]

Proof â–¼

See [ 12 ] and [ 5 , 8 , 13 ] .

Proof â–¼

Theorem 2

If the i-factor \(c(n)\) appearing in (6) is

\begin{equation} \label{FunctiaPhi} c(n)<\phi (n)=\tfrac {1}{n+2\sqrt{n-1}}\ \textnormal{and}\ c(n)<\psi (n)=\tfrac {1}{2n}, \end{equation}

then both inequalities (8) hold and the minimal radius of the inclusion disk given in Theorem 1 is not greater than \(\left\vert W_k\right\vert \).

Proof â–¼

See [ 31 , T 1.5. ] .

Proof â–¼

Theorem 3

Let \(c(a,b,n)=\tfrac {1}{an+b}\), \(a\ge 2\), \(b{\gt}(2-a)n\), and let us assume that \(w{\lt}c(a,b,n)d\), holds. Then for \(n\in \mathbf{d}_3\), the disks

\begin{align*} D_1=D\left(z_1-W_1;\tfrac {n}{(a-1)n+b}\left\vert W_1\right\vert \right),\ldots , D_n=D\left(z_n-W_n;\tfrac {n}{(a-1)n+b}\left\vert W_n\right\vert \right) \end{align*}

are mutually disjoint and each of then contain unique zero of \(P\).

Proof â–¼

See [ 31 , T 1.6 ] .

Proof â–¼

Corollary 4

Under the conditions of Theorem 3, each of disks \(D^*_k\) defined by

\begin{align} \label{DiscuriD*} D^*_k& =D\left(z_k-W_k;\tfrac {n}{(a-1)n+b}\left\vert W_k\right\vert \right)\\ & \nonumber =D\left(z_k;\tfrac {1}{1-nc(a,b,n)}\left\vert W_k\right\vert \right),\ k\in I_n \end{align}

contains exactly one zero of \(P\).

Proof â–¼

See [ 31 , Corollary 1.1 ] .

Proof â–¼

Let \(g:(0,1)\to \mathbb R\)

\begin{equation} \label{Functiag} g(t)= \begin{cases} 1+2t, & 0 < t\le \tfrac {1}{2}, \\ \tfrac {1}{1-t}, & \tfrac {1}{2} < t < 1. \end{cases} \end{equation}

Lemma 5

Let

\[ s_m(t)=t^m+\sum _{k=0}^mt^k~ ,\ t\in (0,1),\ m=1,2,\ldots ~ . \]

Then \(s_m(t){\lt}g(t)\).

Proof â–¼

Proof is elementary.

Proof â–¼

Theorem 6

Let the iterative method (5) have the iterative correction of the form (4) and let \(z^{(0)}_1\), \(z^{(0)}_2\), …\(z^{(0)}_n\) be distinct initial approximations of zeros for the polynomial \(P\). If there exists a real number \(\beta \) such that the following two inequalities:

\(\left\vert C^{(m+1)}_k\right\vert \le \beta \left\vert C^{(m)}_k\right\vert ~ ,\ \textnormal{for}\ m=0,1,\ldots \),
\(\left\vert z^{(0)}_k-z^{(0)}_j\right\vert {\gt}g(\beta )\left(\left\vert C^{(0)}_k\right\vert +\left\vert C^{(0)}_j\right\vert \right),\ \textnormal{for}\ k\ne j,\ k,j\in I_n\),

are valid, then the iterative method (5) is convergent.

Proof â–¼

See [ 31 , T 3.1 ] .

Proof â–¼

All the simultaneous inclusion methods convergence theorems try to determine the values of \(a\) and \(b\) such that the initial condition (6) assures the convergence for the method. We try to find the optimum values for \(a\) and \(b\), namely an optimum i-factor for every simultaneous method with corrections, [ 31 , pp. 80-81 ] , [ 30 ] .

Let us consider the nonlinear general problem with restrictions for simultaneous inclusion methods with the disks

\begin{equation} \label{DiscuriD} D_k=D\big(\widehat{z}_k;\left\vert C_k\right\vert \big),\ \ k\in I_n, \end{equation}

\begin{equation} \label{PNR} \left\{ \begin{array}{ll} \max c(a,b,n) & \textnormal{maximization},\\ a>1,\ b\ge 0,\ n\in \mathbf{d}_5 & \textnormal{defining \emph{c}},\\ c(a,b,n)\le \phi (n) & \textnormal{asymptotic condition to}\ \phi (n),\\ 0<\lambda (a,b,n)<\tfrac {1}{2} & \Rightarrow \left\vert C_k\right\vert \le \tfrac {\lambda (a,b,n)}{c(a,b,n)}\left\vert W_k\right\vert ,\\ 0<\delta (a,b,n)<1 & \Rightarrow \ \displaystyle \lim _{m\to \infty }\left\vert W_k^{(m)}\right\vert =0,\\ 0<\beta (a,b,n)<1 & \Rightarrow \ \displaystyle \lim _{m\to \infty }\left\vert C_k^{(m)}\right\vert =0,\\ \theta (a,b,n)\le 1 & \Rightarrow \ if\ w\le c(a,b,n)d\Rightarrow \widehat{w}\le c(a,b,n)\widehat{d},\\ \eta (a,b,n)<0 & \Rightarrow \ D_k\cap D_j=\emptyset , \end{array}\right. \end{equation}

for \(k,j\in I_n\). The function \(\phi (n)\) is given by (9). Functions \(\delta \), \(\beta \), \(\theta \) and \(\eta \) are defined by

\begin{equation} \label{FunctiilePNR} \left\{ \begin{array}{lcl} \lambda & =& \lambda (c,n)~ ,\\ \Pi (\lambda ,n) & =& \left(1+\tfrac {\lambda }{1-2\lambda }\right)^{n-1}~ , \\ \delta (\lambda ,c,n) & =& \mu _\delta (\lambda ,c,n)\cdot \Pi (\lambda ,n)~ , \\ \beta (\lambda ,c,n) & =& \mu _\beta (\lambda ,c,n)\cdot \delta (\lambda ,c,n)~ , \\ \mu _\theta (\lambda ) & =& \tfrac {1}{1-2\lambda }~ , \\ \theta (\lambda ,c,n) & =& \mu _\theta (\lambda )\cdot \beta (\lambda ,c,n)~ , \\ \eta (\lambda ,c,n) & =& 2\lambda -\tfrac {1}{g\big(\beta (\lambda ,c,n)\big)}~ . \end{array}\right. \end{equation}

The functions \(\lambda \), \(\mu _\delta \), \(\mu _\beta \), will be defined for every inclusion method from the lemmas and convergence theorems. The functions \(\lambda \) depend on \(c\) and \(n\) while \(c\) depends on \(a\) \(b\) and \(n\). The function \(g\) is given in (11).

Let us consider the nonlinear general problem with restrictions for simultaneous inclusion methods with the disks \(D^*_k\) given by (10):

\begin{equation} \label{PNRpentruD*} \left\{ \begin{array}{ll} \max c(a,b,n) & \textnormal{maximization},\\ a\ge 2,\ b\ge 0,\ n\in \mathbf{d}_5 & \textnormal{defining \emph{c}},\\ c(a,b,n)\le \psi (n) & \textnormal{asymptotic condition to}\ \psi (n),\\ 0<\lambda (a,b,n)<\tfrac {1}{2}, & \Rightarrow \left\vert C_k\right\vert \le \tfrac {\lambda (a,b,n)}{c(a,b,n)}\left\vert W_k\right\vert ,\\ 0<\delta (a,b,n)<1 & \Rightarrow \ \displaystyle \lim _{m\to \infty }\left\vert W_k^{(m)}\right\vert =0,\\ 0<\beta (a,b,n)<1 & \Rightarrow \ \displaystyle \lim _{m\to \infty }\left\vert C_k^{(m)}\right\vert =0,\\ \theta (a,b,n)\le 1 & \Rightarrow \ if\ w\le c(a,b,n)d\Rightarrow \widehat{w}\le c(a,b,n)\widehat{d}, \end{array}\right. \end{equation}

for \(k,j\in I_n\), where functions are defined by (16).

Proposition 7

If the functions \(f_1,f_2:I\subset \mathbb {R}\to \mathbb {R}_+\) are monotonically increasing (monotonically decreasing), then the function \(f:I\subset \mathbb {R}\to \mathbb {R}_+\), \(f(t)=f_1(t)\cdot f_2(t)\) is monotonically increasing (monotonically decreasing).

Proof â–¼

If the functions \(f_1,f_2\) are positive and increasing (strictly increasing), then \(f'_1(t)\), \(f'_2(t)\ge 0,\ ({\gt}0)\), and \(f'(t)=f'_1(t)\cdot f_2(t)+f_1(t)\cdot f'_2(t)\ge 0,\ ({\gt}0)\). Then it follows that the function \(f(t)\) is increasing (strictly increasing).

Proof â–¼

Remark 8

If the functions \(\mu _\beta (a,b,n)\) and \(\mu _\theta (a,b,n)\), are monotonically and \(\ge 1\), then we have \(\delta (a,b,n)\le \beta (a,b,n)\le \theta (a,b,n)\).
If the function \(\Pi =\Pi (a,b,n)\nearrow \) it is necessary for the functions \(\delta =\delta (a,b,n)\nearrow \), \(\beta =\beta (a,b,n)\nearrow \) and \(\theta =\theta (a,b,n)\nearrow \). These involve the followings:
- If \(\Pi \nearrow \), then is necessary that : \(\mu _\delta \nearrow \) for as \(\delta =\mu _\delta \Pi \nearrow \).
- If \(\delta \nearrow \), then is necessary that: \(\mu _\beta \nearrow \) for as \(\beta =\mu _\beta \delta \nearrow \) or if \(\mu _\beta \searrow \), then \(\mu _{\beta \delta }=\mu _\beta \mu _\delta \nearrow \) for as \(\beta =\mu _{\beta \delta }\Pi \nearrow \).
- If \(\beta \nearrow \), then is necessary that: \(\mu _\theta \nearrow \) for as \(\theta =\mu _\theta \beta \nearrow \) or if \(\mu _\theta \searrow \), then:
  - \(\mu _{\beta \delta }=\mu _\beta \mu _\delta \nearrow \) for as \(\theta =\mu _{\beta \delta }\delta \nearrow \) or if \(\mu _{\beta \delta }\searrow \), then:
  - \(\mu _{\theta \beta \delta }=\mu _\theta \mu _\beta \mu _\delta \nearrow \) for as \(\theta =\mu _{\theta \beta \delta }\Pi \nearrow \).

The following notations where used: \(\mu _\delta =\mu _\delta (a,b,n)\), \(\mu _\beta =\mu _\beta (a,b,n)\), \(\mu _\theta =\mu _\theta (a,b,n)\).

If \(\Pi =\Pi (a,b,n)\searrow \) then we have conditions similar to the case \(\nearrow \).â–¡

Lemma 9

The function \(\Pi (\lambda ,n)\) is strictly increasing if \(\lambda (n){\lt}\Lambda (n)\) and strictly decreasing if \(\lambda (n){\gt}\Lambda (n)\), where

\begin{equation} \label{SolutiaLambda} \Lambda (n)=\tfrac {1-\sqrt[n-1]{e}}{1-2\sqrt[n-1]{e}}~ . \end{equation}

Proof â–¼

If we derive the function \(\Pi (\lambda ,n)\) in respect to the variable \(n\) we obtain

\begin{equation*} \tfrac {\partial }{\partial n}\Pi (\lambda ,n) =\left[(n-1)\lambda ’(n)\! +\! \big(1-2\lambda (n)\big)\big(1\! -\! \lambda (n)\big) \ln \left(\tfrac {1\! -\! \lambda (n)}{1-2\lambda (n)}\right)\right] \times \left(\tfrac {1-\lambda (n)}{1-2\lambda (n)}\right)^n. \end{equation*}

Since \(\lambda (n)\in (0,\tfrac {1}{2})\), under the constraints of nonlinear problems with restrictions (15) and (17), we have that

\[ \left(\tfrac {1-\lambda (n)}{1-2\lambda (n)}\right)^n =\left(1+\tfrac {\lambda (n)}{1-2\lambda (n)}\right)^n{\gt}0. \]

The solution of differential equation

\[ \lambda '(n)=-\tfrac {1}{n-1}\big(1-2\lambda (n)\big)\big(1-\lambda (n)\big) \ln \left(\tfrac {1-\lambda (n)}{1-2\lambda (n)}\right), \]

is \(\Lambda (n)\), given by (18). Then:

if \(\lambda (n){\lt}\Lambda (n)\), for \(n\in \mathbf{d}_5\), then \(\Pi (\lambda ,n)\) is increasing,
if \(\lambda (n){\gt}\Lambda (n)\), for \(n\in \mathbf{d}_5\), then \(\Pi (\lambda ,n)\) is decreasing.

Proof â–¼

3 The Durand–Kerner’s method

Durand Kerner method, [ 3 , 6 ] , or Weierstrass-Docev method, [ 2 , 4 ] , [ 15 ] is defined by

\begin{equation} \label{MD-KsauMW-D} z^{(m+1)}_k=z^{(m)}_k-W^{(m)}_k\ \textnormal{for}\ k\in I_n\ \textnormal{and}\ m=0,1,\ldots ~ . \end{equation}

This method is part of the correction methods of form \(C_k=W_k=\tfrac {P(z_k)}{F_k(z)}\) where

\[ F_k(z)=F_k(z_1,z_2,\ldots ,z_n)=\prod _{j\ne k}(z_k-z_j)~ ,\ k\in I_n. \]

3.1 Durand–Kerner’s method convergence

Proof of Durand–Kerner’s method convergence requires the next lemma and theorem.

Lemma 10

Let \(z_1\), \(z_2\), …, \(z_n\) be distinct approximations and let initial conditions

\begin{equation*} w\le c(a,b,n)d, \end{equation*}

\begin{equation} \label{PsiDinMDK} 0 20

\begin{equation} \label{ThetaDinMDK} \theta (a,b,n)=\tfrac {\delta (a,b,n)}{1-2c(a,b,n)}\le 1, \end{equation}

where

\begin{equation} \label{DeltaDinMDK} \delta (a,b,n)=\tfrac {(n-1)c(a,b,n)}{1-c(a,b,n)} \left(1+\tfrac {c(a,b,n)}{1-2c(a,b,n)}\right)^{n-1}. \end{equation}

hold. Then:

\(\left\vert \widehat{W}_k\right\vert \le \delta (a,b,n)\left\vert W_k\right\vert \),
\(\widehat{w}\le c(a,b,n)\widehat{d}\).

Proof â–¼

See [ 31 , Lemma 3.3. ] .

Proof â–¼

Theorem 11

Let the i-factor

\begin{equation} \label{I-FactorPetkovicMDK} c_P(n)=\tfrac {1}{1.76325n+0.8689425}, \end{equation}

then the Durnad-Kerner method is convergent if the initial condition is satisfied, namely if

\begin{equation*} w^{(0)}{\lt}c_P(n)d^{(0)}. \end{equation*}

Proof â–¼

See [ 31 , T 3.3. ] .

Proof â–¼

Petković in [ 31 , pp. 80 ] stated that the i–factor is “almost optimum".

3.2 The analytically optimum i-factor for Durand–Kerner’s method with inclusion disks \(D_k\)

These inclusion disks are \(D_k=D(\widehat{z}_k,\left\vert C_k\right\vert )\), where for Durand-Kerner method the corrections \(C_k\) are Weierstrass factors \(W_k\).

The solution for the Lambert equation, \(x {\rm e}^x=1\), [ 32 , LambertW-Function ] , [ 19 ] , is denoted by \(W(1)\). The constant \(1/W(1)\), is called omega constant [ 32 , OmegaConstant ] , [ 32 , A030178 ] prints 59 decimals for the constant \(W(1)\),

\[ W(1)\approx 0.56714329040978387299996866221\ldots . \]

Next \(1/W(1)\) will be denoted by \(\omega \),

\[ \omega \approx 1.76322283435189671022520177695\ldots . \]

Let the constant

\begin{equation} \label{ConstantaTau} \tau \approx 0.88049674007368891\ldots , \end{equation}

be the real solution of

\begin{equation} \label{EcuatiaPentruTau} b^3+(11\omega -3)b^2+(35\omega ^2-30\omega +2)b+25\omega ^3-75\omega ^2+18\omega =0. \end{equation}

For Durand–Kerner’s method we have the function \(c(a,b,n)\), given by (7), and the functions:

\begin{equation} \label{FunctiileMDK} \left\{ \begin{array}{l} \lambda (c)=c,\\ \mu _\delta (\lambda ,n)=\tfrac {(n-1)\lambda }{1-\lambda },\\ \mu _\beta =1, \end{array}\right. \end{equation}

resulting from Lemma 10 relations (21) and (22), and the functions \(\delta \), \(\beta \), \(\mu _\theta \), \(\theta \) and \(\eta \) are defined in (16).

Proposition 12

If \(b{\gt}h(a,5)\), then the function \(\lambda (a,b,n)=c(a,b,n){\lt}\Lambda (n)\), where

\[ h(a,n)=\tfrac {1}{\Lambda (n)}-an \]

and \(\Lambda \) is given by (18).

Proof â–¼

The function

\begin{equation} \label{Functiah(a,n)MDK} h(a,n)=\tfrac {1-\sqrt[n-1]{e}}{1-2\sqrt[n-1]{e}}-an, \end{equation}

is decreasing, because

\[ h'(a,n)=\tfrac {\partial }{\partial n}h(a,n) =\tfrac {1}{\left(2(n-1)\sinh \left(\tfrac {1}{2(n-1)}\right)\right)^2}-a{\lt}0, \]

for \(a{\gt}1\) and \(n\in \mathbf{d}_5\). Then, if \(b{\gt}h(a,5)\) resulting that \(\lambda (a,b,n){\lt}\Lambda (n)\).

Proof â–¼

Lemma 13

Let the i-factor

\begin{equation} \label{I-FactorOptimMDK} c(n)=c(\omega ,\tau ,n)=\tfrac {1}{\omega n+\tau }, \end{equation}

then:

\(0{\lt}\lambda (\omega ,\tau ,n){\lt}0.10313\),
\(0.707{\lt}\delta (\omega ,\tau ,n){\lt}1\),
\(0.944{\lt}\theta (\omega ,\tau ,n){\lt}1\)
\(\eta (\omega ,\tau ,n){\lt}0\),

for \(n\in \mathbf{d}_5\).

Proof â–¼

The derivative function \(\lambda (a,b,n)=c(a,b,n)\) with respect to \(n\) is

\[ -\tfrac {a}{(an+b)^2}{\lt}0, \]

which implies that the functions \(c\) and \(\lambda \) are strictly decreasing. For

\[ \lambda (\omega ,\tau ,n)=c(\omega ,\tau ,n) \]

we have

\[ \lim _{n\to \infty }\lambda (\omega ,\tau ,n)=0\ \ \textnormal{and}\ \ \lambda (5)=\tfrac {1}{5\omega +\tau }\approx 0.10312881573707708\ldots {\lt}\tfrac {1}{2}, \]

then we have (1) of lemma.

If the function \(\lambda (a,b,n)\to 0\), then the function \(\Pi (\lambda (a,b,n),n)\) converges and we have

\[ \lim _{n\to \infty }\Pi \big(\lambda (a,b,n),n\big)= \lim _{n\to \infty }\Pi (a,b,n)={\rm e}^{\tfrac {1}{a}}, \]

for \(a{\gt}1\). In these conditions we have that

\[ \lim _{n\to \infty }\delta (a,b,n)=\tfrac {1}{a}{\rm e}^{\tfrac {1}{a}}\ \ \textnormal{and}\ \lim _{n\to \infty }\theta (a,b,n)=\tfrac {1}{a}{\rm e}^{\tfrac {1}{a}}. \]

Since \(\mu _\theta (a,b,n)=(an+b)/(an+b-2){\gt}1\) it follows that \(\theta (a,b,n){\gt}\beta (a,b,n)=\delta (a,b,n)\). Imposing the inequality \(\theta (a,b,n)\le 1\) it follows that the equation

\[ \tfrac {{\rm e}^{\tfrac {1}{a}}}{a}=1. \]

This equation is a Lambert type equation, [ 19 ] , whose solution is the constant \(\omega \).

The function \(\mu _\delta (\omega ,b,n)=(n-1)/(an+b-1)\) is increasing, because

\[ \tfrac {\partial }{\partial n}\mu _\delta (\omega ,b,n)=\tfrac {\omega +b-1}{(\omega n+b-1)^2}{\gt}0, \]

for \(b{\gt}1-\omega \approx -0.7632228\ldots \) and \(n\in \mathbf{d}_5\).

Under Lemma 9 and Proposition 12, for function \(\Pi (\omega ,b,n)\) to be increasing it is necessary that \(b{\gt}h(\omega ,5)\approx -3.295\ldots \), where \(h\) is given by (27). Then, it follows that \(\delta (\omega ,b,n)\nearrow 1\), for \(b\ge 0\) when \(n\to \infty \).

The derivative for the function \(\mu _\theta (\omega ,b,n)\) is

\[ \tfrac {\partial }{\partial n}\mu _\theta (\omega ,b,n)=\tfrac {-2\omega }{(\omega n+b-2)^2}{\lt}0. \]

Therefore we can not say that the function \(\theta (\omega ,b,n)=\mu _\theta (\omega ,b,n)\delta (\omega ,b,n)\) is increasing on Proposition 7. But the function \(\theta (a,b,n)\) can be expressed as

\begin{equation} \label{Theta} \theta (a,b,n)=\mu _\theta (a,b,n)\delta (a,b,n)=\mu _\theta (a,b,n)\mu _\delta (a,b,n)\Pi (a,b,n). \end{equation}

Using the notation \(\mu _{\theta \delta }(a,b,n)=\mu _\theta (a,b,n)\mu _\delta (a,b,n)\), it follows that

\begin{equation} \label{Mu} \mu _{\theta \delta }(a,b,n)=(n-1)\tfrac {an+b}{(an+b-1)(an+b-2)} \end{equation}

and

\begin{equation} \label{MuPrim} \mu '_{\theta \delta }(a,b,n)=\tfrac {\partial }{\partial n}\mu _{\theta \delta }(a,b,n) =\tfrac {P_3(a,b,n)}{(an+b-1)^2(an+b-2)^2}. \end{equation}

Thus we have the polynomial

\begin{equation} \label{PolinomulMuPrim} P_3(a,b,n)=b^3+\alpha _2(a,n)b^2+\alpha _1(a,n)b+\alpha _0(a,n), \end{equation}

with coefficients

\begin{equation} \label{CoefPolinomMuPrim} \begin{array}{lcl} \alpha _2(a,n) & =& (2n+1)a-3, \\ \alpha _1(a,n) & =& n(n+2)a^2-6na+2, \\ \alpha _0(a,n) & =& a(n^2a^2-3n^2a+4n-2) , \end{array} \end{equation}

where

\begin{eqnarray*} \alpha _2(a,n) & \ge 0& for\ a\ge \tfrac {3}{11}\ \textnormal{and}\ n\in \mathbf{d}_5, \\ \alpha _1(a,n) & \ge 0& for\ a\notin \left(\tfrac {3}{7}-\sqrt{\tfrac {31}{7}}, \tfrac {3}{7}+\sqrt{\tfrac {31}{7}}\right)\approx (0.073,0.748)\ \textnormal{and}\ n\in \mathbf{d}_5,\\ \alpha _0(a,n) & \le 0& for\ a\in \left(\tfrac {3}{2}-\tfrac {3\sqrt{17}}{10}, \tfrac {3}{2}+\tfrac {3\sqrt{17}}{10}\right)\approx (0.263,2.737)\ \textnormal{and}\ n\in \mathbf{d}_5. \end{eqnarray*}

Then, according to Cauchy’s theorem, [ 29 , pp. 3 ] , the equation \(P_3(a,b,n)=0\) has a unique positive real root, in relation to \(b\). The greatest root results for \(n=5\). For \(a=\omega \) and \(n=5\) we have the equation (25). For \(a=\omega \) and \(n=6\) we have the solution \(\approx 0.92989\ldots \), for \(a=\omega \) and \(n=7\) we have the solution \(\approx 0.96706\ldots \) and so on.

Then it follows that \(\mu _{\theta \delta }(\omega ,b,n)\) is strictly increasing if \(\mu '_{\theta \delta }(\omega ,b,5){\gt}0\). We have this inequality if \(b{\gt}\tau \approx 0.8804967400681223\ldots \) is true. The function \(\theta (\omega ,b,n)\) is the product of two positive and increasing functions, \(\Pi (\omega ,b,n)\) and \(\mu _{\theta \delta }(\omega ,b,n)\). If \(b{\gt}\tau \), then, according to Proposition 7, the function \(\theta (\omega ,b,n)\) is strictly increasing.

We compute the function values \(\delta \) and \(\theta \) for \(n=5\),

\begin{eqnarray*} \delta (\omega ,\tau ,5) & \approx & 0.7497422461897223\ldots , \\ \theta (\omega ,\tau ,5) & \approx & 0.9445662420442020\ldots . \end{eqnarray*}

Because functions \(\delta \) and \(\theta \) are strictly increasing resulting that claims the second and the third from the lemma are true.

For Durand–Kerner’s method we have \(\delta (a,b,n)=\beta (a,b,n)\), when taking into account (2) of the lemma and the definition of function g, given by (11), we have

\[ \eta (\omega ,\tau ,n)=2\lambda (\omega ,\tau ,n)+\beta (\omega ,\tau ,n)-1 =2\lambda (\omega ,\tau ,n)+\delta (\omega ,\tau ,n)-1. \]

To demonstrate that \(\eta (\omega ,\tau ,n){\lt}0\), for \(n\in \mathbf{d}_5\), but this relation is equivalent to \(\theta (\omega ,\tau ,n){\lt}1\), for \(n\in \mathbf{d}_5\), relation that has already been demonstrated.

Proof â–¼

Theorem 14

The function \(c(n)\) given by (28) is the optimum i-factor for Durand–Kerner’s method with inclusion disks \(D_k\), given by (14).

Proof â–¼

Since \(\omega \) was computed from the limit condition

\[ \tfrac {1}{\omega }{\rm e}^{\tfrac {1}{\omega }}=1, \]

and \(\tau \) from the extreme condition, namely \(\tau \) is the real solution for the equation, it implies that \(\omega \) and \(\tau \) are the best values for the given conditions. We can then state that \(c(n)\) given by (28) is the optimum i-factor for Durand–Kerner’s method.

Proof â–¼

Theorem 15

If the initial distinct approximations \(z^{(0)}_1,z^{(0)}_2,\ldots ,z^{(0)}_n\) satisfy the initial condition

\begin{equation} \label{CondInitialaMDK} w^{(0)} 34

for \(n\in \mathbf{d}_5\), where \(c\) given by (28), then the Durand-Kerner method with inclusion disks \(D_k\), given by (14), is convergent.

Proof â–¼

The conclusions in the Lemma 13 assure that the conclusions of Lemma 10 are satisfied, which, in turn assure the convergence of the Durand-Kerner method if the initial condition is verified (34).

Proof â–¼

Remark 16

If \(n\in \mathbf{d}_3\), case considered by Petković et al., \(a=\omega \) and \(b=\tau _3\), where \(\tau _3\) is the solution for the equation \(\mu '_{\theta \delta }(\omega ,b,3)=0\), and the function \(\mu '_{\theta \delta }\) is given by (31). So we have

\[ b^3+(7\omega -3)b^2+(15\omega ^2-18\omega +2)b+9\omega ^3-27\omega ^2+10\omega =0, \]

and the optimum i-factor

\[ c(n)=\tfrac {1}{\omega n+\tau _3},\ \ \textnormal{with}\ \ \tau _3=0.7071447767242046\ldots , \]

for \(n\in \mathbf{d}_3\).â–¡

3.3 The analytically optimum i-factor for Durand–Kerner’s method
with inclusion disks \(D^*_k\)

The inclusion disks \(D^*_k\) are given by (10).

Lemma 17

Let the i-factor be

\begin{equation} \label{I-FactorOptimMDKD*} c(n)=c(2,\tau _*,n)=\tfrac {1}{2n+\tau _*},\ \ \tau _*\approx 0.67211423631036255\ldots , \end{equation}

where \(\tau _*\) is a root of equation

\begin{equation} \label{EcuatiaPentruTau*} b^3+19b^2+82b-64=0, \end{equation}

then:

\(0{\lt}\lambda (2,\tau _*,n){\lt}0.094\),
\(0.639{\lt}\delta (2,\tau _*,n)\le \tfrac {\sqrt{e}}{2}\approx 0.824\),
\(0.787{\lt}\theta (2,\tau _*,n)\le \tfrac {\sqrt{e}}{2}\approx 0.824\),

for \(n\in \mathbf{d}_5\).

Proof â–¼

According to corollary 4 if we consider the inclusion disks \(D^*_k\) given by (10), then \(a\ge 2\) and \(b{\gt}(2-a)n\). Let \(a=2\), the lowest value of \(a\), then it follows that \(b{\gt}0\).

The function \(\lambda (2,b,n)\searrow 0\) when \(n\to \infty \), because the derivative function \(\lambda \) in relation to the variable \(n\) is \(-2/(2n+b)^2{\lt}0\). Then, \(\Pi (2,b,n)\to \sqrt{{\rm e}}\) when \(n\to \infty \). According to Proposition 7, the function \(\delta (2,b,n)\) is increasing if the functions \(\mu _\delta (2,b,n)\) and \(\Pi (2,b,n)\) are increasing. The derivative of the function \(\mu _\delta (2,b,n)\) is

\[ \tfrac {\partial }{\partial n}\mu _\delta (2,b,n)=\tfrac {b+1}{(b+2n-1)^2}~ , \]

and is positive if \(b{\gt}-1\). The function \(\Pi (2,b,n)\) is increasing if \(b{\gt}h(2,5)\approx -4.479\), where \(h\) is given by (27). Therefore it follows that \(\delta (2,b,n)\) is increasing for \(b\ge 0\) and \(n\in \mathbf{d}_5\). In these circumstances we have

\[ \lim _{n\to \infty }\delta (2,b,n)=\lim _{n\to \infty }\theta (2,b,n)=\tfrac {\sqrt{{\rm e}}}{2}\approx 0.824{\lt}1. \]

The derivative of the function \(\mu _\theta (2,b,n)\) is

\[ \tfrac {\partial }{\partial n}\mu _\theta (2,b,n)=\tfrac {-4}{(2n+b-2)^2}{\lt}0. \]

We can not say that the function \(\theta (2,b,n)=\mu _\theta (2,b,n)\delta (2,b,n)\) is increasing in the Proposition 7. But the function \(\theta (a,b,n)\) can be expressed as (29). We denote by \(\mu _{\theta \delta }(a,b,n)=\mu _\theta (a,b,n)\mu _\delta (a,b,n)\) and consider the polynomial (32) with coefficients (33). If \(0.748{\lt}a{\lt}2.737\), then, according to Cauchy’s theorem, [ 29 , pp. 3 ] , the equation \(P_3(a,b,n)=0\), in relation to the variable \(b\), has a unique real positive solution. The largest positive real root results for \(n=5\). For \(a=2\) and \(n=5\) resulting the equation (36), with real positive solution \(\tau _*\approx 0.67211423631036255\ldots \). For \(a=2\) and \(n=6\) we have the solution \(0.71912\ldots \), for \(a=2\) and \(n=7\) we have the solution \(0.75419\ldots \) and so on.

Then it follows that the function \(\mu _{\theta \delta }(2,b,n)\) is increasing if \(b{\gt}\tau _*\). The function \(\theta (2,b,n)\) is the product of two positive and increasing functions, namely \(\Pi (2,b,n)\) and \(\mu _{\theta \delta }(2,b,n)\), if \(b{\gt}\tau _*\), then, according to Proposition 7, the function \(\theta (2,b,n)\) is increasing.

Monotonous function values \(\theta \), \(\delta \) and \(\lambda \) for \(n=5\) are:

\begin{eqnarray*} \theta (2,\tau _*,5) & \approx & 0.787498541207337\ldots , \\ \delta (2,\tau _*,5) & \approx & 0.6399179355710173\ldots , \\ \lambda (2,\tau _*,5) & \approx & 0.09370214540972971. \end{eqnarray*}

Proof â–¼

Theorem 18

The function \(c(n)\) given by (35) is the optimum i-factor for Durand–Kerner’s method with the inclusion disks \(D^*_k\) given by (10).

Proof â–¼

Since \(a=2\) and \(b=\tau _*\) are the best values under the circumstances, then we say that \(c(n)\) given by (35) is optimum i-factor for Durand–Kerner’s method with the inclusion disks \(D^*_k\), given by (10).

Proof â–¼

Theorem 19

If the initial distinct approximations \(z^{(0)}_1,z^{(0)}_2,\ldots ,z^{(0)}_n\) satisfy the initial condition

\begin{equation} \label{CondInitialaMDKD*} w^{(0)} 37

for \(n\in \mathbf{d}_5\), where \(c\) is given by (35), then Durand–Kerner’s method with inclusion disks \(D^*_k\), given by (10), is convergent.

Proof â–¼

The conclusions in the Lemma 17 assure that the conclusions of Lemma 10 are satisfied, which, in turn assure the convergence of the Durand-Kerner method if the initial condition is verified (37).

Proof â–¼

4 The Tanabe’s method

The Tanabe’s method, [ 10 ] , is given by the formula:

\begin{equation} \label{MetodaTanabe} z^{(m+1)}_k=z^{(m)}_k-W^{(m)}_k\left(1-\sum _{j\ne k}\tfrac {W^{(m)}_j}{z^{(m)}_k-z^{(m)}_j}\right),\ k\in I_n\ m=0,1,\ldots . \end{equation}

If we denote by

\[ t_k=\sum _{j\ne k}\tfrac {W_j}{z_k-z_j},\ k\in I_n, \]

then for reasonably small values of \(t_k\), we can state that \(1/(1+t_k)=1-t_k+O(t_k^2)\). It is well known that Tanabe’s method results form Börsch-Supan’s method based on this observation. Tanabe’s method is one with corrections, where

\[ C_k(z_1,z_2,\ldots ,z_n)=\tfrac {P(z_k)}{F_k(z_1,z_2,\ldots ,z_n)},\ k\in I_n, \]

but

\[ F_k(z_1,z_2,\ldots ,z_n) =\tfrac {1}{1-\displaystyle \sum _{j\ne k}\tfrac {W^{(m)}_k}{z^{(m)}_k-z^{(m)}_j}} \cdot \prod _{j\ne k}(z_k-z_j). \]

4.1 Tanabe’s method convergence

In order to prove the convergence we state the following theorem and 4 lemmas.

Lemma 20

Let \(z_1,z_2,\ldots ,z_n\in \mathbb {C}\) be distinct numbers and the i-factor \(c(a,b,n)\) that satisfies the conditions

\begin{equation} \label{PsiDinMT} 0 39

and

\begin{equation} \label{CondInitialaMT} w\le c(a,b,n)d. \end{equation}

Then:

\begin{eqnarray*} (1) & & \tfrac {\lambda (a,b,n)}{c(a,b,n)}\ge \left\vert 1-\sum _{j\ne k}\tfrac {W_j}{z_k-z_j}\right\vert \ge 2-\tfrac {\lambda (a,b,n)}{c(a,b,n)},\\ (2) & & \left\vert \widehat{z}_k-z_k\right\vert \le \tfrac {\lambda (a,b,n)}{c(a,b,n)}\left\vert W_k\right\vert \le \lambda (a,b,n)d,\\ (3) & & \left\vert \widehat{z}_k-z_j\right\vert \ge \big(1-\lambda (a,b,n)\big)d,\\ (4) & & \left\vert \widehat{z}_k-\widehat{z}_j\right\vert \ge \big(1-2\lambda (a,b,n)\big)d,\\ (5) & & \left\vert 1+\sum \tfrac {W_j}{\widehat{z}_k-z_j}\right\vert \le \tfrac {(n-1)\big(\lambda (a,b,n)+ (n-1)c(a,b,n)\big)c(a,b,n)^2}{\big(2c(a,b,n)-\lambda (a,b,n)\big)\big(1-\lambda (a,b,n)\big)},\\ (6) & & \left\vert \prod _{j\ne k}\tfrac {\widehat{z}_k-z_j}{\widehat{z}_k-\widehat{z}_j}\right\vert \le \left(1+\tfrac {\lambda (a,b,n)}{1-2\lambda (a,b,n)}\right)^{n-1},\\ \end{eqnarray*}

where

\begin{equation} \label{LambdaDinMT} \lambda (a,b,n)=\big(1+(n-1)c(a,b,n)\big)c(a,b,n). \end{equation}

Proof â–¼

See [ 31 , Lemma 3.8. ] .

Proof â–¼

Lemma 21

Let \(z_1\), \(z_2\), …, \(z_n\) be distinct approximations for the roots \(\zeta _1\), \(\zeta _2\), …, \( \zeta _n\) of the polynomial \(P\) and let us assume the conditions (39) and (40) from Lemma 20 to be true. Let us also consider true the following inequality

\begin{equation} \label{ThetaDinMT} \theta (a,b,n)=\tfrac {\delta (a,b,n)}{1-2\lambda (a,b,n)}\le 1, \end{equation}

where

\begin{multline} \label{DeltaDinMT} \delta (a,b,n)=\tfrac {(n-1)c(a,b,n)\lambda (a,b,n)\big(\lambda (a,b,n)+(n-1)c(a,b,n)\big)} {\big(2c(a,b,n)-\lambda (a,b,n)\big)\big(1-\lambda (a,b,n)\big)} \times \left(1+\tfrac {\lambda (a,b,n)}{1-2\lambda (a,b,n)}\right)^{n-1}. \end{multline}

Then:

\begin{eqnarray*} (1) & & \left\vert \widehat{W}_k\right\vert \le \delta (a,b,n)\left\vert W_k\right\vert ,\ k\in I_n \\ (2) & & \widehat{w}\le c(a,b,n)w. \end{eqnarray*}

Proof â–¼

See [ 31 , Lemma 3.9. ] .

Proof â–¼

Lemma 22

Let us consider all the conditions form Lemma 20 and 21 and the next two ones to be true

\begin{equation} \label{BetaDinMT} \beta (a,b,n)=\tfrac {\lambda (a,b,n)\delta (a,b,n)}{2c(a,b,n)-\lambda (a,b,n)}<1 \end{equation}

and

\begin{equation} \label{EtaDinMT} \eta (a,b,n)=2\lambda (a,b,n)-\tfrac {1}{g\big(\beta (a,b,n)\big)}<0~ . \end{equation}

If the initial distinct approximations \(z^{(0)}_1,z^{(0)}_2,\ldots ,z^{(0)}_n\) satisfy the initial condition

\begin{equation} \label{CIMT} w^{(0)}\le c(a,b,n)d^{(0)}, \end{equation}

then Tanabe’s method given by (38) is convergent.

Proof â–¼

See [ 31 , T 3.6. ] .

Proof â–¼

Lemma 23

The i-factor function

\begin{equation} \label{I-FactorMTPetkovic} c_P(n)=\tfrac {1}{3n}. \end{equation}

satisfies then conditions (39), (42), (44) and (45).

Proof â–¼

See [ 31 , Lemma 3.10. ] .

Proof â–¼

Theorem 24

The Tanabe’s method, given by (38), is convergent if the initial condition (40) is true for the initial distinct approximations \(z^{(0)}_1\), \(z^{(0)}_2\), …\(z^{(0)}_n\), where the i-factor is given by (47).

4.2 The optimum analytic i-factor

For Tanabe’s method we have the function \(c(a,b,n)\), given by (7) and the functions:

\begin{equation} \label{FunctiileMT} \left\{ \begin{array}{lcl} \lambda (c,n) & =& c+(n-1)c^2 \\ \mu _\delta (\lambda ,c,n) & =& \tfrac {(n-1)^2c^2\lambda +(n-1)c\lambda ^2}{(2c-\lambda )(1-\lambda )}, \\ \mu _\beta (\lambda ,c) & =& \tfrac {\lambda }{2c-\lambda }, \end{array}\right. \end{equation}

resulting from the Lemmas 20, 21 and 22, respectively from the relations (41), (43) and (44) and the functions \(\delta \), \(\beta \), \(\mu _\theta \) and \(\theta \) defined in (16). Let the constant \(\omega _{_\textrm {T}}\) be the solution for the Lambert type equation, [ 19 ] ,

\begin{equation} \label{EcuatiaLambertOmegaT} \tfrac {x+1}{x^2}\exp \left(\tfrac {x+1}{x^2}\right) =\tfrac {(x-1)^2}{x+1}~ . \end{equation}

The approximative value \(\omega _{_\textrm {T}}\) is \(2.7480500253477966212\ldots \).

Proposition 25

If \(b{\gt}h_\emph {T}(a,5)\), then \(\lambda (a,b,n){\lt}\Lambda (n)\), where \(\lambda (a,b,n)=c(a,b,n)+(n-1)c(a,b,n)^2\),

\begin{equation} \label{Functiah(a,n)MT} h_\emph {T}(a,n)=\tfrac {-2(a-1)\sqrt[n-1]{e}+2an-1}{2(\sqrt[n-1]{e}-1)} +\tfrac {\sqrt{4(2n-1)\sqrt[n-1]{e^2}-4(3n-2)\sqrt[n-1]{e}+4n-3}}{2(\sqrt[n-1]{e}-1)} \end{equation}

and \(\Lambda \) is given by (18).

Proof â–¼

The equation \(\lambda (a,b,n)=\Lambda (n)\) has solutions:

\[ \tfrac {-2(a-1)\sqrt[n-1]{e}+2an-1}{2(\sqrt[n-1]{e}-1)} \pm \tfrac {\sqrt{4(2n-1)\sqrt[n-1]{e^2}-4(3n-2)\sqrt[n-1]{e}+4n-3}}{2(\sqrt[n-1]{e}-1)}. \]

The function \(h_\textrm {T}(a,n)\), given by (50), for \(a{\gt}1\) and \(n\in \mathbf{d}_5\). Then, if \(b{\gt}h_\textrm {T}(a,5)\) resulting that \(\lambda (a,b,n){\lt}\Lambda (n)\).

Proof â–¼

Lemma 26

If \(a=\omega _\emph {T}\) and \(b=0\), then for the i-factor \(c(n)=c(\omega _\emph {T},0,n)\) the following inequalities must be true for \(n\in \mathbf{d}_5\),

\(0{\lt}c(\omega _\emph {T},0,n){\lt}\psi (n)\),
\(0{\lt}\lambda (\omega _\emph {T},0,n){\lt}0.094\),
\(0.349{\lt}\delta (\omega _\emph {T},0,n){\lt}0.4664\),
\(0.636{\lt}\beta (\omega _\emph {T},0,n){\lt}1\),
\(0.783{\lt}\theta (\omega _\emph {T},0,n){\lt}1\),

where \(\psi (n)\) is given by (39).

Proof â–¼

The function \(c(\omega _{_\textrm {T}},0,n)\) is clearly greater than \(0\) and verifies the inequality \(c(\omega _{_\textrm {T}},0,n){\lt}\psi (n)\), for \(n\in \mathbf{d}_5\).

For the function

\[ \lambda (a,b,n)=\lambda \big(c(a,b,n),n\big)=\tfrac {1}{an+b}+\tfrac {n-1}{(an+b)^2}, \]

we have

\[ \lim _{n\to \infty }\lambda (a,b,n)=0,\ \ \textnormal{for}\ \ a{\gt}0. \]

The function \(\Pi (a,b,n)\) is

\[ \Pi (a,b,n)=\left(1+\tfrac {\lambda (a,b,n)}{1-2\lambda (a,b,n)}\right)^{n-1}. \]

Since the limit the function \(\lambda \) is \(0\), then we move to limit the function \(\Pi (a,b,n)\) and we have

\[ L_\Pi (a)=\lim _{n\to \infty }\Pi (a,b,n)={\rm e}^{\tfrac {a+1}{a^2}}. \]

The function \(\mu _\delta (a,b,n)\) is

\begin{equation} \label{FunctiaMuDelta} \mu _\delta (a,b,n) =\tfrac {(n-1)[(a+1)n+b-1][an^2+(b+1)n-1]}{(an+b)[(a-1)n+b+1][a^2n^2+(2ab-a-1)n+b^2-b+1]}, \end{equation}

and its limit is

\[ L_{\mu _\delta }(a)=\lim _{n\to \infty }\mu _\delta (a,b,n)=\tfrac {a+1}{a^2(a-1)}. \]

Then the function \(\delta (a,b,n)=\mu _\delta (a,b,n)\Pi (a,b,n)\), has the limit

\[ L_\delta (a)=\lim _{n\to \infty }\delta (a,b,n)=\tfrac {a+1}{a^2(a-1)}{\rm e}^{\tfrac {a+1}{a^2}}. \]

The function \(\mu _\beta (a,b,n)\) is

\[ \mu _\beta (a,b,n)=\tfrac {(a+1)n+b-1}{(a-1)n+b+1}, \]

and its limit is

\[ L_{\mu _\beta }(a)=\lim _{n\to \infty }\mu _\beta (a,b,n)=\tfrac {a+1}{a-1}. \]

Then the function \(\beta (a,b,n)=\mu _\beta (a,b,n)\delta (a,b,n)\), has the limit

\[ L_\beta (a)=\lim _{n\to \infty }\beta (a,b,n)=\tfrac {(a+1)^2}{a^2(a-1)^2}{\rm e}^{\tfrac {a+1}{a^2}}. \]

The function \(\mu _\theta (a,b,n)\) is

\[ \mu _\theta (a,b,n)=\tfrac {(an+b)^2}{a^2n^2-2(a+1-ab)n+b^2-2b+2}, \]

and its limit is \(1\) when \(n\to \infty \). Then it follows that the function

\[ \theta (a,b,n)=\mu _\theta (a,b,n) \beta (a,b,n), \]

has the limit

\[ L_\theta (a)=\tfrac {(a+1)^2}{a^2(a-1)^2}{\rm e}^{\tfrac {a+1}{a^2}}. \]

Impose conditions \(L_\delta (a)\le 1\) and \(L_\beta (a)=L_\theta (a)\le 1\). Lambert type equations, \(L_\delta (a)=1\) has solution \(\approx 2.236180389652745005\) and \(L_\theta (a)=1\) has solution \(\omega _{_\textrm {T}}\approx 2.7480500253477966212\ldots \). Let \(a=\omega _{_\textrm {T}}\), sine for any \(a{\gt}\omega _{_\textrm {T}}\) we have \(L_\delta (a){\lt}1\).

To prove that the function \(\Pi (\omega _{_\textrm {T}},b,n)\) is monotonically increasing to its limit. According to Lemma 9 and Proposition 25, the function \(\Pi (\omega _{_\textrm {T}},b,n)\) is increasing for \(b{\gt}h_\textrm {T}(\omega _{_\textrm {T}},5)\approx -5.529\ldots \). It follows that for \(b\ge 0\) the function \(\Pi (\omega _{_\textrm {T}},0,n)\) is monotonically increasing to its limit. Let further \(b=0\).

To prove that the function \(\delta (\omega _{_\textrm {T}},0,n)\) is monotonically increasing to its limit, we derivative the function \(\mu _\delta (\omega _{_\textrm {T}},0,n)\), where \(\mu _\delta (a,b,n)\) is given by (51), so

\[ \mu '_\delta (\omega _{_\textrm {T}},0,n) =\tfrac {\alpha _6n^6 +\alpha _5n^5+\alpha _4n^4+\alpha _3n^3+\alpha _2n^2+\alpha _1n+\alpha _0} {\omega _{_\textrm {T}}^2n^2[(\omega _{_\textrm {T}}-1)n+1]^2[\omega _{_\textrm {T}}^2n^2-(\omega _{_\textrm {T}}+1)n+1]^2}, \]

where

\begin{eqnarray*} \alpha _6 & =& \omega _{_\textrm {T}}^5-2\omega _{_\textrm {T}}^3+2\omega _{_\textrm {T}}^2+\omega _{_\textrm {T}}\approx 133.06582372905672183, \\ \alpha _5 & =& 2\omega _{_\textrm {T}}^4+4\omega _{_\textrm {T}}^3-10\omega _{_\textrm {T}}^2-4\omega _{_\textrm {T}}\approx 110.55940610241204683, \\ \alpha _4 & =& -3\omega _{_\textrm {T}}^4-6\omega _{_\textrm {T}}^3+14\omega _{_\textrm {T}}^2+6\omega _{_\textrm {T}}+1 \approx -172.39088809543209589, \\ \alpha _3 & =& 4\omega _{_\textrm {T}}^3-6\omega _{_\textrm {T}}^2-4\omega _{_\textrm {T}}-4 \approx 22.707791497616619358, \\ \alpha _2 & =& \omega _{_\textrm {T}}+6\approx 8.7480500253477966212, \\ \alpha _1 & =& -4, \\ \alpha _0 & =& 1. \end{eqnarray*}

The largest real root of the nominator polynomial function \(\mu '_\delta (\omega _{_\textrm {T}},0,n)\) is \(\approx 0.63786\ldots \), hence for \(n\in \mathbf{d}_5\), \(\mu '_\delta (\omega _{_\textrm {T}},0,n){\gt}0\). Then, according to Proposition 7, the function \(\delta (\omega _{_\textrm {T}},0,n)=\mu _\delta (\omega _{_\textrm {T}},0,n)\Pi (\omega _{_\textrm {T}},0,n)\) is monotonically increasing.

To prove that \(\beta (\omega _{_\textrm {T}},0,n)\) is monotone increasing function to its limit, we derivative the function \(\mu _\beta (\omega _{_\textrm {T}},0,n)\), is \(2\omega _{_\textrm {T}}/[(\omega _{_\textrm {T}}-1)n+1]^2{\gt}0\). Then, according to Proposition 7, the function \(\beta (\omega _{_\textrm {T}},0,n)=\mu _\beta (\omega _{_\textrm {T}},0,n)\delta (\omega _{_\textrm {T}},0,n)\) is monotonically increasing.

To prove that \(\theta (\omega _{_\textrm {T}},0,n)\) is monotonically increasing function to its limit. The derivative function \(\mu _\theta (\omega _{_\textrm {T}},0,n)\) is

\[ -\tfrac {2\omega _{_\textrm {T}}^2n[(\omega _{_\textrm {T}}+1)n-2]} {[\omega _{_\textrm {T}}^2n^2-2(\omega _{_\textrm {T}}+1)+2]^2}{\lt}0~ . \]

Then we can say that the function \(\theta (\omega _{_\textrm {T}},0,n)=\mu _\theta (\omega _{_\textrm {T}},0,n)\beta (\omega _{_\textrm {T}},0,n)\) is monotonically increasing. Let the function

\begin{align*} \mu _{\theta \beta \delta }(\omega _{_\textrm {T}},0,n) & =\mu _\theta (\omega _{_\textrm {T}},0,n)\mu _\beta (\omega _{_\textrm {T}},0,n)\mu _\delta (\omega _{_\textrm {T}},0,n)\\ & =\tfrac {\omega _{_\textrm {T}}n(n-1)[(\omega _{_\textrm {T}}+1)n-1]^2(\omega _{_\textrm {T}}n^2+n-1)} {[(\omega _{_\textrm {T}}-1)n+1]^2[\omega _{_\textrm {T}}^2n^2-2(\omega _{_\textrm {T}}+1)n+2] [\omega _{_\textrm {T}}^2n^2-(\omega _{_\textrm {T}}+1)n+1]}, \end{align*}

its derivative is

\begin{align*} \mu ’_{\theta \beta \delta }(\omega _{_\textrm {T}},0,n) =\tfrac {\omega _{_\textrm {T}}[(\omega _{_\textrm {T}}+1)n-1]P_8(\omega _{_\textrm {T}},n)} {[(\omega _{_\textrm {T}}-1)n+1]^3[\omega _{_\textrm {T}}^2n^2-2(\omega _{_\textrm {T}}+1)n+2]^2 [\omega _{_\textrm {T}}^2n^2-(\omega _{_\textrm {T}}+1)n+1]^2} \end{align*}

where polynomial \(P_8(\omega _{_\textrm {T}},n)=\alpha _8n^8+\alpha _7n^7+\alpha _6n^6+\alpha _5n^5+\alpha _4n^4+\alpha _3n^3+\alpha _2n^2+\alpha _1n+\alpha _0\) has the following coefficients:

\begin{eqnarray*} \alpha _8 & =& \omega _{_\textrm {T}}^7-4\omega _{_\textrm {T}}^5+4\omega _{_\textrm {T}}^4+3\omega _{_\textrm {T}}^3 \approx 847.0086516, \\ \alpha _7 & =& 4\omega _{_\textrm {T}}^5-16\omega _{_\textrm {T}}^4-12\omega _{_\textrm {T}}^3-8\omega _{_\textrm {T}}^2 -4\omega _{_\textrm {T}}\approx -606.0300766, \\ \alpha _6 & =& -3\omega _{_\textrm {T}}^6-8\omega _{_\textrm {T}}^5+18\omega _{_\textrm {T}}^4+28\omega _{_\textrm {T}}^3 +43\omega _{_\textrm {T}}^2+18\omega _{_\textrm {T}}-2\approx -565.9812397, \\ \alpha _5 & =& 10\omega _{_\textrm {T}}^5+8\omega _{_\textrm {T}}^4-18\omega _{_\textrm {T}}^3-72\omega _{_\textrm {T}}^2 -24\omega _{_\textrm {T}}+12\approx 1052.2011279, \\ \alpha _4 & =& -14\omega _{_\textrm {T}}^4-15\omega _{_\textrm {T}}^3+38\omega _{_\textrm {T}}^2-4\omega _{_\textrm {T}}-30 \approx -863.72570760, \\ \alpha _3 & =& 14\omega _{_\textrm {T}}^3+8\omega _{_\textrm {T}}^2+36\omega _{_\textrm {T}}+40\approx 489.8813608, \\ \alpha _2 & =& -9\omega _{_\textrm {T}}^2-30\omega _{_\textrm {T}}-30\approx -180.4075112, \\ \alpha _1 & =& 8\omega _{_\textrm {T}}+12\approx 33.9844002, \\ \alpha _0 & =& -2. \end{eqnarray*}

The monomials \((\omega _{_\textrm {T}}+1)n-1\) and \((\omega _{_\textrm {T}}-1)n+1\) are equal to 0 in \(0.2668054\ldots \) and \(-0.572066\ldots \). The largest positive real root of polynomial \(P_8(\omega _{_\textrm {T}},n)\) is \(\approx 0.600633\ldots \), hence \(\mu '_{\theta \beta \delta }(\omega _{_\textrm {T}},0,n){\gt}0\) for \(n\in \mathbf{d}_5\), i.e. \(\mu _{\theta \beta \delta }(\omega _{_\textrm {T}},0,n)\) is increasing, then and the function \(\theta (\omega _{_\textrm {T}},0,n)=\mu _{\theta \beta \delta }(\omega _{_\textrm {T}},0,n)\Pi (\omega _{_\textrm {T}},0,n)\) is increasing for \(n\in \mathbf{d}_5\).

Monotonous function values \(\lambda \), \(\delta \), \(\beta \) and \(\theta \) for \(n=5\) are:

\begin{eqnarray*} \lambda (\omega _{_\textrm {T}},0,5) & \approx & 0.093965939752349623079, \\ \delta (\omega _{_\textrm {T}},0,5) & \approx & 0.349197650213356803400, \\ \beta (\omega _{_\textrm {T}},0,5) & \approx & 0.636005603331306147860, \\ \theta (\omega _{_\textrm {T}},0,5) & \approx & 0.783192428417692776398. \end{eqnarray*}

For the function \(\delta \) we have

\[ \lim _{n\to \infty }\delta (\omega _{_\textrm {T}},0,n)=\tfrac {\omega _{_\textrm {T}}-1}{\omega _{_\textrm {T}}+1}\approx 0.46638919265374213777. \]

Proof â–¼

Theorem 27

The optimum i-factor for Tanabe’s method is

\begin{equation} \label{I-FactorOptimMT} c(n)=\tfrac {1}{\omega _\emph {T}n}. \end{equation}

Proof â–¼

The constants \(a=\omega _{_\textrm {T}}\) and \(b=0\), are the best values in the given conditions, so the i-factor \(c(n)\) given by (52), is optimal.

Proof â–¼

Theorem 28

If the initial distinct approximation \(z^{(0)}_1,z^{(0)}_2,\ldots ,z^{(0)}_n\) satisfy the initial condition

\begin{equation} \label{CondInitialaCuCOptimMT} w^{(0)} 53

for \(n\in \mathbf{d}_5\), where \(c\) given by (52), then Tanabe’s method with inclusion disks \(D^*_k\), given by (10), is convergent.

Proof â–¼

Since \(\omega _{_\textrm {T}}{\gt}2\) and \(b=0\), then according to corollary 4 the disks \(D^*_k\), given by (10), are mutually disjoint and each of them contain exactly one zero of polynomial \(P\).

The conclusions on Lemma 26 assure the fulfillment of Lemmas 20, 21 and 22, fact, that in turn, assures the convergence for Tanabe’s method if the initial condition (53) is verified.

Proof â–¼

5 Conclusions

For Durand–Kerner’s method, given by (19), with the inclusion disks \(D_k\), given by (14), the optimum i-factor is

\[ c(n)=\tfrac {1}{\omega n+\tau }~ ,\ \ n\in \mathbf{d}_5, \]

where \(\omega \approx 1.7632228343518967\ldots \), \(\tau \approx 0.88049674007368891\ldots \).
For Durand–Kerner’s method, given by (19), with the inclusion disks \(D^*_k\), given by (10), the optimum i-factor is

\[ c(n)=\tfrac {1}{2n+\tau _*},\ \ n\in \mathbf{d}_5, \]

where \(\tau _*\approx 0.67211423631036255\ldots \).
For Tanabe’s method, given by (38), with the inclusion disks \(D^*_k\), given by (10), the optimum i-factor is

\[ c(n)=\tfrac {1}{\omega _{_\textrm {T}}n},\ \ n\in \mathbf{d}_5, \]

where \(\omega _{_\textrm {T}}\approx 2.7480500253477966212\ldots \).

Bibliography

1: N. H. Abel, Beweis der Unmoglichkeit, algebraische Gleichungen von hoheren Graden als dem vierten allgemein aufzulosen, J. Reine Angew. Math., 1, Reprinted in Abel, N. H. Œ (Ed. L. Sylow and S. Lie), Christiania (Oslo), Norway, 1881. Reprinted in New York: Johnson Reprint Corp., pp. 66–87, 1988, pp. 65–84, 1826.
2: K. Weierstrass, Neuer Beweis des Satzes, dass jede ganze rationale Funktion einer Veränderlichen dargestellt werden kann als ein Product aus linearen Funktionen dertelben Verändelichen, Ges. Werke, 3, pp. 251–269, 1903.
3: I. E. Durand, Solutions Numérique des Équations Algébriques. Équations du Type F(x)=0; Racines d’une Polynôme, Masson, Paris, 1, pp. 279–281, 1960.
4: K. Docev, An Alternative Method of Newton for Simultaneous Calculation of All the Roots of a Given Algebraic Equation, Phys. Math. J. Bulgar. Acad. Sci., 5, No. 2, pp. 136–139, 1962 (in bulgarian).
5: W. Börsch-Supan, A posteriori error bounds for the zeros of polynomials, Numer. Math., 5, pp. 380–398, 1963.
6: I. O. Kerner, Simultaneous Displacement of Polynomial Roots if Real and Simple, Comm. ACM, 9, pp. 273, 1966.
7: W.Börsch-Supan, Residuenabschätzung für Polynom-Nullstellen mittels Lagrange Interpolation, Numer. Math. 14, pp. 287–296, 1970.
8: D. Braess and K. P. Handeler, Simultaneous inclusion of the zeros of polynomial, Numer. Math., 21, pp. 161–165, 1973.
9: A. W. M. Nourein, An iteration formula for the simultaneous determination of the zeroes of polynomial, J. Comput. Appl. Math., 4, pp. 251–254, 1975.
10: K. Tanabe, Behavior of the sequences around multiple zeros generated by some simultaneous methods for solving algebraic equations, Tech. Rep. Inf. Procces. Numer. Anal., 4-2, pp. 1–6, 1983 (in Japanese).
11: D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1986, address: Middlesex, England.
12: C. Carstensen, Anwendungen von Begleitmatrizen, Z. Angew. Math., 71. pp. 809–812, 1991.
13: C. Carstensen, Inclusion of the roots of polynomial based on Gerschgorin’s theorem, Numer. Math., 59, pp. 349–360, 1991.
14: C. B. Boyer and U. C. Merzbach , A History of Mathematics, CHAPTER: The Renaissance, Wiley, address: New York, edition: 2an, pp. 282–287, 1991.
15: M. S. Petković, C. Trajković and M. Carstensen, Weierstrass’ formula and zero-finding methods, Numer. Math., 69, pp. 353–372, 1995.
16: M. S. Petković, On initial conditions for the convergence of simultaneous root finding methods, Computing, 57, pp. 163–177, 1996.
17: M. S. Petković and J. Herceg, Point estimation and safe convergence of root-finding simultaneous methods, Scientific Review, 21-22, pp. 117–130, 1996.
18: G. Birkhoff and S. Mac Lane, Galois Theory, CHAPTER: 15 in A Survey of Modern Algebra, PUBLISHER: Macmillan, address: New York, edition: 5th, pp. 395–421, 1996.
19: R. M. Corless, G. H. Gonnet, D. E. G. Hare , D. J. Jeffrey and D. E. Knuth, On the Lambert Function, Adv. Comput. Math., 5, pp. 329–359, 1996.
20: M. S. Petković, J. Herceg and S. Ilić, Point Estimation Theory and its Applications, Institute of Mathematics, address: Novi Sad, 1997.
21: M. S. Petković and J. Herceg, Börsch-Supan-like methods: Point estimation and parallel implementation, Inter. J. Comput. Math., 64, pp. 117–130, 1997.
22: M. S. Petković and S. Ilić, Point estimation and the convergence of Ehrlich-Aberth metod, Publ. Inst. Math., 62, pp. 141–149, 1997.
23: P. Batra, Improvement of a convergence condition for the Durand-Kerner iteration, J. of Comp. and Appl. Math., 96 2, pp. 117–125, 1998.
24: M. S. Petković, J. Herceg and S. Ilić, Safe Convergence of Simultaneous Methods for Polynomial Zeros, Numerical Algorithms, 17, pp. 313–331, 1998.
25: M. S. Petković, J. Herceg and S. Ilić, Point estimation and some applications to iterative methods, BIT, 38, pp. 112–126, 1998.
26: M. S. Petković and J. Herceg, On the convergence of Wang-Zheng’s metod, J. Comput. Appl. Math., 91, pp. 123–135, 1998.
27: D. S. Dummit and R. M. Foote, Galois Theory, CHAPTER:14 in Abstract Algebra, PUBLISHER: Prentice-Hall, address: New York, edition: 2nd Englewood Cliffs, pp. 471–570, 1998.
28: M. S. Petković and J. Herceg, Point estimation of simultaneous methods for solving polynomial equations:a survey, J. Comput. Appl. Math., 136, pp. 183–207, 2001.
29: O. Cira, Metode numerice pentru rezolvarea ecuaţiilor algebrice, Ed. Academiei Române, 2005, Bucureşti, (in romanian).
30: O. Cira and C. M. Cira, The optimum convergence condition for the Durand-Kerner type simultaneous inclusion method, BOOKTITLE: SYNASC 2006 – \(8^{th}\) International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 171–174, 2006, address: Timişoara, România, month: 26-29 September, publisher: IEEE Computer Society, Los Alamitos California, Washington, Tokyo.
31: M. S. Petković, Point estimation of root finding methods, PUBLISHER: Springer, 2008, series: Lecture Notes in Mathematics 1933.
32: Mathworld, howpublished: http://mathworld.wolfram.com, 30 Aug. 2010.
33: Wolfram, howpublished: http://www.wolfram.com/products/mathematica, 30 Sept. 2010.

Optimal inequality factor for Durand–Kerner’s and Tanabe’s methods

1 Introduction

2 Simultaneous methods with corrections

3 The Durand–Kerner’s method

3.1 Durand–Kerner’s method convergence

3.2 The analytically optimum i-factor for Durand–Kerner’s method with inclusion disks \(D_k\)

3.3 The analytically optimum i-factor for Durand–Kerner’s methodwith inclusion disks \(D^*_k\)

4 The Tanabe’s method

4.1 Tanabe’s method convergence

4.2 The optimum analytic i-factor

5 Conclusions

Bibliography

Optimal inequality factor
for Durand–Kerner’s and Tanabe’s methods

3.3 The analytically optimum i-factor for Durand–Kerner’s method
with inclusion disks \(D^*_k\)