Weierstrass formula and zero-finding methods

Summary. Classical Weierstrass' formula [29] has been often the subject of investigation of many authors. In this paper we give some further applications of this formula for finding the zeros of polynomials and analytic functions. We are concerned with the problems of localization of polynomial zeros and the construction of iterative methods for the simultaneous approximation and inclusion of these zeros. Conditions for the safe convergence of Weierstrass' method, depending only on initial approximations, are given. In particular, we study polynomials with interval coefficients. Using an interval version of Weierstrass' method enclosures in the form of disks for the complex-valued set containing all zeros of a polynomial with varying coefficients are obtained. We also present Weierstrass-like algorithm for approximating, simultaneously, all zeros of a class of analytic functions in a given closed region. To demonstrate the proposed algorithms, three numerical examples are included. Received September 13, 1993     

On the convergence of Wang-Zheng's method

The choice of initial conditions ensuring safe convergence of the implemented iterative method is one of the most important problems in solving polynomial equations. These conditions should depend only on the coefficients of a given polynomial P and initial approximations to the zeros of P. In this paper we state initial conditions with the described properties for the Wang-Zheng method for the simultaneous approximation of all zeros of P. The safe convergence and the fourth-order convergence of this method are proved.     

Relationships between different types of initial conditions for simultaneous root finding methods

The construction of initial conditions of an iterative method is one of the most important problems in solving nonlinear equations. In this paper, we obtain relationships between different types of initial conditions that guarantee the convergence of iterative methods for simultaneously finding all zeros of a polynomial. In particular, we show that any local convergence theorem for a simultaneous method can be converted into a convergence theorem with computationally verifiable initial conditions which is of practical importance. Thus, we propose a new approach for obtaining semilocal convergence results for simultaneous methods via local convergence results.     

A new simultaneous method of fourth order for finding complex zeros in circular interval arithmetic

Starting from disjoint disks which contain polynomial complex zeros, the new iterative interval method for simultaneous finding of inclusive disks for complex zeros is formulated. The convergence theorem and the conditions for convergence are considered, and the convergence is shown to be fourth. Numerical examples are included.     

Efficient methods for the inclusion of polynomial zeros

Using a suitable zero-relation and the inclusion isotonicity property, new interval iterative methods for the simultaneous inclusion of simple complex zeros of a polynomial are derived. These methods produce disks in the complex plane that contain the polynomial zeros in each iteration, providing in this manner an information about upper error bounds of approximations. Starting from the basic method of the fourth order, two accelerated methods with Newton’s and Halley’s corrections, having the order of convergence five and six respectively, are constructed. This increase of the convergence rate is obtained without any additional operations, which means that the methods with corrections are very efficient. The convergence analysis of the basic method and the methods with corrections is performed under computationally verifiable initial conditions, which is of practical importance. Two numerical examples are presented to demonstrate the convergence behavior of the proposed interval methods.     

Safe convergence of simultaneous methods for polynomial zeros

The theory of point estimation treating the initial conditions for the safe convergence of iterative processes for the simultaneous determination of polynomial zeros is considered. A general approach which makes use of corrections appearing in iterative formulas is given and demonstrated in the case of three well known methods without derivatives and based on Weierstrass’ corrections. The established convergence conditions are of practical importance since they depend only on available data: coefficients of a polynomial and initial approximations to the zeros. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the new fourth-order methods for the simultaneous approximation of polynomial zeros

A new iterative method of the fourth-order for the simultaneous determination of polynomial zeros is proposed. This method is based on a suitable zero-relation derived from the fourth-order method for a single zero belonging to the Schröder basic sequence. One of the most important problems in solving polynomial equations, the construction of initial conditions that enable both guaranteed and fast convergence, is studied in detail for the proposed method. These conditions are computationally verifiable since they depend only on initial approximations, the polynomial coefficients and the polynomial degree, which is of practical importance. The construction of improved methods in ordinary complex arithmetic and complex circular arithmetic is discussed. Finally, numerical examples and the comparison with existing fourth-order methods are given.     

