Higher-Order Root-Finding Algorithm and its Applications
Wei Guo Foo, Chik How Tan · 2025
Read Higher-Order Root-Finding Algorithm and its Applications by Wei Guo Foo, Chik How Tan (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-2509-20897.txt.
Introduction
Finding the root of an equation by repeated refinement is a basic task in applied mathematics. Wei Guo Foo and Chik How Tan propose a higher-order root-finding algorithm in a 2025 paper set to appear in the International Journal of Computer Mathematics. Their method uses only Taylor expansions of the function.
Classic higher-order methods, such as Householder's, need higher derivatives of a reciprocal function. Computing those symbolically is slow, and numerical differentiation piles up errors. The new method avoids both problems and carries an explicit convergence factor, sharper than earlier rough estimates. It can also implement Householder's method numerically. The authors apply it to computing quantities such as option-related values, showing the scheme at work.
Catalog record
| CREATOR | Wei Guo Foo, Chik How Tan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-20897
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher-Order Root-Finding Algorithm and its Applications Wei Guo Foo, Chik How Tan Abstract Root-finding method is an iterative process that constructs a sequence converging to a solution of an equation. Householder’s method is a higher-order method that requires higher order derivatives of the reciprocal of a function and has disadvantages. Firstly, symbolic computations can take a long time, and numerical methods to differentiate a function can accumulate errors. Secondly, the convergence factor existing in the literature is a rough estimate. In this paper, we propose a higher-order root-finding method using only Taylor expansion of a function. It has lower computational complexity with explicit convergence factor, and can be used to numerically implement Householder’s method. As an application, we apply the proposed method to compute pre-images of q q -ary entropy functions, commonly seen in coding theory. Finally, we study basins of attraction using the proposed method and compare them with other root-finding methods. Keywords : Higher-order root-finding methods, q -ary entropy functions, Householder’s method. MSC Classification : 65H05, 94-08 1 Introduction Finding a solution to an equation f(x)=0 may require numerical methods, especially when a closed-form formula can not be found. It requires setting up iterative schemes to construct sequences based on initial guesses converging to the nearest solution, and their convergence speeds vary according to different methods. The well-known ones are derivative-based methods such as Newton’s and Halley’s method, with respective convergence orders of 2 and 3. Householder’s method [ 8 , 15 , 3 ] (or in some places known as the König’s method [ 1 , 4 , 11 ] ) is one of their generalisations which achieve higher orders of convergence. However, its use has a few limitations. Firstly, its implementation requires taking derivatives of the reciprocal of the function, which for high orders, can be symbolically difficult to implement. There are workarounds using finite difference methods to find numerical approximations to the derivative of a function but they accumulate errors and can lead to inaccurate results [ 7 , 9 ] . Secondly, existing literature describes the convergence rate using the big O notation. Hence the method may fail to produce a converging sequence despite its implementation for high orders since the convergence factor may be very large, underscoring the importance of finding an accurate estimate of its value. This paper is therefore motivated by the following problem: Problem 1.1 . Given an equation f(x)=0 with \alpha being a solution. Is there an effective and efficient numerical root-finding method that constructs a sequence of the form: x_{n+1}=x_{n}+P(x_{n}), (1) with convergence to the actual solution in the following way for high orders of k : |x_{n+1}-\alpha|\leq C|x_{n}-\alpha|^{k+1}, (2) and with an accurate estimation of convergence factor C ? To address this problem, we propose a method which requires a set of equations consisting of Taylor series expansion of f centered at the n -th iterated value x_{n} evaluated at the nearest solution \alpha treated as a symbolic variable that remained to be solved. Then we eliminate some Taylor coefficients by using linear combinations of equations similar to Gaussian elimination to obtain equation ( 1 ). In addition, the elimination process allows us to compute C in equation ( 2 ). The following theorem describes our main result of the paper. Theorem 1 . Let f(x) be a k+1 continuously-differentiable function and \alpha be one of the solutions to the equation f(x)=0 . Define iteratively: \displaystyle A_{0} \displaystyle=1,\quad A_{1}=f^{\prime},\quad A_{2}=(f^{\prime})^{2}-\frac{1}{2}f^{\prime\prime}f, (3) \displaystyle A_{j+1} \displaystyle=f^{\prime}A_{j}-f\widehat{A}_{j},\quad\text{where}\quad\widehat{A}_{j}=\sum_{l=2}^{j+1}\frac{1}{l!}(-f)^{l-2}f^{(l)}A_{j+1-l}. Let x_{0} be the initial guess and consider the following sequence: x_{n+1}=x_{n}-\frac{f(x_{n})A_{k-1}(x_{n})}{A_{k}(x_{n})}. Then there exists an expression C such that \left|x_{n+1}-\alpha\right|\leq C\left|\alpha-x_{n}\right|^{k+1}. Recall that the Householder’s method of order k for the equation f(x)=0 with an initial guess x_{0} to one of the roots \alpha is a sequence given by the iteration: x_{n+1}=x_{n}+k\frac{(1/f)^{(k-1)}(x_{n})}{(1/f)^{(k)}(x_{n})}, (4) where (1/f)^{(k)} denotes the k -th derivative of the reciprocal of the function f . As a consequence of Theorem 1 , we show that our proposed method can be used to numerically implement Householder’s method, which is our second main result. Theorem 2 . Let A_{k} be coefficients given by equation ( 3 ). Then k\frac{(1/f)^{(k-1)}}{(1/f)^{(k)}}=-f\frac{A_{k-1}}{A_{k}}. In other words, the Householder’s method can numerically be done by Theorem 1 . Due to Theorem 2 , we are able to obtain a more accurate description of the convergence factor for the Householder’s method. Corollary 2.1 . Let f(x)=0 be an equation and x_{0} be the first guess of the actual solution \alpha . Let x_{n}^{\prime} and x_{n}^{\prime\prime} be sequences given by \displaystyle x_{n+1}^{\prime} \displaystyle=x_{n}^{\prime}+k\frac{(1/f)^{(k-1)}(x_{n}^{\prime})}{(1/f)^{(k)}(x_{n}^{\prime})}, (5) \displaystyle x_{n+1}^{\prime\prime} \displaystyle=x_{n}^{\prime\prime}-\frac{f(x_{n}^{\prime\prime})A_{k-1}(x_{n}^{\prime\prime})}{A_{k}(x_{n}^{\prime\prime})}. Let C be such that |x_{n+1}^{\prime\prime}-\alpha|\leq C(x_{n}^{\prime\prime},\alpha)|x_{n}^{\prime\prime}-\alpha|^{k+1}. Then for the same C , |x_{n+1}^{\prime}-\alpha|\leq C(x_{n}^{\prime\prime},\alpha)|x_{n}^{\prime}-\alpha|^{k+1}. There are several advantages of our proposed root-finding method in Theorem 1 . Firstly, it has lower computational complexity. If k is the order of convergence, an estimation shows that it takes about O(k^{3}) steps to compute the sequence \{A_{0},\cdots,A_{k}\} . In contrast, the time complexity of Householder’s method can grow exponentially with respect to k if \frac{d^{k}}{dx^{k}}\frac{1}{f} were to be symbolically calculated. Secondly, it allows Householder’s method to be numerically implemented with lower computational complexity by avoiding symbolic calculations. Lastly, it gives us better clarity of the time complexity and a more explicit convergence factor of the Householder’s method. As a demonstration of our proposed root-finding method, we apply Theorem 1 to find the pre-images of the q -ary entropy function, which plays an important role in information theory and cryptography. It describes how much choice is involved in the selection of events and how uncertain we are of the outcome. It was introduced by Shannon [ 16 , 10 ] in 1948, and is mathematically written as: H=-\sum_{i=1}^{n}p_{i}\log_{b}(p_{i}), where p_{i} ’s are the probabilities of occurences of events so that their sum is 1 . The case n=b=2 is the well-known binary entropy function: H_{2}(x)=-x\log_{2}x-(1-x)\log_{2}(1-x). (6) More generally when dealing with finite fields with q elements, one has the q -ary entropy function: Definition 1 . For any q\geq 2 , the q -ary entropy function H_{q}:[0,1]\longrightarrow\mathbb{R} is defined as H_{q}(x):=x\log_{q}(q-1)-x\log_{q}x-(1-x)\log_{q}(1-x). Recall that a linear code is a vector subspace of \mathbb{F}_{q}^{n} , and suppose its dimension grows proportionally to n at a certain rate 0<R<1 . A successful decoding of a syndrome depends on finding the minimal distance of the linear code, which is an NP-complete problem [ 19 ] especially for large n . Nonetheless, an estimation of the minimal distance of a general random linear code is possible by the Gilbert-Varshamov distance [ 6 , 20 ] , denoted by D_{\text{GV}}(R) , which is the unique solution x\in[0,\frac{q-1}{q}] to H_{q}(x)=1-R. (7) A classical result shows that in almost all of the linear codes, the distance between any two elements is at least \lfloor D_{\text{GR}}(R)n\rfloor . Thus computing the minimum distance of a linear code requires finding solution to equation ( 7 ). To date, other than the obvious ones 1-R\in\{0,1\} , there is no known closed-form solution. Hence the second problem we aim to address in this paper is the following: Problem 1.2 . For any y\in[0,1] , find the numerical solution to H_{q}(x)=y for x\in[0,\frac{q-1}{q}] . A common challenge to implementing root-finding methods is the choice of first guess x_{0}