libs/math/doc/html/math_toolkit/internals/minimax.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Minimax Approximations and the Remez Algorithm</title>
   5 <link rel="stylesheet" href="../../math.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
   7 <link rel="home" href="../../index.html" title="Math Toolkit 2.11.0">
   8 <link rel="up" href="../internals.html" title="Internal tools">
   9 <link rel="prev" href="tuples.html" title="Tuples">
  10 <link rel="next" href="error_test.html" title="Relative Error and Testing">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="tuples.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="error_test.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="math_toolkit.internals.minimax"></a><a class="link" href="minimax.html" title="Minimax Approximations and the Remez Algorithm">Minimax Approximations
  28       and the Remez Algorithm</a>
  29 </h3></div></div></div>
  30 <p>
  31         The directory <code class="computeroutput"><span class="identifier">libs</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">minimax</span></code>
  32         contains an interactive command-line driven program for the generation of
  33         minimax approximations using the Remez algorithm. Both polynomial and rational
  34         approximations are supported, although the latter are tricky to converge:
  35         it is not uncommon for convergence of rational forms to fail. No such limitations
  36         are present for polynomial approximations which should always converge smoothly.
  37       </p>
  38 <p>
  39         It's worth stressing that developing rational approximations to functions
  40         is often not an easy task, and one to which many books have been devoted.
  41         To use this tool, you will need to have a reasonable grasp of what the Remez
  42         algorithm is, and the general form of the approximation you want to achieve.
  43       </p>
  44 <p>
  45         Unless you already familar with the Remez method, you should first read the
  46         <a class="link" href="../remez.html" title="The Remez Method">brief background article explaining the
  47         principles behind the Remez algorithm</a>.
  48       </p>
  49 <p>
  50         The program consists of two parts:
  51       </p>
  52 <div class="variablelist">
  53 <p class="title"><b></b></p>
  54 <dl class="variablelist">
  55 <dt><span class="term">main.cpp</span></dt>
  56 <dd><p>
  57               Contains the command line parser, and all the calls to the Remez code.
  58             </p></dd>
  59 <dt><span class="term">f.cpp</span></dt>
  60 <dd><p>
  61               Contains the function to approximate.
  62             </p></dd>
  63 </dl>
  64 </div>
  65 <p>
  66         Therefore to use this tool, you must modify f.cpp to return the function
  67         to approximate. The tools supports multiple function approximations within
  68         the same compiled program: each as a separate variant:
  69       </p>
  70 <pre class="programlisting"><span class="identifier">NTL</span><span class="special">::</span><span class="identifier">RR</span> <span class="identifier">f</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">NTL</span><span class="special">::</span><span class="identifier">RR</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">variant</span><span class="special">);</span>
  71 </pre>
  72 <p>
  73         Returns the value of the function <span class="emphasis"><em>variant</em></span> at point
  74         <span class="emphasis"><em>x</em></span>. So if you wish you can just add the function to approximate
  75         as a new variant after the existing examples.
  76       </p>
  77 <p>
  78         In addition to those two files, the program needs to be linked to a <a class="link" href="../high_precision/use_ntl.html" title="Using NTL Library">patched NTL library to compile</a>.
  79       </p>
  80 <p>
  81         Note that the function <span class="emphasis"><em>f</em></span> must return the rational part
  82         of the approximation: for example if you are approximating a function <span class="emphasis"><em>f(x)</em></span>
  83         then it is quite common to use:
  84       </p>
  85 <div class="blockquote"><blockquote class="blockquote"><p>
  86           <span class="serif_italic">f(x) = g(x)(Y + R(x))</span>
  87         </p></blockquote></div>
  88 <p>
  89         where <span class="emphasis"><em>g(x)</em></span> is the dominant part of <span class="emphasis"><em>f(x)</em></span>,
  90         <span class="emphasis"><em>Y</em></span> is some constant, and <span class="emphasis"><em>R(x)</em></span> is
  91         the rational approximation part, usually optimised for a low absolute error
  92         compared to |Y|.
  93       </p>
  94 <p>
  95         In this case you would define <span class="emphasis"><em>f</em></span> to return <span class="serif-italic">f(x)/g(x)</span>
  96         and then set the y-offset of the approximation to <span class="emphasis"><em>Y</em></span>
  97         (see command line options below).
  98       </p>
  99 <p>
 100         Many other forms are possible, but in all cases the objective is to split
 101         <span class="emphasis"><em>f(x)</em></span> into a dominant part that you can evaluate easily
 102         using standard math functions, and a smooth and slowly changing rational
 103         approximation part. Refer to your favourite textbook for more examples.
 104       </p>
 105 <p>
 106         Command line options for the program are as follows:
 107       </p>
 108 <div class="variablelist">
 109 <p class="title"><b></b></p>
 110 <dl class="variablelist">
 111 <dt><span class="term">variant N</span></dt>
 112 <dd><p>
 113               Sets the current function variant to N. This allows multiple functions
 114               that are to be approximated to be compiled into the same executable.
 115               Defaults to 0.
 116             </p></dd>
 117 <dt><span class="term">range a b</span></dt>
 118 <dd><p>
 119               Sets the domain for the approximation to the range [a,b], defaults
 120               to [0,1].
 121             </p></dd>
 122 <dt><span class="term">relative</span></dt>
 123 <dd><p>
 124               Sets the Remez code to optimise for relative error. This is the default
 125               at program startup. Note that relative error can only be used if f(x)
 126               has no roots over the range being optimised.
 127             </p></dd>
 128 <dt><span class="term">absolute</span></dt>
 129 <dd><p>
 130               Sets the Remez code to optimise for absolute error.
 131             </p></dd>
 132 <dt><span class="term">pin [true|false]</span></dt>
 133 <dd><p>
 134               "Pins" the code so that the rational approximation passes
 135               through the origin. Obviously only set this to <span class="emphasis"><em>true</em></span>
 136               if R(0) must be zero. This is typically used when trying to preserve
 137               a root at [0,0] while also optimising for relative error.
 138             </p></dd>
 139 <dt><span class="term">order N D</span></dt>
 140 <dd><p>
 141               Sets the order of the approximation to <span class="emphasis"><em>N</em></span> in the
 142               numerator and <span class="emphasis"><em>D</em></span> in the denominator. If <span class="emphasis"><em>D</em></span>
 143               is zero then the result will be a polynomial approximation. There will
 144               be N+D+2 coefficients in total, the first coefficient of the numerator
 145               is zero if <span class="emphasis"><em>pin</em></span> was set to true, and the first
 146               coefficient of the denominator is always one.
 147             </p></dd>
 148 <dt><span class="term">working-precision N</span></dt>
 149 <dd><p>
 150               Sets the working precision of NTL::RR to <span class="emphasis"><em>N</em></span> binary
 151               digits. Defaults to 250.
 152             </p></dd>
 153 <dt><span class="term">target-precision N</span></dt>
 154 <dd><p>
 155               Sets the precision of printed output to <span class="emphasis"><em>N</em></span> binary
 156               digits: set to the same number of digits as the type that will be used
 157               to evaluate the approximation. Defaults to 53 (for double precision).
 158             </p></dd>
 159 <dt><span class="term">skew val</span></dt>
 160 <dd><p>
 161               "Skews" the initial interpolated control points towards one
 162               end or the other of the range. Positive values skew the initial control
 163               points towards the left hand side of the range, and negative values
 164               towards the right hand side. If an approximation won't converge (a
 165               common situation) try adjusting the skew parameter until the first
 166               step yields the smallest possible error. <span class="emphasis"><em>val</em></span> should
 167               be in the range [-100,+100], the default is zero.
 168             </p></dd>
 169 <dt><span class="term">brake val</span></dt>
 170 <dd><p>
 171               Sets a brake on each step so that the change in the control points
 172               is braked by <span class="emphasis"><em>val%</em></span>. Defaults to 50, try a higher
 173               value if an approximation won't converge, or a lower value to get speedier
 174               convergence.
 175             </p></dd>
 176 <dt><span class="term">x-offset val</span></dt>
 177 <dd><p>
 178               Sets the x-offset to <span class="emphasis"><em>val</em></span>: the approximation will
 179               be generated for <code class="computeroutput"><span class="identifier">f</span><span class="special">(</span><span class="identifier">S</span> <span class="special">*</span> <span class="special">(</span><span class="identifier">x</span> <span class="special">+</span> <span class="identifier">X</span><span class="special">))</span> <span class="special">+</span> <span class="identifier">Y</span></code>
 180               where <span class="emphasis"><em>X</em></span> is the x-offset, <span class="emphasis"><em>S</em></span>
 181               is the x-scale and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults
 182               to zero. To avoid rounding errors, take care to specify a value that
 183               can be exactly represented as a floating point number.
 184             </p></dd>
 185 <dt><span class="term">x-scale val</span></dt>
 186 <dd><p>
 187               Sets the x-scale to <span class="emphasis"><em>val</em></span>: the approximation will
 188               be generated for <code class="computeroutput"><span class="identifier">f</span><span class="special">(</span><span class="identifier">S</span> <span class="special">*</span> <span class="special">(</span><span class="identifier">x</span> <span class="special">+</span> <span class="identifier">X</span><span class="special">))</span> <span class="special">+</span> <span class="identifier">Y</span></code>
 189               where <span class="emphasis"><em>S</em></span> is the x-scale, <span class="emphasis"><em>X</em></span>
 190               is the x-offset and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults
 191               to one. To avoid rounding errors, take care to specify a value that
 192               can be exactly represented as a floating point number.
 193             </p></dd>
 194 <dt><span class="term">y-offset val</span></dt>
 195 <dd><p>
 196               Sets the y-offset to <span class="emphasis"><em>val</em></span>: the approximation will
 197               be generated for <code class="computeroutput"><span class="identifier">f</span><span class="special">(</span><span class="identifier">S</span> <span class="special">*</span> <span class="special">(</span><span class="identifier">x</span> <span class="special">+</span> <span class="identifier">X</span><span class="special">))</span> <span class="special">+</span> <span class="identifier">Y</span></code>
 198               where <span class="emphasis"><em>X</em></span> is the x-offset, <span class="emphasis"><em>S</em></span>
 199               is the x-scale and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults
 200               to zero. To avoid rounding errors, take care to specify a value that
 201               can be exactly represented as a floating point number.
 202             </p></dd>
 203 <dt><span class="term">y-offset auto</span></dt>
 204 <dd><p>
 205               Sets the y-offset to the average value of f(x) evaluated at the two
 206               endpoints of the range plus the midpoint of the range. The calculated
 207               value is deliberately truncated to <span class="emphasis"><em>float</em></span> precision
 208               (and should be stored as a <span class="emphasis"><em>float</em></span> in your code).
 209               The approximation will be generated for <code class="computeroutput"><span class="identifier">f</span><span class="special">(</span><span class="identifier">x</span> <span class="special">+</span> <span class="identifier">X</span><span class="special">)</span> <span class="special">+</span> <span class="identifier">Y</span></code> where <span class="emphasis"><em>X</em></span> is
 210               the x-offset and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults to
 211               zero.
 212             </p></dd>
 213 <dt><span class="term">graph N</span></dt>
 214 <dd><p>
 215               Prints N evaluations of f(x) at evenly spaced points over the range
 216               being optimised. If unspecified then <span class="emphasis"><em>N</em></span> defaults
 217               to 3. Use to check that f(x) is indeed smooth over the range of interest.
 218             </p></dd>
 219 <dt><span class="term">step N</span></dt>
 220 <dd><p>
 221               Performs <span class="emphasis"><em>N</em></span> steps, or one step if <span class="emphasis"><em>N</em></span>
 222               is unspecified. After each step prints: the peek error at the extrema
 223               of the error function of the approximation, the theoretical error term
 224               solved for on the last step, and the maximum relative change in the
 225               location of the Chebyshev control points. The approximation is converged
 226               on the minimax solution when the two error terms are (approximately)
 227               equal, and the change in the control points has decreased to a suitably
 228               small value.
 229             </p></dd>
 230 <dt><span class="term">test [float|double|long]</span></dt>
 231 <dd><p>
 232               Tests the current approximation at float, double, or long double precision.
 233               Useful to check for rounding errors in evaluating the approximation
 234               at fixed precision. Tests are conducted at the extrema of the error
 235               function of the approximation, and at the zeros of the error function.
 236             </p></dd>
 237 <dt><span class="term">test [float|double|long] N</span></dt>
 238 <dd><p>
 239               Tests the current approximation at float, double, or long double precision.
 240               Useful to check for rounding errors in evaluating the approximation
 241               at fixed precision. Tests are conducted at N evenly spaced points over
 242               the range of the approximation. If none of [float|double|long] are
 243               specified then tests using NTL::RR, this can be used to obtain the
 244               error function of the approximation.
 245             </p></dd>
 246 <dt><span class="term">rescale a b</span></dt>
 247 <dd><p>
 248               Takes the current Chebeshev control points, and rescales them over
 249               a new interval [a,b]. Sometimes this can be used to obtain starting
 250               control points for an approximation that can not otherwise be converged.
 251             </p></dd>
 252 <dt><span class="term">rotate</span></dt>
 253 <dd><p>
 254               Moves one term from the numerator to the denominator, but keeps the
 255               Chebyshev control points the same. Sometimes this can be used to obtain
 256               starting control points for an approximation that can not otherwise
 257               be converged.
 258             </p></dd>
 259 <dt><span class="term">info</span></dt>
 260 <dd><p>
 261               Prints out the current approximation: the location of the zeros of
 262               the error function, the location of the Chebyshev control points, the
 263               x and y offsets, and of course the coefficients of the polynomials.
 264             </p></dd>
 265 </dl>
 266 </div>
 267 </div>
 268 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 269 <td align="left"></td>
 270 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2019 Nikhar
 271       Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos,
 272       Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan
 273       R&#229;de, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg,
 274       Daryle Walker and Xiaogang Zhang<p>
 275         Distributed under the Boost Software License, Version 1.0. (See accompanying
 276         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 277       </p>
 278 </div></td>
 279 </tr></table>
 280 <hr>
 281 <div class="spirit-nav">
 282 <a accesskey="p" href="tuples.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="error_test.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 283 </div>
 284 </body>
 285 </html>