[music] Well here is a linear
approximation problem.
So I've got some function F.
And you don't know that function
immediately, but I know it's derivative is
equal to the function's value, say at all
X.
And let's suppose that I know this
function's value at zero.
So this function's value at 0 is 1, and
then my goal is to find f of 1.
Now we secretly know something, right?
I mean, I secretly know that this function
is really e to the x.
So when I say find f of 1.
I really mean that I'm trying to calculate
e to the first power, I'm trying to
calculate e.
The point, here, you know, isn't to the
say that answer is e, right?
The point is going to be to try to
approximate this quantity without actually
knowing the value of e.
We already know how to do this.
We can use linear approximation, all
right.
I want to know what f of 1 is, and by the
linear approximation business, well it's
not equal to, but it's approximately the
value at 0.
Plus how much I change the input by times
the derivative at 0.
Now I know the function's value at 0.
The function's value at 0 is 1.
And since the derivative is equal to the
value everywhere, that means I also know
the derivative is 0.
So the function's value is 1, the
derivative at 0 is the same as function
value at 0, which is 1.
1 plus 1 times 1 is 2 so approximately f
of 1 is 2.
And since I secretly know that this
function is e to the x, I'm saying that e
is about 2, 2 is a terrible approximation
but we can do better.
If we can do any approximation once, we
can do it a bunch of time.
So instead of this jumping all the way to
1, let's first approximate f of 1 half and
that will f of 0, plus how much I wiggled
by which is 1 half times the derivative at
0.
Well, f of 0 is still 1, 1 half is a half
and the derivative at 0 is still 1.
So this is 1 plus a half, this is 3
halves.
Now we use data approximation to
approximate f of 1.
Yes, I'm sort of bootstrapping up here,
now I want to know f of 1 at least
approximately.
But instead of starting at 0, I'm going to
start at 1 half.
So that will be about f of 1 half, which
admittedly I don't know but I got this
approximation for it.
Plus how much I changed to go from 1 half
to 1 times the derivative at one half.
Now f of one half is approximately this
three halves, one half and the derivative
of one half I don't really know what it is
but I still know that the derivative is
equal to function's value and I've got an
approximation of the function's value.
So I can use that approximation here at
the derivative at one half Is about 3
halves.
And I've got 3 halves.
And I've got 3 quarters.
That ends up being 9 4th, which is a
slightly better approximation to the
function's value of one.
I mean, nine fourths is closer to the
actual value of e.
Well if two steps worked better than one
step, ten steps will work even better.
So here we go, let's approximate this
function at 0.1.
Well that's approximately the function
value at 0 plus how much I change the
input by times the derivative at 0 and the
function value at 0 is 1 plus 0.1 times
derivative of 0 is 1.
So approximately, E to the 0.1 is about
1.1.
Now I repeat this process, I want to know
exactly what's the function's value at
0.2.
That should be about the function's value
at 0.1 plus 0.1 times the derivative at
0.1.
So approximately the function values at
point 0.1 is about 1.1 plus 0.1 times
derivative at 0.1, which is about, no, see
this in fact the function values at 0.1
which is about 1.1.
So 1.1 plus 0.1 times 1.1, it's kind of a
mouthful.
But that ends up being 1.21.
Now to approximate the function value at
0.3.
All right, I'll start with the function's
value at 0.2.
I go from 0.2 to 0.3 by adding 0.1.
And then I multiply by the derivative, at
0.2.
The function's value at 0.2 is 1.21 plus
0.1 times the derivative of 0.2, which is
also about 1.21, and 1.21 times 1.21 plus
0.1 times 1.21, that's 1.331.
Now you might begin to see a pattern here,
right?
1.1, 1.21, 1.331, these are pieces of
Pascal's triangle, really.
I mean that makes sense considering how.
How I'm adding the number plus 0.1 times
the number.
Lets just keep going.
So let's compute f of 0.4, that's f of 0.3
plus 0.1 times the derivative of 0.3.
Well, the approximation here for f of 0.3
is 1.331 plus 0.1 times 1.331, which is,
1.4641.
Now I can do this again to get an
approximation for 0.5.
Right, I'm really just taking this number
and adding 0.1 times it and I get 1.61051.
Can do the same thing to approximate 0.6
and I get 1.771561.
Can do the same thing to approximate 0.7,
and take this number and add this number
times 0.1, which is 1.9487171.
Do the same game, do approximate f of 0.8?
So I take this number and add 0.1 times
this number.
And I get 2.14358881 can do the same thing
now a 0.9.
So this number plus 0.1 times this number
and I get 2.357947691 and last.
I take this number and add 0.1 times this
number, and I get 2.5937424601,
approximately e.
Well, not so great.
But I mean, it's, you know, much closer to
my previous attempts, where I just used
two steps, you know.
So using ten steps is better, this
technique of repeated linear approximation
has a name.
So instead of calling this you know
repeated linear approximation people
usually call this the Euler method.
Lets summarize the algorithm.
So this is a set up.
I've got a formula for the derivative of
f, just in terms of f and x.
So this cloud represents some formula that
involves f of x and x and that's my
formula for the derivative of f at x.
And let's say I know the value of f at
zero.
Just some number and suppose I've picked
some small number H.
Well what Euler method tells me to do, is
I want to know F of H, well I already know
how to do that.
Right, that's just linear approximation.
It's f of zero plus h times the derivative
at zero.
I can use this formula, say to calculate
the derivative of F at zero.
And I know the value of f at zero.
So I can get an approximation to the
function's value H.
Now the neat thing is I an keep playing
this game, right?
If I want to know an approximate value to
the function at 2 times h, well that's
about the function's value h plus h times
the derivative at h.
And now I know the function's value at h
approximately.
And I know the derivative at h, because
I've got a formula for the derivative in
terms of f and x, and I know how to
calculate f of h, approximately, and I
know x, all right, it's h in this case.
And that means that I can get an
approximation to f of 2h and I'll just
keep playing this game.
If I want to know f of 3h, well that's
about f of 2h plus h times f prime of 2h,
so that's that linear approximation
formula again.
To go from 2h to 3h, I add h so f of 3h is
approximately my function's value with 2h
which I've already approximated, plus how
much I change the input by, times the
derivative of 2h.
And this I can also approximate, because
my formula for the derivative just
involves things I already know at least
approximately.
Right, I know the value of f at 2h
approximately.
And I can just keep on repeating this to
move myself further and further to the
right and, you know, approximate values of
the function that tend to get very far
away from zero.
The cool thing here is that I'm using, you
know, linear approximation in each stage.
And then I'm using the information from
previous stages not only to approximate
the function's value, but also to
approximate the function's derivative.
I should wan you that in the really world,
people don't really use the Euler method
so often.
But like any really great mathematical
idea, there's a ton of different riffs
that you can play on this basic framework.
For example since this is just going to
end up being an approximation of the
derivative anyhow, it's sometimes better
not to pick a point which is all the way
on the left hand side of the interval I'm
approximating over.
So sometimes you'll see that say instead
of using zero here, I might use h over 2.
Instead of using h, which is really on the
left hand side of the interval between h
and 2h.
You'll see that sometimes people will use,
say 3 halves h, which is smack in the
middle of h and 2h.
And say instead of using 2h here, people
will sometimes use 5 halves h, which is
right in between 2h and 3h.
So you can play some games, say by
choosing a different point to approximate
the derivative at, and using the midpoint
is sometimes better.
Incidentally, if you've got some
programming experience, I'd encourage you
to try to write a program to do the Euler
method.
It's really fun to be able to see these
calculations come alive.