Efficient and stable derivative-free Steffensen algorithm for root finding

Alexandre Wagemakers, Vipul Periwal · 2025

Read Efficient and stable derivative-free Steffensen algorithm for root finding by Alexandre Wagemakers, Vipul Periwal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10402.txt.

Introduction

Alexandre Wagemakers and Vipul Periwal wrote a mathematics paper in 2025 on finding roots of functions without using derivatives. Their methods grow out of a classic iterative scheme based on divided differences. The family reaches second-order convergence with two function values per step, at small extra cost. A side gain is better stability across starting points than the classic scheme.

The authors present results for single functions, for fields, and for scalar fields. By standard measures, the new family beats the classic method in most cases. The paper frames the methods as an efficient and stable option for root finding when derivatives are costly or not available.

Catalog record

CREATORAlexandre Wagemakers, Vipul Periwal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-10402

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient and stable derivative-free Steffensen algorithm for root finding Alexandre Wagemakers, Vipul Periwal Abstract We explore a family of numerical methods, based on the Steffensen divided difference iterative algorithm, that do not evaluate the derivative of the objective functions. The family of methods achieves second-order convergence with two function evaluations per iteration with marginal additional computational cost. An important side benefit of the method is the improvement in stability for different initial conditions compared to the vanilla Steffensen method. We present numerical results for scalar functions, fields, and scalar fields. This family of methods outperforms the Steffensen method with respect to standard quantitative metrics in most cases. Journal: JMAA 1 Introduction Finding roots of nonlinear functions is a common task in engineering and science. Iterative algorithms are the preferred method to solve such problems, and there is an extensive literature on adapting and implementing methods for specific cases, e.g. [ 1 , 2 , 3 , 4 ] . However, there is still room for improvement in convergence and efficiency for root finding methods. Another challenge is the difficulty of computing or evaluating the derivative of the objective function when it is even possible. In these situations, we must aim for a method avoiding the derivative while keeping the function evaluations as few as possible. Among the simplest iterative algorithms to find roots without differentiating a function, a popular choice is the Steffensen method. This is a simple modification of the Newton iterative method, where the derivative of the function f is replaced by the first-order divided difference requiring only two function evaluations. The Kung-Traub bound, also known as the Kung-Traub conjecture, states that an optimal iterative method without memory, using n function evaluations per iteration, can achieve a maximum convergence order of 2^{n-1} [ 5 ] . The Steffensen method is optimal in this sense, achieving an order of 2. This has motivated adaptations of the Steffensen method to multistep schemes to improve the local order of convergence [ 6 , 7 ] . The use of memory to store previous values of the evaluations can also improve the convergence of these multipoint methods [ 8 , 9 , 5 ] . While the Steffensen method is guaranteed to converge quadratically locally, the estimation of the derivative is far from optimal away from the root. This results in poor stability properties with large regions of initial conditions diverging or converging very slowly. Solutions to this issue have been proposed in [ 10 , 11 , 12 ] with modifications to the first-order difference estimation. In particular, these authors noticed that controlling the values of the first-order divided difference improves stability. Here, we propose a different modification preserving the local convergence behavior while providing a satisfactory estimates of the derivative in regions far from the root. A welcome side-effect of this stability is a reduction in the number of iterations on average. In the present work, we test the method on a collection of nonlinear functions and fields and briefly discuss applications to scalar fields and the implications for optimization. One objective of this article is to show that small modifications to known methods yield significant performance improvements. 2 A family of Steffensen functions for root finding The celebrated Newton-Raphson iteration method is: x_{n+1}=x_{n}-\frac{f(x_{n})}{f^{\prime}(x_{n})}\ . (1) The idea behind the Steffensen-Traub iterative process is to replace the derivative f^{\prime} with the first-order approximation of the derivative: h(x_{n})=\frac{f(x_{n}+g(f(x_{n})))-f(x_{n})}{g(f(x_{n}))}. (2) The updated scheme is written as: x_{n+1}=x_{n}-\frac{f(x_{n})}{h(x_{n})} (3) When g(x)=x we obtain the Steffensen iterative algorithm requiring two evaluations of the function f at each step. While the method guarantees second-order convergence in the vicinity of a root, the estimation of the derivative is rather poor for initial conditions far from the solution. These inaccurate estimates lead to stability problems and divergent trajectories. In this article, The proposed functions g solve the stability problem and improve the speed of convergence. A direct consequence of our modification is a reduction in the number of iteration and an increased range of valid initial conditions. The local quadratic convergence for smooth functions still holds for a large class of functions g . We will show empirically that the choice of nonlinear functions performs better in numerical simulations. In the articles [ 11 , 13 ] , a similar argument has been proposed using a basic control algorithm to keep the value of g(f(x_{n})) within bounds. We generalize their approach baking the ad hoc argument into the function g . An interesting modification of the Steffensen algorithm has been introduced in several works with a constant \gamma in the estimation of the derivative: \Gamma_{n}=\frac{f(x_{n}+\gamma f(x_{n}))-f(x_{n})}{\gamma f(x_{n})}. (4) The properties of the iteration scheme are well studied, see for example [ 5 , 8 ] . If we treat the constant \gamma as a dynamical variable depending on the previous iteration we can obtain an accelerated Steffensen method with convergence order at least 1+\sqrt{2} . This has been described in [ 5 ] section 8.6. The accelerated algorithm is summarized as: \displaystyle x_{n+1}=x_{n}-\frac{f(x_{n})}{\Gamma_{n}}, (5) \displaystyle\Gamma_{n}=\frac{f(x_{n}+g(\gamma_{n}f(x_{n})))-f(x_{n})}{g(\gamma_{n}f(x_{n}))}, (6) \displaystyle\gamma_{n}=-\frac{1}{\Gamma_{n-1}}. (7) The difference with the normal method is an additional cost in memory storage to keep the previous value of \Gamma_{k} at each step and two multiplications.These computation costs actually increase quadratically with the dimension of the domain of the function. Notice that the accelerated method can be integrated in a generalized function \varphi(u,v)=g(u\cdot v) . This trivial definition is useful for the generalization of the computer code abstraction. Considering these two numerical schemes, we will compare several functions g for the approximation of the derivative, Jacobians, and gradients to obtain better convergence and stability results. 3 Order of convergence The convergence of the scheme is of second order for smooth functions. We can prove this convergence by approximating the error e_{k}=x_{k}-x^{*} up to the second order. We define: v(x)=x-\frac{f(x)}{h(x)}, (8) with h(x) our derivative estimate. We expand the function v using a Taylor expansion near a root x^{*} : v(x_{k})=v(e_{k}+x^{*})=v(x^{*})+v^{\prime}(x^{*})e_{k}+\frac{1}{2}v^{\prime\prime}(x^{*})e_{k}^{2}+O(e_{k}^{3}), (9) with v(x^{*})=x^{*} . To prove the convergence, it is sufficient to prove that v^{\prime}(x^{*})=0 and v^{\prime\prime}(x^{*})\neq 0 . For the first part, we differentiate: v^{\prime}(x)=1-\frac{f^{\prime}(x)h(x)-h^{\prime}(x)f(x)}{h^{2}(x)}. (10) The evaluation near the root gives the expression: v^{\prime}(x^{*})=1-\frac{g(f(x^{*}))f^{\prime}(x^{*})}{f(x^{*}+g(f(x^{*}))}. (11) For a smooth function g such that g(0)=0 and g^{\prime}(0)\neq 0 , we can expand f again around g(f(x^{*})) at first order as f(x^{*}+g(f(x^{*})))\simeq f(x^{*})+g(f(x^{*}))f^{\prime}(x^{*}) , obtaining: v^{\prime}(x^{*})=1-\frac{g(f(x^{*}))f^{\prime}(x^{*})}{g(f(x^{*})))f^{\prime}(x^{*})}=0. (12) If the estimated derivative h converges to the true derivative f^{\prime} , the previous expression is meaningful. The last step consists in writing v(x_{n})-x^{*}=e_{k+1} and we obtain the recurrence formula for the error: e_{k+1}=\frac{1}{2}v^{\prime\prime}(x^{*})e_{k}^{2}+O(e_{k}^{3}) (13) The evaluation of v^{\prime\prime}(x^{*})=f^{\prime\prime}(x^{*})/f^{\prime}(x^{*})\not=0 follows from the simple root assumption and v^{\prime\prime}(x)=-\frac{f^{\prime\prime}(x)h(x)-h^{\prime\prime}(x)f(x)}{h^{2}(x)}+2\frac{h(x)}{h^{\prime}(x)}\left(1-v^{\prime}(x)\right) (14) evaluated at x=x^{*}. This proves the convergence for smooth functions. A more general result proven in [ 14 ] shows that any iteration scheme in the form x_{n+1}=x_{n}-f(x_{n})/\hat{f}^{\prime}(x_{n}) where \hat{f}^{\prime} is an approximation to f^{\prime} has convergence order \min((x-x^{*})(f^{\prime}(x^{*})-\hat{f}^{\prime}(x^{*})),2) . The theorem holds under reasonable assumptions on the regularity of f . Another argument for the convergence of semi-smooth functions has been developed in [ 10 ] and [ 11 ] and can be adapted to our scheme. The order of convergence of the accelerated method has been demonstrated in [ 5 , 15 ]

Read the complete text