Current time:0:00Total duration:18:50

0 energy points

# Least squares examples

An example using the least squares solution to an unsolvable system. Created by Sal Khan.

Video transcript

So I've got three lines in R2,
and I want to find their intersection. So the first one is 2x minus y
is equal to 2, the second one is x plus 2y is equal to 1, and
the third one is x plus y is equal to 4. So let's first just graph these,
just to have a visual representation of what
we're trying to do. So I like writing my lines in
y equals mx plus b form. So this top line becomes what? Minus y is equal to minus
2x, minus 2x plus 2. I just subtracted 2x
from both sides. Or we could write that y
is equal to 2x minus 2. That's the first line here. The second line-- I'm doing it
in green --we could write this as 2y is equal to minus x plus
1, or we could write that y is equal to minus 1/2 x plus 1/2. I just divided both
sides by 2. And this last line right here,
we could write this as y is equal to minus x plus 4. Go straight here. y is equal to minus x plus 4. Now let me graph these. Let me draw an axis,
that is my y-axis. I can call it my y-axis since
we're actually dealing with x and y's now. I'll do it slightly lighter. I'll do it in this
grey as well. I'd say that is my x-axis. Just like that. And this first guy is going
to be 2x minus 2. So it's y-intercept is going
to be at minus 2. It's going to have a slope of
2, so it's going to be a pretty steep line,
just like that. So that's that first line,
just like that. 2x minus 2. The next line is 1/2,
minus 1/2, plus 1/2. So if we go plus 1/2, that's
right there, and then the slope is minus 1/2. So for every 2 we go
over, we go down 1. So it's going to be like that. It's actually going to
be orthogonal, right? Because it's the negative
inverse of this guy. So it's going to look
something like that. We draw it like that,
just like that. And this guy is minus
x plus 4. This is 1, 2, 3, 4, and you go
minus x, so for every 1 you go over, you go down 1. So this other line is going to
look something like this. This other line, this last
line, is going to look something like that. Just like that. Now, I said at the beginning of
this video that I want to find the intersection of
these three lines. But notice, there is
no intersection of these three lines. They all intersect the other
two, but they don't all intersect each other
in one point. We can kind of call the system
as being overdetermined. We've overconstrained it. There is no intersection of
all three of these points. So if I were to actually try to
solve this system, I would find no solution. And to say that this has no
solution is equivalent to saying that this
matrix, or this equation has no solutions. Let me write this. I'm just going to rewrite
the system like this. This is equivalent to the
matrix, let me make sure I get this right, the matrix times
the vector xy is equal to 2, 1, and 4. And so, this first equation is
2 times x, minus 1 times y. So it's 2 and minus 1. 2 times x minus 1 times
y is equal to 2. That's that first equation
over there. The second equation-- actually
I could even, well I won't color code it, that'll take
forever --that's 1 times x plus 2 times y is equal to 1. And then we have x plus
y is equal to 4. This system and this equation,
this system right here, these are equivalent. Now, this isn't going to
have any solution. You could try to find
a solution to this. You could create an augmented
matrix, put it in reduced row echelon form. But there is no intersection
to the three things. So you're not going to find
a solution to A times some vector-- we could call this some
vector x --is equal to B. Or another way to say it, is
that B is not in the column space of this matrix
right here. Now, we learned in the last
video that sure, we can't find a solution to Ax equals B. Ax equals B has no solution. We see it graphically here;
these lines don't intersect with each other. And you could prove it for
yourself algebraically by trying to find a
solution here. You'll end up with
a 0 equals 1. But we can almost get
there by finding a least squares solution. And we find a least squares
solution if we multiply both sides by A transpose. We know that A transpose times
A times our least squares solution is going to be equal
to A transpose times B. So at least we can find the
closest fit for our solution. So let's find the vector
x this is our least squares solution. So what is A transpose
times A? A transpose looks like
this, you'll have 2 minus 1, 1, 2, 1, 1. That is A transpose. And then of course A is
just this thing: 2 minus 1, 1, 1, 1, 1. So A transpose A is going to be
equal to-- We have a 2 by 3 times a 3 by 2 matrix, so it's
going to be a 2 by 2 matrix. So it's going to be
a 2 by 2 matrix. So what do we get, we get 2
times 2 which is 4, plus 1 times 1, plus 1 times 1. So it's 4 plus 1 plus 1. So that's equal to 6. And then we have 2 times minus
1, which is minus 2, plus 1 times 2, so those cancel out. Minus 2 plus 2 is 0,
plus 1 times 1. That's just going to be 1. And then we get minus 1 times
2, which is minus 2, plus 2 times 1, which is 2. So the minus 2 plus 2 is 0, plus
1 times 1, so we get a 1. And then finally, we get minus
1 times minus 1, which is positive 1. Plus 2 times 2, which is
4, so we're now at 5. Plus 1 times 1, so this
is going to be 6. So this is A transpose A. Now, what is A transpose
times B? A transpose is 2, 1,
1, minus 1, 2, 1. And then B is just the 3 by 1
vector, the vector that's a member of R3, 2, 1, 4. So what is this going
to be equal to? This is going to be equal
to-- We get a 3. Sorry, this is a 2 by
3 times a 3 by 1. We're going to get
a 2 by 1 vector. You get a 2 by 1 vector here. So 2 times 2 is 4, plus 1
times 1, so that's plus 1, so that's 5. Plus-- let me actually write it
down, I'm going to make a careless mistake --2 times 2,
which is 4, plus 1 times 1, which is 1, plus 1 times
4, which is 4. Then here, you have minus 1
times 2, which is minus 2, 2 times 1, which is 2, plus
1 times 4, which is 4. So A transpose times B is
equal to 9, and this is going to be 4. So we can rewrite this guy right
here as the matrix A transpose A. Which is just 6, 1, 1, 6 times
my least squares solution-- so this is actually going to be in
the column space of A --is equal to A transpose times B,
which is just the vector 9 4. And this'll be a little bit more
straightforward to find a solution for. In fact, there will
be a solution. We proved it in the
last video. So to find a solution, let's
create our little augmented matrix: 6, 1, augmented
with a 9. You have the 4 there,
you get a 1 and a 6. Just like that. Let's put the left hand side in
reduced row echelon form. Actually, first I'm going
to swap these two rows. That's my first row operation
that I choose to do, just because I like to have
that 1 there. It's a nice pivot entry. So then it goes to 1,
6, 4, and 6, 1, 9. And then let me replace my
second row with the second row minus 6 times the first row. So I'm going to keep my
first row the same. So I have 1, 6, and 4. And then my second row, I'm
going to replace my second row with a second row minus
6 times the first row. So 6 minus 6 is 0. 1 minus 6 times 6, that's 1
minus 36, so that's minus 35. And then a 9 minus 6 times
4, is 9 minus 24. This one always gets
me in trouble. So 9 minus 24, that's the
negative of 24 minus 9, so that is minus 15. Let me make sure I didn't
make a careless mistake. 1 minus 36 is minus 35, 9
minus 24, is minus 15. So that's what I get
right there. And then let me go to the right
now, so let me let me divide this row right here, let
me divide it by minus 35. So I'm going to keep my
first row the same. 1, 6, and 4. And then this guy right
here, I'm going to divide by minus 35. So I'm going to get 0, 1, and
then minus 15 over minus 35. That's 15 over 35, or
that's 3 over 7, so that is equal to 3/7. And then let me just put this
in complete reduced row echelon form. That'll be nice. Let me keep my second
row the same. So my second row is
0, 1, and 3/7. And then my first row, I'm going
to replace it with my first row minus 6 times
my second row. So 1 minus 6 times 0 is 1, 6
minus 6 times 1 is 0, and then we have 4 minus 6 times 3/7. So 4 is 28/7. Let me write it up here. So we have 4, which is 28/7,
minus 6 times 3/7, so minus 18/7, right? That's 6 times 3/7. So this is going to
be equal to 10/7. And just like that, I've solved
this new equation. So you could say that-- Let
me write it this way. We could write that x star--
This is going to the first entry of x star, which
we could call x, is going to be 10/7. Let me write this. x star, the solution is going
to be 10/7 and 3/7. So I'm saying that if you take
x is equal to 10/7 and y is equal to 3/7, you're going
to get as close to a solution as possible. Let's see what that looks
like visually? What is 10/7? Let me write this down. x star
is equal to 10/7 and 3/7. We're saying the closest-- Our
least squares solution is x is equal to 10/7, so x is
a little over one. And then y is going to be 3/7,
a little less than 1/2. So our least squares solution
is going to be this one, right there. And so this, when you put this
value for x, when you put x is equal to 10/7 and y is equal
to 3/7, you're going to minimize the collective squares
of the distances between all of these guys. I drew this a little bit
too small to show that. But let's actually figure out
what our least, what our minimized difference is. Remember, the whole point of
the is to minimize the distance between Ax star, is
to minimize the distance between Ax star and B. Or between B and Ax star. Now, what was Ax
star equal to? Ax star was equal to 9/4. So this right here. Sorry, Ax star, that's not
equal to 9/4, that's A transpose Ax star
is equal to 9/4. Ax star is our original matrix
A, which is this one right here, so 2-- Let me write
it down here. I know it's off the
page right now. So our original matrix A was
2, minus 1, 1, 2, 1, 1. That was our original matrix
A right there. And then our x star,
we were able to determine, is 10/7 and 3/7. So Ax star is going to be
this product, so what does it equal to? It is equal to, it is going
to be a 3 by 1 matrix. So we got 2 times 10/7, which
is 20/7, minus 1 times 3/7, so minus 3/7. And then we get, let me see,
yep, that's 10 minus 3/7, and we have 10/7, minus 2 times
3/7, so minus 6/7. Or plus, sorry, this
is a plus. Right? 2 times 10/7 is 20/7 minus 1
times 3/7, then we have 1 times 10/7 plus 2 times 3/7. And then we have
10/7 plus 3/7. So Ax, so this is A and x
star, our least squares approximation for x, is
equal to what is this? This is 17/7, this is 16/7,
and this is 13/7. We want to find out with this
minimum distance is. So, let's see, this is going
to be this thing. So 17/7, 16/7, and 13/7
minus our original B. Our original B was
2, 1, and 4. So I'm claiming that my solution
that we just found, this minimizes this distance. Because this is the projection
of B onto the column space of A. We saw that before. So our B we see all the
way up here is 2, 1, 4, just like that. So if we take the length of
this-- let me switch colors --this is equal to the length. Let me write all of us
in sevenths-- I'll just do it in my head. I don't want to waste
too much time. So this is 17/7 minus
14/7, right? 2 is 14/7, so this is
going to be 3/7. Then it's 16/7 minus
7/7, so that's 9/7. And then we have 13/7 minus
28/7, so that is minus 15 over 7. So this is the vector that
separates the B that was not in my column space of A from
the projection of B. And if we find it's length,
it's length is going to be equal to-- Let's find the square
of it's length first. The square of its length is
going to be 3/7 squared, so that is 9/49, plus 9/7 squared,
which is 81/49, plus minus 15/7 squared. What's 15 squared? 15 squared is 225, I think. Let me make sure. I'm prone to careless
mistakes. 5 times 5 is 25, 1 times
5, this is 75, and then I have a 150. Yep, 225. So plus 225/49. Which is equal to-- So 9 plus 81
is 90, and then so 225 plus 90, to get a 5, was a 315. So this is equal to 315/49. Or, if we actually wanted the
difference, that's going to square root of this. So if we take just the regular
distance, that's equal to the square root of that. So it's equal to the square
root of 315 over 7. And square root of 315,
it looks like that is simplifiable. Does 9 go into it? Looks like 9 goes into it,
maybe 35 five times? So it would be what, 3 square
roots of 35 over 7. So that is just a measure. Let me put it this way, you're
not going to be able to find any member of R2, any values
of x and y, that's going to give you a smaller value than
this when you find the distance between it's solution
and the solution you were trying to get to. So this, based on our least
squares solution, is the best estimate you're going to get.
x is equal to 10/7, y is equal to 3/7. A little bit right,
just like that. Anyway, hopefully you found
that useful, and you're starting to appreciate that the
least squares solution is pretty useful.