0
$\begingroup$

I am trying to implement the nth root algorithm. The algorithm says to repeat until $|\Delta x_{k}| < \epsilon$. I want to know if $\epsilon$ has any particular meaning.

I thought it was an upper bound on the error, but after some experimentation that does not hold up. For example:

Trying to find $\sqrt[11]{2048}$ (true answer is 2), with initial guess $x_{0}=5$:

$$\Delta x{_k} = {1 \over n} \left( {A \over x_{k}^{n-1}} - x_{k} \right)$$

$$= {1 \over 11} \left( {2048 \over 5^{10}} - 5 \right)$$ $$\approx -0.4545$$

If I use $\epsilon = 0.5$, the algorithm stops here even though it's off by 3 (or off by $\approx 2.5455$ after adding $\Delta x_{k}$).

Ultimately, I just want to get within 0.5 (I'm actually trying to compute the integer closest to the true answer). Is there any way of picking an epsilon that will accomplish this result?

$\endgroup$
1
  • $\begingroup$ The $\mathsf{Newton-Rapson Method}$ converges '$\texttt{quadratically}$'. It means you have to stop after "some tolerance" < $\sqrt{mp}$ where $mp$ is the Machine Precision. However, some software already defines that value. For instance, $\texttt{C++}$ defines $\texttt{FLT_EPSILON}$, $\texttt{DBL_EPSILON}$ and $\texttt{LDBL_EPSILON}$ for types $\texttt{float}$, $\texttt{double}$ and $\texttt{long double}$, respectively. So, there is no case in pushing above such limits. $\endgroup$ May 25, 2017 at 23:08

1 Answer 1

2
$\begingroup$

You are wanting the error in your approximation to be less than $0.5$. As the algorithm is written, it terminates whenever one step is less than $0.5$ These are two different things. You could have a case where there were many steps, all less than $0.5$ and slowly decreasing, but the error of the approximation when the step size drops below $0.5$ could be huge. This is about what happens here.

As you are using Newton's method, once you get close to the root the relative error gets squared each step. Once the relative error is small, this means that all the remaining steps sum to very little. The problem here is that you are far from the root and quadratic convergence has not set in yet. If you used $\epsilon=0.1$ you would quit at $x_k=2.007918$ and the error would be well below the last step. The stopping criterion in Wikipedia ignores the requirement that you be close enough to the root to assume the error is less than the last step. Newton's method basically constructs the tangent line at your current $x_k$ and projects it down to the $x$ axis to find $x_{k+1}$. If the tangent is not a good approximation to the curve between your current approximation and the root it will not converge rapidly.

All this does not give a simple rule for when to stop your root finding. You could also take your current $x_k$ to the $11$th power and compare with $2048$. That gives the error in the function value, not the error in the root. I don't think there is a simple answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .