We draw the curve $g$ (in red in the figure).
We draw the line $y=x$ (in black in the figure). We are looking for the fixed point $g(x)=x$, that is, the intersection of the curve with the line.
We obtain the point $(x_0,f(x_0))$ on the curve.
We draw the horizontal line to the line $y = x.$ As it has the same ordinate as the point of the curve, the ordinate of the point on the line, that is, the coordinate $y$ is equal to $y=x,$ As for the points of the line $y=x,$ the coordinate $x$ is the same, that is, $x_1.$
We draw the vertical line to the curve and obtain the point $(x_1,f(x_1))$ on the curve.
We draw the horizontal line up to the line $y = x.$ Since it is at the same ordinate as the point of the curve, the ordinate of the point on the line, that is, the coordinate $y$ is equal to $x_2=f(x_1).$ As for the points of the line $y=x,$ the coordinate $x$ is the same, that is, $x_2.$
And we continue like this, curve, line, curve, line, $\ldots$

Convergence¶

The Contraction Mapping Theorem: let $g$ be a differentiable function defined in the interval $[a,b] \subset \mathbb{R} $ and $x_0 \in [a,b]$ is an initial guess. Suppose that

$x \in [a,b] \quad \Rightarrow \quad g(x)\in [a,b]$
$\left|g'(x)\right|\le k\lt 1$ for all $x\in [a,b]$

Then $g$ has a unique fixed point $\alpha \in [a,b]$, and the sequence $x_n$ defined as $x_{i+1}=g(x_i)$ with initial guess $x_0$ converges to $\alpha$ with order at least linear.

Let's see if these conditions are met by the function $g(x)=\cos x$ in the interval $[0,1]$

Graphically

If we look at the OY axis, we see that the graph of $g$ is always contained between 0 and 1. Therefore the first condition is met.
Also, the slope of the curve is always less than 1 in absolute value in the interval $[0,1].$ The references are the diagonals: if the curve is less steep than the corresponding diagonal (in this case the black one of slope $-1$), it meets the second condition.

Analytically

As $\cos(x)$ decreases in $\left[0,\dfrac{\pi}{2}\right]$
- and $[0,1]\subset\left[0,\dfrac{\pi}{2}\right]=\left[0,1.57\right]$
- then $\cos(x)$ decreases in $[0,1]$
- and has a maximum in $0$ and a minimum in $1$, that is
  
  $$\cos(1)\le \cos(x) \le \cos(0)$$ and $$0.54\le \cos(x) \le 1$$

and finally

$$\mathrm{Si}\quad x\in[0,1]\quad \Longrightarrow\quad \cos(x)\in [0.54,1]\subset[0,1]$$

$g'(x)=-\sin(x)$
- and $\left|g'(x)\right|=\sin(x)$ in $[0,1].$
- As $\sin(x)$ increases in $[0,1]$
- it has a maximum in $1$ and a minimum in $0$, that is

$$\sin(0)\le \sin(x) \le \sin(1)$$

and $$0\le \sin(x) \le 0.84$$

finally

$$\left|g'(x)\right|\le 0.84\lt 1 \;\mathrm{for}\; \mathrm{all}\; x\in [0,1]$$

As the Contraction Mapping Theorem conditions are met, we can choose any point within the interval $[0,1]$ as $x_0$ and the convergence of the sequence generated with the iteration function $g$ is guaranteed.

There are four possible cases:

Advantages¶

The fixed point method is very easy to implement.
It allows a systematic theoretical study of convergence.
It is really a set of methods: for example, Newton-Raphson is a fixed point method where $g(x)=x-f(x)/f'(x).$
Fixed point methods of the desired convergence order can be constructed.

Drawbacks¶

Methods with high convergence orders require the existence and good behavior of $g$ derivatives.
If we do not use the derivatives the order of convergence is linear and converges slowly.

Exercise¶

We want to find the zeros of the function $f(x)=x+\ln(x)$ using the fixed point method and the following iteration functions are proposed

$$(i)~g_{1}(x)=-\ln(x),\quad(ii)~g_{2}(x)=\text{e}^{-x},\quad(iii)~g_{3}(x)=\frac{x+\text{e}^{-x}}{2}$$

Prove that the solution of $f(x)=0$ is the fixed point of $g_{i}(x)=x,$ with $i=1,2,3.$
Check graphycally if the conditions of the Contraction Mapping Theorem are met for interval $\left[0,1\right].$
Perform nine iterations with each iteration function using as initial guess $x_{0}=0.5.$
What formulas may be used? What formula should be used?

