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

Implementation of Iteration method in C

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 *