The fixed point iteration method in numerical analysis is used to find an approximate solution to algebraic and transcendental equations. Sometimes, it becomes very tedious to find solutions to cubic, bi-quadratic and transcendental equations; then, we can apply specific numerical methods to find the solution; one among those methods is the fixed point iteration method.
The fixed point iteration method uses the concept of a fixed point in a repeated manner to compute the solution of the given equation. A fixed point is a point in the domain of a function g such that g(x) = x. In the fixed point iteration method, the given function is algebraically converted in the form of g(x) = x.
Learn about the Jacobian Method.
Fixed Point Iteration Method
Suppose we have an equation f(x) = 0, for which we have to find the solution. The equation can be expressed as x = g(x). Choose g(x) such that |g’(x)| < 1 at x = xo where xo,is some initial guess called fixed point iterative scheme. Then the iterative method is applied by successive approximations given by xn = g(xn – 1), that is, x1 = g(xo), x2 = g(x1) and so on.
Algorithm of Fixed Point Iteration Method
- Choose the initial value xo for the iterative method. One way to choose xo is to find the values x = a and x = b for which f(a) < 0 and f(b) > 0. By narrowing down the selection of a and b, take xo as the average of a and b.
- Express the given equation, in the form x = g(x) such that |g’(x)| < 1 at x = xo. If there more than one possibility of g(x), choose the g(x) which has the minimum value of g’(x) at x = xo.
- By applying the successive approximations xn = g(xn – 1), if f is a continuous function, we get a sequence of {xn} which converges to a point lo, which is the approximate solution of the given equation.
Important Facts
Some interesting facts about the fixed point iteration method are
- The form of x = g(x) can be chosen in many ways. But we choose g(x) for which |g’(x)|<1 at x = xo.
- By the fixed-point iteration method, we get a sequence of xn, which converges to the root of the given equation.
- Lower the value of g’(x), fewer the iterations are required to get the approximate solution.
- The rate of convergence is more if the value of g’(x) is smaller.
- The method is useful for finding the real roots of the equation, which is the form of an infinite series.
- The type of convergence seen is linear.
Related Articles
Solved Examples of Fixed Point Iteration
Example 1:
Find the first approximate root of the equation 2x3 – 2x – 5 = 0 up to 4 decimal places.
Solution:
Given f(x) = 2x3 – 2x – 5 = 0
As per the algorithm, we find the value of xo, for which we have to find a and b such that f(a) < 0 and f(b) > 0
Now, f(0) = – 5
f(1) = – 5
f(2) = 7
Thus, a = 1 and b = 2
Therefore, xo = (1 + 2)/2 = 1.5
Now, we shall find g(x) such that |g’(x)| < 1 at x = xo
2x3 – 2x – 5 = 0
⇒ x = [(2x + 5)/2]1/3
g(x) = [(2x + 5)/2]1/3 which satisfies |g’(x)| < 1 at x = 1.5
Now, applying the iterative method xn,= g(xn – 1) for n = 1, 2, 3, 4, 5, …
For n = 1; x1 = g(xo) = [{2(1.5) + 5}/2]1/3 = 1.5874
For n = 2; x2 = g(x1) = [{2(1.5874) + 5}/2]1/3 = 1.5989
For n = 3; x3 = g(x2) = [{2(1.5989) + 5}/2]1/3 = 1.60037
For n = 4; x4 = g(x3) = [{2(1.60037) + 5}/2]1/3 = 1.60057
For n = 5; x5 = g(x4) = [{2(1.60057) + 5}/2]1/3 = 1.60059
For n = 6; x6 = g(x5) = [{2(1.60059) + 5}/2]1/3 = 1.600597 ≈ 1.6006
The approximate root of 2x3 – 2x – 5 = 0 by the fixed point iteration method is 1.6006.
Example 2:
Find the first approximate root of the equation cos x = 3x – 1 up to 4 decimal places.
Solution:
Let f(x) = cos x – 3x + 1 = 0
As per the algorithm, we find the value of xo, for which we have to find a and b such that f(a) < 0 and f(b) > 0
Now, f(0) = 2
f(𝜋/2) = -3𝜋/2 – 1 < 0
Hence, xo is a value lying between 0 and 𝜋/2, for ease of calculation let us take xo = 0
Now, we shall find g(x) such that |g’(x)| < 1 at x = xo
cos x – 3x + 1 = 0
⇒ x = (cos x + 1)/3
Then g(x) = (cos x + 1)/3 which satisfies |g’(x)| < 1 at x = 0
Now, applying the iterative method xn,= g(xn – 1) for n = 1, 2, 3, 4, 5, …
For n = 1; x1 = g(xo) = (cos 0 + 1)/3 = ⅔ = 0.66667
For n = 2; x2 = g(x1) = {cos (0.66667) + 1}/3 = 0.595296
For n = 3; x3 = g(x2) = {cos (0.595296) + 1}/3 = 0.609328
For n = 4; x4 = g(x3) = {cos (0.609328) + 1}/3 = 0.6066778
For n = 5; x5 = g(x4) = {cos (0.6066778) + 1}/3 = 0.607182
For n = 6; x6 = g(x5) = {cos (0.607182) + 1}/3 = 0.607086
For n = 7; x7 = g(x6) = {cos (0.607086) + 1}/3 = 0.607105
For n = 8; x8 = g(x7) = {cos (0.607105) + 1}/3 = 0.607101 ≈ 0.6071
The approximate root of cos x = 3x – 1 by the fixed-point iteration method is 0.6071.
Practice Problems
1. Find the first approximate root of the equation x3 – x – 1 = 0 up to 4 decimal places.
2. Find the first approximate root of the equation x3 – 3x – 5 = 0 up to 4 decimal places.
3. Find the first approximate root of the equation 2x3 – 7x2 – 6x + 1 = 0 up to 4 decimal places.
Frequently Asked Questions on Fixed Point Iteration
What is the fixed point iteration method?
The fixed point iteration method is an iterative method to find the roots of algebraic and transcendental equations by converting them into a fixed point function.
How to determine the solution of the given equation by the fixed point iteration method?
The given equation f(x) = 0, is expressed as x = g(x). By guessing some initial xo The iterative method is applied by successive approximations given by xn = g(xn – 1). We get a sequence {xn} such that as xn → 𝛼 consequently f(x) → 0. Hence we get x = 𝛼 as a approximate solution.
How to determine the solution of a given equation in the lowest number of iterations?
The given equation f(x) = 0, is expressed as x = g(x). We must choose g(x) such that |g’(x)|<1 at x = xo. Lower the value of g’(x), the lesser the number of iterations required to get the approximate solution.
Comments