On The Convergence Of Some Interval Methods For Simultaneous Computation Of Polynomial Zeros

In this paper we consider the convergence of a certain interval method for simultaneous computation of polynomial zeros. Under the legitimacy of suitable isolation of the roots in a restrictive respective circular disks it is established in a limiting sense a finite positive constant in existence for which convergence is certain. This positive constant which is the limiting convergence factor is dependent on the minimum distance between the zeros of the polynomial. This provides a qualitative information that may be found useful on the occasion the roots are clustered. The climax however, is an introduction of a new interval method and an improved modification of an existing one considered.     

Derivative Free Inclusion Methods for Polynomial Zeros

Two iterative methods for the simultaneous inclusion of complex zeros of a polynomial are presented. Both methods are realized in circular interval arithmetic and do not use polynomial derivatives. The first method of the fourth order is composed as a combination of interval methods with the order of convergence two and three. The second method is constructed using double application of the inclusion method of Weierstrass’ type in serial mode. It is shown that its R-order of convergence is bounded below by the spectral radius of the corresponding matrix. Numerical examples illustrate the convergence rate of the presented methods     

Detection and Validation of Clusters of Polynomial Zeros

We consider the task of partitioning the zeros of a real or complex polynomial into clusters and of determining their location and multiplicity for polynomials with coefficients of limited accuracy. We derive computational procedures for the solution of this task which combine symbolic computation with floating-point arithmetic. The validation of the existence ofmzeros in a specified small disk is described.     

喇叭增益的精确设计和精确计算

本文综述了作者和他人有关喇叭增益的精确设计与精确计算的理论结果,并且得出结论,举出实例。     

Ostrowski-Like Method with Corrections for the Inclusion of Polynomial Zeros

In this paper we construct iterative methods of Ostrowski's type for the simultaneous inclusion of all zeros of a polynomial. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis of the total-step and the single-step methods with Newton and Halley's corrections. The case of multiple zeros is also considered. The suggested algorithms possess a great computational efficiency since the increase of the convergence rate is attained without additional calculations. Numerical examples and an analysis of computational efficiency are given.     

Sharp Bounds on Interval Polynomial Roots

An algorithm is developed for computing sharp bounds on the real roots of polynomials with interval coefficients. The procedure is introduced by studying interval quadratic equations.     

Halley-Like Method with Corrections for the Inclusion of Polynomial Zeros

In this paper we present iteration methods of Halley's type for the simultaneous inclusion of all zeros of a polynomial. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis for the total-step and the single-step methods with Newton's corrections. The suggested algorithms possess a great computational efficiency since the increase of the convergence rate is attained without additional calculations. A numerical example is given. Received: June 23, 1998     

Weierstrass-like Methods with Corrections for the Inclusion of Polynomial Zeros

In this paper, we present iterative methods of Weierstress’ type for the simultaneous inclusion of all simple zeros of a polynomial. The main advantage of the proposed methods is the increase of the convergence rate attained by applying suitable correction terms. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis for the total-step and the single-step methods. Numerical examples are given.     

Mapping Based Algorithm for Large-Scale Computation of Quasi-Polynomial Zeros

A method for computing all zeros of a retarded quasi-polynomial that are located in a large region of the complex plane is presented. The method is based on mapping the quasi-polynomial and on utilizing asymptotic properties of the chains of zeros. First, the asymptotic exponentials of the chains are determined based on the distribution diagram of the quasi-polynomial. Secondly, large regions free of zeros are defined. Finally, the zeros are located as the intersection points of the zero-level curves of the real and imaginary parts of the quasi-polynomial, which are evaluated over the areas of the region outside those free of zeros.     

Hypergeometric Functions in Exact Geometric Computation

Most problems in computational geometry are algebraic. A general approach to address nonrobustness in such problems is Exact Geometric Computation (EGC). There are now general libraries that support EGC for the general programmer (e.g., Core Library, LEDA Real). Many applications require non-algebraic functions as well. In this paper, we describe how to provide non-algebraic functions in the context of other EGC capabilities. We implemented a multiprecision hypergeometric series package which can be used to evaluate common elementary math functions to an arbitrary precision. This can be achieved relatively easily using the Core Library which supports a guaranteed precision level of accuracy. We address several issues of efficiency in such a hypergeometric package: automatic error analysis, argument reduction, preprocessing of hypergeometric parameters, and precomputed constants. Some preliminary experimental results are reported.     

