SOME HIGH-ORDER ZERO-FINDING METHODS USING ALMOST ORTHOGONAL POLYNOMIALS

RICHARD P. BRENT

Abstract

Some multipoint iterative methods without memory, for approximating simple zeros of functions of one variable, are described. For m > 0, n ≥ 0, and k satisfying m+1 ≥ k > 0, there exist methods which, for each iteration, use one evaluation of f, f′, …, f^{(m)}, followed by n evaluations of f^{(k)}, and have order of convergence m + 2n + 1. In particular, there are methods of order 2(n + 1) which use one function evaluation and n + 1 derivative evaluations per iteration. These methods naturally generalize the known cases n = 0 (Newton’s method) and n = 1 (Jarratt’s fourth-order method), and are useful if derivative evaluations are less expensive than function evaluations. To establish the order of convergence of the methods we prove some results, which may be of independent interest, on orthogonal and “almost orthogonal” polynomials. Explicit, nonlinear, Runge-Kutta methods for the solution of a special class of ordinary differential equations may be derived from the methods for finding zeros of functions. The theoretical results are illustrated by several numerical examples.

Comments

Only the Abstract is given here. The full paper appeared as [1]. For related work, see [2].

References

1. R. P. Brent, “Some high-order zero-finding methods using almost orthogonal polynomials”, J. Australian Mathematical Society (Series B) 19 (1975), 1–29. MR 52#16000, Zbl 333.65022. Also appeared as Efficient Methods for Finding Zeros of Functions whose Derivatives are Easy to Evaluate, Technical Report, Department of Computer Science, Carnegie-Mellon University (December 1974), 62 pp. rpb026.

2. R. P. Brent, “A class of optimal-order zero-finding methods using derivative evaluations”, in Analytic Computational Complexity (edited by J. F. Traub), Academic Press, 1975, 59–73. MR 52#15938, 54#9073; Zbl 342.65030. rpb027.

Computer Centre, Australian National University, Canberra, Australia

1991 Mathematics Subject Classification. Primary 65H05; Secondary 65D05, 65D20, 65D30, 65D32, 65L06, 65Y20.

Key words and phrases. Zero-finding, Newton’s method, Jarratt’s method, orthogonal polynomials, almost orthogonal polynomials, Runge-Kutta methods, ordinary differential equations.

Received 11 October 1974; revised 19 February 1975. The author thanks J. C. Butcher, M. R. Osborne and J. F. Traub for several useful comments on

earlier versions of this paper.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1975, Australian Mathematical Society. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb026a typeset using AMS-L^{A}TEX