Comparative Testing of Five Numerical Methods for Finding Roots of Polynomials

This paper summarizes the results of comparative testing of (1) Wilf's global bisection method, (2) the Laguerre method, (3) the companion matrix eigenvalue method, (4) the companion matrix eigenvalue method with balancing, and (5) the Jenkens-Traub method, all of which are methods for finding the zeros of polynomials. The test set of polynomials used are those suggested by [5]. The methods were compared on each test polynomials on the basis of the accuracy of the computed roots and the CPU time required to numerically compute all roots.     

Bounds and majorization relations for the critical points of polynomials

We apply several matrix inequalities to the derivative companion matrices of complex polynomials to establish new bounds and majorization relations for the critical points of these polynomials in terms of their zeros.     

Polynomial zerofinders based on Szegő polynomials

The computation of zeros of polynomials is a classical computational problem. This paper presents two new zerofinders that are based on the observation that, after a suitable change of variable, any polynomial can be considered a member of a family of Szegő polynomials. Numerical experiments indicate that these methods generally give higher accuracy than computing the eigenvalues of the companion matrix associated with the polynomial.     

Bounds for the zeros of polynomials from matrix inequalities - II

In this article, we present new bounds for the zeros of polynomials depending on some estimates for the spectral norms and the spectral radii of the square and the cube of the Frobenius companion matrix.     

Relationship between the zeros of two polynomials

In this paper, we shall follow a companion matrix approach to study the relationship between zeros of a wide range of pairs of complex polynomials, for example, a polynomial and its polar derivative or Sz.-Nagy’s generalized derivative. We shall introduce some new companion matrices and obtain a generalization of the Weinstein-Aronszajn Formula which will then be used to prove some inequalities similar to Sendov conjecture and Schoenberg conjecture and to study the distribution of equilibrium points of logarithmic potentials for finitely many discrete charges. Our method can also be used to produce, in an easy and systematic way, a lot of identities relating the sums of powers of zeros of a polynomial to that of the other polynomial.     

Pseudozeros of polynomials and pseudospectra of companion matrices

Summary. It is well known that the zeros of a polynomial are equal to the eigenvalues of the associated companion matrix . In this paper we take a geometric view of the conditioning of these two problems and of the stability of algorithms for polynomial zerofinding. The is the set of zeros of all polynomials obtained by coefficientwise perturbations of of size ; this is a subset of the complex plane considered earlier by Mosier, and is bounded by a certain generalized lemniscate. The is another subset of defined as the set of eigenvalues of matrices with ; it is bounded by a level curve of the resolvent of $A$. We find that if $A$ is first balanced in the usual EISPACK sense, then and are usually quite close to one another. It follows that the Matlab ROOTS algorithm of balancing the companion matrix, then computing its eigenvalues, is a stable algorithm for polynomial zerofinding. Experimental comparisons with the Jenkins-Traub (IMSL) and Madsen-Reid (Harwell) Fortran codes confirm that these three algorithms have roughly similar stability properties. Received June 15, 1993     

Stability of rootfinding for barycentric Lagrange interpolants

Computing the roots of a univariate polynomial can be reduced to computing the eigenvalues of an associated companion matrix. For the monomial basis, these computations have been shown to be numerically stable under certain conditions. However, for certain applications, polynomials are more naturally expressed in other bases, such as the Lagrange basis or orthogonal polynomial bases. For the Lagrange basis, the equivalent stability results have not been published. We show that computing the roots of a polynomial expressed in barycentric form via the eigenvalues of an associated companion matrix pair is numerically stable, and give a bound for the backward error. Numerical experiments show that the error bound is approximately an order of magnitude larger than the backward error. We also discuss the matter of scaling and balancing the companion matrix to bring it closer to a normal pair. With balancing, we are able to produce roots with small backward error.     

Bounds and a majorization for the real parts of the zeros of polynomials

We apply some eigenvalue inequalities to the real parts of the Frobenius companion matrices of monic polynomials to establish new bounds and a majorization for the real parts of the zeros of these polynomials.

     

Krawtchouk多项式零点的渐近展开及其误差限

Krawtchouk多项式在现代物理学中有着广泛应用．基于Li和Wong的结果,利用Airy函数改进了Krawtchouk多项式的渐近展开式,而且得到了一个一致有效的渐近展开式A·D2进一步,利用Airy函数零点的性质,推导出了Krawtchouk多项式零点的渐近展开式,并讨论了其相应的误差限．同时还给出了Krawtchouk多项式和其零点的渐近性态,它优于Li和Wong的结果．     

To solving multiparameter problems of algebra. 9. The Ψ<Emphasis Type="Italic">F-q</Emphasis> method for factorizing invariant polynomials and its applications

