On some improvements of square root iteration for polynomial complex zeros

Using Newton's and Halley's corrections, some modifications of the simultaneous method for finding polynomial complex zeros, based on square root iteration, are obtained. The convergence order of the proposed methods is five and six respectively. Further improvements of these methods are performed by applying the Gauss—Seidel approach. The lower bounds of the R-order of convergence and the convergence conditions for the accelerated (single-step) methods are given. Faster convergence is attained without additional calculations. The considered iterative procedures are illustrated numerically in the example of an algebraic equation.     

An iteration formula for the simultaneous determination of the zeros of a polynomial

The need for efficient algorithms for determining zeros of given polynomials has been stressed in many applications. In this paper we give a new cubic iteration method for determining simultaneously all the zeros of a polynomial (assumed distinct) starting with ‘reasonably close’ initial approximations (also assumed distinct).The polynomial is expressed as an expansion in terms of the starting and their correction terms.A formula which gives cubic convergence without involving second derivatives is derived by retaining terms up to second order of the expansion in the correction terms.Numerical evidence is given to illustrate the cubic convergence of the process.     

On some iteration functions for the simultaneous computation of multiple complex polynomial zeros

Second order methods for simultaneous approximation of multiple complex zeros of a polynomial are presented. Convergence analysis of new iteration formulas and an efficient criterion for the choice of the appropriate value of a root are discussed. A numerical example is given which demonstrates the effectiveness of the presented methods.     

On the location of the zeros of a generalized polynomial

A determinantal formula, based on an appropriate extension of the definition of subresultants, is derived for the location of the number of zeros of a generalized polynomial in the upper half plane.     

A basic family of iteration functions for polynomial root finding and its characterizations

Let p(x) be a polynomial of degree n?2 with coefficients in a subfield K of the complex numbers. For each natural number m?2, let L_m(x) be the m×m lower triangular matrix whose diagonal entries are p(x) and for each j=1,…,m−1, its jth subdiagonal entries are . For i=1,2, let L_m^i)(x) be the matrix obtained from L_m(x) by deleting its first i rows and its last i columns. L₁⁽¹⁾(x)≡1. Then, the function B_m(x)=x−p(x) defines a fixed-point iteration function having mth order convergence rate for simple roots of p(x). For m=2 and 3, B_m(x) coincides with Newton's and Halley's, respectively. The function B_m(x) is a member of S(m,m+n−2), where for any M?m, S(m,M) is the set of all rational iteration functions g(x) ∈ K(x) such that for all roots θ of p(x), then g(x)=θ+∑_i=m^Mγ_i(x)(θ−x)ⁱ, with γ_i(x) ∈ K(x) and well-defined at any simple root θ. Given g ∈ S(m,M), and a simple root θ of p(x), gⁱ(θ)=0, i=1, …, m−1 and the asymptotic constant of convergence of the corresponding fixed-point iteration is . For B_m(x) we obtain . If all roots of p(x) are simple, B_m(x) is the unique member of S(m,m + n − 2). By making use of the identity , we arrive at two recursive formulas for constructing iteration functions within the S(m,M) family. In particular, the family of B_m(x) can be generated using one of these formulas. Moreover, the other formula gives a simple scheme for constructing a family of iteration functions credited to Euler as well as Schröder, whose mth order member belongs to S(m,mn), m>2. The iteration functions within S(m,M) can be extended to any arbitrary smooth function f, with the uniform replacement of p^(j) with f^(j) in g as well as in γ_m(θ).     

On the zeros of a polynomial and its derivatives

If is univariate polynomial with complex coefficients having all its zeros inside the closed unit disk, then the Gauss-Lucas theorem states that all zeros of lie in the same disk. We study the following question: what is the maximum distance from the arithmetic mean of all zeros of to a nearest zero of ? We obtain bounds for this distance depending on degree. We also show that this distance is equal to for polynomials of degree 3 and polynomials with real zeros.

     

A moment approach to analyze zeros of triangular polynomial sets

Let be a zero-dimensional ideal of such that its associated set of polynomial equations for all is in triangular form. By introducing multivariate Newton sums we provide a numerical characterization of polynomials in . We also provide a necessary and sufficient (numerical) condition for all the zeros of to be in a given set , without explicitly computing the zeros. In addition, we also provide a necessary and sufficient condition on the coefficients of the 's for to have (a) only real zeros, (b) to have only real zeros, all contained in a given semi-algebraic set . In the proof technique, we use a deep result of Curto and Fialkow (2000) on the -moment problem, and the conditions we provide are given in terms of positive definiteness of some related moment and localizing matrices depending on the 's via the Newton sums of . In addition, the number of distinct real zeros is shown to be the maximal rank of a related moment matrix.

     

Interval iteration for zeros of systems of equations

Easily verifiable existence and convergence conditions are given for a class of interval iteration algorithms for the enclosure of a zero of a system of nonlinear equations. In particular, a quadratically convergent method is obtained which throughout the iteration uses the same interval enclosure of the derivative.     

A parallel wilf algorithm for complex zeros of a polynomial

A global recursive bisection algorithm is described for computing the complex zeros of a polynomial. It has complexityO(n ³ p) wheren is the degree of the polynomial andp the bit precision requirement. Ifn processors are available, it can be realized in parallel with complexityO(n ² p); also it can be implemented using exact arithmetic. A combined Wilf-Hansen algorithm is suggested for reduction in complexity.     

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.     

