Lecture 03 - Gaussian Elimination with Examples

IIT Kanpur July 201
20 followers
May 31, 2024
[Music]
[Music]
hello and welcome to another lecture on
linear programming remember we had
talked about what a linear program was
and we wanted to study linear algebra
what was a linear program we said a
linear program is something an
optimization problem where maximization
was a linear function and even the
constraints were all linear that means I
can have linear equations I can have
linear inequalities either greater than
equal to or less than equal to greater
than equal to zero and so on and so
forth again you have to believe me all
of the such constraints can be
changed into these two this is what we
call the standard
form
all linear programs can be thought of
optimization linear function such that I
have constraints ax equal to B is a
system of linear
equations they look like this with the
constraint that every variable is
positive this is what we wanted to solve
and we realized that first step in
solving all this in the linear program
is to actually
concentrate on Ax
B and ask can we solve a xal to B
remember here a is a
matrix X is a
vector of
variables b is
another
Vector if I expand it out it will look
like this bunch
of linear equation so when I say ax
equal to B when I say system of linear
equations all
this should should uh make this picture
in your
mind that means I
have M equations
here in N variables
my variables are X1 up to xn my
coefficients are a11 A1 to a1n so on and
so forth and b12 BM are constants on the
right hand side okay so to take an
example remember last time we wanted to
solve this bunch of
equations if I want to talk about it
here there are two
variables and three
equations the variables are X1 X2 and
constants are 1 3 1 1 7 and 4 in this
case B1 is 98 B2 is 40 B3 is
390 so this system of linear equations
we want to solve I
will write this as axal B how to solve
axal to
B
and when I say I want to solve a xal to
B this should be very happy moment for
us as a mathematician because this
is what I will
call the
problem of linear
algebra what I mean by that uh going
into a bit of philosophy if you look at
any branch of
mathematics most of them owe their
existence to a central problem there's a
single problem which we wanted to solve
and that gave rise to the entire
mathematical theory behind that
problem for linear algebra I would say
there are two problems one is axal to
B and
another is axal to Lambda X this takes
us to igon values and igon vectors I'm
sure you have seen this calculating the
igon value of a simple Matrix all
that for this course let's not worry
about
this what we will start with and we will
be focusing on is how to solve ax equal
to B and using that solution to finally
incorporate even X great than equal to Z
here
so this problem is something which is
which has been solved in many ways this
I'm almost sure that this was
uh this you must have seen in your basic
course of mathematics in your
engineering course so this lecture is
basically a refresher of linear
algebra or a part of linear algebra
which talks about solving axal to B
uh if you are not familiar with this if
this is new to you I encourage you to
look at any standard book of linear
algebra my favorite R is the book by
Gilbert string which
is linear
algebra and its
applications but any standard textbook
on linear algebra will be good enough
for these constants these are Central
basic concepts of linear algebra so next
two lectures we'll talk about ax equal
to B how to solve axal to
B and generally when we have such a kind
of a general task of solving such
difficult problems or such set of
problems the first step is to actually
look at examples simple examples and see
can we at least solve some simple
examples and find a
way and let me give you a very very
simple
example
uh notice that I have replaced X1 with X
and X2 with Y I don't think this should
be a cause of concern this is just
change of
variables if I give you this set of
linear equations you will immediately
realize oh this is very very
simple right the solution
is X is equal to
1 and Y is equal to
2 so by doing some manipulation you can
I'm sure almost all of you can solve
this set of
equations
right this is not the only
case there are complications
here what what about this set of
equations 2x + 2 y = 4 and x + y =
3 and if you think about it for a little
bit you will realize that this set of
equations cannot be
solved in some cases we have a solution
in some cases we have a no solution it
will turn out there are some cases where
we have infinite many
solutions so even this innocent looking
bunch of equations can give rise to many
situations how are we going to solve now
once again you can say oh you gave me
the equation I looked at it and I could
solve
it that is great when you had small
number of variables and small number of
equations here but like in linear
program we want to do it when we have
thousands of variables and thousands of
equations can we still design an
algorithm can we still design a program
to solve all such equations and not such
simple
equations
though if you want to even solve such
General
equations let's take some hint from how
we went about solving this equation
right what we actually did to come up
with this solution here and that should
probably give us an idea of solving
this big
equation if you already know
it then this is
called gosin
elimination if you don't know it you're
are going to learn it in next 30 minutes
what is gosin elimination we are going
to redefine our thinking and see that
there's a standard way to attack any
such axal to B
problem if we wanted to solve this bunch
of
equation uh I think a very natural way
to look at this is and say oh there is
an extra X
here right so what I can do is I can
subtract this equation from this
equation this will tell me me that
actually adding one extra X gives me one
more so this bunch of equations are
actually equivalent
to notice this is
obtained by doing this right 2 x - x is
x y - Y is 0 4 - 3 is
1 and once I did this step my life
became easy if x is 1 I
can substitute this
value and this will give me
y
right so if I put x = 1 in this equation
2 4 Y = 2 great so I found x = 1 and y =
2 as a
solution now this is what I will call
a good form you know why is this a good
form X is equal to 1 I get the value of
x then I can substitute X in the
previous equation to get Y and probably
if there were more equations it might
have happened that the next equation was
in x + y + z so I will substitute the
value of X and Y I will get the value of
Zed so to give you an
example let's say if I had these three
equations X = to 1 y equal to two and
then right so I get Z is equal
to -1 by 3 so I can back substitute and
get my entire solution so my objective
would be to convert take this General
set of equations and convert them into
good form you can notice that this
is trying to make
a
upper or lower
triangular this is what I want to but I
had a set of equations which were very
simple our life is not going to be that
simple all the time we take more
examples and we see more complications
so let's take more and more examples and
it will tell us what can happen in
different
situations
now this is a slightly bigger example
which has three variables now and I want
to solve for x y and
z now looking at the idea of this is it
possible that I remove X from equation 2
and equation
three that is my first objective because
remember here I made the coefficient of
y0 here I will first make the
coefficient of x0 in these two then
coefficient of y z in this equation
that's what I want to
do
so to make my life
easy
I can
divide by two so that I have a single
coefficient of x x and then I can
multiply this by four to make this zero
I can multiply that this equation by
minus 2 to make this zero right
so 3 what I'm going to do is I'm going
to do 2 - 4 * equation so let me just
make a better notation so that you don't
get confused sorry for this let's call
it E1 equation
1 equation 2 equation 3 so what I'm
going to do is I'm going to take
equation 2 and subtract four * equation
1 that will make the coefficient of x0
and to making the coefficient
of x0 in equation 3 I'm going to do
2 * equation one you can make these
calculations and what you will get is
X
it is important that you should be able
to do these calculations on your own so
make sure that you can come to this
step and
now I can add these two equations to
make the coefficient of y0 in equation
three notice uh it requires a formal
proof it is there in any Le of the book
but this operation when I add this and
write the added added
equation this and these are equivalent
system of equations that means the
solutions here are the same as the
solutions here this this these
operations do not change the set of
solutions that's it's easy to prove
it
now uh just to give you an idea there
could have been complications here what
if the coefficient of Y was zero
here if the coefficient of Y was zero
here instead of minus 8 how can I remove
it from equation three that's an easy
thing right very good so as Tuan said
one way is I say that oh Zed is my
second
variable or other way is I say that oh I
will just interchange E2 and
E3 and then I will have a y coefficient
and I can make sure that other where y
becomes zero this is not a big
problem so uh first problem could have
been coefficient of
Y 0o in
E2 but then you can exchange E2 and E3
but a bigger
problem is
if coefficient of Y is zero
everywhere there are multiple such cases
where our
standard uh procedure will get stuck but
there are solutions out we will talk
about them but for now let's proceed
here in this case life is
simple I replace
E3 with E2 +
E3 and
then
once again we have things in
the good form Z is equal to
2 if I put Z is equal to 2 here this
will show that Y is equal to
1 this will be 1
this will be
half so by back
substitution I can solve
everything and you can uh convince
yourself that if even if there were more
equations and if my
process does not get stuck into these
problems I will always get into a good
form and my life will be okay
this is a good news in ax equal to B if
I don't get into stuck into this problem
I can always convert into good form and
I can find
solution
good where will be where will there be a
hiccup
and these are what I
call weird cases there are some set of
equations which can actually create
problem for us
so let's
see
I'm got not going to write every step in
detail now because you have seen how to
make it work once again if I want to
remove coefficient of x I will take this
equation multiply it by two and remove
it from
here
so once you do this you will see that uh
X and Y both are eliminated
here and again important point is these
two system of equations are actually
equivalent they are exactly the same
instead of solving this I can now solve
this but now this this is our first
problem it's not really a problem uh
Tuan has already told us how to solve it
but the uh let's say even at the first
glance it seems like oh my God I wanted
to remove coefficient of Y using this
equation but the coefficient of Y here
is
zero
so first
problem but I would say even this is not
even a
problem at all this is very very
easy instead of this I can just
interchange
this obviously if I change the order of
these equations the set of solutions do
not
change so
then I get this and I don't need any
vincing to tell you that just because I
write this equation first and this
equation later I don't change any
solution right good so now once I have
gotten this notice this is
in good
form once again if these equations are
in good form I can back
substitute Zed is going to be Min - 4
you can calculate value of y you can
calculate value of x so the first
problem is not really an important
problem even the bigger problem is not
going to be
a very big problem you will see that uh
there's a simple resolution to go about
it
let's say we had this set of
equations and now once again if I try to
eliminate
X
I
get
right what should we do now we are in a
bigger problem where coefficient of Y is
zero
everywhere though there's a small thing
here that if you ignore this equation
look at these two equations it tells us
that we have no solution if 3 Z is equal
to -12 then 4 Z should be equal to
-6 so we can forget about why we can say
that oh there is no solution possible
just because of
of E2 and
E3 no
solution but what if this was
actually the correct number okay so let
me just do it correctly If instead I
replace it
by-6 now what do I know
I have x + y + z = 5 3 Z = -12 4 Z =
-6 I know that equation 2 and equation
three are the same equations so why
worry about
this futile
equation right I will just
say my original set of
equations this
box is
same as this box and now I can
even uh replace this I know Zed is
-4 so I
get x + y = 9 right this is the case
when we actually get infinite
solutions in this case your Zed is min
-4 y you can choose y or you can choose
X why you can
choose whatever you
like and depending on that your X
is L this
way
[Music]
[Music]
[Music]
right
[Music]
