Placeholder Image

Subtitles section Play video

  • Okay. This is it.

  • The second lecture in linear algebra, and I've put below my

  • main topics for today. I put right there a system of

  • equations that's going to be our example to work with.

  • But what are we going to do with it?

  • We're going to solve it. And the method of solution will

  • not be determinants. Determinants are something that

  • will come later. The method we'll use is called

  • elimination. And it's the way every software

  • package solves equations. And elimination,

  • well, if it succeeds, it gets the answer.

  • And normally it does succeed. If the matrix A that's coming

  • into that system is a good matrix, and I think this one is,

  • then elimination will work. We'll get the answer in an

  • efficient way. But why don't we,

  • as long as we're sort of seeing how elimination works -- it's

  • always good to ask how could it fail?

  • So at the same time, we'll see how elimination

  • decides whether the matrix is a good one or has problems.

  • Then to complete the answer, there's an obvious step of back

  • substitution. In fact, the idea of

  • elimination is -- you would have thought of it,

  • right? I mean Gauss thought of it

  • before we did, but only because he was born

  • earlier. It's a natural idea...

  • and died earlier, too.

  • Okay, and you've seen the idea. But now, the part that I want

  • to show you is elimination expressed in matrix language,

  • because the whole course -- all the key ideas get expressed

  • as matrix operations, not as words.

  • And one of the operations, of course, that we'll meet is

  • how do we multiply matrices and why?

  • Okay, so there's a system of equations.

  • Three equations and three unknowns.

  • And there's the matrix, the three by three matrix -- so

  • this is the system Ax = b. This is our system to solve,

  • Ax equal -- and the right-hand side is that vector 2,

  • 12, 2. Okay.

  • Now, when I describe elimination -- it gets to be a

  • pain to keep writing the equal signs and the pluses and so on.

  • It's that matrix that totally matters.

  • Everything is in that matrix. But behind it is those

  • equations. So what does elimination do?

  • What's the first step of elimination?

  • We accept the first equation, it's okay.

  • I'm going to multiply that equation by the right number,

  • the right multiplier and I'm going to subtract it from the

  • second equation. With what purpose?

  • So that will decide what the multiplier should be.

  • Our purpose is to knock out the x part of equation two.

  • So our purpose is to eliminate x.

  • So what do I multiply -- and again, I'll do it with this

  • matrix, because I can do it short.

  • What's the multiplier here? What do I multiply -- equation

  • one and subtract. Notice I'm saying that word

  • subtract. I'd like to stick to that

  • convention. I'll do a subtraction.

  • First of all this is the key number that I'm starting with.

  • And that's called the pivot. I'll put a box around it and

  • write its name down. That's the first pivot.

  • The first pivot. Okay.

  • So I'm going to use -- that's sort of like the key number in

  • that equation. And now what's the multiplier?

  • So I'm going to -- my first row won't change,

  • that's the pivot row. But I'm going to use it -- and

  • now, finally, let me ask you what the

  • multiplier is. Yes?

  • 3. 3 times that first equation

  • will knock out that 3. Okay.

  • So what will it leave? So the multiplier is 3.

  • 3 times that will make that 0. That was our purpose.

  • 3 2s away from the 8 will leave a 2 and three 1s away from 1

  • will leave a minus 2. And this guy didn't change.

  • Okay. Now the next step -- this is

  • forward elimination and that step's completed.

  • Oh, well, you could say wait a minute, what about the right

  • hand side? Shall I carry -- the right-hand

  • side gets carried along. Actually MatLab finishes up

  • with the left side before -- and then just goes back to do the

  • right side. Maybe I'll be MatLab for a

  • moment and do that. Okay.

  • I'm leaving a room for a column of b, the right-hand side.

  • But I'll fill it in later. Okay.

  • Now the next step of elimination is what?

  • Well, strictly speaking... this position that I cleaned up

  • was like the 2, 1 position, row 2,

  • column 1. So I got a 0 in the 2,

  • 1 position. I'll use 2,1 as the index of

  • that step. The next step should be to

  • finish the column and get a 0 in that position.

  • So the next step is really the 3,1 step, row three,

  • column one. But of course,

  • I already have 0. Okay.

  • So the multiplier is 0. I take 0 of this equation away

  • from this one and I'm all set. So I won't repeat that,

  • but there was a step there which, MatLab would have to look

  • -- it would look at this number and, do that step,

  • unless you told it in advance that it was 0.

  • Okay. Now what?

  • Now we can see the second pivot, which is what?

  • The second pivot -- see, we've eliminated -- x is now

  • gone from this equation, right?

  • We're down to two equations in y and z.

  • And so now I just do it again. Like, everything's very recursive

  • at this -- this is like -- such a basic algorithm and

  • you've seen it, but carry me through one last

  • step. So this is still the first

  • pivot. Now the second pivot is this

  • guy, who has appeared there. And what's the multiplier,

  • the appropriate multiplier now? And what's my purpose?

  • Is it to wipe out the 3, 2 position, right?

  • This was the 2, 1 step.

  • And now I'm going to take the 3, 2 step.

  • So this all stays the same, 1 2 1, 0 2 -1 and the pivots

  • are there. Now I'm using this pivot,

  • so what's the multiplier? 2.

  • 2 times this equation, this row, gets subtracted from

  • this row and makes that a 0. So it's 0, 0 and is it a 5?

  • Yeah, I guess it's a 5, is that right?

  • Because I have a one there and I'm subtracting twice of twice

  • this, so I think it's a 5 there. There's the third pivot.

  • So let me put a box around all three pivots.

  • Is there a -- oh, did I just invent a negative

  • one? I'm sorry that the tape can't,

  • correct that as easily as I can.

  • Okay. Thank you very much.

  • You get an A in the course now. Is that correct?

  • Is it correct now? Okay.

  • So the three pivots are there -- I know right away a lot about

  • this matrix. This elimination step from A --

  • this matrix I'm going to call U. U for upper triangular.

  • So the whole purpose of elimination was to get from A to

  • U. And, literally,

  • that's the most common calculation in scientific

  • computing. And people think of how could I

  • do that faster? Because it's a major,

  • major thing. But we're doing it the

  • straightforward way. We found three pivots,

  • and by the way, I didn't say this,

  • pivots can't be 0. I don't accept 0 as a pivot.

  • And I didn't get 0. So this matrix is great.

  • It gave me three pivots, I didn't have to do anything

  • special, I just followed the rules and, and the pivots are 1,

  • 2 and 5. By the way, just because I

  • always anticipate stuff from a later day, if I wanted to know

  • the determinant of this matrix --

  • which I never do want to know, but I would just multiply the

  • pivots. The determinant is 10.

  • So even things like the determinant are here.

  • Okay. Now -- oh, let me talk about

  • failure for a moment, and then --

  • and then come back to success. How could this have failed?

  • How could -- by fail, I mean to come up with three

  • pivots. I mean, there are a couple of

  • points. I would have already been in

  • trouble if this very first number here was 0.

  • If it was a 0 there -- suppose that had been a 0,

  • there were no Xs in that equation -- first equation.

  • Does that mean I can't solve the problem?

  • Does that mean I quit? No.

  • What do I do? I switch rows.

  • I exchange rows. So in case of a 0,

  • I will not say 0 pivot. I will never be heard to utter

  • those words, 0 pivot. But if there's a 0 in the pivot

  • position, maybe I can say that, I would try to exchange for a

  • lower equation and get a proper pivot up there.

  • Okay. Now, for example,

  • this second pivot came out two. Could it have come out 0?

  • What -- actually, if I change that 8 a little

  • bit, I would have got a little trouble.

  • What should I change that 8 to so that I run into trouble?

  • A 6. If that had been a 6,

  • then this would have been 0 and I couldn't have used that as the

  • pivot. But I could have exchanged

  • again. In this case.

  • In this case, because when can I get out of

  • trouble? I can get out of trouble if

  • there's a non-0 below this troublesome 0.

  • And there is here. So I would be okay in this

  • case. If this was a 6,

  • I would survive by a row exchange.

  • Now -- of course, it might have happened that I

  • couldn't do the row, that -- that there was 0s below

  • it, but here there wasn't. Now, I could also have got in

  • trouble if this number 1 was a little different.

  • See, that 1 became a 5, I guess, by the end.

  • So can you see what number there would have got me trouble

  • that I really couldn't get out of?

  • Trouble that I couldn't get out of would mean if 0 is in the

  • pivot position and I've got no place to exchange.

  • So there must be some number which if I had had here it would

  • have meant failure. Negative 4, good.

  • If it was a negative 4 here -- if it happened to be a negative

  • 4, I'll temporarily put it up here.

  • If this had been a negative 4 z, then I would have gone

  • through the same steps. This would have been a minus 4,

  • it still would have been a minus 4.

  • But at the last minute it would have become 0.

  • And there wouldn't have been a third pivot.

  • The matrix would have not been invertible.

  • Well, of course, the inverse of a matrix is

  • coming next week, but, you've heard these words

  • before. So, that's how we identify

  • failure. There's temporary failure when

  • we can do a row exchange -- and get out of it,

  • or there's complete failure when we get a 0 and -- and

  • there's nothing below that we can use.

  • Okay. Let's stay with -- back to

  • success now. In fact, I guess the next topic

  • is back substitution. So what's back substitution?

  • Well, now I'd better bring the right-hand side in.

  • So what would MatLab do and what should we do?

  • Let me bring in the right-hand side as an extra column.

  • So there comes B. So it's 2, 12,

  • 2. I would call this the augmented

  • matrix. "Augment" means you've tacked

  • something on. I've tacked on this extra

  • column. Because, when I'm working with

  • equations, I do the same thing to both sides.

  • So, at this step, I subtracted 2 of the first

  • equation away from the second equation so that this augmented

  • -- I even brought some colored chalk, but I don't know if it

  • shows up. So this is like the augmented

  • -- no! Damn, circled the wrong thing.

  • Okay. Here is b.

  • Okay, that's the extra column. Okay.

  • So what happened to that extra column, the right-hand side of

  • the equations, when I did the first step?

  • So that was 3 of this away from this, so it took -- the 2 stayed

  • the same, but three 2s got taken away from 12,

  • leaving 6, and that 2 stayed the same.

  • So this is how it's looking halfway along.

  • And let me just carry to the end.

  • The 2 and the 6 stay the same, but -- what do I have here?

  • Oh, gosh. Help me out,

  • now. What -- so now I'm --

  • This is still like forward elimination.

  • I got to this point, which I think is right,

  • and now what did I do at this step?

  • I multiplied that pivot by 2 or that whole equation by 2 and

  • subtracted from that, so I think I take two 6s,

  • which is 12, away from the 2.

  • Do you think minus 10 is my final right-hand side -- the

  • right-hand side that goes with U, and let me call that once and

  • forever the vector c. So c is what happens to b,

  • and U is what happens to A. Okay.

  • There you've seen elimination clean.

  • Okay. Oh, what's back substitution?

  • So what are my final equations, then?

  • Can I copy these equations? x+2y+z=2 is still there and

  • 2y-2z=6 is there, and 5z=-10.

  • Okay. Those are the equations that

  • these numbers are telling me about.