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.     

Computing the Invariant Polynomials of a Polynomial Matrix. II

The paper considers the problem of computing the invariant polynomials of a general (regular or singular) one-parameter polynomial matrix. Two new direct methods for computing invariant polynomials, based on the W and V rank-factorization methods, are suggested. Each of the methods may be regarded as a method for successively exhausting roots of invariant polynomials from the matrix spectrum. Application of the methods to computing adjoint matrices for regular polynomial matrices, to finding the canonical decomposition into a product of regular matrices such that the characteristic polynomial of each of them coincides with the corresponding invariant polynomial, and to computing matrix eigenvectors associated with roots of its invariant polynomials are considered. Bibliography: 5 titles.     

An algorithm for decomposing a polynomial system into normal ascending sets

We present an algorithm to decompose a polynomial system into a finite set of normal ascending sets such that the set of the zeros of the polynomial system is the union of the sets of the regular zeros of the normal ascending sets.If the polynomial system is zero dimensional,the set of the zeros of the polynomials is the union of the sets of the zeros of the normal ascending sets.     

To solving multiparameter problems of algebra 3. Cylindrical manifolds of the regular spectrum of a matrix

Methods for computing polynomials (complete polynomials) whose zeros form cylindrical manifolds of the regular spectrum of a q-parameter polynomial matrix in the space ^q are considered. Based on the method of partial relative factorization of matrices, new methods for computing cylindrical manifolds are suggested. The W and V methods, previously proposed for computing complete polynomials of q-parameter polynomial matrices whose regular spectrum is independent of one of the parameters, are extended to a wider class of matrices. Bibliography: 4 titles._______Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 296, 2003, pp. 108–121.     

Minimum relative error approximations for 1/t

Summary We give explicit solutions to the problem of minimizing the relative error for polynomial approximations to 1/t on arbitrary finite subintervals of (0, ). We give a simple algorithm, using synthetic division, for computing practical representations of the best approximating polynomials. The resulting polynomials also minimize the absolute error in a related functional equation. We show that, for any continuous function with no zeros on the interval of interest, the geometric convergence rates for best absolute error and best relative error approximants must be equal. The approximation polynomials for 1/t are useful for finding suitably precise initial approximations in iterative methods for computing reciprocals on computers.     

To solving problems of algebra for two-parameter matrices. IV

This paper continues the series of publications devoted to surveying and developing methods for solving the following problems for a two-parameter matrix F (λ, μ) of general form: exhausting points of the mixed regular spectrum of F (λ, μ); performing operations on polynomials in two variables (computing the GCD and LCM of a few polynomials, division of polynomials, and factorization); computing a minimal basis of the null-space of polynomial solutions of the matrix F (λ, μ) and separation of its regular kernel; inversion and pseudo in version of polynomial and rational matrices in two variables, and solution of systems of nonlinear algebraic equations in two unknowns. Most of the methods suggested are based on rank factorizations of a two-parameter polynomial matrix and on the method of hereditary pencils. Bibliography: 8 titles.     

Moments and sums of squares for polynomial optimization and related problems

We briefly review the duality between moment problems and sums of squares (s.o.s.) representations of positive polynomials, and compare s.o.s. versus nonnegative polynomials. We then describe how to use such results to define convergent semidefinite programming relaxations in polynomial optimization as well as for the two related problems of computing the convex envelope of a rational function and finding all zeros of a system of polynomial equations.     

To solving multiparameter problems of algebra. 2. The method of partial relative factorization and its applications

For a q-parameter (q 2) polynomial matrix of full rank whose regular and singular spectra have no points in common, a method for computing its partial relative factorization into a product of two matrices with disjoint spectra is suggested. One of the factors is regular and is represented as a product of q matrices with disjoint spectra. The spectrum of each of the factors is independent of one of the parameters and forms in the space ^q a cylindrical manifold w.r.t. this parameter. The method is applied to computing zeros of the minimal polynomial with the corresponding eigenvectors. An application of the method to computing a specific basis of the null-space of polynomial solutions of the matrix is considered. Bibliography: 4 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 296, 2003, pp. 89–107.     

Erdös-Turán theorems on a system of Jordan curves and arcs

