Computing multiple roots of inexact polynomials

We present a combination of two algorithms that accurately calculate multiple roots of general polynomials.

Algorithm I transforms the singular root-finding into a regular nonlinear least squares problem on a pejorative manifold, and it calculates multiple roots simultaneously from a given multiplicity structure and initial root approximations. To fulfill the input requirement of Algorithm I, we develop a numerical GCD-finder containing a successive singular value updating and an iterative GCD refinement as the main engine of Algorithm II that calculates the multiplicity structure and the initial root approximation. While limitations exist in certain situations, the combined method calculates multiple roots with high accuracy and consistency in practice without using multiprecision arithmetic, even if the coefficients are inexact. This is perhaps the first blackbox-type root-finder with such capabilities.

To measure the sensitivity of the multiple roots, a structure-preserving condition number is proposed and error bounds are established. According to our computational experiments and error analysis, a polynomial being ill-conditioned in the conventional sense can be well conditioned with the multiplicity structure being preserved, and its multiple roots can be computed with high accuracy.

     

On One Method for Factorization of Algebraic Polynomials

We propose a method for the factorization of algebraic polynomials with real or complex coefficients and construct a numerical algorithm, which, along with the factorization of a polynomial with multiple roots, solves the problem of the determination of multiplicities and the number of multiple roots of the polynomial.     

ROBUST INEXACT ALTERNATING OPTIMIZATION FOR MATRIX COMPLETION WITH OUTLIERS

We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise. We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization, whose objective function consists of an $\ell_1$ norm data fidelity and a rank constraint. To reduce the computational cost per iteration, two inexact schemes are developed to replace the most time-consuming step in the generic ADMM algorithm. The resulting algorithms remarkably outperform the existing solvers for robust matrix completion with outlier noise. When the noise is severe and the underlying matrix is ill-conditioned, the proposed algorithms are faster and give more accurate solutions than state-of-the-art robust matrix completion approaches.     

Extended Jury criterion

In this paper,algebraic criteria are established to determine whether or not a real coefficient polynomial has one or two pairs of conjugate complex roots whose moduli are equal to 1 and the other roots have moduli less than 1 directly from its coefficients.The form and the function of the criteria are similar to those of the Jury criterion which can be used to determine whether or not all the moduli of the roots of a real coefficient polynomial are less than 1.     

Some properties of zeros of polynomials with vanishing coefficients

It is well-known that when a polynomial whose coefficients are continuous functions of a parameter loses its degree then some of its zeros must vanish at infinity. In this paper, we consider such a situation: we examine how roots of a complex polynomial tend to infinity as some of its coefficients, including the leading one, tend to zero. We show, among other things, that in such a situation the unbounded paths traced by the roots of the polynomial have asymptotes; we also obtain their formulas. Some examples are presented to complete and illustrate the results.     

An implementation of Vincent's theorem

Summary A new method is presented for the isolation of the real roots of a polynomial equation; it is based on Vincent's forgotten theorem of 1836 and has been implemented using exact (infinite precision) integer arithmetic algorithms. A theoretical analysis of the computing time of this method is given along with some empirical results.     

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.     

On the class of proper linear differential systems with unbounded coefficients

Proper linear differential systems (whose coefficients are not necessarily bounded on the half-line) are defined as systems for which there exists a generalized Lyapunov transformation reducing them to a diagonal system with constant coefficients (Basov). We prove that Lyapunov’s original definition of a proper system and the Perron and Vinograd criteria hold for the class of proper systems as well as for the class of proper systems with uniformly bounded coefficients. We show that the Lyapunov properness criterion for a triangular system fails for systems with unbounded coefficients; namely, we construct an improper system with the following properties: the Lyapunov exponents of all nonzero solutions of that system are finite and exact, and for an arbitrary reduction of this system by a generalized Lyapunov transformation to triangular form, its diagonal coefficients have finite exact mean values, whose set with regard of multiplicities is independent of the choice of the transformation. In addition, we show that the main property of proper systems with uniformly bounded coefficients (preservation of conditional exponential stability as well as the dimension of the exponentially stable manifold and the exponent of the asymptotic behavior of solutions under perturbations of higher-order smallness) holds for proper systems with unbounded coefficients as well.     

求複數根的舗D法

<正> 一. 引言 代數方程f(x)=0的實數根的逐步接近法已有多種,其中計算簡單收斂最快的是用牛頓公式     

Some parallel methods for polynomial root-finding

