# Show that the newton-rhapson iteration is a contraction under certain conditions

The Newton–Raphson method for finding roots of a differentiable function $f : \mathbb{R} \to \mathbb{R}$ is to iterate the function $$x \mapsto g(x):=x - \frac{f(x)}{f'(x)}$$ Where the following conditions is assumed on $f$

1. $f$ has a continous second derivative
2. $f'(x) \neq 0 \ \forall \ x \in \mathbb{R}$
3. There exists some $\alpha \in (0,1)$ such that $\left| f(x) f''(x)\right| \, \leq \, \alpha \left| f'(x) \right|^2 \ \forall \ x \in \mathbb{R}$

The question is how to prove that $g$ is a contraction.

I have already tried to use the definition of a contraction, that there exists some $0<\alpha<1$ such that

$$d(Tx,Ty) \leq \alpha d(x,y),$$

holds. Now I tried using the metric induced by the supremum norm. But alas this gave me nothing. The hint was to use the Mean Value Theorem, but I can not quite see how that applies here. Can someone show me/ give me some clear suggestions on how to proceed? =)

-
Hint: What is $g'(x)$? – Thomas Andrews Dec 3 '12 at 16:28
Why are you using the "supremum norm" metric, when your space is just $\mathbb R$? You are trying to show $g(x)$ is a contraction map, and $g(x):\mathbb R\rightarrow\mathbb R$. – Thomas Andrews Dec 3 '12 at 16:32
Just differentiate $g$, using Quotient Rule. We get $ff"/(f')^2$. (Not needed observation: so $g'(x)$ at root is $0$, which is why when Newton-Raphson is good it is very very good. Attractive force gets stronger as we near the root.) – André Nicolas Dec 3 '12 at 16:46

You want to compare $|g(x)-g(y)|$ to $|x-y|$. By the MVT, $g(x)-g(y) = g'(\xi)(x-y)$ for some $\xi$ between $x$ and $y$. Now $$g'(\xi)=1-\frac{f'(\xi)^2-f(\xi)f''(\xi)}{f'(\xi)^2}=\frac{f(\xi)f''(\xi)}{f'(\xi)^2}$$ and thus you immediately find that $\alpha$ is your contraction constant.
You seem to have misunderstood the hint. The hint is to prove that $g$ is a contraction map, where $g$ is defined as:$$g(x)=x-\frac{f(x)}{f'(x)}$$ The metric space in question is $\mathbb R$, not some function space where you need a "supremum norm."
In particular, $g$ is a contraction if there is a $\beta\in(0,1)$ such that for all $x,y$, $$|g(x)-g(y)|<\beta |x-y|$$
Now use the mean value theorem on $g(x)-g(y)$ to get a bound which uses $g'$.