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 f0(x) be a function of one variable with a simple zero
at r0.
An iteration scheme is said to be locally convergent if, for some initial
approximation x1, ... , xk
near r0
and all functions f which are
sufficiently close (in a certain sense) to f0, the scheme
generates a
sequence (xk) which lies near r0
and converges to a zero r of f.
The order of convergence of the scheme is the infimum of the order of
convergence of (xk) for all such functions f.
We study iteration
schemes which are locally convergent and use only evaluations of
f, f', ... , fd
at x1, ... , xk-1 to determine
xk,
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