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     

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.     

Suboptimal Kronrod extension formulae for numerical quadrature

Summary We consider cases where the Stieltjes polynomial associated with a Gaussian quadrature formula has complex zeros. In such cases a Kronrod extension of the Gaussian rule does not exist. A method is described for modifying the Stieltjes polynomial so that the resulting polynomial has no complex zeros. The modification is performed in such a way that the Kronrod-type extension rule resulting from the addition of then+1 zeros of the modified Stieltjes polynomial to the original knots of the Gaussian rule has only slightly lower degree of precision than normally achieved when the Kronrod extension rule exists. As examples of the use of the method, we present some new formulae extending the classical Gauss-Hermite quadrature rules. We comment on the limited success of the method in extending Gauss-Laguerre rules and show that several modified extensions of the Gauss Gegenbauer formulae exist in cases where the standard Kronrod extension does not.     

Quadrature formulas for the Laplace and Mellin transforms

A discrete Laplace transform and its inversion formula are obtained by using a quadrature of the integral Fourier transform which is given in terms of Hermite polynomials and its zeros. This approach yields a convergent discrete formula for the two-sided Laplace transform if the function to be transformed falls off rapidly to zero and satisfies given conditions of integrability, achieving convergence also for singular functions. The inversion formula becomes a quadrature formula for the Bromwich integral. The use of asymptotic formulae yields an algorithm to compute the discrete Laplace transform by using only exponentials.     

具有指定衰减度的极点与零点的最优配置

其中A_0>0,A_i≥0,1≤i≤n-1.当b_i=0,1≤i≤m时求使J_1极小的G(s)问题在调节原理中称为广义二次最优问题。现在我们研究的是b_i≠0的更广的一般情况,从G(s)的分子分母多项式的根分布角度看,求使J_1极小的G(s)问题就是极点与零点的最优配置问题。     

A modified fast Fourier transform for polynomial evaluation and the jenkins-Traub algorithm

Summary We present an algorithm to evaluate a polynomial at uniformly spaced points on a circle in the complex plane. As an application of this algorithm, a procedure is developed which gives a starting point for the Jenkins-Traub algorithm [5, 6] to compute the zeros of a polynomial.This work was supported by National Science Foundation grants DMS-8401758 and DMS-8520926 and Air Force Office of Scientific Research grant AFOSR-ISSA-860091     

Accurate computation of the zeros of the generalized Bessel polynomials

Summary. A general method for approximating polynomial solutions of second-order linear homogeneous differential equations with polynomial coefficients is applied to the case of the families of differential equations defining the generalized Bessel polynomials, and an algorithm is derived for simultaneously finding their zeros. Then a comparison with several alternative algorithms is carried out. It shows that the computational problem of approximating the zeros of the generalized Bessel polynomials is not an easy matter at all and that the only algorithm able to give an accurate solution seems to be the one presented in this paper. Received July 25, 1997 / Revised version received May 19, 1999 / Published online June 8, 2000     

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     

Numerical factorization of a polynomial by rational Hermite interpolation

We derive a class of iterative formulae to find numerically a factor of arbitrary degree of a polynomialf(x) based on the rational Hermite interpolation. The iterative formula generates the sequence of polynomials which converge to a factor off(x). It has a high convergence order even for a factor which includes multiple zeros. Some numerical examples are also included.     

A new method for the solution ofAx=b

Summary An alternative to Gauss elimination is developed to solveAx=b. The method enables one to exploit zeros in the lower triangle ofA, so that the number of multiplications needed to perform the algorithm can be substantially reduced.     

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.     

The Durand-Kerner polynomials roots-finding method in case of multiple roots

The convergence of the Durand-Kerner algorithm is quadratic in case of simple roots but only linear in case of multiple roots. This paper shows that, at each step, the mean of the components converging to the same root approaches it with an error proportional to the square of the error at the previous step. Since it is also shown that it is possible to estimate the multiplicity order of the roots during the algorithm, a modification of the Durand-Kerner iteration is proposed to preserve a quadratic-like convergence even in case of multiple zeros.This work is supported in part by the Research Program C3 of the French CNRS and MEN, and by the Direction des Recherches et Etudes Techniques (DGA).     

