Re: Minimax Polynomial Fit Message #3 Posted by Valentin Albillo on 11 Oct 2005, 4:40 a.m., in response to message #2 by Gerson W. Barbosa
Hi, Gerson:
Gerson posted:
"Can the user also specify polynomials with odd or even powers only? This would be particularly
useful when fitting odd and even functions, as less coefficients would be needed for a given accuracy."
First of all, thanks for your interest in my article. As for your question, there's no need of a separate option to achieve that effect. You just simply specify an interval where it shows that the function is odd or even, and the minimax error condition itself will guarantee that only odd or even powers are used.
For instance, let's say that you want to fit a minimax polynomial of lowest possible degree to y=sin(x) for values of x not exceeding Pi/2 and using just odd powers of x (as sin(-x) = -sin(x), so sin(x) is an odd function). Also, you want a guaranteed maximum error <= 1E-6.
As I've stated, you only need to specify an interval where the 'oddness' of the functions shows, in this case [-Pi/2, Pi/2] will
do. For this particular function, interval, and maximum error,
my program returns the following 7th-degree polynomial:
P(x) = 0.99999661 * x - 0.16664831 * x3 + 0.00830636 * x5
- 0.00018365 * x7
with guaranteed absolute maximum error less than 1E-6 in [-Pi/2, Pi/2]. As you can see, only odd powers of x were returned, all the remaining coefficients being zero within machine rounding limits so our minimax approximation only requires four non-zero coefficients.
Here's a short table of sin(x) vs. P(x):
>FIX 7 @ FOR X=-PI/2 TO PI/2 STEP PI/20 @ DISP X,SIN(X),FNF(X),RES-SIN(X) @ NEXT X
X SIN(X) P(X) ERROR
-------------------------------------------------------------------------------
-1.5707963 -1.0000000 -0.9999994 0.0000006
-1.4137167 -0.9876883 -0.9876887 -0.0000004
-1.2566371 -0.9510565 -0.9510560 0.0000005
-1.0995574 -0.8910065 -0.8910061 0.0000004
-0.9424778 -0.8090170 -0.8090173 -0.0000003
-0.7853982 -0.7071068 -0.7071074 -0.0000006
-0.6283185 -0.5877853 -0.5877856 -0.0000003
-0.4712389 -0.4539905 -0.4539903 0.0000002
-0.3141593 -0.3090170 -0.3090164 0.0000006
-0.1570796 -0.1564345 -0.1564340 0.0000005
0.0000000 0.0000000 0.0000000 0.0000000
0.1570796 0.1564345 0.1564340 -0.0000005
0.3141593 0.3090170 0.3090164 -0.0000006
0.4712389 0.4539905 0.4539903 -0.0000002
0.6283185 0.5877853 0.5877856 0.0000003
0.7853982 0.7071068 0.7071074 0.0000006
0.9424778 0.8090170 0.8090173 0.0000003
1.0995574 0.8910065 0.8910061 -0.0000004
1.2566371 0.9510565 0.9510560 -0.0000005
1.4137167 0.9876883 0.9876887 0.0000004
1.5707963 1.0000000 0.9999994 -0.0000006
and, as you can see, the absolute error never exceeds 0.0000006 < 1E-6, so the results are accurate to six decimal places plus or minus 1 ulp.
This exact same approach, but specifying the [-Pi/6, Pi/6] interval instead, yields a 7th-degree, odd-powers-only, minimax polynomial which has a guaranteed absolute maximum error e = 3.2E-11 in that interval, while using only four coefficients.
Combined with range reduction, this could form the basis of a simple yet very accurate implementation of trigonometric functions in machines lacking them, as you know. Similar approaches would allow implementing most any specialized function, say Gamma(x), Lambert's W(x), etc.
Best regards from V.
Edited: 11 Oct 2005, 5:55 a.m.
|