INDIRECT METHODS FOR
S O LV I N G S Y S T E M S O F L I N E A R
E Q U AT I O N S
ITERATIVE METHODS
• The preceding methods of solving the system of simultaneous
algebraic linear equations are direct methods, as these methods
yield the solution after a certain amount of fixed computation.
• On the other hand, an iterative method is that in which we start
from an approximation to the true solution and obtain better and
better approximations from a repeated computation as often as
may be necessary for achieving a desired accuracy.
CONT’D
• Thus in an iterative method, the number of iterations depends on
the degree of accuracy required and the initial solution.
• This iterative method is not always successful to all systems of
equations.
• If this method is to succeed, each equation of the system must
possess one large coefficient and the large coefficient must be
attached to a different unknown in that equation.
CONT’D
•Let us, consider a system with three equations and
three unknowns for a while, and later we can extend this
discussion to any number of equations & unknowns.
Suppose
CONT’D
and assume that the coefficients in the leading diagonal are large
enough so that
a11 a12 a13
a22 a21 a23
a33 a31 a32
• This system is then solvable by the iteration method.
CONT’D
• In other words, the solution exists (iteration will converge) if
the absolute values of the leading diagonal elements of the
coefficient matrix A of the system Ax = B are greater than the
sum of absolute values of the other coefficients of the row. We
say such a matrix A, a diagonally dominant matrix.
• Notice that the condition is sufficient but not necessary.
CONT’D
1. Gauss-Jacobi method or Jacobi method iteration
Suppose a1 x b1 y c1 z d1
a2 x b2 y c2 z d 2
a3 x b3 y c3 z d 3 ………. (1)
Without loss of any generality let us assume that
a1 b1 c1
b2 a2 c2
c3 a3 b3
CONT’D
Now solve for x, y and z (whose coefficients are the larger values) in terms
of the other variables. That is
1
x d1 b1 y c1 z
a1
1
y d 2 a2 x c2 z
b2
1
z d3 a3 x c3 y ……….. (2)
c3
Let us choose an initial approximations x 0 , y 0 , z 0 for the values of x, y and z
respectively.
1
Thus x1 d1 b1 y0 c1 z0
a1
1
y1 d 2 a2 x0 c2 z0
b2
1
z1 d3 a3 x0 b3 y0
c3
CON’T
Now use these values of x1 , y1 , z1 in (2) and get
1
x2 d1 b1 y1 c1 z1
a1
1
y2 d 2 a2 x1 c2 z1
b2
1
z2 d3 a3 x1 b3 y1
c3
Proceeding in the same way, if the rth iterates are x r , y r , z r ,
1
then xr 1 d1 b1 yr c1 zr
a1
1
y r 1 d1 a 2 x r c 2 z r
b2
1
z r 1 d 3 a3 x r b3 y r
c3
This process is repeated till the difference between two consecutive
approximations is very small as the desired accuracy.
To have a clear understanding on this method let us see some examples.
CONT’D
Example 1. Solve the following system by Gauss-Jacobi iteration
method correct to five decimal places
10 x y 2 z 7
3x 10 y z 15
x y 10 z 20
CONT’D
Solution
We see that the coefficient matrix is diagonally dominant so we can apply
Gauss-Jacobi iteration method. To do this first let us write the given equations
as
1
x 7 y 2z
10
1
y 15 3x z …….. (1)
10
1
z 20 x y
10
Let the starting solution be x 0 0 y 0 z 0
7
Thus x1 0.7
10
15
y1 1. 5 and
10
20
z1 2
10
CONT’D
Now using these values of x, y and z , in (1) and let us find for the second
iteration.
1
x2 7 1.5 2)( 2) 0.95
10
1
y2 15 3(0.7) 2 1.09
10
1
z2 20 0.7 1.5 1.92
10
Again substituting these values in (1), we obtain
1
x3 7 1.09 2(1.92) 0.975
10
1
y3 (15 3(0.95) (1.92) 1.023
10
1
z3 (20 0.95 1.09) 1.986
10
CONT’D
Putting these values once again in (1), we get
1
x4 7 1.023 2(1.986) 0.9949
10
1
y4 (15 3(0.975) 1.986) 1.0089
10
1
z4 (20 0.975 1.023) 1.9952
10
Putting these values in (1), we have
1
x5 7 1.0089 2(1.9952) 0.99815
10
1
y5 (15 3(0.9949) 1.9952) 1.00201
10
1
z5 (20 0.9949 1.0089) 1.9986
10
CONT’D
Putting these values again in (1), we get
1
x6 7 1.00201 2(1.9986) 0.999519
10
1
y6 (15 3(0.99815) 1.9986) 1.000695
10
1
z6 (20 0.99815 1.00201) 1.999614
10
Putting these values again in (1), we have
1
x7 7 1.000695 2(1.999614) 0.9998533
10
1
y7 (15 3(0.999519) 1.999614) 1.0001829
10
1
z7 (20 0.999519 1.000695) 1.9998824
10
CONT’D
Putting these values again in (1), we obtain
1
x8 7 1.001829 2(1.9998824) 0.99995819
10
1
y8 (15 3(0.998533) 1.9998824) 1.00005577
10
1
z8 (20 0.9998533 1.0001829) 1.99996704
10
Putting these again in (1) we have
1
x9 7 1.00005577 2(1.99996704) 0.999987831
10
1
y9 (15 3(0.99995819) 1.99996704) 1.00005839
10
1
z9 (20 0.99995819 1.00005577) 1.999990242
10
CONT’D
Putting these values once again in (1), we get
1
x10 7 1.000015839 2(1.999990242) 0.9999964645
10
1
y10 (15 3(0.999987831) 1.99996704) 1.000006947
10
1
z10 (20 0.999987831 1.000015839) 1.999997199
10
Now again putting these values in (1), we have
1
x11 7 1.000006947 2(1.999997199) 0.9999987451
10
1
y11 (15 3(0.9999964645) 1.999997199) 1.000001341
10
1
z11 (20 0.9999964645 1.000006947) 1.999998951
10
Thus correct to five decimal places the solution of the given equation is
x 1, y 1 and z 2 .
Jacobi method : Example 2
Consider the following set of equations.
10 x1 x2 2 x3 6
x1 11 x2 x3 3x4 25
2 x1 x2 10 x3 x4 11
3 x2 x3 8 x4 15
Convert the set Ax = b in the form of x = Tx + c.
1 1 3
x1 x2 x3
10 5 5
1 1 3 25
x2 x1 x3 x4
11 11 11 11
1 1 1 11
x3 x1 x2 x4
5 10 10 10
3 1 15
x4 x2 x3
8 8 8
Jacobi method : Example 2
(1) 1 (0) 1 (0) 3
x1 x2 x3
10 5 5
(1) 1 ( 0) 1 (0) 3 ( 0) 25
x2 x1 x3 x4
11 11 11 11
(1) 1 (0) 1 (0) 1 (0) 11
x3 x1 x2 x4
5 10 10 10
(1) 3 (0) 1 (0) 15
x4 x2 x3
8 8 8
(0) (0) (0) (0)
x1 0, x2 0, x3 0 and x4 0.
(1) 1 1 3
x1 (0) (0)
(1)
(1) 1
10 5
1 3
5
25 x1 0.6000,
x2 (0) (0) (0)
11 11 11 11 (1)
(1) 1 1 1 11 x2 2.2727,
x3 (0) (0) (0)
5 10 10 10 (1)
(1) 3 1 15 x3 1.1000
x4 (0) (0)
8 8 8 (1)
x4 1.8750
Jacobi method : Example 2
(2) 1 (1) 1 (1) 3
x1 x2 x3
10 5 5
( 2) 1 (1) 1 (1) 3 (1) 25
x2 x1 x3 x4
11 11 11 11
( 2) 1 (1) 1 (1) 1 (1) 11
x3 x1 x2 x4
5 10 10 10
( 2) 3 (1) 1 (1) 15
x4 x2 x3
8 8 8
(k) 1 ( k 1) 1 ( k 1) 3
x1 x2 x3
10 5 5
(k ) 1 ( k 1) 1 ( k 1) 3 ( k 1) 25
x2 x1 x3 x4
11 11 11 11
(k ) 1 ( k 1) 1 ( k 1) 1 ( k 1) 11
x3 x1 x2 x4
5 10 10 10
(k ) 3 ( k 1) 1 ( k 1) 15
x4 x2 x3
8 8 8
Jacobi method : Example 2
Results:
iteration 0 1 2 3
(k ) 0.0000 0.6000 1.0473 0.9326
x1
(k ) 0.0000 2.2727 1.7159 2.0530
x2
(k ) 0.0000 -1.1000 -0.8052 -1.0493
x3
(k ) 0.0000 1.8750 0.8852 1.1309
x4
JACOBI METHOD : EXAMPLE 3
A diverging case study:
2 1 5 x1 15 0
4 8 1 x 21
2 x 0 0 b Ax 0 26.7395
2
4 1 1 x3 7 0
The matrix is not diagonally dominant
15 x20 5 x30 15
x
1
1
7.5
2 2 b Ax1 54.8546
21 4 x10 x30 21 2
x2
1
2.625
8 8
x31 7 4 x10 x20 7.0
JACOBI METHOD : EXAMPLE 4
15 2.625 5 7
x
1
1 11 .3125
2
21 4 7.5 7
x2
1
0.25
8 b Ax 2 208.3761
2
x31 7 4 7.5 2.625 39.625
The residual term is increasing at each iteration,
so the iterations are diverging.
Note that the matrix is not diagonally dominant
2. GAUSS-SEIDEL ITERATION METHOD
This method is a refinement of Gauss-Jacobi method.
We consider all the hypothesis of the Gauss-Jacobi method and write the given
equations as
1
x d1 b1 y c1z
a1
1
y d 2 a2 x c2 z ..........
b2
1
z d3 a3 x b3 y
c3
CONT’D
We start with the initial values y 0 , z 0 for y and z , and get x , from the first
equation of (*)
1
x1 d1 b1 y0 c1z0
a1
Then use this value of x x1 and z z 0 in (*) to get
1
y1 d 2 a2 x1 c2 z0
b2
Now use x x1 and y y1 in the 3rd equation of (*) to get
1
z1 d3 a3 x1 b3 y1
c3
CONT’D
Continuing again using these values of y y1 , and z z1 in (*), we get
1
x2 d1 b1 y1 c1 z1
a1
Again use x x 2 , z z1 to solve y2
1
y2 d 2 a2 x2 c2 z1
b2
Putting these values of x x 2 and y y 2 to get z 2 , we obtain
1
z2 d3 a3 x2 b3 y2
c3
This process of iteration is repeated till the values of x, y and z is obtained to the
desired degree of accuracy.
CONT’D
Note – As the current values of the unknowns at each stage of
iteration are used in getting the values of unknowns, the
convergence in Gauss-Seidel method is very fast when
compared to the Gauss-Jacobi method.
Example 2 Solve the following system by Gauss-Seidel methods
correct to 3 decimal places.
5 x 2 y z 4
x 6 y 2 z 1
3x y 5 z 13
CONT’D
Solution
Since the coefficient matrix is a diagonally dominant matrix we can apply
the Gauss-Seidel method.
1
x 4 2 y z
5
1
y 1 x 2z .............1
6
1
z 13 3 x y
5
Take y 0 0 z 0 as a starting point, and get
1
x1 4 0.8
5
Now putting x x1 and z 0 0 , we obtain
1
y1 1 (0.8) 0.033333333
6
Putting x x1 and y y1 , in (1), we get
1
z1 13 3(0.8) (0.033333333) 3.086666667
5
CONT’D
2nd iteration
Putting y y1 and z z1 in (1), we have
1
x2 4 2(0.03333333 3.0866666667) 1.430666667
5
Put x x 2 and z z1 in (1) to get
1
y2 1 1.430666667 2 3.086666667 1.100666667
6
Put x x 2 and y y1 in (1) and get
1
z2 13 3 1.430666667 1.100666667 3.238266667
5
CONT’D
3rd iteration
1
x3 4 2 1.430666667 3.238266667 2.01992
5
1
y3 1 2.01992 2 3.238266667 1.249408889
6
1
z3 13 3 2.01992 1.249408889 3.562070222
5
4th iteration
1
x4 4 2 1.249408889 3.562070222 1.012650489
5
1
y4 1 1.012650489 2 3.562070222 1.189465156
6
1
z4 13 3 1.012650489 1.189465156 2.969697262
5
CONT’D
5th iteration
1
x5 4 2 1.189465156 2.969697262 0.91815339
5
1
y5 1 0.91815339 2 2.969697262 0.976257985
6
1
z5 13 3 0.91815339 0.976257985 2.955640437
5
6th iteration
1
x6 4 2 0.976257985 2.955640437 1.000624893
5
1
y6 1 1.000624893 2 2.955640437 0.985317627
6
1
z6 13 3 1.000624893 0.985317627 3.00331141
5
CONT’D
7th iteration
1
x7 4 2 0.985317627 3.00331141 1.006535231
5
1
y7 1 1.006535231 2 3.00331141 1.002193009
6
1
z7 13 3 1.006535231 1.002193009 3..003482537
5
8th iteration
1
x8 4 2 1.002193009 3.003482537 0.999819303
5
1
y8 1 0.999819303 2 3.003482537 1.00113073
6
1
z8 13 3 0.999819303 1.00113073 2.999665436
5
GAUSS-SEIDEL METHOD: EXAMPLE 2
Given the system of equations The coefficient matrix is:
12x 1 3x 2 - 5x 3 1
x 1 5x 2 3x 3 28 12 3 5
3x1 7x2 13x3 76
A 1 5 3
3 7 13
With an initial guess of
Will the solution converge using the
x1 1
Gauss-Siedel method?
x 0
2
x3 1
GAUSS-SEIDEL METHOD: EXAMPLE
Step 1:Checking if the coefficient matrix is diagonally dominant
a11 12 12 a12 a13 3 5 8
12 3 5
A 1 5 3 a 22 5 5 a 21 a 23 1 3 4
3 7 13 a33 13 13 a31 a32 3 7 10
The coefficient matrix is diagonally
dominant
Therefore, The solution should converge
using the Gauss-Siedel Method
GAUSS-SEIDEL METHOD: EXAMPLE
With an initial guess of
Step 2: Rewriting each equation
x1 1
12 3 5 a1 1 x 0
1 5 3 a 28 2
2 x3 1
3 7 13 a3 76
1 3 0 51
1 3 x 2 5 x3 x1 0.50000
x1 12
12 28 0.5 31
x2 4.9000
28 x1 3 x3 5
x2
5
76 3 0.50000 7 4.9000
76 3 x1 7 x 2 x3 3.0923
x3 13
13
GAUSS-SEIDEL METHOD: EXAMPLE
Step 3: The absolute relative approximate error
0.50000 1.0000
a 1 100 67.662%
0.50000
4.9000 0
a 2
100 100.00%
4.9000
3.0923 1.0000
a 3
100 67.662%
3.0923
The maximum absolute relative error after the first iteration is 100%
GAUSS-SEIDEL METHOD: EXAMPLE
Iteration #2 absolute relative approximate error
0.14679 0.50000
a 1 100 240.62%
0.14679
3.7153 4.9000
a 2
100 31.887%
3.7153
3.8118 3.0923
a 3 100 18.876%
3.8118
The maximum absolute relative error after the first iteration is
240.62%
This is much larger than the maximum absolute relative error
obtained in iteration #1. Is this a problem?
GAUSS-SEIDEL METHOD: EXAMPLE
Repeating more iterations, the following values are obtained
Iteration a1 a2 a3
a 1 a 2
a 3
1 0.50000 67.662 4.900 100.00 3.0923 67.662
2 0.14679 240.62 3.7153 31.887 3.8118 18.876
3 0.74275 80.23 3.1644 17.409 3.9708 4.0042
4 0.94675 21.547 3.0281 4.5012 3.9971 0.65798
5 0.99177 4.5394 3.0034 0.82240 4.0001 0.07499
6 0.99919 0.74260 3.0001 0.11000 4.0001 0.00000
x1 0.99919
The solution obtained
x
2 3 .0001
x3 4.0001
x1 1
is close to the exact solution of x 2 3
x3 4
