# Fixed Point Iteration, does it converge?

Find the fixed point(s) of $g(x) = x^2 + 3x - 3$. Does the fixed point iteration(s) converge(s) to the fixed points if you start with a close enough first approximation?

I set $g(x) = x$ and got $g(x) = x^2 + 2x - 3$. So either $x=1$ or $x=-3$. How do I find out if it converges or diverges?

• Perhaps it would be clearer if we avoid using $g(x)$ for two different functions. The original $g(x) = x^2 + 3x - 3$ is the one you want to find fixed points for. The related function $h(x) = g(x) - x$ will have roots at the same places that $g(x)$ has fixed points. – hardmath Jan 23 '14 at 15:42
• Check this <---$\qquad$ – Felix Marin Jan 23 '14 at 18:11

If we write

$$x_{n+1} = G(x_n)$$

The error term is given by:

$$e_n = [G'(r)]^ne_0$$

where $r$ is the root.

The error reduces if $|G'(r)| \lt 1$ and increases if $|G'(r)| \gt 1$.

Also, are you sure you wrote $G(x)$ correctly?

Update

• Let's see, we have a root at $r = 1$ or $r = -3$.
• $|G'(r)| = |2r+2|$.
• At $r= 1, ~~~|G'(r)| = |4|>1 \rightarrow$ diverges.
• At $r= -3, |G'(r)| = |4|>1 \rightarrow$ diverges.
• I'm sure I wrote both g(x)'s correctly. The derivative of g(x) would be 2x + 2. If we are looking for the absolute value of the the derivative to be less than 1, then -1.5 < x < -.5. – Jesus Jan 21 '14 at 16:44
• @Jesus You make a mistake you need the derivative of $g(x) = x^2 + 3x - 3$. And then test if the absolute value of $|g'(x)| < 1$, a functions fixed point doesn't have to be convergend. – Willemien Jan 21 '14 at 19:25
• Actually, he needs the derivative of $x = g(x)$, that is, the transformed $G(x)$. For his example, $g(x)$ is not correct. Regards – Amzoti Jan 21 '14 at 22:26
• @Amzoti Why does it need the derivative of $G(x)$ (not the original function) and not of $g(x)$ (the original one)? – nbro Apr 8 '16 at 15:24

Hint: the answer depends on the derivative of $g$ at the fixed point

First, the fixed points of $g(x)=x^2+2x-3$ are not $1$ and $-3$, those are the roots. The fixed points are the solutions to $x^2+2x-3=x$ or, by the quadratic formula, $(-1\pm\sqrt{13})/2$.

To show that the larger of these $(\sqrt{13}-1)/2$ is repulsive, we can re-write $g(x)$ as

$$g(x)=\left(x+\frac{1}{2} \left(1-\sqrt{13}\right)\right)^2+\left(1+\sqrt{13}\right) \left(x+\frac{1}{2} \left(1-\sqrt{13}\right)\right)+\frac{1}{2} \left(\sqrt{13}-1\right).$$

You can verify this equality by expanding it out; you can even have WolframAlpha do the algebra for you.

Now, consider a quadratic of the form

$$f(x) = (x-x_0)^2 + m(x-x_0) + x_0,$$

where $m>1$. This is exactly what we have for $x_0 = (\sqrt{13}-1)/2$ and $m=1+\sqrt{13}$.

Now, I claim that $$|f(x)-x_0|>|x-x_0|$$ for $x$ sufficiently close to $x_0$. This follows from the equality $$|f(x)-x_0| = |(x-x_0) + m| \cdot |x-x_0|.$$ All we need is $|(x-x_0) + m|>1$, which will certainly be true for $x$ close to $x_0$, since $m>1$.

Note that $m$ is exactly the value of the derivative of $f$ at $x_0$ and what we see near the fixed point is that the linear term in the expansion dominates the behavior of the function. This is exactly the hint that the others were trying to offer.

One way to understand the qualitative behaviour of iteration of $g$ is a cobweb diagram. Read that article and try to apply it to your situation. After doing that, you should understand Robert Israels hint to look at the derivative.

• I used the coweb diagram. – Jesus Jan 23 '14 at 14:59