Ein verallgemeinerter Kettenbruch-Algorithmus zur rationalen Hermite-Interpolation

Summary In this paper we consider rational interpolation for an Hermite Problem, i.e. prescribed values of functionf and its derivatives. The algorithm presented here computes a solutionp/q of the linearized equationsp–fq=0 in form of a generalized continued fraction. Numeratorp and denominatorq of the solution attain minimal degree compatible with the linearized problem. The main advantage of this algorithm lies in the fact that accidental zeros of denominator calculated during the algorithm cannot lead to an unexpected stop of the algorithm. Unattainable points are characterized.

Herrn Prof. Dr. Dr. h.c.mult. L. Collatz zum 70. Geburtstag gewidmet     

Numerical computation of stability and detection of Hopf bifurcations of steady state solutions of delay differential equations

The characteristic equation of a system of delay differential equations (DDEs) is a nonlinear equation with infinitely many zeros. The stability of a steady state solution of such a DDE system is determined by the number of zeros of this equation with positive real part. We present a numerical algorithm to compute the rightmost, i.e., stability determining, zeros of the characteristic equation. The algorithm is based on the application of subspace iteration on the time integration operator of the system or its variational equations. The computed zeros provide insight into the system’s behaviour, can be used for robust bifurcation detection and for efficient indirect calculation of bifurcation points. This revised version was published online in June 2006 with corrections to the Cover Date.     

Explicit zero density theorems for Dedekind zeta functions

This article studies the zeros of Dedekind zeta functions. In particular, we establish a smooth explicit formula for these zeros and we derive an effective version of the Deuring–Heilbronn phenomenon. In addition, we obtain an explicit bound for the number of zeros in a box.     

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.     

Integral dispersion equation method to solve a nonlinear boundary eigenvalue problem

In this work a nonlinear eigenvalue problem for a nonlinear autonomous ordinary differential equation of the second order is considered. This problem describes the process of propagation of transverse-electric electromagnetic waves along a plane dielectric waveguide with nonlinear permittivity. We demonstrate, as far as we know, a new method that allows one to derive an equation w.r.t. spectral parameter (the dispersion equation) which contains all necessary information about the eigenvalues. The method is based on a simple idea that the distance between zeros of a periodic solution to the differential equation is the same for the adjacent zeros. This method has no connections with the perturbation theory or the notion of a bifurcation point. Theorem of equivalence between the eigenvalue problem and the dispersion equation is proved. Periodicity of the eigenfunctions is proved, a formula for the period is found, and zeros of the eigenfunctions are determined. The formula for the distance between adjacent zeros of any eigenfunction is given. Also theorems of existence and localization of the eigenvalues are proved.     

The Haar condition and multiplicity of zeros

Summary In this paper the problem is investigated of how to take the (possibly noninteger) multiplicity of zeros into account in the Haar condition for a linear function space on a given interval. Therefore, a distinction is made between regular and singular points of the interval, and a notion of geometric multiplicity, which always is a positive integer, is introduced. It is pointed out that, for regular zeros (i.e., zeros situate at regular points), aq-fold zero (in the sense that its geometric multiplicity equalsq), counts forq distinct zeros in the Haar condition. For singular zeros (i.e., zeros situated at singular points), this geometric multiplicity has to be diminished by some well-determinable integer.     

On the eigenvalue problem for Toeplitz band matrices

A formula is given for the characteristic polynomial of an nth order Toeplitz band matrix, with bandwidth k < n, in terms of the zeros of a kth degree polynomial with coefficients independent of n. The complexity of the formula depends on the bandwidth k, and not on the order n. Also given is a formula for eigenvectors, in terms of the same zeros and k coefficients which can be obtained by solving a k × k homogeneous system.     

Estimating convergence regions of Schröder’s iteration formula: how the Julia set shrinks to the Voronoi boundary

Numerical Algorithms - Schröder’s iterative formula of the second kind (S2 formula) for finding zeros of a function f(z) is a generalization of Newton’s formula to an arbitrary...