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.

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|improve this question
    
Is this homework? If so please tag it as such. –  Epictetus Dec 3 '12 at 16:21
    
No, preparing for an exam.. This was one of the last questions. See here for a source math.ntnu.no/~stacey/documents/tma4145/finalH09en.pdf. –  N3buchadnezzar Dec 3 '12 at 16:23
1  
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
add comment

2 Answers 2

up vote 4 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|improve this answer
add comment

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|improve this answer
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.