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.     

The improved Farmer–Loizou method for finding polynomial zeros

An improvement of the Farmer–Loizou method for the simultaneous determination of simple roots of algebraic polynomials is proposed. Using suitable corrections of Newton's type, the convergence of the basic method is increased from 4 to 5 without any additional calculations. In this manner, a higher computational efficiency of the improved method is achieved. We prove a local convergence of the presented method under initial conditions which depend on a geometry of zeros and their initial approximations. Numerical examples are given to demonstrate the convergence behaviour of the proposed method and related methods.     

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.     

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 a generalisation of the root iterations for polynomial complex zeros in circular interval arithmetic

Consider a polynomialP (z) of degreen whose zeros are known to lie inn closed disjoint discs, each disc containing one and only one zero. Starting from the known simultaneous interval processes of the third and fourth order, based on Laguerre iterations, two generalised iterative methods in terms of circular regions are derived in this paper. These interval methods make use of the definition of thek-th root of a disc. The order of convergence of the proposed interval methods isk+2 (k≧1). Both procedures are suitable for simultaneous determination of interval approximations containing real or complex zeros of the considered polynomialP. A criterion for the choice of the appropriatek-th root set is also given. For one of the suggested methods a procedure for accelerating the convergence is proposed. Starting from the expression for interval center, the generalised iterative method of the (k+2)-th order in standard arithmetic is derived.     

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

The convergence of Euler-like method for the simultaneous inclusion of polynomial zeros

In this paper, we give the convergence analysis of the Euler-like iterative method for the simultaneous inclusion of all simple real or complex zeros of a polynomial. The established initial conditions provide the safe convergence of the considered method and the fourth order of convergence. These conditions are computationally verifiable, which is of practical importance. A procedure for the choice of initial inclusion disks is also given.     

On the convergence condition and convergence time of BGP

The Internet composes of thousands of Autonomous System (ASes). The Border Gateway Protocol (BGP) is the standard protocol for sharing inter-domain routing information. Unlike OSPF and IS-IS, BGP allows an AS to use a lot of attributes to express semantic rich routing policies that are consistent with its desired economic, business, performance, and security goals. However, the expressiveness could cause to delay convergence or even divergence in BGP. Recent work do not rigorously analyze the impact of the general routing policies on the convergence condition and convergence time of BGP, especially considering the widely used Multi-Exit Discriminator (MED) attribute. In this paper, we will fill this gap and give the rigorous analysis on the impact of the general routing policies on the convergence condition and convergence time of BGP, including MED attribute. We first introduce a timeless model to represent BGP with the general routing policies including the MED attribute. By incorporating the timeless model we derive a sufficient condition on these general routing policies for robust convergence of BGP. We then extend the timeless model to the real-time model by adding the edge delay. Finally, we find an upper bound on convergence time of BGP by incorporating the real-time model.     

Fourth-order two-step iterative methods for determining multiple zeros of non-linear equations

In this paper, we describe and analyse two two-step iterative methods for finding multiple zeros of non-linear equations. We prove that the methods have fourth-order convergence. The methods calculate the multiple zeros with high accuracy. These are the first two-step multiple zero finding methods. The numerical tests show their better performance in the case of algebraic as well as non-algebraic equations     

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 a geometric characterisation of zeros for non-square linear systems with time-delay in state

The concept of invariant zeros in a linear time-invariant system with point delay in state vector is discussed in the state space framework. These zeros are treated as the triples: complex number, non-zero state-zero direction and input-zero direction. Such treatment is strictly related to the output-zeroing problem and in that spirit the zeros can be easily interpreted. As is shown, for systems with matrix CB of full row-rank, general formulas for output-zeroing inputs can be obtained as well as a characterisation of invariant zeros as the roots of a certain quasi-polynomial can be given. The question of degeneracy/non-degeneracy of the system is also addressed. Moreover, it is shown that diagonal decoupling can be achieved by constant state feedbacks and a pre-compensator. The transfer matrix of the decoupled system is square and does not contain delay. The mathematical tools used in the analysis are the Moore–Penrose pseudo-inverse and singular value decomposition of a matrix.     

Finding the roots of a polynomial on an MIMD multicomputer

This paper introduces the parallelization on a distributed memory multicomputer of two iterative methods for finding all the roots of a given polynomial. The parallel algorithms share the computation of the roots among the processors and perform a total exchange of the data at each step. Since the amount of communications is the main drawback of this approach, we study the effect of the network topology on the performance of the algorithms. Particularly, we show that among the different classical processors networks topologies (ring, 2d-torus or n-cube), the hypercube topology minimizes the communications. For each topology is computed the optimal number of processors. Experiments on the hypercube FPS T40 illustrate the results.     

A comparison of the average case numerical condition of the power and bernstein polynomial bases

The relative numerical condition of a root x ₀, of arbitrary multiplicity, of a polynomial p(x) in the power and Bernstein bases is considered. The polynomial equation p(x)=0 and the linear algebraic equation that defines the transformation between the bases are used to show that the relative numerical condition of x ₀ in the bases is strongly dependent on the numerical condition of this equation. Furthermore, as the multiplicity of x _o increases for a given polynomial order, the relative numerical condition of x ₀ approaches unity. Computational examples that illustrate the theoretical results are presented.     

Further discussion on the calculation of transmission zeros

The transmission zeros of a previous reported boiler system example [1,2] are computed, using double and extended precision arithmetic on an IBM 370/165 digital computer, by the algorithm of [2].     

基于多项式展开的三角平动点垂直周期轨道解析构建方法研究

平动点是圆型限制性三体问题中的五个平衡解,其附近存在着大量的周期轨道,研究这些周期轨道的构建方法在深空探测中具有重要的理论及工程意义.本文从模态运动的角度出发,分析三角平动点附近周期轨道,通过多项式展开法构建出主坐标下周期轨道三个运动方向之间的渐近关系,从新的角度分析了系统的动力学特性和三维周期运动三个方向内在关联以及物理规律.同时可以为设计真实力学模型下的飞行器轨道提供借鉴.文中提出的方法可以被拓展至椭圆型限制性三体问题的三维周期轨道构建或共线平动点附近的轨道构建中.     

On the guaranteed convergence of a cubically convergent Weierstrass-like root-finding method

Initial conditions that provide guaranteed and fast convergence of the Weierstrass-like cubically convergent iterative method for the simultaneous determination of all simple zeros of a polynomial are considered. It is proved that this method is convergent under suitable conditions stated in the spirit of Smale's point estimation theory. The proposed convergence conditions are computationally verifiable since they depend only on initial approximations and the degree of a given polynomial, which is of practical importance.     

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

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.