Dr. Robert van de Geijn: When we looked at Gaussian elimination,
we started by manipulating a system of linear equations,
and then we introduced the notion of an appended system,
and then we introduced Gauss transforms.
What we're going to do in this video is simultaneously
work with an appended system, so that we only
have to manipulate the coefficients.
And we're going to show how a slight extension of the notion of a Gauss
transform allows us to elegantly capture what we just
discussed in the previous unit.
Here we have our prototypical system of linear equations.
We can represent this with an appended system, where again, as before,
all we did was we got rid of the variable names,
and then we put a line there, in this case a double line,
in order to separate the right-hand side from the rest of the equations.
And what we're going to do is we're just going
to manipulate this appended system from here on.
Just like before, what we can do is we can
think of introducing 0's below this diagonal entry,
as requiring a Gauss transform to be applied from the left.
And the entries in the Gauss transform are computed exactly as before.
You take the entry divided by the entry on the diagonal,
and you take the negative of that to get any particular entry in the Gauss
transform.
So here we have 2 divided by minus 2 is minus 1.
Negate that, you get 1.
So we get this right here.
And so far everything is very similar.
Now we introduce a slightly changed Gauss transform, because notice
that now, not only are there non-zeros below the diagonal element,
there are also non-zeros above it.
And the way you compute those is exactly as before.
You take this entry, divide it by that, that gives you 1.
And then you take the negative of that, you get that.
You want to put a 0 right there, you divide it
by the diagonal element, that gives you minus 2.
You negate that, you get 2.
Now if you think of this matrix as partitioned by rows, then
you notice that the new row, here at the top, is 1 times the first row
plus 2 times the second row plus 0 times the third row.
And what that does is it eliminates that entry right there.
And if you reason through that, what you get is this right here.
And notice that we introduced a 0 right there, and a 0 right there.
If we do that one more time, we want to introduce 0s here.
We compute the multipliers, and if you think
about what this Gauss transform does, it does
exactly the taking multiples of certain rows and adding them to other rows
that you need, in order to eliminate those terms.
And when you're done, you end up with this diagonal matrix to the left,
and some update to the right-hand side.
And then there's one more step.
If you now multiply by a diagonal matrix,
and recall that multiplying from the left by a diagonal matrix
meant that you were scaling the individual rows.
What this does, if you think of this as rows,
is the first row is multiplied by minus 1/2, that introduces a 1 right here.
The second row is multiplied by minus 1, that introduces a 1 right there.
And the third row is left alone in this case.
And what you get this right here.
And then you recognize that the right-hand side right here
is just a solution to the original system
of linear equations, with which we started.
So the general form here is that you have a matrix where up to some point
you've already introduced 0s in the off-diagonal elements.
What you would like to do is introduce 0s in the current column.
The way you do that is you compute entries in a Gauss
transform, such that the current row is left alone, and multiples of that row
are taken-- are subtracted or added onto the other rows,
in an effort to introduce the 0s in the places where we would like them to be.
This is a way of abstracting that.
This here is this diagonal matrix right here.
This here represents the multipliers that
have been negated right up here and down here.
If you multiply that times this matrix, then what you get is this right here.
And what you recognize is that if you pick your vectors u 0, 1 and l 2, 1
correctly, then you can introduce 0s here and here.
And what you end up with is a matrix like that.
And then you move on, as you've done many, many times,
in your various algorithms.
So in general, if you look carefully at what this here does,
it leaves the current row alone.
It updates all of the rows above it.
And notice that it updates it with a rank-1 update.
It updates all of the rows below with a rank-1 update.
And if we then choose these vectors correctly,
then we can selectively introduce 0s in our matrix.
Now, this then inspires an algorithm that
executes in more general terms what we illustrated
with our system of three equations and three unknowns.
And, let's see, how would we explain that.
Well, this is what we were after.
We had to compute these two vectors right here,
and if you looked very carefully previously, what you saw
was that you want to compute those as indicated there.
And then all you see down here are the updates
that are happening-- that are happening right there.
And then in the end you come back and overwrite these vectors with 0s,
because previously you temporarily stored
u and l, u 0, 1 and l 2, 1 in those vectors.
And then you have to go through and sweep
through the matrix in the right-hand side vector one more time,
because you want to divide the current row by the diagonal entry,
and that's happening right here.
In practice, all you need to do is divide the current entry on the right
by the current diagonal entry, and then set the current diagonal entry to 1,
because the other parts of the matrix had already been overwritten by 0s,
and therefore you don't need to compute with those.
So in summary what we've just illustrated
is an alternative way for solving Ax equals b,
through a process that's often referred to as Gauss-Jordan elimination.