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.     

A higher order family for the simultaneous inclusion of multiple zeros of polynomials

Starting from a suitable fixed point relation, a new family of iterative methods for the simultaneous inclusion of multiple complex zeros in circular complex arithmetic is constructed. The order of convergence of the basic family is four. Using Newtons and Halleys corrections, we obtain families with improved convergence. Faster convergence of accelerated methods is attained with only few additional numerical operations, which provides a high computational efficiency of these methods. Convergence analysis of the presented methods and numerical results are given. AMS subject classification 65H05, 65G20, 30C15     

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.     

A note on the interlacing of zeros and orthogonality

Let be a sequence of monic polynomials with deg(t_n)=n such that, for each n∈N, the zeros of t_n are real and simple and t_n and t_n+1 have no common zeros. We discuss the connection between the orthogonality of the sequence, the positivity of a certain ratio, and the interlacing of the zeros of t_n and t_n+1 for n≥1, n∈N.     

Comments on some recent methods for the simultaneous determination of polynomial zeros

In this note we give some comments on the recent results concerning a simultaneous method of the fourth-order for finding complex zeros in circular interval arithmetic. The main discussion is directed to a rediscovered iterative formula and its modification, presented recently in (Sun and Kosmol (J. Comput. Appl. Math. 130 (2001) 293)). The presented comments include some critical parts of the papers (Jpn. J. Indust. Appl. Math. 15 (1998) 295) and (Sun and Kosmol, 2001) which treat the same subject.     

On the coefficients of a polynomial with restricted zeros

LetP(Z)=αn Zn + αn-1Zn-1 +…+α0 be a complex polynomial of degree n. There is a close connection between the coefficients and the zeros of P(z). In this paper we prove some sharp inequalities concerning the coeffi-cients of the polynomial P(z) with restricted zeros. We also establish a sufficient condition for the separation of zeros of P(z).     

On a simultaneous method of Newton-Weierstrass’ type for finding all zeros of a polynomial

Combining a suitable two-point iterative method for solving nonlinear equations and Weierstrass’ correction, a new iterative method for simultaneous finding all zeros of a polynomial is derived. It is proved that the proposed method possesses a cubic convergence locally. Numerical examples demonstrate a good convergence behavior of this method in a global sense. It is shown that its computational efficiency is higher than the existing derivative-free methods.     

Bounds on the moduli of polynomial zeros

In this paper, we develop methods for establishing improved bounds on the moduli of the zeros of complex and real polynomials. Specific (lacunary) as well as arbitrary polynomials are considered. The methods are applied to specific polynomials by way of example. Finally, we evaluate the quality of some bounds numerically.     

A sufficient condition for a polynomial to be stable

A real polynomial is called Hurwitz (stable) if all its zeros have negative real parts. For a given n∈N we find the smallest possible constant dn>0 such that if the coefficients of F(z)=a₀+a₁z+?+anzn are positive and satisfy the inequalities akak+1>dnak−1ak+2 for k=1,2,…,n−2, then F(z) is Hurwitz.     

On the zeros of a polynomial and its derivatives

If is univariate polynomial with complex coefficients having all its zeros inside the closed unit disk, then the Gauss-Lucas theorem states that all zeros of lie in the same disk. We study the following question: what is the maximum distance from the arithmetic mean of all zeros of to a nearest zero of ? We obtain bounds for this distance depending on degree. We also show that this distance is equal to for polynomials of degree 3 and polynomials with real zeros.

     

Numerical computation of polynomial zeros by means of Aberth's method

