- Research
- Open access
- Published:
On the convergence of high-order Ehrlich-type iterative methods for approximating all zeros of a polynomial simultaneously
Journal of Inequalities and Applications volume 2015, Article number: 336 (2015)
Abstract
We study a family of high-order Ehrlich-type methods for approximating all zeros of a polynomial simultaneously. Let us denote by \(T^{(1)}\) the famous Ehrlich method (1967). Starting from \(T^{(1)}\), Kjurkchiev and Andreev (1987) have introduced recursively a sequence \({(T^{(N)})_{N = 1}^{\infty}}\) of iterative methods for simultaneous finding polynomial zeros. For given \(N \ge1\), the Ehrlich-type method \(T^{(N)}\) has the order of convergence \({2 N + 1}\). In this paper, we establish two new local convergence theorems as well as a semilocal convergence theorem (under computationally verifiable initial conditions and with an a posteriori error estimate) for the Ehrlich-type methods \(T^{(N)}\). Our first local convergence theorem generalizes a result of Proinov (2015) and improves the result of Kjurkchiev and Andreev (1987). The second local convergence theorem generalizes another recent result of Proinov (2015), but only in the case of the maximum norm. Our semilocal convergence theorem is the first result in this direction.
1 Introduction
Throughout this paper \({(\mathbb{K},|\cdot|)}\) denotes an algebraically closed field and \(\mathbb{K}[z]\) denotes the ring of polynomials (in one variable) over \(\mathbb{K}\). For a given vector x in \(\mathbb{K}^{n}\), \({x_{i}}\) always denotes the ith coordinate of x. In particular, if F is a map with values in \(\mathbb{K}^{n}\), then \({F_{i}(x)}\) denotes the ith coordinate of the vector \(F(x)\). We endow the vector space \(\mathbb{K}^{n}\) with the norm \(\|x\|_{p}\) defined as usual:
We endow \(\mathbb{R}^{n}\) with the coordinate-wise ordering ⪯ defined by
Then \({(\mathbb{R}^{n},\|\cdot\|_{p})}\) is a solid vector space. We endow \(\mathbb{K}^{n}\) with the cone norm \(\|\cdot\| \colon \mathbb{K}^{n} \to \mathbb{R}^{n} \) defined by
Then \({(\mathbb{K}^{n},\|\cdot\|, \preceq)}\) is a cone normed space over \(\mathbb{R}^{n}\) (see, e.g., Proinov [1]).
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\). A vector \({\xi\in \mathbb{K}^{n}}\) is said to be a root vector of f if
where \({a_{0} \in \mathbb{K}}\). Obviously, f has a root vector in \(\mathbb{K}^{n}\) if and only if it splits in \(\mathbb{K}\). We denote by \(\operatorname{sep}(f)\) the separation number of f which is defined to be the minimum distance between two distinct zeros of f, that is,
1.1 The Weierstrass method and Weierstrass correction
In the literature, there are a lot of iterative methods for finding all zeros of f simultaneously (see, e.g., the monographs of Sendov et al. [2], Kyurkchiev [3], McNamee [4] and Petković [5] and references given therein). In 1891, Weierstrass [6] published his famous iterative method for simultaneous computation of all zeros of f. The Weierstrass method is defined by the following iteration:
where the operator \({W_{f} \colon\mathcal{D} \subset \mathbb{K}^{n} \to \mathbb{K}^{n}}\) is defined by
where \({a_{0} \in \mathbb{K}}\) is the leading coefficient of f and the domain \(\mathcal{D}\) of W is the set of all vectors in \(\mathbb{K}^{n}\) with distinct components. The Weierstrass method (1.5) has second order of convergence provided that all zeros of f are simple. The operator \(W_{f}\) is called Weierstrass correction. We should note that \(W_{f}\) plays an important role in many semilocal convergence theorems for simultaneous methods.
1.2 The Ehrlich method
Another famous iterative method for finding simultaneously all zeros of a polynomial f was introduced by Ehrlich [7] in 1967. The Ehrlich method is defined by the following fixed point iteration:
where the operator \({T \colon\mathscr{D} \subset \mathbb{K}^{n} \to \mathbb{K}^{n}}\) is defined by \({T(x) = (T_{1}(x),\ldots,T_{n}(x))}\) with
and the domain of T is the set
Here and throughout the paper, we denote by \(I_{n}\) the set of indices \({1, \ldots, n}\), that is, \({I_{n} = \{1, \ldots, n\}}\). The Ehrlich method has third order of convergence if all zeros of f are simple. The Ehrlich method was rediscovered by Abert [8] in 1973. In 1970, Börsch-Supan [9] introduced another third-order method for numerical computation of all zeros of a polynomial simultaneously. In 1982, Werner [10] has proved that the both methods are identical. The Ehrlich method (1.7) is known also as ‘Ehrlich-Abert method’, ‘Börsch-Supan method’, and ‘Abert method’.
Recently, Proinov [11] obtained two local convergence theorems for Ehrlich method under different types of initial conditions. The first one generalizes and improves the results of Kyurkchiev and Tashev [12, 13] and Wang and Zhao [14], Theorem 2.1. The second one generalizes and improves the results of Wang and Zhao [14], Theorem 2.2 and Tilli [15], Theorem 3.3.
Before we state the two results of [11], we need some notations which will be used throughout the paper. For given vectors \({x \in \mathbb{K}^{n}}\) and \({y \in \mathbb{R}^{n}}\), we define in \({\mathbb{R}^{n}}\) the vector
provided that y has no zero components. Given p such that \({1 \le p \le\infty}\), we always denote by q the conjugate exponent of p, i.e. q is defined by means of
In the sequel, we use the function \({d \colon \mathbb{K}^{n} \to \mathbb{R}^{n}}\) defined by \({d(x) = (d_{1}(x),\ldots,d_{n}(x))}\) with
Let \({a > 0}\) and \({b \ge1}\). We define the real function Ï• by
and the real number R as follows:
Theorem 1.1
(Proinov [11])
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) which has only simple zeros, \({\xi\in \mathbb{K}^{n}}\) be a root vector of f and \({1 \le p \le\infty}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess satisfying
where \({a = (n - 1) ^{1/q}}\) and \({b = 2^{1/q}}\). Then the Ehrlich iteration (1.7) is well defined and converges cubically to ξ with error estimates
for all \({k \ge0}\), where \({\lambda= \phi(E(x^{(0)}))}\) and the function Ï• is defined by (1.10).
Theorem 1.2
(Proinov [11])
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\), \({\xi\in \mathbb{K}^{n}}\) be a root vector of f and \({1 \le p \le\infty}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is a vector with distinct components satisfying
where \({a = (n - 1) ^{1/q}}\) and \({b = 2^{1/q}}\). Then f has only simple zeros in \(\mathbb{K}\) and Ehrlich iteration (1.7) is well defined and converges to ξ with error estimates
for all \({k \ge0}\), where \({\lambda= \phi(E(x^{(0)}))}\), \({\theta= \psi(E(x^{(0)}))}\) and the function ϕ is defined by (1.10) and the function ψ by
Moreover, the method converges cubically to ξ provided that \({E(x^{(0)}) < R}\).
1.3 A family of high-order Ehrlich-type methods
In the following definition, we define a sequence \((T^{(N)})_{N = 0}^{\infty}\) of iteration functions in the vector space \(\mathbb{K}^{n}\). In what follows, we define the binary relation # on \(\mathbb{K}^{n}\) by
Definition 1.3
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\). Define the sequence \((T^{(N)})_{N=0}^{\infty}\) of functions \({T^{(N)} \colon D_{N} \subset \mathbb{K}^{n} \to \mathbb{K}^{n}}\) recursively by setting \({T^{(0)}(x) = x}\) and
where the sequence of domains \((D_{N})_{N = 0}^{\infty}\) is also defined recursively by setting \({D_{0} = \mathbb{K}^{n}}\) and
Given \({N \in \mathbb{N}}\), the Nth method of Kjurkchiev-Andreev’s family can be defined by the following fixed point iteration:
It is easy to see that in the case \({N = 1}\) the Ehrlich-type method (1.18) coincides with the classical Ehrlich method (1.7). The order of convergence of the Ehrlich-type method (1.18) is \({2 N + 1}\).
Kjurkchiev and Andreev [16] established the following convergence result for the Ehrlich-type methods (1.18). This result and its proof can also be found in the monographs of Sendov, Andreev and Kjurkchiev [2], Section 19 and Kyurkchiev [3], Chapter 9.2).
Theorem 1.4
(Kjurkchiev and Andreev [16])
Let \({f \in \mathbb{C}[z]}\) be a polynomial of degree \({n \ge2}\) which has only simple zeros, \({\xi\in \mathbb{C}^{n}}\) be a root vector of f and \({N \ge1}\). Let \({0 < h < 1}\) and \({c > 0}\) be such that
where \({\delta= \operatorname{sep}(f)}\) defined by (1.4). Suppose \({x^{(0)} \in \mathbb{C}^{n}}\) is an initial guess satisfying the condition
Then the Ehrlich-type method (1.18) converges to ξ with error estimate
1.4 The purpose of the paper
In this paper, we present two new local convergence theorems as well as a semilocal convergence theorem (under computationally verifiable initial conditions and with an a posteriori error estimate) for Ehrlich-type methods (1.18). Our first local convergence result (Theorem 4.6) generalizes Theorem 1.1 (Proinov [11]) and improves Theorem 1.4 (Kjurkchiev and Andreev [16]). Our second local convergence result (Theorem 5.4) generalizes Theorem 1.2 (Proinov [11]), but only in the case \({p = \infty}\). Furthermore, several numerical examples are provided to show some practical applications of our semilocal convergence result.
2 A general convergence theorem
Recently, Proinov [17–19] has developed a general convergence theory for iterative processes of the type
where \({T \colon D \subset X \to X}\) is an iteration function in a cone metric space X. In order to make this paper self-contained, we briefly review some basic definitions and results from this theory.
Throughout this paper J denotes an interval on \({\mathbb{R}_{+}}\) containing 0. For an integer \({k \ge1}\), we denote by \({S_{k}(t)}\) the following polynomial:
If \({k = 0}\) we assume that \({S_{k}(t) \equiv0}\). Throughout the paper we assume by definition that \({0^{0} = 1}\).
Definition 2.1
([18])
A function \({\varphi\colon J \to \mathbb{R}_{+}}\) is called quasi-homogeneous of degree \({r \ge0}\) on J if it satisfies the following condition:
If m functions \({\varphi_{1},\ldots,\varphi_{m}}\) are quasi-homogeneous on J of degree \({r_{1},\ldots,r_{m}}\), then their product \({\varphi_{1} \cdots\varphi_{m}}\) is a quasi-homogeneous function of degree \({r_{1} + \cdots+ r_{m}}\) on J. Note also that a function φ is quasi-homogeneous of degree 0 on J if and only it is nondecreasing on J.
Definition 2.2
([17])
A function \({\varphi\colon J \to J}\) is said to be a gauge function of order \({r \ge1}\) on J if it satisfies the following conditions:
-
(i)
φ is quasi-homogeneous of degree r on J;
-
(ii)
\({\varphi(t) \le t}\) for all \({t \in J}\).
A gauge function φ of order r on J is said to be a strict gauge function if the inequality in (ii) holds strictly whenever \({t \in J \backslash\{ 0 \}}\).
The following is a sufficient condition for a gauge function of order r.
Lemma 2.3
([18])
If \({\varphi\colon J \to \mathbb{R}_{+}}\) is a quasi-homogeneous function of degree \({r \ge1}\) on an interval J and \({R > 0}\) is a fixed point of φ in J, then φ is a gauge function of order r on \({[0, R]}\). Moreover, if \({r > 1}\), then function φ is a strict gauge of order r on \({J = [0, R)}\).
Definition 2.4
([17])
Let \({T \colon D \subset X \to X}\) be a map on an arbitrary set X. A function \({E \colon D \to \mathbb{R}_{+}}\) is said to be a function of the initial conditions of T (with a gauge function φ on J) if there exists a function \({\varphi\colon J \to J}\) such that
Definition 2.5
([17])
Let \({T \colon D \subset X \to X}\) be a map on an arbitrary set X, and \(E \colon D \to \mathbb{R}_{+}\) be a function of the initial conditions of T with a gauge function on J. Then a point \({x \in D}\) is said to be an initial point of T (with respect to E) if \({E(x) \in J}\) and all of the iterates \({T^{k}x}\) (\(k = 0,1,2,\ldots \)) are well defined and belong to D.
The following is a simple sufficient condition for initial points.
Theorem 2.6
([18])
Let \({T \colon D \subset X \to X}\) be a map on an arbitrary set X and \({E \colon D \to \mathbb{R}_{+}}\) be a function of the initial conditions of T with a gauge function φ on J. Suppose that \({x \in D}\) with \({E(x) \in J}\) implies \({Tx \in D}\). Then every point \({x_{0} \in D}\) such that \({E(x_{0}) \in J}\) is an initial points of T.
Definition 2.7
([19])
Let \({T \colon D \subset X \to X}\) be an operator in a cone normed space \({(X,\|\cdot\|)}\) over a solid vector space \({(Y,\preceq)}\), and let \({E \colon D \to \mathbb{R}_{+}}\) be a function of the initial conditions of T with a gauge function on an interval J. Then the operator T is said to be an iterated contraction at a point \({\xi\in D}\) (with respect to E) if \(E{(\xi) \in J}\) and
where the control function \({\beta\colon J \to[0,1)}\) is nondecreasing.
The following fixed point theorem plays an important role in our paper.
Theorem 2.8
(Proinov [19])
Let \({T \colon D \subset X \to X}\) be an operator of a cone normed space \({(X,\|\cdot\|)}\) over a solid vector space \({(Y,\preceq)}\), and let \({E \colon D \to \mathbb{R}_{+}}\) be a function of the initial conditions of T with a gauge function φ of order \({r \ge1}\) on an interval J. Suppose T is an iterated contraction at a point ξ with respect to E with control function β such that
and there exists a function \({\psi\colon J \to \mathbb{R}_{+}}\) such that
where \({\phi\colon J \to \mathbb{R}_{+}}\) is a nondecreasing function satisfying
Then the following statements hold true.
-
(i)
The point ξ is a unique fixed point of T in the set \({U = \{ x \in D : E(x) \in J \}}\).
-
(ii)
Starting from each initial point \({x^{(0)}}\) of T, Picard iteration (2.1) remains in the set U and converges to ξ with error estimates
$$ \bigl\Vert x^{(k+1)} - \xi\bigr\Vert \preceq\theta \lambda^{r^{k}} \bigl\Vert x^{(k)} - \xi\bigr\Vert \quad \textit{and}\quad \bigl\Vert x^{(k)} - \xi\bigr\Vert \preceq \theta^{k} \lambda^{S_{k}(r)} \bigl\Vert x^{(0)} - \xi \bigr\Vert $$(2.8)for all \({k \ge0}\), where \({\lambda= \phi(E(x^{(0)}))}\) and \({\theta = \psi(E(x^{(0)}))}\).
In the case \({\beta\equiv\phi}\), Theorem 2.8 reduces to the following result.
Corollary 2.9
([19])
Let \({T \colon D \subset X \to X}\) be an operator in a cone normed space \({(X,\|\cdot\|)}\) over a solid vector space \({(Y,\preceq)}\), and let \({E \colon D \to \mathbb{R}_{+}}\) be a function of the initial conditions of T with a strict gauge function φ of order \({r \ge1}\) on an interval J. Suppose that T is an iterated contraction at a point ξ with respect to E and with control function ϕ satisfying (2.7). Then the following statements hold true.
-
(i)
The point ξ is a unique fixed point of T in the set \({U = \{ x \in D : E(x) \in J \}}\).
-
(ii)
Starting from each initial point \({x^{(0)}}\) of T, Picard iteration (2.1) remains in U and converges to ξ with order r and error estimates
$$ \bigl\Vert x^{(k+1)} - \xi\bigr\Vert \preceq \lambda^{r^{k}} \bigl\Vert x^{(k)} - \xi\bigr\Vert \quad \textit{and}\quad \bigl\Vert x^{(k)} - \xi\bigr\Vert \preceq \lambda^{S_{k}(r)} \bigl\Vert x^{(0)} - \xi\bigr\Vert $$(2.9)for all \({k \ge0}\), where \({\lambda= \phi(E(x^{(0)}))}\).
3 Some inequalities in \(\mathbb{K}^{n}\)
In this section, we present some useful inequalities in \(\mathbb{K}^{n}\) which play an important role in the paper.
Lemma 3.1
([20])
Let \({u,v \in \mathbb{K}^{n}}\), v be a vector with distinct components and \({1 \le p \le\infty}\). Then for all \({i,j \in I_{n}}\),
Lemma 3.2
([19])
Let \({u,v \in \mathbb{K}^{n}}\) and \({1 \le p \le\infty}\). If the vector v has distinct components and
then the vector u also has distinct components.
Lemma 3.3
([21])
Let \({u,v,\xi\in \mathbb{K}^{n}}\), ξ be a vector with distinct components, \({1 \le p \le\infty}\) and
Then for all \({i,j \in I_{n}}\),
Lemma 3.4
Let \({u,v,\xi\in \mathbb{K}^{n}}\), \({\alpha\ge0}\), and \({1 \le p \le\infty }\). If v is a vector with distinct components such that
then for all \({i,j \in I_{n}}\),
Proof
By the triangle inequality of cone norm in \(\mathbb{K}^{n}\) and (3.5), we obtain
which yields
Taking the p-norm, we get
From (3.1) and (3.7), we obtain (3.6), which completes the proof. □
Lemma 3.5
Let \({u,v,\xi\in \mathbb{K}^{n}}\), \({\alpha\ge0}\), and \({1 \le p \le\infty }\). If v is a vector with distinct components such that (3.5) holds, then for all \({i,j \in I_{n}}\),
Proof
From (3.2) and (3.7), we get (3.8), which completes the proof. □
4 Local convergence theorem of the first type
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) which has only simple zeros in \(\mathbb{K}\), and let \({\xi\in \mathbb{K}^{n}}\) be a root vector of f. In this section we study the convergence of the Ehrlich-type methods (1.18) with respect to the function of the initial conditions \({E \colon \mathbb{K}^{n} \to \mathbb{R}_{+}}\) defined as follows:
Let \({a > 0}\) and \({b \ge1}\). Throughout this section, we define the function Ï• and the real number R by (1.10) and (1.11), respectively. It is easy to show that R is the smallest positive solution of the equation \({\phi(t) = 1}\). Note that Ï• is an increasing function which maps \([0,R]\) onto \([0,1]\). Besides, Ï• is quasi-homogeneous of degree 2 on \({[0,R]}\). In the next definition, we introduce a sequence of such functions.
Definition 4.1
We define the sequence \((\phi_{N})_{N = 0}^{\infty}\) of nondecreasing functions \(\phi_{N} \colon[0,R] \to[0,1]\) recursively by setting \(\phi_{0}(t) = 1\) and
where \({a > 0}\) and \({b \ge1}\) are constants.
Proof of the correctness of Definition 4.1
We prove the correctness of the definition by induction. For \(N = 0\) it is obvious. Assume that for some \({N \ge0}\) the function \(\phi_{N}\) is well defined and nondecreasing on \({[0,R]}\) and \({\phi_{N}(R) = 1}\). We shall prove the same for \(\phi_{N + 1}\). It follows from the induction hypothesis that
which means that the function \({\phi_{N + 1}}\) is well defined on \({[0, R]}\). From (4.2) and the induction hypothesis, we deduce that \({\phi_{N + 1}}\) is nondecreasing on \([0,R]\). From (4.2) and \({\phi_{N}(R) = 1}\), we obtain
This completes the induction and the proof of the correctness of Definition 4.1. □
Definition 4.2
For any integer \({N \ge0}\), we define the function \({\varphi_{N} \colon [0,R] \to[0,R]}\) as follows:
where the function \(\phi_{N}\) is defined by Definition 4.1.
In the next lemma, we present some properties of the functions \(\phi_{N}\) and \(\varphi_{N}\).
Lemma 4.3
Let \({N \ge0}\). Then:
-
(i)
\(\phi_{N}\) is a quasi-homogeneous function of degree 2N on \({[0,R]}\);
-
(ii)
\({\phi_{N+1}(t) \le\phi(t) \phi_{N}(t)}\) for every \({t \in[0,R]}\);
-
(iii)
\({\phi_{N+1}(t) \le\phi_{N}(t)}\) for every \({t \in[0,R]}\);
-
(iv)
\({\phi_{N}(t) \le\phi(t)^{N}}\) for every \({t \in[0,R]}\);
-
(v)
\(\varphi_{N}\) is a gauge function of order \({2 N + 1}\) on \({[0,R]}\).
Proof
Claim (i) can easily be proved by induction. From (4.2) and (4.3), we get
which proves (ii). Claim (iii) is a trivial consequence from (ii). Claim (iv) follows from (ii) by induction. Claim (v) follows from (i) and the definition of \(\varphi_{N}\). □
Lemma 4.4
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\), \({\xi\in \mathbb{K}^{n}}\) be a root vector of f and \({N \ge0}\). Suppose \({x \in D_{N}}\) is a vector such that \({f(x_{i}) \ne0}\) for some \({i \in I_{n}}\).
-
(i)
If \({x \mathbin{\#} T^{(N)}(x)}\), then
$$ \frac{f'(x_{i})}{f(x_{i})} - \sum_{j \ne i} \frac{1}{x_{i} - T_{j}^{(N)}(x)} = \frac{1 - \sigma_{i}}{x_{i} -\xi_{i}}, $$(4.5)where \({\sigma_{i} \in \mathbb{K}}\) is defined by
$$ \sigma_{i} = (x_{i} - \xi_{i}) \sum_{j \ne i} \frac{ T_{j} ^{(N)}(x) - \xi_{j}}{(x_{i} - \xi_{j})(x_{i} - T_{j} ^{(N)}(x))} . $$(4.6) -
(ii)
If \({x \in D_{N + 1}}\), then
$$ T^{(N + 1)}_{i}(x) - \xi_{i} = - \frac{ \sigma_{i}}{1 - \sigma_{i}} (x_{i} - \xi_{i}). $$(4.7)
Proof
(i) Taking into account that ξ is a root vector of f, we get
which proves (4.5).
(ii) It follows from \({x \in D_{N + 1}}\) that
Then from (1.16) and (4.5), we obtain
which completes the proof. □
Lemma 4.5
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) which has only simple zeros in \(\mathbb{K}\), \({\xi\in \mathbb{K}^{n}}\) be a root vector of f, \({N \ge0}\), and \({1 \le p \le\infty}\). Suppose \({x \in \mathbb{K}^{n}}\) is a vector satisfying the following condition:
where the function \({E \colon \mathbb{K}^{n} \to \mathbb{R}_{+}}\) is defined by (4.1), \({a = (n - 1) ^{1/q}}\), and \({b = 2^{1/q}}\). Then
Proof
We shall prove statements by induction on N. If \({N = 0}\), then (4.10) holds trivially. Assume that (4.10) holds for some \({N \ge0}\).
First, we show that \({x \in D_{N + 1}}\), i.e. \({x \mathbin{\#} T^{(N)}(x)}\) and (4.8) holds for every \({i \in I_{n}}\). It follows from the first inequality in (4.10) that the inequality (3.3) is satisfied with \({u = x}\) and \({v = T^{(N)}(x)}\). Then by Lemma 3.3 and (4.9), we obtain
for every \({j \ne i}\). Consequently, \({x \mathbin{\#} T^{(N)}(x)}\). It remains to prove (4.8) for every \({i \in I_{n}}\). Let \({i \in I_{n}}\) be fixed. We shall consider only the non-trivial case \({f(x_{i}) \ne0}\). In this case (4.8) is equivalent to
We define \(\sigma_{i}\) by (4.6). It follows from Lemma 4.4(i) that (4.12) is equivalent to \({\sigma_{i} \ne1}\). By Lemma 3.1 with \({u = x}\) and \({v = \xi }\) and (4.9), we get
for every \({j \ne i}\). From the triangle inequality in \(\mathbb{K}\), (4.11), (4.13), the induction hypothesis and Hölder’s inequality, we get
From this, \({\phi_{N}(E(x)) \le1}\) and (4.9), we obtain
which yields \({\sigma_{i} \ne1}\), and so (4.8) holds. Hence, \(x \in D_{N + 1}\).
Second, we show that the inequalities in (4.10) hold for \({N + 1}\). The first inequality for \({N + 1}\) is equivalent to
Let \({i \in I_{n}}\) be fixed. If \({x_{i} = \xi_{i}}\), then \({T^{(N + 1)}_{i}(x) = \xi_{i}}\) and so (4.15) becomes an equality. Suppose \({x_{i} \ne\xi_{i}}\). By Lemma 4.4(ii), the triangle inequality in \(\mathbb{K}\), and the estimate (4.14), we get
which proves (4.15). Dividing both sides of the inequality (4.15) by \({d_{i}(\xi)}\) and taking the p-norm, we obtain
which proves that the second inequality in (4.10) holds for \({N + 1}\). This completes the induction and the proof of the lemma. □
Now we are ready to state the main result of this section. In the case \({N = 1}\) this result coincides with Theorem 1.1.
Theorem 4.6
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) which has only simple zeros in \(\mathbb{K}\), \({\xi\in \mathbb{K}^{n}}\) be a root vector of f, \({N \ge1}\), and \({1 \le p \le\infty}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess satisfying
where the function \({E \colon \mathbb{K}^{n} \to \mathbb{R}_{+}}\) is defined by (4.1), \({a = (n - 1) ^{1/q}}\), and \({b = 2^{1/q}}\). Then the Ehrlich-type iteration (1.18) is well defined and converges to ξ with error estimates
for all \({k \ge0}\), where \({\lambda= \phi_{N}(E(x^{(0)}))}\) and the function \(\phi_{N}\) is defined by Definition 4.1.
Proof
We apply Corollary 2.9 to the iteration function \({T^{(N)} \colon D_{N} \subset \mathbb{K}^{n} \to \mathbb{K}^{n}}\) defined by Definition 1.3 and to the function \({E \colon \mathbb{K}^{n} \to \mathbb{R}_{+}}\) defined by (4.1). Let \({J = [0, R)}\). It follows from Lemma 4.5, Lemma 4.3(v), and Lemma 2.3 that E is a function of the initial conditions of \(T^{(N)}\) with a strict gauge function \(\varphi_{N}\) of order \({r = 2 N + 1}\) on J. Since ξ is a root vector of f, then \({E(\xi) = 0 \in J}\). It follows from Lemma 4.5 that \({T^{(N)}}\) is an iterated contraction at a point ξ with respect to E and with control function \(\phi_{N}\). The fact that \({x^{(0)}}\) is an initial point of \({T^{(N)}}\) follows from Lemma 4.5 and Theorem 2.6. Hence, all the assumptions of Corollary 2.9 are satisfied, and the statement of Theorem 4.6 follows from it. □
Corollary 4.7
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) which has only simple zeros in \(\mathbb{K}\), \({\xi\in \mathbb{K}^{n}}\) be a root vector of f, \({N \ge1}\), and \({1 \le p \le\infty}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess satisfying (4.16). Then the Ehrlich-type iteration (1.18) is well defined and converges to ξ with error estimates
for all \({k \ge0}\), where \({\lambda= \phi(E(x^{(0)}))}\) and Ï• is a real function defined by (1.10).
Proof
It follows from Theorem 4.6 and Lemma 4.3(iv). □
Let \({0 < h < 1}\) be a given number. Solving the equation \({\phi(t) = h^{2}}\) in the interval \({(0,R)}\), we can reformulate Corollary 4.7 in the following equivalent form.
Corollary 4.8
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \(n \ge2\) which has n simple zeros in \(\mathbb{K}\), \({\xi\in \mathbb{K}^{n}}\) be a root vector of f, \({N \ge1}\), \({1 \le p \le\infty}\), and \({0 < h < 1}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess which satisfies
where \({a = (n - 1) ^{1/q}}\) and \({b = 2^{1/q}}\). Then the Ehrlich-type method (1.18) is well defined and converges to ξ with error estimates
for all \({k \ge0}\).
Remark 4.9
Corollary 4.8 is an improvement of the result of Kjurkchiev and Andreev [16] (see Theorem 1.4 above). Suppose that a vector \({x^{(0)} \in \mathbb{K}^{n}}\) satisfies (1.20). It is easy to show that condition (1.19) is equivalent to the following one:
From this, the initial condition (1.20) and \({0 < h < 1}\), we obtain
Therefore, \(x^{(0)}\) satisfies (4.19) with \(p = \infty\). Then it follows from Corollary 4.8 that the Ehrlich-type method (1.18) is well defined and converges to ξ with error estimates (4.20). From the second estimate in (4.20) and (1.20), we get the estimate (1.21), which completes the proof.
5 Local convergence theorem of the second type
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \(n \ge2\). We study the convergence of the Ehrlich-type method (1.18) with respect to the function of the initial conditions \({E \colon\mathcal{D} \to \mathbb{R}_{+}}\) defined by
In the previous section, we introduce the functions \(\phi_{N}\), \(\varphi _{N}\), and the real number R with two parameters \({a > 0}\) and \({b \ge1}\). In this section, we consider a special case of \(\phi_{N}\), \(\varphi_{N}\), and R when \({b = 2}\). In other words, now we define R by
Furthermore, we define the functions \(\phi_{N}\) and \(\varphi_{N}\) by Definitions 4.1 and 4.2, respectively, but with
instead of (4.2), where \({a > 0}\) is a constant.
Definition 5.1
For a given integer \(N \ge1\), we define the increasing function \(\beta _{N} \colon[0,R] \to[0,1)\) by
and we define the decreasing function \({\psi_{N} \colon[0,R] \to(0,1]}\) as follows:
Proof of the correctness of Definition 5.1
The functions \({\beta_{N}}\) and \({\psi_{N}}\) are well defined on \({[0, R]}\) since
The monotonicity of \({\beta_{N}}\) and \({\psi_{N}}\) is obvious. It remains to prove that \({\beta_{N}(R) < 1}\) and \({\psi_{N}(R) > 0}\). Since \({\phi_{N}(R) = 1}\), we obtain
which completes the proof of the correctness of Definition 5.1. □
Lemma 5.2
Let \({N \ge1}\). Then:
-
(i)
\(\beta_{N}\) is a quasi-homogeneous of degree 2N on \({[0,R]}\);
-
(ii)
\({\beta_{N}(t) = \phi_{N}(t) \psi_{N}(t)}\) for every \({t \in[0,R]}\);
-
(iii)
\({\beta_{N+1}(t) \le\beta_{N}(t)}\) for every \({t \in[0,R]}\);
-
(iv)
\({\psi_{N + 1}(t) \ge\psi_{N}(t)}\) for every \({t \in[0,R]}\).
Proof
The function \({\beta_{N}}\) can be presented in the form \({\beta_{N}(t) = t^{2} \phi_{N-1}(t) \Phi(t)}\), where \(\Phi(t) = a / (1 - t -a t^{2} \phi_{N-1}(t))\). Therefore, \({\beta_{N}}\) is quasi-homogeneous of degree 2N on \({[0, R]}\) since it is a product of three quasi-homogeneous functions on \({[0, R]}\) of degree 2, \({2N-2}\), and 0. From the definitions of the functions \(\phi_{N}\), \(\psi_{N}\), and \(\beta _{N}\), we get
Claim (iii) follows from Lemma 4.3(iii) and (5.4). Claim (iv) follows from (iii) and (5.5). □
Lemma 5.3
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) which splits over \(\mathbb{K}\), \({\xi\in \mathbb{K}^{n}}\) a root vector of f, \({N \ge1}\), and \({1 \le p \le\infty}\). Suppose \({x \in \mathbb{K}^{n}}\) is a vector with distinct components such that
where the function \({E \colon\mathcal{D} \to \mathbb{R}_{+}}\) is defined by (5.1) and \({a = (n - 1) ^{1/q}}\). Then f has only simple zeros in \(\mathbb{K}\),
Besides, the vector \(T^{(N)}(x)\) has pairwise distinct components.
Proof
It follows from (5.7) and \(R < 1/2\) that \({E(x) < 1/2}\). Then it follows from Lemma 3.2 that the vector ξ has distinct components, which means that f has only simple zeros in \(\mathbb{K}\). We divide the proof into two steps.
Step 1. In this step, we prove \({x \in D_{N}}\) and the first inequality in (5.8) by induction on N. If \({N = 1}\), the proof of the claims can be found in [11]. Assume that \({x \in D_{N}}\) and the first inequality in (5.8) hold for some \({N \ge1}\).
First we show that \({x \in D_{N + 1}}\), i.e. \({x \mathbin{\#} T^{(N)}(x)}\) and (4.8) holds for every \({i \in I_{n}}\). It follows from the first inequality in (5.8) that (3.5) holds with \({v = x}\), \({u = T^{(N)}(x)}\), and \({\alpha= 1}\). Therefore by Lemma 3.4, (5.7) and \({R < 1/2}\), we obtain
for every \({j \ne i}\). Consequently, \({x \mathbin{\#} T^{(N)}(x)}\). It remains to prove (4.8) for every \({i \in I_{n}}\). Let \({i \in I_{n}}\) be fixed. We shall consider only the non-trivial case \({f(x_{i}) \ne0}\). In this case (4.8) is equivalent to (4.12). On the other hand, it follows from Lemma 4.4(i) that (4.12) is equivalent to \({\sigma_{i} \ne1}\), where \({\sigma_{i}}\) is defined by (4.6). By Lemma 3.1 with \({u = \xi}\) and \({v = x}\) and (5.7), we get
for every \({j \ne i}\). Hence, we obtain \({x \mathbin{\#} \xi}\). From the induction hypothesis, we get
Combining the triangle inequality in \(\mathbb{K}\), (5.10), (5.9) and (5.11), we obtain
which, using Hölder’s inequality, yields
From this and (5.7), we deduce
which yields \({\sigma_{i} \ne1}\), and so (4.12) holds. Thus we prove that \(x \in D_{N + 1}\).
Now we have to prove that the first inequality in (5.8) is satisfied for \({N + 1}\), which is equivalent to
Let \({i \in I_{n}}\) be fixed. If \({x_{i} = \xi_{i}}\), then \({T^{(N + 1)}_{i}(x) = \xi_{i}}\) and the inequality (5.13) becomes an equality. Suppose \({x_{i} \ne\xi_{i}}\). It follows from Lemma 4.4(ii), the triangle inequality in \(\mathbb{K}\), and the estimate (5.12) that
From this inequality, Lemma 5.2(ii), \({\psi _{N}(t) \le1}\), (5.3) and Lemma 5.2(iv), we obtain
which proves (5.13). This completes the induction.
Step 2. In this step we prove the second inequality in (5.8) and that \(T^{(N)}(x)\) has distinct components. First inequality in (5.8) allow us to apply Lemma 3.5 with \({u = T^{(N)}(x)}\), \({v = x}\), and \({\alpha= \beta_{N}(E(x))}\). By Lemma 3.5 and (5.5), we deduce
By taking the minimum over all \({j \in I_{n}}\) such that \({j \ne i}\), we obtain
which implies that \(T^{(N)}(x)\) has distinct components. It follows from (5.11), (5.14), and Lemma 5.2(ii) that
By taking the p-norm, we obtain
which proves the second inequality in (5.8). This completes the proof. □
Now we are able to state the main result of this section. In the case when \({N = 1}\) and \({p = \infty}\) this result reduces to Theorem 1.2.
Theorem 5.4
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) which splits over \(\mathbb{K}\), \({\xi\in \mathbb{K}^{n}}\) be a root vector of f, \({N \ge1}\), and \({1 \le p \le\infty}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess with distinct components such that
where the function E is defined by (5.1) and \({a = (n - 1) ^{1/q}}\). Then f has only simple zeros in \(\mathbb{K}\), and the Ehrlich-type iteration (1.18) is well defined and converges to ξ with error estimates
for all \({k \ge0}\), where \({\lambda= \phi_{N}(E(x^{(0)}))}\), \({\theta= \psi_{N}(E(x^{(0)}))}\). Moreover, the method is convergent with order \({2N + 1}\) provided that \({E(x^{(0)}) < R}\).
Proof
We apply Theorem 2.8 to the iteration function \({T^{(N)} \colon D_{N} \subset \mathbb{K}^{n} \to \mathbb{K}^{n}}\) together with the function \({E \colon D_{N} \to \mathbb{R}_{+}}\) defined by (5.1).
It follows from Lemma 5.3 and Lemma 4.3(v) that E is a function of the initial conditions of \({T^{(N)}}\) with gauge function \(\varphi_{N}\) of order \({r = 2 N + 1}\) on the interval \({J = [0, R]}\).
From Lemma 5.3, we see that \({T^{(N)}}\) is an iterated contraction at ξ with respect to E and with control function \({\beta_{N}}\). Also, it is easy to see that the functions \(\beta_{N}\), \(\phi_{N}\), \(\psi _{N}\), and \(\varphi_{N}\) have the properties (2.5), (2.6) and (2.7).
It follows from Lemma 5.3 that \({x^{(0)} \in D_{N}}\). According to Theorem 2.6 to prove that \({x^{(0)}}\) is an initial point of \({T^{(N)}}\) it is sufficient to prove that
From \({x \in D_{N}}\), we have \({T^{(N)}(x) \in \mathbb{K}^{n}}\). By Lemma 5.3, \({T^{(N)}(x)}\) has distinct components and \({E(T^{(N)}(x)) \le\varphi_{N}(E(x))}\). The last inequality yields \({E(T^{(N)}(x)) \in J}\) since \({\varphi_{N} \colon J \to J}\) and \({E(x) \in J}\). Thus we have both \({T^{(N)}(x) \in\mathcal{D}}\) and \({E(T^{(N)}(x)) \in J}\). Applying Lemma 5.3 to the vector \({T^{(N)}(x)}\), we get \({T^{(N)}(x) \in D_{N}}\), which proves (5.17). Therefore, \({x^{(0)}}\) is an initial point of \({T^{(N)}}\).
Now the statement of Theorem 5.4 follows from Theorem 2.8. □
6 Semilocal convergence theorem
In this section we establish semilocal convergence theorems for Ehrlich-type methods (1.18) for finding all zeros of a polynomial simultaneously. We study the convergence of these methods with respect to the function of the initial conditions \({E_{f} \colon\mathcal{D} \to \mathbb{R}_{+}}\) defined by
Recently Proinov [22] has shown that there is a relationship between local and semilocal theorems for simultaneous root-finding methods. It turns out that from any local convergence theorem for a simultaneous method one can obtain as a consequence a semilocal theorem for the same method. In particular, from Theorem 5.4 we can obtain a semilocal convergence theorem for Ehrlich-type methods (1.18) under computationally verifiable initial conditions. For this purpose we need the following result.
Theorem 6.1
(Proinov [22])
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\). Suppose \({x \in \mathbb{K}^{n}}\) is an initial guess with distinct components such that
for some \({1 \le p \le\infty}\) and \({0 < R \le1/(1 + \sqrt{a})}\), where \({a = (n - 1) ^{1/q}}\). In the case \({n = 2}\) and \({p = \infty}\) we assume that inequality in (6.2) is strict. Then f has only simple zeros in \(\mathbb{K}\), and there exists a root vector \({\xi\in \mathbb{K}^{n}}\) of f such that
where the real function α is defined by
If the inequality (6.2) is strict, then the second inequality in (6.3) is strict too.
Now, we are ready to state and prove the main result of this paper.
Theorem 6.2
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\), \({N \ge 1}\), \({1 \le p \le\infty}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess with distinct components such that
where the function \({E_{f}}\) is defined by (6.1) and \({a = (n - 1) ^{1/q}}\). Then f has only simple zeros in \(\mathbb{K}\), and the Ehrlich-type iteration (1.18) is well defined and converges to a root vector ξ of f with order of convergence \({2N + 1}\) and with an a posteriori error estimate
for all \({k \ge0}\) such that \({E_{f}(x^{(k)}) < 8 / (3 + \sqrt{1 + 8 a})^{2}}\), where the function α is defined by (6.4).
Proof
Let us define R by (5.2). It is easy to calculate that \({R < 1 / (1 + \sqrt{a})}\) and
Therefore, (6.5) can be written in the form
Then it follows from Theorem 6.1 that f has only simple zeros in \(\mathbb{K}\) and there exists a root vector \({\xi\in \mathbb{K}^{n}}\) of f such that
Now Theorem 5.4 implies that the Ehrlich-type iteration (1.18) converges to ξ with order of convergence \({2N + 1}\). It remains to prove the error estimate (6.6). Suppose that for some \({k \ge0}\),
Then it follows from Theorem 6.1 that there exists a root vector \({\eta\in \mathbb{K}^{n}}\) of f such that
From the second inequality in (6.8) and Theorem 5.4, we conclude that the Ehrlich-type iteration (1.18) converges to η. By the uniqueness of the limit, we get \({\eta= \xi}\). Therefore, the error estimate (6.6) follows from the first inequality in (6.8). This completes the proof. □
Setting \({p = \infty}\) in Theorem 6.2, we obtain the following result.
Corollary 6.3
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) and \({N \ge1}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess with distinct components such that
Then f has only simple zeros in \(\mathbb{K}\) and the Ehrlich-type iteration (1.18) is well defined and converges to a root vector ξ of f with order of convergence \({2N + 1}\) and with error estimate (6.6) for \({p = \infty}\).
Setting \({p = 1}\) in Theorem 6.2 we obtain the following result.
Corollary 6.4
Let \({f \in \mathbb{K}[z]}\) be a polynomial of degree \({n \ge2}\) and \({N \ge1}\). Suppose \({x^{(0)} \in \mathbb{K}^{n}}\) is an initial guess with distinct components such that
Then f has only simple zeros in \(\mathbb{K}\) and the Ehrlich-type iteration (1.18) is well defined and converges with order \({2N + 1}\) to a root vector ξ of f with error estimate (6.6) for \({p = 1}\).
7 Numerical examples
In this section, we present several numerical examples to show some applications of Theorem 6.2. Let \({f \in \mathbb{C}[z]}\) be a polynomial of degree \({n \ge2}\) and let \(x^{(0)} \in \mathbb{C}^{n}\) be an initial guess. We show that Theorem 6.2 can be used:
-
to prove numerically that f has only simple zeros;
-
to prove numerically that Nth Ehrlich-type iteration (1.18) starting from \({x^{(0)}}\) is well defined and converges with order \({2N + 1}\) to a root vector of f;
-
to guarantee the desired accuracy when calculating the roots of f via the Nth Ehrlich-type method.
In the examples below, we use the function of the initial conditions \({E_{f} \colon\mathcal{D} \to \mathbb{R}_{+}}\) defined by
where \(W_{f}\) is the Weierstrass correction defined by (1.6). We consider only the case \({p = \infty}\), since the other cases are similar.
Also, we use the real function α defined by
It follows from Theorem 6.2 that if there exists an integer \({m \ge0}\) such that
then f has only simple zeros and the Ehrlich-type iteration (1.18) is well defined and converges to a root vector ξ of f with order of convergence \({2N + 1}\). Besides, for all \({k \ge m}\) such that
the following a posteriori error estimate holds:
In the examples, we apply the Ehrlich-type methods (1.18) for some \({N \ge1}\) using the following stopping criterion:
For given N we calculate the smallest \(m \ge0\) which satisfies the convergence condition (7.3), the smallest \(k \ge m\) for which the stopping criterion (7.6) is satisfied, as well as the value of \(\varepsilon_{k}\) for the last k.
In Table 2 the values of iterations are given to 15 decimal places. The values of other quantities (\(\mathscr{R}\), \(E_{f}(x^{(m)})\), etc.) are given to six decimal places.
Numerical calculations are made using the software package Mathematica [23].
Example 7.1
We consider the polynomial
and the initial guess
which are taken from Zhang et al. [24]. We have \({\mathscr{R} = 0.125}\) and \({E(x^{(0)}) = 0.506619}\). The results for this example are presented in Table 1. For example, we can see that for \({N = 10}\) at the first iteration we have proved that the Ehrlich-type method converges with order of convergence 21 and that at the second iteration we have calculated the zeros f with accuracy less than 10−127. Moreover, at the next iteration we obtain the zeros of f with accuracy less than 10−2,682. Also, we can see that for \({N = 100}\) at the second iteration we have obtained the zeros of f with accuracy less than 10−11,450.
In Table 2, we present numerical results for Example 7.1 in the case \({N = 10}\).
Example 7.2
We consider the polynomial
and Aberth’s initial approximation \({x^{(0)} \in \mathbb{C}^{n}}\) given by (see Aberth [8] and Petković et al. [25]):
where \({a_{1} = 1}\), \({r_{0} = 2}\), and \({n = 15}\). We have \({\mathscr{R} = 0.043061}\) and \({E(x^{(0)}) = 0.179999}\). The results for this example are presented in Table 3. For example, we can see that for \({N = 30}\) at the third iteration we have obtained the zeros of f with accuracy less than 10−248. Moreover, at the next iteration we get the zeros of f with accuracy less than 10−15,105.
Example 7.3
We consider the Wilkinson polynomial [26]
and Aberth’s initial approximation (7.7) with \({a_{1} = - 120}\), \({r_{0} = 20}\), and \({n = 20}\). We have \({\mathscr{R} = 0.033867}\) and \({E(x^{(0)}) = 0.344409}\). The results for Example 7.3 are shown in Table 4. For example, for \({N = 30}\) at the seventh iteration, we get the zeros of f with accuracy less than 10−13,776.
In Figure 1, we present the trajectories of approximations generated by the method (1.18) for \({N = 30}\) after 6 iterations.
Example 7.4
We consider the polynomial
In this example we use Aberth’s initial approximation (7.7) with \({a_{1} = 0}\), \({r_{0} = 2}\), and \({n = 40}\). We have \({\mathscr{R} = 0.018685}\), \({E(x^{(0)}) = 0.159318}\). The results for Example 7.4 can be seen in Table 5.
In Figure 2, we present the trajectories of approximations generated by the method (1.18) for \({N = 30}\) after 5 iterations.
References
Proinov, PD: A unified theory of cone metric spaces and its applications to the fixed point theory. Fixed Point Theory Appl. 2013, Article ID 103 (2013)
Sendov, B, Andreev, A, Kjurkchiev, N: Numerical Solution of Polynomial Equations. In: Handbook of Numerical Analysis, vol. III, pp. 625-778. Elsevier, Amsterdam (1994)
Kyurkchiev, NV: Initial Approximations and Root Finding Methods. Mathematical Research, vol. 104. Wiley, Berlin (1998)
McNamee, JM: Numerical Methods for Roots of Polynomials - Part I. Studies in Computational Mathematics, vol. 14. Elsevier, Amsterdam (2007)
Petković, M: Point Estimation of Root Finding Methods. Lecture Notes in Mathematics, vol. 1933. Springer, Berlin (2008)
Weierstrass, K: Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen. Sitzungsber. Königl. Preuss. Akad. Wiss. Berlin II, 1085-1101 (1891)
Ehrlich, LW: A modified Newton method for polynomials. Commun. ACM 10(2), 107-108 (1967)
Aberth, O: Iteration methods for finding all zeros of a polynomial simultaneously. Math. Comput. 27, 339-344 (1973)
Börsch-Supan, W: Residuenabschatzung für Polynom-Nullstellen mittels Lagrange-Interpolation. Numer. Math. 14, 287-296 (1970)
Werner, W: On the simultaneous determination of polynomial roots. In: Iterative Solution of Nonlinear Systems of Equations. Lecture Notes Math., vol. 953, pp. 188-202. Springer, Berlin (1982)
Proinov, PD: On the local convergence of the Ehrlich method for numerical computation of polynomial zeros. Calcolo (2015). doi:10.1007/s10092-015-0155-y
Kyurkchiev, NV, Taschev, S: A method for simultaneous determination of all roots of algebraic polynomials. C. R. Acad. Bulg. Sci. 34, 1053-1055 (1981) (in Russian)
Tashev, S, Kyurkchiev, N: Certain modifications of Newton’s method for the approximate solution of algebraic equations. Serdica Math. J. 9, 67-73 (1983) (in Russian)
Wang, DR, Zhao, FG: Complexity analysis of a process for simultaneously obtaining all zeros of polynomials. Computing 43, 187-197 (1989)
Tilli, P: Convergence conditions of some methods for the simultaneous computation of polynomial zeros. Calcolo 35, 3-15 (1998)
Kjurkchiev, NV, Andreev, A: Ehrlich’s methods with a raised speed of convergence. Serdica Math. J. 13, 52-57 (1987)
Proinov, PD: General local convergence theory for a class of iterative processes and its applications to Newton’s method. J. Complex. 25, 38-62 (2009)
Proinov, PD: New general convergence theory for iterative processes and its applications to Newton-Kantorovich type theorems. J. Complex. 26, 3-42 (2010)
Proinov, PD: General convergence theorems for iterative processes and applications to the Weierstrass root-finding method. J. Complex. (2015, accepted). arXiv:1503.05243
Proinov, PD, Cholakov, SI: Semilocal convergence of Chebyshev-like root-finding method for simultaneous approximation of polynomial zeros. Appl. Math. Comput. 236, 669-682 (2014)
Proinov, PD, Vasileva, MT: On the convergence of a family of Weierstrass-type root-finding methods. C. R. Acad. Bulg. Sci. 68, 697-704 (2015)
Proinov, PD: Relationships between different types of initial conditions for simultaneous root finding methods. Appl. Math. Lett. 52, 102-111 (2016)
Wolfram Mathematica, version 7. Wolfram Research, Inc., Champaign, Illinois, USA (2009)
Zhang, X, Peng, H, Hu, G: A high order iteration formula for the simultaneous inclusion of polynomial zeros. Appl. Math. Comput. 179, 545-552 (2006)
Petković, M, Ilić, S, Petković, I: A posteriori error bound methods for the inclusion of polynomial zeros. J. Comput. Appl. Math. 208, 316-330 (2007)
Wilkinson, JH: Rounding Errors in Algebraic Processes. Prentice Hall, New York (1963)
Acknowledgements
This research is supported by the project NI15-FMI-004 of Plovdiv University.
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
Both authors contributed equally and significantly in writing this paper. Both authors read and approved the final manuscript.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Proinov, P.D., Vasileva, M.T. On the convergence of high-order Ehrlich-type iterative methods for approximating all zeros of a polynomial simultaneously. J Inequal Appl 2015, 336 (2015). https://doi.org/10.1186/s13660-015-0855-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13660-015-0855-5