Iteration Method or Fixed Point Iteration – Algorithm, Implementation in C With Solved Examples


Numerical Methods & Algorithms / Thursday, October 11th, 2018

Iteration Method or Fixed Point Iteration

The iteration method or the method of successive approximation is one of the most important methods in numerical mathematics. This method is also known as fixed point iteration.

Let f(x) be a function continuous on the interval [a, b] and the equation f(x) = 0 has at least one root on [a, b]. The equation f(x) = 0 can be written in the form
\[x=\phi \left( x \right)……….(1)\]
Suppose x0 Є [a, b] be an initial guess to the desired root ξ. Then φ(x0) is evaluated and this value is denoted by x1. It is the first approximation of the root ξ. Again, x1 is substituted for x to the right side of equation (1) and obtained a new value x2 = φ(x1). This process is continued to generate the sequence of numbers x0, x1, x2, …, xn, …. those are defined by the following relation
\[{{x}_{n+1}}=\phi \left( {{x}_{n}} \right)……….(2)\]
This successive iterations are repeated till the approximate numbers xn converges to the root with desired accuracy, i.e., |xn+1 – xn| < ϵ, where ϵ is a sufficiently small number. The function φ(x) is called the iteration function.

Algorithm of fixed point Iteration method

Step 1. Start the program.
Step 2. Define the function x = φ(x).
Step 3. Enter the initial guess of the root, say x0.
Step 4. Calculate y0 = φ(x0).
Step 5. If |x0 – y0| < ϵ, a prescribed accuracy, then go to step 7.
Step 6. Let x0 = y0 and go to step 4.
Step 7. Print the value of x0.
Step 8. Stop the program.

Implementation of Iteration method in C

/* Program Fixed Point Iteration
   Program to find the root of the equation x*x*x - 3x + 1 =0
   by fixed point iteration method. phi(x) is obtained by 
   rewrite f(x) = 0 as x = phi(x), which is to be supplied.*/

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define phi(x) (3*x-1)/(x*x)
/*definition of the function phi(x) and it to be
  changed accordingly */

void main()
{
	int k=0; //counts number of iterations
	float x1,x0; //initial guess
	float eps = 1e-5 //error tolerance

	printf("\nEnter the initial guess x0: ");
	scanf("%f",&x0);
	x1=x0;

	do
	{
		k++;
		x0=x1;
		x1=phi(x0);
	}while(fabs(x1-x0)>eps);
	printf("One root is %8.5f obtained at %d th iteration ",x1,k);
}

Output
Enter the initial guess x0: 1
One root is 1.53209 obtained at 37 th iteration

 Example 01

Compute one root of e-x – 3x = 0 correct to two decimal places between 0 and 1 using any suitable method.

Solution:

Let f(x) = e-x – 3x
Therefore f(0) = 1 and f(1) = -2.6321
So a root of the given equation lies between 0 and 1.
Let us write the given equation in the form
\[x=\frac{1}{3}{{e}^{-x}}=\phi \left( x \right)\]
\[\therefore \phi ‘\left( x \right)=-\frac{1}{3}{{e}^{-x}}\]
\[\therefore \left| \phi ‘\left( x \right) \right|=\frac{1}{3}{{e}^{-x}}=\frac{1}{3{{e}^{x}}}<1~[0,1]\]
Taking x0 = 0 and using the formula
\[{{\text{x}}_{\text{n}+\text{1}}}=\phi \left( {{\text{x}}_{\text{n}}} \right),n=0,1,2,…\]
We have
\[{{x}_{1}}=\phi \left( {{\text{x}}_{0}} \right)=\frac{1}{3}=0.3333\]
\[{{x}_{2}}=\phi \left( {{\text{x}}_{1}} \right)=\frac{1}{3}{{e}^{-0.3333}}=0.2388\]
\[{{x}_{3}}=0.2625,{{x}_{4}}=0.2564,{{x}_{5}}=0.2579\]
Thus the required root of the given equation is 0.26 correct to two decimal places.

 Example 02

Find a real root of the equation cos x = 2x – 3 correct upto three decimal places using iteration method.

Solution:
The given equation is f(x) = 2x – cos x – 3 = 0, so that f(0) = -4, f(1) = -1.9998 and f(2) = 0.0006. Hence a real root lies between 1 and 2.
We write the given equation f(x) = 0 in the form
\[x=\frac{1}{2}\left( \cos x+3 \right)=\phi \left( x \right)~~so~~that~~\]
\[\phi ‘\left( x \right)=-\frac{1}{2}\sin x~~and~~\left| \phi ‘\left( x \right) \right|<1\]
Hence the iterative method is applicable. Using the formula xn+1 =φ(xn) and taking x0 = 1, we have
\[{{x}_{1}}=1.7702,{{\text{x}}_{2}}=1.4010,{{\text{x}}_{3}}=1.5845,{{\text{x}}_{4}}=1.4931,\]
\[{{\text{x}}_{5}}=1.5388,{{\text{x}}_{6}}=1.5160,{{\text{x}}_{7}}=1.5274,{{\text{x}}_{8}}=1.5217,\]
\[{{\text{x}}_{9}}=1.5245,{{\text{x}}_{10}}=1.5231,{{\text{x}}_{11}}=1.5238,{{\text{x}}_{12}}=1.5235,\]
\[{{\text{x}}_{13}}=1.5236,{{\text{x}}_{14}}=1.5236\]
Thus the real root of the given equation correct to three decimal places is 1.524

Leave a Reply

Your email address will not be published. Required fields are marked *