Tip:
Highlight text to annotate it
X
We are considering gauss elimination method for solving a system of linear equations.
Today, what we are going to show is that, this gauss elimination method is equivalent
to writing LU decomposition of matrix A. So, the A is the coefficient matrix, L is going
to be unit lower triangular matrix; that means, the diagonal entries, they are going to be
equal to 1 and U is upper triangular matrix. As I said these two methods like gauss elimination
method and LU decomposition, they are going to be equivalent. So, in terms of number of
computations, we do not save anything, but when we consider backward error analysis of
gauss elimination method, there this LU decomposition becomes convenient.
And for a positive definite matrix, we want to show that, matrix A has a Cholesky decomposition;
that means, it can be written as g into g transpose, where g is going to be lower triangular
matrix and n g transpose will be upper triangular matrix. So, for that, we are going to need
LU decomposition. So, what I am going to do is, I will first
illustrate it for 3 by 3 matrices and then consider general case n by n matrix. So, let
us recall, what we have done last time.
So, we have a system of equations, n equations in n unknowns, which we write in the compact
form as A x is equal to b, a is the coefficient matrix, b is right hand side vector which
is given to us, and x is unknown vector x 1, x 2, x i. We had assumed, that matrix A
is such that, if you look at principle leading sub matrix, which is formed by first k rows
and first k columns.
So, determinant of this A k is not equal to zero, for k is equal to 1 to up to n; this
condition is stronger than invertibility. The invertibility, it means that, determinant
of A is not equal to zero. Now, we want not only determinant A to be non-zero, but also
determinant of A k not equal to 0. Now, this Gauss elimination method, we will write, we
will show that it is equivalent to writing A as L into U.
So, the Gauss elimination method will be equivalent to saying A is equal to L into U, L is unit
lower triangular, U is upper triangular matrix; this is what we want to show and then that
will be the LU decomposition. So, we will always assume that, LU decomposition means,
L is unit lower triangular and U is upper triangular matrix. What we are going to show
is, yesterday we saw that using elementary row transformations, we had reduced A to an
upper triangular matrix U. So, that is going to be our U - upper triangular
matrix, and L unit lower triangular matrix will consist of the multipliers. In order
to introduce zeroes or to reduce matrix A to an upper triangular form, our first step
was, multiply the first row by a 21 by a 11, subtract it from second row, so this m 21
is equal to a 21 by a 11 is going to be multiplier. So, lower triangular matrix we are going to
show, that it will be such that, it will have one on the diagonal and the remaining entries
will be multipliers in the Gauss elimination method.
So, L is lower triangular along the diagonal 1. And here, you have got, m 21, m 31, m n
1, these were needed to introduce zeroes in the first column below the diagonal and so
on. So, we are going to first consider 3 by 3 matrix.
Now, here are some notations, e j will denote canonical vector, which has got only one at
jth place; all the other entries, they are 0. When we talk off vector x, it is always
going to be a column vector. So, this will be equal to x 1 e 1 plus x 2 e 2 plus x n
e n. i jth entry of n by n matrix, we denote by a ij, if you look at a multiplied by e
j; e j is this canonical vector, then what we get is jth column of a, you can verify
this. If you look at e i transpose A, then you will
get ith row of A; and if you consider e i transpose A e j, A is n by n matrix, e j is
n by 1 vector, e i transpose will be 1 by n vector. So, the result is going to be scalar
and that is our a i j.
So, now, let us look at 3 by 3 matrix. So, here it is a 3 by 3 matrix, and in the gauss
elimination, what we are doing is, the first step is going to be look at a 21 by a 11,
that is our m 21 and then R 2 minus m 21, r 1; then, you look at a 31 by a 11, that
is, m 31 and then R 3 minus m 31 r 1, this is the first type of gauss elimination method.
The way we we have chosen m 21 and m 31, the entries here they are going to be 0. So, you
are converting matrix A to this matrix. Now, this entry a 22, that will be modify to a
22 super script 1, which will be a 22 minus m 21 and then the corresponding entry a 12.
a 23 will be modified to a 23 minus m 21 and then a 13, that is the result of R 2 minus
m 21 R 1; then, a 21 becomes a 21 minus m 31 a 12, and a 331 becomes a 33 minus m 31
a 13. Now, these operations we could have performed by multiplying our matrix a by this
matrix. So, the matrix has one along the diagonal.
Here, you have entries to be 0 and here it is minus m 21 minus m 31. So, when I do pre
multiply matrix a by this matrix, first row into first column will give us a 11, then
first row into second column a 12, and first row into third column a 13. So, no change
in the first row; then, minus m 21 times a 11 plus a 21. Now, what was m 21? It is a
21 by a 11. So, a 21 by a 11 multiplied by a 11, that will give you a 21, because of
this minus sign, it will be a 21 and then you are subtracting. So, here this entry will
become 0; then, minus m 21 a 12 plus a 22 which is nothing but the right hand side here
and, so on. So, thus the first type of gauss elimination method is pre multiplying our
matrix a by this matrix.
So, now, consider matrix E 1. If I define m 1 to be this vector, 0, m 21, m 31, when
I look at m 1 E 1 transpose, E 1 is our canonical vector, E 1 transpose is 1 0 0, m 1 is this
vector, 0, m 21, m 31. When you multiply, you are going to get matrix of this form;
this is our E 1; this is m 1 E 1 transpose. So, E 1 will
be identity matrix minus m 1 E 1 transpose; if you look at E 1 transpose m 1, that means,
you are interchanging the order, so it is going to be 1 0 0 0, m 21, m 31; so, that
is going to be 0. Using this, you can check that i minus m 1 e 1 transpose into i plus
m 1 e 1 transpose is equal to identity, which means inverse of this matrix E 1 is going
to be identity plus m 1 e 1 transpose. So, this is the first type gauss elimination method.
Now, we are going to look at the second step. So, in the second step, we are looking at
only 3 by 3 matrix. So, we will have to make only one entry to be 0.
We are going to look at the third row, minus m 32 times r 2; this is after the first type
of gauss elimination method we have got this. Now, you define m 32 to be a 321 divided by
a 22 1, and subtract from the third row, the second row multiplied by m 32, you have zeroes
here. So, these will not be affected, this entry will become 0 and this entry will get
modified. So, a 332 is equal to a 331 minus m 32 a 231,
and you can verify, that this can be achieved by pre multiplying our matrix A 1 by this
matrix, you have got 100; so, the first row will remain unchanged. Second
row here is 010; so, the second row also remains unchanged. When you look at the third row,
the third row into first column will give you 0, third row into second column because
of the choice of m 32, this become zero, and a 331 gets modified a 332.
As before, let us look at matrix E 2 and define m 22 be vector 00 m 32; m 2 e 2 transpose,
that is going to be a matrix which has 0 everywhere except m 32 here. And hence, E 2 will be identity
matrix minus m 2 E 2 transpose. Consider i minus m 2 e 2 transpose into I plus m 2 e
2 transpose, this is going to be equal to identity, because e 2 transpose m 2 is going
to be 0, you will have identity; then, minus m 2 e 2 transpose and plus m 2 e 2 transpose,
so that gets cancelled. And then, minus m 2 e 2 transpose m 2 e 2 transpose, e 2 transpose
m 2 will be zero; so, you are left with identity. So, e 2 inverse is identity plus m 2, e 2
transpose.
So, thus our gauss elimination is equivalent to doing E 2 E 1 A and then you get matrix
A 2, which is equal to our upper triangular matrix U. We have seen that E 1 and E 2, these
are invertible matrices. So, we have got E 2 E 1 into A is equal to matrix U, which will
mean that, A is going to be equal to E 1 inverse E 2 inverse U; and this E one inverse E 2
inverse we will show that, that matrix is going to be a lower triangular matrix with
1 along the diagonal. So, that is going to give us LU decomposition
of our matrix A; it is a big technical, but the idea is simple. It is just that, whatever
operations we are doing in the case of gauss elimination method, they can be performed
3 by pre multiplying our matrix a by an appropriate matrix, which is say E 1, then E 2 and so
on.
So, let us look at E 1 inverse E 2 inverse, that is identity plus m 1 e 1 transpose and
identity plus m 2 e 2 transpose multiply. So, that will be identity plus m 1 e 1 transpose
plus m 2 e 2 transpose and e 1 transpose m 2; e 1 transpose is row vector 1 0 0, m 2
was 0 0 m 32; so, that is 0 and hence this term is not there. Now, identity matrix, that
means, you have got these ones and remaining entries 0.
m 1 e 1 transpose we had seen that, m 1 e 1 transpose is the matrix 0 everywhere, except
m 21 and m 31, and hence you have m 1 e 1 transpose will be contributing m 21 m 31.
m 2 e 2 transpose was matrix with 0 everywhere except entry m 32. And thus our E 1 inverse
E 2 inverse is going to be a lower triangular matrix with diagonal entries to be equal to
1. So, this was for 3 by 3 matrix. Now, I am going to quickly do for n by n matrix,
but not going into all the details, the idea is similar.
So, look at n by n matrix and look at the first step. So, in the first step, you are
multiplying the first row by m i1 and subtracting it from Ri, where m i 1 is a i 1 divided by
a 11. This is our matrix A; we want to introduce zeros here. So, you consider a 21 by a 11
multiply the first row and subtract from the second row.
So, as we had seen before, this first type of gauss elimination method can be performed
by pre multiplying our matrix A by this matrix; call this matrix to be E 1. So, we have E
1 1 is equal to A 1, that is the first type of gauss elimination method.
This matrix E 1 as before define vector m 1 to be 0, m 21, m n 1. So, we had done it
for the 3 by 3 matrix. So, in that case, our matrix our vector m 1 was 0, m 21, m 31. So,
now, the only difference is instead of a 3 by 1 vector, you have got n by 1 vector. So,
0, m 21, m 31, m n1, then our matrix E 1 is nothing but identity minus m 1 e 1 transpose,
exactly same as before.
Only difference is, instead of 3 by 1 vector, you have got n by 1 vector. So, this matrix
E 1, which is identity minus m 1 E 1 transpose; it is going to be an invertible matrix and
its inverse will be given by identity plus m 1 e 1 transpose, same proof as before. So,
E 1 is identity minus m 1 e 1 transpose, and e 1 inverse is going to be equal to identity
plus m 1 e 1 transpose.
Next, in the second step of gauss elimination method, you have a ij 2 to be equal to a ij
1 minus m i2 A 2 j 1 ij varying from 3 up to n. So, here, now you define your vector
m 2, which has the multipliers. So, the multipliers are m 32, m 42, m n2, and then E 2 is going
to be your matrix, which has 1 along the diagonal minus m 32 minus m n2o.
If you look at E 2 multiplied by A 1, that is going to give you a 2. So, you has started
with A, you pre multiplied by E 1 and you got a modified matrix a superscript 1. Now,
you multiply by E 2 and then you get a 2; this E 2 is also invertible matrix. E 2 is
identity minus m 2 e 2 transpose its inverse is identity plus m 2 e 2 transpose.
And in general, your E k is going to be identity minus m k e k transpose; E k inverse will
be identity plus m k e k transpose. And then, when you look at E n minus 1 into E n minus
2 up to E 1 multiplied by A, then you are going to get your upper triangular matrix
U, exactly the same matrix which we had obtained in the gauss elimination method.
In the gauss elimination method, our system A x is equal to b, we had converted into an
upper triangular system, u x is equal to y. And if it is a upper triangular system, then
we can do back substitution. So, we first determine x n, then x n minus 1 and so on.
So, this U 1 can obtain by pre multiplying A by invertible matrices E n minus 1 E n minus
2 up to E 1; then, that gives you A to be equal to E 1 inverse E 2 inverse up to E n
minus 1 inverse. Now, if you remember in yesterdays lecture,
we had send that, our aim is to reduce the system Ax is equal to b to a system, Ux is
equal to y, and that should be a equivalent system; that means, the original system and
a new system, they should have the same solution. So, now, here is a proof of this, that when
you do gauss elimination method, then the new system is equivalent to the earlier system.
So, we have got matrix A, you pre multiply by matrix E . So, E is going to be matrix
obtain by multiplying E n minus 1, E n minus 2 up to E 1. Each of E j is invertible matrix;
so, E is going to be an invertible matrix.
So, we have a x is equal to b which is same as E A x is equal to E b, where E is invertible
and then E into A will be our U; so, you get U x is equal to y. So, if x is a solution
of a x is equal to b, it is going to be solution of U x is equal to y; and the converse is
also true, if x is a solution of U x is equal to y, then it will be a solution of A x is
equal to b. Now, look at E 1 E inverse, it will be E 1
inverse, E 2 inverse, E n minus 1 inverse, E 1 inverse is identity plus m 1 e 1 transpose,
e 2 inverse is identity plus m 2 e 1 transpose and e n minus 1 inverse is this. You multiply
and when you simplify, what you are going to get is, e inverse to be this lower triangular
matrix with 1 along the diagonal, and the entries here to be the multiplier; we have
E into A is equal to U. So, A is equal to E inverse U, and now E inverse is equal to
l. So, you get A is equal to l into U.
Now, you have to note that the gauss elimination method, it can be performed provided at no
stage our pivot becoming zero, and that means, we have proved that at, a can be equal to
l into U, i f at no stage the pivot becomes 0. So, let me look at the system A x is equal
to b, this A we have written as L into U. So, you have got L into U x is equal to b.
Now, this I will split into two systems, U x is equal to y and L y is equal to b. So,
what is given is, b is given vector. So, look at L y is equal to b, L is matrix lower triangular
1 1 1 1, then you had here m 21, m n1 and so on. These are all entries to be 0, y 1,
y 2, up to y n is equal to b 1, b 2, up to b n.
So, when we look at the first equation, it is y 1 e is equal to b 1, vector b is given
to us; so, you determine y 1. In the next equation, you will have y 1 and y 2; y 1 is
already determined; so, you determine y 2. So, this is going to be forward substitution.
So, you determine y 1, y 2 and y n. once you have done that, then you look at u x is equal
to y. Now, in U x is equal to y, the right hand
side we have determined and there you are going to do back substitution. So, we have
either you consider gauss elimination method or you look at a is equal to L into U, and
solve two systems of equations. Once forward substitution, once backward substitution and
both of these, they will need the number of computations to be of the order of n square,
whereas finding L and U that will be of the order of n cube by 3.
So, what we have done is, we have proved that the gauss elimination method is equivalent
to or one can reshow, that if you have perform gauss elimination method. So, you have obtained
U, you have got multipliers, construct matrix L, and then you have got a is equal to L into
U. So, now, may be what one can do is, try to write this a is equal to L into U directly.
So, before we do that, trying to write directly; let us show that, such a decomposition is
unique. If you say that a should be equal to L into U, where L is lower triangular,
U is upper triangular; such a decomposition is not unique. But if you say that L should
be unit lower triangular, that means, all the diagonal entries should be equal to 1,
that is what makes the decomposition to be unique.
Now, the proof of uniqueness is straight forward; there what we are going to use is, if you
have got two upper triangular matrices and if you take their product, that is going to
be again an upper triangular matrix. Similarly, if you have got two lower triangular matrices,
if you take their product, then it is going to be again a lower triangular. And if this
two matrices are unit lower triangular, their product is also unit lower triangular.
This we will do as a tutorial problem, the verification, that product of upper triangular
matrices is upper triangular. We also have a result that, if your matrix is lower triangular
and it is invertible, then its inverse is also lower triangular. So, using these two
results, we are going to show that LU decomposition of a matrix A is unique, where L is unit lower
triangular and U is going to be upper triangular. Our assumption is determinant of A k not equal
to 0, where A k is principle leading sub matrix of order k, which is formed by first k rows
and first k columns of our matrix A. So, under these assumptions, our matrix A is going to
be invertible matrix. Now, determinant of a will be determinant of L into determinant
of U. We have proved existence of LU decomposition;
start with a matrix A with the property that determinant of A k is not equal to 0 perform
gauss elimination method, the final matrix upper triangular matrix, that is U, construct
L using multipliers and that gives you L. So, we definitely know, that a matrix A can
be written as L into U. Now, we want to show that such a decomposition is unique; determinant
of upper triangular matrix or a lower triangular matrix is product of the diagonal entry.
Now, L has all the diagonal entries to be 1. So, determinant of L is going to be 1,
determinant of U, that is same as determinant of a, because what we have done is, we have
used elementary row transformations; and a elementary row transformation of only 1 type,
which is multiplying a row by a non-zero constraint and subtracting from other row. So, such an
operation does not change value of the determinant. So, determinant of A is going to be determinant
of U. So, determinant of U will be not equal to 0, because determinant of q is not equal
to 0. So, our u is going to be a invertible matrix.
And also l will be invertible matrix. So, let us start with two decompositions, A is
equal to L 1 U 1 and also L 2 U 2, and then show that, L 1 has to be equal to L 2, u 1
has to be equal to U 2.
So, a is L 1 U 1 plus is equal to L 2 U 2, that will mean that, L 2 inverse L 1 is equal
to U 1 inverse U 2; determinant of U 1 is determinant A which is not equal to 0; so,
U 1 is invertible. Determinant of l 2 is equal to 1; so, L 2 is invertible. So, it is L 2
inverse L 1 is equal to U 1 inverse U 2. U 1 is upper triangular and hence its inverse
will be upper triangular, product of two upper triangular matrices is upper triangular, L
1 is lower triangular, L 2 inverse is lower triangular. So, there product is also going
to be lower triangular. So, you have on one hand a lower triangular
matrix; on another hand, an upper triangular matrix. So, these two are equal, provided
both of them those are diagonal matrices. So, our L 2 inverse L 1 and U 1 inverse U
2, they are going to be both of them diagonal matrices. In addition, L to inverse L 1 is
going to be unit lower triangular. So, that means, all the diagonal entries, they are
equal to 1. So, your L 2 inverse L 1, then U 1 inverse U 2, both of them they will be
diagonal matrices with diagonal entries to be equal to 1; that means, identity matrix.
So, you get L 1, L 2 inverse L 1 is equal to identity, that gives you L 1 is equal to
L 2; U 1 inverse U 2 is equal to identity, that gives you U 1 is equal to U 2. So, that
is uniqueness of LU decomposition; and this uniqueness we are going to need, when we want
to show that a positive definite matrix can be written as G, G transpose, that is the
Cholesky decomposition. So, now, let us see, take, we know that A can be written as L into
U and such a decomposition is unique. So, let me see, whether I can try to determine
the elements of L and U directly; that means, not going through the gauss elimination method
and then multipliers, and then constructing L and all; what I can try to do is, write
A as L into U, where L is unit lower triangular matrix, U is upper triangular matrix, and
try to determine the entries of matrix L and matrix U. So, matrix A is given to me; the
entries of L and U, these are not known. So, you will multiply identify the corresponding
entries and then try to determine. So, again I am going to quickly do this.
So, we are writing A as a unit lower triangular matrix. So, you have got one along the diagonal
and then l 21, l 31, l n1, that will be the first column and so on. All the entries above
the diagonal, they are going to be 0. U will be upper triangular matrix; so, you have,
u 11, u 12, u 13, u 1n, first row; then in the second row, you will have 0 here, u 22
u 23, u 2n and so on. Some of the entries above the diagonal in
U also can be 0, but what we know is definitely below the diagonal, they are all 0. Now, you
look at first row into first column. So, that is going to be u 11. So, that u 1 1 will be
equal to a 11; like that, then, first row into second column, first row into third column
and so on, that will give you a 1j to be equal to U 1j; that means, you have determined the
first row of u; our L the first row is only has only 1 and remaining entries 0.
So, when I consider first row of L multiplied by various columns of U, what comes into picture
are only the entries of the first row of U, and then you get a 1j is equal to u 1j. So,
you have determined first row of U. Now, you consider the l 21 u 11, that is going to be
equal to a 21; then, third row first column, fourth row first column, and so on. When you
do that, you are going to have l i1, u 11 is equal to a i1; and l i1 is equal to a i1
divided by u 11. So, that means, you have determined first
column of L. So, we write A as L into U, L unit lower triangular, U upper triangular;
and then, the first row of U is determined, first column of L is determined. Now, we will
determine the second row of U, second column of L, third row of U, third column of L and
so on. In this order, we can determine all the entries
of L into U. Now, what you have to notice is that, when you do this thing, all the diagonal
entries of U, they have to be not equal to 0, because in the first one, we notice that
we are dividing by u 11; the matrix A is given to us and we are trying to determine the entries
of L and U. Now, in the second step, the first column
of L is known, first row of U is known. So, you consider second row of l and jth column
of U, that is going to give us a 2 j. So, this a 2j is going to be equal to l 21 u 1j
plus u2j, j going from 2 up to n; a 2 j's are given to us. l 21 we have already determined
u 1j, elements of the first row are determined; so, that will determine the second row of
U. Then, ith row of L into second column of U, that will determine the second column of
L. In the second row of L, these being all zeroes, we have already determined second
column and second row of L. So, you have so far determined, first row
of U first column of U, second row of U second column of U, and similarly for the matrix
L. So, one continues this and one determines L and U; you can do the number computation
of number of operations. We have already computed the operations in the gauss elimination method,
and we saw that they were of the order of n cube by 3.
Now, we are doing it differently, but you will see, that here also the total number
of operations, they are going to be n cube by 3. So, we do not gain as such in the number
of operation, whether you do gauss elimination method or whether you determine L and U directly,
you are going to be the number of operations they are going to be the same, but as I said,
this writing a as L into U, that is useful in doing the backward error analysis for gauss
elimination method; and for considering the Cholesky decomposition of the matrix A; we
have got LU decomposition. Now, we have got another decomposition, which
is known as LDV decomposition. So, what are these, L is unit lower triangular, V is unit
upper triangular and D is going to be diagonal matrix.
A is equal to L into U with all u i's to be not zero, then you define consider D to be
diagonal u 11, u 11, u n n, and then V is equal to D 1 inverse U; so, this is my definition.
When you try to look at the entries of V, so v i i will be given by D inverse, its i
kth entry into u k I, k going from 1 to n the matrix multiplication; D being a diagonal
matrix. The only term which remains is this summation will be, D inverse i i and u i comma
i will be nothing but u i i. So, you get v i i to be equal to 1. So, that
means, if you define V to be equal to D inverse U, where D is diagonal entries diagonal matrix
consisting of diagonal entries of U, then our matrix v it becomes an upper triangular
matrix with diagonal entries to be equal to 1. So, we have A is equal to L into U, V is
equal to D inverse U; that means, U is going to be equal to D into V.
So, we have A is equal to LDV. So, staring with LU decomposition, we have proved existence
of LDV decomposition, where L is unit lower triangular, V is unit upper triangular and
D is diagonal matrix. Now, soon it will become clear to you, why we are going to this, that
we had LU decomposition, that might not satisfied with it, but go now to this LU decomposition
LDV. So, let us show that this LDV decomposition
is also going to be unique; we have proved the existence and uniqueness of LU decomposition.
From the LU decomposition, we deduced LDV decomposition, but there can be some other
way of finding LDV; so, we want to show the existence.
So, we have A is equal to l 1 d 1 v 1 is equal toL 2 D 2 V 2, where L 1, L 2, these are unit
lower triangular; D 1, D 2 are diagonal matrices and V 1, V 2 are upper triangular, and unit
the diagonal entries to be equal to L. So, now let me look at this way. So, by uniqueness
of LU decomposition, what we get is, L 1 is equal to L 2 and D L V1 is equal to D 2 V
2; this will imply that D 2 inverse D 1 is equal to V 1 inverse V 2. Now, each V 1 invertible?
yes, because V 1 is going to be unit upper triangular. So, determinant of V 1 is going
to be equal to 1. So, we have got D 2 inverse D 1; that means,
a diagonal matrix. V 1 inverse V 2; that means, it is going to be a unit upper triangular
matrix. So, both of them they have to be diagonal matrices; and since the diagonal entries of
V 1 inverse V 2, they are going to be all equal to 1; all both of these, they have to
be equal to identity matrix. So, that gives you D 1 is equal to D 2 and
V 1 is equal to V 2. Today's lecture we have shown that, the gauss elimination method can
be written can be expressed as, a LU decomposition of the matrix; then, we proved uniqueness
of LU decomposition, and then we also saw how to determine L and U by starting with
the formula A is equal to L into U, and then taking the matrix multiplication and identifying
various entries. Then, we have talked about LDV decomposition,
we proved is uniqueness. So, in tomorrow's lecture, we will use this for showing that
a positive definite matrix has got a Cholesky decomposition. So, thank you.