Newton's method and error term analysis for $f(x) = x - \cos(x)$

Question

I'm taking a first course in Real Analysis and the instructor is using Arthur Mattuck's book. I'm struggling with a particular exercise: prove that the Newton's method of finding roots works for finding the root of $$f(x) = x - \cos(x)$$, i.e., it converges for the right value of $x$. It also gives me the hint to use that $|\sin(x)| < |x|, \forall x$ and $|1-\cos(x)| < \frac{x^{2}}{2}, \forall x$.

The chapter 4, which is the one the exercise belongs to, is all about error term analysis, I mean, if you can show that the limit of a sequence $e_{n} = a_{n} - L$ is $0$, where $a_{n}$ is another sequence and $L$ a real number, then the limit of $a_{n}$ is $L$.

Applying the method, it takes me to: $$x_{n+1} = x_{n} - \frac{x_{n} - \cos(x_{n})}{1+\sin(x_{n})}$$ And it gets like this: $$x_{n+1} = \frac{x_{n}\sin(x_{n}) - \cos(x_{n})}{1+\sin(x_{n})}$$ Writing using error terms: $$e_{n+1} = \frac{(e_{n}+L)\sin(e_{n}+L) - \cos(e_{n}+L)}{1+\sin(e_{n}+L)}$$ I know I should prove that ${e_{n}}$ goes to $0$ but I can't figure out the algebra.

Answer 1

I don't know that the direction you are heading will be very useful. Instead, let me note some things:

• Let $f(x) = x - \cos x$, then $f'(x) = 1 + \sin x \ge 0$, and futher is equal to $0$ only at isolated points. Hence $f$ is strictly increasing.
• $f(0) = -1$ and $f(1) = 1 - \cos 1 \approx 0.46$. Hence by the intermediate value theorem, there is some $L$ with $ 0 < L < 1$ such that $f(L) = 0$. Because $f$ is strictly increasing, $L$ is unique.
• Let $g(x) = x - \frac{f(x)}{f'(x)} = x - \frac {x - \cos x}{1 + \sin x}$. For $x \in (-\pi/2, L), f(x) < 0$ while $f'(x) > 0$, so $g(x) < x$. Conversely, for $x \in (L, \pi/2), f(x) > 0$ and $f'(x) > 0$. Hence $g(x) < x$.
• $$g'(x) = \frac{f(x)f''(x)}{(f'(x))^2} = \frac{(x - \cos x)\cos x}{(1 + \sin x)^2}$$ Since $\cos x$ and $(1 + \sin x)^2$ are both positive on $(-\pi/2, \pi/2)$, $g'(x) < 0$ for $x < L$ and $g'(x) > 0$ for $x > L$. So $L$ is the minimum of $g$ on $(-\pi/2, \pi/2)$. Further $g(0) = 1$ and $g(1) \approx 0.75$, so the maximum value of $g(x)$ on $[0, 1]$ is $1$. Since $L > 0$, this means if $x_0 \in [0,1]$, then so is $x_n$ for all $n$.
• If $0 \le x_n \le L$, then $x_{n+1} = g(x_n) \in [L, 1]$. If $x_n \in [L, 1]$, then, $x_{n+1} = g(x_n) \in [L, 1]$. So for arbitrary $x_0 \in [0,1]$, we have that for all $n > 0$, $x_n \in [L,1]$.
• Note that in $[L, 1], g'(x) - 1 < 0$ (the two factors in the numerator of $g'$ are both $< 1$, while the denominator is $> 1$). Therefore $g(x) - x$ is decreasing. Since $g(L) = L$, it follows that for $x \in [L, 1], g(x) - x \le g(L) - L = 0$, so $g(x) < x$. Hence for $n > 0, x_{n+1} < x_n$.
• Therefore if $x_0 \in [0, 1]$, then $x_n$ for $n > 0$ is a decreasing sequence bounded below by $L$. Therefore it converges to some limit $L'$.
• Since $\{x_n\}$ converges, we can take the limit on both sides of $$x_{n+1} = x_n - \frac{x_n - \cos x_n}{1 + \sin x_n}$$ to get $$L' = L' - \frac{L' - \cos L'}{1 + \sin L'},$$ noting that since $L' \in [0, 1]$, the denominator is not $0$. This solves to give $L' - \cos L' = 0$. Since I've already shown above that there is only one solution to this equation, $L' = L$.

I believe a little more effort would show that sequence converges for any $x_0 \in (-\pi/2, 3\pi/2)$. But the sequence becomes undefined for $x_n = 2k\pi - \pi/2$. And for starting values outside $(-\pi/2, 3\pi/2)$, a few will eventually land on one of these undefined numbers. So you cannot prove convergence for all $x_0$.