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

A third-order convergent iterative method for solving non-linear equations

In this paper, we present and analyse a new predictor-corrector iterative method for solving non-linear single variable equations. The convergence analysis establishes that the new method is cubically convergent. Numerical tests show that the method is comparable with the well-known existing methods and in many cases gives better results.     

Computation of nonconservative stability perturbation bounds forsystems with nonlinearly correlated uncertainties

Consideration is given to the problem of robust stability analysis of linear dynamic systems with uncertain physical parameters entering as polynomials in the state equation matrices. A method is proposed giving necessary and sufficient conditions for computing the uncertain system stability margin in parameter space, which provides a measure of maximal parameter perturbations preserving stability of the perturbed system around a known, stable, nominal system. A globally convergent optimization algorithm that enables solutions to the problem to be obtained is presented. Using the polynomial structure of the problem, the algorithm generates a convergent sequence of interval estimates of the global extremum. These intervals provide a measure of the accuracy of the approximating solution achieved at each step of the iterative procedure. Some numerical examples are reported, showing attractive features of the algorithm from the point of view of computational burden and convergence behavior     

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.     

Linear tracking-differentiator and application to online estimation of the frequency of a sinusoidal signal with random noise perturbation

A simple linear tracking-differentiator is proposed and the convergence proved for any differentiable signal with random perturbation to be tracked. This enables us to design a relatively simple globally convergent online estimator of the frequency of a sinusoidal signal under small random perturbation. The polynomial convergent rate is obtained.     

A modification of Muller’s method

Abstract It is well-known that Muller’s method for the computation of the zeros of continuous functions has order ≈ 1.84 [10], and does not have the character of global convergence. Muller’s method is based on the interpolating polynomial built on the last three points of the iterative sequence. In this paper the authors take as nodes of the interpolating polynomial the last two points of the sequence and the middle point between them. The resulting method has order p=2 for regular functions. This method leads to a globally convergent algorithm because it uses dichotomic techniques. Many numerical examples are given to show how the proposed code improves on Muller’s method.     

Convergence characterisation of an iterative algorithm for periodic Lyapunov matrix equations

This paper is concerned with convergence characterisation of an iterative algorithm for a class of reverse discrete periodic Lyapunov matrix equation associated with discrete-time linear periodic systems. Firstly, a simple necessary condition is given for this algorithm to be convergent. Then, a necessary and sufficient condition is presented for the convergence of the algorithm in terms of the roots of polynomial equations. In addition, with the aid of the necessary condition explicit expressions of the optimal parameter such that the algorithm has the fastest convergence rate are provided for two special cases. The advantage of the proposed approaches is illustrated by numerical examples.     

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.     

一种求解多项式根最大模的区间进化AFSA

针对多项式根的最大模求解问题,给出一种求解多项式根最大模的区间进化人工鱼群算法(AFSA)。该算法利用公告板上前后两代的信息,将搜索区间映射到更为有效的区域中,其搜索区间是动态的和进化的,从理论上证明该算法的收敛性。仿真实验结果表明,该算法在求多项式根最大模中是可行有效的,收敛速度快,求解精度高。     

Multigrid algorithms for $$\varvec{}$$-version interior penalty discontinuous Galerkin methods on polygonal and polyhedral meshes

In this paper we analyze the convergence properties of two-level and W-cycle multigrid solvers for the numerical solution of the linear system of equations arising from hp-version symmetric interior penalty discontinuous Galerkin discretizations of second-order elliptic partial differential equations on polygonal/polyhedral meshes. We prove that the two-level method converges uniformly with respect to the granularity of the grid and the polynomial approximation degree p, provided that the number of smoothing steps, which depends on p, is chosen sufficiently large. An analogous result is obtained for the W-cycle multigrid algorithm, which is proved to be uniformly convergent with respect to the mesh size, the polynomial approximation degree, and the number of levels, provided the number of smoothing steps is chosen sufficiently large. Numerical experiments are presented which underpin the theoretical predictions; moreover, the proposed multilevel solvers are shown to be convergent in practice, even when some of the theoretical assumptions are not fully satisfied.     

The Steiglitz-McBride identification algorithm revisited--Convergence analysis and accuracy aspects

