Academic Commons


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
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.