Solving the apples and bananas problem: Gaussian elimination

Loading...

来自 Imperial College London 的课程

Mathematics for Machine Learning: Linear Algebra

897 个评分

Imperial College London

Mathematics for Machine Learning: Linear Algebra

897 个评分

课程 1（共 3 门，Specialization Mathematics for Machine Learning）

In this course on Linear Algebra we look at what linear algebra is and how it relates to vectors and matrices. Then we look through what vectors and matrices are and how to work with them, including the knotty problem of eigenvalues and eigenvectors, and how to use these to solve problems. Finally we look at how to use these to do fun things with datasets - like how to rotate images of faces and how to extract eigenvectors to look at how the Pagerank algorithm works. Since we're aiming at data-driven applications, we'll be implementing some of these ideas in code, not just on pencil and paper. Towards the end of the course, you'll write code blocks and encounter Jupyter notebooks in Python, but don't worry, these will be quite short, focussed on the concepts, and will guide you through if you’ve not coded before. At the end of this course you will have an intuitive understanding of vectors and matrices that will help you bridge the gap into linear algebra problems, and how to apply these concepts to machine learning.

从本节课中

Matrices in Linear Algebra: Objects that operate on Vectors

Now that we've looked at vectors, we can turn to matrices. First we look at how to use matrices as tools to solve linear algebra problems, and as objects that transform vectors. Then we look at how to solve systems of linear equations using matrices, which will then take us on to look at inverse matrices and determinants, and to think about what the determinant really is, intuitively speaking. Finally, we'll look at cases of special matrices that mean that the determinant is zero or where the matrix isn't invertible - cases where algorithms that need to invert a matrix will fail.

Solving the apples and bananas problem: Gaussian elimination8:00

Going from Gaussian elimination to finding the inverse matrix8:38

与讲师见面

David Dye
Professor of Metallurgy
Department of Materials
Samuel J. Cooper
Lecturer
Dyson School of Design Engineering
A. Freddie Page
Strategic Teaching Fellow
Dyson School of Design Engineering

So, now we're finally going to find a way to solve the apples and bananas problem.

And along the way,

we're going to find out about a thing called

the inverse of a matrix and a method for finding it.

So, let's go back to the apples and bananas problem.

We said that I walked into a shop and I bought two apples and three bananas,

and that that cost 8 dollars or euros or whatever my currency is.

And I went to the shop on another day and I buy ten apples and one banana,

and I got charged 13 euros for that.

So I wrote that down as a matrix times the vector.

And I could call that matrix, A,

and I call this vector, r,

and I could call that output vector, s.

So, A operates on r and gives me s.

What I want to do is I want to find out what Rr is,

what this vector a b is,

in order to give me the right numbers for the output vector.

Now, let's just think about this matrix, A, for a moment.

Let's see if I can think of another matrix.

I'm going to call this matrix A to the minus one,

that when I multiply it by A,

gives me the identity matrix.

I call this matrix here the inverse of A because

what it does to A is it exactly reverses whatever A does and gives me just the identity.

So, if I take this equation, Ar equals s,

if I multiply it on the left by A to the minus one on both sides, well,

what I find is,

is that this is just going to be the identity which is the matrix that does nothing.

So, when I multiply it by I, just get r,

so then I've got r is equal to A to the minus one times s,

the inverse matrix of a times s. So if I could find the inverse of A,

the matrix where multiplying by A

gives me the inverse, if I could find the inverse of A,

I can solve my problem and I can find what my a and b are,

and I've solved my apples and bananas problem.

Now, hold that thought about inverses for just a moment.

So, we said the inverse of A times A was the identity matrix.

We'll just park that up there for a moment.

Now, I actually don't have to go all

the way to the inverse to solve the apples and bananas problem.

I can do it just by substitutions.

So let's look at a slightly more complicated problem and see what I mean.

So, take a matrix that looks like like this: 1 1 3, 1 2 4, 1 1 2.

And I'm going to say that I have apples and bananas and carrots, say.

Okay they're not a fruit but they're another sort of fruit like object that we eat.

So, I'm saying that I bought one apple, one banana,

and three carrots, and that cost me,

let's say 15 euros.

Another day I went and I bought 1, 2 and 4, and that cost me 21 euros.

I don't know that I bought 1, 1, and 2,

and that cost me 13 euros.

Now, the thing to notice about a system of equations like this is that I can,

if I take this row off of another row,

I haven't changed anything, right?

So, I know that an apple, a banana,

and three carrots cost 15.

So if I take an apple, a banana, and three carrots,

and 15 off of the next row,

I haven't changed anything really about that row,

and the same for the third row.

So, I can make this problem simpler by going and doing that,

that sort of a process of elimination.

So if I call this row one,

row two, and row three,

if I take row one off of row two,

then I would have, take row one off of row two,

I'll have 0 1 1.

If I take row one off of row three,

I'll have 0 0 minus 1.

I'd still have a, b, and c. If I've taken on the right-hand side,

I've taken row one,

I've taken row one off of row two,

so I've taken 15 off of 21, so I'll have six left.

I'm taking row one off of row three,

so I'll have 13 minus 15 is minus two.

Ah, interesting.

So now, I can see that actually minus C is equal to minus two,

so I can multiply that row three by minus one.

Let's change pens.

And I've got a solution now for c,

that c is equal to two, so that's interesting.

Now, I've got what's called a triangular matrix,

that is, everything below the body diagonal is zero.

And that's a very interesting sort of matrix.

I've reduced it to what's called Echelon form.

All the numbers below the leading diagonal is zero.

Now, I can do what's called back substitution.

I can take my answer for c here and I

can put my answer for c back into the first two rows.

So, if I take one c equals two,

I know that one times c here is two here,

so I could take that off there and I could do the same.

I can take three times that of the first row.

So, if I go take three times it off the first row,

I'm going to get 1 1 0, a, b, c,

and I've taken three times the first one off of here,

so I've taken three twos off of here, so I'm going to get nine.

And if I take that third row off of the second row,

I'm going to get 0 1 0.

And I've got two off of six is four,

and I haven't changed the last row at all.

So now, I know that c here is equal to two.

I know that if I multiply that row by that column,

I've got just b is equal to four.

And I've got a plus b is equal to nine,

but I can tell you my answer for b back off this first row.

So, I've got then 1 0 0, 0 1 0, 0 0 1, a, b, c, and I've taken one b,

I've taken four off of the first row,

so that's 5 4 2.

So, my solution here for my apples,

bananas and carrot problem is the apples cost five euros,

bananas cost four euros,

and carrots cost two euros.

And that's solved the problem for me.

Very nice. So I didn't really have to compute the inverse at all.

But I've only found out the answer for this specific output vector.

So we said that this was A times r is equal to s.

I've only found it for this specific s. If I did the inverse in the general case,

I could do it for any s. I could find r for any s.

So, what I've done here is I've done what's first, elimination.

I've taken multiples of rows and I've taken them off of each

other to get to having a triangular form where the bottom corner here is zero.

So I've just got ones on the leading diagonal.

And then, I've done back substitution. Back substitution.

I've gone back up

of putting the numbers for c back into the first two rows, and then for b back into the first row,

and so on, to get my solution to my problem.

And that's very nice. This is actually one of

the most computationally efficient ways to solve this problem,

and it's going to work every time,

and it's very simple to understand how we can do it in relatively few operations.

So it's really, really nice.

And one thing to notice here is that, in doing so,

what I've done is I've transformed A into the identity matrix.

This is just the identity matrix.

There's ones only on leading diagonals and zeros everywhere else.

So, this is going to be a key to a way

to find the inverse which is what we'll look at next.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取