# Basic numerical analysis, fixed point iteration

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?

• 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

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.

Hints:

1. 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

• 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