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 correlations of finite Desarguesian planes, Part III: The classification (II)

This paper continues the classification of the correlations of planes of odd nonsquare order. Part I (Generalities) included introductory definitions and results (Section 1), algebraic preliminaries (Section 2), as well as a discussion of equivalent correlations (Section 3) and of their general properties (Section 4). The classification proper revolves around a special polynomial which can have one, two, or q + 1 zeros, or no zeros at all, and each of these four possibilities leads to different families of correlations. Part II contained Section 5, devoted to the cases in which the correlation is defined by a diagonal matrix (Subsection 5.1) or the polynomial in the preceding paragraph possesses q + 1 zeros (Subsection 5.2), one zero (Subsection 5.3) and two zeros (Subsection 5.4). Subsection 5.5 presented certain results to be used in the subsequent sections. The present article contains Section 6, devoted to the case in which the above-mentioned polynomial has no zeros.     

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. 10. Computing zeros of a scalar polynomial

The paper considers the problem of computing zeros of scalar polynomials in several variables. The zeros of a polynomial are subdivided into the regular (eigen-and mixed) zeros and the singular ones. An algorithm for computing regular zeros, based on a decomposition of a given polynomial into a product of primitive polynomials, is suggested. The algorithm is applied to solving systems of nonlinear algebraic equations. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 346, 2007, pp. 119–130.     

On Isolation of Real and Nearly Real Zeros of a Univariate Polynomial and Its Splitting into Factors

We show two simple algorithms for isolation of the real and nearly real zeros of a univariate polynomial, as well as of those zeros that lie on or near a fixed circle on the complex plane. We also simplify slightly approximation of complex zeros of a polynomial with real coefficients.     

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.     

Spectral factorization of Laurent polynomials

We analyse the performance of five numerical methods for factoring a Laurent polynomial, which is positive on the unit circle, as the modulus squared of a real algebraic polynomial. It is found that there is a wide disparity between the methods, and all but one of the methods are significantly influenced by the variation in magnitude of the coefficients of the Laurent polynomial, by the closeness of the zeros of this polynomial to the unit circle, and by the spacing of these zeros. This revised version was published online in August 2006 with corrections to the Cover Date.     

A new,simple approach to the derivation of exact analytical formulae for the zeros of analytic functions

A very simple method for the construction of the polynomial whose zeros coincide with the zeros of an analytic function inside and along a simple closed contour in the complex plane, based on an appropriate application of the Cauchy theorem in complex analysis, is proposed. The present method was motivated by the classical Burniston-Siewert method, based on the theory of the Riemann-Hilbert boundary-value problem for the construction of the aforementioned polynomial, but, although essentially equivalent to the Burniston-Siewert method, it is much simpler.     

Graeffe's, Chebyshev-like, and Cardinal's Processes for Splitting a Polynomial into Factors

