1 00:00:00,012 --> 00:00:04,371 [music] Well here is a linear approximation problem. 2 00:00:04,371 --> 00:00:09,314 So I've got some function F. And you don't know that function 3 00:00:09,314 --> 00:00:16,174 immediately, but I know it's derivative is equal to the function's value, say at all 4 00:00:16,174 --> 00:00:19,117 X. And let's suppose that I know this 5 00:00:19,117 --> 00:00:24,722 function's value at zero. So this function's value at 0 is 1, and 6 00:00:24,722 --> 00:00:30,793 then my goal is to find f of 1. Now we secretly know something, right? 7 00:00:30,793 --> 00:00:36,344 I mean, I secretly know that this function is really e to the x. 8 00:00:36,344 --> 00:00:41,027 So when I say find f of 1. I really mean that I'm trying to calculate 9 00:00:41,027 --> 00:00:43,846 e to the first power, I'm trying to calculate e. 10 00:00:43,846 --> 00:00:47,896 The point, here, you know, isn't to the say that answer is e, right? 11 00:00:47,896 --> 00:00:52,830 The point is going to be to try to approximate this quantity without actually 12 00:00:52,830 --> 00:00:56,315 knowing the value of e. We already know how to do this. 13 00:00:56,315 --> 00:00:59,290 We can use linear approximation, all right. 14 00:00:59,290 --> 00:01:04,831 I want to know what f of 1 is, and by the linear approximation business, well it's 15 00:01:04,831 --> 00:01:08,500 not equal to, but it's approximately the value at 0. 16 00:01:08,501 --> 00:01:13,027 Plus how much I change the input by times the derivative at 0. 17 00:01:13,027 --> 00:01:17,522 Now I know the function's value at 0. The function's value at 0 is 1. 18 00:01:17,522 --> 00:01:22,888 And since the derivative is equal to the value everywhere, that means I also know 19 00:01:22,888 --> 00:01:26,699 the derivative is 0. So the function's value is 1, the 20 00:01:26,699 --> 00:01:31,250 derivative at 0 is the same as function value at 0, which is 1. 21 00:01:31,250 --> 00:01:34,779 1 plus 1 times 1 is 2 so approximately f of 1 is 2. 22 00:01:34,779 --> 00:01:40,275 And since I secretly know that this function is e to the x, I'm saying that e 23 00:01:40,275 --> 00:01:44,900 is about 2, 2 is a terrible approximation but we can do better. 24 00:01:44,900 --> 00:01:49,728 If we can do any approximation once, we can do it a bunch of time. 25 00:01:49,729 --> 00:01:56,723 So instead of this jumping all the way to 1, let's first approximate f of 1 half and 26 00:01:56,723 --> 00:02:03,521 that will f of 0, plus how much I wiggled by which is 1 half times the derivative at 27 00:02:03,521 --> 00:02:06,397 0. Well, f of 0 is still 1, 1 half is a half 28 00:02:06,397 --> 00:02:11,054 and the derivative at 0 is still 1. So this is 1 plus a half, this is 3 29 00:02:11,054 --> 00:02:13,789 halves. Now we use data approximation to 30 00:02:13,789 --> 00:02:17,677 approximate f of 1. Yes, I'm sort of bootstrapping up here, 31 00:02:17,677 --> 00:02:20,747 now I want to know f of 1 at least approximately. 32 00:02:20,747 --> 00:02:24,528 But instead of starting at 0, I'm going to start at 1 half. 33 00:02:24,528 --> 00:02:29,556 So that will be about f of 1 half, which admittedly I don't know but I got this 34 00:02:29,556 --> 00:02:34,126 approximation for it. Plus how much I changed to go from 1 half 35 00:02:34,126 --> 00:02:39,543 to 1 times the derivative at one half. Now f of one half is approximately this 36 00:02:39,543 --> 00:02:45,187 three halves, one half and the derivative of one half I don't really know what it is 37 00:02:45,187 --> 00:02:50,665 but I still know that the derivative is equal to function's value and I've got an 38 00:02:50,665 --> 00:02:56,567 approximation of the function's value. So I can use that approximation here at 39 00:02:56,567 --> 00:02:59,947 the derivative at one half Is about 3 halves. 40 00:02:59,947 --> 00:03:03,651 And I've got 3 halves. And I've got 3 quarters. 41 00:03:03,651 --> 00:03:08,817 That ends up being 9 4th, which is a slightly better approximation to the 42 00:03:08,817 --> 00:03:13,099 function's value of one. I mean, nine fourths is closer to the 43 00:03:13,099 --> 00:03:16,989 actual value of e. Well if two steps worked better than one 44 00:03:16,989 --> 00:03:22,556 step, ten steps will work even better. So here we go, let's approximate this 45 00:03:22,556 --> 00:03:27,166 function at 0.1. Well that's approximately the function 46 00:03:27,166 --> 00:03:33,214 value at 0 plus how much I change the input by times the derivative at 0 and the 47 00:03:33,214 --> 00:03:37,887 function value at 0 is 1 plus 0.1 times derivative of 0 is 1. 48 00:03:37,887 --> 00:03:41,216 So approximately, E to the 0.1 is about 1.1. 49 00:03:41,216 --> 00:03:47,690 Now I repeat this process, I want to know exactly what's the function's value at 50 00:03:47,690 --> 00:03:51,507 0.2. That should be about the function's value 51 00:03:51,507 --> 00:03:55,079 at 0.1 plus 0.1 times the derivative at 0.1. 52 00:03:55,080 --> 00:04:01,333 So approximately the function values at point 0.1 is about 1.1 plus 0.1 times 53 00:04:01,333 --> 00:04:07,564 derivative at 0.1, which is about, no, see this in fact the function values at 0.1 54 00:04:07,564 --> 00:04:12,231 which is about 1.1. So 1.1 plus 0.1 times 1.1, it's kind of a 55 00:04:12,231 --> 00:04:15,381 mouthful. But that ends up being 1.21. 56 00:04:15,381 --> 00:04:19,116 Now to approximate the function value at 0.3. 57 00:04:19,116 --> 00:04:23,876 All right, I'll start with the function's value at 0.2. 58 00:04:23,876 --> 00:04:30,131 I go from 0.2 to 0.3 by adding 0.1. And then I multiply by the derivative, at 59 00:04:30,131 --> 00:04:34,113 0.2. The function's value at 0.2 is 1.21 plus 60 00:04:34,113 --> 00:04:41,389 0.1 times the derivative of 0.2, which is also about 1.21, and 1.21 times 1.21 plus 61 00:04:41,389 --> 00:04:48,254 0.1 times 1.21, that's 1.331. Now you might begin to see a pattern here, 62 00:04:48,254 --> 00:04:52,350 right? 1.1, 1.21, 1.331, these are pieces of 63 00:04:52,350 --> 00:04:58,775 Pascal's triangle, really. I mean that makes sense considering how. 64 00:04:58,776 --> 00:05:03,576 How I'm adding the number plus 0.1 times the number. 65 00:05:03,576 --> 00:05:09,293 Lets just keep going. So let's compute f of 0.4, that's f of 0.3 66 00:05:09,293 --> 00:05:16,668 plus 0.1 times the derivative of 0.3. Well, the approximation here for f of 0.3 67 00:05:16,668 --> 00:05:21,590 is 1.331 plus 0.1 times 1.331, which is, 1.4641. 68 00:05:21,590 --> 00:05:26,595 Now I can do this again to get an approximation for 0.5. 69 00:05:26,595 --> 00:05:34,998 Right, I'm really just taking this number and adding 0.1 times it and I get 1.61051. 70 00:05:34,998 --> 00:05:43,298 Can do the same thing to approximate 0.6 and I get 1.771561. 71 00:05:43,298 --> 00:05:52,416 Can do the same thing to approximate 0.7, and take this number and add this number 72 00:05:52,416 --> 00:06:00,065 times 0.1, which is 1.9487171. Do the same game, do approximate f of 0.8? 73 00:06:00,065 --> 00:06:05,061 So I take this number and add 0.1 times this number. 74 00:06:05,062 --> 00:06:13,346 And I get 2.14358881 can do the same thing now a 0.9. 75 00:06:13,346 --> 00:06:24,258 So this number plus 0.1 times this number and I get 2.357947691 and last. 76 00:06:24,259 --> 00:06:30,662 I take this number and add 0.1 times this number, and I get 2.5937424601, 77 00:06:30,662 --> 00:06:34,021 approximately e. Well, not so great. 78 00:06:34,021 --> 00:06:41,517 But I mean, it's, you know, much closer to my previous attempts, where I just used 79 00:06:41,517 --> 00:06:45,919 two steps, you know. So using ten steps is better, this 80 00:06:45,919 --> 00:06:50,290 technique of repeated linear approximation has a name. 81 00:06:50,290 --> 00:06:55,070 So instead of calling this you know repeated linear approximation people 82 00:06:55,070 --> 00:06:59,479 usually call this the Euler method. Lets summarize the algorithm. 83 00:06:59,479 --> 00:07:03,428 So this is a set up. I've got a formula for the derivative of 84 00:07:03,428 --> 00:07:07,991 f, just in terms of f and x. So this cloud represents some formula that 85 00:07:07,991 --> 00:07:12,565 involves f of x and x and that's my formula for the derivative of f at x. 86 00:07:12,566 --> 00:07:15,324 And let's say I know the value of f at zero. 87 00:07:15,324 --> 00:07:19,393 Just some number and suppose I've picked some small number H. 88 00:07:19,393 --> 00:07:24,794 Well what Euler method tells me to do, is I want to know F of H, well I already know 89 00:07:24,794 --> 00:07:28,570 how to do that. Right, that's just linear approximation. 90 00:07:28,570 --> 00:07:31,822 It's f of zero plus h times the derivative at zero. 91 00:07:31,822 --> 00:07:36,179 I can use this formula, say to calculate the derivative of F at zero. 92 00:07:36,179 --> 00:07:40,404 And I know the value of f at zero. So I can get an approximation to the 93 00:07:40,404 --> 00:07:44,059 function's value H. Now the neat thing is I an keep playing 94 00:07:44,059 --> 00:07:47,867 this game, right? If I want to know an approximate value to 95 00:07:47,867 --> 00:07:53,067 the function at 2 times h, well that's about the function's value h plus h times 96 00:07:53,067 --> 00:07:57,133 the derivative at h. And now I know the function's value at h 97 00:07:57,133 --> 00:08:01,106 approximately. And I know the derivative at h, because 98 00:08:01,106 --> 00:08:06,180 I've got a formula for the derivative in terms of f and x, and I know how to 99 00:08:06,180 --> 00:08:11,787 calculate f of h, approximately, and I know x, all right, it's h in this case. 100 00:08:11,788 --> 00:08:16,490 And that means that I can get an approximation to f of 2h and I'll just 101 00:08:16,490 --> 00:08:20,543 keep playing this game. If I want to know f of 3h, well that's 102 00:08:20,543 --> 00:08:25,689 about f of 2h plus h times f prime of 2h, so that's that linear approximation 103 00:08:25,689 --> 00:08:29,089 formula again. To go from 2h to 3h, I add h so f of 3h is 104 00:08:29,089 --> 00:08:34,777 approximately my function's value with 2h which I've already approximated, plus how 105 00:08:34,777 --> 00:08:38,435 much I change the input by, times the derivative of 2h. 106 00:08:38,435 --> 00:08:42,662 And this I can also approximate, because my formula for the derivative just 107 00:08:42,662 --> 00:08:45,830 involves things I already know at least approximately. 108 00:08:45,830 --> 00:08:48,610 Right, I know the value of f at 2h approximately. 109 00:08:48,610 --> 00:08:52,968 And I can just keep on repeating this to move myself further and further to the 110 00:08:52,968 --> 00:08:57,524 right and, you know, approximate values of the function that tend to get very far 111 00:08:57,524 --> 00:09:01,086 away from zero. The cool thing here is that I'm using, you 112 00:09:01,086 --> 00:09:05,949 know, linear approximation in each stage. And then I'm using the information from 113 00:09:05,949 --> 00:09:10,227 previous stages not only to approximate the function's value, but also to 114 00:09:10,227 --> 00:09:15,494 approximate the function's derivative. I should wan you that in the really world, 115 00:09:15,494 --> 00:09:18,780 people don't really use the Euler method so often. 116 00:09:18,780 --> 00:09:23,141 But like any really great mathematical idea, there's a ton of different riffs 117 00:09:23,141 --> 00:09:28,447 that you can play on this basic framework. For example since this is just going to 118 00:09:28,447 --> 00:09:33,661 end up being an approximation of the derivative anyhow, it's sometimes better 119 00:09:33,661 --> 00:09:39,191 not to pick a point which is all the way on the left hand side of the interval I'm 120 00:09:39,191 --> 00:09:43,209 approximating over. So sometimes you'll see that say instead 121 00:09:43,209 --> 00:09:48,840 of using zero here, I might use h over 2. Instead of using h, which is really on the 122 00:09:48,840 --> 00:09:52,255 left hand side of the interval between h and 2h. 123 00:09:52,255 --> 00:09:57,071 You'll see that sometimes people will use, say 3 halves h, which is smack in the 124 00:09:57,071 --> 00:10:00,630 middle of h and 2h. And say instead of using 2h here, people 125 00:10:00,630 --> 00:10:04,644 will sometimes use 5 halves h, which is right in between 2h and 3h. 126 00:10:04,644 --> 00:10:10,194 So you can play some games, say by choosing a different point to approximate 127 00:10:10,194 --> 00:10:14,872 the derivative at, and using the midpoint is sometimes better. 128 00:10:14,872 --> 00:10:22,223 Incidentally, if you've got some programming experience, I'd encourage you 129 00:10:22,223 --> 00:10:26,704 to try to write a program to do the Euler method. 130 00:10:26,704 --> 00:10:32,747 It's really fun to be able to see these calculations come alive.