]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [section:minimax Minimax Approximations and the Remez Algorithm] |
2 | ||
3 | The directory libs/math/minimax contains a command line driven | |
4 | program for the generation of minimax approximations using the Remez | |
5 | algorithm. Both polynomial and rational approximations are supported, | |
6 | although the latter are tricky to converge: it is not uncommon for | |
7 | convergence of rational forms to fail. No such limitations are present | |
8 | for polynomial approximations which should always converge smoothly. | |
9 | ||
10 | It's worth stressing that developing rational approximations to functions | |
11 | is often not an easy task, and one to which many books have been devoted. | |
12 | To use this tool, you will need to have a reasonable grasp of what the Remez | |
13 | algorithm is, and the general form of the approximation you want to achieve. | |
14 | ||
15 | Unless you already familar with the Remez method, | |
16 | you should first read the [link math_toolkit.remez | |
17 | brief background article explaining the principles behind the | |
18 | Remez algorithm]. | |
19 | ||
20 | The program consists of two parts: | |
21 | ||
22 | [variablelist | |
23 | [[main.cpp][Contains the command line parser, and all the calls to the Remez code.]] | |
24 | [[f.cpp][Contains the function to approximate.]] | |
25 | ] | |
26 | ||
27 | Therefore to use this tool, you must modify f.cpp to return the function to | |
28 | approximate. The tools supports multiple function approximations within | |
29 | the same compiled program: each as a separate variant: | |
30 | ||
31 | NTL::RR f(const NTL::RR& x, int variant); | |
32 | ||
33 | Returns the value of the function /variant/ at point /x/. So if you | |
34 | wish you can just add the function to approximate as a new variant | |
35 | after the existing examples. | |
36 | ||
37 | In addition to those two files, the program needs to be linked to | |
38 | a [link math_toolkit.high_precision.use_ntl patched NTL library to compile]. | |
39 | ||
40 | Note that the function /f/ must return the rational part of the | |
41 | approximation: for example if you are approximating a function | |
42 | /f(x)/ then it is quite common to use: | |
43 | ||
44 | f(x) = g(x)(Y + R(x)) | |
45 | ||
46 | where /g(x)/ is the dominant part of /f(x)/, /Y/ is some constant, and | |
47 | /R(x)/ is the rational approximation part, usually optimised for a low | |
48 | absolute error compared to |Y|. | |
49 | ||
50 | In this case you would define /f/ to return ['f(x)/g(x)] and then set the | |
51 | y-offset of the approximation to /Y/ (see command line options below). | |
52 | ||
53 | Many other forms are possible, but in all cases the objective is to | |
54 | split /f(x)/ into a dominant part that you can evaluate easily using | |
55 | standard math functions, and a smooth and slowly changing rational approximation | |
56 | part. Refer to your favourite textbook for more examples. | |
57 | ||
58 | Command line options for the program are as follows: | |
59 | ||
60 | [variablelist | |
61 | [[variant N][Sets the current function variant to N. This allows multiple functions | |
62 | that are to be approximated to be compiled into the same executable. | |
63 | Defaults to 0.]] | |
64 | [[range a b][Sets the domain for the approximation to the range \[a,b\], defaults | |
65 | to \[0,1\].]] | |
66 | [[relative][Sets the Remez code to optimise for relative error. This is the default | |
67 | at program startup. Note that relative error can only be used | |
68 | if f(x) has no roots over the range being optimised.]] | |
69 | [[absolute][Sets the Remez code to optimise for absolute error.]] | |
70 | [[pin \[true|false\]]["Pins" the code so that the rational approximation | |
71 | passes through the origin. Obviously only set this to | |
72 | /true/ if R(0) must be zero. This is typically used when | |
73 | trying to preserve a root at \[0,0\] while also optimising | |
74 | for relative error.]] | |
75 | [[order N D][Sets the order of the approximation to /N/ in the numerator and /D/ | |
76 | in the denominator. If /D/ is zero then the result will be a polynomial | |
77 | approximation. There will be N+D+2 coefficients in total, the first | |
78 | coefficient of the numerator is zero if /pin/ was set to true, and the | |
79 | first coefficient of the denominator is always one.]] | |
80 | [[working-precision N][Sets the working precision of NTL::RR to /N/ binary digits. Defaults to 250.]] | |
81 | [[target-precision N][Sets the precision of printed output to /N/ binary digits: | |
82 | set to the same number of digits as the type that will be used to | |
83 | evaluate the approximation. Defaults to 53 (for double precision).]] | |
84 | [[skew val]["Skews" the initial interpolated control points towards one | |
85 | end or the other of the range. Positive values skew the | |
86 | initial control points towards the left hand side of the | |
87 | range, and negative values towards the right hand side. | |
88 | If an approximation won't converge (a common situation) | |
89 | try adjusting the skew parameter until the first step yields | |
90 | the smallest possible error. /val/ should be in the range | |
91 | \[-100,+100\], the default is zero.]] | |
92 | [[brake val][Sets a brake on each step so that the change in the | |
93 | control points is braked by /val%/. Defaults to 50, | |
94 | try a higher value if an approximation won't converge, | |
95 | or a lower value to get speedier convergence.]] | |
96 | [[x-offset val][Sets the x-offset to /val/: the approximation will | |
97 | be generated for `f(S * (x + X)) + Y` where /X/ is the | |
98 | x-offset, /S/ is the x-scale | |
99 | and /Y/ is the y-offset. Defaults to zero. To avoid | |
100 | rounding errors, take care to specify a value that can | |
101 | be exactly represented as a floating point number.]] | |
102 | [[x-scale val][Sets the x-scale to /val/: the approximation will | |
103 | be generated for `f(S * (x + X)) + Y` where /S/ is the | |
104 | x-scale, /X/ is the x-offset | |
105 | and /Y/ is the y-offset. Defaults to one. To avoid | |
106 | rounding errors, take care to specify a value that can | |
107 | be exactly represented as a floating point number.]] | |
108 | [[y-offset val][Sets the y-offset to /val/: the approximation will | |
109 | be generated for `f(S * (x + X)) + Y` where /X/ | |
110 | is the x-offset, /S/ is the x-scale | |
111 | and /Y/ is the y-offset. Defaults to zero. To avoid | |
112 | rounding errors, take care to specify a value that can | |
113 | be exactly represented as a floating point number.]] | |
114 | [[y-offset auto][Sets the y-offset to the average value of f(x) | |
115 | evaluated at the two endpoints of the range plus the midpoint | |
116 | of the range. The calculated value is deliberately truncated | |
117 | to /float/ precision (and should be stored as a /float/ | |
118 | in your code). The approximation will | |
119 | be generated for `f(x + X) + Y` where /X/ is the x-offset | |
120 | and /Y/ is the y-offset. Defaults to zero.]] | |
121 | [[graph N][Prints N evaluations of f(x) at evenly spaced points over the | |
122 | range being optimised. If unspecified then /N/ defaults | |
123 | to 3. Use to check that f(x) is indeed smooth over the range | |
124 | of interest.]] | |
125 | [[step N][Performs /N/ steps, or one step if /N/ is unspecified. | |
126 | After each step prints: the peek error at the extrema of | |
127 | the error function of the approximation, | |
128 | the theoretical error term solved for on the last step, | |
129 | and the maximum relative change in the location of the | |
130 | Chebyshev control points. The approximation is converged on the | |
131 | minimax solution when the two error terms are (approximately) | |
132 | equal, and the change in the control points has decreased to | |
133 | a suitably small value.]] | |
134 | [[test \[float|double|long\]][Tests the current approximation at float, | |
135 | double, or long double precision. Useful to check for rounding | |
136 | errors in evaluating the approximation at fixed precision. | |
137 | Tests are conducted at the extrema of the error function of the | |
138 | approximation, and at the zeros of the error function.]] | |
139 | [[test \[float|double|long\] N] [Tests the current approximation at float, | |
140 | double, or long double precision. Useful to check for rounding | |
141 | errors in evaluating the approximation at fixed precision. | |
142 | Tests are conducted at N evenly spaced points over the range | |
143 | of the approximation. If none of \[float|double|long\] are specified | |
144 | then tests using NTL::RR, this can be used to obtain the error | |
145 | function of the approximation.]] | |
146 | [[rescale a b][Takes the current Chebeshev control points, and rescales them | |
147 | over a new interval \[a,b\]. Sometimes this can be used to obtain | |
148 | starting control points for an approximation that can not otherwise be | |
149 | converged.]] | |
150 | [[rotate][Moves one term from the numerator to the denominator, but keeps the | |
151 | Chebyshev control points the same. Sometimes this can be used to obtain | |
152 | starting control points for an approximation that can not otherwise be | |
153 | converged.]] | |
154 | [[info][Prints out the current approximation: the location of the zeros of the | |
155 | error function, the location of the Chebyshev control points, the | |
156 | x and y offsets, and of course the coefficients of the polynomials.]] | |
157 | ] | |
158 | ||
159 | ||
160 | [endsect][/section:minimax Minimax Approximations and the Remez Algorithm] | |
161 | ||
162 | [/ | |
163 | Copyright 2006 John Maddock and Paul A. Bristow. | |
164 | Distributed under the Boost Software License, Version 1.0. | |
165 | (See accompanying file LICENSE_1_0.txt or copy at | |
166 | http://www.boost.org/LICENSE_1_0.txt). | |
167 | ] |