On Location and Approximation of Clusters of Zeros of Analytic Functions

At the beginning of the 1980s, M. Shub and S. Smale developed a quantitative analysis of Newton's method for multivariate analytic maps. In particular, their α-theory gives an effective criterion that ensures safe convergence to a simple isolated zero. This criterion requires only information concerning the map at the initial point of the iteration. Generalizing this theory to multiple zeros and clusters of zeros is still a challenging problem. In this paper we focus on one complex variable function. We study general criteria for detecting clusters and analyze the convergence of Schroder's iteration to a cluster. In the case of a multiple root, it is well known that this convergence is quadratic. In the case of a cluster with positive diameter, the convergence is still quadratic provided the iteration is stopped sufficiently early. We propose a criterion for stopping this iteration at a distance from the cluster which is of the order of its diameter.     

On Locating Clusters of Zeros of Analytic Functions

Given an analytic function f and a Jordan curve that does not pass through any zero of f, we consider the problem of computing all the zeros of f that lie inside , together with their respective multiplicities. Our principal means of obtaining information about the location of these zeros is a certain symmetric bilinear form that can be evaluated via numerical integration along . If f has one or several clusters of zeros, then the mapping from the ordinary moments associated with this form to the zeros and their respective multiplicities is very ill-conditioned. We present numerical methods to calculate the centre of a cluster and its weight, i.e., the arithmetic mean of the zeros that form a certain cluster and the total number of zeros in this cluster, respectively. Our approach relies on formal orthogonal polynomials and rational interpolation at roots of unity. Numerical examples illustrate the effectiveness of our techniques.     

Do Orthogonal Polynomials Dream of Symmetric Curves?

The complex or non-Hermitian orthogonal polynomials with analytic weights are ubiquitous in several areas such as approximation theory, random matrix models, theoretical physics and in numerical analysis, to mention a few. Due to the freedom in the choice of the integration contour for such polynomials, the location of their zeros is a priori not clear. Nevertheless, numerical experiments, such as those presented in this paper, show that the zeros not simply cluster somewhere on the plane, but persistently choose to align on certain curves, and in a very regular fashion. The problem of the limit zero distribution for the non-Hermitian orthogonal polynomials is one of the central aspects of their theory. Several important results in this direction have been obtained, especially in the last 30 years, and describing them is one of the goals of the first parts of this paper. However, the general theory is far from being complete, and many natural questions remain unanswered or have only a partial explanation. Thus, the second motivation of this paper is to discuss some “mysterious” configurations of zeros of polynomials, defined by an orthogonality condition with respect to a sum of exponential functions on the plane, that appeared as a results of our numerical experiments. In this apparently simple situation the zeros of these orthogonal polynomials may exhibit different behaviors: for some of them we state the rigorous results, while others are presented as conjectures (apparently, within a reach of modern techniques). Finally, there are cases for which it is not yet clear how to explain our numerical results, and where we cannot go beyond an empirical discussion.     

On simple double zeros and badly conditioned zeros of analytic functions of variables

We give a numerical criterion for a badly conditioned zero of a system of analytic equations to be part of a cluster of two zeros.

     

On zeros of polynomials orthogonal with respect to a quasi-definite inner product on the unit circle

In this paper we present some results concerning the zeros of sequences of polynomials orthogonal with respect to a quasi-definite inner product on the unit circle. We study zero general properties, the existence of sequences with prefixed zeros and some situations concerning the polynomials with multiple zeros.     

Hyperbolic rank and subexponential corank of metric spaces

We introduce a new quasi-isometry invariant corank X of a metric space X called subexponential corank. A metric space X has subexponential corank k if roughly speaking there exists a continuous map , T is a topological space, such that for each the set g ^-1(t) has subexponential growth rate in X and the topological dimension dimT = k is minimal among all such maps. Our main result is the inequality for a large class of metric spaces X including all locally compact Hadamard spaces, where rank _h X is the maximal topological dimension of among all CAT(—1) spaces Y quasi-isometrically embedded into X (the notion introduced by M. Gromov in a slightly stronger form). This proves several properties of rank _h conjectured by Gromov, in particular, that any Riemannian symmetric space X of noncompact type possesses no quasi-isometric embedding of the standard hyperbolic space H ⁿ with . Submitted: February 2001, Revised: October 2001.     

Approximating the zeros of analytic functions by the exclusion algorithm

We give a practical version of the exclusion algorithm for localizing the zeros of an analytic function and in particular of a polynomial in a compact of . We extend the real exclusion algorithm to a Jordan curve and give a method which excludes discs without any zero. The result of this algorithm is a set of discs arbitrarily small which contains the zeros of the analytic function.     

Finding a Cluster of Zeros of Univariate Polynomials

A method to compute an accurate approximation for a zero cluster of a complex univariate polynomial is presented. The theoretical background on which this method is based deals with homotopy, Newton's method, and Rouché's theorem. First the homotopy method provides a point close to the zero cluster. Next the analysis of the behaviour of the Newton method in the neighbourhood of a zero cluster gives the number of zeros in this cluster. In this case, it is sufficient to know three points of the Newton sequence in order to generate an open disk susceptible to contain all the zeros of the cluster. Finally, an inclusion test based on a punctual version of the Rouché theorem validates the previous step. A specific implementation of this algorithm is given. Numerical experiments illustrate how this method works and some figures are displayed.     

A simple quadrature-type method for the computation of real zeros of analytic functions in finite intervals

