Zero-Cost Enhancement of the Steffensen Method for Nonlinear Equations

The Steffensen method is a very effective root-finding procedure used for solving nonlinear equations of the form f(x)=0 numerically. When the root of f(x) is simple, this method converges with order 2. Following a critical review of its convergence analysis, in this work, we provide a modification with memory of the Steffensen method, which achieves an order substantially higher than 2, without increasing the number of function evaluations per iteration. Specifically, with an arbitrary fixed integer k≥1 and with initial approximations x0,x1,…,xk, the modified method generates a sequence of approximations to the solution of f(x)=0 via xn+1=xn−f(xn)/f[cn,xn], n=k,k+1,…, where cn=xn−f(xn)/pn,k′(xn) and pn,k(x) is the polynomial of interpolation to f(x) at the points xn,xn−1,…,xn−k. Just as in the original method, the modified method makes use of only f(x); no derivatives of f(x) are needed. We prove that the order of this method is 1+2=˙2.414 for k=1 and it can be increased towards (3+5)/2=˙2.618 by increasing k. (For example, the order of the method is 2.617⋯ already for k=6.)