A new method (the ΨF-q method) for computing the invariant polynomials of a q-parameter (q ≥ 1) polynomial matrix F is suggested. Invariant polynomials are computed in factored form, which permits one to analyze the structure of the regular spectrum of the matrix F, to isolate the divisors of each of the invariant polynomials whose zeros belong to the invariant polynomial in question, to find the divisors whose zeros belong to at least two of the neighboring invariant polynomials, and to determine the heredity levels of points of the spectrum for each of the invariant polynomials. Applications of the ΨF-q method to representing a polynomial matrix F(λ) as a product of matrices whose spectra coincide with the zeros of the corresponding divisors of the characteristic polynomial and, in particular, with the zeros of an arbitrary invariant polynomial or its divisors are considered. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 165–173.     

Extending the notions of companion and infinite companion to matrix polynomials

The notion of infinite companion matrix is extended to the case of matrix polynomials (including polynomials with singular leading coefficient). For row reduced polynomials a finite companion is introduced as the compression of the shift matrix. The methods are based on ideas of dilation theory. Connections with systems theory are indicated. Applications to the problem of linearization of matrix polynomials, solution of systems of difference and differential equations and new factorization formulae for infinite block Hankel matrices having finite rank are shown. As a consequence, any system of linear difference or differential equations with constant coefficients can be transformed into a first order system of dimension n = deg det D.     

On permanents and the zeros of rook polynomials

The concept of rook polynomial of a “chessboard” may be generalized to the rook polynomial of an arbitrary rectangular matrix. A conjecture that the rook polynomials of “chessboards” have only real zeros is thus carried over to the rook polynomials of nonnegative matrices. This paper proves these conjectures, and establishes interlacing properties for the zeros of the rook polynomials of a positive matrix and the matrix obtained by striking any one row or any one column.     

Application of Neumann's Lemma to the minimum and characteristic polynomials

Conditions are determined under which the minimum and/or characteristic polynomials of a matrix have simple zeros.     

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.     

Random block matrices generalizing the classical Jacobi and Laguerre ensembles

In this paper we consider random block matrices which generalize the classical Laguerre ensemble and the Jacobi ensemble. We show that the random eigenvalues of the matrices can be uniformly approximated by the zeros of matrix orthogonal polynomials and obtain a rate for the maximum difference between the eigenvalues and the zeros. This relation between the random block matrices and matrix orthogonal polynomials allows a derivation of the asymptotic spectral distribution of the matrices.     

Do Orthogonal Polynomials Dream of Symmetric Curves?

The complex or non-Hermitian orthogonal polynomials with analytic weights are ubiquitous in several areas such as approximation theory, random matrix models, theoretical physics and in numerical analysis, to mention a few. Due to the freedom in the choice of the integration contour for such polynomials, the location of their zeros is a priori not clear. Nevertheless, numerical experiments, such as those presented in this paper, show that the zeros not simply cluster somewhere on the plane, but persistently choose to align on certain curves, and in a very regular fashion. The problem of the limit zero distribution for the non-Hermitian orthogonal polynomials is one of the central aspects of their theory. Several important results in this direction have been obtained, especially in the last 30 years, and describing them is one of the goals of the first parts of this paper. However, the general theory is far from being complete, and many natural questions remain unanswered or have only a partial explanation. Thus, the second motivation of this paper is to discuss some “mysterious” configurations of zeros of polynomials, defined by an orthogonality condition with respect to a sum of exponential functions on the plane, that appeared as a results of our numerical experiments. In this apparently simple situation the zeros of these orthogonal polynomials may exhibit different behaviors: for some of them we state the rigorous results, while others are presented as conjectures (apparently, within a reach of modern techniques). Finally, there are cases for which it is not yet clear how to explain our numerical results, and where we cannot go beyond an empirical discussion.     

The Bezoutian and the algebraic Riccati equation

The classical Bezoutian is a square matrix which counts the common zeros of two polynomials in the complex plane. The usual proofs of this property are based on connections between the Bezoutian and the Sylvester resultant matrix. These proofs do not make transparent the nature of the Bezoutian as a finite dimensional operator. This paper establishes that the Bezoutian is a solution of a suitable operator Riccati equation which makes evident the connections between the Bezoutian as an operator and the common zeros of polynomials. One application to the inversion of block Hankel (Toeplitz) matrices is given. Brief discussions of other Bezoutian operators are included. Apparently, even in the classical case the connection between the Bezoutian and the Riccati equation has not been studied previously.     

The Bezoutian and the algebraic Riccati equation

The classical Bezoutian is a square matrix which counts the common zeros of two polynomials in the complex plane. The usual proofs of this property are based on connections between the Bezoutian and the Sylvester resultant matrix. These proofs do not make transparent the nature of the Bezoutian as a finite dimensional operator. This paper establishes that the Bezoutian is a solution of a suitable operator Riccati equation which makes evident the connections between the Bezoutian as an operator and the common zeros of polynomials. One application to the inversion of block Hankel (Toeplitz) matrices is given. Brief discussions of other Bezoutian operators are included. Apparently, even in the classical case the connection between the Bezoutian and the Riccati equation has not been studied previously.     

Three-way companion matrices of three-variable polynomials

The existence of the companion matrices of three-variable polynomials is investigated. A theorem giving necessary and sufficient conditions for the existence of a three-way companion matrix is stated and proved. The construction of such a matrix is given too. The problem of the factorization of three-variable polynomials is also solved.