A new direct approximate method for the computation of zeros of analytic functions is proposed. For such a function possessing one real zero in a finite part of the real axis, this method permits the determination of this zero with a satisfactory accuracy by using a quite elementary algorithm. The present method is based on the Gauss- and Lobatto-Chebyshev quadrature rules for Cauchy type principal value integrals and is always convergent. The simplicity, accuracy and unrestricted convergence of the proposed method make it competitive to the analogous classical elementary methods. Numerical results are also presented.     

Low-temperature phase transitions in the quadratic family

We give the first example of a quadratic map having a phase transition after the first zero of the geometric pressure function. This implies that several dimension spectra and large deviation rate functions associated to this map are not (expected to be) real analytic, in contrast to the uniformly hyperbolic case. The quadratic map we study has a non-recurrent critical point, so it is non-uniformly hyperbolic in a strong sense.     

Sturm's Method in Counting Roots of Random Polynomial Equations

The problem of finding the probability distribution of the number of zeros in some real interval of a random polynomial whose coefficients have a given continuous joint density function is considered. An algorithm which enables one to express this probability as a multiple integral is presented. Formulas for the number of zeros of random quadratic polynomials and random polynomials of higher order, some coefficients of which are non-random and equal to zero, are derived via use of the algorithm. Finally, the applicability of these formulas in numerical calculations is illustrated.     

Chebyshev–Halley methods for analytic functions

Two modifications of the family of Chebyshev–Halley methods are given. The first is to improve the rate of convergence to a multiple zero of an analytic function. The second is to find simultaneously all distinct zeros of a polynomial.     

A one parameter family of locally quartically convergent zero-finding methods

A one parameter family of iteration functions for finding simple and multiple zeros of analytic functions is derived. The family includes, as a special case, Traub's quartic square root method and, as limiting cases, the Kiss method of order 4, the Halley and the Newton methods. All the methods of the family are locally quartically convergent for a simple or multiple zero with known multiplicity. The asymptotic error constants for the methods of the family are given. The decreasing ratio at infinity of iteration functions is discussed. The optimum parameter of the family for polynomials is given.     

Efficient solutions for weight-balanced partitioning problems

We prove polynomial-time solvability of a large class of clustering problems where a weighted set of items has to be partitioned into clusters with respect to some balancing constraints. The data points are weighted with respect to different features and the clusters adhere to given lower and upper bounds on the total weight of their points with respect to each of these features. Further the weight-contribution of a vector to a cluster can depend on the cluster it is assigned to. Our interest in these types of clustering problems is motivated by an application in land consolidation where the ability to perform this kind of balancing is crucial.Our framework maximizes an objective function that is convex in the summed-up utility of the items in each cluster. Despite hardness of convex maximization and many related problems, for fixed dimension and number of clusters, we are able to show that our clustering model is solvable in time polynomial in the number of items if the weight-balancing restrictions are defined using vectors from a fixed, finite domain. We conclude our discussion with a new, efficient model and algorithm for land consolidation.     

Removing multiplicities in by double newtonization

The graphical analysis of the zero level curves of the imaginary and real parts of a complex-valued analytic function f is used, both to localize the zeros of the function and to count their multiplicities. The comparison of the referred level curves with the zero level curves of F=f/f^′ (for which a multiple zero of f becomes simple) is made in order to predict good initial guesses for the iterative process defined by the iteration function N_f, which we called the double newtonization of f. This approach enables us to obtain high precision approximations for the zeros of f, regardless of their multiplicities. Several examples of analytic functions are presented to illustrate the results obtained. In these examples the occurrence of extraneous zeros is observed, and their location is in agreement with a classical theorem of Gauss–Lucas for polynomials.     

Improved two-step Newton’s method for computing simple multiple zeros of polynomial systems

Numerical Algorithms - Given a polynomial system f that is associated with an isolated singular zero ξ whose Jacobian matrix is of corank one, and an approximate zero x that is close to...     

The existence and local behaviour of the quadratic function approximation

This paper analyses the local behaviour of the quadratic function approximation to a function which has a given power series expansion about the origin. It is shown that the quadratic Hermite-Padé form always defines a quadratic function and that this function is analytic in a neighbourhood of the origin. This result holds even if the origin is a critical point of the function (i.e., the discriminant has a zero at the origin). If the discriminant has multiple zeros the order of the approximation will be degraded but only to a limited extent.     

New results on averaging theory and applications

The usual averaging theory reduces the computation of some periodic solutions of a system of ordinary differential equations, to find the simple zeros of an associated averaged function. When one of these zeros is not simple, i.e., the Jacobian of the averaged function in it is zero, the classical averaging theory does not provide information about the periodic solution associated to a non-simple zero. Here we provide sufficient conditions in order that the averaging theory can be applied also to non-simple zeros for studying their associated periodic solutions. Additionally, we do two applications of this new result for studying the zero–Hopf bifurcation in the Lorenz system and in the Fitzhugh–Nagumo system.     

Circular arithmetic and the determination of polynomial zeros

Summary Suppose all zeros of a polynomialp but one are known to lie in specified circular regions, and the value of the logarithmic derivativepp ^–1 is known at a point. What can be said about the location of the remaining zero? This question is answered in the present paper, as well as its generalization where several zeros are missing and the values of some derivatives of the logarithmic derivative are known. A connection with a classical result due to Laguerre is established, and an application to the problem of locating zeros of certain transcendental functions is given. The results are used to construct (i) a version of Newton's method with error bounds, (ii) a cubically convergent algorithm for the simultaneous approximation of all zeros of a polynomial. The algorithms and their theoretical foundation make use of circular arithmetic, an extension, based on the theory of Moebius transformations, of interval arithmetic from the real line to the extended complex plane.