Estimate the number of iterations of Newton's method needed to find a root of $f(x)=\cos(x)-x$ to within $10^{-100}$.
The answer is $7$ iterations, but I have no idea how it was solved by my instructor.
Asked
Active
Viewed 172 times
0
-
Starting from which point? – Daniel Fischer Oct 17 '13 at 00:20
-
@Daniel I don't know the starting point. My instructor wrote $\log_{2}100 = 6.6$. And so $7$ iterations. – Oct 17 '13 at 00:23
-
So apparently the assumption is that one starts with a value of magnitude around $1$. One can create longer sequences by choosing the right large starting point. – Daniel Fischer Oct 17 '13 at 00:29
1 Answers
1
The idea behind the reasoning is the quadratic convergence of Newton's algorithm (if the zero is simple).
When you are near the zero $\alpha$, an iteration takes you from $\alpha + \delta$ to
$$(\alpha + \delta) - \frac{f(\alpha+\delta)}{f'(\alpha+\delta)} \approx \alpha + \delta - \frac{f'(\alpha)\delta + f''(\alpha)\frac{\delta^2}{2}}{f'(\alpha) + f''(\alpha)\delta} \approx \alpha + \frac{f''(\alpha)}{2f'(\alpha)}\delta^2,$$
so each step roughly doubles the number of correct digits.
If you start with approximately one correct digit, after seven steps, you have roughly $2^7 = 128$ correct digits.
Daniel Fischer
- 206,697
-
Is there a more simple explanation to this? Yes, I know that it has to do with quadratic convergence, but can I use a formula such as the one for the bisection method ($2^-N< 10^3$) to solve for N? – Oct 17 '13 at 00:41
-
The doubling of the number of correct digits translates into a (roughly) $10^{-s\cdot 2^N}$ relative error after $N$ steps when your initial guess had a relative error of $10^{-s}$. Is that the sort of formula you were looking for? – Daniel Fischer Oct 17 '13 at 00:46
-
-
A measure of the initial error. If you start with five correct digits, you need fewer iterations than if you start with only one. – Daniel Fischer Oct 17 '13 at 00:52