estimation of error - Newton-Raphson method

Question

I am trying to write code that solves equations using Newton-Raphson method. I want the iterations would stop when the error is smaller than the tolerance defiend by the user. How can I validate the error is smaller than the tolerance?

thanks

Answer 1

In general, you cannot. You don't know the true value of the solution.

Consider solving $x^2+0.00001 =0$ and $x^2-0.00001$, the first has no solution, but a NR method will initially appear to be converging to a value close to zero, before diverging.

If you have an estimate for the root $\alpha$, and a tolerance $\epsilon$ then you can evaluate $f(\alpha\pm\epsilon)$. If these two values have different signs then you know that there is a root in the interval $\alpha\pm\epsilon$. If they have the same sign then either there is either no root in the range, a double root, or an even number of roots.

You can iterate the NR method until the difference between terms becomes small, then test by looking for a change of sign. If there is a change of sign then you have a proven root. If there is no certain way of telling whether a root even exists or not.