A root finding method with arbitrary order of convergence

Abstract

Let $a\in {\mathbb{R}}^{+}\backslash \left\{0\right\}$ and $M\in \mathbb{N}$. We consider the equation $t^M-a=0$, which is equivalent to $1-\frac{t^M}{a}=0.$ The real solution is $\sqrt[M]{a}$. In this publication, we present a method that enables the calculation of $\sqrt[M]{a}$ with arbitrary order of convergence using only polynomials. We define the fixed point function \[ 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 $\left(P\cdot M+1\right)$ with $\left(P+1\right)$ terms. The calculation of $\sqrt[M]{a}$ is thus reduced to a polynomial evaluation. The computational tests we performed demonstrate the efficiency of the method. -- Es sei $a\in {\mathbb{R}}^{+}\backslash \left\{0\right\}$ und $M\in \mathbb{N}$. Vorgelegt ist die Gleichung $t^M-a=0$, die äquivalent zu $1-\frac{t^M}{a}=0$ ist. Die reelle Lösung hiervon ist $\sqrt[M]{a}$. In dieser Veröffentlichung stellen wir ein Verfahren vor, das die Berechnung von $\sqrt[M]{a}$ mit beliebiger Konvergenzordnung ermöglicht und nur Polynome verwendet. Wir definieren die Fixpunktfunktion \[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 $\left(P\cdot M+1\right)$ mit $\left(P+1\right)$ Summanden. Anhand ausgewählter Beispiele von Wurzelberechnungen zeigen wir die Effizienz des Verfahrens.

bilingual: English (18 pages) and German (18 pages)