SSCE 2393 NUMERICAL METHODS

CHAPTER 2
LINEAR EQUATION SYSTEMS

Farhana Johar, Department of Mathematical Sciences, Faculty of Science, UTM.

[email protected]
 Overview Chapter 2

Linear Equation Systems

ELIMINATION METHOD ITERATION METHOD

GAUSS ELIMINATION JACOBI

GAUSS ELIMINATION WITH GAUSS-SEIDEL

PARTIAL PIVOTING

LU FACTORIZATION
• DOOLITTLE

• CROUT

• THOMAS METHOD

• THOMAS ALGORITHM

• CHOLESKY
2.1 INTRODUCTION OF LINEAR EQUATION SYSTEMS

Linear equations: ax = b
a11 x1 + a12 x2 +  + a1n xn = b1
a21 x1 + a22 x2 +  + a2 n xn = b2
    
am1 x1 + am 2 x2 +  + amn xn = bm

In matrix form ( A m×n x = b)

 a11 a12  a1n   x1   b1 
a a22  a2 n   x2  b2 
 21 =
          
    
am1 am 2  amn   xn  bn 

In augmented matrix form

 a11 a12  a1n b1 
 
 a21 a22  a2 n b2 
     
 
am1 am 2  amn bn 

We will only consider A n×n matrix (square matrix).

Elimination method
Solutions LU
Iteration
 2.1 Elimination Method

• Gauss Elimination
• Gauss elimination with partial pivoting

2.1.1 Gauss Elimination

Given:
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
Written in augmented matrix form as:
u11 u12 u13 f1 
 a11 a12 a13 b1   
 0 u22 u23 f 2 
Elementary row
 
 a21 a22 a23 b2  operations
 0 0 u33 f 3 
 a31 a32 a33 b3 
Ux = f
Ax = b Elementary row
operations
Backward
subst.
x3 = f3 u33  u11 u12 u13   x1   f1 
   
x2 ( f 2 − u33 x3 ) / u22
=
 0 u 22 u 23   2   f 2 
x =
x1 =( f1 − u12 x2 − u 13 x3 ) / u33  0 0 u   f 
 33   x3   3 
 Example 1:

Solve the following linear system using Gauss elimination method.

2.51x1 + 1.48 x2 + 4.53x3 = 5.56

1.48 x1 + 0.93x2 − 1.30 x3 = −0.75
2.68 x1 + 3.04 x2 − 1.48 x3 = −1.84

Solution
 2.51 1.48 4.53 5.56 B2 → −0.59 B1 + B2
1.48 0.93 − 1.30 − 0.75 
 
2.68 3.04 − 1.48 − 1.84 
multiplier, m21 = a21 a11 = 0.59 multiplier, m31 = a31 a11 = 1.07

B → −1.07 B + B
3 1 3

multiplier,

∴ Using backward substitution, we get:

Exercise:

Solve the following linear systems using Gauss elimination

method:

1. Use 4 decimal places.

5 − 1 1  x1  10 
2 4 0  x  = 12 
   2  
1 1 5  x3  − 1

2. Use 3 decimal places.

Ans: x3 = −1.0555, x2 = 1.7222, x1 = 2.5555

x4 = −0.325, x3 = −0.231, x2 = −0.458, x1 = −0.083
2.1.2 Gauss Elimination with Partial Pivoting

why????
• to solve problem that involve division by zero (in case a11 = 0
or a22 = 0)
• reduce the round-off errors.

The algorithm follows the Gauss elimination method except:

• Interchange rows when needed at the k-th step so that the
absolute value of pivot element a kk is the largest element
compare to the other elements underneath the pivot.

Then, do the elimination process.

Example 2:

Use Gauss elimination method with partial pivoting to solve:

0 0 3 4  x1  8
2 9 1 0  x  6 
   2 =  
0 1 9 4  x3  8
     
5 1 0 0  x4  9
Solution

Then we have:

Use backward subst. to get

 Exercise:

Solve the following systems using Gauss elimination method with

partial pivoting. Use 3 decimal places.

1.

2.

Ans: 1.
2.
2.2 LU FACTORIZATION METHOD

For a linear system

Ax = b

Use substitution of A = LU, where L is a lower triangular matrix,

and U is upper triangular matrix.

LUx = b
Let
Ux = Y
Yields
LY = b

L = a 0 0 0 U = k l m n
b c 0 0 
 0 u p q 
d  
e f 0 0 0 r s 
 
g h i j  
 0 0 0 t 

