Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.
|
|
Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
A series of progressively better approximations to exp(-x), x>=0
Replies:
6
Last Post:
Oct 19, 2010 10:29 AM
|
 |
|
|
Re: A series of progressively better approximations to exp(-x), x>=0
Posted:
Oct 19, 2010 8:39 AM
|
|
On Oct 19, 3:11 am, Tim Norfolk <timsn...@aol.com> wrote: > On Oct 15, 1:02 pm, Knud Thomsen <sa...@kt-algorithms.com> wrote: > > > > > On Oct 15, 3:39 pm, Tim Norfolk <timsn...@aol.com> wrote: > > > > On Oct 15, 8:48 am, Knud Thomsen <sa...@kt-algorithms.com> wrote: > > > > > Consider approximations of the form, x>=0, p an integer: > > > > > C 1 > > > > exp(-x) ~ (-----)^p = ------------- (1) > > > > C + x (1 + 1/C x)^p > > > > > The complexity of the approximations is arguably independent of p, > > > > with only one optimizable constant. Execution time grows as > > > > O(log(p)) using exponentiation by squaring; then p being a power of > > > > 2 is particularly efficient. > > > > > Note that substituting variable x, e.g. with x^2/2 to create an > > > > approximation to the Gaussian, does not change the maximum > > > > |abs. error|. > > > > > With an optimal C-value, Copt, the maximum |abs. error| becomes > > > > roughly inversely proportional to p. > > > > > A simple asymptotic approximation to Copt is: C(p) = p-0.6627435. > > > > > The following approximation might be useful for precalculation of > > > > Copt(p): > > > > > Copt(p) ~ Cappr(p) = p - Q0 + Q1/p - Q2/p^2 + Q3/p^3 - Q4/p^4 > > > > > Q0 = 0.6627435 Q1 = 0.2569148 Q2 = 0.0772350 Q3 = 0.0157493 > > > > Q4 = 0.0009863 > > > > > with an |abs. error| < 9E-7. > > > > > In the table below, giving relevant parameters for selected values > > > > of p, the following abbreviations are introduced: > > > > > Eopt The max. |abs. error| of appr. (1) for C=Copt > > > > Esimp The max. |abs. error| of appr. (1) for C=p-0.6627435 > > > > Eappr The max. |abs. error| of appr. (1) for C=Cappr > > > > > ---------------------------------------------------------- > > > > p Copt Eopt Esimp/Eopt Eappr/Eopt > > > > ---------------------------------------------------------- > > > > 1 0.5316985 1.018926E-1 2.1001687 1.0000016 > > > > 2 1.4483130 5.635451E-2 1.3831008 1.0000024 > > > > 3 2.4148834 3.892816E-2 1.2331002 1.0000013 > > > > 4 3.3969007 2.972884E-2 1.1675592 1.0000011 > > > > 5 4.3856753 2.404472E-2 1.1307883 1.0000022 > > > > 6 5.3780032 2.018465E-2 1.1072508 1.0000020 > > > > 7 6.3724285 1.739220E-2 1.0908921 1.0000014 > > > > 8 7.3681949 1.527833E-2 1.0788628 1.0000008 > > > > 10 9.3621912 1.229050E-2 1.0623562 1.0000001 > > > > 12 11.3581384 1.028000E-2 1.0515630 1.0000005 > > > > 16 15.3530151 7.745754E-3 1.0383026 1.0000008 > > > > 24 23.3478275 5.187811E-3 1.0252929 1.0000010 > > > > 32 31.3452094 3.899888E-3 1.0188801 1.0000010 > > > > 48 47.3425749 2.605962E-3 1.0125275 1.0000008 > > > > 64 63.3412515 1.956740E-3 1.0093735 1.0000006 > > > > 128 127.3392587 9.800744E-4 1.0046704 1.0000003 > > > > 256 255.3382588 4.904639E-4 1.0023312 1.0000001 > > > > 512 511.3377580 2.453387E-4 1.0011646 1.0000000 > > > > 1024 1023.3375074 1.226961E-4 1.0005821 1.0000000 > > > > 2048 2047.3373820 6.135471E-5 1.0002911 1.0000001 > > > > 4096 4095.3373193 3.067903E-5 1.0001456 1.0000001 > > > > 8192 8191.3372879 1.533993E-5 1.0000728 1.0000001 > > > > .. > > > > ->inf p-0.6627435# 0.1256681/p# 1.0000000 1.0000000 > > > > ---------------------------------------------------------- > > > > #) Using Aitken's delta-squared process on (p-Copt) and (p*Eopt). > > > > > Best regards, > > > > Knud Thomsen > > > > Geologist, Denmark > > > > This specific problem is an old one in approximation theory. Have you > > > looked at Pade approximants, for example? > > > Yes, I'm familiar with Pade approximants and other approaches in my > > work with mathematical modelling. > > What I find interesting about the proposed method is the simple > > scalability. > > > Regards, > > Knud- Hide quoted text - > > > - Show quoted text - > > If you want simple, why not set $f_n(x) = (1+x/n)^{-n}$ as your $n$-th > approximant? The maximum error $f_n(x)-exp(-x)$ on $[0,\infty)$ is at > $x=x_n$, and equal to $x_n exp(-x_n)/n$. This last quantity is bounded > by $1/ne$.
That would correspond to setting C=p in my terminology. This results in a measured error profile like this:
------------------------ p E(C=p)/E(C=Copt) ------------------------ 1 1.9984982 2 2.0597549 3 2.0864088 ... 2048 2.1537360 4096 2.1537941 8192 2.1538230 ... ------------------------
Using C=p-0.6627435, as I suggested, while less simple than just C=p, offers an asymptotically better approximation (see original table).
Regards, Knud
|
|
|
|