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.     

Chebyshev–Halley methods for analytic functions

Two modifications of the family of Chebyshev–Halley methods are given. The first is to improve the rate of convergence to a multiple zero of an analytic function. The second is to find simultaneously all distinct zeros of a polynomial.     

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.     

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.     

同时求多项式全部零点的一族快速并行迭代和区间迭代(Ⅱ)

本文对[1]所提出的一族同时求多项式全部零点的并行迭代兼区间迭代加以进一步的发展。首先,作为纯粹的并行迭代法,我们在§2把每步并行迭代扩展为q个并行子步,这样得到的并行迭代法对只有单零点的多项式的全部零点的收敛是q(p 1)阶的。值得注意的是,在这里阶的提高大大超过了每步计算代价的增加,例如,当q=2时,每步     

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.     

Quadratically Convergent Method for Simultaneously Approaching the Roots of Polynomial Solutions of a Class of Differential Equations: Application to Orthogonal Polynomials

This paper investigates the application of the method introduced by L. Pasquini (1989) for simultaneously approaching the zeros of polynomial solutions to a class of second-order linear homogeneous ordinary differential equations with polynomial coefficients to a particular case in which these polynomial solutions have zeros symmetrically arranged with respect to the origin. The method is based on a family of nonlinear equations which is associated with a given class of differential equations. The roots of the nonlinear equations are related to the roots of the polynomial solutions of differential equations considered. Newton's method is applied to find the roots of these nonlinear equations. In (Pasquini, 1994) the nonsingularity of the roots of these nonlinear equations is studied. In this paper, following the lines in (Pasquini, 1994), the nonsingularity of the roots of these nonlinear equations is studied. More favourable results than the ones in (Pasquini, 1994) are proven in the particular case of polynomial solutions with symmetrical zeros. The method is applied to approximate the roots of Hermite–Sobolev type polynomials and Freud polynomials. A lower bound for the smallest positive root of Hermite–Sobolev type polynomials is given via the nonlinear equation. The quadratic convergence of the method is proven. A comparison with a classical method that uses the Jacobi matrices is carried out. We show that the algorithm derived by the proposed method is sometimes preferable to the classical QR type algorithms for computing the eigenvalues of the Jacobi matrices even if these matrices are real and symmetric.     

On the refinement of Cauchy's theorem and Pellet's theorem

Using the relationship of a polynomial and its associated polynomial, we derived a necessary and sufficient condition for determining all roots of a given polynomial on the circumference of a circle defined by its associated polynomial. By employing the technology of analytic inequality and the theory of distribution of zeros of meromorphic function, we refine two classical results of Cauchy and Pellet about bounds of modules of polynomial zeros. Sufficient conditions are obtained for the polynomial whose Cauchy's bound and Pellet's bounds are strict bounds. The characteristics is given for the polynomial whose Cauchy's bound or Pellet's bounds can be achieved by the modules of zeros of the polynomial.     

The self-validated method for polynomial zeros of high efficiency

The improved iterative method of Newton’s type for the simultaneous inclusion of all simple complex zeros of a polynomial is proposed. The presented convergence analysis, which uses the concept of the R-order of convergence of mutually dependent sequences, shows that the convergence rate of the basic third order method is increased from 3 to 6 using Ostrowski’s corrections. The new inclusion method with Ostrowski’s corrections is more efficient compared to all existing methods belonging to the same class. To demonstrate the convergence properties of the proposed method, two numerical examples are given.     

Zeros of Racah coefficients and the pell equation

