Lu Decomposition

Linear Algebraic Equations: LU DECOMPOSITION

Chapter 3

Representing Linear Algebraic Equations in Matrix Form

a11 x1 + a12 x2 +  + a1n xn = b1  a 21 x1 + a 22 x2 +  + a 2 n xn = b2    a n1 x1 + a n 2 x2 +  + a nn xn = bn [ A]{ X } = {B}

LU DECOMPOSITION •

By using this method, system of linear equations [A]{x}={b} will be transformed to [L][U]{x}={b} where [L] is a lower triangular matrix and [U] is an upper triangular matrix.

•

In this course, 4 methods to decompose matrix A into matrix L and U will be discussed which are : (i)

Gauss Elimination Method

(ii)

Doolittle Method

(iii) (iv)

Crout Method Cholesky Method

LU DECOMPOSITION 1) Solve [L]{y}={b} by using forward substitution. 2) Solve [U]{x}={y} by using backward substitution.

5) LU Decomposition which is categorized under direct method also known as matrix factorization.

DOOLITTLE METHOD  a11 a  21 a31

a12 a 22 a32

a13   1 0 0 u11 u12 u13  a 23  = l 21 1 0  0 u 22 u 23  a33  l 31 l 32 1  0 0 u 33  u12 u13  u11   = l 21u11 l 21u12 + u 22 l 21u13 + u 23  l 31u11 l 31u12 + l 32 u 22 l 31u13 + l 32 u 23 + u 33 

DOOLITTLE METHOD u11 = a11 u12 = a12 u13 = a13 a 21 u11

a 21 = l 21u11

→

l 21 =

a 22 = l 21u12 + u 22

→

u 22 = a 22 − l 21u12

a 23 = l 21u13 + u 23

→

u 23 = a 23 − l 21u13

a31 = l31u11

→

l31 =

a31 u11

a32 = l31u12 + l32 u 22

→

l 32 =

a32 − l31u12 u 22

a33 = l31u13 + l32 u 23 + u 33

→

u 33 = a33 − l 31u13 − l 32 u 23

EXAMPLE 1 Solve the following system of linear equations using Doolittle Method.

3x1 − x 2 + 2 x3 = 12 x1 + 2 x 2 + 3x3 = 11 2 x1 − 2 x 2 − x3 = 2

SOLUTION 1 Step 1: Convert the system of linear equations into the matrix form,

[ A]{ x} = { b}.

3 − 1 2   x1  12     1 2  3 x = 11     2   2 − 2 − 1  x3   2 

SOLUTION 1 Step 2: Decompose [A] into [L] and [U] using Doolittle formula. u11 = 3 u12 = −1 u13 = 2 1 = l 21 ( 3) 2 = ( 0.3333)( − 1) + u 22

→

1 = 0.3333 3 = 2.3333

l 21 =

3 = ( 0.3333)( 2 ) + u 23

→

u 22

→

u 23 = 2.3334

2 = l31 ( 3)

→

l 31 =

− 2 = ( 0.6667 )( − 1) + l32 ( 2.3333)

→

− 1 = ( 0.6667 )( 2 ) − ( 0.5714 )( 2.3334 ) + u 33 →

2 = 0.6667 3 − 1.3333 l32 = = −0.5714 2.3333 u 33 = −1.0001

SOLUTION 1 Step 2: Decompose [A] into [L] and [U] using Doolittle formula.

3 − 1 2  1 2  = [ L][U ] 3   2 − 2 − 1 0 0 3 −1 2   1 =  0.3333 1 0 0 2.3333 2.3334  0.6667 − 0.5714 1 0 0 − 1.0001

SOLUTION 1 Step 3: Solve [ L ]{ y} = { b} using forward substitution. 0 0  y1  12  1  0.3333   y  = 11 1 0   2    0.6667 − 0.5714 1  y 3   2  y1 = 12 0.3333(12 ) + y 2 = 11

→

y 2 = 7.0004

0.6667(12 ) − 0.5714( 7.0004 ) + y 3 = 2

→

y 3 = −2.0004

SOLUTION 1 Step 4: Solve [U ]{ x} = { y} using backward substitution. 3 0  0

−1

 x1   12      2.3333 2.3334 x 2  =  7.0004     0 − 1.0001 x3  − 2.0004 2

− 1.0001x3 = −2.0004

→

x3 = 2.0002

2.3333 x 2 + 2.3334( 2.0002 ) = 7.0004 3 x1 − 0.9999 + 2( 2.0002 ) = 12

→

→

x 2 = 0.9999

x1 = 2.9998

EXAMPLE 4 1) Solve the following system using Gauss Elimination Method with partial pivoting

2 x1 + 5 x2 + 8 x3 = 36 4 x1 + 8 x2 − 12 x3 = −16 x1 + 8 x2 + x3 = 20

Exercise 1 Solve the following system using Doolittle and Cholesky methods. The exact solution is given and compare the true error between the methods. 5 x1 + 3x2 + x3 = 9 3 x1 + 6 x2 + 2 x3 = 11 x1 + 2 x2 + 7 x3 = 10

 x1 = 1   x2 = 1 x = 1  3