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.

I have just started numerical analysis so this question probably seems trivial.

Say I have a function $f(x) = x^2 - x - 3$

I let $g(x) = x^2 - 3$

Then I want to find the roots of $f(x)$ so I have $f(x) = g(x) - x = 0$

So I can find the roots by finding the fixed points of $x = g(x)$

So far so good yes?

Now I use the fixed point iteration formula - $x_{n+1} = g(x_{n}) = x_{n}^2 - 3$

Say I pick 3 for $x_{1}$, then I get $x_{2} = 6$ and $x_{3} = 33$...so it is diverging

I then tried picking 1 for $x_{1}$, then I get $x_{2} = -2$ and $x_{3} = 1$...so it is going to infinitely alternate...

So the fixed point iteration method isn't working. Why is it not working in this situation and what are the conditions it needs to work?

share|improve this question
2  
You function $g$ must be Lipschitz with coefficient $<1$ in order to make it work. Try the Newton-Raphson algorithm instead ;) –  vanna Sep 12 '12 at 16:44

2 Answers 2

up vote 2 down vote accepted

One thing to consider is whether the iteration is a contraction map in a neighborhood of the desired root. Here the derivative of the iteration function is $2x$, and this has absolute value greater than 1 near either root.

In such a case an inverse iteration often works as a contraction, i.e. here we'd assign $\sqrt{x+3}$ to $x$ repeatedly to approximate the positive root.

The contraction mapping property is that $|f(x)-f(y)|$ is less than $|x-y|$, but this is a sufficient condition rather than a necessary one for convergence of a fixed point iteration. However if the inequality goes the other way, iterates cannot converge to the fixed point.

share|improve this answer

Hints:

  1. Plot the function: http://www.wolframalpha.com/input/?i=Solve%5Bx%5E2-x-3%3D0%2Cx%5D&t=crmtb01

  2. Look at section 2.1 and 2.2 in: http://pages.cs.wisc.edu/~amos/412/lecture-notes/lecture03.pdf

Can you figure out what is wrong from that?

HTH

share|improve this answer
    
Nice hints. What is HTH? (I'm not the most savvy nor well-versed in terms of knowledge of common/informal "text" or "chat" acronyms, as my question probably reveals.) –  amWhy May 19 '13 at 0:26

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.