On the convergence of the sequences of Gerschgorin-like disks

Carstensen’s results from 1991, connected with Gerschgorin’s disks, are used to establish a theorem concerning the localization of polynomial zeros and to derive an a posteriori error bound method. The presented quasi-interval method possesses useful property of inclusion methods to produce disks containing all simple zeros of a polynomial. The centers of these disks behave as approximations generated by a cubic derivative free method where the use of quantities already calculated in the previous iterative step decreases the computational cost. We state initial convergence conditions that guarantee the convergence of error bound method and prove that the method has the order of convergence three. Initial conditions are computationally verifiable since they depend only on the polynomial coefficients, its degree and initial approximations. Some computational aspects and the possibility of implementation on parallel computers are considered, including two numerical examples.In honor of Professor Richard S. Varga.     

A posteriori error bound methods for the inclusion of polynomial zeros

Using Carstensen's results from 1991 we state a theorem concerning the localization of polynomial zeros and derive two a posteriori error bound methods with the convergence order 3 and 4. These methods possess useful property of inclusion methods to produce disks containing all simple zeros of a polynomial. We establish computationally verifiable initial conditions that guarantee the convergence of these methods. Some computational aspects and the possibility of implementation on parallel computers are considered, including two numerical examples. A comparison of a posteriori error bound methods with the corresponding circular interval methods, regarding the computational costs and sizes of produced inclusion disks, were given.     

An efficient higher order family of root finders

A one parameter family of iterative methods for the simultaneous approximation of simple complex zeros of a polynomial, based on a cubically convergent Hansen–Patrick's family, is studied. We show that the convergence of the basic family of the fourth order can be increased to five and six using Newton's and Halley's corrections, respectively. Since these corrections use the already calculated values, the computational efficiency of the accelerated methods is significantly increased. Further acceleration is achieved by applying the Gauss–Seidel approach (single-step mode). One of the most important problems in solving nonlinear equations, the construction of initial conditions which provide both the guaranteed and fast convergence, is considered for the proposed accelerated family. These conditions are computationally verifiable; they depend only on the polynomial coefficients, its degree and initial approximations, which is of practical importance. Some modifications of the considered family, providing the computation of multiple zeros of polynomials and simple zeros of a wide class of analytic functions, are also studied. Numerical examples demonstrate the convergence properties of the presented family of root-finding methods.     

Point estimation of simultaneous methods for solving polynomial equations: A survey (II)

The construction of computationally verifiable initial conditions which provide both the guaranteed and fast convergence of the numerical root-finding algorithm is one of the most important problems in solving nonlinear equations. Smale's “point estimation theory” from 1981 was a great advance in this topic; it treats convergence conditions and the domain of convergence in solving an equation f(z)=0$f(z)=0$ using only the information of f   at the initial point _z0$z_0$. The study of a general problem of the construction of initial conditions of practical interest providing guaranteed convergence is very difficult, even in the case of algebraic polynomials. In the light of Smale's point estimation theory, an efficient approach based on some results concerning localization of polynomial zeros and convergent sequences is applied in this paper to iterative methods for the simultaneous determination of simple zeros of polynomials. We state new, improved initial conditions which provide the guaranteed convergence of frequently used simultaneous methods for solving algebraic equations: Ehrlich–Aberth's method, Ehrlich–Aberth's method with Newton's correction, Börsch-Supan's method with Weierstrass’ correction and Halley-like (or Wang–Zheng) method. The introduced concept offers not only a clear insight into the convergence analysis of sequences generated by the considered methods, but also explicitly gives their order of convergence. The stated initial conditions are of significant practical importance since they are computationally verifiable; they depend only on the coefficients of a given polynomial, its degree n and initial approximations to polynomial zeros.     

A new semilocal convergence theorem for the Weierstrass method for finding zeros of a polynomial simultaneously

