Fixed Point Iteration

def: Fixed Point $p$ is the value $p$ such that      $g(p)=p$.

Fixed Point problems and root-finding problems $f(x)=0$ are equivalent: let $g(p)-p=f(p)\Rightarrow f(p)=0$. Hence, if a function has a fixed point $g(p)=p$ then $f(p)=0$ has a root.

Three Problems:

1. What functions have a fixed point?
2. How do we determine the fixed point?
3. Is the fixed point unique?

Example $g(x)=x$    $0\le x\le 1$ has a fixed point at each $x\in[0,1]$....just plot.

Example $g(x)=x-\sin\pi x$ has 2 fixed points in $[0,1]$    $x=0,\, x=1$....plot, again.

$\Box$

Theorem (Existence and Uniqueness): If $g\in C[a,b]$ and $g(x) \in[a,b]\,\forall x\in [a,b]$ then $g(x)$ has a fixed point in $[a,b]$.

Suppose, in addition, that $g'(x)$ exists on $(a,b)$ and that a positive constant $k<1$ exists with

$$\vert g'(x)\vert\le k<1\quad \forall x\in (a,b)$$

then the fixed point in $[a,b]$ is unique.

Proof:

If $g(a)=a$ or $g(b)=b$, then existence of fixed point is clear. Suppose not, then it must be true that $g(a)>a$ and $g(b)<b$. Define $h(x)=g(x)-x$. Then $h$ is continuous on $[a,b]$ and

$$h(a)=g(a)-a>0\quad h(b)=g(b)-b<0$$

The Intermediate Value Theorem implies that there exist $p\in(a,b)$ for which $h(p)=0$. Thus, $g(p)-p=0\Rightarrow p$ is fixed point of $g$.

Suppose, in addition $\vert g'(x)\vert\le k<1$     $\forall x\in (a,b)$.

holds and that $p$ and $q$ are both fixed points in $[a,b]$ with $p\ne q$. By the Mean Value Theorem a number exists between $p$ and $q$ such that

$$\frac{g(p)-g(q)}{p-q}=g'(\xi)$$

then $\vert p-q\vert=\vert g(p)-g(q)\vert=\vert g'(\xi)\vert p-q\vert \vert\le k\vert p-q\vert<\vert p-q\vert$ which is a contradiction.

This contradiction comes from $p\ne q\therefore p=q$ and the fixed point is unique. $\Box$

Fixed-Point Iteration    $g(p)=p$

Pick a $p_0$ and generate a sequence $$\{p_n\}^{\infty}_{n=0}$$ such that $p_n=g(p_{n-1})\,n\ge 1.$ If the sequence converges to $p$ and $g$ is continuous then by the theorem above:

$$p=\lim_{n\to \infty}p_n=\lim_{n\to\infty}g(p_{n-1})=g(\lim_{n\to \infty} p_{n-1})=g(p)$$

The algorithm is depicted in Figure 18

Figure 18: Fixed Point Iteration

Fixed Point Algorithm

Input: $p_0,$ TOL, $N_0$
Output: $p$ or message of failure
Step 1: Set $i=1$
Step 2: While $i\le N_0$ do Steps 3 - 6
Step 3: Set $p=g(p_0)$    % Compute $p_i$
Step 4: if $\vert p-p_0\vert<$ TOL then
output $(p)$;     % found not
Stop
Step 5: Set $i=i+1$
Step 6: Set $p_0=p$     Update $p$.
Step 7: Output (Iterations exceeded. $N>N_0$)
END

$\Box$

Theorem: (Fixed Point Iteration) Let $g\in C[a,b]$ and suppose $g(x) \in[a,b]\,\forall x\in [a,b]$. Suppose in addition that $g'$ is continuous on $(a,b)$ with

$$\vert g'(x)\vert\le k<1\quad \forall x\in (a,b)$$

if $g'(p)\ne 0$ then for any $p_0$ in $[a,b]$, the sequence

$$p_n=g(p_{n-1})\quad n\ge 1$$

converges only linearly to the unique fixed point in $[a,b]$

