Is there an explicit formula for finding the number of iterations needed for an approximation for Newton's method?

Question

I was asked to find the approximate number of iterations using Newton's Method and I was curious if there were an explicit formula as there is for the bisection method which is $|p_n-p|=\dfrac{(b-a)}{2^n}$. I was told that it was $2^N=$ (the number of decimal places desired), but I am finding that to be incorrect.

Answer 1

It depends on how close your first guess was to the root. One can prove convergence for newton's method with the Banach Contraction Theorem. If we let $$ g(x) = x-\frac{f(x)}{f'(x)} $$ then we can show that this is a contraction if $x_0$ is close to a root of $f$ that we'll call $a$ (and you make some reasonable assumptions about $f'$). Then note that $g(a)=a$. Let's call it's contraction constant $\theta$. And let $x_n=g(x_{n-1})$.

$$ |x_n-a|=|g^{(n)}(x_0)-g^{(n)}(a)| \leq \theta^n|x_0-a| $$

So your suggestion in the post isn't bad. Getting $\theta \leq 1/2$ isn't too hard with a good guess on $a$.

Answer 2

The beauty of Newton's method is that it is second order. If the function is well represented by a Taylor series between your current estimate and the root, you roughly square the error each time. Say we are finding a root to $f(x)$ and the correct root is at $x=a$. Then $f(x) = f'(a)(x-a) + \frac 12f''(a)(x-a)^2+\dots$ As long as $f''(x)$ is not too large, so $f'(x_n) \approx f'(a)$ you will cancel out the linear term. This is the source of the approximation $2^N=$ desired decimal places. We assume that you have about one place at the start and that the error is squared each time. If you don't start near the root, it can often take a long time to get there, or you may get to another universe entirely.