Stopping criterion for Newton-Raphson

Question

I am currently doing a question on Newton-Raphson method and I am not sure what it means by 'explain your stopping criterion'.

Question

Using the Newton-Raphson method with initial guess $x_0=1.5$, solve the equation $$x^2=2$$ correct to four decimal places. Be sure to explain your stopping criterion

So my issue is not working out Newton-Raphson, you just follow the equation, to which I make it $1.4142$ after three iterations which is to 4 d.p but what dose it mean by 'stopping criterion'?

In an computer lab, we have done code for this and in a while loop we set the to |$f(x_0)$|>$\epsilon $

where epsilon was set by us, and the lower we set $\epsilon$ the more iterations were produced. But there was a limit on this, and from that I got the gist it was a convergence limit? But I am not sure if or how this relates to this question nor how one would workout the stopping criterion.

Answer 1

The stopping criterion? That's a rule for looking at the numbers you've calculated so far and deciding "OK, I'm sure this is accurate to four decimal places. We can stop now, and take the last calculated value as our estimate".

Possible things to take into consideration: the values $f(x_n)$, the derivatives $f'(x_n)$, the differences $x_n - x_{n-1}$. Whatever rule you come up with, it should be something that, in theory, you could put into a computer program as a condition to end that while loop. You don't have to write that program, of course - just explain your rule in natural language.

Answer 2

To stop, you need to be sure you're right to four decimal places, so for example you might require consecutive estimates to differ by at most $10^{-5}$.

For a really advanced treatment you could estimate roughly how many steps that should take from first principles. In solving $f(x)=0$, in this case with $f(x):=x^2-2$, the error terms have an approximate iteration $\epsilon_{n+1}\approx M\epsilon_n^2,\,M:=-\frac{f^{\prime\prime}(a)}{f^\prime(a)}$ with $a$ the root. So $M=-\frac{2}{2\sqrt{2}}=-\frac{1}{\sqrt{2}}$ and the initial error approximates $0.1$. This suggests three iterations beyond $1.5$ is enough. That fits my data.

Answer 3

In reality, your objective is to produce a code which can compute $\sqrt{\alpha}$ with a small relative error for any $\alpha > 0$. It is easy to determine when $\alpha - x_n^2$ is small, but when is it small enough? The relative error is given by $$r_n = \frac{\sqrt{\alpha} - x_n}{\sqrt{\alpha}}.$$ We do not know the exact value of $\sqrt{\alpha}$, but we can nevertheless estimate the relative error as follows. We have $$ r_n = \frac{(\sqrt{\alpha}-x_n)(\sqrt{\alpha}+x_n)}{\sqrt{\alpha} (\sqrt{\alpha}+x_n)} = \frac{\alpha-x_n^2}{\sqrt{\alpha} (\sqrt{\alpha}+x_n)} \approx \frac{\alpha-x_n^2}{2\alpha}.$$ The last approximation is good when $\sqrt{\alpha} - x_n$ is small.

---

Resist the temptation to use $|f(x)| > \epsilon$ to control a while loop. It is a recipe for disaster, because you depend on $f$ being implemented correctly. If $f$ returns NaN (not a number), then you exit the while loop believing $|f(x)| \leq \epsilon$. This is a consequence of IEEE standard for floating point arithmetic which specifies that all comparisons with NaN return false. The safe construction is to use a for loop with a user defined number of iterations. You should evaluate $|f(x)|$ inside the loop and exit the loop prematurely if $|f(x)| \leq \epsilon$ (all is well) or if $f(x)$ is not finite (serious problem).