Interpolation-based methods

• When a step produces an approximate result, you are free to carry it out approximately

Secant iteration:

\[ x_{k+1} = x_k - \frac{f(x_k)(x_k - x_{k-1})}{f'(x_k) - f(x_{k+1})},\quad k = 2,3,... \]

• converges at a rate strictly between linear and quadratic
• if function evaluations are used to measure work, secant iteration converges more rapidly than Newton’s method