[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.