Fixed Point Iteration

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

Q1

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.

Q2

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.

Q3

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

Leave a Comment

Your Mobile number and Email id will not be published.

*

*