No Period Two Implies Convergence, or Why Use Tangents When Secants Will Do

摘要

A familiar task is to solve f(x) = 0 given a continuously differentiable real function f. Newton's iteration could be tried; so could the Secant iteration. Except when the derivative f' costs appreciably less to evaluate than does f, the Secant iteration tends in practice to converge ultimately more efficiently than Newton's whenever both iterations converge to the desired root. When will they both converge. We find roughly that whenever Newton's iteration converges from every starting point in an interval I, so must the Secant iteration converge from every pair of starting points in I provided only that f actually reverses sign in I. This is an unexpected way for the Secant iteration to dominate Newton's.