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.

$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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)$? $\endgroup$
    – Huy
    Dec 14, 2010 at 11:00
  • $\begingroup$ 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). $\endgroup$
    – Xodarap
    Dec 14, 2010 at 15:03
  • $\begingroup$ 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? $\endgroup$
    – Huy
    Dec 14, 2010 at 15:09
  • $\begingroup$ @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$. $\endgroup$
    – Xodarap
    Dec 14, 2010 at 16:10
  • $\begingroup$ 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... $\endgroup$
    – Huy
    Dec 14, 2010 at 16:15
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ ah clever! (and some more to 15) $\endgroup$
    – Xodarap
    Dec 14, 2010 at 19:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .