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.     

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.     

Halley-Like Method with Corrections for the Inclusion of Polynomial Zeros

In this paper we present iteration methods of Halley'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 for the total-step and the single-step methods with Newton's corrections. The suggested algorithms possess a great computational efficiency since the increase of the convergence rate is attained without additional calculations. A numerical example is given. Received: June 23, 1998     

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.     

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.     

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.     

Some variants of the Chebyshev–Halley family of methods with fifth order of convergence

In this paper we present some techniques for constructing high-order iterative methods in order to approximate the zeros of a non-linear equation f(x)=0, starting from a well-known family of cubic iterative processes. The first technique is based on an additional functional evaluation that allows us to increase the order of convergence from three to five. With the second technique, we make some changes aimed at minimizing the calculus of inverses. Finally, looking for a better efficiency, we eliminate terms that contribute to the error equation from sixth order onwards.

The paper contains a comparative study of the asymptotic error constants of the methods and some theoretical and numerical examples that illustrate the given results. We also analyse the efficiency of the aforementioned methods, by showing some numerical examples with a set of test functions and by using adaptive multi-precision arithmetic in the computation.     

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.     

Root-finding by expansion with independent constraints

Elimination methods are highly effective for the solution of linear and nonlinear systems of equations, but reversal of the elimination principle can be beneficial as well: competent incorporation of additional independent constraints and variables or more generally immersion of the original computational problem into a larger task, defined by a larger number of independent constraints and variables can improve global convergence of iterative algorithms, that is their convergence from the start. A well known example is the dual linear and nonlinear programming, which enhances the power of optimization algorithms. We believe that this is just an ad hoc application of general Principle of Expansion with Independent Constraints; it should be explored systematically for devising iterative algorithms for the solution of equations and systems of equations and for optimization. At the end of this paper we comment on other applications and extensions of this principle.Presently we show it at work for the approximation of a single zero of a univariate polynomial p of a degree n. Empirical global convergence of the known algorithms for this task is much weaker than that of the algorithms for all n zeros, such as Weierstrass–Durand–Kerner’s root-finder, which reduces its root-finding task to Viète’s (Vieta’s) system of n polynomial equations with n unknowns. We adjust this root-finder to the approximation of a single zero of p, preserve its fast global convergence and decrease the number of arithmetic operations per iteration from quadratic to linear. Together with computing a zero of a polynomial p, the algorithm deflates this polynomial as by-product, and then could be reapplied to the quotient to approximate the next zero of p. Alternatively by using m processors that exchange no data, one can concurrently approximate up to m zeros of p. Our tests confirm the efficiency of the proposed algorithms.Technically our root-finding boils down to computations with structured matrices, polynomials and partial fraction decompositions. Our study of these links can be of independent interest; e.g., as by-product we express the inverse of a Sylvester matrix via its last column, thus extending the celebrated result of Gohberg and Sementsul (1972) [22] from Toeplitz to Sylvester matrix inverses.     

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.     

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     

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.     

Preconditioned Descent Algorithms for p-Laplacian

In this paper, we examine some computational issues on finite element discretization of the p-Laplacian. We introduced a class of descent methods with multi-grid finite element preconditioners, and carried out convergence analysis. We showed that their convergence rate is mesh-independent. We studied the behavior of the algorithms with large p. Our numerical tests show that these algorithms are able to solve large scale p-Laplacian with very large p. The algorithms are then used to solve a variational inequality.      

Comparing parallel Newton''s method with parallel Laguerre''s method

Newton's and Laguerre's methods can be used to concurrently refine all separated zeros of a polynomial P(z). This paper analyses the rate convergence of both procedures, and its implication on the attainable number n of correct figures. In two special cases the number m of iterations required to reach an accuracy η = 10⁻ⁿ is shown to grow as log_λ n, where λ = 3 for Newton's and λ = 4 for Laguerre's. In the general case m is shown to grow linearly with n for both procedures. An assessment of the efficiency of the two methods is also given, by evaluating the computational complexity of operations in circular arithmetic, and the efficiency indices of the two iterative schemes.     

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.     

A niching genetic k-means algorithm and its applications to gene expression data

Partitional clustering is a common approach to cluster analysis. Although many algorithms have been proposed, partitional clustering remains a challenging problem with respect to the reliability and efficiency of recovering high quality solutions in terms of its criterion functions. In this paper, we propose a niching genetic k-means algorithm (NGKA) for partitional clustering, which aims at reliably and efficiently identifying high quality solutions in terms of the sum of squared errors criterion. Within the NGKA, we design a niching method, which encourages mating among similar clustering solutions while allowing for some competitions among dissimilar solutions, and integrate it into a genetic algorithm to prevent premature convergence during the evolutionary clustering search. Further, we incorporate one step of k-means operation into the regeneration steps of the resulted niching genetic algorithm to improve its computational efficiency. The proposed algorithm was applied to cluster both simulated data and gene expression data and compared with previous work. Experimental results clear show that the NGKA is an effective clustering algorithm and outperforms two other genetic algorithm based clustering methods implemented for comparison.     

Synchronous and Asynchronous Interval Newton-Schwarz Methods for a Class of Large Systems of Nonlinear Equations

We introduce a class of parallel interval arithmetic iteration methods for nonlinear systems of equations, especially of the type Ax+(x) = f, diagonal, in R ^N . These methods combine enclosure and global convergence properties of Newton-like interval methods with the computational efficiency of parallel block iteration methods: algebraic forms of Schwarz-type methods which generalize both the well-known additive algebraic Schwarz Alternating Procedure and multisplitting methods. We discuss both synchronous and asynchronous variants. Besides enclosure and convergence properties, we present numerical results from a CRAY T3E.     

Fast multilevel augmentation method for nonlinear integral equations

In this study, we extend the multilevel augmentation method for Hammerstein equations established in Chen et al. [Fast multilevel augmentation methods for solving Hammerstein equations, SIAM J. Numer. Anal. 47 (2009), pp. 2321–2346] to solve nonlinear Urysohn integral equations. Under certain differentiability assumptions on the kernel function, we show that the method enjoys the optimal convergence order and linear computational complexity. Finally, numerical experiments are presented to confirm the theoretical results and illustrate the efficiency of the method.     

An iterative method for the computation of the solutions of nonlinear equations

In this paper, we present new iterative methods for the computation of zeros of C ¹ functions. The idea is mainly based on a new asymptotic expansion (the Bernoulli expansion) for regular functions. Just as the Newton method is derived from the linear part of the Taylor polynomial, the new methods are analogously derived from the quadratic part of the Bernoulli expansion. We prove that the proposed procedures combine the assured convergence of bisection-like algorithms with a superlinear convergence speed which characterizes Newton-like methods. We show that the order of this new procedure is p= 2 and that the cost per iteration is completely equivalent to that of the Newton method. Finally some numerical experiments are performed. The related results seem to indicate that at least one of the proposed techniques works better than the Newton method. Moreover, the given method used in connection with an enclosing-interval procedure [2], is competitive with the ones recently proposed by Alefeld and Potra [2]. Received: July 1997 / Accepted: January 1998