Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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? =)

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.