The convergence and accuracy properties of the Steiglitz and McBride identification method are examined. The analysis is valid for a sufficiently large number of data. It is shown that the method can converge to the true parameter vector only when the additive output noise is white. In that case the method is proved to be locally convergent to the true parameters. The global convergence properties are also investigated. It is pointed out that the method is not always globally convergent. Some sufficient conditions guaranteeing global convergence are given. Assuming convergence takes place the estimates are shown to be asymptotically Gaussian distributed. An explicit expression is given for their asymptotic covariance matrix.     

Enclosing the solutions of nonlinear systems of equations

The quadratically convergent Newton-type methods and its variants are generally used for solving the nonlinear systems of equations. Most of these methods use the convexity conditions [7] of the involved bounded linear operators for their convergence. Alefeld and Herzberger [1] have proposed a quadratically convergent iterative method for enclosing the solutions of the special type of nonlinear system of equations arising from the discretization of nonlinear boundary value problems which do not require the convexity conditions but uses the subinverses of the bounded linear operators. In this paper, we have proposed a modification of this method which takes it further faster. The proposed method uses bom the superinverses and subinverses of bounded linear operators. At the expense of slightly more computations than used in [1], the rate of convergence of our method enhances from quadratic to cubic. Finally, the method is tested on a numerical example.     

On the computational complexity of binary and analog symmetric hopfield nets

We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this problem in the case of binary nets. Finally, we show that symmetric analog nets with an external clock are computationally Turing universal.     

Bounds for an interval polynomial

We discuss the evaluation of the range of values of an interval polynomial over an interval. Several algorithms are proposed and tested on numerical examples. The algorithms are based on ideas by Cargo and Shiska [2] and Rivlin [4]. The one basic algorithm uses Bernstein polynomials. It is shown to converge to the exact bounds and it has furthermore the property that if the maximum respectively the minimum of the polynomials occurs at an endpoint of the interval then the bound is exact. This is a useful property in routines for polynomials zeros. The other basic method is based on the meanvalue theorem and it has the advantage that the degree of approximation required for a certain apriori tolerance is smaller than the degree required in the Bernstein polynomial case. The mean value method is shown to be at least quadratically convergent and the Bernstein polynomial method is shown to be at least linearly convergent.     

合同网协议协商机制收敛性与收敛速率分析

针对合同网协议协商机制缺乏问题求解质量与效率分析的情况,设定假设条件,构建马尔可夫链模型,得出了利用目前已有的合同类型无法保证全局收敛的结论.在此基础上,提出了变邻域合同系的概念,通过分析控制方式对收敛性的影响,得出了集中式控制可以保证全局收敛以及分布式控制以概率保证全局收敛的结论,并设计了概率的计算方法.采用Doebin理论,对应用变邻域合同系的收敛速率进行分析,得出了集中式控制收敛速率与分布式控制收敛速率的上下界估计.     

Boundedness and convergence of online gradient method with penalty and momentum

In this paper, the deterministic convergence of an online gradient method with penalty and momentum is investigated for training two-layer feedforward neural networks. The monotonicity of the new error function with the penalty term in the training iteration is firstly proved. Under this conclusion, we show that the weights are uniformly bounded during the training process and the algorithm is deterministically convergent. Sufficient conditions are also provided for both weak and strong convergence results.     

Analysis of asynchronous polynomial root finding methods on adistributed memory multicomputer

We have studied various implementations of iterative polynomial root finding methods on a distributed memory multicomputer. These methods are based on the construction of a sequence of approximations that converge to the set of zeros. The synchronous version consists in sharing the computation of the next iterate among the processors and updating their data through a total exchange of their results. In order to decrease the communication cost, we introduce asynchronous versions. The computation of the next iterate is still shared among the processor, but the updating is done by using only nearest neighbor communications. We prove that under weak conditions, these asynchronous versions are still locally convergent, even if their convergence orders are reduced. We analyze the behavior of the asynchronous methods in function of their delay, the topology of the interconnection network, and the elementary computation and communication times. We have implemented and compared these methods on a hypercube multicomputer     

A method for high-order multipoint boundary value problems with Birkhoff-type conditions

In this paper an efficient numerical method for solving a class of multipoint boundary value problems with special boundary conditions of Birkhoff-type is presented. After a quick reference to Birkhoff-type interpolation polynomial which satisfies the particular conditions, and a result on the existence and uniqueness of solution of the given problem, an algorithm is introduced to find a polynomial that approximates the solution. It is a general collocation method. Then an a priori estimation of the error of this approximation is given. Finally, to show the efficiency and the applicability of the method, numerical results are presented. These numerical experiments provide favourable comparisons with the NDSolve command of Mathematica.