Optimizing Memory Allocation in a Simple, but Long Function
Oscar Benjamin
oscar.j.benjamin at gmail.com
Mon Apr 25 09:45:55 EDT 2016
On 25 April 2016 at 08:39, Gregory Ewing <greg.ewing at canterbury.ac.nz> wrote:
> Derek Klinge wrote:
>>
>> Also, it seems to me if the goal is to use the smallest value of n to get
>> a
>> particular level of accuracy, changing your guess of N by doubling seems
>> to
>> have a high chance of overshoot.
>
>
> If you want to find the exact n required, once you overshoot
> you could use a binary search to narrow it down.
Also you can calculate the truncation error for Euler's method. Since
f(t) = f(t0) + f'(t0)*(t - t0) + (1/2)f''(t0)*(t - t0)**2 + O((t - t0)**3)
Euler's method just uses the first two terms so
x[n+1] = x[n] + dt*f(x[n])
the next term would be
(1/2)*f'(x[n])*dt**2
Since in your case f'(x) = x and dt = 1/N that's
(1/2)*x[n]*(1/N)**2
As a relative error (divide by x[n]) that's
(1/2)*(1/N)**2
Let's add the relative error from N steps to get
N*(1/2)*(1/N)**2 = 1/(2*N)
So the relative error integrating from 0 to 1 with N steps is 1/(2*N).
If we want a relative error of epsilon then the number of steps needed
is 1/(2*epsilon).
That is to say that for a relative error of 1e-4 we need N =
1/(2*1e-4) = 1e4/2 = 5e3 = 5000.
>>> import math
>>> N = 5000
>>> error = math.e - (1 + 1.0/N)**N
>>> relative_error = error / math.e
>>> relative_error
9.998167027596845e-05
Which is approximately 1e-4 as required.
--
Oscar
More information about the Python-list
mailing list