Finding Convergence, Part III: Fixed Point Iteration

The generalization of our square-root problem in Part I and Part II is that of finding the root of a non-linear function. Given a continuous and differentiable function \(f(x)\), we want to find a value of \(x\) such that

$$\ f(x) = 0$$

1. The first step in the application of the Fixed Point Iteration method is to algebraically manipulate \(f(x)\) so that we can rewrite the underlying relationship in the form of

$$\ x = g(x)$$

2. The second step is making a guess for a starting point, \(x_{0}\). In nearly all cases, the closer the initial guess is to the answer, the more likely the fixed point iteration will converge, and the faster the method will converge.

3. The main step in the algorithm is then expressed as an iterative application of

$$\ x_{n+1} = g(x_{n})$$

which we repeat until the change in \(x\) from one iteration to the next is insignificant in the context of our problem. In a computer implementation, it is often convenient to simply carry out a fixed number of iterations that we know to be more than enough iterations.

Example

Given the function below, let's perform steps 1 to 3:

$$\ f(x) = cos(x) - x$$

Step 1: Arrange the function so that \(x\) is on the left hand side. We want the form of \(f(x)=0\).

$$\ x = cos(x)$$

Step 2: Make an initial guess of  \(x\). 

We know that \(cos(x=0)=1\) and \(cos(x=\frac{\pi}{2})=0\). Therefore, the root must fall in somewhere between 0 and \(\frac{\pi}{2}\). Let's pick the middle,

$$\ x_{0} = \frac{\pi}{4}$$

The results are shown as below. We see that convergence takes place after around 15 iterations. However, it takes 29 iterations to get  \(f(x)\) to \(10^{-7}\).

 

                xn        g(x)                f(x)

0	0.785398	0.707107	-7.829138e-02
1	0.707107	0.760245	5.313782e-02
2	0.760245	0.724667	-3.557712e-02
3	0.724667	0.748720	2.405240e-02
4	0.748720	0.732561	-1.615904e-02
...	...	...	...
26	0.739087	0.739084	-2.715506e-06
27	0.739084	0.739086	1.829198e-06
28	0.739086	0.739085	-1.232170e-06
29	0.739085	0.739085	8.300044e-07
30	0.739085	0.739085	-5.591009e-07

Babylonian Method

Now, if we modify Step 3 using the Babylonian method described in Part II.

$$\ x_{n+1} = \frac{1}{2}(g(x_{n})+x_{n})$$

The result is shown as below. Clearly, the modified method converges much quicker compared to the original method, i.e. 15 iterations vs. 7 iterations.