12. Computing Eigenvalues and Singular Values
2.71M subscribers
SUBSCRIBED
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018 Instructor: Gilbert Strang View the complete course: https://ocw.mit.edu/18-065S18YouTube Playlist: https://www.youtube.com/playlist?list...Numerical linear algebra is the subject of this lecture and, in particular, how to compute eigenvalues and singular values. This includes discussion of the Hessenberg matrix, a square matrix that is almost (except for one extra diagonal) triangular. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
00:00
00:01
The following content is provided under a Creative
00:03
Commons license.
00:05
Your support will help MIT OpenCourseWare
00:07
continue to offer high quality educational resources for free.
00:11
To make a donation or to view additional materials
00:14
from hundreds of MIT courses, visit MIT OpenCourseWare
00:18
at ocw.mit.edu.
00:19
00:22
GILBERT STRANG: OK.
00:23
Why don't I start?
00:25
So I was hoping that we would have the next online assignment
00:32
ready, but Julia 0.6, the new version, is slowing us down,
00:37
and it'll probably be next time.
00:42
But my lectures, of course, are--
00:47
well, what I want to say, perhaps,
00:49
is this isn't intended to be a course
00:52
in numerical linear algebra, but I
00:55
thought I couldn't let the whole semester go by without saying
01:00
something about how to compute eigenvalues and singular
01:04
values.
01:07
Of course, you're going to call eig or SVD or the equivalent
01:14
in Python or Julia.
01:17
But actually, the QR factorization
01:23
that we spoke about, that we spoke entirely about last time,
01:27
is the key--
01:29
unexpectedly, unexpectedly.
01:31
You have a matrix A whose eigenvalues you want.
01:38
So let's start with eigenvalues.
01:41
And it might be a symmetric matrix.
01:44
I'll stay with A rather than S because it doesn't have to be,
01:49
but you get special--
01:51
always you get something special if the matrix is symmetric.
01:55
01:58
So this method of computing eigenvalues, to me at least
02:03
and I think to many people, came out
02:05
of the blue a while ago, but not that long ago.
02:12
And it worked very well.
02:14
So here's the idea.
02:16
It's called the QR method because you start by factoring
02:21
your matrix into QR.
02:23
So here's A. Can we call it A0?
02:29
That's the matrix we start with whose eigenvalues we want.
02:33
And I'll call these Q0 and R0.
02:37
And you remember what that means,
02:40
what's hiding behind those letters that I've written?
02:44
You have the columns of A, possibly symmetric as I said,
02:49
but not orthogonal usually.
02:54
So you find an orthogonal basis.
02:59
You orthogonalize-- you line them up
03:01
perpendicular to each other.
03:03
And then there is a matrix R, which
03:07
happens to be upper triangular, that
03:11
connects the not-orthogonal basis
03:15
with the orthogonality base.
03:18
Right.
03:18
We constructed R step-by-step.
03:26
And then, the idea is write these in the reverse order,
03:34
and that will be A1, the next A. And then do it again and again
03:42
and again.
03:44
And so we're hoping, of course, that the eigenvalues didn't
03:50
change.
03:51
We're hoping that we can forget A0, start again with A1,
03:56
and produce A2 and continue.
03:59
So we're hoping two things.
04:00
One will not be a hope.
04:02
We can see that the eigenvalues of A1 and A0 are the same.
04:08
So we have not changed the eigenvalues.
04:11
How do we see that?
04:12
If you had to show that two matrices had
04:15
the same eigenvalues, would you compute all the eigenvalues
04:20
and compare them?
04:21
Certainly not.
04:23
What would you do?
04:23
What's the best test, the usual test, the usual thing
04:29
you would want to show to--
04:31
AUDIENCE: They're similar.
04:33
GILBERT STRANG: They're similar, that's right.
04:35
So the claim would be that these two matrices are similar.
04:39
Right.
04:40
So maybe we should show that.
04:42
So we want to write A1 in a different way.
04:45
So the claim is A1 is similar to A.
04:51
So we just have to figure out--
04:55
we have to get A1 and turn it to A0.
04:58
So here is A1.
04:59
05:03
So A1.
05:05
I want to show that that's right.
05:07
So that's R0, Q0.
05:11
But what is Q0?
05:14
From here, Q0 is what we--
05:17
05:20
Q0 is-- what do I want?
05:22
I want to put R0 inverse over there.
05:24
So R0.
05:27
Now for Q0, I'm going to substitute.
05:31
So what is Q0?
05:35
I multiply both sides of that equation by R0 inverse.
05:39
So Q0 is A0 is-- sorry, I said A and wrote Q. A0, R0 inverse.
05:51
05:55
For Q0, I've put in what it equals.
05:59
And that's done it.
06:02
That's exactly telling me that A1 which is this, equals this,
06:09
and that's a similarity transformation.
06:12
I have not changed the eigenvalues.
06:14
So that's OK.
06:17
The other thing, which is the, you could say,
06:20
the miracle in this thing, is that when
06:24
I continue to do that for almost every matrix,
06:29
the matrices begin to lose stuff off the diagonal,
06:35
especially below the diagonal by the ordering that QR has done.
06:41
So it would tend to--
06:43
you start with a matrix A0.
06:45
06:49
You got a matrix A1, which is a little smaller here.
06:54
06:59
This part being especially smaller.
07:02
You do it again.
07:03
This is even smaller.
07:06
Even smaller.
07:07
A2.
07:08
Even smaller.
07:10
And you keep going.
07:11
And for most matrices, the result is that--
07:18
I don't know how many steps we want to think of taking,
07:22
but we get quite small numbers here, especially--
07:28
yeah.
07:29
So once we get small numbers here, little epsilons--
07:32
that's everybody's shorthand for small numbers--
07:37
what would you expect to see on the diagonal?
07:41
AUDIENCE: The eigenvalues.
07:42
GILBERT STRANG: The eigenvalues, because this
07:45
has the same eigenvalues as this,
07:47
as this, as this, and these little epsilons
07:50
are not going to change the eigenvalues too much.
07:53
So these will be, on the diagonal,
07:56
will be close to the eigenvalues.
08:02
And actually, what happens is this one comes first.
08:07
That one is quite accurate first.
08:10
I guess we should probably do a simple example
08:16
to see this happen.
08:19
Actually, I do an example in the notes.
08:22
And let me say what happens.
08:25
So I do a 2 by 2 example which has something
08:29
like cos theta, sine theta.
08:33
08:37
I don't know what--
08:38
I've forgotten what I took, and I don't have that page of notes
08:41
here.
08:42
Something here, something here, something here as A0.
08:51
And, then A1, after just one step,
08:55
has sine cubed theta there and numbers there
09:04
that are getting much closer to the eigenvalues.
09:08
Sorry that this isn't a full-scale example,
09:11
but the point of the example is here,
09:14
that this off-diagonal entry gets cubed.
09:22
And the next step will be its 9th power, and then
09:27
the 27th power.
09:29
So it's really quickly going to 0.
09:32
And this happens-- so cubic convergence is--
09:39
that's a price in numerical linear algebra.
09:45
So that happens.
09:48
So this arrived on the scene and quickly
09:53
blew away all other methods that were being
09:57
used to compute eigenvalues.
10:00
But numerical people, being what they are,
10:04
they wanted to improve it--
10:06
like, is there a way to make it faster?
10:08
And it turned out there is.
10:12
It turned out that the better way--
10:14
10:17
basically, the same idea, but just you're
10:21
always looking for a simple change.
10:27
10:31
And the idea of introducing a shift
10:34
was tried and turned out to work extremely well.
10:42
So that's the improvement.
10:44
So we take A1--
10:47
no.
10:47
So how does it--
10:49
how does the shift work?
10:51
So instead of A1--
10:54
have I got space here to do this?
10:57
Instead of A0, I take A1 minus a shift.
11:02
So a shift is some multiple of the identity.
11:06
If I just move a matrix by a multiple of the identity,
11:10
what happens to its eigenvectors?
11:12
What happens to its eigenvalues?
11:14
Something pretty simple, right, because I'm just
11:16
shifting by sI.
11:19
What happens to its eigenvectors?
11:21
AUDIENCE: They stay the same.
11:22
GILBERT STRANG: They're the same.
11:24
And what happens to the eigenvalues?
11:26
AUDIENCE: They change by s.
11:27
GILBERT STRANG: They change by s.
11:30
If A0 V equaled lambda v, then when I multiply this by V,
11:37
there will be an extra--
11:39
it'll be lambda minus s because the identity times the V
11:44
is just V. So it just shifts all the eigenvalues by s.
11:50
And you try to shift--
11:52
you look for a shift.
11:54
This would be great.
11:55
If you knew lambda N, a shift there,
11:59
you would be looking for 0 then if you shifted them
12:03
all by that lambda.
12:05
And it turns out that would speed things up.
12:07
So it will work instead with this matrix as now,
12:12
again, I'm factoring it in a Q0 R0.
12:17
So that's the work of the method is in doing Gram-Schmidt
12:23
at every step.
12:25
And then there's a little work in reversing the order.
12:28
12:33
And then I want to undo the shift,
12:37
so I do that factorization.
12:39
Now, let's see.
12:40
You may have to help me to remember what I should do here.
12:45
So I factor those.
12:47
I reverse those.
12:50
And then I think I add back the shift, and that's my A1.
12:57
13:00
So I took A0.
13:01
I shifted it.
13:03
I worked with it.
13:04
QR.
13:05
Reversed the order.
13:06
RQ.
13:07
Added back the shift to get a matrix.
13:11
And what am I, of course, hoping about the matrix A1 and A0?
13:16
I'm hoping they're still similar.
13:19
So I did a shift and I undid a shift.
13:23
But of course, after doing our QR, I have to check,
13:28
are these really still similar?
13:31
So let me just try to check that one again.
13:34
Maybe I'll just-- it's sitting right there,
13:39
so let me do it again.
13:42
I'm hoping something-- where did we--
13:49
oh yeah, here.
13:50
We show that A1 was similar to A0,
13:54
and I'm hoping that's probably still true even--
13:58
the shift didn't mess that up.
14:02
Let's just try.
14:03
So A0-- that's R0, Q0 plus sI.
14:08
14:12
And now what am I going to do?
14:15
I'm going to-- what did I do before?
14:19
I figured out what Q0 was from this.
14:24
14:26
You remember?
14:27
So this R0.
14:28
14:31
Now I have to put in Q0.
14:33
But Q0 is this thing inverse times this.
14:36
Is this going to work?
14:38
I'm hoping, but I don't think I wanted to get that.
14:42
14:47
No, it's not Q0 there.
14:50
What do I put it here?
14:52
14:55
And if it doesn't work, we'll leave it as an exercise.
15:01
AUDIENCE: [INAUDIBLE]
15:02
15:03
GILBERT STRANG: Yeah, because I didn't start right somehow.
15:08
15:11
But let me just push along to see what happens.
15:14
So I'm plugging in for Q0 here.
15:17
I'm plugging in this matrix, so it's shouldn't have
15:20
inverted it, times R0 inverse.
15:25
Who knows?
15:26
It might work.
15:28
Who knows?
15:29
So that's the R0, Q0.
15:31
Right?
15:33
Is everybody with me?
15:34
Sorry about the--
15:37
R0 inverse.
15:39
And then I have to add sI.
15:41
15:45
So what have I done?
15:47
I've just pushed on, believing that this
15:51
would work because it's the method that is constantly used.
15:59
Now, do I have--
16:01
what do I have there?
16:02
16:05
Is it working?
16:07
This is R0 A. That was, of course, A0.
16:11
R0, A0, R0 inverse.
16:14
R0, A0, R0 inverse.
16:19
Good.
16:21
Minus s.
16:23
What have I got there from the R0 minus sI R0?
16:29
What is that?
16:31
AUDIENCE: Minus sI.
16:32
GILBERT STRANG: That's minus sI.
16:33
Ha, look.
16:35
Success.
16:36
The R0 cancels the R0 inverse.
16:38
So that term from that, that, that is minus sI
16:44
cancels plus sI.
16:45
I'm finished.
16:46
And lo and behold, we have the same similarity.
16:51
So we messed around by a multiple of the identity,
16:56
and it didn't--
16:58
it actually makes the thing converge faster
17:04
if we choose the shifts well.
17:08
But basically, the same idea is still working.
17:12
So that's the QR method.
17:16
Well, that's the method.
17:17
We haven't shown and won't show that--
17:22
except for this half-completed example,
17:28
I don't plan to prove that the lower triangular part begins
17:36
to disappear, gets smaller and smaller and smaller,
17:40
and then the eigenvalues pop up on the diagonal.
17:44
It's amazing.
17:44
17:47
Amazing.
17:50
Now, is there any other improvement we can make?
17:55
So that's the method.
17:57
And where is the work in using that method?
18:00
Because that's what we always focus on.
18:03
Where are we spending computer time?
18:06
Well, we're spending computer time
18:08
in doing the factorization.
18:13
So it didn't cost anything to shift by the identity,
18:17
but then we had to factor that into Q0, R0.
18:21
Then it didn't cost much to multiply them
18:24
in the opposite order.
18:25
So the work was in QR.
18:29
So could we think of anything to improve that aspect?
18:36
Can we think of anything there?
18:38
And then we've got a really first class method.
18:43
Well, the matrix A--
18:48
A0, the matrix we started with--
18:52
had some zeros that allowed us to skip steps
19:02
in doing the QR factorization.
19:05
So what am I going to say?
19:07
I'm going to say if A or A0, our original matrix,
19:14
has a bunch of zeros--
19:16
let's say it's got a whole lot of zeros there.
19:18
Maybe it's--
19:18
19:25
Well, OK.
19:26
I overdid it here.
19:29
I know the eigenvalues right off.
19:33
But so the truth is I can't--
19:37
saying that if that is not going to happen.
19:41
But we can get zeros with one extra diagonal.
19:48
That turns out-- so here is the main diagonal.
19:51
Everybody's got his eye on the main diagonal.
19:55
And one diagonal--
20:01
I can get a lot of zeros, but I can't by simple computations.
20:06
And I'll show you how to get one.
20:10
But I can't get all those to be 0,
20:12
because then I would have the eigenvalues right there.
20:18
Well, how do I know that I can't?
20:20
In elimination, ordinary solving AX equal B,
20:24
you really do get to an upper triangular form.
20:29
Some operator, some elimination steps you plug away,
20:35
and your matrix becomes upper triangular U and you're golden.
20:42
But that's too much to expect here.
20:48
In fact, we know we can't do it by simple steps
20:52
because if we could do it, if we could get to a U
20:55
with a whole lower triangular part 0,
20:58
we would have found the eigenvalues.
21:02
And we know that the eigenvalues solve a system--
21:06
solve an equation of nth degree.
21:09
And we know-- somebody proved a century or more ago--
21:16
that you can't solve an nth degree equation
21:18
by simple little steps.
21:22
Do you know who that was and that you
21:24
know that fact and what degree does it apply to?
21:30
So that's an important fact that you pick up in math.
21:36
Yeah?
21:37
AUDIENCE: The 5th [INAUDIBLE].
21:38
GILBERT STRANG: 5th degree, yeah.
21:39
So 5 by 5 and up would be--
21:44
this is impossible.
21:45
Impossible.
21:48
There is no formula to find a simple formula for the lambdas.
22:02
And similarly for the sigmas for singular values.
22:06
So the eigenvalues is definitely a level
22:10
of difficulty beyond AX equal B, the inverse matrix,
22:15
or something, that pivots.
22:17
All that you can do exactly if you're doing exact arithmetic.
22:20
We cannot find the lambdas exactly,
22:27
but we can get as close as we like by continuing with the QR
22:35
method.
22:36
So yeah.
22:37
In other words, we can't--
22:39
we have to settle for--
22:41
if we want to, like at the beginning,
22:44
improve our matrix before we start doing that stuff,
22:49
we can get it with one extra diagonal.
22:52
And do you know what kind of a matrix, whose name--
22:56
I don't know why.
22:57
AUDIENCE: Upper Hessenberg.
22:58
GILBERT STRANG: Yeah.
22:59
Say it again.
22:59
AUDIENCE: Upper Hessenberg.
23:00
GILBERT STRANG: Upper Hessenberg.
23:02
So upper is just like upper triangular.
23:04
It's up there.
23:05
But key person's name is Hessenberg.
23:10
As I say, that's a Hessenberg matrix.
23:17
So Hessenberg matrix is a matrix with one triangular
23:21
plus one more diagonal, but lots of zeros.
23:26
Order of N squared.
23:28
Something like almost like half N squared--
23:31
not quite, but close--
23:34
zeros.
23:35
And you could show those zeros stay zeros in QR.
23:42
So that really pays off.
23:44
It cuts the work down significantly.
23:49
So that's the-- full QR method is Step 1--
23:55
reduce A to Hessenberg form with these zeros.
24:08
And when I say reduce, I mean find a similarity
24:11
transformation, of course, because I
24:13
want the eigenvalues of this to end up the same as the Hessen.
24:19
I want to keep the same eigenvalues as I go.
24:21
And then, Step 2 is QR on this Hessenberg matrix with shifts.
24:28
24:33
So that's the code that would be programmed in eig(A).
24:37
24:41
That's what Matlab and--
24:42
well really, Matlab is appealing--
24:46
like other matrix systems--
24:49
is appealing to LAPACK and LINPACK.
24:54
A team of professional numerical analysts
24:59
really spent a lot of effort and time.
25:04
The book LAPACK has 10 authors, and you
25:14
can download any of these codes, like the eigenvalue code.
25:18
So that's where Matlab, naturally--
25:23
that's the Bible for code in linear algebra.
25:29
25:32
I think it's interesting to know.
25:35
And there's one more good thing to tell you about this method.
25:42
And it applies if the matrix is symmetric.
25:45
If the matrix is symmetric, then if we check all this,
25:49
we could find that the matrices stayed symmetric.
25:55
If A0 is symmetric, I can check--
25:58
you could easily check through this
26:00
and you would discover that A1 is also symmetric.
26:03
26:08
It turns out you could rewrite this
26:12
with a Q0 in a Q0 inverse on the other side,
26:17
but that Q0 inverse is the same as Q0 transposed
26:21
because it's an orthogonal matrix,
26:23
and symmetry would fall out.
26:26
So if it's symmetric, and it's in his Hessenberg form
26:31
and it stays symmetric at every step,
26:34
what can you tell me about a symmetric Heisenberg matrix?
26:39
AUDIENCE: [INAUDIBLE]
26:41
GILBERT STRANG: It's only got--
26:42
yeah.
26:42
You just erase all these.
26:45
If they are zeros there and if the matrix is symmetric,
26:48
then we can safely predict that it will only
26:54
have one diagonal above, one non-zero
26:57
diagonal above the main diagonal.
27:00
In fact, it will say symmetric.
27:04
So now I should write "symmetric Hessenberg matrix,"
27:09
and equals tridiagonal matrix.
27:13
27:19
Three diagonals.
27:23
So now you really have reduced the time
27:25
to do QR because you've got a tridiagonal matrix.
27:32
It'll stay tridiagonal in all these steps.
27:35
So you're working with just three N numbers.
27:38
Well actually, two N because the diagonal above and the diagonal
27:42
below are the same.
27:44
You're working with just two N numbers instead of order N
27:47
squared, and it just goes like a bomb.
27:50
So that's eig for symmetric matrices.
27:55
And you see that it was all based--
27:57
that really the heart of the algorithm was QR.
28:08
So that's my-- that took half the class
28:12
to report on the favorite way, the eig way,
28:20
to find eigenvalues.
28:23
Oh, I should say something about singular values.
28:29
So singular values.
28:31
Of course, the singular values of the matrix
28:35
are the eigenvalues of A transpose A--
28:39
square root of those eigenvalues.
28:43
But you wouldn't do it that way.
28:44
You would never form A transpose A.
28:46
Oh, I didn't mention the other thing you would never,
28:49
ever, ever do, so let me just put it here like in disgrace.
28:57
To solve that equation is like, OK, back to first grade,
29:03
because that's not--
29:06
that's very bad.
29:09
A determinant-- first of all, it's extremely slow-- extremely
29:14
slow.
29:15
And the determinant is packing all this N squared pieces
29:21
of information into N coefficient,
29:24
and it's hopelessly ill conditioned.
29:28
Yeah.
29:28
You lose information all the time.
29:31
So really, if this is going on camera,
29:36
it better go on camera with an x, because you don't do it.
29:40
29:42
Yeah.
29:44
So where was I?
29:47
Singular values.
29:49
So A transpose A. So again, let's
29:56
think about what you could do at the beginning
29:59
before starting on QR for A transpose A
30:05
or for the matrix A. What could you
30:08
do with orthogonal matrices?
30:13
So I guess-- what did we say about symmetric matrices?
30:17
So here's what I said about symmetric matrices.
30:20
If you'll give me a symmetric matrix,
30:22
I can in just a simple number of simple steps
30:26
make it tridiagonal.
30:28
30:31
I can't make it diagonal because then I'd
30:33
be finding the eigenvalues and Abel, who was the first person
30:39
to see that that was impossible, forbids it.
30:42
30:45
So let me let me write down what I'm saying here.
30:48
If I have a symmetric matrix S, I
30:51
can find a bunch of Qs and Q transposes,
30:56
and I can put them all together into one big Q,
31:00
and it's transposed.
31:02
And what do I know about the eigenvalues of that matrix?
31:05
31:09
Q is orthogonal always.
31:12
So what can you tell me about the--
31:13
this is the same as QSQ inverse, and therefore the eigenvalues
31:20
are the same.
31:23
It's similar to S. And it becomes tridiagonal After?
31:35
I find a good Q. Therefore, same lambdas.
31:43
31:47
It's tridiagonal with the same lambdas.
31:50
Now, what am I thinking about here?
31:52
I'm thinking about-- tell me the corresponding possibility
32:00
about singular values.
32:01
I wanted to do something to my matrix.
32:04
Now, I'm always taking a general matrix A.
32:11
And I'm looking for its singular values.
32:14
And I'm looking to simplify it.
32:17
And what am I allowed to do?
32:21
Yeah, I guess my question is--
32:24
similarity transformations left the eigenvalues alone.
32:28
What can I do that leaves the singular values alone?
32:32
That's a fundamental question because it was so fundamental
32:35
for eigenvalues.
32:37
By doing this, a matrix and its inverse,
32:41
I got something similar, and I checked even
32:44
in this class that the eigenvalues, same lambdas.
32:49
Now I want a whole line that ends up with the same sigmas.
32:56
And I want you to tell me what I'm allowed to do to the matrix
33:01
without changing the sigmas.
33:03
So this is a--
33:05
maybe don't shout it out immediately.
33:07
Let everybody think.
33:10
What am I allowed to do to a matrix?
33:13
Every matrix has got these singular values,
33:16
and now I want to make it a better matrix
33:21
with more zeros or something.
33:25
If I do that to it, does that change the sigmas?
33:32
Can I do more than that to it?
33:35
What can I do?
33:36
What group of matrices will have the same sigmas
33:42
as my starting matrix A?
33:45
So that's a basic, basic question about singular values
33:50
and the SVD.
33:52
So let's think of the answer together.
33:57
So it's connected to the SVD, so let me remember the SVD.
34:02
The SVD-- I have some orthogonal matrix.
34:06
Then the singular value of the matrix--
34:08
SV for singular values.
34:10
And then another orthogonal matrix.
34:12
34:16
What could I do to that equation that would not touch this guy?
34:20
34:25
So I'm asking, what invariants?
34:28
Because not touching it means leaving it not varying.
34:32
So I'm looking for under what operations are the singular
34:39
values invariant?
34:41
When I was looking at eigenvalues,
34:43
this was the operation.
34:45
Well, it didn't have to be orthogonal--
34:47
something, then its inverse.
34:50
But now, what is it up there?
34:52
What could I do to that matrix A?
34:54
34:57
Could I multiply it by Q?
34:59
Could I throw in a Q maybe not even on the other end?
35:04
If I throw in an orthogonal Q, do I change the singular values
35:10
or do I not change them?
35:12
Fundamental question.
35:15
The answer is no, I don't change them.
35:18
I'm allowed to do.
35:19
That because here's an orthogonal matrix,
35:23
a Q times U. If both of those are orthogonal,
35:26
then the product is.
35:29
Everybody knows that a product of two orthogonal matrix
35:33
is still orthogonal.
35:35
Better know that.
35:36
Better know that.
35:37
35:39
So if I have an orthogonal matrix Q
35:42
and an orthogonal matrix U, I claim
35:45
that this is still orthogonal.
35:51
And how do I check it?
35:53
Well, I use some test for orthogonality.
35:56
What would be the--
35:57
what test do you like to use?
36:01
The inverse is the same as that transpose,
36:03
do you like that test?
36:05
So I'll invert it.
36:08
QU inverse.
36:10
Of course, for any matrix that's U inverse, Q inverse.
36:13
36:16
But these were separately orthogonal,
36:18
so that's U transpose Q transpose.
36:20
36:23
And that is the same as QU transpose.
36:28
36:31
So I used the orthogonality of U and the orthogonality of Q
36:36
to conclude that the inverse is the transpose.
36:40
So the answer is yes, I could do that.
36:44
Now, with singular value--
36:45
with eigenvalues, I had to multiply on the other side
36:50
by Q inverse or Q transpose.
36:53
Do I have to do that now?
36:55
No.
36:56
What can I do on the right-hand side?
36:58
37:01
I can multiply by--
37:03
I can leave it alone.
37:06
Then it has the same singular values because it's
37:10
the same sigma in there.
37:11
If I have a orthogonal matrix times a diagonal
37:14
times an orthogonal, that diagonal is--
37:18
positive diagonal is going to be sigma.
37:22
So what can I do on this side?
37:26
I can multiply by any orthogonal matrix on that side too.
37:32
So let's call this guy Q1 and this guy Q2.
37:37
I still have an orthogonal matrix there,
37:40
orthogonal matrix there, and the same sigma
37:43
popped in the middle.
37:45
So that's what you're allowed to do.
37:48
That gives us more freedom.
37:51
Before we got-- when we had to do similarity transformations
37:55
with the same guy, we got it to be tridiagonal.
38:00
But now, we're allowed to do more stuff.
38:04
We're allowed to use different orthogonal matrices on the left
38:09
and right.
38:11
And we can reduce it even further
38:13
from tridiagonal to bidiagonal.
38:17
So the first step is getting zero.
38:21
The step of getting zeros reduces it all the way
38:25
to that, with all zeros there.
38:28
38:31
So it's easier.
38:37
Then I work on this.
38:40
This is the matrix I work on using a QR type
38:44
idea, some method like that.
38:46
So everybody's seeing that our algorithm has got two stages.
38:53
One is get a lot of zeros and get them
38:56
in places that will stay zero as Part 2 of the algorithm
39:02
gets going.
39:03
And then, run Part 2 of the algorithm.
39:06
You staying with-- each step is very fast now
39:10
because doing a QR factorization is fast.
39:17
Was there a question?
39:18
Yeah.
39:20
So I would call this bidiagonal, of course.
39:23
39:26
And everybody recognizes that if I have a bidiagonal matrix--
39:31
call it A or A0 or whatever--
39:35
then what do you think about A transpose A?
39:39
What would A transpose A-- if that was A,
39:43
what could you tell me about A transpose A?
39:46
39:50
Could you multiply matrices knowing where the non-zeros are
39:57
in your head and get an idea of where--
40:00
and so if I have a bidiagonal matrix A, then implicitly
40:06
in the SVD, I'm looking at A transpose A.
40:10
And what would be true about A transpose A?
40:15
It would be tridiagonal.
40:18
So what I've done here and what I've done there just match up.
40:25
You can operate-- if you don't want to change singular values,
40:29
you can get all the way to here.
40:32
But then, to find those singular values, that
40:35
would involve A transpose A. It would
40:37
be symmetric and tridiagonal, and then you'd be in that game.
40:44
So those are the basic facts of eig and SVD
40:50
for matrices of order up to 1,000, say.
40:56
I'm not enough of an expert to know where--
40:59
41:03
Maybe higher, because in perfect math,
41:09
it's going to take infinitely many steps
41:12
or Abel would be very surprised.
41:16
He would see you solving for eigenvalues an nth degree
41:19
equation by a whole lot of little steps
41:21
and getting them exactly right.
41:23
That won't happen.
41:24
But you get them within epsilon in a number
41:29
of steps that's like N cubed.
41:32
So that's pretty impressive.
41:35
The eigenvalue problem is being "solved,"
41:38
in quotes, by a fast method that gets
41:47
you a good answer within a tolerance in N cube steps.
41:52
41:55
So that's great as long as N isn't too big.
41:58
And then, when N is too big-- which, of course, happens--
42:03
you have to think again.
42:04
So this method is a giant success up to large matrices,
42:12
but then you have to think again.
42:15
And what is involved in thinking again?
42:19
Well, I guess more thinking.
42:24
So what do you do if the matrix is bigger?
42:26
42:29
I guess that Krylov would say, use my method.
42:35
So Krylov would say-- especially if your matrix was sparse.
42:39
Can we just remember what Krylov was?
42:43
Krylov started with a vector b, multiplied it
42:47
by A, multiplied that by A, and got up to,
42:53
let's say, A to the 999b.
42:55
42:59
So now he's got--
43:01
Krylov has got 1,000-dimensional space.
43:05
He's got a basis for it--
43:06
1,000 vectors that span 1,000-dimensional space.
43:13
And he'll look at the matrix A only on that space.
43:17
In other words--
43:20
I won't go into detail about that.
43:22
He restricts the matrix to this 1,000-dimensional space,
43:28
and he hopes that it's captured.
43:29
We hope that the eigenvector is almost--
43:33
is virtually in that space.
43:35
And actually, I wouldn't go to--
43:38
let me take a 9 out of that.
43:39
43:42
100-dimensional would probably catch the eigenvector.
43:46
So if the eigenvector is virtually in this space,
43:50
then we can look at a matrix of order 100.
43:53
We can bring A down to just see its action on that space.
43:59
And any piece of--
44:02
so here is a-- so I look at vectors
44:06
v, which are some combination-- c1 b plus c2 Ab plus c3 A
44:14
squared b, and c100 A to the 99th b.
44:20
44:25
Plus an error.
44:26
44:29
And I'm going to ignore that error because I've
44:36
gone up to dimension 100.
44:38
I'd probably say it's pretty safe to ignore that error.
44:42
And then, in this space, just looking at the matrix
44:47
A-- so wherever A to the 100th comes in, forget it.
44:51
Just think about the matrix A as multiplying vectors
44:56
of this kind in this space.
44:58
Then I have 100 by 100 eigenvalue problem.
45:03
And so the big matrix A is reduced to a matrix of size 100
45:12
by--
45:13
do you see what I'm saying even?
45:15
So I'm not giving the details.
45:17
45:20
Think of a matrix A of size a million.
45:25
45:27
And you apply it to Krylov vectors--
45:30
so I call them little k for a Krylov vector--
45:33
45:36
in this 100-dimensional space.
45:38
45:41
So they have a million minus 100 0-components,
45:47
you could say, this k.
45:49
This is in the Krylov space.
45:51
This is A, a million--
45:53
k, 100.
45:58
It's a full-- so it's got a million components,
46:02
but it's out of just 100-dimensional space.
46:04
So when I multiply by A, it'll be mostly in--
46:10
partly in the Krylov space--
46:13
k100-- and a piece out of k100.
46:21
And I just ignore that part of the matrix.
46:25
So I have 100 by 100 problem, and I
46:27
solve to find the eigenvalues.
46:29
And they're a pretty good approximation
46:31
to the eigenvalues, to the, hopefully,
46:35
like the lowest 100 eigenvalues.
46:38
I'd like to know that, but I might not
46:40
be sure that this idea would give me
46:43
the lowest 100-- the first 100 eigenvalues of the million,
46:49
of the matrix of size a million.
46:51
I'm just taking a few minutes here to wave hands
46:58
about what Krylov idea would do.
47:03
And I probably won't mention Krylov again in this semester.
47:07
So what it can do is look at this particular type of space
47:14
because we can get a basis for it quickly.
47:17
Just multiply again and again by A. Then we
47:21
can orthogonalize that basis.
47:24
That's Gram-Schmidt in some form.
47:27
We're always going back to Gram-Schmidt.
47:29
Then I have 100 by 100--
47:31
I have a subspace of size 100.
47:34
I look at what the matrix does in that space,
47:38
and that I could look for--
47:41
I could find eigenvalues restricted to that space.
47:45
They wouldn't be the perfect eigenvalues,
47:47
but they would be accurate.
47:50
So I didn't know it would take one class time to talk
47:54
about finding eigenvalues and singular values,
47:57
but we did some important things.
48:00
We remembered that similarity is the thing to check,
48:05
thing to preserve, because it doesn't change the eigenvalues.
48:09
And then we-- for singular values, what was the thing?
48:14
You could multiply left and right
48:16
by different orthogonal matrices.
48:20
And somehow, maybe that doesn't have an established name,
48:24
multiplying left and right by a Q1 and a Q2 transpose.
48:31
But the idea is clear, and that doesn't
48:34
change the singular values.
48:37
We're ready to move now into--
48:42
maybe our next step, which we don't spend a long time on,
48:47
will be random sampling.
48:49
What if your matrix is just way too big?
48:53
So that's a very new idea, very different idea
49:00
in numerical linear algebra, is just to sample the matrix.
49:05
Could you believe that the answer
49:06
is going to come out right just for a random sample?
49:10
Well, the odds are in your favor.
49:13
So that will be Wednesday, and then we
49:15
have lots of new-- we'll move onward after that.
49:23
See you Wednesday.
49:24
Thanks.
49:25
English - CC (English)
###