A fitting algorithm for real coefficient polynomial rooting

A new algorithm for computing all roots of polynomials with real coefficients is introduced. The principle behind the new algorithm is a fitting of the convolution of two subsequences onto a given polynomial coefficient sequence. This concept is used in the initial stage of the algorithm for a recursive slicing of a given polynomial into degree-2 subpolynomials from which initial root estimates are computed in closed form. This concept is further used in a post-fitting stage where the initial root estimates are refined to high numerical accuracy. A reduction of absolute root errors by a factor of 100 compared to the famous Companion matrix eigenvalue method based on the unsymmetric QR algorithm is not uncommon. Detailed computer experiments validate our claims.     

Some variants of Hansen-Patrick method with third and fourth order convergence

Based on Hansen-Patrick method [E. Hansen, M. Patrick, A family of root finding methods, Numer. Math. 27 (1977) 257-269], we derive a two-parameter family of methods for solving nonlinear equations. All the methods of the family have third-order convergence, except one which has the fourth-order convergence. In terms of computational cost, all these methods require evaluations of one function, one first derivative and one second derivative per iteration. Numerical examples are given to support that the methods thus obtained are competitive with other robust methods of similar kind. Moreover, it is shown by way of illustration that the present methods, particularly fourth-order method, are very effective in high precision computations.     

Sixth-order variants of Chebyshev–Halley methods for solving non-linear equations

In this paper, we present a family of new variants of Chebyshev–Halley methods with sixth-order convergence. Compared with Chebyshev–Halley methods, the new methods require one additional evaluation of the function. The numerical results presented show that the new methods compete with Chebyshev–Halley methods.     

A generalization of Müller’s iteration method based on standard information

For finding a root of a function f, Müler’s method is a root-finding algorithm using three values of f in every step. The natural values available are values of f and values of its first number of derivatives, called standard information. Based on standard information, we construct an iteration method with maximal order of convergence. It is a natural generalization of Müller’s iteration method. This work was partially supported by National Natural Science Foundation of China (Grant No. 10471128), NSFC (Grant No. 10731060).     

On a simultaneous method of Newton-Weierstrass’ type for finding all zeros of a polynomial

Combining a suitable two-point iterative method for solving nonlinear equations and Weierstrass’ correction, a new iterative method for simultaneous finding all zeros of a polynomial is derived. It is proved that the proposed method possesses a cubic convergence locally. Numerical examples demonstrate a good convergence behavior of this method in a global sense. It is shown that its computational efficiency is higher than the existing derivative-free methods.     

A third-order modification of Newton’s method for multiple roots

In this paper, we present a new third-order modification of Newton’s method for multiple roots, which is based on existing third-order multiple root-finding methods. Numerical examples show that the new method is competitive to other methods for multiple roots.     

Discretization of implicit ODEs for singular root-finding problems

This paper addresses the use of dynamical system theory to tackle singular root-finding problems. The use of continuous-time methods leads to implicit differential systems when applied to singular nonlinear equations. The analysis is based on a taxonomy of singularities and uses previous stability results proved in the context of quasilinear implicit ODEs. The proposed approach provides a framework for the systematic formulation of quadratically convergent iterations to singular roots. The scope of the work includes also the introduction of discrete-time analysis techniques for singular problems which are based on continuous-time stability and numerical stability. Some numerical experiments illustrate the applicability of the proposed techniques.     

A new sixth-order scheme for nonlinear equations

In this paper we present a new efficient sixth-order scheme for nonlinear equations. The method is compared to several members of the family of methods developed by Neta (1979) [B. Neta, A sixth-order family of methods for nonlinear equations, Int. J. Comput. Math. 7 (1979) 157-161]. It is shown that the new method is an improvement over this well known scheme.     

McMullen's root-finding algorithm for cubic polynomials

We show that a generally convergent root-finding algorithm for cubic polynomials defined by C. McMullen is of order 3, and we give generally convergent algorithms of order 5 and higher for cubic polynomials. We study the Julia sets for these algorithms and give a universal rational map and Julia set to explain the dynamics.