Proof: Fixed Point Theorem says $$\{p_n\}^{\infty}_0\to p$$. Since $g'$ exists on $(a,b)$ apply mean value Theorem to $g$ to show that for any $n$

$$p_{n+1}-p=g(p_n)-g(p)=g'(\xi_n)(p_n-p)$$

$$\xi_n \mbox { lies between } p_n \mbox {and } p.$$

since $$\{p_n\}^{\infty}_0\to p$$, and $\{\xi_n\}^{\infty}_{0}\to p$. Since $g'$ is continuous on $(a,b)$ we have

$$\lim_{n\to\infty}g'(\xi_n)=g'(p)$$

thus

$$\begin{eqnarray*} \lim_{n\to\infty}\frac{p_{n+1}-p}{p_n-p} =\lim_{n\to\infty}g'... ...d point iteration converges}\\ \mbox {linearly if } g'(p)\ne 0. \end{eqnarray*}$$

$\Box$

Remark: Can get higher-order convergence when $g'(p)=0:$

Theorem: Suppose $p$ solution of $x=g(x)$. $g'(p)=0$ and $g''$ continuous and strictly bounded by $M$ on an open interval $I$ containing $p$. Then $\exists\, \delta>0$ such that $p_0\in [p-\delta, p+\delta]$. The sequence $p_n=g(p_{n-1}),\, n\ge 1$ converges quadratically:

$$\vert p_{n+1}-p\vert<\frac{M}{2}\vert p_n-p\vert^2$$

$\Box$

Fixed Point Iteration: let $g\in C \subseteq [a,b]$ and suppose $g(x) \in[a,b]\,\forall x\in [a,b]$. Suppose in addition that $g'$ exists on $(a,b)$ with

$$\vert g'(x)\vert\le k<1\quad \forall x\in (a,b)$$ (6)

if $p_0$ is any number in $[a,b]$, then

$$p_n=g(p_{n-1}), \quad n\ge 1$$

converges to unique fixed point in $[a,b]$.

Proof: From fixed point theorem, a unique fixed point exists in $[a,b]$. Since $g$ maps $[a,b]$ into itself, the sequence $\{p_n\}^{\infty}_{n=0}$ is defined $\forall_n\ge 0$ and $p_n\in [a,b] \quad \forall_n$.

Using (6) and the Mean Value Theorem

$$\begin{eqnarray*} && \vert p_n-p\vert\approx \vert g(p_{n-1})-g(p)\vert=\vert g'... ...\vert\le k\vert p_{n-1}-p\vert\\ &&\mbox { where } \xi\in(a,b). \end{eqnarray*}$$

By induction

$$\vert p_n-p\vert\le k\vert p_{n-1}-p\vert\le k^2\vert p_{n-2}-p\vert\le\cdots k^n\vert p_0-p\vert.$$ (7)

Since $\vert k<1\vert$

$$\lim_{n\to\infty}\vert p_n-p\vert\le\lim_{n\to\infty}k^n\vert p_0-p\vert=0$$

and

$$\{p_n\}_{n=0}\to p.$$

$\Box$

Corollary If $g$ satisfies hypothesis of Fixed Point Iteration theorem, a bounds for the error involved in using $p_n$ to approximate $p$ are given by

$$\begin{eqnarray*} \vert p-p_n\vert\le k^n\max\{p_0-a, b-p_0\}\quad \mbox {(a)}\... ...k}\vert p_1-p_0\vert \qquad \forall n \ge 1\quad \mbox {(b)}\\ \end{eqnarray*}$$

Proof: (a) follows from (7):

$$\vert p_n-p\vert\le k^n\vert p_0-p\vert\le k^n\max\{p_0-a, b-p_0\} \mbox { since } p\in [a,b].$$

For $n\ge 1$

$$\vert p_{n+1}-p_n\vert=\vert g(p_n)-g(p_{n-1})\vert\le k\vert p_n-p_{n-1}\vert\le k^n\vert p_1-p_0\vert$$

therefore for $m>n\ge 1$