In this paper we study the convergence of the famous Weierstrass method for simultaneous approximation of polynomial zeros over a complete normed field. We present a new semilocal convergence theorem for the Weierstrass method under a new type of initial conditions. Our result is obtained by combining ideas of Weierstrass (1891) and Proinov (2010). A priori and a posteriori error estimates are also provided under the new initial conditions.     

A note on the improved derivative free root-solvers

Using a fixed point relation of the square-root type and the basic fourth-order method, improved methods of fifth and sixth order for the simultaneous determination of simple zeros of a polynomial are obtained. An increase in convergence is achieved without additional numerical operations, which points to high computational efficiency of the accelerated methods. The main aim of this work is the convergence analysis of improved simultaneous methods given under computationally verifiable initial conditions in the spirit of Smale’s point estimation theory.     

On an iterative method for simultaneous inclusion of polynomial complex zeros

Starting from disjoint discs which contain polynomial complex zeros, the iterative interval method of the third order for the simultaneous finding inclusive discs for complex zeros is formulated. The Lagrangean interpolation formula and complex circular arithmetic are used. The convergence theorem and the conditions for convergence are considered. The proposed method has been applied for solving an algebraic equation.     

A unified semilocal convergence analysis of a family of iterative algorithms for computing all zeros of a polynomial simultaneously

In this paper, we first present a family of iterative algorithms for simultaneous determination of all zeros of a polynomial. This family contains two well-known algorithms: Dochev-Byrnev’s method and Ehrlich’s method. Second, using Proinov’s approach to studying convergence of iterative methods for polynomial zeros, we provide a semilocal convergence theorem that unifies the results of Proinov (Appl. Math. Comput. 284: 102–114, 2016) for Dochev-Byrnev’s and Ehrlich’s methods.     

一种求多项式重零点的并行圆盘迭代法

本文给出一种三阶收敛的同时求多项式重零点的圆盘迭代法 ,并分析该法收敛的初始值条件 ,它改进了文献 [2 ]的结果 .     

Improvement of a convergence condition for the Durand-Kerner iteration

The Durand-Kerner iteration is a well-known simultaneous method for approximation of (simple) zeros of a polynomial. By relating Weierstrass' correction and the minimal distance between approximations practical conditions for convergence have been obtained. These conditions also ensure the existence of isolating discs for the polynomial roots, i.e. each iteration step gives a refined set of inclusion discs. In this paper refined conditions of convergence are given.     

An iteration formula for the simultaneous determination of the zeros of a polynomial

The need for efficient algorithms for determining zeros of given polynomials has been stressed in many applications. In this paper we give a new cubic iteration method for determining simultaneously all the zeros of a polynomial (assumed distinct) starting with ‘reasonably close’ initial approximations (also assumed distinct).The polynomial is expressed as an expansion in terms of the starting and their correction terms.A formula which gives cubic convergence without involving second derivatives is derived by retaining terms up to second order of the expansion in the correction terms.Numerical evidence is given to illustrate the cubic convergence of the process.     

On quadratic-like convergence of the means for two methods for simultaneous rootfinding of polynomials

Durand-Kerner's method for simultaneous rootfinding of a polynomial is locally second order convergent if all the zeros are simple. If this condition is violated numerical experiences still show linear convergence. For this case of multiple roots, Fraigniaud [4] proves that the means of clustering approximants for a multiple root is a better approximant for the zero and called this Quadratic-Like-Convergence of the Means.This note gives a new proof and a refinement of this property. The proof is based on the related Grau's method for simultaneous factoring of a polynomial. A similar property of some coefficients of the third order method due to Börsch-Supan, Maehly, Ehrlich, Aberth and others is proved.     

A new higher-order family of inclusion zero-finding methods

Starting from a suitable fixed point relation, a new one-parameter family of iterative methods for the simultaneous inclusion of complex zeros in circular complex arithmetic is constructed. It is proved that the order of convergence of this family is four. The convergence analysis is performed under computationally verifiable initial conditions. An approach for the construction of accelerated methods with negligible number of additional operations is discussed. To demonstrate convergence properties of the proposed family of methods, two numerical examples results are given.