Numerical splitting of a real or complex univariate polynomial into factors is the basic step of the divide-and-conquer algorithms for approximating complex polynomial zeros. Such algorithms are optimal (up to polylogarithmic factors) and are quite promising for practical computations. In this paper, we develop some new techniques, which enable us to improve numerical analysis, performance, and computational cost bounds of the known splitting algorithms. In particular, we study a Chebyshev-like modification of Graeffe's lifting iteration (which is a basic block of the splitting algorithms, as well as of several other known algorithms for approximating polynomial zeros), analyze its numerical performance, compare it with Graeffe's, prove some results on numerical stability of both lifting processes (that is, Graeffe's and Chebyshev-like), study their incorporation into polynomial root-finding algorithms, and propose some improvements of Cardinal's recent effective technique for numerical splitting of a polynomial into factors. Our improvement relies, in particular, on a modification of the matrix sign iteration, based on the analysis of some conformal mappings of the complex plane and of techniques of recursive lifting/recursive descending. The latter analysis reveals some otherwise hidden correlations among Graeffe's, Chebyshev-like, and Cardinal's iterative processes, and we exploit these correlations in order to arrive at our improvement of Cardinal's algorithm. Our work may also be of some independent interest for the study of applications of conformal maps of the complex plane to polynomial root-finding and of numerical properties of the fundamental techniques for polynomial root-finding such as Graeffe's and Chebyshev-like iterations.     

A posteriori error bounds for the zeros of a polynomial

Summary An algorithm for the computation of error bounds for the zeros of a polynomial is described. This algorithm is derived by applying Rouché's theorem to a Newton-like interpolation formula for the polynomial, and so it is suitable in the case where the approximations to the zeros of the polynomial are computed successively using deflation. Confluent and clustered approximations are handled easily. However bounds for the local rouding errors in deflation, e.g. in Horner's scheme, must be known. In practical application the method can, especially in some ill-conditioned cases, compete with other known estimates.     

The Use of Interval Arithmetic to Bound the Zeros of Real Polynomials

This paper discusses the problem of bounding the zeros of areal polynomial. Champagne's results in this field are given,and then Moore's extension of the Newton-Raphson Process forinterval arithmetic. Methods are then presented to deal withthe cases of complex zeros and multiple zeros, for which theNewton-Raphson-Moore Method is not applicable.     

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.     

Lifting/Descending Processes for Polynomial Zeros

The recently proposed Chebyshev-like lifting map for the zeros of a univariate polynomial was motivated by its applications to splitting a univariate polynomial p(z) numerically into factors, which is a major step of some most efficient algorithms for approximating polynomial zeros. We complement the Chebyshev-like lifting process by a descending process, decrease the estimated computational cost of performing the algorithm, demonstrate its correlation to Graeffe's lifting/descending process, and generalize lifting from Graeffe's and Chebyshev-like maps to any fixed rational map of the zeros of the input polynomial.     

The correlations of finite Desarguesian planes, Part II: The classification (I)

This paper continues the classification of the correlations of planes of odd nonsquare order. Part I (Generalities) – see reference [1]-included introductory definitions and results (Section 1), algebraic preliminaries (Section 2), as well as a discussion of equivalent correlations (Section 3) and of their general properties (Section 4). The classification proper revolves around a special polynomial which can have one, two, or q + 1 zeros, or no zeros at all, and each of these four possibilities leads to different families of correlations. The present article contains Section 5, devoted to the cases in which the correlation is defined by a diagonal matrix (Subsection 5.1) or the polynomial in the preceding paragraph possesses q + 1 zeros (Subsection 5.2), one zero (Subsection 5.3) and two zeros (Subsection 5.4). Subsection 5.5 presents certain results to be used in the subsequent sections.     

Weierstrass formula and zero-finding methods

Summary. Classical Weierstrass' formula [29] has been often the subject of investigation of many authors. In this paper we give some further applications of this formula for finding the zeros of polynomials and analytic functions. We are concerned with the problems of localization of polynomial zeros and the construction of iterative methods for the simultaneous approximation and inclusion of these zeros. Conditions for the safe convergence of Weierstrass' method, depending only on initial approximations, are given. In particular, we study polynomials with interval coefficients. Using an interval version of Weierstrass' method enclosures in the form of disks for the complex-valued set containing all zeros of a polynomial with varying coefficients are obtained. We also present Weierstrass-like algorithm for approximating, simultaneously, all zeros of a class of analytic functions in a given closed region. To demonstrate the proposed algorithms, three numerical examples are included. Received September 13, 1993     

Containment regions for zeros of polynomials from numerical ranges of companion matrices

Containment regions for the zeros of a monic polynomial are given with the aid of results for containment regions for the numerical range of certain bordered diagonal matrices which are applied to different types of companion matrices of the polynomial.     

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.     

An Algorithm for Finding All Isolated Zeros of Polynomial Systems

Finding all zeros of polynomial systems is very interesting and it is also useul for many applied science problems.In this paper,based on Wu‘s method,we give an algorithm to find all isolated zeros of polynomial systems (or polynomial equations).By solving Lorenz equations,it is shown that our algo-rithm is efficient and powerful.     

Fehlerabschätzungen bei Polynomgleichungen mit dem Fixpunktsatz von Brouwer

Summary It is supposed that to every zero of a polynomial of degreem an approximation is known. A method is described to give a simultaneous error estimation. The idea is to construct an operator of them-dimensional vector space such that the components of its fixed point are exactly the zeros of the polynomial. Under certain conditions an error bound for the fixed point and hence for the zeros of the polynomial follows from BROUWER'S fixed point theorem. The estimation received is numerically useful.