Keywords: nonlinear equation, iterative method, order of convergence, optimality, Hermite polynomial, efficiency index.

In this paper the problem of finding a real solution of a nonlinear equation (f(x)=0)is considered. The most well known iterative scheme is the classical Newton's method. It is understood that this method has quadratic convergence, under some conditions, and it uses two functional evaluations per step.

A known acceleration technique consists of the composition of two iterative methods of order p and q, respectively, to obtain a method of order pq [1]. Usually, new evaluations of the function or its derivatives are needed to increase the order of convergence. In order to compare different methods, it is very common to use the efficiency index, introduced by Ostrowski [2], which involves the order of convergence and the number of functional evaluations per step required by the method.

Kung and Traub [3] conjectured that an iterative method, without memory, that uses n+1 functional evaluations per iteration can have at most a convergence order 2 up to n. If this bound is reached, the method is said to be optimal.

General procedures to obtain families of optimal multipoint iterative methods for every n were given in [3,4]. Recently, different optimal iterative methods of order eight or sixteen have been published in several journals.

In this work, a family of iterative schemes is presented for solving nonlinear equations with order of convergence 2 up to n, by using n+1 functional evaluations per step, so these methods are optimal in the sense of Kung-Traub's conjecture. The family is obtained by composing n Newton's steps and approximating the derivative of f(x) by the derivative of a polynomial that is obtained using already computed function values, namely, the Hermite's interpolation polynomial. In addition to the convergence theorem, an explicit formula for the computation of the approximated derivative, is derived, that avoids the solution of a linear system in each step of the iteration.

The effectiveness of the new optimal iterative schemes, is checked, by comparing them with the optimal family introduced by Kung and Traub [3]. The numerical tests confirm the theoretical results and show that the new family has a slightly better performance than the classical one, so it can be competitive.

1

J.F. Traub, "Iterative methods for the solution of equations", Chelsea Publishing Company, New York, 1982.

2

A.M. Ostrowski, "Solutions of equations and systems of equations", Academic Press, New York-London, 1966.

3

H.T. Kung, J.F. Traub, "Optimal order of one-point and multi-point iteration", Journal of the Association for Computing Machinery, 21, 643-651, 1974.

4

B. Neta, "On a family of multipoint methods for non-linear equations", International Journal for Computation and Mathematics, 9, 353-361, 1981. doi:10.1080/00207168108803257

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £50 +P&P)