Procedure:

Step 1: From A = LU, solve for L and U.

Step 2: From LY = b , solve for Y by forward substitution.
Step 3: From Ux = Y , solve for x by backward substitution.
2.2.1 Doolittle Method

A = LU

Diagonal element for matrix L = 1 1 0 0 0

b 1 0 0

d e 1 0
 
g h i 1
Ax = b

objective to get the value of x

Step:

1. A = LU , find the matrix for L and U

2. Ly = b , solve for y use backward and forward

substitution
3. Ux = y , solve for x
Example 3:

Solve this equation system using Doolittle method.

3 x1 + 2 x2 + 9 x3 = 28
2 x1 − x2 + 6 x3 = 14
5 x1 + 2 x2 − 4 x3 = −13

Do the calculation in 4 decimal places.

Example 4:

Solve this equation system using Doolittle method.

2 x1 = 3
x1 + 1.5 x2 = 4.5
− 3 x2 + 0.5 x3 = −6.6
x4 + x3 + 2 x1 − 2 x2 − 0.8 = 0
2.2.2 Crout Method
A = LU
1 l m n
Diagonal element for matrix U = 1 0 1 p q 

0 0 1 s
 
0 0 0 1
Ax = b
objectiveto find the value of x

Step:

1. A = LU , determine L and U

2. Ly = b , solve for y use forward and backward

3. Ux = y , solve for x substitutions

Example 5:

Solve this linear system using Crout method.

3 x1 + 2 x2 + 9 x3 = 28
2 x1 − x2 + 6 x3 = 14
5 x1 + 2 x2 − 4 x3 = −13
2.2.3 Thomas Method
Ax = b
Check this first!

Make sure that matrix A must

be Tridiagonal Matrix

If not  rearrange the matrix

Ax = b
objective to find the value of x
Step:

1. A = LU , determine the matrix for L and U

2. Lw = b , solve for y use forward and backward

substitutions
3. Ux = w , solve for x

Example 6:

Solve this linear system equation using Thomas method.

1 3 0 0   x1   − 1 
1
 2 1 0   x2   1 
=
0 4 − 1 − 5  x3  − 20
    
0 0 2 3   x4   11 
2.2.4 Thomas Algorithm

Generalization of Thomas method

 suitable to solve large system
 Easy for programming coding

Remember! Always check whether Matrix A is tridiagonal matrix

or not…

Check this first!

If not  rearrange the matrix

di
ci
Formula:

Thomas’s Algorithm:

α 1 = d1
α i = d i − ci β i −1 , i = 2, 3, ..., n
ei
βi =
α i , i = 1, 2, 3, ..., n − 1
y1 = b1 / α1
, i = 2, 3, ..., n

, i = n − 1, n − 2, ..., 1

Table:
i 1 2  n
di
ei
ci
bi
αi
βi
yi
xi
Example 7:

Solve this linear system using Thomas method.

1 3 0 0   x1   − 1 
1
 2 1 0   x2   1 
=
0 4 − 1 − 5  x3  − 20
    
0 0 2 3   x4   11 

Example 8:

Given
3 x3 + 4 x4 = 8
2 x1 + 9 x2 + x3 = 6
x2 + 9 x3 + 4 x4 = 8
2 x1 + x2 = 9
(i) What condition that needs to be fulfilled before using
Thomas’s Algorithm?
(ii) If the system above satisfied the condition, solve the
equation system.
2.2.5 Cholesky Method

Ax = b
Matrix A must be symmetric positive-definite

Definition Rules (theorem)

/
xT Ax > 0, ∀x ≠ 0 1. A ≠ 0
2. aii > 0, ∀i = 1,2,, n

3. max akj ≤ max aii

1≤ k ≤ n 1≤ i ≤ n
1≤ j ≤ n
2
4. ( aij ) < aii a jj , ∀ i , j = 1, 2,  , n
i≠ j

A = LU
T
where U = L

Ax = b
Target to find the value of x
Step:

1. A = LU , determine L and U

2. Ly = b , solve for y use forward and backward

substitutions
3. Ux = y , solve for x
Example 9:

Show that matrix A for the following linear system is symmetric

positive-definite by using definition. Then, solve the system of
linear equations by Cholesky Method.

4 x1 − x2 + x3 = 7
− x1 + 7 x2 + 3x3 = 6
x1 + 3x2 + 5 x3 = 1
 2.3 ITERATIVE METHOD

Must satisfy convergence criterion i.e.

A must be strictly diagonally dominant matrix

