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.     

An iterative method for algebraic equation by Padé approximation

In this paper, we consider iterative formulae with high order of convergence to solve a polynomial equation,f(z)=0. First, we derive the numerator of the Padé approximant forf(z)/f′(z) by combining Viscovatov's and Euclidean algorithms, and then calculate the zeros of the numerator so as to apply one of the zeros for the next approximation. Regardless of whether the root is simple or multiple, the convergence order of this iterative formula is always attained for arbitrary positive integerm with the Taylor polynomial of degreem for a given polynomialf(z). Since it is easy to systematically obtain formulae of different order, we can choose formulae of suitable order according to the required accuracy.     

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 the positivity of cotes numbers for interpolatory quadratures with Jacobi abscissas

For interpolatory quadrature rules having abscissas at the zeros of then-th Jacobi polynomialP _n ^(α,β) (x), we show by counterexample that positive Cotes numbers do not exist for all ?1<α,β≤3/2.     

Polynomial root finding by means of continuation

In this paper we deal with the problem of locating all the zeros of a given polynomialp(x) and approximating them to any degree of precision: by combining classical iterative methods with homotopy path tracking techniques, we introduce a new algorithm for polynomial root finding, prove its convergence and estimate its computational cost.     

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).     

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     

A practical algorithm to design fast and optimal band-Toeplitz preconditioners for hermitian toeplitz systems

In this paper we are concerned with the iterative solution ofn×n Hermitian Toeplitz systems by means of preconditioned conjugate gradient (PCG) methods. In many applications [9] such as signal processing [24], differential equations [39], linear prediction of stationary processes [18], the related Toeplitz systems have the formA _n (f)x=b where the symbolf, the generating function, is anL ¹ function and the entries ofA _n (f) along thek-th diagnonal coincide with thek-th Fourier coefficient off. When the essential range of the generating function has a convex hull containing zero, the matricesA _n (f) are asymptotically ill-conditioned [21, 33, 28] and circulant or Hartley preconditioners do not work [15]. For this difficult case the only optimal preconditioners in the sense of [3, 29] are found in the τ algebra [15, 35] and especially in the band Toeplitz matrix class [7, 16]. In particular the band Toeplitz preconditioning strategy has been shown to be the most flexible one since it allows one to treat the nonnegative case [7, 16, 11, 31], the nondefinite one [27, 30, 34, 26]. On the other hand, the main criticism to this approach is surely the assumption that we must know the position and the order of the zeros off: in some applicative fields this is a feasible assumption, in other applications it is merely a theoretical possibility. Therefore, we discuss an economical technique in order to discover the sign off, the position of the possible zeros of the generating function and to evaluate approximately the order of these zeros. Finally, we exhibit some numerical experiments which confirm the effectiveness of the proposed idea.     

The root and Bell’s disk iteration methods are of the same error propagation characteristics in the simultaneous determination of the zeros of a polynomial,Part II: Round-off error analysis by use of interval arithmetic

In Part I (Ikhile, 2008) [4], it was established that the root and Bell’s disk/point iteration methods with or without correction term are of the same asymptotic error propagation characteristics in the simultaneous determination of the zeros of a polynomial. This concluding part of the investigation is a study in round-offs, its propagation and its effects on convergence employing interval arithmetic means. The purpose is to consequently draw attention on the effects of round-off errors introduced from the point arithmetic part, on the rate of convergence of the generalized root and Bell’s simultaneous interval iteration algorithms and its enhanced modifications introduced in Part I for the numerical inclusion of all the zeros of a polynomial simultaneously. The motivation for studying the effects of round-off error propagation comes from the fact that the readily available computing devices at the moment are limited in precision, more so that accuracy expected from some programming or computing environments or from these numerical methods are or can be machine dependent. In fact, a part of the finding is that round-off propagation effects beyond a certain controllable order induces overwhelmingly delayed or even a severely retarded convergence speed which manifest glaringly as poor accuracy of these interval iteration methods in the computation of the zeros of a polynomial simultaneously. However, in this present consideration and even in the presence of overwhelming influence of round-offs, we give conditions under which convergence is still possible and derive the error/round-off relations along with the order/$R$-order of convergence of these methods with the results extended to similar interval iteration methods for computing the zeros of a polynomial simultaneously, especially to Bell’s interval methods for refinement of zeros that form a cluster. Our findings are instructive and quite revealing and supported by evidence from numerical experiments. The analysis is preferred in circular interval arithmetic.     

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 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.     

Unified convergence analysis for Picard iteration in <Emphasis Type="Italic">n</Emphasis>-dimensional vector spaces

In this paper, we provide three types of general convergence theorems for Picard iteration in n-dimensional vector spaces over a valued field. These theorems can be used as tools to study the convergence of some particular Picard-type iterative methods. As an application, we present a new semilocal convergence theorem for the one-dimensional Newton method for approximating all the zeros of a polynomial simultaneously. This result improves in several directions the previous one given by Batra (BIT Numer Math 42:467–476, 2002).     

On the equivalence of the k-step iterative euler methods and successive overrelaxation (SOR) methods for k-cyclic matrices

For the solution of the linear system x = Tx + c (1), where T is weakly cyclic of index k ≥ 2, the block SOR method together with two classes of monoparametric k-step iterative Euler methods, whose (optimum) convergence properties were studied in earlier papers, are considered. By establishing the existence of the matrix analog of the Varga's relation, connecting the eigenvalues of the SOR and the Jacobi matrices associated with (1), it is proved that the aforementioned SOR method is equivalent to a certain monoparametric k-step iterative Euler method derived from (1). By suitably modifying the existing theory, one can then determine (optimum) relaxation factors for which the SOR method in question converges, (optimum) regions of convergence etc., so that one can obtain, what is known, several new results. Finally, a number of theoretical applications of practical importance is also presented.     

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.     

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.     

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.     

A family of simultaneous zero finding methods

A class of iterative methods with arbitrary high order of convergence for the simultaneous approximation of multiple complex zeros is considered in this paper. A special attention is paid to the fourth order method and its modifications because of their good computational efficiency. The order of convergence of the presented methods is determined. Numerical examples are given.     

A class of single-input single-output systems stabilizable by reduced-order controllers

Let the Euclidian algorithm be applied to the numerator and denominator polynomial of an n-th order system transfer function. It isshown that there exists an (n − 1 − k)-nt order stabilizing controller provided one of the remainder polynomials occuring in the algorithm is a k-th order Hurwitz polunomial. The controller is constructed using almost disturbance decoupling techniques. The result specifies an algebraic condition under which a reduced-order controller can be determined using a reduced-order model obtained by minimal partial realization or a certain continued-fraction expansion.     

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.     

A family of root-finding methods with accelerated convergence

A parametric family of iterative methods for the simultaneous determination of simple complex zeros of a polynomial is considered. The convergence of the basic method of the fourth order is accelerated using Newton's and Halley's corrections thus generating total-step methods of orders five and six. Further improvements are obtained by applying the Gauss-Seidel approach. Accelerated convergence of all proposed methods is attained at the cost of a negligible number of additional operations. Detailed convergence analysis and two numerical examples are given.