The interface between Racah coefficients and mathematics is reviewed and several unsolved problems pointed out. The specific goal of this investigation is to determine zeros of these coefficients. The general polynomial is given whose set of zeros contains all nontrivial zeros of Racah (6j) coefficients [this polynomial is also given for the Wigner-Clebsch-Gordan (3j) coefficients]. Zeros of weight 1 3j- and 6j-coefficients are known to be related to the solutions of classic Diophantine equations. Here it is shown how solutions of the quadratic Diophantine equation known as Pell's equation are related to weight 2 zeros of 3j- and 6j-coefficients. This relation involves transformations of quadratic forms over the integers, the orbit classification of zeros of Pell's equation, and an algorithm for determining numerically the fundamental solutions of Pell's equation. The symbol manipulation program MACSYMA was used extensively to effect various factorings and transformations and to give a proof.The results of this paper were presented in an invited talk by one of us (JDL) at the NSF-CBMS Regional Conference on Special Functions, Physics and Computer Algebra, May 20–24, 1985, Arizona State University, Tempe, AZ.     

Point estimation and some applications to iterative methods

We consider one of the crucial problems in solving polynomial equations concerning the construction of such initial conditions which provide a safe convergence of simultaneous zero-finding methods. In the first part we deal with the localization of polynomial zeros using disks in the complex plane. These disks are used for the construction of initial inclusion disks which, under suitable conditions, provide the convergence of the Gargantini-Henrici interval method. They also play a key role in the convergence analysis of the fourth order Ehrlich-Aberth method with Newton's correction for the simultaneous approximation of all zeros of a polynomial. For this method we state the initial condition which enables the safe convergence. The initial condition is computationally verifiable since it depends only on initial approximations, which is of practical importance.     

Some curious properties and loci problems associated with cubics and other polynomials

The article begins with a well-known property regarding tangent lines to a cubic polynomial that has distinct, real zeros. We were then able to generalize this property to any polynomial with distinct, real zeros. We also considered a certain family of cubics with two fixed zeros and one variable zero, and explored the loci of centroids of triangles associated with the family. Some fascinating connections were observed between the original family of the cubics and the loci of the centroids of these triangles. For example, we were able to prove that the locus of the centroid of certain triangles associated with the family of cubics is another cubic whose zeros are in arithmetic progression. Motivated by this, in the last section of the article, we considered families of cubic polynomials whose zeros are in arithmetic progression, along with the loci of the special points of certain triangles arising from such families. Special points include the centroid, circumcentre, orthocentre, and nine-point centre of the triangles. Throughout the article, we used the computer algebra system, Mathematica®, to form conjectures and facilitate calculations. Mathematica® was also used to create various animations to explore and illustrate many of the results.     

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.     

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.     

Enclosing clusters of zeros of polynomials

Lagrange interpolation and partial fraction expansion can be used to derive a Gerschgorin-type theorem that gives simple and powerful a posteriori error bounds for the zeros of a polynomial if approximations to all zeros are available. Compared to bounds from a corresponding eigenvalue problem, a factor of at least two is gained.The accuracy of the bounds is analyzed, and special attention is given to ensure that the bounds work well not only for single zeros but also for multiple zeros and clusters of close zeros.A Rouché-type theorem is also given, that in many cases reduces the bound even further.     

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 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.     

On the Rate of Overconvergence of the Generalized Eneström-Kakeya Functional for Polynomials

The classical Eneström-Kakeya Theorem, which provides an upper bound for the moduli of zeros of any polynomial with positive coefficients, has been recently extended by Anderson, Saff and Varga to the case of any complex polynomial having no zeros on the ray [0,$+∞$). Their extension is sharp in the sense that, given such a complex polynomials $p_n(z)$ of degree $n≥1$, a sequence of multiplier polynomial can be found for which the Eneström-Kakeya upper bound, applied to the products $Q_{mi}(z)$ · $p_n(z)$, converges, in the limit as $i$ tends to $∞$, to the maximum of the moduli of the zeros of $p_n(z)$. Here, the rate of convergence of these upper bounds is studied. It is shown that the obtained rate of convergence is best possible.     

并行Halley迭代法的修正及其效率分析

In this paper a modification of the parallel Halley iteration method for simultaneously finding polynomial zeros is discussed. The convergence and the convergence rate with high order are obtained and the efficiency analysis is given.