$$\begin{eqnarray*} \vert p_m-p_n\vert&=&\vert p_m-p_{m-1}+p_{m-1}\cdots +p_{n+1}... ...p_0\vert+k^{m-2}\vert p_1-p_0\vert+\cdots k^n\vert p_1-p_0\vert \end{eqnarray*}$$

Since $$\lim_{m\to\infty}p_m=p$$ then

$$\vert p-p_n\vert=\lim_{m\to\infty}\vert p_m-p_n\vert\le k^n\vert p_1-p_0\vert\sum^{\infty}_{i=0}k^i$$

Since $\sum^{\infty}_{i=0}k^i=\frac{1}{1-k}$ then

$$\vert p-p_n\vert\le\frac{k^n}{1-k}\vert p_1-p_0\vert.$$

$\Box$

Remark: Rate depends on $k$. The smaller $k$, the faster it converges.

Example: Consider $g(x)=(3x+18)^{\frac{1}{3}}$ for $x \in [0,\infty )$. This function is illustrated in Figure 19. Get matlab code used in the example.

Figure 19: Plot of $g(x)$

First we wish to ensure that the function maps $[0,\infty)$ into itself.

$$g([0,\infty))=[18^\frac{1}{3},\infty) \subset [0,\infty)$$

Next we look at the derivative of $g(x)$

$$\begin{eqnarray*} g'(x)&=&\frac{1}{3}(3x+18)^\frac{-2}{3} \times 3 \\ &=& \frac{1}{(3x+18)^\frac{2}{3}} \end{eqnarray*}$$

$$\vert g'(x)\vert=\frac{1}{(3x+18)^\frac{2}{3}}\leq \frac{1}{18^\frac{2}{3}} < 1 \mbox{ for }x \in [0,\infty)$$

This fulfills the requirements for a unique fixed point to exist in $[0,\infty)$. It also ensures that if we start with any non-negative value we will converge to the fixed point. The table below shows the first ten iterations for three different values of $x_0$. Figure 20a and Figure 20b illustrate the iteration history and the logarithm of the error, for a case starting with $x_0 = 0$.

Figure 20: Iteration history and the logarithm of the error. Case starting with $x_0 = 0$. $g(x)=(3x+18)^{\frac{1}{3}}$ for $x \in [0,\infty )$

Figure 21a and Figure 21b illustrate the iteration history and the logarithm of the error, for a case starting with $x_0 = 100$.

Figure 21: Iteration history and the logarithm of the error. Case starting with $x_0 = 100$. $g(x)=(3x+18)^{\frac{1}{3}}$ for $x \in [0,\infty )$

Finally, Figure 22a and Figure 22b illustrate the iteration history and the logarithm of the error, for a case starting with $x_0 = 10000$.

Figure 22: Iteration history and the logarithm of the error. Case starting with $x_0 = 10000$. $g(x)=(3x+18)^{\frac{1}{3}}$ for $x \in [0,\infty )$

