1
00:00:00,000 --> 00:00:00,499
2
00:00:00,499 --> 00:00:02,944
The following content is
provided under a Creative
3
00:00:02,944 --> 00:00:03,610
Commons license.
4
00:00:03,610 --> 00:00:05,460
Your support will help
MIT OpenCourseWare
5
00:00:05,460 --> 00:00:10,405
continue to offer high-quality
educational resources for free.
6
00:00:10,405 --> 00:00:12,530
To make a donation, or to
view additional materials
7
00:00:12,530 --> 00:00:16,170
from hundreds of MIT courses,
visit MIT OpenCourseWare
8
00:00:16,170 --> 00:00:20,045
at ocw.mit.edu.
9
00:00:20,045 --> 00:00:21,170
PROFESSOR STRANG: Well, OK.
10
00:00:21,170 --> 00:00:26,980
So I thought I would, as
last time, before Quiz 1
11
00:00:26,980 --> 00:00:29,250
and now before Quiz 2,
I thought I would just
12
00:00:29,250 --> 00:00:33,850
tell you what the topics
of the four problems are.
13
00:00:33,850 --> 00:00:39,350
Remember that trusses
are still to be reviewed,
14
00:00:39,350 --> 00:00:45,360
and of course the fun
was to find mechanisms,
15
00:00:45,360 --> 00:00:50,010
to find solutions to Au=0, in
the case when the truss was
16
00:00:50,010 --> 00:00:50,770
unstable.
17
00:00:50,770 --> 00:00:53,080
So you can guess
that I'll probably
18
00:00:53,080 --> 00:00:55,670
pick an unstable truss.
19
00:00:55,670 --> 00:00:59,800
And ask for mechanisms.
20
00:00:59,800 --> 00:01:06,070
Then maybe the key problem
for this third of the course
21
00:01:06,070 --> 00:01:09,550
is finite elements.
22
00:01:09,550 --> 00:01:12,030
That idea, and
finite elements we've
23
00:01:12,030 --> 00:01:13,910
really only done
in one dimension,
24
00:01:13,910 --> 00:01:20,780
so-- And particularly linear
hat function elements.
25
00:01:20,780 --> 00:01:25,640
So you see what's not
included there is like cubics.
26
00:01:25,640 --> 00:01:28,300
I mean, those are really
great finite elements,
27
00:01:28,300 --> 00:01:32,090
but maybe not so
great for an exam.
28
00:01:32,090 --> 00:01:35,480
So 1-D is enough;
linear elements
29
00:01:35,480 --> 00:01:37,500
are enough to do on an exam.
30
00:01:37,500 --> 00:01:40,540
And then questions
three and four,
31
00:01:40,540 --> 00:01:44,600
so this one will be
weighted more heavily.
32
00:01:44,600 --> 00:01:47,030
Then questions three
and four are the topics
33
00:01:47,030 --> 00:01:51,640
that we've been doing
the last week, two weeks.
34
00:01:51,640 --> 00:01:55,490
And I realize we
haven't had full time
35
00:01:55,490 --> 00:01:58,960
to digest them, to work
a whole lot of exercises.
36
00:01:58,960 --> 00:02:04,130
So those will be, right
now they're too simple,
37
00:02:04,130 --> 00:02:06,130
my questions on those topics.
38
00:02:06,130 --> 00:02:08,990
Three and four, I'll try to make
them a little harder for you.
39
00:02:08,990 --> 00:02:11,220
But I might not succeed.
40
00:02:11,220 --> 00:02:13,140
So, anyway.
41
00:02:13,140 --> 00:02:14,130
There we go.
42
00:02:14,130 --> 00:02:21,090
So I just felt we can't talk
about a course in applied math
43
00:02:21,090 --> 00:02:25,300
without dealing with these
topics in vector calculus
44
00:02:25,300 --> 00:02:28,100
that lead to Laplace's equation.
45
00:02:28,100 --> 00:02:31,520
But my heart is
really in solving
46
00:02:31,520 --> 00:02:35,970
Laplace's equation or Poisson's
equation by finite differences.
47
00:02:35,970 --> 00:02:39,310
That'll be today, or
by finite elements,
48
00:02:39,310 --> 00:02:43,370
that'll be Wednesday
and probably Friday.
49
00:02:43,370 --> 00:02:49,370
So this is like the core
of the computational side,
50
00:02:49,370 --> 00:02:52,390
but we had to do
this preparation.
51
00:02:52,390 --> 00:02:56,720
And then you know
that Peter kindly
52
00:02:56,720 --> 00:03:01,400
changed his weekly review
session to Tuesday,
53
00:03:01,400 --> 00:03:04,850
I think it's Tuesday at noon;
you could look on the website.
54
00:03:04,850 --> 00:03:12,670
So Peter will be a Tuesday
review and then regular, that's
55
00:03:12,670 --> 00:03:16,910
me, on Wednesday.
56
00:03:16,910 --> 00:03:21,430
And then the exam, I think,
is Wednesday evening.
57
00:03:21,430 --> 00:03:22,420
I think, yeah.
58
00:03:22,420 --> 00:03:24,800
Let me just do a review.
59
00:03:24,800 --> 00:03:29,840
Oh, Peter sent me a note about
a question on an old exam.
60
00:03:29,840 --> 00:03:34,680
I think it was 2005,
question three.
61
00:03:34,680 --> 00:03:42,170
I think it was 2005
question three.
62
00:03:42,170 --> 00:03:47,670
Peter said he didn't understand,
at all, the solution to 3c.
63
00:03:47,670 --> 00:03:52,860
Nor do I. I think
somehow, I think
64
00:03:52,860 --> 00:03:56,720
there was a little confusion in
that, and the answer in there
65
00:03:56,720 --> 00:03:58,970
is the answer to a
different question.
66
00:03:58,970 --> 00:04:01,890
Forget it.
67
00:04:01,890 --> 00:04:04,220
Having looked at
this one, a and b
68
00:04:04,220 --> 00:04:14,760
are worth looking at in this
div, grad, potential, stream
69
00:04:14,760 --> 00:04:18,690
function world that we're in.
70
00:04:18,690 --> 00:04:23,630
Those are typical
exercises in that area.
71
00:04:23,630 --> 00:04:24,370
Yes, question.
72
00:04:24,370 --> 00:04:26,170
AUDIENCE: [INAUDIBLE]
73
00:04:26,170 --> 00:04:27,670
PROFESSOR STRANG:
Oh, good question.
74
00:04:27,670 --> 00:04:28,170
Yes.
75
00:04:28,170 --> 00:04:29,200
Thanks for reminding me.
76
00:04:29,200 --> 00:04:35,160
So, solutions to the homework
that you're practicing with.
77
00:04:35,160 --> 00:04:41,150
If anybody has typed
up solutions or could,
78
00:04:41,150 --> 00:04:43,680
we'll post them right away.
79
00:04:43,680 --> 00:04:50,390
So I'll just hope for an
email from somebody who solved
80
00:04:50,390 --> 00:04:53,480
some or all of those problems.
81
00:04:53,480 --> 00:04:56,630
And of course you'll
see me again Wednesday.
82
00:04:56,630 --> 00:04:58,740
But that's an
invitation for anybody
83
00:04:58,740 --> 00:05:03,820
who worked through
those homeworks
84
00:05:03,820 --> 00:05:05,410
that I'll never collect.
85
00:05:05,410 --> 00:05:07,190
The current homework.
86
00:05:07,190 --> 00:05:09,500
OK, thanks for that.
87
00:05:09,500 --> 00:05:11,940
Other questions about
the exam, and then you'll
88
00:05:11,940 --> 00:05:16,130
have another chance
Wednesday to ask about that,
89
00:05:16,130 --> 00:05:18,030
so those are the topics.
90
00:05:18,030 --> 00:05:19,520
OK.
91
00:05:19,520 --> 00:05:24,350
And before I get to the
fast Poisson solvers
92
00:05:24,350 --> 00:05:27,930
there's so much about
Laplace's equation to say
93
00:05:27,930 --> 00:05:31,580
and I think it still
remains to write
94
00:05:31,580 --> 00:05:34,010
Green's formula on the board.
95
00:05:34,010 --> 00:05:39,990
And that's part of the big
picture of Laplace's equation
96
00:05:39,990 --> 00:05:41,350
is to see this.
97
00:05:41,350 --> 00:05:45,900
So we have double integrals
now, that's the difference.
98
00:05:45,900 --> 00:05:51,730
But we're still
integrating Au against w.
99
00:05:51,730 --> 00:05:56,430
So Au is the gradient
of u; w is w_1, w_2,
100
00:05:56,430 --> 00:06:00,000
and this is now for
any u and any w,
101
00:06:00,000 --> 00:06:04,080
so I want the inner product.
102
00:06:04,080 --> 00:06:11,170
Of the gradient of u with any
w, so this is like the Auw part,
103
00:06:11,170 --> 00:06:16,640
so the gradient of u, that
would be a du/dx times the w_1.
104
00:06:16,640 --> 00:06:24,680
And a du/dy times w_2.
dx dy, that would be.
105
00:06:24,680 --> 00:06:28,260
So inner products, if
I'm in two dimensions,
106
00:06:28,260 --> 00:06:30,150
inner products are
integrals, of course,
107
00:06:30,150 --> 00:06:31,870
if I'm dealing with functions.
108
00:06:31,870 --> 00:06:37,560
So this is like
the Au against w.
109
00:06:37,560 --> 00:06:39,240
Inner product.
110
00:06:39,240 --> 00:06:44,070
Au is those two pieces, w is
those, there's the dot product.
111
00:06:44,070 --> 00:06:49,450
And now the key idea behind
what Green's formula is about,
112
00:06:49,450 --> 00:06:55,690
what we use it for in 1-D,
is integration by parts.
113
00:06:55,690 --> 00:06:57,460
So an integration
by parts is going
114
00:06:57,460 --> 00:07:02,230
to produce a double
integral in which-- So I'm
115
00:07:02,230 --> 00:07:05,480
just sort of thinking
through Green's formula.
116
00:07:05,480 --> 00:07:08,620
Of course, we could just say
OK, remember that formula.
117
00:07:08,620 --> 00:07:12,440
But you want to just see it
as an integration by parts.
118
00:07:12,440 --> 00:07:14,504
See how it evolved.
119
00:07:14,504 --> 00:07:15,420
And then we can think.
120
00:07:15,420 --> 00:07:18,560
So I plan to do
integration by parts,
121
00:07:18,560 --> 00:07:23,570
that x derivative will get
taken off of u and put onto w_1.
122
00:07:23,570 --> 00:07:27,410
So I'll have u*dw_1-- Oh,
there'll be a minus right,
123
00:07:27,410 --> 00:07:36,330
from the integration by part.
u will multiply minus dw_1/dx,
124
00:07:36,330 --> 00:07:39,090
so that was this guy
integrated by parts.
125
00:07:39,090 --> 00:07:41,640
Now this one
integrated by parts,
126
00:07:41,640 --> 00:07:46,500
a y derivative is coming
off of u and onto w_2.
127
00:07:46,500 --> 00:07:53,720
So that'll leave me with u times
dw_2/dy with the minus sign.
128
00:07:53,720 --> 00:07:57,370
That comes also from that
integration by parts.
129
00:07:57,370 --> 00:08:00,100
And then there's
the boundary term.
130
00:08:00,100 --> 00:08:04,100
So there's the term which--
Now the boundary of the region
131
00:08:04,100 --> 00:08:07,870
is the curve around it instead
of just the two points.
132
00:08:07,870 --> 00:08:11,590
And what do we see in
the integration by parts?
133
00:08:11,590 --> 00:08:15,090
Well, from the boundary
term we expect a u
134
00:08:15,090 --> 00:08:21,200
and then the key point
is it's w dot n ds.
135
00:08:21,200 --> 00:08:26,340
It's the normal component
of of this vector w.
136
00:08:26,340 --> 00:08:31,850
Because we're looking, well,
that's just what it is.
137
00:08:31,850 --> 00:08:35,720
So that's Green's formula
written out in detail.
138
00:08:35,720 --> 00:08:38,400
And this is the
formula that tells us
139
00:08:38,400 --> 00:08:44,460
that here, if this was
A, A being gradient,
140
00:08:44,460 --> 00:08:50,680
on the left side I'm seeing
grad u in a product with w,
141
00:08:50,680 --> 00:08:55,120
and over here I'm seeing
the inner product of u with,
142
00:08:55,120 --> 00:08:57,460
what's that?
143
00:08:57,460 --> 00:09:00,290
If I look at minus, if I
have this quantity there
144
00:09:00,290 --> 00:09:04,470
that's in parentheses,
what's its name?
145
00:09:04,470 --> 00:09:05,420
It's the divergence.
146
00:09:05,420 --> 00:09:11,680
It's minus the divergence of w.
147
00:09:11,680 --> 00:09:15,620
Plus the boundary term.
148
00:09:15,620 --> 00:09:24,810
So this is why I allowed
myself this gradient transpose
149
00:09:24,810 --> 00:09:29,160
equal minus divergence to see
that if A is the gradient then
150
00:09:29,160 --> 00:09:31,660
A transpose will be
minus the divergence.
151
00:09:31,660 --> 00:09:35,900
And this shows how
that-- just sort of shows
152
00:09:35,900 --> 00:09:39,890
you the integration by
parts that makes that true.
153
00:09:39,890 --> 00:09:51,600
So, you know there's so many
integral formulas in this world
154
00:09:51,600 --> 00:09:52,700
of vector calculus.
155
00:09:52,700 --> 00:09:55,450
But this is like, one to know.
156
00:09:55,450 --> 00:09:58,400
And actually, if
you want to know,
157
00:09:58,400 --> 00:10:01,980
OK what about the details,
where did that come from?
158
00:10:01,980 --> 00:10:04,800
This actually turns
out to be, and the text
159
00:10:04,800 --> 00:10:09,110
will make it clear, is
the divergence theorem.
160
00:10:09,110 --> 00:10:14,490
The divergence theorem gives
us this, this, exactly this,
161
00:10:14,490 --> 00:10:23,220
so the divergence theorem
applied to the vector field u
162
00:10:23,220 --> 00:10:26,070
times w.
163
00:10:26,070 --> 00:10:29,790
It turns out if I apply the
divergence theorem to that,
164
00:10:29,790 --> 00:10:32,870
then I get a whole lot of terms
from the divergence of that,
165
00:10:32,870 --> 00:10:34,610
and they are these.
166
00:10:34,610 --> 00:10:38,270
And then I get this
for the boundary.
167
00:10:38,270 --> 00:10:40,650
The flux out.
168
00:10:40,650 --> 00:10:42,540
OK, so.
169
00:10:42,540 --> 00:10:45,870
I just didn't want to leave the
subject without writing down
170
00:10:45,870 --> 00:10:49,110
the central thing.
171
00:10:49,110 --> 00:10:52,530
What does this tell us, then?
172
00:10:52,530 --> 00:10:55,240
I have a region.
173
00:10:55,240 --> 00:11:03,430
In that region I have Laplace's
equation or Poisson's equation.
174
00:11:03,430 --> 00:11:06,710
Say Poisson.
175
00:11:06,710 --> 00:11:07,700
On the boundary.
176
00:11:07,700 --> 00:11:12,230
Now, this is the final
thing to ask you about.
177
00:11:12,230 --> 00:11:16,470
What are suitable
boundary conditions
178
00:11:16,470 --> 00:11:19,220
for this problem in 2-D?
179
00:11:19,220 --> 00:11:20,200
Right?
180
00:11:20,200 --> 00:11:24,840
In 1-D, by now we know
boundary conditions.
181
00:11:24,840 --> 00:11:26,500
We know the main ones.
182
00:11:26,500 --> 00:11:29,730
There's fixed, where u is given.
183
00:11:29,730 --> 00:11:33,780
Or there's free where
the slope is given.
184
00:11:33,780 --> 00:11:37,270
Now, what do we do here?
185
00:11:37,270 --> 00:11:46,190
So this is where we used to be
in 1-D. That's a straight line.
186
00:11:46,190 --> 00:11:48,890
Not perfectly straight
but anyway, straight line.
187
00:11:48,890 --> 00:11:52,930
So 1-D there are only
two boundary points.
188
00:11:52,930 --> 00:11:56,400
The normal vector goes
that way, and that way.
189
00:11:56,400 --> 00:12:01,510
This is the n in this formula.
190
00:12:01,510 --> 00:12:04,950
I think if I just wrote
ordinary integration
191
00:12:04,950 --> 00:12:07,980
by parts it would
look just the same
192
00:12:07,980 --> 00:12:12,620
and my boundary
reduces to two points.
193
00:12:12,620 --> 00:12:15,940
Here my boundary's the
whole curve around.
194
00:12:15,940 --> 00:12:21,210
So what corresponds to
fixed boundary conditions,
195
00:12:21,210 --> 00:12:23,720
and what corresponds to
free boundary conditions?
196
00:12:23,720 --> 00:12:27,860
So I want the-- What
corresponds to fixed,
197
00:12:27,860 --> 00:12:32,940
those are the ones that
named after Dirichlet.
198
00:12:32,940 --> 00:12:34,110
Other names?
199
00:12:34,110 --> 00:12:37,710
Or the rest will
be free, those are
200
00:12:37,710 --> 00:12:41,420
the ones named after
Neumann, and those
201
00:12:41,420 --> 00:12:49,040
are what we call natural
boundary conditions.
202
00:12:49,040 --> 00:12:53,810
So I haven't-- Just ready
to finish this story here.
203
00:12:53,810 --> 00:12:57,400
What are the possibilities?
204
00:12:57,400 --> 00:13:02,900
Well, in each we could have part
of the boundary could be fixed.
205
00:13:02,900 --> 00:13:05,620
Part could be free.
206
00:13:05,620 --> 00:13:09,250
So fixed would mean say
some other boundary,
207
00:13:09,250 --> 00:13:11,790
let me call this part
of the boundary fixed.
208
00:13:11,790 --> 00:13:15,470
So the temperature,
for example is fixed
209
00:13:15,470 --> 00:13:17,090
on this part of the boundary.
210
00:13:17,090 --> 00:13:20,790
So this would be like, and this
might be the whole boundary.
211
00:13:20,790 --> 00:13:22,250
It might be fixed
on the whole one,
212
00:13:22,250 --> 00:13:24,860
but I'm now allowing
the possibility
213
00:13:24,860 --> 00:13:33,780
that we have here a fixed part
and here we have a free part.
214
00:13:33,780 --> 00:13:39,290
In fluids, here we have
fixed corresponds to,
215
00:13:39,290 --> 00:13:40,860
like, there's some
obstacle there.
216
00:13:40,860 --> 00:13:44,260
Some wall.
217
00:13:44,260 --> 00:13:50,960
Free is where the fluid is
coming in or flowing out.
218
00:13:50,960 --> 00:13:54,190
So there it's a
velocity condition.
219
00:13:54,190 --> 00:13:59,900
OK, so fixed conditions, these
Dirichlet ones, will be like,
220
00:13:59,900 --> 00:14:05,910
tell me what u is, u is given.
221
00:14:05,910 --> 00:14:08,150
On this part.
222
00:14:08,150 --> 00:14:11,780
So on part of the
boundary, or possibly all,
223
00:14:11,780 --> 00:14:15,120
I could be given u=u_0.
224
00:14:15,120 --> 00:14:21,560
It could be zero, as it often
was in 1-D. Often just took u
225
00:14:21,560 --> 00:14:22,660
to be zero.
226
00:14:22,660 --> 00:14:26,290
Now, what I'm asking
maybe for the first time,
227
00:14:26,290 --> 00:14:30,060
is what's the free
boundary conditions?
228
00:14:30,060 --> 00:14:35,200
Do we prescribe w=0 on the
free part of the boundary?
229
00:14:35,200 --> 00:14:38,880
Is w=0 the correct
free condition?
230
00:14:38,880 --> 00:14:41,480
Or w=w_0?
231
00:14:41,480 --> 00:14:45,230
If we wanted to allow
it to be non-zero.
232
00:14:45,230 --> 00:14:49,830
That would sound right, right?
u on one side, w on the other.
233
00:14:49,830 --> 00:14:54,120
But now we're in 2-D.
u is still a scalar.
234
00:14:54,120 --> 00:14:55,430
That's fine.
235
00:14:55,430 --> 00:14:57,580
But w is now a vector.
236
00:14:57,580 --> 00:15:01,840
So if I was to prescribe w
on this part of the boundary,
237
00:15:01,840 --> 00:15:04,550
I'm giving you two
conditions, not one.
238
00:15:04,550 --> 00:15:06,630
And that's not good.
239
00:15:06,630 --> 00:15:09,050
I can't give you more than
one boundary condition.
240
00:15:09,050 --> 00:15:11,380
And the clue is there.
241
00:15:11,380 --> 00:15:16,340
It's w dot n, it's
the outward flow.
242
00:15:16,340 --> 00:15:18,340
That you could prescribe.
243
00:15:18,340 --> 00:15:24,200
You can't say in advance what
the tangential flow should be.
244
00:15:24,200 --> 00:15:30,150
So the free conditions
would be like w dot n,
245
00:15:30,150 --> 00:15:35,810
which is of course,
since w is v,
246
00:15:35,810 --> 00:15:42,210
we have Laplace's equation here
with c=1 in between w and v,
247
00:15:42,210 --> 00:15:49,240
so this is the gradient
of u dot n, grad u dot n,
248
00:15:49,240 --> 00:15:53,450
and it's sometimes written, the
derivative of u in the normal
249
00:15:53,450 --> 00:15:54,960
direction.
250
00:15:54,960 --> 00:15:59,880
And that we can
prescribe as some w_0.
251
00:15:59,880 --> 00:16:05,150
Oh, I don't like to say
w_0 because w_0 makes
252
00:16:05,150 --> 00:16:08,490
it sound like a vector
would be allowed,
253
00:16:08,490 --> 00:16:10,420
and that's the whole point here.
254
00:16:10,420 --> 00:16:15,640
We give one boundary condition;
we either give u or w dot n.
255
00:16:15,640 --> 00:16:26,660
So let me give it some
different name, like F.
256
00:16:26,660 --> 00:16:27,160
So.
257
00:16:27,160 --> 00:16:30,940
I'll just ask one more
question to bring this home.
258
00:16:30,940 --> 00:16:36,130
And then I'll get on to the fun
today of fast Poisson solvers.
259
00:16:36,130 --> 00:16:38,670
260
00:16:38,670 --> 00:16:45,270
What was the deal on in 1-D
when we had free-free boundary
261
00:16:45,270 --> 00:16:46,650
conditions?
262
00:16:46,650 --> 00:16:49,720
What was the deal in one
dimension when we had
263
00:16:49,720 --> 00:16:51,720
free-free boundary conditions?
264
00:16:51,720 --> 00:16:57,700
Both conditions were
slope conditions. u'=0.
265
00:16:57,700 --> 00:17:00,270
What matrix did we get?
266
00:17:00,270 --> 00:17:05,480
What was different about that
matrix, the free-free case?
267
00:17:05,480 --> 00:17:07,730
I'm always looking back
to 1-D because that's
268
00:17:07,730 --> 00:17:10,410
the case we really understood.
269
00:17:10,410 --> 00:17:15,440
What was the the problem
with the free-free matrix?
270
00:17:15,440 --> 00:17:16,580
It was singular.
271
00:17:16,580 --> 00:17:19,400
What was its name?
272
00:17:19,400 --> 00:17:21,640
Was K, was it?
273
00:17:21,640 --> 00:17:27,520
You remember the first day of
class, the unforgettable four
274
00:17:27,520 --> 00:17:30,490
matrices?
275
00:17:30,490 --> 00:17:34,150
So this was fixed-fixed,
fixed-fixed.
276
00:17:34,150 --> 00:17:41,000
This one was, you could tell
me better than I can remember.
277
00:17:41,000 --> 00:17:43,430
T was free-fixed.
278
00:17:43,430 --> 00:17:45,360
And that was still OK.
279
00:17:45,360 --> 00:17:47,510
By OK I mean it was
still invertible.
280
00:17:47,510 --> 00:17:49,660
What was B?
281
00:17:49,660 --> 00:17:51,700
Free-free, that's
what I'm looking at.
282
00:17:51,700 --> 00:17:54,480
And the problem with
free-free-- And then this
283
00:17:54,480 --> 00:17:59,290
was periodic, that's
Fourier stuff that's
284
00:17:59,290 --> 00:18:01,390
the next part of the course.
285
00:18:01,390 --> 00:18:08,250
But the point is that this
free-free was singular.
286
00:18:08,250 --> 00:18:09,320
Right?
287
00:18:09,320 --> 00:18:11,420
And it'll be the same here.
288
00:18:11,420 --> 00:18:15,910
If the whole boundary
is free, then I've
289
00:18:15,910 --> 00:18:18,180
got a singular problem.
290
00:18:18,180 --> 00:18:20,920
If I've got a whole
boundary that's free,
291
00:18:20,920 --> 00:18:23,790
yeah actually I'll
just put it here.
292
00:18:23,790 --> 00:18:34,000
Suppose I have Laplace's
equation, zero,
293
00:18:34,000 --> 00:18:41,280
and suppose I make
the whole all free.
294
00:18:41,280 --> 00:18:47,850
So grad u dot n is zero
on the whole boundary.
295
00:18:47,850 --> 00:18:55,510
So it's like solving Bu=0.
296
00:18:55,510 --> 00:18:58,360
And the point is that
that has solutions.
297
00:18:58,360 --> 00:19:01,320
You remember, what
was in the null space
298
00:19:01,320 --> 00:19:04,020
of B, this free-free case?
299
00:19:04,020 --> 00:19:08,240
Bu=0, for what vector?
300
00:19:08,240 --> 00:19:12,490
Our favorite guilty vector.
301
00:19:12,490 --> 00:19:15,160
It was constants.
302
00:19:15,160 --> 00:19:16,280
Right, all ones.
303
00:19:16,280 --> 00:19:20,000
All constants.
u=1, all constants.
304
00:19:20,000 --> 00:19:23,450
Right, so that was the
free-free case in 1-D. Now,
305
00:19:23,450 --> 00:19:28,560
I just want you to tell me
the same thing over here.
306
00:19:28,560 --> 00:19:32,040
That equation does not
have a unique solution.
307
00:19:32,040 --> 00:19:34,130
So it's a singular problem.
308
00:19:34,130 --> 00:19:38,490
Here's the equation,
something u equals zero,
309
00:19:38,490 --> 00:19:44,990
but you can tell me solutions
to that pure Neumann problem.
310
00:19:44,990 --> 00:19:46,970
That are not zero.
311
00:19:46,970 --> 00:19:52,140
So this is a problem where
there's a null space.
312
00:19:52,140 --> 00:19:54,480
And what is the solution?
313
00:19:54,480 --> 00:19:59,460
What's a solution to this?
314
00:19:59,460 --> 00:20:04,470
To the Laplace's equation
in the inside and slope
315
00:20:04,470 --> 00:20:09,390
zero all around the boundary.
316
00:20:09,390 --> 00:20:12,010
There's a simple
solution to that one,
317
00:20:12,010 --> 00:20:16,020
which is just like this guy.
318
00:20:16,020 --> 00:20:20,240
And do you see what it is?
u equal constant, right.
319
00:20:20,240 --> 00:20:25,730
So u equal constant.
320
00:20:25,730 --> 00:20:30,430
So I'd like you to see the
whole picture connecting
321
00:20:30,430 --> 00:20:34,330
with what we fully
understood in the 1-D case
322
00:20:34,330 --> 00:20:37,090
for those matrices.
323
00:20:37,090 --> 00:20:43,330
We don't expect to be able to
have a pure Neumann problem.
324
00:20:43,330 --> 00:20:45,670
A totally free problem.
325
00:20:45,670 --> 00:20:48,190
Because these, it'll
be singular and we'll
326
00:20:48,190 --> 00:20:51,970
have to do something special.
327
00:20:51,970 --> 00:20:56,830
So the point is that it
would be enough for me just
328
00:20:56,830 --> 00:20:59,280
to fix that little bit.
329
00:20:59,280 --> 00:21:03,210
If I just fix that little bit
and prescribe u=u_0 on a little
330
00:21:03,210 --> 00:21:07,830
bit, I could make
the rest of it free.
331
00:21:07,830 --> 00:21:11,740
But I can't make it all free.
332
00:21:11,740 --> 00:21:12,660
OK.
333
00:21:12,660 --> 00:21:21,680
So those are things which, just
to complete the big picture
334
00:21:21,680 --> 00:21:26,400
of Laplace's equation.
335
00:21:26,400 --> 00:21:29,720
OK, now I'm going
to turn to solving.
336
00:21:29,720 --> 00:21:33,410
So now I want to solve Laplace's
equation and then we'll have,
337
00:21:33,410 --> 00:21:36,390
because we have the
review sessions coming
338
00:21:36,390 --> 00:21:42,630
on Tuesday and Wednesday of the
past, now we're looking future.
339
00:21:42,630 --> 00:21:43,600
Forward.
340
00:21:43,600 --> 00:21:46,700
Ready to look forward.
341
00:21:46,700 --> 00:21:48,370
Laplace's equation.
342
00:21:48,370 --> 00:21:50,170
On a square.
343
00:21:50,170 --> 00:21:52,460
On a square.
344
00:21:52,460 --> 00:21:53,090
OK.
345
00:21:53,090 --> 00:21:57,200
So let me draw this square.
346
00:21:57,200 --> 00:22:02,330
Laplace's equation or
Poisson's equation.
347
00:22:02,330 --> 00:22:03,560
In a square.
348
00:22:03,560 --> 00:22:06,900
OK, I'm going to make it
the boundary conditions--
349
00:22:06,900 --> 00:22:08,230
So I'm going to have a mesh.
350
00:22:08,230 --> 00:22:11,790
This is going to be
finite differences.
351
00:22:11,790 --> 00:22:15,390
Finite differences will
do fine on a square.
352
00:22:15,390 --> 00:22:20,180
As soon as I draw
this curved region,
353
00:22:20,180 --> 00:22:22,980
I better be thinking
about finite elements.
354
00:22:22,980 --> 00:22:27,850
So that's what, today is
the, like, square day.
355
00:22:27,850 --> 00:22:32,250
OK, so square day I could
think of finite differences.
356
00:22:32,250 --> 00:22:40,270
I just draw a mesh,
let's make it small.
357
00:22:40,270 --> 00:22:41,790
So this is all known.
358
00:22:41,790 --> 00:22:47,620
These are all known values,
let me just say u is given.
359
00:22:47,620 --> 00:22:48,420
On the boundary.
360
00:22:48,420 --> 00:22:54,230
I'll do the Dirichlet problem.
361
00:22:54,230 --> 00:22:59,600
So at all these mesh
points, I know u.
362
00:22:59,600 --> 00:23:04,660
And I want to find u inside.
363
00:23:04,660 --> 00:23:06,850
So I've got nine
unknowns, right?
364
00:23:06,850 --> 00:23:08,690
Nine interior mesh points.
365
00:23:08,690 --> 00:23:11,230
Three times three three.
366
00:23:11,230 --> 00:23:14,230
So I've got nine unknowns,
I want nine equations
367
00:23:14,230 --> 00:23:17,300
and I'm thinking here
about difference equations.
368
00:23:17,300 --> 00:23:23,690
So let me write my
equation -u_xx-u_yy=f.
369
00:23:23,690 --> 00:23:30,690
370
00:23:30,690 --> 00:23:35,340
Poisson.
371
00:23:35,340 --> 00:23:38,430
What finite difference--
I want to turn this
372
00:23:38,430 --> 00:23:40,710
into finite differences.
373
00:23:40,710 --> 00:23:47,320
That'll be my system
of nine equations.
374
00:23:47,320 --> 00:23:50,646
And the unknowns will
be the nine values of u,
375
00:23:50,646 --> 00:23:52,840
so these are unknown.
376
00:23:52,840 --> 00:23:53,440
Right?
377
00:23:53,440 --> 00:23:56,080
Those are the unknown.
378
00:23:56,080 --> 00:23:58,990
OK, and I need equations.
379
00:23:58,990 --> 00:24:04,690
So let me take a typical
mesh point, like this one.
380
00:24:04,690 --> 00:24:07,690
I'm looking for the finite
difference approximation
381
00:24:07,690 --> 00:24:09,590
to the Laplacian.
382
00:24:09,590 --> 00:24:13,880
If you give me Laplace's
equation and I say OK,
383
00:24:13,880 --> 00:24:17,270
what's a good finite
difference approximation,
384
00:24:17,270 --> 00:24:20,880
that I can then put in
the computer and solve.
385
00:24:20,880 --> 00:24:22,180
I'm ready to do it.
386
00:24:22,180 --> 00:24:25,650
So what should we
do for this one?
387
00:24:25,650 --> 00:24:27,050
For that term?
388
00:24:27,050 --> 00:24:29,480
What's the natural,
totally natural thing
389
00:24:29,480 --> 00:24:33,800
to do to replace-- the
finite difference replacement
390
00:24:33,800 --> 00:24:36,040
of minus u_xx?
391
00:24:36,040 --> 00:24:37,490
Second differences.
392
00:24:37,490 --> 00:24:38,900
Second differences.
393
00:24:38,900 --> 00:24:43,150
And with the minus sign
there, second differences
394
00:24:43,150 --> 00:24:46,450
around this point will
be a minus one of there,
395
00:24:46,450 --> 00:24:49,490
two of those, a
minus one of those.
396
00:24:49,490 --> 00:24:56,540
That second difference in the
x direction is my replacement.
397
00:24:56,540 --> 00:24:57,900
My approximation.
398
00:24:57,900 --> 00:25:01,460
And what about in
the y direction?
399
00:25:01,460 --> 00:25:02,600
Same thing.
400
00:25:02,600 --> 00:25:05,130
Second differences,
but now vertically.
401
00:25:05,130 --> 00:25:07,900
So now I have minus
one, two more,
402
00:25:07,900 --> 00:25:10,080
that makes this guy a four.
403
00:25:10,080 --> 00:25:12,810
And this is minus one.
404
00:25:12,810 --> 00:25:15,280
And on the right hand
side, I'll take the value
405
00:25:15,280 --> 00:25:18,330
of f at the center point.
406
00:25:18,330 --> 00:25:22,360
Do you see that molecule?
407
00:25:22,360 --> 00:25:26,650
Let me highlight
the molecule there.
408
00:25:26,650 --> 00:25:30,770
Four in the center,
minus ones beside it.
409
00:25:30,770 --> 00:25:37,740
Our matrix, we're going
to produce a KU=f matrix,
410
00:25:37,740 --> 00:25:39,360
and what's the K going to be?
411
00:25:39,360 --> 00:25:40,400
It's K2D.
412
00:25:40,400 --> 00:25:41,940
Let's give a name.
413
00:25:41,940 --> 00:25:43,450
A new name.
414
00:25:43,450 --> 00:25:44,710
We've had K forever.
415
00:25:44,710 --> 00:25:45,500
Let's have K2D.
416
00:25:45,500 --> 00:25:48,460
417
00:25:48,460 --> 00:25:52,220
And u is, so tell me now
again just so we got,
418
00:25:52,220 --> 00:25:56,160
what size is K2D for
this particular problem?
419
00:25:56,160 --> 00:25:59,250
What's the shape of it?
420
00:25:59,250 --> 00:26:02,950
How many unknowns
have I got in u?
421
00:26:02,950 --> 00:26:04,000
Nine.
422
00:26:04,000 --> 00:26:06,080
Nine unknowns.
423
00:26:06,080 --> 00:26:13,080
And notice, of course,
near the boundary,
424
00:26:13,080 --> 00:26:16,080
if this was the-- Well
let me take the first one.
425
00:26:16,080 --> 00:26:19,120
What does the very first
row of K look like?
426
00:26:19,120 --> 00:26:20,880
If I number nodes like this.
427
00:26:20,880 --> 00:26:24,830
So this will be node number one,
two, three, four, five, six,
428
00:26:24,830 --> 00:26:27,370
seven, eight, nine.
429
00:26:27,370 --> 00:26:31,220
So number one is sort
of close to a boundary.
430
00:26:31,220 --> 00:26:36,410
So I have here a minus one,
a two, and this is gone.
431
00:26:36,410 --> 00:26:40,810
That's like a column
of our matrix removed.
432
00:26:40,810 --> 00:26:43,080
Like a grounded
node, or whatever.
433
00:26:43,080 --> 00:26:46,520
But then I have the
vertical one minus one, two,
434
00:26:46,520 --> 00:26:49,070
making this into a four.
435
00:26:49,070 --> 00:26:52,320
And this guy will
also be removed.
436
00:26:52,320 --> 00:26:57,670
So I think if I look at
K2D, it's nine by nine.
437
00:26:57,670 --> 00:27:01,640
I don't plan to
write all 81 entries.
438
00:27:01,640 --> 00:27:04,040
But I could write the first row.
439
00:27:04,040 --> 00:27:09,150
The first row comes
from the first equation.
440
00:27:09,150 --> 00:27:12,520
So the first row has an
f_1 on the right hand
441
00:27:12,520 --> 00:27:14,510
side, f at this point.
442
00:27:14,510 --> 00:27:17,070
And what do you see,
what's on the diagonal?
443
00:27:17,070 --> 00:27:19,140
Of K2D?
444
00:27:19,140 --> 00:27:20,790
Four.
445
00:27:20,790 --> 00:27:25,100
And what's the rest of the row?
446
00:27:25,100 --> 00:27:30,200
Well there's the next point
and it has a minus one.
447
00:27:30,200 --> 00:27:33,050
And then this point is
not connected to that,
448
00:27:33,050 --> 00:27:33,870
so it's a zero.
449
00:27:33,870 --> 00:27:37,340
I'd better leave room
for nine by nine here.
450
00:27:37,340 --> 00:27:40,510
Four, minus one, zero.
451
00:27:40,510 --> 00:27:45,480
And now what about number,
the rest of the row?
452
00:27:45,480 --> 00:27:49,980
So there's four is the
center, minus one, zero.
453
00:27:49,980 --> 00:27:51,720
And now I come to
here, so what's
454
00:27:51,720 --> 00:27:54,060
the next entry in my matrix?
455
00:27:54,060 --> 00:27:55,310
Minus one.
456
00:27:55,310 --> 00:27:59,080
We're multiplying the
unknown, the fourth unknown.
457
00:27:59,080 --> 00:28:02,780
And what about the
rest of the row?
458
00:28:02,780 --> 00:28:05,610
This guy is not connected
to five, six, seven, eight,
459
00:28:05,610 --> 00:28:06,110
or nine.
460
00:28:06,110 --> 00:28:11,040
So now I have zero,
zero, zero, zero, zero.
461
00:28:11,040 --> 00:28:13,250
OK.
462
00:28:13,250 --> 00:28:16,120
So that would be
a row, that would
463
00:28:16,120 --> 00:28:19,390
be a row that's sort
of different because it
464
00:28:19,390 --> 00:28:21,680
corresponds to a
mesh point that's
465
00:28:21,680 --> 00:28:23,510
way over near the corner.
466
00:28:23,510 --> 00:28:25,260
How about the fifth row?
467
00:28:25,260 --> 00:28:30,240
What would be the fifth row of
K2D corresponding to this guy
468
00:28:30,240 --> 00:28:33,320
that's right in the middle?
469
00:28:33,320 --> 00:28:39,140
What's on the diagonal,
what's the 5, 5 entry of K2D?
470
00:28:39,140 --> 00:28:39,701
Four.
471
00:28:39,701 --> 00:28:40,200
Good.
472
00:28:40,200 --> 00:28:42,530
I'm going to have a
diagonal of fours.
473
00:28:42,530 --> 00:28:45,020
I'm going to have fours all
the way down the diagonal.
474
00:28:45,020 --> 00:28:48,290
Because every point
the molecule is
475
00:28:48,290 --> 00:28:52,150
centered at gives me the four,
and I just have a minus one
476
00:28:52,150 --> 00:28:53,460
for its neighbor.
477
00:28:53,460 --> 00:28:56,210
And this guy has
all four neighbors.
478
00:28:56,210 --> 00:29:02,140
They're all alive and
well, so there's a guy,
479
00:29:02,140 --> 00:29:03,940
this is the fifth row.
480
00:29:03,940 --> 00:29:06,300
There's somebody right
next door on the left.
481
00:29:06,300 --> 00:29:08,700
Somebody right next
door on the right.
482
00:29:08,700 --> 00:29:15,950
And then do the other
minus ones go after that?
483
00:29:15,950 --> 00:29:17,000
This is the whole point.
484
00:29:17,000 --> 00:29:21,200
I want you to see how
this K2D matrix looks.
485
00:29:21,200 --> 00:29:24,600
Because it's the one, it's
the equation we have to solve.
486
00:29:24,600 --> 00:29:27,450
So we've got to know what
this matrix looks like.
487
00:29:27,450 --> 00:29:29,030
So what's the point here?
488
00:29:29,030 --> 00:29:30,960
Four, it's got a neighbor there.
489
00:29:30,960 --> 00:29:34,090
This was unknown number five.
490
00:29:34,090 --> 00:29:36,920
It's fourth unknown
and the sixth unknown,
491
00:29:36,920 --> 00:29:39,120
what are the numbers
of these unknowns?
492
00:29:39,120 --> 00:29:43,110
Two and eight.
493
00:29:43,110 --> 00:29:48,440
So this guy is going to have a
minus one in the two position.
494
00:29:48,440 --> 00:29:49,920
And then zero.
495
00:29:49,920 --> 00:29:54,510
And this guy, it'll also have
a minus one, is that nine?
496
00:29:54,510 --> 00:29:56,410
Yeah, do you see how it's going?
497
00:29:56,410 --> 00:30:03,450
I have a diagonal, I have
five diagonals somehow.
498
00:30:03,450 --> 00:30:06,470
I have diagonal, the
neighbor on the left,
499
00:30:06,470 --> 00:30:09,390
the neighbor on the right,
the neighbor underneath,
500
00:30:09,390 --> 00:30:12,630
and the neighbor above.
501
00:30:12,630 --> 00:30:17,380
Across the street you could say.
502
00:30:17,380 --> 00:30:20,990
So our matrix, this
very important matrix,
503
00:30:20,990 --> 00:30:24,270
more attention has
gone into how to solve
504
00:30:24,270 --> 00:30:30,320
this equation for that matrix
than any other single specific
505
00:30:30,320 --> 00:30:33,340
example in numerical analysis.
506
00:30:33,340 --> 00:30:36,700
It's just a model problem.
507
00:30:36,700 --> 00:30:40,190
And what do I notice
about this matrix?
508
00:30:40,190 --> 00:30:44,780
So now you see it's
got five diagonals.
509
00:30:44,780 --> 00:30:48,740
But, and what's the big but?
510
00:30:48,740 --> 00:30:53,000
The big but is that those
five diagonals don't run,
511
00:30:53,000 --> 00:30:58,290
it's not just a band
of five because you
512
00:30:58,290 --> 00:31:02,370
don't get to the one
up above until you've
513
00:31:02,370 --> 00:31:09,470
gone all the way-- You
see the bandwidth is big.
514
00:31:09,470 --> 00:31:16,080
If my matrix-- If this is one,
two up to n, and this is one,
515
00:31:16,080 --> 00:31:22,050
two up to n, then how
many unknowns have I got?
516
00:31:22,050 --> 00:31:23,600
Just think big now.
517
00:31:23,600 --> 00:31:27,500
We're in 2-D, think 2-D. How
many unknowns have I got?
518
00:31:27,500 --> 00:31:31,870
N was three in the
picture, but now you're
519
00:31:31,870 --> 00:31:34,760
kind of visualizing
a much finer grid.
520
00:31:34,760 --> 00:31:36,570
How many unknowns?
521
00:31:36,570 --> 00:31:38,730
N squared unknowns, right?
522
00:31:38,730 --> 00:31:40,470
One to N in each direction.
523
00:31:40,470 --> 00:31:43,620
So we've got the matrix
of size N squared.
524
00:31:43,620 --> 00:31:46,240
Way bigger, way bigger.
525
00:31:46,240 --> 00:31:50,780
I mean if N was ten, our
matrix is of size 100.
526
00:31:50,780 --> 00:31:54,840
And of course, that's
completely simple.
527
00:31:54,840 --> 00:31:58,770
The real question is when N
becomes 1,000 and our matrix
528
00:31:58,770 --> 00:32:00,680
is of size a million.
529
00:32:00,680 --> 00:32:02,990
And those get solved every day.
530
00:32:02,990 --> 00:32:05,940
So, question is how.
531
00:32:05,940 --> 00:32:10,150
Actually this, for a
million by million matrix,
532
00:32:10,150 --> 00:32:15,650
this fast Poisson solver that I
want to describe does it great.
533
00:32:15,650 --> 00:32:21,340
Actually, so you can deal with
a matrix of order a million
534
00:32:21,340 --> 00:32:23,130
without turning a hair.
535
00:32:23,130 --> 00:32:25,670
OK now, but can we
understand that matrix?
536
00:32:25,670 --> 00:32:29,580
So suppose N is 100.
537
00:32:29,580 --> 00:32:33,830
Just to have us--
What's the story?
538
00:32:33,830 --> 00:32:35,100
This matrix, then.
539
00:32:35,100 --> 00:32:37,250
What's the size of that matrix?
540
00:32:37,250 --> 00:32:39,160
Did I say 100?
541
00:32:39,160 --> 00:32:43,500
Or 1,000, do you want
to think really big?
542
00:32:43,500 --> 00:32:44,870
I guess I said 1,000.
543
00:32:44,870 --> 00:32:47,430
To get up to a million.
544
00:32:47,430 --> 00:32:50,390
OK, so N is 1,000,
so we have a 1,000
545
00:32:50,390 --> 00:32:52,940
by 1,000, a million unknowns.
546
00:32:52,940 --> 00:32:56,550
My matrix is a
million by a million.
547
00:32:56,550 --> 00:32:57,510
Let me ask you this.
548
00:32:57,510 --> 00:32:59,840
Here's the question
that I want to ask you.
549
00:32:59,840 --> 00:33:01,770
What's the bandwidth?
550
00:33:01,770 --> 00:33:09,900
How far from the main
diagonal out to the last-- out
551
00:33:09,900 --> 00:33:12,020
to that minus one.
552
00:33:12,020 --> 00:33:18,920
In other words, this is really
the full band of the matrix.
553
00:33:18,920 --> 00:33:22,470
It's got a lot of
zeroes inside the band.
554
00:33:22,470 --> 00:33:23,270
A whole bunch.
555
00:33:23,270 --> 00:33:28,630
Maybe 990 something
zeroes in here.
556
00:33:28,630 --> 00:33:34,890
And in here, and how far
is it from here to here?
557
00:33:34,890 --> 00:33:36,450
1,000, right?
558
00:33:36,450 --> 00:33:38,080
It's 1,000.
559
00:33:38,080 --> 00:33:40,430
So the bandwidth is 1,000.
560
00:33:40,430 --> 00:33:46,700
And what if I do
ordinary, so now I
561
00:33:46,700 --> 00:33:50,120
want to begin to think how
do I solve this equation?
562
00:33:50,120 --> 00:33:52,110
How do I work with that matrix?
563
00:33:52,110 --> 00:33:54,780
And you have an
idea of that matrix?
564
00:33:54,780 --> 00:33:58,140
It's a beautiful
matrix to work with.
565
00:33:58,140 --> 00:34:01,980
It's very like
our K matrix; it's
566
00:34:01,980 --> 00:34:07,730
just up to 2-D. In fact, it's
closely connected to our-- K2D
567
00:34:07,730 --> 00:34:09,870
will be closely
connected to K and that's
568
00:34:09,870 --> 00:34:13,850
what makes life possible here.
569
00:34:13,850 --> 00:34:21,250
But suppose I had to
solve this equation.
570
00:34:21,250 --> 00:34:25,600
Alright, so I give it to MATLAB
just as a system of equations.
571
00:34:25,600 --> 00:34:27,820
A million equations,
a million unknowns.
572
00:34:27,820 --> 00:34:32,580
So MATLAB takes a gulp
and then it tries, OK?
573
00:34:32,580 --> 00:34:37,040
So ordinary elimination,
that's what backslash does.
574
00:34:37,040 --> 00:34:40,440
By the way this
matrix is symmetric,
575
00:34:40,440 --> 00:34:43,500
and, you won't be surprised,
it's positive definite.
576
00:34:43,500 --> 00:34:46,540
Everything is nice
about that matrix.
577
00:34:46,540 --> 00:34:49,940
In fact more than I've said.
578
00:34:49,940 --> 00:34:56,400
OK, what happens if I do
elimination on that matrix?
579
00:34:56,400 --> 00:34:59,950
How long does it
take, how fast is it?
580
00:34:59,950 --> 00:35:03,750
Well, MATLAB will take
advantage, or any code,
581
00:35:03,750 --> 00:35:10,610
will take advantage of
all these zeroes, right?
582
00:35:10,610 --> 00:35:14,040
In other words, what do
I mean by take advantage?
583
00:35:14,040 --> 00:35:15,670
And what do I mean
by elimination?
584
00:35:15,670 --> 00:35:19,290
You remember I'm going to
subtract multiples of this row.
585
00:35:19,290 --> 00:35:24,370
There'll be a minus one
below it on this guy.
586
00:35:24,370 --> 00:35:29,590
This row that has some fours
and some minus ones, whatever.
587
00:35:29,590 --> 00:35:32,900
Elimination, I'm subtracting
a multiple of this row
588
00:35:32,900 --> 00:35:37,470
from this row to get that
minus one to be a zero, right?
589
00:35:37,470 --> 00:35:40,440
I'm eliminating this
entry in the matrix.
590
00:35:40,440 --> 00:35:47,580
This is ordinary LU, this
is ordinary LU of K2D.
591
00:35:47,580 --> 00:35:51,210
I'm sort of thinking
through LU of K2D.
592
00:35:51,210 --> 00:35:54,180
And what I'm going to
conclude is that there
593
00:35:54,180 --> 00:35:56,040
ought to be a better way.
594
00:35:56,040 --> 00:35:58,560
It's such a special
matrix, and it's
595
00:35:58,560 --> 00:36:00,490
going to be messed up by LU.
596
00:36:00,490 --> 00:36:02,470
And what do I mean by messed up?
597
00:36:02,470 --> 00:36:08,730
I mean that all these great
zeroes, 990-something zeroes
598
00:36:08,730 --> 00:36:16,950
there and there, inside the
band, are going to fill in.
599
00:36:16,950 --> 00:36:19,670
That's the message,
if you want to talk
600
00:36:19,670 --> 00:36:23,660
about solving large
linear systems,
601
00:36:23,660 --> 00:36:27,560
the big issue is fill in.
602
00:36:27,560 --> 00:36:29,200
It's a sparse matrix.
603
00:36:29,200 --> 00:36:30,490
That's typical.
604
00:36:30,490 --> 00:36:33,650
We have a local operator
here, so we expect
605
00:36:33,650 --> 00:36:36,080
a very local, sparse matrix.
606
00:36:36,080 --> 00:36:39,560
Large sparse matrices
is what we're doing now.
607
00:36:39,560 --> 00:36:44,860
And the problem is that--
Zeroes here will never
608
00:36:44,860 --> 00:36:48,290
get touched because we
don't need any elimination,
609
00:36:48,290 --> 00:36:49,630
they're already zero.
610
00:36:49,630 --> 00:36:54,680
But all this diagonal
of minus ones when we do
611
00:36:54,680 --> 00:36:57,740
eliminations to make
those zero, then
612
00:36:57,740 --> 00:37:03,920
some non-zeroes are going to
come in and fill in the zeroes.
613
00:37:03,920 --> 00:37:07,720
So the work, how much work
would elimination be, actually?
614
00:37:07,720 --> 00:37:15,540
We could even think about that.
615
00:37:15,540 --> 00:37:19,910
Can I just give the result for
how much time would elimination
616
00:37:19,910 --> 00:37:20,970
take?
617
00:37:20,970 --> 00:37:22,540
Ordinary elimination.
618
00:37:22,540 --> 00:37:28,320
So I have N squared
rows to work on.
619
00:37:28,320 --> 00:37:33,420
N squared rows to work
on, and then the distance,
620
00:37:33,420 --> 00:37:36,680
that distance was
what in terms of N?
621
00:37:36,680 --> 00:37:38,330
The width there is?
622
00:37:38,330 --> 00:37:39,990
N, right?
623
00:37:39,990 --> 00:37:41,660
It was about 1,000.
624
00:37:41,660 --> 00:37:46,590
So I get N numbers here and
I have to work on N numbers
625
00:37:46,590 --> 00:37:52,540
below.
626
00:37:52,540 --> 00:37:56,990
To clean up a column I'm working
with a vector of length N
627
00:37:56,990 --> 00:38:01,670
and I'm subtracting
it from N rows below.
628
00:38:01,670 --> 00:38:05,620
So cleaning up a column
takes me N squared operation.
629
00:38:05,620 --> 00:38:10,150
The total then is N^4.
630
00:38:10,150 --> 00:38:14,370
N^4, for elimination.
631
00:38:14,370 --> 00:38:16,170
And that's not acceptable.
632
00:38:16,170 --> 00:38:16,730
Right?
633
00:38:16,730 --> 00:38:20,970
If N is 1,000, I'm up to 10^12.
634
00:38:20,970 --> 00:38:28,110
So elimination is not a good
way to solve-- Elimination,
635
00:38:28,110 --> 00:38:30,830
in this ordering, ha.
636
00:38:30,830 --> 00:38:31,650
Yeah.
637
00:38:31,650 --> 00:38:36,520
So can I tell you two
ways, two better ways
638
00:38:36,520 --> 00:38:39,590
to deal with this problem?
639
00:38:39,590 --> 00:38:42,930
So two better ways to
deal with this problem.
640
00:38:42,930 --> 00:38:49,600
One is, and MATLAB have
a code that would do it,
641
00:38:49,600 --> 00:38:54,930
one is to change from this
ordering one, two, three, four,
642
00:38:54,930 --> 00:39:00,020
five, six, seven, eight, nine,
change to a different ordering
643
00:39:00,020 --> 00:39:03,360
that had less fill-in.
644
00:39:03,360 --> 00:39:09,550
So that's a substantial part
of scientific computing.
645
00:39:09,550 --> 00:39:15,340
Is to re-order the unknowns.
646
00:39:15,340 --> 00:39:20,687
To reduce the number of
wasted, fill-in things
647
00:39:20,687 --> 00:39:22,270
that you have to
fill in, and then you
648
00:39:22,270 --> 00:39:25,080
have to eliminate out again.
649
00:39:25,080 --> 00:39:29,990
And I can get that N^4
down quite a bit that way.
650
00:39:29,990 --> 00:39:34,090
OK, so that's a
topic of importance
651
00:39:34,090 --> 00:39:37,470
in scientific computing.
652
00:39:37,470 --> 00:39:42,790
Is given a large linear system,
put the rows and columns
653
00:39:42,790 --> 00:39:44,260
in a good order.
654
00:39:44,260 --> 00:39:47,330
OK, and that's something
you hope the machine can do.
655
00:39:47,330 --> 00:39:53,030
The machine will have a record
of where are the non-zeroes.
656
00:39:53,030 --> 00:39:55,400
And then so you run
the little, you really
657
00:39:55,400 --> 00:39:57,080
run the program twice.
658
00:39:57,080 --> 00:40:00,690
You run it once without
using the numbers.
659
00:40:00,690 --> 00:40:04,220
Just the positions of
non-zeroes to get a good
660
00:40:04,220 --> 00:40:08,310
ordering so that the
number of elimination steps
661
00:40:08,310 --> 00:40:09,920
will be way down.
662
00:40:09,920 --> 00:40:13,500
And then you run it with the
numbers in that good order
663
00:40:13,500 --> 00:40:15,340
to do the elimination.
664
00:40:15,340 --> 00:40:21,190
So that's a topic of,
one topic in this.
665
00:40:21,190 --> 00:40:23,440
But.
666
00:40:23,440 --> 00:40:31,310
Today's topic is using the
fact that this is a square.
667
00:40:31,310 --> 00:40:34,290
That this matrix
has a special form.
668
00:40:34,290 --> 00:40:38,150
That we can actually find its
eigenvalues and eigenvectors.
669
00:40:38,150 --> 00:40:41,270
And that's what makes
a fast Poisson solver.
670
00:40:41,270 --> 00:40:44,020
So that's the topic
of the lecture
671
00:40:44,020 --> 00:40:46,820
and the topic of the
next section in the book.
672
00:40:46,820 --> 00:40:49,430
And I will get
started on it now,
673
00:40:49,430 --> 00:40:52,750
and then complete it Wednesday.
674
00:40:52,750 --> 00:40:58,060
So I want to take this
particular K2D for a square
675
00:40:58,060 --> 00:41:05,120
and show a different way to
solve the equations that uses
676
00:41:05,120 --> 00:41:06,880
the fast Fourier transform.
677
00:41:06,880 --> 00:41:14,550
When I see, when you see, a
regular mesh, regular numbers,
678
00:41:14,550 --> 00:41:19,440
nothing varying,
constant diagonals,
679
00:41:19,440 --> 00:41:21,480
think fast Fourier transform.
680
00:41:21,480 --> 00:41:23,600
The FFT has got
a chance when you
681
00:41:23,600 --> 00:41:25,860
have matrices like this one.
682
00:41:25,860 --> 00:41:32,630
And this I want to
show you how it works.
683
00:41:32,630 --> 00:41:34,880
I want to show you
the underlying idea,
684
00:41:34,880 --> 00:41:37,470
and then we'll see the
details of the fast Fourier
685
00:41:37,470 --> 00:41:40,180
transform in the
Fourier section.
686
00:41:40,180 --> 00:41:42,540
So, of course, everybody
knows the third part
687
00:41:42,540 --> 00:41:46,470
of this course, which
is coming up next week,
688
00:41:46,470 --> 00:41:51,600
we'll be well into it,
is the Fourier part.
689
00:41:51,600 --> 00:41:52,200
OK.
690
00:41:52,200 --> 00:41:54,600
But I can give
you, because we've
691
00:41:54,600 --> 00:41:58,000
seen the eigenvectors
and eigenvalues of K,
692
00:41:58,000 --> 00:42:00,670
I can do this now.
693
00:42:00,670 --> 00:42:04,590
Ready for the smart idea?
694
00:42:04,590 --> 00:42:07,250
The good way, and it
only works because this
695
00:42:07,250 --> 00:42:10,370
is a square, because the
coefficients are constant,
696
00:42:10,370 --> 00:42:14,460
because everything's
beautiful, here's the idea.
697
00:42:14,460 --> 00:42:16,620
OK.
698
00:42:16,620 --> 00:42:26,340
Central idea.
699
00:42:26,340 --> 00:42:31,370
The idea is, so I
have this matrix K2D
700
00:42:31,370 --> 00:42:35,610
and I'm trying to solve a system
with that particular matrix.
701
00:42:35,610 --> 00:42:38,250
And the fantastic
thing about this matrix
702
00:42:38,250 --> 00:42:43,810
is that I know what its
eigenvalues and eigenvectors
703
00:42:43,810 --> 00:42:44,470
are.
704
00:42:44,470 --> 00:42:47,070
So let's suppose we know them.
705
00:42:47,070 --> 00:42:55,040
So I know (K2D)y = lambda*y.
706
00:42:55,040 --> 00:42:57,140
y is an eigenvector,
and remember
707
00:42:57,140 --> 00:42:59,430
it's got N squared components.
708
00:42:59,430 --> 00:43:01,420
Lambda's a number.
709
00:43:01,420 --> 00:43:07,710
And I've got a whole lot of
these, y_k, lambda_k, y_k.
710
00:43:07,710 --> 00:43:16,850
And I've got k going
from one up to N squared.
711
00:43:16,850 --> 00:43:19,340
Now I want to use them.
712
00:43:19,340 --> 00:43:23,330
I want to use them
to solve (K2D)u=f.
713
00:43:23,330 --> 00:43:27,900
714
00:43:27,900 --> 00:43:33,820
Let me say, it's totally
amazing that I would,
715
00:43:33,820 --> 00:43:36,400
in fact this is the only
important example I know
716
00:43:36,400 --> 00:43:40,580
in scientific computing,
in which I would use
717
00:43:40,580 --> 00:43:43,760
the eigenvalues and
eigenvectors of the matrix
718
00:43:43,760 --> 00:43:46,020
to solve a linear system.
719
00:43:46,020 --> 00:43:49,020
You see, normally you think of
eigenvalue problems as like,
720
00:43:49,020 --> 00:43:51,350
those are harder.
721
00:43:51,350 --> 00:43:55,780
It's more difficult to solve
this problem than this one.
722
00:43:55,780 --> 00:43:56,700
Normally, right?
723
00:43:56,700 --> 00:43:59,670
That's the way to
think about it.
724
00:43:59,670 --> 00:44:06,720
But for this special
matrix, we can figure out
725
00:44:06,720 --> 00:44:10,690
the eigenvalues and eigenvectors
by pencil and paper.
726
00:44:10,690 --> 00:44:14,640
So we know what these guys are.
727
00:44:14,640 --> 00:44:20,120
And that will give us a way
to solve a linear system.
728
00:44:20,120 --> 00:44:24,800
So can I remember, this
is now central message.
729
00:44:24,800 --> 00:44:33,160
What are the three steps
that to use eigenvectors
730
00:44:33,160 --> 00:44:39,130
and eigenvalues in
solving linear equations,
731
00:44:39,130 --> 00:44:42,180
in solving differential
equations, in solving
732
00:44:42,180 --> 00:44:46,080
difference equations, they're
always the same three steps.
733
00:44:46,080 --> 00:44:49,280
Can I remember what
those three steps are?
734
00:44:49,280 --> 00:44:56,360
So step one, so I'm supposing
that I know these guys.
735
00:44:56,360 --> 00:44:57,900
First of all, that's amazing.
736
00:44:57,900 --> 00:44:59,680
To know them in advance.
737
00:44:59,680 --> 00:45:01,830
And the second amazing
thing is that they
738
00:45:01,830 --> 00:45:04,490
have beautiful structure.
739
00:45:04,490 --> 00:45:08,280
And those facts make it
possible to do something
740
00:45:08,280 --> 00:45:10,140
you would never expect to do.
741
00:45:10,140 --> 00:45:12,320
Use eigenvalues for
a linear system.
742
00:45:12,320 --> 00:45:14,550
So here's the way to
do it, three steps.
743
00:45:14,550 --> 00:45:23,130
One, expand f as a combination
of the eigenvectors, c_1*y_1,
744
00:45:23,130 --> 00:45:27,620
up to however many we've got.
745
00:45:27,620 --> 00:45:30,000
We've got N squared of them.
746
00:45:30,000 --> 00:45:33,670
Gosh, we're loaded
with eigenvectors.
747
00:45:33,670 --> 00:45:41,270
Do you remember, this a
column of size N squared.
748
00:45:41,270 --> 00:45:43,530
Our problem has size N squared.
749
00:45:43,530 --> 00:45:45,940
So it's big, a million.
750
00:45:45,940 --> 00:45:50,090
So I'm going to expand f
in terms of the million
751
00:45:50,090 --> 00:45:52,660
eigenvectors.
752
00:45:52,660 --> 00:45:54,170
OK.
753
00:45:54,170 --> 00:45:56,530
So that tells me
the right hand side.
754
00:45:56,530 --> 00:46:01,250
Now, you remember step two in
this one, two, three process?
755
00:46:01,250 --> 00:46:05,170
Step two is the easy
one, because I want
756
00:46:05,170 --> 00:46:06,890
to get, what am I looking for?
757
00:46:06,890 --> 00:46:10,690
I'm aiming for, of course,
the answer I'm aiming for
758
00:46:10,690 --> 00:46:15,930
is K2D inverse f.
759
00:46:15,930 --> 00:46:16,430
Right?
760
00:46:16,430 --> 00:46:17,930
That's what I'm shooting for.
761
00:46:17,930 --> 00:46:22,150
That's my goal,
that's the solution.
762
00:46:22,150 --> 00:46:27,100
So here I've got f in
terms of the eigenvectors.
763
00:46:27,100 --> 00:46:32,950
Now I want to get, how do I get
u in terms of the eigenvectors?
764
00:46:32,950 --> 00:46:39,740
Well, what's the eigenvalue for
the inverse, for K2D inverse?
765
00:46:39,740 --> 00:46:42,050
Do you remember?
766
00:46:42,050 --> 00:46:43,800
It's one over.
767
00:46:43,800 --> 00:46:45,530
It's one over the
eigenvalue, right?
768
00:46:45,530 --> 00:46:53,090
If this is true, then this will
be true with lambda_k inverse.
769
00:46:53,090 --> 00:46:55,390
It's simple and I
won't stop to do it,
770
00:46:55,390 --> 00:46:57,660
but we could come back to it.
771
00:46:57,660 --> 00:47:01,630
So I know how to
get K2D inverse.
772
00:47:01,630 --> 00:47:03,340
So that's what I'm going to do.
773
00:47:03,340 --> 00:47:06,860
I'm going to divide, so
here's the fast step.
774
00:47:06,860 --> 00:47:14,370
Divide c_k, each of
those c_k's, by lambda_k.
775
00:47:14,370 --> 00:47:17,440
776
00:47:17,440 --> 00:47:18,730
What do I have now?
777
00:47:18,730 --> 00:47:26,730
I've got c_1/lambda_1*y_1
plus c_(N squared),
778
00:47:26,730 --> 00:47:30,700
the last guy divided by
its eigenvalue times its
779
00:47:30,700 --> 00:47:34,960
eigenvector.
780
00:47:34,960 --> 00:47:37,460
And that's the answer.
781
00:47:37,460 --> 00:47:40,300
Right, that's the
correct answer.
782
00:47:40,300 --> 00:47:45,320
If this is the right hand side,
then this is the solution.
783
00:47:45,320 --> 00:47:46,640
Because why?
784
00:47:46,640 --> 00:47:50,400
Because when I multiply
this solution by K2D
785
00:47:50,400 --> 00:47:53,570
it multiplies every
eigenvector by the eigenvalue,
786
00:47:53,570 --> 00:47:57,030
it cancels all the
lambdas, and I get f.
787
00:47:57,030 --> 00:48:01,570
Do you see-- I can't raise
that board, I'm sorry.
788
00:48:01,570 --> 00:48:04,820
Can you see it at the back?
789
00:48:04,820 --> 00:48:08,310
Should I write it up here
again, because everything
790
00:48:08,310 --> 00:48:09,960
hinges on that.
791
00:48:09,960 --> 00:48:16,620
The final, the answer
u, the K2D inverse f,
792
00:48:16,620 --> 00:48:20,550
is the same combination
that gave f.
793
00:48:20,550 --> 00:48:26,290
But I divide by lambda_1,
c_2 y, the second eigenvector
794
00:48:26,290 --> 00:48:28,750
over lambda_2 and so on.
795
00:48:28,750 --> 00:48:34,440
Because when I multiply by
K2D, multiplying each y,
796
00:48:34,440 --> 00:48:36,570
each eigenvector will
bring out an eigenvalue,
797
00:48:36,570 --> 00:48:41,800
it will cancel that and
I'll have the original f.
798
00:48:41,800 --> 00:48:45,040
So do you see that
those are the steps?
799
00:48:45,040 --> 00:48:49,460
The steps are, you have to
do a-- you could say it's
800
00:48:49,460 --> 00:48:52,130
a transform into eigenspace.
801
00:48:52,130 --> 00:48:55,140
I take my vector
in physical space,
802
00:48:55,140 --> 00:48:57,690
it's got its N
squared component.
803
00:48:57,690 --> 00:49:01,320
At physical points.
804
00:49:01,320 --> 00:49:03,780
I express it in eigenspace.
805
00:49:03,780 --> 00:49:06,970
By that I mean it's a
combination of the eigenvectors
806
00:49:06,970 --> 00:49:09,980
and now the N squared
physical values
807
00:49:09,980 --> 00:49:18,170
are N squared amplitudes, or
amounts of each eigenvector.
808
00:49:18,170 --> 00:49:21,850
So that was a, that's the
Fourier series idea, that's
809
00:49:21,850 --> 00:49:26,260
the Fourier transform idea,
it just appears everywhere.
810
00:49:26,260 --> 00:49:30,200
Express the function
in the good basis.
811
00:49:30,200 --> 00:49:32,170
We're using these
good functions.
812
00:49:32,170 --> 00:49:35,430
In these good functions,
the answer is simple.
813
00:49:35,430 --> 00:49:38,440
I'm just dividing by lambda.
814
00:49:38,440 --> 00:49:40,660
Do you see that I'm just
dividing by lambda, where
815
00:49:40,660 --> 00:49:42,430
if it was a
differential equation--
816
00:49:42,430 --> 00:49:45,120
This is just what we did
for differential equations.
817
00:49:45,120 --> 00:49:49,060
What did I do for
differential equations?
818
00:49:49,060 --> 00:49:51,640
Do you mind if I just ask you?
819
00:49:51,640 --> 00:50:01,460
If I was solving
dU/dt=(K2D)U. Starting from f,
820
00:50:01,460 --> 00:50:06,730
start with U(0) as f.
821
00:50:06,730 --> 00:50:10,250
I just want to draw the analogy.
822
00:50:10,250 --> 00:50:12,110
How did we solve
these equations?
823
00:50:12,110 --> 00:50:16,100
I expanded f in terms
of the eigenvector,
824
00:50:16,100 --> 00:50:19,820
and then what was step two?
825
00:50:19,820 --> 00:50:22,970
For the differential
equation, I didn't divide
826
00:50:22,970 --> 00:50:26,840
by lambda_k, what did I do?
827
00:50:26,840 --> 00:50:29,220
I multiplied by e^(lambda_k*t).
828
00:50:29,220 --> 00:50:32,510
829
00:50:32,510 --> 00:50:34,270
You see, it's the same trick.
830
00:50:34,270 --> 00:50:37,160
Just get it in eigenspace.
831
00:50:37,160 --> 00:50:41,360
In eigenspace it's like
one tiny problem at a time.
832
00:50:41,360 --> 00:50:43,850
You're just following
that normal mode,
833
00:50:43,850 --> 00:50:47,170
and so here instead
of dividing by lambda,
834
00:50:47,170 --> 00:50:49,840
I multiplied by e^(lambda*t).
835
00:50:49,840 --> 00:50:53,930
And for powers of-- For
K2D to the 100th power,
836
00:50:53,930 --> 00:50:56,550
I would multiply by
lambda to the hundredth.
837
00:50:56,550 --> 00:50:59,820
Here, I have K2D to
the minus first power.
838
00:50:59,820 --> 00:51:03,100
So I'm multiplying by
lambdas to the minus one.
839
00:51:03,100 --> 00:51:10,820
OK, and the key point is that
these c's can be found fast.
840
00:51:10,820 --> 00:51:14,400
And this summing up
can be done fast.
841
00:51:14,400 --> 00:51:17,740
Now that's what's
also very exceptional.
842
00:51:17,740 --> 00:51:19,980
And that's where
the FFT comes in.
843
00:51:19,980 --> 00:51:26,300
The fast Fourier transform is a
fast way to get into eigenspace
844
00:51:26,300 --> 00:51:28,130
and to get back.
845
00:51:28,130 --> 00:51:31,950
When eigenspace happens
to be frequency space.
846
00:51:31,950 --> 00:51:35,810
You see that's the key.
847
00:51:35,810 --> 00:51:40,750
In other words these y's and
lambdas that I said we knew,
848
00:51:40,750 --> 00:51:48,130
these y's, the eigenvectors,
are pure sine vectors.
849
00:51:48,130 --> 00:51:53,060
So that this is an expansion,
is a sine transform.
850
00:51:53,060 --> 00:51:56,810
S-I-N-E. A pure sine transform.
851
00:51:56,810 --> 00:52:00,940
And that can be done fast,
and it can be inverted fast.
852
00:52:00,940 --> 00:52:05,630
So you see, what makes this
fast Poisson solver work,
853
00:52:05,630 --> 00:52:09,150
is I have to know
eigenvectors and eigenvalues,
854
00:52:09,150 --> 00:52:13,480
and they have to be fantastic
vectors like sine vectors.
855
00:52:13,480 --> 00:52:18,470
OK, so I'll give you more, the
final picture, the details,
856
00:52:18,470 --> 00:52:21,308
Wednesday and then move
on to finite elements.
857
00:52:21,308 --> 00:52:21,808