Prove that the solution of $f(x)=0$ is the fixed point of $g_{i}(x)=x,$ with $i=1,2,3$¶

Let us verify that the root of the equation is the fixed point of the functions that are defined from the equivalent equations. That is,

$$f(x)=0\quad \Longleftrightarrow \quad g(x)=x$$

Let's start with the iteration function

$g_1(x)=-\ln x\\ x=-\ln x \Longleftrightarrow x+\ln x=0 \Longleftrightarrow f(x)=0 \;\mathrm{with}\; f(x)=x+\ln x$

$g_2(x)=e^{-x} \\ x=e^{-x} \Longleftrightarrow \ln x=\ln e^{-x} \Longleftrightarrow \ln x=-x \Longleftrightarrow \ln x+x=0 \Longleftrightarrow f(x)=0 \;\mathrm{with}\; f(x)=x+\ln x$

$g_3(x)=\dfrac{x+e^{-x}}{2} \\ x=\dfrac{x+e^{-x}}{2} \Longleftrightarrow 2x=x+e^{-x} \Longleftrightarrow x=e^{-x} \Longleftrightarrow f(x)=0 \;\mathrm{with}\; f(x)=x+\ln x$

Check graphycally if the conditions of the Contraction Mapping Theorem are met for interval $\left[0,1\right].$¶

The Contraction Mapping Theorem: let $g$ be a differentiable function derivable defined in the interval $[a,b] \subset \mathbb{R} $ and $x_0 \in [a,b]$ and initial guess. Suppose that

$x \in [a,b] \quad \Rightarrow \quad g(x)\in [a,b]$
$\left|g'(x)\right|\le k\lt 1$ for all $x\in [a,b]$

Then $g$ has a unique fixed point $\alpha \in [a,b]$, and the sequence $x_n$ defined as $x_{i+1}=g(x_i)$ with initial guess $x_0$ converges to $\alpha$ with order at least linear.

Looking at the graphs:

$g_1$ does not satisfy condition 2 (of the contractive application theorem) at any point.
$g_2$ meets condition 2 except perhaps at $0$ so we need an interval included in $[0,1]$ without the $0.$
$g_3$ meets the two conditions for the interval $[0,1]$ and we also see that it is the function with the smallest derivative (the most horizontal).

Perform nine iterations with each iteration function using as initial guess $x_{0}=0.5.$¶

If we start with $x_0=0.5$ with iteration function $g_1(x)=-\ln(x)$:

Iteration 1: $x_1=-\ln(0.5)=0.693147$
Iteration 2: $x_2=-\ln(0.693147)=0.366513$
Iteration 3: $x_3=-\ln(0.366513)=1.003722$
$\dots$

Similarly for the other functions

\begin{array}{|c|ccc|} \hline k & g_1 & g_2 & g_3\\ \hline 0 & 0.500000 & 0.500000 & 0.500000\\ 1 & 0.693147 & 0.606531 & 0.553265\\ 2 & 0.366513 & 0.545239 & 0.564167\\ 3 & 1.003722 & 0.579703 & 0.566500\\ 4 & -0.003715 & 0.560065 & 0.567004\\ 5 & \mathtt{NaN} & 0.571172 & 0.567113\\ 6 & \mathtt{NaN}& 0.564863 & 0.567137\\ 7 & \mathtt{NaN}& 0.568438 & 0.567142\\ 8 & \mathtt{NaN}& 0.566409 & 0.567143\\ 9 & \mathtt{NaN}& 0.567560 & 0.567143\\ \hline \end{array}

We see that, for the function $g_1,$ since it is not defined for negative values, from a certain point, the sequence is not defined.

We can assume that, if a series of decimals are repeated in successive iterations, they are correct. Thus, the sequences generated with $g_2$ and $g_3$ converge, but the one generated with $g_3$ converges faster because we can assume that as in $0.567143$ the 6 decimals are repeated in the last two iterations, this is the correct solution with 6 decimals. On the other hand, for $g_2$, with 9 iterations, only two decimal digits are repeated.

What formulas may be used? What formula should be used?¶

Taking into account the previous results, we can use $ g_2 $ and $g_3.$ The function $g_1$ does not meet the convergence conditions and the sequence generated by it does not converge.

The best iteration function is the one with the lowest derivative in the interval because it converges more quickly, that is, $g_3.$

Contents

Fixed point method¶

Algorithm¶