## Optimal Iterative Processes for Rootfinding

16. R. P. Brent, S. Winograd and P. Wolfe,
Optimal iterative processes for rootfinding,
* Numerische Mathematik* 20 (1973), 327-341.
CR 15#26753,
MR 47#6079.
Abstract and errata:
dvi (2K),
pdf (30K),
ps (33K).

Paper:
pdf (1262K).

Errata:
pdf (35K).

## Abstract

Let *f*_{0}(x) be a function of one variable with a simple zero
at *r*_{0}.
An iteration scheme is said to be locally convergent if, for some initial
approximation *x*_{1}, ... , x_{k}
near *r*_{0}
and all functions *f* which are
sufficiently close (in a certain sense) to *f*_{0}, the scheme
generates a
sequence *(x*_{k}) which lies near *r*_{0}
and converges to a zero *r* of *f*.
The order of convergence of the scheme is the infimum of the order of
convergence of *(x*_{k}) for all such functions *f*.
We study iteration
schemes which are locally convergent and use only evaluations of
*f, f', ... , f*^{d}
at *x*_{1}, ... , x_{k-1} to determine
*x*_{k},
and we show that no such scheme has order greater than *d+2*.
This bound is the best possible, for it is attained by certain schemes
based on polynomial interpolation.
Go to next publication

Return to Richard Brent's index page