A number \(p\) is a fixed point of a function \(g\) if \(g(p)=p\).

Example. If \(g(x)=x^2-2\), then solving \(g(x)=x^2-2=x\) we get \(x=-1,2\). We can easily check \(g(-1)=-1\) and \(g(2)=2\). Thus \(-1\) and \(2\) are fixed points of \(g\). Note that fixed points of \(g\) are the \(x\)-value of the points of intersection of the curve \(y=g(x)\) and the line \(y=x\).

The following shows the equivalence of root finding and finding fixed points.

Observation. \(p\) is a fixed point of a function \(g\) if and only if \(p\) is a root of \(f(x)=x-g(x)\).

If \(p\) is a fixed point of a function \(g\), then \(g(p)=p\) and consequently \(f(p)=p-g(p)=0\). The converse follows similarly. Note that there are multiple choices for \(f\) such as \(f(x)=e^x(x-g(x))\), \(f(x)=-1+e^{x-g(x)}\) etc.

The following theorem gives us sufficient conditions for existence and uniqueness of a fixed point:

Theorem.(Fixed Point Theorem) Let \(g\) be a function on \([a,b]\).

1. (Existence) If \(g\) is continuous and \(a\leq g(x)\leq b\) for all \(x\in [a,b]\), then \(g\) has a fixed point in \([a,b]\).


2. (Uniqueness) Moreover, if \(|g'(x)|<1\) for all \(x\in(a,b)\), then \(g\) has a unique fixed point in \([a,b]\).

Suppose \(a\leq g(x)\leq b\) for all \(x\in [a,b]\) and \(|g'(x)|\leq k<1\) for all \(x\in(a,b)\). For any initial approximation \(x_0\) in \([a,b]\), the fixed point iteration constructs a sequence \(\{x_n\}\), where \[\boxed{x_{n+1}=g(x_n),\;n=0,1,2,\ldots}\] to approximate the unique fixed point \(x^*\) of \(g\) in \([a,b]\). We will show \(\{x_n\}\) converges to \(x^*\).

Example. This problem approximates the root \(x^*\) of \(f(x)=e^x-x-2\) on the interval \([0,2]\).

1. Find a function \(g\) that has a unique fixed point which is the root \(x^*\) of \(f(x)=e^x-x-2\) on the interval \([0,2]\).


2. Do six iterations by the fixed point iteration to approximate the root \(x^*\) of \(f(x)=e^x-x-2\) on the interval \([0,2]\) using \(x_0=1\).

Solution. 1. We need to find a function \(g\) such that

• \(0\leq g(x)\leq 2\) for all \(x\in [0,2]\), and
• \(|g'(x)|<1\) for all \(x\in(0,2)\).

\(f(x)=e^x-x-2=0\implies x=e^x-2\). But \(g(x)=e^x-2\) does not satisfy (a) as \(g(0)=-2<0\) and also (b) as \(g'(2)=e^2>1\). Note that \[f(x)=e^x-x-2=0\implies e^x=x+2 \implies x=\ln(x+2).\] Take \(g(x)=\ln(x+2)\). Then \(g\) is an increasing function and \(g(0)=\ln 2>0\) and \(g(2)=\ln 4<2\). Thus \(0\leq g(x)\leq 2\) for all \(x\in [0,2]\). Also \(|g'(x)|=\frac{1}{x+2}\leq \frac{1}{2}<1\) for all \(x\in(0,2)\). Thus \(g\) has a unique fixed point in \([0,2]\) which is the root \(x^*\) of \(f(x)=e^x-x-2\) on the interval \([0,2]\). 2. Use \(g(x)=\ln(x+2)\) and \(x_0=1\). \[\begin{array}{|l|l|l|} \hline n & x_{n-1} & x_n=g(x_{n-1})\\ \hline 1 & 1 & 1.0986\\ \hline 2 & 1.0986 & 1.1309\\ \hline 3 & 1.1309 & 1.1413\\ \hline 4 & 1.1413 & 1.1446\\ \hline 5 & 1.1446 & 1.1456\\ \hline 6 & 1.1457 & 1.1460\\ \hline \end{array}\] Since \(|x_6-x_5|=|1.1460-1.1456|=0.0004<0.001=10^{-3}\), we can say that the root is \(x_6=1.1460\) roughly correct to three decimal places (which is true indeed as \(x^*=1.146193\)).

The Maximum Error: Let \(\varepsilon_n\) be the absolute error for the \(n\)th iteration \(x_n\). Then \[\begin{align*} \varepsilon_n=|x^*-x_n|\leq & k^n \max\{x_0-a, b-x_0\} \text{ and}\\ \varepsilon_n=|x^*-x_n|\leq & \frac{k^n}{1-k}|x_1-x_0|. \end{align*}\]

Convergence: The sequence \(\{x_n\}\) constructed by the fixed point iteration converges to the unique fixed point \(x^*\) irrespective of choice of the initial approximation \(x_0\) because \[\lim_{n\to \infty}|x^*-x_n|\leq \lim_{n\to \infty}k^n \max\{x_0-a, b-x_0\}=0 \;(\text{as }0< k <1) \implies \lim_{n\to \infty}|x^*-x_n|=0.\] It converges really fast when \(k\) is close to \(0\).

Example. Find the number of iteration by the fixed point iteration that guarantees to approximate the root \(x^*\) of \(f(x)=e^x-x-2\) on \([0,2]\) using \(x_0=1\) with accuracy within \(10^{-3}\).

Solution. Consider \(g(x)=\ln(x+2)\) on \([0,2]\) where \(|g'(x)|\leq \frac{1}{2}=k<1\) for all \(x\in(0,2)\). \[\begin{align*} & \varepsilon_n=|x^*-x_n|\leq k^n \max\{x_0-a, b-x_0\}=\left(\frac{1}{2}\right)^n\cdot 1<10^{-3} \\ \implies & 10^3< 2^{n}\\ \implies & \ln 10^3 < \ln 2^{n} \\ \implies & 3 \ln 10< n\ln 2 \\ \implies & \frac{3\ln 10}{\ln 2}\approx 9.97< n \end{align*}\] Thus 10th iteration guarantees to achieve accuracy of the root within \(10^{-3}\). But note that \(|x^*-x_5|=|1.1461-1.1457|=0.0004<10^{-3}\). So Thus accuracy within \(10^{-3}\) is reached at 5th iteration (way before 10th iteration). Also note that the other bound of \(\varepsilon_n=|x^*-x_n|\leq \frac{k^n}{1-k}|x_1-x_0| \) gives \(10.94< n\) which does not improve our answer.

Last edited