Aryendu Lal
LU decomposition
(Triangularization)
TOPICS TO COVER
Introduction 1
Definition 2
Why use it and application 3
Steps involved 4
Example question 5
1 Introduction
LU-decomposition (where 'LU' stands for
'lower upper', and also called LU
factorization) factors a matrix as the
product of a lower triangular matrix (L)
and an upper triangular matrix (U) was
introduced by mathematician Alan
Turing in 194
1 Definition
A K x k matrix is said to have an LU decomposition if and
only if there exists a lower triangular k x k
matrix L and an upper triangular k x k matrix U such that
A=LU
NOTE: Not all square matrices have an LU
decomposition, and it may be necessary to permute the
rows of a matrix before obtaining its LU factorization.
2 WHY USE IT AND APPLICATION
It is much easier to compute the inverse of an upper or lower
triangular matrix. Since inverses are useful for solving linear
systems, this makes solving any linear system associated to the
matrix much faster as well.
APPLICATION
•Solving linear systems of equations
•Calculating matrix inverses
•Calculating determinants
•Optimization
•Statistical analysis
•Machine learning
STEPS
1 2 3 4 5
Generate a Now, we can Let us From eq (1) Substituting
matrix A = LU write AX = B assume and (2), we Y in eq (2),
as: UX = Y have; we get
LUX =B….(1) LY = B UX = Y
On solving this By solving
equation, we eq we get X,
get y1, y2, y3. x1, x2, x3.
EXAMPLE
Solve the system of equations
x1 + x2 + x3 = 1, 3x1 + x2 – 3x3 = 5
and x1 – 2x2 – 5x3 = 10 by LU
decomposition method.
0 EXAMINING THE QUES
Given system of equations are:
x1 + x 2 + x 3 = 1
3x1 + x2 – 3x3 = 5
x1 – 2x2 – 5x3 = 10
1 Let us write the above matrix as LU = A.
1 writing the above matrix as LU = A.
Thus, by equating the corresponding elements,
we get;
u11 = 1, u12 = 1, u13 = 1
l21u11 = 3,
l21u12 + u22 = 1,
u21u13 + u23 = -3
l31u11 = 1,
l31u12 + l32u22 = -2,
l31u13 + l32u23 + u33 = -5
Solving these equations, we get;
u22 = -2, u23 = -6, u33 = 3
l21 = 3, l31 = 1, l32 = 3/2
2 LUX = B
From the previous two steps, we have
4 LY = B
So,
y1 = 1
3y1 + y2 = 5
y1 + (3/2)y2 + y3 = 10
Solving these equations, we get;
y1 = 1, y2 = 2, y3 = 6
5 Now, consider UX = Y. So,
By expanding this equation, we get;
x1 + x 2 + x3 = 1
-2x2 – 6x3 = 2
3x3 = 6
Solving these equations, we can get;
x3 = 2, x2 = -7 and x1 = 6
Therefore, the solution of the given system of equations is (6, -7, 2).
Thank you
