ceph/src/boost/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.77.1">
   7 <link rel="home" href="../../index.html" title="Math Toolkit 2.5.1">
   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 libs/math/minimax contains a command line driven program for
  32         the generation of minimax approximations using the Remez algorithm. Both
  33         polynomial and rational approximations are supported, although the latter
  34         are tricky to converge: it is not uncommon for convergence of rational forms
  35         to fail. No such limitations are present for polynomial approximations which
  36         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 <pre class="programlisting"><span class="identifier">f</span><span class="special">(</span><span class="identifier">x</span><span class="special">)</span> <span class="special">=</span> <span class="identifier">g</span><span class="special">(</span><span class="identifier">x</span><span class="special">)(</span><span class="identifier">Y</span> <span class="special">+</span> <span class="identifier">R</span><span class="special">(</span><span class="identifier">x</span><span class="special">))</span>
  86 </pre>
  87 <p>
  88         where <span class="emphasis"><em>g(x)</em></span> is the dominant part of <span class="emphasis"><em>f(x)</em></span>,
  89         <span class="emphasis"><em>Y</em></span> is some constant, and <span class="emphasis"><em>R(x)</em></span> is
  90         the rational approximation part, usually optimised for a low absolute error
  91         compared to |Y|.
  92       </p>
  93 <p>
  94         In this case you would define <span class="emphasis"><em>f</em></span> to return <span class="emphasis"><em>f(x)/g(x)</em></span>
  95         and then set the y-offset of the approximation to <span class="emphasis"><em>Y</em></span>
  96         (see command line options below).
  97       </p>
  98 <p>
  99         Many other forms are possible, but in all cases the objective is to split
 100         <span class="emphasis"><em>f(x)</em></span> into a dominant part that you can evaluate easily
 101         using standard math functions, and a smooth and slowly changing rational
 102         approximation part. Refer to your favourite textbook for more examples.
 103       </p>
 104 <p>
 105         Command line options for the program are as follows:
 106       </p>
 107 <div class="variablelist">
 108 <p class="title"><b></b></p>
 109 <dl class="variablelist">
 110 <dt><span class="term">variant N</span></dt>
 111 <dd><p>
 112               Sets the current function variant to N. This allows multiple functions
 113               that are to be approximated to be compiled into the same executable.
 114               Defaults to 0.
 115             </p></dd>
 116 <dt><span class="term">range a b</span></dt>
 117 <dd><p>
 118               Sets the domain for the approximation to the range [a,b], defaults
 119               to [0,1].
 120             </p></dd>
 121 <dt><span class="term">relative</span></dt>
 122 <dd><p>
 123               Sets the Remez code to optimise for relative error. This is the default
 124               at program startup. Note that relative error can only be used if f(x)
 125               has no roots over the range being optimised.
 126             </p></dd>
 127 <dt><span class="term">absolute</span></dt>
 128 <dd><p>
 129               Sets the Remez code to optimise for absolute error.
 130             </p></dd>
 131 <dt><span class="term">pin [true|false]</span></dt>
 132 <dd><p>
 133               "Pins" the code so that the rational approximation passes
 134               through the origin. Obviously only set this to <span class="emphasis"><em>true</em></span>
 135               if R(0) must be zero. This is typically used when trying to preserve
 136               a root at [0,0] while also optimising for relative error.
 137             </p></dd>
 138 <dt><span class="term">order N D</span></dt>
 139 <dd><p>
 140               Sets the order of the approximation to <span class="emphasis"><em>N</em></span> in the
 141               numerator and <span class="emphasis"><em>D</em></span> in the denominator. If <span class="emphasis"><em>D</em></span>
 142               is zero then the result will be a polynomial approximation. There will
 143               be N+D+2 coefficients in total, the first coefficient of the numerator
 144               is zero if <span class="emphasis"><em>pin</em></span> was set to true, and the first
 145               coefficient of the denominator is always one.
 146             </p></dd>
 147 <dt><span class="term">working-precision N</span></dt>
 148 <dd><p>
 149               Sets the working precision of NTL::RR to <span class="emphasis"><em>N</em></span> binary
 150               digits. Defaults to 250.
 151             </p></dd>
 152 <dt><span class="term">target-precision N</span></dt>
 153 <dd><p>
 154               Sets the precision of printed output to <span class="emphasis"><em>N</em></span> binary
 155               digits: set to the same number of digits as the type that will be used
 156               to evaluate the approximation. Defaults to 53 (for double precision).
 157             </p></dd>
 158 <dt><span class="term">skew val</span></dt>
 159 <dd><p>
 160               "Skews" the initial interpolated control points towards one
 161               end or the other of the range. Positive values skew the initial control
 162               points towards the left hand side of the range, and negative values
 163               towards the right hand side. If an approximation won't converge (a
 164               common situation) try adjusting the skew parameter until the first
 165               step yields the smallest possible error. <span class="emphasis"><em>val</em></span> should
 166               be in the range [-100,+100], the default is zero.
 167             </p></dd>
 168 <dt><span class="term">brake val</span></dt>
 169 <dd><p>
 170               Sets a brake on each step so that the change in the control points
 171               is braked by <span class="emphasis"><em>val%</em></span>. Defaults to 50, try a higher
 172               value if an approximation won't converge, or a lower value to get speedier
 173               convergence.
 174             </p></dd>
 175 <dt><span class="term">x-offset val</span></dt>
 176 <dd><p>
 177               Sets the x-offset to <span class="emphasis"><em>val</em></span>: the approximation will
 178               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>
 179               where <span class="emphasis"><em>X</em></span> is the x-offset, <span class="emphasis"><em>S</em></span>
 180               is the x-scale and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults
 181               to zero. To avoid rounding errors, take care to specify a value that
 182               can be exactly represented as a floating point number.
 183             </p></dd>
 184 <dt><span class="term">x-scale val</span></dt>
 185 <dd><p>
 186               Sets the x-scale to <span class="emphasis"><em>val</em></span>: the approximation will
 187               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>
 188               where <span class="emphasis"><em>S</em></span> is the x-scale, <span class="emphasis"><em>X</em></span>
 189               is the x-offset and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults
 190               to one. To avoid rounding errors, take care to specify a value that
 191               can be exactly represented as a floating point number.
 192             </p></dd>
 193 <dt><span class="term">y-offset val</span></dt>
 194 <dd><p>
 195               Sets the y-offset to <span class="emphasis"><em>val</em></span>: the approximation will
 196               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>
 197               where <span class="emphasis"><em>X</em></span> is the x-offset, <span class="emphasis"><em>S</em></span>
 198               is the x-scale and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults
 199               to zero. To avoid rounding errors, take care to specify a value that
 200               can be exactly represented as a floating point number.
 201             </p></dd>
 202 <dt><span class="term">y-offset auto</span></dt>
 203 <dd><p>
 204               Sets the y-offset to the average value of f(x) evaluated at the two
 205               endpoints of the range plus the midpoint of the range. The calculated
 206               value is deliberately truncated to <span class="emphasis"><em>float</em></span> precision
 207               (and should be stored as a <span class="emphasis"><em>float</em></span> in your code).
 208               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
 209               the x-offset and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults to
 210               zero.
 211             </p></dd>
 212 <dt><span class="term">graph N</span></dt>
 213 <dd><p>
 214               Prints N evaluations of f(x) at evenly spaced points over the range
 215               being optimised. If unspecified then <span class="emphasis"><em>N</em></span> defaults
 216               to 3. Use to check that f(x) is indeed smooth over the range of interest.
 217             </p></dd>
 218 <dt><span class="term">step N</span></dt>
 219 <dd><p>
 220               Performs <span class="emphasis"><em>N</em></span> steps, or one step if <span class="emphasis"><em>N</em></span>
 221               is unspecified. After each step prints: the peek error at the extrema
 222               of the error function of the approximation, the theoretical error term
 223               solved for on the last step, and the maximum relative change in the
 224               location of the Chebyshev control points. The approximation is converged
 225               on the minimax solution when the two error terms are (approximately)
 226               equal, and the change in the control points has decreased to a suitably
 227               small value.
 228             </p></dd>
 229 <dt><span class="term">test [float|double|long]</span></dt>
 230 <dd><p>
 231               Tests the current approximation at float, double, or long double precision.
 232               Useful to check for rounding errors in evaluating the approximation
 233               at fixed precision. Tests are conducted at the extrema of the error
 234               function of the approximation, and at the zeros of the error function.
 235             </p></dd>
 236 <dt><span class="term">test [float|double|long] N</span></dt>
 237 <dd><p>
 238               Tests the current approximation at float, double, or long double precision.
 239               Useful to check for rounding errors in evaluating the approximation
 240               at fixed precision. Tests are conducted at N evenly spaced points over
 241               the range of the approximation. If none of [float|double|long] are
 242               specified then tests using NTL::RR, this can be used to obtain the
 243               error function of the approximation.
 244             </p></dd>
 245 <dt><span class="term">rescale a b</span></dt>
 246 <dd><p>
 247               Takes the current Chebeshev control points, and rescales them over
 248               a new interval [a,b]. Sometimes this can be used to obtain starting
 249               control points for an approximation that can not otherwise be converged.
 250             </p></dd>
 251 <dt><span class="term">rotate</span></dt>
 252 <dd><p>
 253               Moves one term from the numerator to the denominator, but keeps the
 254               Chebyshev control points the same. Sometimes this can be used to obtain
 255               starting control points for an approximation that can not otherwise
 256               be converged.
 257             </p></dd>
 258 <dt><span class="term">info</span></dt>
 259 <dd><p>
 260               Prints out the current approximation: the location of the zeros of
 261               the error function, the location of the Chebyshev control points, the
 262               x and y offsets, and of course the coefficients of the polynomials.
 263             </p></dd>
 264 </dl>
 265 </div>
 266 </div>
 267 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 268 <td align="left"></td>
 269 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2010, 2012-2014 Nikhar Agrawal,
 270       Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
 271       Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan R&#229;de, Gautam Sewani,
 272       Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p>
 273         Distributed under the Boost Software License, Version 1.0. (See accompanying
 274         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>)
 275       </p>
 276 </div></td>
 277 </tr></table>
 278 <hr>
 279 <div class="spirit-nav">
 280 <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>
 281 </div>
 282 </body>
 283 </html>