Coinduction for Exact Real Number Computation

This paper studies coinductive representations of real numbers by signed digit streams and fast Cauchy sequences. It is shown how the associated coinductive principle can be used to give straightforward and easily implementable proofs of the equivalence of the two representations as well as the correctness of various corecursive exact real number algorithms. The basic framework is the classical theory of coinductive sets as greatest fixed points of monotone operators and hence is different from (though related to) the type theoretic approach by Ciaffaglione and Gianantonio.     

Exact Computation of Delaunay and Power Triangulations

In this paper we present a topologically correct and efficient version of the algorithm by Guibas and Stolfi (Algorithmica 7 (1992), pp. 381-413) for the exact computation of Delaunay and power triangulations in two dimensions. The algorithm avoids numerical errors and degeneracies caused by the accumulation of rounding errors in fixed length floating point arithmetic when constructing these triangulations.Most methods for computing Delaunay and power triangulations involve the calculation of two basic primitives: the INCIRCLE test and the CCW orientation test. Both primitives require the computation of the sign of a determinant. The key to our method is the exact computation of this sign and is based on an algorithm for determining the sign of the sum of a finite set of normalized floating point numbers of fixed mantissa length (machine numbers) exactly. The exact computation of the primitives allows the construction of the correct Delaunay and power triangulations. The method has been implemented and tested for the incremental construction of Delaunay and power triangulations. Tests have been conducted for different distributions of points for which non-exact algorithms may encounter difficulties, for example, slightly perturbed points on a grid or on a circle. Experimental results show that the performance of our implementation is comparable with that of a simple implementation of the incremental algorithm in single precision floating point arithmetic. For random distribution of points the exact algorithm is only 4 times slower than the inexact implementation. The algorithm is easy to implement, robust and portable as long as the input data to the algorithm remains exact.     

Computation of Approximate Polynomial GCDs and an Extension

Computation of approximate polynomial greatest common divisors (GCDs) is important both theoretically and due to its applications to control linear systems, network theory, and computer-aided design. We study two approaches to the solution so far omitted by the researchers, despite intensive recent work in this area. Correlation to numerical Padé approximation enabled us to improve computations for both problems (GCDs and Padé). Reduction to the approximation of polynomial zeros enabled us to obtain a new insight into the GCD problem and to devise effective solution algorithms. In particular, unlike the known algorithms, we estimate the degree of approximate GCDs at a low computational cost, and this enables us to obtain certified correct solution for a large class of input polynomials. We also restate the problem in terms of the norm of the perturbation of the zeros (rather than the coefficients) of the input polynomials, which leads us to the fast certified solution for any pair of input polynomials via the computation of their roots and the maximum matchings or connected components in the associated bipartite graph.     

求多项式全部根的遗传算法

本文给出了一种求复系数多项式全部根的遗传算法,探讨了算法实现的一些技术问题。     

求多项式全部根的遗传算法

本文给出了一种求复系数多项式全部根的遗传算法,探讨了算法实现的一些技术问题。     

Symbolic Computation on Complex Polynomial Solution of Differential Equations

A symbolic computation scheme, based on the Lanczos τ-method, is proposed for obtaining exact polynomial solutions to some perturbed differential equations with suitable boundary conditions. The automated τ-method uses symbolic Faber polynomials as the perturbation terms for arbitrary circular sections of the complex plane and has advantages of avoiding rounding error and easy manipulation over the numerical counterpart. The method is illustrated by applying it to the modified Bessel function of the first kindI₀(z) and the quality of the approximation is discussed.     

Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks

An O(nlog² n) algorithm is presented to compute all coefficients of the characteristic polynomial of a tree on n vertices improving on the previously best quadratic time. With the same running time, the algorithm can be generalized in two directions. The algorithm is a counting algorithm for matchings, and the same ideas can be used to count other objects. For example, one can count the number of independent sets of all possible sizes simultaneously with the same running time. These counting algorithms not only work for trees, but can be extended to arbitrary graphs of bounded tree-width.