Erdös and Turán established in [4] a qualitative result on the distribution of the zeros of a monic polynomial, the norm of which is known on [–1, 1]. We extend this result to a polynomial bounded on a systemE of Jordan curves and arcs. If all zeros of the polynomial are real, the estimates are independent of the number of components ofE for any regular compact subsetE ofR. As applications, estimates for the distribution of the zeros of the polynomials of best uniform approximation and for the extremal points of the optimal error curve (generalizations of Kadec's theorem) are given.Communicated by Dieter Gaier.     

Zeros of univariate interval polynomials

Polynomials with perturbed coefficients, which can be regarded as interval polynomials, are very common in the area of scientific computing due to floating point operations in a computer environment. In this paper, the zeros of interval polynomials are investigated. We show that, for a degree n interval polynomial, the number of interval zeros is at most n and the number of complex block zeros is exactly n if multiplicities are counted. The boundaries of complex block zeros on a complex plane are analyzed. Numeric algorithms to bound interval zeros and complex block zeros are presented.     

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.     

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     

To Solving Multiparameter Problems of Algebra. 5. The ∇V-q Factorization Algorithm and its Applications

The algorithm of ∇V-factorization, suggested earlier for decomposing one- and two-parameter polynomial matrices of full row rank into a product of two matrices (a regular one, whose spectrum coincides with the finite regular spectrum of the original matrix, and a matrix of full row rank, whose singular spectrum coincides with the singular spectrum of the original matrix, whereas the regular spectrum is empty), is extended to the case of q-parameter (q ≥ 1) polynomial matrices. The algorithm of ∇V-q factorization is described, and its justification and properties for matrices with arbitrary number of parameters are presented. Applications of the algorithm to computing irreducible factorizations of q-parameter matrices, to determining a free basis of the null-space of polynomial solutions of a matrix, and to finding matrix divisors corresponding to divisors of its characteristic polynomial are considered. Bibliogrhaphy: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 144–153.     

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

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.     

A recursive algorithm by the moments method to evaluate a class of numerical integrals over an infinite interval

A special recursive algorithm is built by a three-term recursive formula with coefficients evaluated by the moments method.A new functionalc(·) is studied over any function space that contains the polynomial space and it is shown that such a functional is positive definite, enabling us to use the advantages of such a property on the zeros of orthogonal polynomials for such a functional. A comparison is presented of the numerical advantages of such a method with respect to the Laguerre polynomials.     

Expansions for the Fundamental Hermite Interpolation Polynomials in Terms of Chebyshev Polynomials

We obtain explicit expansions of the fundamental Hermite interpolation polynomials in terms of Chebyshev polynomials in the case where the nodes considered are either zeros of the (n + 1)th-degree Chebyshev polynomial or extremum points of the nth-degree Chebyshev polynomial.     

To Solving Multiparameter Problems of Algebra. 4. The AB-Algorithm and its Applications

The paper continues the investigation of methods for factorizing q-parameter polynomial matrices and considers their applications to solving multiparameter problems of algebra. An extension of the AB-algorithm, suggested earlier as a method for solving spectral problems for matrix pencils of the form A - λB, to the case of q-parameter (q ≥ 1) polynomial matrices of full rank is proposed. In accordance with the AB-algorithm, a finite sequence of q-parameter polynomial matrices such that every subsequent matrix provides a basis of the null-space of polynomial solutions of its transposed predecessor is constructed. A certain rule for selecting specific basis matrices is described. Applications of the AB-algorithm to computing complete polynomials of a q-parameter polynomial matrix and exhausting them from the regular spectrum of the matrix, to constructing irreducible factorizations of rational matrices satisfying certain assumptions, and to computing “free” bases of the null-spaces of polynomial solutions of an arbitrary q-parameter polynomial matrix are considered. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 127–143.     

Number of zeros of interval polynomials

In this paper, we develop a rigorous algorithm for counting the real interval zeros of polynomials with perturbed coefficients that lie within a given interval, without computing the roots of any polynomials. The result generalizes Sturm’s Theorem for counting the roots of univariate polynomials to univariate interval polynomials.     

Computing the Invariant Polynomials of a Polynomial Matrix. I

An algorithm for computing the invariant polynomials and the canonical triangular (trapezoidal) matrix for a polynomial matrix of full column rank is suggested. The algorithm is based on the Δ W-1 rank-factorization method for solving algebraic problems for polynomial matrices, previously suggested by the author. Bibliography: 3 titles.