Some high-order zero-finding methods using almost orthogonal polynomials

26. 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.

Abstract: dvi (2K), pdf (82K).

Paper: pdf (1000K).


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.


For a related paper, see Brent [27].

Go to next publication

Return to Richard Brent's index page