
Proceedings
home
preface
contents
authors
keywords
copyright
reference
©2012 Civil-Comp Ltd |
 |
 |
 |
A. Cordero1, J.L. Hueso1, E. Martínez2 and J.R. Torregrosa1
1Institute for Multidisciplinary Mathematics, 2Institute for Pure and Applied de Mathematics,
Universitat Politècnica de València, Spain
Keywords: nonlinear equation, iterative method, order of convergence, optimality, Hermite polynomial, efficiency index.
full paper (pdf) -
reference
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.
|