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.

  • 1
    $\begingroup$ Your equations are a little off. They should be $$x_{n+1} = \frac{x_{n}\sin(x_{n}) \color{red}{+} \cos(x_{n})}{1+\sin(x_{n})}$$ and $$e_{n+1} \color{red}{+L}= \frac{(e_{n}+L)\sin(e_{n}+L) \color{red}{+} \cos(e_{n}+L)}{1+\sin(e_{n}+L)}$$ This may be the source of your algebraic difficulties. $\endgroup$ – Paul Sinclair Jan 20 '16 at 3:07
  • $\begingroup$ Ok, that's right, my fault. But this was just a typo, I had the correct sign all the time in my paperwork. I still can't figure out the algebra, tough. Could you help me? $\endgroup$ – Raul Guarini Jan 20 '16 at 17:02

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$.

  • $\begingroup$ Alright, thanks a lot! I can understand what you did, seems nice. But the bad thing about the exercise is that I am supposed to use the so-called "error term analysis". I will keep trying. Thank you again! $\endgroup$ – Raul Guarini Jan 21 '16 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.