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?

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

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.



  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?


  • $\begingroup$ 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.) $\endgroup$ – amWhy May 19 '13 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.