2
$\begingroup$

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 give me some clear suggestions on how to proceed?

  • 0
    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.)2012-12-03

2 Answers 2

6

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.

3

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