6
$\begingroup$

I'm trying to get familiar with the Newton-iteration over here but I got stuck at the proof of the error estimate.

Let $f: [a,b] \rightarrow \mathbb{R}$ be continuously differentiable twice, concave or convex and f' \neq 0 \;\; \forall x \in [a,b]. Let $\xi$ be the root of $f$. We define the Newton-iteration for $k \in \mathbb{Z}_{\geq 0}$: x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}

Also, we assume $x_1 \in [a,b]$ for $x_0 = a$ and $x_0 = b$.

I already showed that the sequence $(x_k)_{k \in \mathbb{N}}$ converges to $\xi$. Now, I want to show the following error estimate:

|\xi - x_{k+1}| \leq \frac{\max_{a \leq x \leq b} |f''(x)|}{2 \min_{a \leq x \leq b} |f'(x)|} (x_{k+1}-x_k)^2

I am quite sure I will have to combine the mean value theorem and Taylor's theorem (and Lagrange's remainder), but I have no idea, how to. I don't quite know at what point I should use Taylor's theorem, also, I don't know between which two points I should apply the mean value theorem.

I'd be very happy if somebody could give me a little hint so that I can proceed.

2 Answers 2

2

We first apply the Taylor-expansion for $f(x_{k+1})$ around $x_k$: f(x_{k+1})=f(x_k) + f'(x_k)(x_{k+1}-x_k)+R_2

where $R_2$ is the remainder. We'll take Lagrange's remainder and we get to: f(x_{k+1}) = f'(x_k) \cdot (\frac{f(x_k)}{f'(x_k)} - x_k + x_{k+1}) + \frac{1}{2} f''(x_0)(x_{k+1} - x_k)^2

where per definition \frac{f(x)}{f'(x)}-x_k = -x_{k+1} and $x_0$ is some point between $x_{k+1}$ and $x_k$.

So the first term vanishes and we can write: |f(x_{k+1})| \leq \frac{1}{2} \max_{a \leq x \leq b} |f''(x)| (x_{k+1}-x_k)^2

Also, from the mean value theorem we know that: \min_{a \leq x \leq b} |f'(x)| \leq \frac{|f(x_{k+1} - f(\xi)|}{|x_{k+1} - \xi|} = \frac{|f(x_{k+1}|}{|x_{k+1} - \xi|}

It follows: |\xi - x_{k+1}| \leq \frac{1}{2} \frac{\max_{a \leq x \leq b} |f''(x)|}{\min_{a \leq x \leq b} |f'(x)|} (x_{k+1}-x_k)^2

q.e.d.

  • 0
    ah clever! (and some more to 15)2010-12-14
6

Check out the proof on wikipedia.

If you just want a hint: call g(x) = x - \frac{f(x)}{f'(x)}. Consider $g(x) - g(\xi)$ with the Taylor expansion. You will get something related to g''(c), which is your desired result, upon expanding g''.

  • 0
    It's from our current Analysis exercise. However, I solved it. I'll post an answer in a few. Thanks for your help though!2010-12-14