3
$\begingroup$

The ultraradical of a real number, also called the Bring radical, is the unique real solution of the quintic equation

$$y=x^5+x.$$

This function is used in the resolution of general quintic equations, by reducing them to this particular form.

But are there specific methods to efficiently compute it numerically for arbitrary values of $x$ ?

Obviously, for small $y$, $x\approx y$, and for large $y$, $x\approx\sqrt[5]y$. But what about intermediate values ? Anything more specific than Newton ?


Update:

After numerical tests, I observe that Newton's method, taken with the initial approximation $x=y$ or $x=\sqrt[5]y$ takes a maximum of $5$ iterations to reach $10^{-7}$ relative error o $x$. The worst cases are between $0.7$ and $3.5$.

This is already pretty good. I am now targeting a reduction to $3$ iterations by using a better initial approximation.

Here is a plot of a correction factor that should be introduced to improve the initial estimate:

enter image description here

$\endgroup$
5
  • $\begingroup$ You mean to compute it numerically for arbitrary values of $y$? $\endgroup$ – Simply Beautiful Art Aug 16 '17 at 23:19
  • $\begingroup$ @SimplyBeautifulArt: yep. $\endgroup$ – user65203 Aug 16 '17 at 23:19
  • $\begingroup$ Why not to use Halley or Householder mpethods instead ? It would be faster. $\endgroup$ – Claude Leibovici Aug 17 '17 at 7:09
  • $\begingroup$ @ClaudeLeibovici: probably because I never heard of them (even though I know they are your cup of tea) ;-) But I guess that before switching to better convergence speed, the initial approximate should be improved. $\endgroup$ – user65203 Aug 17 '17 at 7:38
  • $\begingroup$ @ClaudeLeibovici: by the way, I have established the empirical correction factor $1 - 0.245 y^{-0.831}$ which works for $y\ge1$. It does reduce the number of iterations to $3$. $\endgroup$ – user65203 Aug 17 '17 at 7:40
0
$\begingroup$

Let the solution for $x$ be denoted by $\newcommand{BR}{\operatorname{BR}}\BR(y)$. We have by Lagrange inversion theorem (see link for more general case), for $|y|<4\cdot5^{-9/5}$,

$$\BR(y)=\sum _{{k=0}}^{\infty }{\binom {5k}{k}}{\frac {(-1)^{k}y^{{4k+1}}}{4k+1}}=y-y^{5}+5y^{9}-35y^{{13}}+\dots$$

On the other hand, a fixed point approach won't hurt. For large $|x|>1$, we should use the iteration

$$x_{n+1}=\sqrt[5]{y-x_n}$$

And for small $|x|<1$, we should use the iteration

$$x_{n+1}=y-x_n^5$$

$\endgroup$
10
  • $\begingroup$ That series isn't convergent in general. $\endgroup$ – Ian Aug 16 '17 at 23:37
  • $\begingroup$ @Ian Yup, fixed. $\endgroup$ – Simply Beautiful Art Aug 16 '17 at 23:39
  • $\begingroup$ What for the intermediate values ? If an iterative method is used, I guess that Newton is preferred as the derivative is available. $\endgroup$ – user65203 Aug 17 '17 at 6:07
  • $\begingroup$ For $|y|<4\cdot5^{-9/5}$, the last term is about $10^{-7}$. Is this what you used to set the bound ? $\endgroup$ – user65203 Aug 17 '17 at 6:10
  • $\begingroup$ @YvesDaoust I suspect that given bound was just where the Lagrange inversion series converges. The fixed point iteration suggestion is pretty much totally unrelated. $\endgroup$ – Ian Aug 17 '17 at 12:57
0
$\begingroup$

To cover the transition interval: Choose a rational $\xi$ (e.g., $\xi=1$), and put $\eta:=\xi+\xi^5$. You then know that $b(\eta)=\xi$ and can easily determine the first few coefficients of the Taylor expansion of $b$ at $\eta$. Use this expansion to find a starting value for the Newton iteration.

An example: Letting $\xi=1$ you have $\eta=2$ and then $$b(y)\approx1+{1\over6}(y-2)-{5\over108}(y-2)^2\qquad(y\approx 2)\ .$$

$\endgroup$
6
  • $\begingroup$ Yep, that's an option. I would prefer something that blends better with $y$ and $\sqrt[5]y$, it will probably have a larger domain of validity. $\endgroup$ – user65203 Aug 17 '17 at 10:25
  • $\begingroup$ @YvesDaoust Perhaps initialize with $y^{1-4/5 f(y)}$ where $f(0)=0,f(\infty)=1$ and $f$ is strictly increasing? $\endgroup$ – Ian Aug 17 '17 at 12:59
  • $\begingroup$ @Ian: that's a nice proposal. First attempts ($f(y)=y/(1+y)$ and similar) are disappointing as they worsen convergence everywhere, but some tuning will help. It is actually possible to plot the ideal $f=1-5/4\log_y x$. $\endgroup$ – user65203 Aug 17 '17 at 14:21
  • $\begingroup$ @YvesDaoust Actually that's a terrible idea, because the root is always lower than the minimum of $y$ and $y^{1/5}$ (for $y>0$, make the obvious changes for $y<0$). So you'd be better off just splitting at $y=1$. $\endgroup$ – Ian Aug 17 '17 at 14:49
  • $\begingroup$ @Ian: that's right, $f$ has a singularity there. But we might rescue with $g(y)^{1-4/5f(y)}$. $\endgroup$ – user65203 Aug 17 '17 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy