Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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

share|improve this answer
    
I'm not sure whether I'm doing this right. I now arrived at $g(x) - \xi = \frac{1}{2} g''(x_0) (x-\xi)^2$. How can I now expand $g''$ (and maybe $g$), so that I get back to $f(x)$? –  Huy Dec 14 '10 at 11:00
    
Just find $g''(x)$ in terms of $f$ and you will be there. Note also that $g(x)=x_{n+1}$ (it is just two different notations for the same thing). –  Xodarap Dec 14 '10 at 15:03
    
I really don't see it. I do realise that $g(x) = x_{n+1}$, but how can I write $g''(x)$ in terms of $f$? I mean, per definition $g(x) = x - \frac{f(x)}{f'(x)}$, so $g''(x)$ requires $f$ to be differentiable thrice, which is not the case here... Or am I missing something else? –  Huy Dec 14 '10 at 15:09
    
@Huy: Good point, I didn't read your question closely enough. I apologize. You may see the wikipedia proof if you only have $f\in C^2$. –  Xodarap Dec 14 '10 at 16:10
    
The wikipedia proof leads me to $|\xi - x_{k+1}| \leq \frac{\max|f''(x)|}{2 \min|f'(x)|} (\xi - x_k)^2$, but actually I wanted the last part to be $(x_{k+1} - x_k)^2$. How could I fix this? Obviously $|x_{k+1} - x_k| \leq |\xi - x_k|$, so it's no option to simply replace them... –  Huy Dec 14 '10 at 16:15
show 3 more comments
up vote 2 down vote accepted

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.

share|improve this answer
    
ah clever! (and some more to 15) –  Xodarap Dec 14 '10 at 19:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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