On the convergence order of a modified method for simultaneous finding polynomial zeros

Using Newton's corrections and Gauss-Seidel approach, a modification of single-step method [1] for the simultaneous finding all zeros of ann-th degree polynomial is formulated in this paper. It is shown thatR-order of convergence of the presented method is at least 2(1+τ _n ) where τ _n ∈(1,2) is the unique positive zero of the polynomial \(\tilde f_n (\tau ) = \tau ^n - \tau - 1\) . Faster convergence of the modified method in reference to the similar methods is attained without additional calculations. Comparison is performed in the example of an algebraic equation.     

On a second order method for the simultaneous inclusion of polynomial complex zeros in rectangular arithmetic

Starting from separated rectangles in the complex plane which contain polynomial complex zeros, an iterative method of second order for the simultaneous inclusion of these zeros is formulated in rectangular arithmetic. The convergence and a condition for convergence are considered. Applying Gauss-Seidel approach to the proposed method, two accelerated interval methods are formulated. TheR-order of convergence of these methods is determined. An analysis of the convergence order is given in the presence of rounding errors. The presented methods are illustrated numerically in examples of polynomial equations.     

On the convergence condition of generalized root iterations for the inclusion of polynomial zeros

Using a fixed point relation based on the logarithmic derivative of the k-th order of an algebraic polynomial and the definition of the k-th root of a disk, a family of interval methods for the simultaneous inclusion of complex zeros in circular complex arithmetic was established by Petković [M.S. Petković, On a generalization of the root iterations for polynomial complex zeros in circular interval arithmetic, Computing 27 (1981) 37–55]. In this paper we give computationally verifiable initial conditions that guarantee the convergence of this parallel family of inclusion methods. These conditions are significantly relaxed compared to the previously stated initial conditions presented in literature.     

The simultaneous determination of all zeros of a polynomial

A class of adaptive iterative methods of higher order for the simultaneous determination of all zeros of a polynomial is constructed. These methods preserve their order of convergence also in the case of multiple roots. Numerical examples are included.     

Higher-order simultaneous methods for the determination of polynomial multiple zeros

Starting from Laguerre's method and using Newton's and Halley's corrections for a multiple zero, new simultaneous methods of Laguerre's type for finding multiple (real or complex) zeros of polynomials are constructed. The convergence order of the proposed methods is five and six, respectively. By applying the Gauss–Seidel approach, these methods are further accelerated. The lower bounds of the R-order of convergence of the improved (single-step) methods are derived. Faster convergence of all proposed methods is attained with negligible number of additional operations, which provides a high computational efficiency of these methods. A detailed convergence analysis and numerical results are given.     

On the improved Newton-like methods for the inclusion of polynomial zeros

The aim of this paper is to present some modifications of Newton's type method for the simultaneous inclusion of all simple complex zeros of a polynomial. Using the concept of the R-order of convergence of mutually dependent sequences, the convergence analysis shows that the convergence rate of the basic method is increased from 3 to 6 using Jarratt's corrections. The proposed method possesses a great computational efficiency since the acceleration of convergence is attained with only few additional calculations. Numerical results are given to demonstrate convergence properties of the considered methods.     

Convergence conditions of some methods for the simultaneous computation of polynomial zeros

The convergence of Newton's, Aberth's and Durand–Kerner's methods for polynomial root finding is analyzed; for each of them convergence theorems and error estimates are provided. Received: December 1995 / Revised version: May 1996     

A family of simultaneous methods for the determination of polynomial complex zeros

Using the development of a rational function by elementary fractions, a family of methods for the simultaneous determination of polynomial complex zeros is derived. All the methods of the family are cubically convergent for simple zeros. The known simultaneous procedures of the third order are included. The presented class of iteration functions is suitable for the parallel inclusion of polynomial complex zeros by circular regions. The family of methods, defined in complex circular arithmetic, gives a new interval method with cubic convergence. Numerical example is given.     

On theR-order of some accelerated methods for the simultaneous finding of polynomial zeros

A Gauss-Seidel procedure is applied to increase the convergence of a basic fourth order method for finding polynomial complex zeros. Further acceleration of convergence is performed by using Newton's and Halley's corrections. It is proved that the lower bounds of theR-order of convergence for the proposed serial (single-step) methods lie between 4 and 7. Computational efficiency and numerical examples are also given.     

An improvement on two iteration methods for simultaneous determination of the zeros of a polynomial

