GuideNonlinear equationsintermediate

Derivative-free methods: secant and Steffensen

When f′f' is unavailable it is replaced by a divided difference: with two previous iterates (secant, order ≈1.618\approx1.618) or with an auxiliary evaluation (Steffensen, order 2).

Replacing the derivative

If the derivative of ff is unknown or expensive to evaluate, the general recipe is to replace it in Newton's formula by a divided difference. Depending on which points are used, two classic methods appear.

Secant method

The secant approximates f′(xk)f'(x_k) with the slope between the last two iterates, f[xk,xk−1]=f(xk)−f(xk−1)xk−xk−1f[x_k,x_{k-1}]=\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}: it is a method with memory that needs two initial estimates.

xk+1=xk−f(xk)f[xk,xk−1],k=1,2,…x_{k+1}=x_k-\frac{f(x_k)}{f[x_k,x_{k-1}]},\qquad k=1,2,\dots
Secant method.

Steffensen's method

Steffensen avoids memory by evaluating ff at an auxiliary point built with the function itself: it approximates f′(xk)≈f(xk+f(xk))−f(xk)f(xk)f'(x_k)\approx\frac{f(x_k+f(x_k))-f(x_k)}{f(x_k)}. Substituting into Newton:

xk+1=xk−f(xk)2f(xk+f(xk))−f(xk),k=0,1,2,…x_{k+1}=x_k-\frac{f(x_k)^2}{f\bigl(x_k+f(x_k)\bigr)-f(x_k)},\qquad k=0,1,2,\dots
Steffensen's method: order 2 without derivatives.

It keeps Newton's order 2 without using f′f', at the cost of two evaluations of ff per iteration. The same idea of replacing derivatives by divided differences reappears when solving nonlinear systems.