MTH2212 – Computational Methods and
Statistics
Solution of Linear System of Equations
Lecture 3:
Iterative Methods
Objectives
Introduction
Jacobi Method
Gauss-Seidel Method
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 2
Introduction
To solve the linear system Ax = b we may use either:
Direct Methods
- Gaussian elimination
- PLU decomposition
Iterative Methods
- Jacobi Method
- Gauss-Seidel Method
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 3
Iterative Methods
Suppose we solve Ax = b for a given matrix A by finding the
PLU decomposition
If we change the vector b, we may continue to use the PLU
If we change A, we now have to re-compute the PLU
decomposition: expensive
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 4
Iterative Methods
Instead, suppose we have solved the system
Ax = b
for a given matrix A
Suppose we change A slightly, e.g., modify a single resistor
in a circuit
If we call that new matrix Amod, is it possible to use the
solution to Ax = b to solve Amodx = b?
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 5
Iterative Methods
They provide an alternative to the elimination method.
Let Ax = b be the set of equations to be solved.
The system Ax = b is reshaped by solving the first equation
for x1, the second equation for x2, and the third for x3, …and
nth equation for xn.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 6
Iterative Methods
For ease of computation, let’s assume we have a 3x3 system
of equations to solve.
a11 x1 a12 x 2 a13 x3 b1
a21 x1 a22 x2 a 23 x3 b2
a x a x a x b
31 1 32 2 33 3 3
If the diagonal elements are all non-zero then:
b1 a12 x2 a13 x3
x1
a11
b2 a21 x1 a 23 x3
x2
a 22
b3 a31 x1 a32 x 2
x3
a33
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 7
Jacobi Iteration Method
1. Assume all the x’s are zero
2. Substitute the zeros into the three equations to get:
b1 b2 b3
x1 x2 x3
a11 a22 a33
3. Repeat the procedure until the error criterion is satisfied:
i 1 b1 a12 x2i a13 x3i
x1
a11
x ij x ij1
i 1 b2 a21 x1i a23 x3i a, j 100% s
x 2 x i
a22 j
i 1 b3 a31 x1i a32 x2i
x3
a33
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 8
Gauss-Seidel Method
It is the most commonly used iterative method.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 9
Gauss-Seidel Procedure
1. Assume all the x’s are zero
2. Substitute the zeros into the first equation i.e. equation (1)
to give: b
x1 1
a11
3. Substitute the new value of x1 and x3 = 0 into equation (2) to
compute x2
4. Substitute the value of x1 and the new value of x2 in
equation (3) to estimate x3
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 10
Gauss-Seidel Procedure
5. Return to equation (1) and repeat the entire procedure until
the error criterion is satisfied:
i 1 b1 a12 x2i a13 x3i
x
1
a11
i 1 b2 a21 x1i 1 a23 x3i
x2
a22
i 1 b3 a31 x1i 1 a32 x2i 1
x
3
a33
x ij x ij1
a, j i
100% s
x j
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 11
Example 1
Use Gauss-Seidel method to solve the following set of
linear equations:
3x1 – 0.1x2 – 0.2x3 = 7.85 (1)
0.1x1 + 7x2 – 0.3x3 = -19.3 (2)
0.3x1 – 0.2x2 + 10x3 = 71.4 (3)
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 12
Example 1 - Solution
First we have:
7.85 0.1x 2 0.2 x3
x1
3
19.3 0.1x1 0.3 x3
x2
7
71.4 0.3 x1 0.2 x 2
x3
10
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 13
Example 1 - Solution
1st iteration
Assume that x2 = 0 and x3 = 0, we obtain
7.85
x1 2.616667
3
Substitute x1 = 2.616667 and x3 = 0 into equation (2)
19.3 0.1(2.616667) 0
x2 2.794524
7
Substitute x1 = 2.616667 and x2 = -2.794524 into equation (3)
71.4 0.3( 2.616667 ) 0.2( 2.794524)
x3 7.005610
10
This completes the first iteration
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 14
Example 1 - Solution
2nd iteration
7.85 0.1(2.79454) 0.2(7.005610)
x1 2.990557
3
19.3 0.1(2.990557 ) 0.3(7.005610)
x2 2.499625
7
71.4 0.3(2.990557) 0.2(2.499625)
x3 7.000291
10
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 15
Example 1 - Solution
Error estimate
For x1
2.990557 2.6166667
a ,1 100% 12.5%
2.990557
For x2
2.499625 (2.794524)
a,2 100% 11 .8%
2.499625
For x3
7.000291 7.005610
a ,3 100% 0.07%
7.000291
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 16
Convergence
Gauss-Seidel is similar in spirit to the simple fixed-point
iteration.
Gauss-Seidel will converge if for every equation of the
system, we have: n
aii aij
j 1
j i
Such system is said to be diagonally dominant.
This criterion is sufficient but not necessary for
convergence.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 17
Relaxation
Designed to Enhance convergence.
After each new value of x is computed, that value is
modified using:
xinew xinew 1 xiold
Where 0 2 is a weighting factor.
The choice of is problem-specific and is often determined
empirically.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 18
Gauss-Seidel/Jacobi Iteration Methods
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 19
Gauss-Seidel/Jacobi Iteration Methods
Gauss-Seidel iteration converges more rapidly than the
Jacobi iteration does; since, it uses the latest updates.
But there are some cases that Jacobi iteration does converge
but Gauss-Seidel does not.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 20
Assignment #1
Computational Methods
12.11, 12.30, 12.33
Statistics
2.2, 2.14, 2.22, 2.26, 2.28, 2.37, 2.45, 2.52, 2.65, 2.74
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 21