Is A Strictly Diagonally Dominant Matrix?

n
aii > ∑ aij
j =1
j ≠i

if not  rearrange rows.

e.g.
3 2 0

Show that
2 −5 1 
is a SDD matrix.
1 2 7 
Solution:
B1 : 3 > 2 + 0
B2 : − 5 > 2 + 1
B3 : 7 > 2 + 1
2.3.1 Jacobi Method

Formula:

(k ) (k )
( k +1) b − a x − a13 x3
x1 = 1 12 2
a11
(k ) (k )
( k +1) b − a21 x1 − a23 x3
x2 = 2
a22
(k ) (k )
( k +1) b − a31 x1 − a32 x2
x3 = 3
a33

(0)
Initial guess: x = (0 0  0) T

Stop the iteration when:

max
1≤ i ≤ n
{ xi(k ) − xi(k −1) }< ε
for a given value of ε and take x ≈ x (k )

Example 10:

Solve the following linear system using Jacobi method.

Set x (0) = 0 . Take ε = 0.05 .

x1 − 3 x2 + 12 x3 = 31
4 x1 + x2 − x3 = 3
2 x1 + 7 x2 + x3 = 19
Solution

Is matrix A SDD?

Rearrange rows :
4 x1 + x2 − x3 = 3
2 x1 + 7 x2 + x3 = 19
x1 − 3 x2 + 12 x3 = 31

The iteration formula:

3 − x2 ( k ) + x3( k )
x1( k +1) =
4
( k +1) 19 − 2 x1( k ) − x3( k )
x2 =
7
( k +1) 31 − x1( k ) + x2 ( k )
x3 =
12

k x1( k ) x2 ( k ) x3( k ) x1( k ) − x1( k −1) x2 ( k ) − x2 ( k −1) x3( k ) − x3( k −1)

0 0 0 0
1
2
3
4
5

{
x (5) − x ( 4) = max xi (5) − xi ( 4)
1≤ i ≤ 3
}
= max {0.01, 0.01, 0.01} = 0.01 < ε
∴ x ≈ x (5) = (1.01, 2.00, 3.00)
2.3.2 Gauss Seidel Method

Formula:
(k ) (k )
( k +1) b1 − a12 x2 − a13 x3
x1 =
a11
( k +1) (k )
( k +1) b2 − a21 x1 − a23 x3
x2 =
a22
( k +1) ( k +1)
( k +1) b3 − a31 x1 − a32 x2
x3 =
a33

(0)
Initial guess: x = (0 0  0) T

Stop the iteration when:

max
1≤ i ≤ n
{ xi(k +1) − xi(k ) }< ε
for a given value of ε and take x ≈ x (k )

Example 11:

Solve the following linear system using Gauss-Seidel method.

Set x (0) = 0 . Take ε = 0.05 .

x1 − 3 x2 + 12 x3 = 31
4 x1 + x2 − x3 = 3
2 x1 + 7 x2 + x3 = 19
Solution

Is matrix A SDD?

Rearrange rows :
4 x1 + x2 − x3 = 3
2 x1 + 7 x2 + x3 = 19
x1 − 3 x2 + 12 x3 = 31

The iteration formula:

3 − x2 ( k ) + x3( k )
x1( k +1) =
4
( k +1) 19 − 2 x1( k +1) − x3( k )
x2 =
7
( k +1) 31 − x1( k +1) + x2 ( k +1)
x3 =
12

k x1( k ) x2 ( k ) x3( k ) x1( k ) − x1( k −1) x2 ( k ) − x2 ( k −1) x3( k ) − x3( k −1)

0 0 0 0
1
2
3
4

{
x ( 4) − x (3) = max xi ( 4) − xi (3)
1≤ i ≤ 3
}
= max {0.00, 0.00, 0.00} = 0.00 < ε

∴ x ≈ x (5) = (1.00, 2.00, 3.00)

Exercise:

1. Write the Gauss - Seidel formula for

5 x1 − x2 + x3 = 11
2 x1 + 8 x2 − x3 = 17
− x1 + x2 + 7 x3 = 21

Then find the value of x1, x2, and x3. Do the calculation in 3 decimal
places.

2. Solve the following system using Gauss – Seidel method and

stop the iteration when x ( k ) − x ( k −1) < 0.0005 .
∞

10 − 1 2 0   x1   6 
− 1 11 − 1 3   x   25 
   2 =  
 2 − 1 10 − 1  x3  − 11
    
 0 3 − 1 8   x4   15 