Optimal Order and Efficiency for Iterations with Two Evaluations

Kung, H.T.; Traub, Josephe F.

The problem is to calculate a simple zero of a nonlinear function f. We consider rational iterations without memory which use two evaluations of f or its derivatives. It is shown that the optimal order is 2. This settles a conjecture of Kung and Traub that an iteration using n evaluations without memory is of order at most 2ⁿ⁻¹, for the case n=2. Furthermore we show that any rational two-evaluation iteration of optimal order must use either two evaluations of f or one evaluation of f and one of f'. From this result we completely settle the question of the optimal efficiency, in our efficiency measure, for any two-evaluation iteration without memory. Depending on the relative cost of evaluating f and f', the optimal efficiency is achieved by either Newton iteration or the iteration ᴪ.


  • thumnail for Traub__optimal_order_and_efficiency_for_iterations_with_two_evaluations.pdf Traub__optimal_order_and_efficiency_for_iterations_with_two_evaluations.pdf application/pdf 1.09 MB Download File

Also Published In

SIAM Journal on Numerical Analysis

More About This Work

Academic Units
Computer Science
Published Here
October 10, 2013