The Durand-Kerner and the Ehrlich? Methods of respective quadratic and cubic convergence are two of the current methods for determining simultaneously all zeros of a polynomial. By respectively including a Durand-Kerner and a Newton correction term in the above formulae, we establish two new methods-the Improved Durand-Kerner and the Improved Ehrlich.

We show that the improvement is reflected by an increase of unity in the order of convergence of each of the two methods.     

A new proximity test for polynomial zeros

We combine some known techniques and results of Turan and Schönhage to improve substantially numerical performance of the computation of the minimum and the maximum distances from a fixed complex point to roots (zeros) of a fixed univariate polynomial.     

The simultaneous approximation of polynomial roots

We give new proofs of some known results concerning an iterative method of Newton type for the simultaneous calculation of all roots of a polynomial, originally proposed by Weierstrass [1]. The previously known local convergence analysis of the method is simplified and sharpened. We also propose a modified method with improved convergence properties. Global convergence of both methods is touched upon briefly.     

On the simultaneous calculation of two zeros

Differentiable functions are approximated by parabolas the zeros of which are approximations for two zeros of the function. Using the calculated zeros for the construction of new approximating parabolas, it arises an iteration method with quadratic convergence at single zeros.     

Optimal and nearly optimal algorithms for approximating polynomial zeros

We substantially improve the known algorithms for approximating all the complex zeros of an n^th degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schönhage [1], Pan [2], and Neff and Reif [3]. In parallel (NC) implementation, we dramatically decrease the number of processors, versus the parallel algorithm of Neff [4], which was the only NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable x has been scaled so as to confine the zeros of p(x) to the unit disc x : |x| ≤ 1, our algorithms (which promise to be practically effective) approximate all the zeros of p(x) within the absolute error bound 2^−b, by using order of n arithmetic operations and order of (b + n)n² Boolean (bitwise) operations (in both cases up to within polylogarithmic factors). The algorithms allow their optimal (work preserving) NC parallelization, so that they can be implemented by using polylogarithmic time and the orders of n arithmetic processors or (b + n)n² Boolean processors. All the cited bounds on the computational complexity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in the Boolean case, under the additional (realistic) assumption that n = O(b)).     

An algorithm for locating all zeros of a real polynomial

We present a globally convergent algorithm for calculating all zeros of a polynomialp _n ,p _n (z) = ∑ _{v = 0} ⁿ a _v z ^v, with real coefficients. Splittingp _n (exp(it)) into its real and imaginary part we can decide via Euclidean division of Chebyshev expansions and Sturm sequence argumentations whetherp _n has some zeros on the unit circle and how many zeros lie on the boundary and in the interior of it. Hence, by a bisection strategy we get the moduli of all zeros to a prescribed accuracy, and additionally we find the arguments as real zeros of a low degree polynomial. In this way we generate starting approximations for all zeros which in a final step are refined by an iterative process of higher order of convergence (e.g. Newton's or Bairstow's method).     

On the convergence of some methods for determining zeros of order-convex operators

LetF:X→Y be an order-convex operator, whereX, Y are partially ordered Banach spaces. Two related methods for the solution ofF(x)=0 are discussed, one of which has been studied by Pasquali (see [2]) and the other by Wolfe [12]. Existence-convergence theorems for the methods are given, and these are illustrated with the aid of example. Some remarks are also made on a method due to Traub [7] which has also been discussed by Wolfe [12].     

Schröder-like algorithms for multiple complex zeros of a polynomial

Using the iterative method of Newton's type in circular arithmetic, introduced in [14], a new iterative method for finding a multiple complex zero of a polynomial is derived. This method can be regarded as a version of classical Schröder's method. Initial conditions which guarantee a safe convergence of the proposed method are stated. The increase of the computational efficiency is achieved by a combination of the complex approximation methods of Schröder's type with some interval methods. The presented algorithms are analysed in view of their efficiency and illustrated numerically in the example of a polynomial equation.     

A modified algorithm for the simultaneous extraction of polynomial roots

A modification of Viswanathan's algorithm for the simultaneous extraction of polynomial roots is proposed. The Fletcher-Powell adaptation of Davidson's algorithm is used instead of the method of steepest descent used by Viswanathan. The modified algorithm is illustrated using the example treated by Viswanathan.     

A simple test for zeros of a complex polynomial in a sector

A simple proof of a recent result for determining whether the zeros of a real polynomial lie within a sector is first given. Secondly, this result is used in a procedure given for confirming whether or not the zeros of an arbitrary complex polynomial lie in a similar sector.