Parallelizations of various different methods for determining the roots of a polynomial are discussed. These include methods which locate a single root only as well as those which find all roots. Some techniques for parallelizing such methods are identified and some examples are given. Further places in polynomial root-finding algorithms where parallel behaviour can be introduced are described. Results are presented for a range of programs written to test the effectiveness of methods presented here.     

Exact stability regions for quartic polynomials

Given an arbitrary real quartic polynomial, we find the exact region containing the coefficients of the polynomial such that all roots have absolute values less than 1.     

On perturbation of roots of homogeneous algebraic systems

A problem concerning the perturbation of roots of a system of homogeneous algebraic equations is investigated. The question of conservation and decomposition of a multiple root into simple roots are discussed. The main theorem on the conservation of the number of roots of a deformed (not necessarily homogeneous) algebraic system is proved by making use of a homotopy connecting initial roots of the given system and roots of a perturbed system. Hereby we give an estimate on the size of perturbation that does not affect the number of roots. Further on we state the existence of a slightly deformed system that has the same number of real zeros as the original system in taking the multiplicities into account. We give also a result about the decomposition of multiple real roots into simple real roots.

     

On the Existence of Real Entire Functions with a Prescribed Ordered Set of Stationary Values

To each ordered set of real stationary values (with multiplicities) is shown to correspond a real entire function ƒ taking on the stationary values in the given order and with the given multiplicities along the real axis. This function has a derivative ƒ′, whose roots are all real, and which is of the Pólya-Laguerre class; the function ƒ is, apart from an arbitrary real affine transformation (conserving order) of the independent variable, the only function satisfying all of the conditions above.     

A simple approach for determining the eigenvalues of the fourth-order Sturm–Liouville problem with variable coefficients

In this paper, a simple and efficient approach is presented to compute the eigenvalues of the fourth-order Sturm–Liouville equations with variable coefficients. By transforming the governing differential equation to a system of algebraic equation, we can get the corresponding polynomial characteristic equations for kinds of boundary conditions based on the polynomial expansion and integral technique. Moreover, the lower and higher-order eigenvalues can be determined simultaneously from the multi-roots. Several examples for estimating eigenvalues are given. The convergence and effectiveness of the method are confirmed by comparing numerical results with the exact and other existing numerical results.     

稳定性判定与多项式求根算法

本文给出了一种判定多项式根是否全在单位圆内的简便方法．该方法可用于判定离散控制系统的稳定性和求多项式的全部根。     

On Descartes' rules of signs and their exactness

This paper revisits the Descartes' rules of signs and provides new bounds for the number of complex roots of a polynomial in certain complex regions. We also prove that the Descartes' rules associated with the Bernstein basis are exact for polynomials whose roots are real. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Polynomial quasisolutions of linear second-order differential-difference equations

We consider the scalar linear second-order differential-difference equation with delay {fx159-01}. This equation is investigated by the method of polynomial quasisolutions based on the representation of an unknown function in the form of a polynomial {ie159-01}. Upon the substitution of this polynomial in the original equation, the residual Δ(t) = O(t ^N−1) appears. An exact analytic representation of this residual is obtained. We show the close connection between a linear differential-difference equation with variable coefficients and a model equation with constant coefficients, the structure of whose solution is determined by the roots of the characteristic quasipolynomial. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 1, pp. 140–152, January, 2008.     

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.     

Convex proximal bundle methods in depth: a unified analysis for inexact oracles

The last few years have seen the advent of a new generation of bundle methods, capable to handle inexact oracles, polluted by “noise”. Proving convergence of a bundle method is never simple and coping with inexact oracles substantially increases the technicalities. Besides, several variants exist to deal with noise, each one needing an ad hoc proof to show convergence. We state a synthetic convergence theory, in which we highlight the main arguments and specify which assumption is used to establish each intermediate result. The framework is comprehensive and generalizes in various ways a number of algorithms proposed in the literature. Based on the ingredients of our synthetic theory, we consider various bundle methods adapted to oracles for which high accuracy is possible, yet it is preferable not to make exact calculations often, because they are too time consuming.     

Numerical enclosure for multiple eigenvalues of an Hermitian matrix whose graph is a tree

In this paper we consider a numerical enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. If an Hermitian matrix A whose graph is a tree has multiple eigenvalues, it has the property that matrices which are associated with some branches in the undirected graph of A have the same eigenvalues. By using this property and interlacing inequalities for Hermitian matrices, we show an enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. Since we do not generally know whether a given matrix has exactly a multiple eigenvalue from approximate computations, we use the property of interlacing inequalities to enclose some eigenvalues including multiplicities.In this process, we only use the enclosure of simple eigenvalues to enclose a multiple eigenvalue by using a computer and interval arithmetic.