A root finding method with arbitrary order of convergence

2026

Read A root finding method with arbitrary order of convergence (2026) 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-2601-22187.txt.

Introduction

A short mathematics preprint studies a basic task: solving for a root of an equation. The equation considered takes a simple power form, where an unknown raised to a whole-number power must equal a given positive number. Its real solution is the corresponding root of that number.

The author presents a root finding method whose order of convergence can be chosen freely. The order measures how fast the error shrinks at each step; higher orders reach a precise root in fewer iterations. Methods with tunable order are useful in numerical software, where root finding sits inside countless larger computations. The note keeps its focus narrow: one equation family, one method, and its convergence behavior.

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22187

Browse the full library · About the Tower of Babel

Full text

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

A root finding method with arbitrary order of convergence Abstract Let a ∈ ℝ + \ { 0 } a\in\mathbb{R}^{+}\backslash\left\{0\right\} and M ∈ ℕ M\in\mathbb{N} . We consider the equation t M − a = 0 t^{M}-a=0 , which is equivalent to 1 − t M a = 0 . 1-\frac{t^{M}}{a}=0\,. The real solution is a M \sqrt[M]{a} . In this publication, we present a method that enables the calculation of a M \sqrt[M]{a} with arbitrary order of convergence using only polynomials. We define the fixed point function F ⁡ ( x ) = ∏ ℓ = 1 P ( 1 + 1 ℓ ⋅ M ) ​ ∫ 0 x ( 1 − t M a ) P ​ 𝑑 t = ∑ k = 0 P ( − 1 ) k a k ⋅ ( P k ) ⋅ x k ⋅ M + 1 k ⋅ M + 1 F\left(x\right)=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\int\limits_{0}^{x}\!\left(1-{\frac{{t}^{M}}{a}}\right)^{P}{\rm d}t=\sum\limits_{k=0}^{P}\frac{\left(-1\right)^{\,k}}{a^{\,k}}\cdot\binom{P}{k}\cdot\frac{x^{\,k\,\cdot M+1}}{k\,\cdot M+1} This is a polynomial of degree ( P ⋅ M + 1 ) \left(P\cdot M+1\right) with ( P + 1 ) \left(P+1\right) terms. The calculation of a M \sqrt[M]{a} is thus reduced to a polynomial evaluation. The computational tests we performed demonstrate the efficiency of the method. Zusammenfassung Es sei a ∈ ℝ + \ { 0 } a\in\mathbb{R}^{+}\backslash\left\{0\right\} und M ∈ ℕ M\in\mathbb{N} . Vorgelegt ist die Gleichung t M − a = 0 t^{M}-a=0 , die äquivalent zu 1 − t M a = 0 1-\frac{t^{M}}{a}=0 ist. Die reelle Lösung hiervon ist a M \sqrt[M]{a} . In dieser Veröffentlichung stellen wir ein Verfahren vor, das die Berechnung von a M \sqrt[M]{a} mit beliebiger Konvergenzordnung ermöglicht und nur Polynome verwendet. Wir definieren die Fixpunktfunktion F ⁡ ( x ) = ∏ ℓ = 1 P ( 1 + 1 ℓ ⋅ M ) ​ ∫ 0 x ( 1 − t M a ) P ​ 𝑑 t = ∑ k = 0 P ( − 1 ) k a k ⋅ ( P k ) ⋅ x k ⋅ M + 1 k ⋅ M + 1 F\left(x\right)=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\int\limits_{0}^{x}\!\left(1-{\frac{{t}^{M}}{a}}\right)^{P}{\rm d}t=\sum\limits_{k=0}^{P}\frac{\left(-1\right)^{\,k}}{a^{\,k}}\cdot\binom{P}{k}\cdot\frac{x^{\,k\,\cdot M+1}}{k\,\cdot M+1} Das ist ein Polynom vom Grad ( P ⋅ M + 1 ) \left(P\cdot M+1\right) mit ( P + 1 ) \left(P+1\right) Summanden. Die Berechnung von a M \sqrt[M]{a} reduziert sich dadurch zu einer Polynomauswertung. Anhand ausgewählter Beispiele von Wurzelberechnungen zeigen wir die Effizienz des Verfahrens. Deutsche Version ab Seite 19 Alois Schiessl 1 1 1 University of Regensburg ; E-Mail: [email protected] August 10, 2026 1 Introduction and Main Result One of the best-known method for calculating an approximate value for \sqrt[M]{a} for a positive real number a and M\in\mathbb{N} is to apply Newton’s method [ 1 ] x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f\,^{\prime}\left(x_{n}\right)} to the function f\left(x\right)=x^{M}-a\;, from which the fixed point iteration can be derived x_{n+1}=x_{n}-\frac{x_{n}^{M}-a}{M\,x_{n}^{M-1}}=x_{n}-\frac{1}{M}\left(x_{n}-\frac{a}{x_{n}^{M-1}}\right)\;;\;n=0,1,\ldots If the initial value x_{0} is sufficiently close to \sqrt[M]{a} , the sequence converges quadratically to \sqrt[M]{a} . Each additional Iteration approximately doubles the number of correct digits. In this article, we present a method that only works with polynomials and allows for any order of convergence. The method is based on the function f\left(t\right)=1-\frac{t^{M}}{a}\;. Now we state our main result: Theorem . Let a\in\mathbb{R}\backslash\left\{0\right\} and M\in\mathbb{N} . We define f:\mathbb{R}\to\mathbb{R}\;; t\mapsto f\left(t\right)\;; f\left(t\right)=1-\frac{t^{M}}{a}\;. Let P\in\mathbb{N}. We define F:\mathbb{R}\to\mathbb{R}\;; x\mapsto F\left(x\right)\;; F\left(x\right)=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\int\limits_{0}^{x}\!f\left(t\right)^{P}{\rm d}t=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\int\limits_{0}^{x}\!\left(1-{\frac{{t}^{M}}{a}}\right)^{P}{\rm d}t\;. Let a>0. Then, there hold the following statements for F\left(x\right) (a) \sqrt[M]{a} is a fixed point, that means: F\left(\sqrt[M]{a}\right)=\sqrt[M]{a}\,. (b) The derivatives up to \left(P+1\right) at the fixed point \sqrt[M]{a} are given by \displaystyle F{\left(\sqrt[M]{a}\right)}^{\left(k\right)}=\left\{\begin{aligned} 0\qquad\qquad\qquad\qquad 1\,\leq&\,k\,\leq{P}\\ \\ \frac{\left(-1\right)^{P}}{\sqrt[M]{a^{P}}}\prod_{\ell=1}^{P}\left(1+\ell\cdot M\right)\qquad\qquad\quad k=&P+1\\ \end{aligned}\right. (c) Let x_{0} an initial value sufficiently close to \sqrt[M]{a}\,, then the sequence x_{n+1}=F\left(x_{{n}}\right)\;;\;n=0,1,\ldots converges to \sqrt[M]{a} with order of convergence exactly \left(P+1\right). 2 Proof of the theorem In this section we give a proof of the main result using only Classical Analysis. 2.1 Fixed point We have to prove that for a>0 the following statement is true F\left(\sqrt[M]{a}\right)=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\int\limits_{0}^{\sqrt[M]{a}}\!\left(1-{\frac{{t}^{M}}{a}}\right)^{P}{\rm d}t=\sqrt[M]{a}\;. We will first consider the definite integral \int\limits_{0}^{\sqrt[M]{a}}\!\left(1-\frac{{t}^{M}}{a}\right)^{P}{\rm d}t\;. We make the substitution \frac{t^{M}}{a}=u to obtain \frac{{\rm d}\,t}{{\rm d}\,u}=\sqrt[M]{a}\cdot\frac{1}{M}\cdot u^{\frac{1}{M}-1}\;. Therefore: \int\limits_{0}^{\sqrt[M]{a}}\!\left(1-{\frac{{t}^{M}}{a}}\right)^{P}{\rm d}t=\int\limits_{0}^{1}\!\left(1-u\right)^{P}\sqrt[M]{a}\cdot\frac{1}{M}\cdot u^{\frac{1}{M}-1}{\rm d}u=\frac{\sqrt[M]{a}}{M}\int\limits_{0}^{1}\!u^{\frac{1}{M}-1}\cdot\left(1-u\right)^{P}{\rm d}u\;. Since the lower limit t=0 was replaced with u=0 , and the upper limit \sqrt[M]{a} with 1 . The next task is now to evaluate the integral \int\limits_{0}^{1}\!u^{\frac{1}{M}-1}\cdot\left(1-u\right)^{P}{\rm d}u\;. Let us remind the real Beta function [ 2 ] : {\rm B}\left(\alpha,\beta\right)=\int\limits_{0}^{1}\!{u}^{\alpha-1}\left(1-u\right)^{\beta-1}\,{\rm d}u\;;\,\alpha>0\;;\,\beta>0\;, which is closely related to the gamma function [ 3 ] {\rm B}\left(\alpha,\beta\right)={\frac{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}{\Gamma\left(\alpha+\beta\right)}}\;. Substituting \alpha=\frac{1}{M}\;;\quad\beta=P+1 gives a representation by the \Gamma function \int\limits_{0}^{1}\!u^{\frac{1}{M}-1}\cdot\left(1-u\right)^{P}{\rm d}u=\frac{\Gamma\left(\frac{1}{M}\right)\cdot\Gamma\left(P+1\right)}{\Gamma\left(P+1+\frac{1}{M}\right)}\;. Now, P is a natural number, so \Gamma\left(P+1\right)=P\,!\; . This simplifies the term to \frac{\Gamma\left(\frac{1}{M}\right)\cdot\Gamma\left(P+1\right)}{\Gamma\left(P+1+\frac{1}{M}\right)}=\frac{\Gamma\left(\frac{1}{M}\right)P\,!}{\Gamma\left(P+1+\frac{1}{M}\right)}\;. Next, we focus on \Gamma\left(P+1+\frac{1}{M}\right)\;. Repeated using of the definition of the \Gamma -Function \Gamma\!\left(1+x\right)=x\,\Gamma\!\left(x\right) with x=\frac{1}{M} yields step by step \Gamma\!\left(1+\frac{1}{M}\right)=\frac{\Gamma\!\left(\frac{1}{M}\right)}{M}\;; \Gamma\!\left(2+\frac{1}{M}\right)=\left(1+\frac{1}{M}\right)\frac{\Gamma\!\left(\frac{1}{M}\right)}{M}=\prod\limits_{\ell=1}^{1}\left(1+\frac{1}{\ell\cdot M}\right)\frac{1\,!\cdot\Gamma\left(\frac{1}{M}\right)}{M}\;; \Gamma\!\left(3+\frac{1}{M}\right)=\left(1+\frac{1}{M}\right)\left(2+\frac{1}{M}\right)\frac{\Gamma\!\left(\frac{1}{M}\right)}{M}=\prod\limits_{\ell=1}^{2}\left(1+\frac{1}{\ell\cdot M}\right)\frac{2\,!\cdot\Gamma\left(\frac{1}{M}\right)}{M}\;; \Gamma\!\left(4+\frac{1}{M}\right)=\left(1+\frac{1}{M}\right)\left(2+\frac{1}{M}\right)\left(3+\frac{1}{M}\right)\frac{\Gamma\!\left(\frac{1}{M}\right)}{M}\\ =\prod\limits_{\ell=1}^{3}\left(1+\frac{1}{\ell\cdot M}\right)\frac{3\,!\cdot\Gamma\left(\frac{1}{M}\right)}{M}\;; \vdots By using an induction argument it is a simple matter to prove that \Gamma\left(P+1+\frac{1}{M}\right)=\prod\limits_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\frac{P\,!\cdot\Gamma\left(\frac{1}{M}\right)}{M}\;. Thus, for the definite integral, we obtain \int\limits_{0}^{1}\!u^{\frac{1}{M}-1}\cdot\left(1-u\right)^{P}{\rm d}u=\frac{\Gamma\left(\frac{1}{M}\right)\cdot\Gamma\left(P+1\right)}{\Gamma\left(P+1+\frac{1}{M}\right)}=\frac{\Gamma\left(\frac{1}{M}\right)\cdot P\,!}{\prod\limits_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\frac{P\,!\cdot\Gamma\left(\frac{1}{M}\right)}{M}}=\frac{M}{\prod\limits_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)}\;. Now we just need to put everything together. That gives us \displaystyle F\left(\sqrt[M]{a}\right) \displaystyle=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\int\limits_{0}^{\sqrt[M]{a}}\!\left(1-{\frac{{t}^{M}}{a}}\right)^{P}{\rm d}t \displaystyle=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\frac{\sqrt[M]{a}}{M}\int\limits_{0}^{1}\!u^{\frac{1}{M}-1}\cdot\left(1-u\right)^{P}{\rm d}u \displaystyle=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\frac{\sqrt[M]{a}}{M}\cdot\frac{M}{\prod\limits_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)} \displaystyle=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\frac{\sqrt[M]{a}}{\prod\limits_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)}=\sqrt[M]{a}\;. The proof of the fixed point statement is completed. 2.2 Derivatives Next, we focus on the derivatives. 2.2.1 First Derivative Starting with the first derivative we obtain immediately F\,^{\prime}\left(x\right)=\left(\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\int\limits_{0}^{x}\!\left(1-{\frac{{t}^{M}}{a}}\right)^{P}{\rm d}t\right)^{\prime}=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\left(1-{\frac{{x}^{M}}{a}}\right)^{P}\;. Plugging in \sqrt[M]{a} yields F\,^{\prime}\left(\sqrt[M]{a}\right)=0 . We will need this result later. 2.2.2 Higher derivatives So far, we have a formula for the first derivative F\,^{\prime}\left(x\right)=\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\cdot\left(1-\frac{x^{M}}{a}\right)^{P}. We still have to prove that the following statement holds at the fixed point x=\sqrt[M]{a}\,: \displaystyle F{\left(\sqrt[M]{a}\right)}^{\left(k\right)}=\left\{\begin{aligned} 0\qquad\qquad\qquad\qquad 1\,\leq&\,k\,\leq{P}\\ \\ \frac{\left(-1\right)^{P}}{\sqrt[M]{a^{P}}}\prod_{\ell=1}^{P}\left(1+\ell\cdot M\right)\qquad\qquad\quad k=&P+1\\ \end{aligned}\right. This requires a little bit more work. We must differentiate \left(P+1\right) times F\left(x\right) and then plugging in x=\sqrt[M]{a} . Using the first derivative F\,^{\prime}\left(x\right) the task simplifies to \displaystyle\left.F\left(x\right)^{\left(P+1\right)}\right|_{x={\sqrt[M]{a}}}=\left.\bigl(F\,^{\prime}\left(x\right)\bigr)^{\left(P\right)}\right|_{x={\sqrt[M]{a}}}=\left.\left(\prod_{\ell=1}^{P}\left(1+\frac{1}{\ell\cdot M}\right)\cdot\left(1-\frac{x^{M}}{a}\right)^{P}\right)^{\left(P\,\right)}\right|_{x={\sqrt[M]{a}}} On the right-hand side, we need at x=\sqrt[M]{a} the P^{\,th} derivative of \left(1-\frac{x^{M}}{a}\right)^{P} Let us put f\left(x\right)=\left(1-\frac{x^{M}}{a}\right) and first calculating some particular values of f\left(x\right), needed later: f\left(\sqrt[M]{a}\right)=0\;; f^{\prime}\left(\sqrt[M]{a}\right)=\left.\left(1-\frac{x^{M}}{a}\right)^{\prime}\right|_{x={\sqrt[M]{a}}}=\ldots=\frac{-M}{\sqrt[M]{a}}\;. In the next step, we expand f\left(x\right) into a Taylor series of degree 1 at the fixed point x_{0}=\sqrt[M]{a} with Lagrange remainder: f\left(x\right)=f\left(\sqrt[M]{a}\right)+f^{\prime}\left(\sqrt[M]{a}\right)\left(x-\sqrt[M]{a}\right)+\frac{f^{\prime\prime}\left(\xi\right)}{2}\left(x-\sqrt[M]{a}\right)^{2} where \xi is between x and \sqrt[M]{a} . Since f\left(\sqrt[M]{a}\right)=0 and f^{\prime}\left(\sqrt[M]{a}\right)=\frac{-M}{\sqrt[M]{a}} , we get f\left(x\right)=\frac{-M}{\sqrt[M]{a}}\left(x-\sqrt[M]{a}\right)+\frac{f^{\prime\prime}\left(\xi\right)}{2}\left(x-\sqrt[M]{a}\right)^{2} and can thus factor out \left(x-\sqrt[M]{a}\right): f\left(x\right)=\left(x-\sqrt[M]{a}\right)\left(\frac{-M}{\sqrt[M]{a}}+\frac{f^{\prime\prime}\left(\xi\right)}{2}\left(x-\sqrt[M]{a}\right)\right)\;. Next we raise f\left(x\right) to the P^{\,th} power : f\left(x\right)^{P}=\left(x-\sqrt[M]{a}\right)^{P}\left(\frac{-M}{\sqrt[M]{a}}+\frac{f^{\prime\prime}\left(\xi\right)}{2}\left(x-\sqrt[M]{a}\right)\right)^{P}\;. We calculate the higher derivatives of f\left(x\right)^{P} by using the Leibniz rule [ 4 ] . Leibniz rule states that if u\left(x\right) and v\left(x\right) are n -times differentiable functions, then the product u\left(x\right)\cdot v\left(x\right) is also n -times differentiable and its n^{\,th} derivative is given by the sum \bigl(u\left(x\right)\cdot v\left(x\right)\bigr)^{\left(n\right)}=\sum\limits_{k=0}^{n}\binom{n}{k}\,u\left(x\right)^{\left(k\right)}\cdot v\left(x\right)^{\left(n-k\right)}\;. Here we want to understand u\left(x\right)^{\left(0\right)}=u\left(x\right) and v\left(x\right)^{\left(0\right)}=v\left(x\right)\;. In our case we have: n=P\;; u\left(x\right)=\left(x-\sqrt[M]{a}\right)^{P}\;; v\left(x\right)=\left(\frac{-M}{\sqrt[M]{a}}+\frac{f^{\prime\prime}\left(x\right)}{2}\left(x-\sqrt[M]{a}\right)\right)^{P}\;. Thus we obtain f\left(x\right)^{P}=\underbrace{{{\left(x-\sqrt[M]{a}\right)}^{P}}}_{u\left(x\right)}\times\underbrace{{{\left(\frac{-M}{\sqrt[M]{a}}+\frac{f^{\prime\prime}{{\left(\xi\right)}}}{2}\left(x-\sqrt[M]{a}\right)\right)}^{P}}}_{v\left(x\right)}\;. Now applying Leibniz rule \left(f\left(x\right)^{P}\right)^{\left({P}\right)}=\sum\limits_{k=0}^{{P}}\binom{{P}}{k}\,\left(\left(x-\sqrt[M]{a}\right)^{P}\right)^{\left(k\right)}\times\left(\left(\frac{-M}{\sqrt[M]{a}}+\frac{f^{\prime\prime}{\left(\xi\right)}}{2}\left(x-\sqrt[M]{a}\right)\right)^{{P}}\right)^{\left({P-k}\right)}\,. We first focus on the sequence of derivatives u\left(x\right)^{\left(k\right)}=\Bigl(\left(x-\sqrt[M]{a}\right)^{P}\Bigr)^{\left(k\right)},\;k=0,1,\ldots,P\;. From a collection of mathematical formulas [ 5 ] , we derive the following statement \displaystyle\Bigl(\left(x-\sqrt[M]{a}\right)^{P}\Bigr)^{\left(k\right)}=\frac{P\,!}{\left(P-k\right)\,!}\left(x-\sqrt[M]{a}\right)^{P-k}\;. In particular, we note that for 0\leq k<P in the formula u\left(x\right)^{\left(k\right)}=\left(\left(x-\sqrt[M]{a}\right)^{{P}}\right)^{\left(k\right)}=\frac{P\,!}{\left(P-k\right)\,!}\left(x-\sqrt[M]{a}\right)^{P-k}, the factor \left(x-\sqrt[M]{a}\right) always occurs and thus for x=\sqrt[M]{a} the terms vanish. Only the case of k=P leads to a non-zero result, namely the product {\left.u{{\left(x\right)}^{\left(P\right)}}\right|}_{x=\sqrt[M]{a}}=\frac{P\,!}{\left(P-P\right)\,!}=P\,!\;. From the sum \left(f\left(x\right)^{P}\right)^{\left({P}\right)}=\sum\limits_{k=0}^{{P}}\binom{{P}}{k}\,\left(\left(x-\sqrt[M]{a}\right)^{P}\right)^{\left(k\right)}\times\left(\left(\frac{-M}{\sqrt[M]{a}}+\frac{f^{\prime\prime}{\left(\xi\right)}}{2}\left(x-\sqrt[M]{a}\right)\right)^{{P}}\right)^{\left({P-k}\right)} only the term with k=P remains at the fixed point x=\sqrt[M]{a} . We can evaluate \left.\left(f\left(x\right)^{P}\right)^{\left({P}\right)}\right|_{x=\sqrt[M]{a}}=\underbrace{\left.\left(\left(x-\sqrt[M]{a}\right)^{P}\right)^{\left(P\right)}\right|_{x=\sqrt[M]{a}}}_{=P\,!}\times\underbrace{\left.\left(\left(\frac{-M}{\sqrt[M]{a}}+\frac{f^{\prime\prime}{\left(\xi\right)}}{2}\left(x-\sqrt[M]{a}\right)\right)^{{P}}\right)\right|_{x=\sqrt[M]{a}}}_{\left(\frac{-M}{\sqrt[M]{a}}\right)^{P}}

Read the complete text