OPTIMAL ITERATIVE PROCESSES FOR ROOTFINDING

RICHARD BRENT, SHMUEL WINOGRAD, AND PHILIP WOLFE

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.

Comments

Only the Abstract is given here. The full paper appeared as [1] and was reprinted in [3, pages 225–239]. A preliminary version appeared as [2].

Errata

page 328, line 7: fεC^{2} ⇒ f ∈ C^{2} page 328, line 11: f′′(r) ≠ 0 ⇒ f′′(r) ≠ 0) page 329, line 7: which includes ⇒ whose centre is page 332, line 7: ∑_{j=1}(b_{j} + 1) ⇒ ∑_{j=1}^{k−1}(b_{j} + 1) page 332, line −9: S(s, e) ⇒ S(a, e) page 333, line 14: xeS ⇒ x ∈ S page 333, Lemma 1: f_{0}(r_{0}) = 0 ≠ f_{0}(r_{0}) ⇒ f_{0}(r_{0}) = 0 ≠ f′_{0}(r_{0}), e sufficiently small page 333, (4.5): xeS ⇒ x ∈ S page 334, line 5: S(t_{0}, e) ⇒ S(r_{0}, e) page 336, (5.15): (x_{k} − x_{j})^{b} ⇒ (x_{k} − x_{j})^{b_{j}} page 339, (6.7): h − 1 ⇒ k − 1 page 340, line 4 of §VII: calues ⇒ values

rpb016a typeset using AMS-L^{A}TEX.

1991 Mathematics Subject Classification. Primary 65Y20; Secondary 65H05, 65B99, 65D05.

Key words and phrases. Root-finding, zero-finding, analytic computational complexity, iteration schemes, order of convergence, interpolation.

This work was supported (in part) by the Office of Naval Research under contract numbers N0014-69-C-0023 and N0014-71-C-0112.

Received August 3, 1972.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1973, Springer-Verlag.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, 2000, R. P. Brent.

References

[1] 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. rpb016.

[2] R. P. Brent, S. Winograd and P. Wolfe, Optimal Iterative Processes for Rootfinding, Report RC3960, IBM T. J. Watson Research Laboratory, Yorktown Heights, New York, August 1972, 29 pp.

[3] R. P. Brent, Topics in computational complexity and the analysis of algorithms, Report TR-CS-80-14, DCS, ANU, October 1980, 375 pp. (D. Sc. thesis). rpb062.

Mathematical Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, New York