Optimal Order of One-Point and Multipoint Iteration

TLDR

The paper addresses computing a simple zero of a nonlinear function by iteration, noting that the best previous result for four evaluations was fifth order. The authors conjecture that a multipoint iteration without memory based on n evaluations achieves the optimal order 2 n − 1. They present two families of multipoint iterations of order 2 n − 1: one using n evaluations of f without derivatives, and another using n − 1 evaluations of f plus one derivative evaluation. They construct an eighth‑order iteration with four evaluations and prove that the optimal order for a general class of multipoint iterations is 2 n − 1, with an upper bound of 2 n for derivative‑free schemes.

Abstract

The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2 n -1 which use n evaluations of ƒ and no derivative evaluations, as well as a second family of iterations of order 2 n -1 based on n — 1 evaluations of ƒ and one of ƒ′. In particular, with four evaluations an iteration of eighth order is constructed. The best previous result for four evaluations was fifth order. It is proved that the optimal order of one general class of multipoint iterations is 2 n -1 and that an upper bound on the order of a multipoint iteration based on n evaluations of ƒ (no derivatives) is 2 n . It is conjectured that a multipoint iteration without memory based on n evaluations has optimal order 2 n -1 .