A posteriori error bound methods for the inclusion of polynomial zeros

Using Carstensen's results from 1991 we state a theorem concerning the localization of polynomial zeros and derive two a posteriori error bound methods with the convergence order 3 and 4. These methods possess useful property of inclusion methods to produce disks containing all simple zeros of a polynomial. We establish computationally verifiable initial conditions that guarantee the convergence of these methods. Some computational aspects and the possibility of implementation on parallel computers are considered, including two numerical examples. A comparison of a posteriori error bound methods with the corresponding circular interval methods, regarding the computational costs and sizes of produced inclusion disks, were given.     

A single oval of Cassini for the zeros of a polynomial

We derive two ovals of Cassini, each containing all the zeros of a polynomial. The computational cost to obtain these ovals is similar to that of the Brauer set for the companion matrix of a polynomial, although they are frequently smaller. Their derivation is based on the Gershgorin set for an appropriate polynomial of the companion matrix.     

Safe convergence of simultaneous methods for polynomial zeros

The theory of point estimation treating the initial conditions for the safe convergence of iterative processes for the simultaneous determination of polynomial zeros is considered. A general approach which makes use of corrections appearing in iterative formulas is given and demonstrated in the case of three well known methods without derivatives and based on Weierstrass’ corrections. The established convergence conditions are of practical importance since they depend only on available data: coefficients of a polynomial and initial approximations to the zeros. This revised version was published online in June 2006 with corrections to the Cover Date.     

Efficient methods for the inclusion of polynomial zeros

Using a suitable zero-relation and the inclusion isotonicity property, new interval iterative methods for the simultaneous inclusion of simple complex zeros of a polynomial are derived. These methods produce disks in the complex plane that contain the polynomial zeros in each iteration, providing in this manner an information about upper error bounds of approximations. Starting from the basic method of the fourth order, two accelerated methods with Newton’s and Halley’s corrections, having the order of convergence five and six respectively, are constructed. This increase of the convergence rate is obtained without any additional operations, which means that the methods with corrections are very efficient. The convergence analysis of the basic method and the methods with corrections is performed under computationally verifiable initial conditions, which is of practical importance. Two numerical examples are presented to demonstrate the convergence behavior of the proposed interval methods.     

On Cauchy's bound for zeros of a polynomial

In this paper we have improved Cauchy's bound for zeros of a polynomialp(z)=z ⁿ+a _n+1 z ^n-1+a _n-2 z ^n-2+......+a ₁ z+a ₀. Our result is best possible and sharpens some other results also.     

Convergence theorem for zeros of generalized Lipschitz generalized phi-quasi-accretive operators

Let be a uniformly smooth real Banach space and let be a mapping with . Suppose is a generalized Lipschitz generalized -quasi-accretive mapping. Let and be real sequences in [0,1] satisfying the following conditions: (i) ; (ii) ; (iii) ; (iv) Let be generated iteratively from arbitrary by

where is defined by and is an arbitrary bounded sequence in . Then, there exists such that if the sequence converges strongly to the unique solution of the equation . A related result deals with approximation of the unique fixed point of a generalized Lipschitz and generalized -hemi-contractive mapping.

     

The numerical radius and bounds for zeros of a polynomial

Let be a monic polynomial. We obtain two bounds for zeros of via the Perron root and the numerical radius of the companion matrix of the polynomial.

     

On a generalized Minkowski inequality and its relation to dominates for t-norms

Leth:?⁺ → ?⁺ be a continuous strictly increasing function withh(0) = 0. Such functionsh give rise to a generalization of the Minkowski inequality; namely, (1) $$h^{ - 1} (h(a + b) + h(c + d)) \leqq h^{ - 1} (h(a + c) + h(b + d))$$ wherea, b, c, andd are arbitrary non-negative real numbers. Theorem 1 shows that, ifh and logh′ (e ^x ) are both convex functions, thenh satisfies (1). Theorem 2, the major result, demonstrates that, if bothh ₁ andh ₂ satisfy the hypotheses of Theorem 1, then the composition ofh ₁ withh ₂ also satisfies the hypotheses of Theorem 1 and hence the inequality (1). The remainder of the paper shows how (1) and Theorems 1 and 2 impinge on the dominates relation for strict t-norms. In particular, Theorem 3 shows how (1) can be interpreted as equivalent to the dominates relation for two strict t-norms. Theorem 4 shows how to use Theorems 1 and 3 to construct a strict t-norm which dominates a given strict t-norm. And, Theorem 5 shows how Theorem 2 can be used to give a qualified answer of yes to the open question of whether or not the dominates relation is a transitive relation.     

The self-validated method for polynomial zeros of high efficiency

The improved iterative method of Newton’s type for the simultaneous inclusion of all simple complex zeros of a polynomial is proposed. The presented convergence analysis, which uses the concept of the R-order of convergence of mutually dependent sequences, shows that the convergence rate of the basic third order method is increased from 3 to 6 using Ostrowski’s corrections. The new inclusion method with Ostrowski’s corrections is more efficient compared to all existing methods belonging to the same class. To demonstrate the convergence properties of the proposed method, two numerical examples are given.