Information about LU decomposition - An Example Calculation - Part 1

  • Title: LU decomposition - An Example Calculation

  • Series: LU decomposition - An Example Calculation

  • YouTube-Title: LU decomposition - An Example Calculation

  • Bright video: https://youtu.be/BFYFkn-eOQk

  • Dark video: https://youtu.be/8RFj6kXUie0

  • PDF: Download PDF version of the bright video

  • Dark-PDF: Download PDF version of the dark video

  • Print-PDF: Download printable PDF version

  • Thumbnail (bright): Download PNG

  • Thumbnail (dark): Download PNG

  • Subtitle on GitHub: lu-deco01_sub_eng.srt

  • Other languages: German version

  • Timestamps

    0:00 Introduction

    0:33 Start Example

    1:45 First step

    2:41 Eliminating the first column

    5:35 Eliminating the second column

    7:10 Eliminating the third column

    7:38 Result of the LU decomposition

  • Subtitle in English

    1 00:00:00,060 –> 00:00:06,990 Hello and welcome! First I want to thank all the  nice people that support this channel on Steady (tbsom.de/s/support)!  

    2 00:00:06,990 –> 00:00:15,090 Today I want to show you the LU decomposition  for a square matrix. This means that we rewrite

    3 00:00:15,090 –> 00:00:21,960 our matrix as a product of two matrices, where on  the one side we have a lower triangular matrix L  

    4 00:00:21,960 –> 00:00:29,610 and on the other side we have an upper triangular  matrix U. Now in this video I want to show you the  

    5 00:00:29,610 –> 00:00:38,100 algorithm with the help of one example. I choose  a 4x4-matrix and I call it A. Here you  

    6 00:00:38,100 –> 00:00:44,340 see this looks like a nice example. However it’s  not a trivial one. Now I can immediately tell you  

    7 00:00:44,340 –> 00:00:51,780 that doing the LU decomposition is basically just  an expanded Gaussian elimination. Therefore please  

    8 00:00:51,780 –> 00:00:57,930 remember you can do the Gaussian elimination  by just using row operations. And what you get  

    9 00:00:57,930 –> 00:01:06,030 out is an upper triangular matrix in the end and  this is exactly the U in our LU decomposition.

    10 00:01:06,030 –> 00:01:12,840 At this point I can give you a warning: we will not  use row exchanges in this example here. Indeed  

    11 00:01:12,840 –> 00:01:19,200 it’s essential for the LU decomposition that  you don’t use row exchanges while applying the  

    12 00:01:19,200 –> 00:01:25,920 algorithm. This means that if you have a matrix  where you really need row exchanges in the  

    13 00:01:25,920 –> 00:01:32,730 Gaussian elimination, then you should apply these  all beforehand and then just use the algorithm

    14 00:01:32,730 –> 00:01:40,470 I now show you. Okay, then I would say we start with  our nice example here. The first step is always  

    15 00:01:40,470 –> 00:01:50,130 to include an identity matrix with the right size. Here it would be 4x4-matrix, so I use 1, 1,

    16 00:01:50,130 –> 00:01:59,040 1, 1 on the diagonal and the rest are zeros. And  on the right hand side I just copy my matrix from  

    17 00:01:59,040 –> 00:02:05,310 before. Obviously, the equality still holds because  we just multiply with the identity matrix.

    18 00:02:05,310 –> 00:02:13,740 And now we see: we almost have our LU decomposition here. We will transform the identity matrix into a  

    19 00:02:13,740 –> 00:02:21,330 lower triangular matrix, so we will fill in numbers  here but not here, and we will transform this one  

    20 00:02:21,330 –> 00:02:28,320 to an upper triangular matrix. This means that we now just use the normal Gaussian elimination on  

    21 00:02:28,320 –> 00:02:36,240 the right, but now we also memorize all the steps  with the help of the matrix on the left.

    22 00:02:36,240 –> 00:02:42,570 Okay, you will see a immediately how this works with the first step. Okay so I copied the first row because we  

    23 00:02:42,570 –> 00:02:48,840 won’t change it but we will change all the other  rows. Now in the first Gaussian elimination step we  

    24 00:02:48,840 –> 00:02:57,420 use this number as a pivot and we want to generate zeros below it. Therefore to get a 0 here in the  

    25 00:02:57,420 –> 00:03:04,200 second row we have to use two times the first row. Hence we can write this as: use the second  

    26 00:03:04,200 –> 00:03:15,030 row minus (-2) times the first row. Of course, we could rewrite this as plus 2 times the first  

    27 00:03:15,030 –> 00:03:22,020 row but for the LU decomposition is always helpful  to use a minus sign here. This means that we always  

    28 00:03:22,020 –> 00:03:30,270 subtract multiples of another row. This is very helpful because this number here we subtract is  

    29 00:03:30,270 –> 00:03:38,340 the number we will put in the matrix L. Where to put it is very easy because here we generated a 0.

    30 00:03:38,340 –> 00:03:46,020 And at the exact same position we put the  new number in the matrix L. And in the same way,

    31 00:03:46,020 –> 00:03:52,680 it works for all other positions here. Now with the matrix multiplication you see that this is  

    32 00:03:52,680 –> 00:03:59,640 indeed the correct sign we chose because if you  multiply 2 with (-2) here you get out  

    33 00:03:59,640 –> 00:04:06,840 indeed -4 as we want. However still we have to do our calculation here so we do our  

    34 00:04:06,840 –> 00:04:14,100 Gaussian elimination step which means we have the 0 here as wanted; here we have 1; here we have

    35 00:04:14,100 –> 00:04:21,720 also 1; and there we have 2. OK, now we can do  the same thing for the third row which means we  

    36 00:04:21,720 –> 00:04:27,960 take the third row and we have to subtract a  multiple of the first row, which is here just

    37 00:04:27,960 –> 00:04:35,910 3 times the first row. OK, now you know the  multiple we subtract, so 3 is the number we  

    38 00:04:35,910 –> 00:04:41,400 put at the right position here. And of course  we also have to do the calculation which is 0  

    39 00:04:41,400 –> 00:04:52,140 here, minus 4, minus 7, and minus 6 here. Again we can  check that our sign was correct: so if you multiply  

    40 00:04:52,140 –> 00:05:00,420 this column with this row, we get out 2 times 3,  so our 6. And finally we can do the whole thing  

    41 00:05:00,420 –> 00:05:07,170 for the last row. So I take the fourth row and I  look at the multiple of the row I have  

    42 00:05:07,170 –> 00:05:14,520 to subtract. And here it is 2 times the first row. And now you already know we have to put this  

    43 00:05:14,520 –> 00:05:22,080 2 into our matrix L. And also the calculation  in last row is not so hard: we have the 0 here,

    44 00:05:22,080 –> 00:05:31,350 here we have 8, so 1 remains, and here we have  minus 8, and there 4. Well now we are finished  

    45 00:05:31,350 –> 00:05:37,740 with our first column because everything is 0 here. Now we go to our next column, so the second  

    46 00:05:37,740 –> 00:05:43,800 column, which means this is our new pivot. So the procedure would be exactly the same, we now just  

    47 00:05:43,800 –> 00:05:50,970 produce the zeros here. OK, in order to do this, let’s start a new line. So let’s copy everything  

    48 00:05:50,970 –> 00:05:57,360 and then do the same Gaussian elimination as  before. We can copy the first two rows because  

    49 00:05:57,360 –> 00:06:04,470 we won’t change them anymore. The first step is  of course to generate a 0 here, which means that  

    50 00:06:04,470 –> 00:06:12,360 we take the third row and use the second row to  change it. Now you see we have to add 4 times the  

    51 00:06:12,360 –> 00:06:21,000 second row to get a 0 here; and therefore we write  it as subtracting minus 4 times the second row.

    52 00:06:21,000 –> 00:06:30,450 And now this multiple is the number we put here at the right position: minus 4. And our calculation  

    53 00:06:30,450 –> 00:06:40,050 in the third row gives us here 0, 0. Here we have 4 and minus 7 so minus 3, and here we have 2.

    54 00:06:40,050 –> 00:06:47,160 So let’s to the next step which means generate  a zero here. So take the fourth row and subtract  

    55 00:06:47,160 –> 00:06:55,980 the second row, so minus 1 times the second row. And again this one is the thing we put here in our  

    56 00:06:55,980 –> 00:07:03,750 matrix L. And the last calculation here is very  easy: we just have 0, 0, -9, and 2.

    57 00:07:03,750 –> 00:07:11,370 Okay very good, so now you see we just need one  last step in our Gaussian elimination. So let’s  

    58 00:07:11,370 –> 00:07:17,850 do that very quickly now. Well, I copied everything  again except the last row because this is the only  

    59 00:07:17,850 –> 00:07:23,490 one we change now. And you immediately see what  we need we just have to change the 4th row  

    60 00:07:23,490 –> 00:07:31,410 by subtracting 3 times the third row. And  as before the number we subtract is the number  

    61 00:07:31,410 –> 00:07:39,450 we put in here. Then we just have to zeros here and (-4) here. And there you have it that’s our  

    62 00:07:39,450 –> 00:07:47,070 LU decomposition. On the left we have our lower  triangular matrix, which we call L, and we want  

    63 00:07:47,070 –> 00:07:53,010 to choose it with only 1s on the diagonal. And  you see that is exactly what we get out with this  

    64 00:07:53,010 –> 00:08:00,090 algorithm. And on the right hand side you see this  is our upper triangular matrix U. There on the  

    65 00:08:00,090 –> 00:08:07,140 diagonal everything can happen. Now please recall that you get U by just using Gaussian elimination  

    66 00:08:07,140 –> 00:08:15,420 and L by saving all these steps in the Gaussian  elimination. Therefore the matrix multiplication  

    67 00:08:15,420 –> 00:08:23,520 here gives us, in fact, our original matrix back. However just in the case that we don’t need to  

    68 00:08:23,520 –> 00:08:30,990 use row exchanges in the Gaussian elimination. How to deal with this and how to generalize the whole  

    69 00:08:30,990 –> 00:08:37,890 concept here, I can show you in another video. For now, I hope this example really helped you such  

    70 00:08:37,890 –> 00:08:45,270 that you now can calculate an LU decomposition  of a matrix. And then: see you next time! Bye!

  • Quiz Content (n/a)
  • Back to overview page