An algorithm for computing polynomial zeros, based on Aberth's method, is presented. The starting approximations are chosen by means of a suitable application of Rouché's theorem. More precisely, an integerq 1 and a set of annuliA _i,i=1,...,q, in the complex plane, are determined together with the numberk _i of zeros of the polynomial contained in each annulusA _i. As starting approximations we choosek _i complex numbers lying on a suitable circle contained in the annulusA _i, fori=1,...,q. The computation of Newton's correction is performed in such a way that overflow situations are removed. A suitable stop condition, based on a rigorous backward rounding error analysis, guarantees that the computed approximations are the exact zeros of a nearby polynomial. This implies the backward stability of our algorithm. We provide a Fortran 77 implementation of the algorithm which is robust against overflow and allows us to deal with polynomials of any degree, not necessarily monic, whose zeros and coefficients are representable as floating point numbers. In all the tests performed with more than 1000 polynomials having degrees from 10 up to 25,600 and randomly generated coefficients, the Fortran 77 implementation of our algorithm computed approximations to all the zeros within the relative precision allowed by the classical conditioning theorems with 11.1 average iterations. In the worst case the number of iterations needed has been at most 17. Comparisons with available public domain software and with the algorithm PA16AD of Harwell are performed and show the effectiveness of our approach. A multiprecision implementation in MATHEMATICA is presented together with the results of the numerical tests performed.Work performed under the support of the ESPRIT BRA project 6846 POSSO (POlynomial System SOlving).     

A note on some quadrature based three-step iterative methods for non-linear equations

In a recent paper [N.A. Mir, T. Zaman, Some quadrature based three-step iterative methods for non-linear equations, Appl. Math. Comput. 193 (2007) 366-373], some new three-step iterative methods for non-linear equations have been proposed. In this note, we show that the Algorithm 2.2 and Algorithm 2.3 given by the authors have twelfth-order and ninth-order convergence respectively, not seventh-order one as claimed in their work.     

A note on exponent of convergence of zeros of entire functions

If f(z) is an entire function with ρ ₁ > 0 as its exponent of convergence of zeros and if 0 ≤ α < ρ ₁, then we prove the existence of entire functions each having α as its exponent of convergence of zeros.      

New higher-order methods for the simultaneous inclusion of polynomial zeros

Higher-order methods for the simultaneous inclusion of complex zeros of algebraic polynomials are presented in parallel (total-step) and serial (single-step) versions. If the multiplicities of each zeros are given in advance, the proposed methods can be extended for multiple zeros using appropriate corrections. These methods are constructed on the basis of the zero-relation of Gargantini’s type, the inclusion isotonicity property and suitable corrections that appear in two-point methods of the fourth order for solving nonlinear equations. It is proved that the order of convergence of the proposed methods is at least six. The computational efficiency of the new methods is very high since the acceleration of convergence order from 3 (basic methods) to 6 (new methods) is attained using only n polynomial evaluations per iteration. Computational efficiency of the considered methods is studied in detail and two numerical examples are given to demonstrate the convergence behavior of the proposed methods.     

On some improvements of square root iteration for polynomial complex zeros

Using Newton's and Halley's corrections, some modifications of the simultaneous method for finding polynomial complex zeros, based on square root iteration, are obtained. The convergence order of the proposed methods is five and six respectively. Further improvements of these methods are performed by applying the Gauss—Seidel approach. The lower bounds of the R-order of convergence and the convergence conditions for the accelerated (single-step) methods are given. Faster convergence is attained without additional calculations. The considered iterative procedures are illustrated numerically in the example of an algebraic equation.     

Modified Newton method in circular interval arithmetic

The modified Newton method for multiple roots is organized in an interval method to include simultaneously the distinct roots of a given polynomialP in complex circular interval arithmetic. A condition on the starting disks which ensures convergence is given, and convergence is shown to be quadratic. As a consequence, a simple parallel algorithm to approach all the distinct roots ofP is derived from the modified Newton method.The research reported in this paper has been made possible through the support and the sponsorship of the Italian Government through the Ministero per l'Universitá e la Ricerca Scientifica under Contract MURST 60%, 1990 at the Universitá di L'Aquila.     

A single oval of Cassini for the zeros of a polynomial

We derive two ovals of Cassini, each containing all the zeros of a polynomial. The computational cost to obtain these ovals is similar to that of the Brauer set for the companion matrix of a polynomial, although they are frequently smaller. Their derivation is based on the Gershgorin set for an appropriate polynomial of the companion matrix.     

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.