$$\begin{array}{\vert\vert c\vert\vert c\vert c\vert c\vert\ve... ...x_{10} & 3.0000 & 3.0000 & 3.0000 \\ \hline \hline \end{array}$$

The iterations for the three different starting points all appear to converge on $3$. The log error plots are straight lines and they all have the same slope, indicating the same rate of convergence.

We can also prove analytically that $3$ is the fixed point of $g(x)$. A fixed point of $g(x)$ satisfies

$$x=(3x+18)^\frac{1}{3}.$$

We can rearrange this to get $x^3-3x-18=0$ which has one real root, $x=3$.

$\Box$

Example: Consider the function $g(x; \alpha)=\frac{x^2-2x+1}{\alpha}$ for $x \in [0,2]$. We will start with the initial value $x_0=0.1$ and consider what happens for various values of $\alpha$. -Figure show the iterations for $\alpha = 2.5,1.5,0.5 \mbox{ and } 0.49$, respectively.

Figure: (a) Iterations, (b) plot of $y=g(x;\alpha=2.5)$ and $y=x$. Here, $g(x; \alpha)=\frac{x^2-2x+1}{\alpha}$ for $x \in [0,2]$. (c) log of the error as a function of the iterate number.

Figure: (a) Iterations. (b) log of the error as a function of the iterate number.

Figure: (a) Iterations, (b) plot of $y=g(x;\alpha=0.5)$ and $y=x$. Here, $g(x; \alpha)=\frac{x^2-2x+1}{\alpha}$ for $x \in [0,2]$. (c) log of the error as a function of the iterate number.

Figure: (a) Iterations, (b) plot of $y=g(x;\alpha=0.49)$ and $y=x$. Here, $g(x; \alpha)=\frac{x^2-2x+1}{\alpha}$ for $x \in [0,2]$. (c) log of the error as a function of the iterate number.

They also plot $g(x; \alpha)$ on the same graph as $y=x$ so we can see the fixed point, and finally plot the log of the error for each value of $\alpha$. We can see that for both $\alpha=2.5$ and $\alpha=1.5$ the iteration converges to a fixed point. The log error plots are straight lines with the slope showing the convergence rate (Question: Why does the log error plot flatten off for $\alpha=2.5$?). In the case $\alpha=2.5$ we can see that it converges faster than the case $\alpha=1.5$. For $\alpha=0.5$ the fixed point does not converge but seems to bounce around different values in the interval $[0,2]$. In fact for values of $\alpha$ between $\frac{4}{3}$ and $\frac{1}{2}$ we get all sorts of interesting beheviour. For more information on this click here. But when we make $\alpha$ less than 0.5 the iteration is able to escape from the interval $[0,2]$ and once it does this it increases rapidly with each iteration until it causes an overflow error in the computer.

(b) $\alpha=1.5$. (c) $\alpha=0.5$. (d) $\alpha=0.49$.">Get matlab code used in the example.

Now lets see whether we can understand what is happening. First let us look at the range of the function

$$\mbox{Range}(g(x))=[0,\frac{1}{\alpha}]$$

This shows why the iterations blow up for $\alpha$ less than 0.5. For $\alpha<0.5$ the range is not within the domain of $g(x)$ (i.e. $[0,2]$) and so points may 'escape'. However for any value of $\alpha$ greater than a half the range is mapped to within the domain.

Next we need to look at the derivative of $g(x)$

$$g'(x)=\frac{2}{\alpha}(x-1)$$

The magnitude of the derivative is only less than one for all values of $x$ if $\alpha \geq 2$. Thus for any value of $\alpha$ greater than two the fixed point theorem holds and we have guaranteed convergence. We know, however, that we still get convergence to a fixed point for some values of $\alpha$ less than two. What is happening in these cases?

If $\alpha<2$ the magnitude of the derivative will be less than one for $(1-\frac{\alpha}{2},1=\frac{\alpha}{2})$. As long as the fixed point lies within this interval the theorem tell us that there will be a region around the fixed point where iterations will converge to the fixed point. This is the case as long as $\alpha>\frac{4}{3}$. As it turns out, we may still start at any point within $[0,2]$ and we will eventually arrive at the fixed point although convergence takes longer and longer the closer $\alpha$ is to the critical point.

For values of $\alpha<\frac{4}{3}$ the fixed point still exists but it becomes unstable (i.e. If you start close to the fixed point and iterate you will move away from it rather than towards it).

If we plot $g(x)$ and the line $y=x$ on the same graph we can see that there is only one fixed point within the interval $[0,2]$ for all values of $\alpha>0.5$. In fact we can calculate the value of the fixed point analytically by solving $g(x)=x$.

$$\begin{eqnarray*} x &=& \frac{x^2-2x+1}{\alpha} \\ \alpha x & = & x^2-2x+1 \\ 0 &=& x^2 -(2+\alpha)x+1 \end{eqnarray*}$$

This is a simple quadratic equation with two solutions

$$\hat{x}=\frac{2+\alpha \pm \sqrt{\alpha^2+4\alpha}}{2}$$

For $\alpha>0.5$ only the smaller of the two solutions lies within the interval $[0,2]$ and is the unique fixed point. $\Box$