3
$\begingroup$

This is related to a question I answered on Stack Overflow regarding calculating the square root of a number. I was thinking about it and realized that the formula is just the first in a family of algorithms to calculate the $p$th root of a number (ie solve $y=x^p$ for $x$).

$$ x_n = \left( \frac{p}{2} \right) \frac{\displaystyle y + \prod_{j=n-p}^{n-1} x_j}{ \displaystyle\sum_{j=n-p}^{n-1} \prod_{\substack{k=n-p \\ k\ne j}}^{n-1} x_k}$$

We can show that as $n\rightarrow\infty$ the result converges to the correct answer, but I'm not sure how to go about finding other important characteristics like a rate of convergence and stability requirements. Any advice on resources?

$\endgroup$
3
  • $\begingroup$ Is the product taken over the previous approximations of the root? Can $y$ be replaced by $x^p$ in the formula? $\endgroup$ – nicoguaro Mar 4 '20 at 11:49
  • $\begingroup$ Sorry, $x_j$ is the $j$th approximation of $x$. $y$ is an input the function $\endgroup$ – user1543042 Mar 4 '20 at 12:08
  • $\begingroup$ For the convergence, maybe you can divide two consecutive iterates and check how the norm changes. $\endgroup$ – nicoguaro Mar 5 '20 at 18:32
1
$\begingroup$

The first thing you can do is determining the convergence rate experimentally. To do it, it is enough to plot error vs. iteration in a log-log scale and check the slope of the line that connects the iterates (approximately). If the method converges very quickly, you might need arbitrary precision reals to get enough data points.

If experiments do not tell you that the algorithm is at least quadratic, I would be surprised if this method is of any use --- the baseline is Newton's method.

$\endgroup$
1
  • $\begingroup$ I know that this is a terrible algorithm, it requires keeping $p$ previous estimates. $\endgroup$ – user1543042 Mar 4 '20 at 12:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.