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.
Best Answer
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).