Linear Algebra: QR Factorization

in this video we're going to go through the process of QR factorization and that's the process by which we take a matrix and turn it into I product of two matrices matrices which we eat a commonly title Q and R so we take a we take em and we want to turn it into two matrices these q and r the q over there is going to be the columns are going to be the orthonormal basis of the column vectors in our original m and the r is going to be an upper triangular matrix so I'm going to write out what that looks like like this here's M because it's matrix M going to call the column vectors little M 1 little M 2 up to MN ok it's going to equal here's our orthonormal basis of vectors so u 1 u 2 all the way up to u n for however many columns that we want check the previous video for the gram-schmidt process on how exactly it is that we calculate this from these but we're going to do it in this video anyway so you get to see it again and finally RR is some kind of upper triangular matrix that looks like that so all zeros down here and then on the diagonal and above various numbers and things that's our that's q m and that's our reference that we'll look at why is this important this has a bunch of applications with regression when you have various points you want to find a best fit line but none of them really lined up this is kind of a way that you fits find a model that'll like fit to your data so there are lots of important reasons to do this but we were primarily turned right now with how to do it so we're going to use this example here where my M is 2 2 1 1 1 5 and these are going to be my M 1 and M 2 so we need to start by finding our Q and the Q is just the gram-schmidt process so we get to go through that again here's U 1 and that's going to equal 1 over the length of M 1 times M 1 itself alright and so I'll do that right now a 1 over what's the length of this that's the square root of 2 squared plus 2 squared plus 1 that's 4 plus 4 plus 1 that's 9 and the square root of 9 is just 3 so 2/3 2/3 1 it's not unlike the example we did in our gram-schmidt video alright now you two luckily there are only two column vectors in this particular matrix so we don't get too complicated with u3 and u4 we just have u 2 which is M 2 minus u 1 dot M 2 times u 1 right okay and then after that's done we're going to have to divide by its length again so M 2 - okay u 1 M 2 that's going to be okay 1 times 2/3 so 2/3 plus 1 times 2 thirds plus 5 times 1/3 that's five thirds parentheses times u 2 and that equals a two plus two plus five that's nine nine thirds is three so that's one one five minus three times this this is going to be three so three times that that will just knock out the thirds on each one so it's really 1 minus 2 is minus 1 1 minus 2x minus 1 and 5 minus 1 is 4 great that is my YouTube that is my u1 sorry that is not my youtube I forgot the last step which is divided by its length so my real u2 is going to be okay 4 squared is 16 plus 1 plus 1 that's 18 so not the friendliest of numbers but the square root of 18 times minus 1 minus 1/4 and unfortunately when you're doing gram-schmidt or QR factorization you do get a lot of square roots because we're dealing with unit vectors so that is my U - that is my u1 I can now write my cue okay right now you're probably wondering how do I get my our and there are actually two ways that you can get this one of them is the smart way I like to call it but it requires you to like really look into these things and think about it deeply and if we do it the smart way we realize that we've actually kind of already calculated our and I'll explain what that means and then there's the more of a brute force method which is we've already found our cue we've already found our M so to find our R that's the same as if we solve for R in that equation by multiplying both sides by Q transpose and our Q transpose Q because that is an orthonormal matrix that'll give us just the unit vector on the identity matrix I so R will equal Q transpose M so we can multiply these matrices out and I'll do that last to just prove that that is correct but here's what I mean when we kind of already calculate R okay first of all M is a three by two matrix Q is a three by two matrix so we know that R has to be a two by two matrix in order for us to get M so we had Q which was u1 u2 times ten some some two by two matrix R say r1 r2 r3 and r4 equals our m1 and m2 okay and let's think about what it actually we're doing what we're doin we multiply a row by column so there are three entries here there are actually three rows but that's you really need to know that we multiply this first row by this first column to get this number we multiply the second row by this first column to get that number and we were all two by this third row by this first column to get this number now if we look up here at what we did right there we found that u1 equals 1 over length of m1 which turned out to be 3 times m1 so from that we know that M 1 this is 3 so m1 equals 3 u 1 so what does that tell us for our matrix R that actually tells us about the first row we've got a 3 here and a 0 right here it takes a little bit of thinking and understanding to understand that but write this row here which is three numbers one two three results from three multiplied by each of the entries in this row so if we're cross multiplying each of these entries into this row there's got to be a three right here in order for that to result and there needs to be a zero here because this number is in the second row are being multiplied by anything similarly for you to let me just rewrite everything that we did we found out that you to my last step was dividing everything by the square root of 18 and here I have m2 minus this number which we discovered was three right okay so let's solve for what our m2 is if I multiply both sides by the square root of 18 so M 2 is equal to 3 u 1 plus the square root of 18 you two okay so that means m2 right here is equal to when we multiply it it's this all of these rows multiplied by this column right here so all the you ones get multiplied by three so there's got to be a three right there and all of the you twos get multiplied by the square root of 18 so there needs to be a square root of 18 right there so and that is our result our and as you can see we had really calculated it in doing this gram-schmidt process that can be a little bit difficult to see which is why I'm showing you this other method which is easier on the brain but more work okay that that is our answer but we're going to just do this out Q transpose m and I'll try to do this as fast as possible because no one likes matrix multiplication if you have Q transpose that's just shifting everything so it's sideways so the rows becomes the columns columns become the rows that multiply by my original M 2 2 1 1 1 5 equals okay row column let's go 2/3 times 2 4 thirds 2/3 times 2 2 4 thirds 1/3 times 1 1/3 so 4 thirds plus 4 thirds plus 1/3 hey that's nine thirds that's three cool running out of room ok this times that we get this entry 2/3 times one two thirds 2/3 times one two thirds 2/3 times one third times five five thirds these are bumping into each other I hate when I do that but two thirds plus 2/3 times 5/3 that's 9/3 hey that's three we got that right all right this row times that that's negative 218 over square root of 18 minus 2 over square root of 18 plus 4 over square root of 18 hey look that equals to 0 so that's right in our last one that's minus 1 over square root of 18 minus 1 over the square root of 18 plus 4 times 5 thats 20 over the square root of 18 and the result of that is 18 over the square root of 18 which is the same thing as the square root of 18 so as you can see we got the same answer both ways this is this is met that's much easier to remember and if you aren't really in the mood to think about it / less likely to make mistakes especially for doing this on a calculator I would go with that method but it's important to the other spin the other one as well so this has been QR factorization how to divide this matrix into these two matrices here which have various applications in things and we just like to know how to do that so that's all for today thanks for watching thanks for watching this video be sure to check out the rest of the videos in this series and any of the other math related videos on our channel if you're not subscribed to our Channel click this link right here for more help with linear algebra check out worldwide differential equations with linear algebra by Robert McGowan or elementary linear algebra by Bruce gooberstein both are available at an affordable price in digital formats on our website just click this link right here you

Channel: Center of Math

Views: 83,743

Rating: 4.8547854 out of 5

Keywords: math, center of math, mathematics, Linear Algebra (Field Of Study), QR Decomposition, Factorization (Literature Subject), help, free, tutor, step by step, lecture, Mathematics (Field Of Study)

Id: 6DybLNNkWyE

Length: 15min 21sec (921 seconds)

Published: Fri Jun 27 2014