| <html> |
| <head> |
| <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> |
| <title>Minimax Approximations and the Remez Algorithm</title> |
| <link rel="stylesheet" href="../../math.css" type="text/css"> |
| <meta name="generator" content="DocBook XSL Stylesheets V1.77.1"> |
| <link rel="home" href="../../index.html" title="Math Toolkit 2.2.0"> |
| <link rel="up" href="../internals2.html" title="Testing and Development"> |
| <link rel="prev" href="polynomials.html" title="Polynomials"> |
| <link rel="next" href="error_test.html" title="Relative Error and Testing"> |
| </head> |
| <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> |
| <table cellpadding="2" width="100%"><tr> |
| <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td> |
| <td align="center"><a href="../../../../../../index.html">Home</a></td> |
| <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td> |
| <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> |
| <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> |
| <td align="center"><a href="../../../../../../more/index.htm">More</a></td> |
| </tr></table> |
| <hr> |
| <div class="spirit-nav"> |
| <a accesskey="p" href="polynomials.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals2.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> |
| </div> |
| <div class="section"> |
| <div class="titlepage"><div><div><h3 class="title"> |
| <a name="math_toolkit.internals2.minimax"></a><a class="link" href="minimax.html" title="Minimax Approximations and the Remez Algorithm">Minimax Approximations |
| and the Remez Algorithm</a> |
| </h3></div></div></div> |
| <p> |
| The directory libs/math/minimax contains a command line driven program for |
| the generation of minimax approximations using the Remez algorithm. Both |
| polynomial and rational approximations are supported, although the latter |
| are tricky to converge: it is not uncommon for convergence of rational forms |
| to fail. No such limitations are present for polynomial approximations which |
| should always converge smoothly. |
| </p> |
| <p> |
| It's worth stressing that developing rational approximations to functions |
| is often not an easy task, and one to which many books have been devoted. |
| To use this tool, you will need to have a reasonable grasp of what the Remez |
| algorithm is, and the general form of the approximation you want to achieve. |
| </p> |
| <p> |
| Unless you already familar with the Remez method, you should first read the |
| <a class="link" href="../remez.html" title="The Remez Method">brief background article explaining the |
| principles behind the Remez algorithm</a>. |
| </p> |
| <p> |
| The program consists of two parts: |
| </p> |
| <div class="variablelist"> |
| <p class="title"><b></b></p> |
| <dl class="variablelist"> |
| <dt><span class="term">main.cpp</span></dt> |
| <dd><p> |
| Contains the command line parser, and all the calls to the Remez code. |
| </p></dd> |
| <dt><span class="term">f.cpp</span></dt> |
| <dd><p> |
| Contains the function to approximate. |
| </p></dd> |
| </dl> |
| </div> |
| <p> |
| Therefore to use this tool, you must modify f.cpp to return the function |
| to approximate. The tools supports multiple function approximations within |
| the same compiled program: each as a separate variant: |
| </p> |
| <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">&</span> <span class="identifier">x</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">variant</span><span class="special">);</span> |
| </pre> |
| <p> |
| Returns the value of the function <span class="emphasis"><em>variant</em></span> at point |
| <span class="emphasis"><em>x</em></span>. So if you wish you can just add the function to approximate |
| as a new variant after the existing examples. |
| </p> |
| <p> |
| 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>. |
| </p> |
| <p> |
| Note that the function <span class="emphasis"><em>f</em></span> must return the rational part |
| of the approximation: for example if you are approximating a function <span class="emphasis"><em>f(x)</em></span> |
| then it is quite common to use: |
| </p> |
| <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> |
| </pre> |
| <p> |
| where <span class="emphasis"><em>g(x)</em></span> is the dominant part of <span class="emphasis"><em>f(x)</em></span>, |
| <span class="emphasis"><em>Y</em></span> is some constant, and <span class="emphasis"><em>R(x)</em></span> is |
| the rational approximation part, usually optimised for a low absolute error |
| compared to |Y|. |
| </p> |
| <p> |
| 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> |
| and then set the y-offset of the approximation to <span class="emphasis"><em>Y</em></span> |
| (see command line options below). |
| </p> |
| <p> |
| Many other forms are possible, but in all cases the objective is to split |
| <span class="emphasis"><em>f(x)</em></span> into a dominant part that you can evaluate easily |
| using standard math functions, and a smooth and slowly changing rational |
| approximation part. Refer to your favourite textbook for more examples. |
| </p> |
| <p> |
| Command line options for the program are as follows: |
| </p> |
| <div class="variablelist"> |
| <p class="title"><b></b></p> |
| <dl class="variablelist"> |
| <dt><span class="term">variant N</span></dt> |
| <dd><p> |
| Sets the current function variant to N. This allows multiple functions |
| that are to be approximated to be compiled into the same executable. |
| Defaults to 0. |
| </p></dd> |
| <dt><span class="term">range a b</span></dt> |
| <dd><p> |
| Sets the domain for the approximation to the range [a,b], defaults |
| to [0,1]. |
| </p></dd> |
| <dt><span class="term">relative</span></dt> |
| <dd><p> |
| Sets the Remez code to optimise for relative error. This is the default |
| at program startup. Note that relative error can only be used if f(x) |
| has no roots over the range being optimised. |
| </p></dd> |
| <dt><span class="term">absolute</span></dt> |
| <dd><p> |
| Sets the Remez code to optimise for absolute error. |
| </p></dd> |
| <dt><span class="term">pin [true|false]</span></dt> |
| <dd><p> |
| "Pins" the code so that the rational approximation passes |
| through the origin. Obviously only set this to <span class="emphasis"><em>true</em></span> |
| if R(0) must be zero. This is typically used when trying to preserve |
| a root at [0,0] while also optimising for relative error. |
| </p></dd> |
| <dt><span class="term">order N D</span></dt> |
| <dd><p> |
| Sets the order of the approximation to <span class="emphasis"><em>N</em></span> in the |
| numerator and <span class="emphasis"><em>D</em></span> in the denominator. If <span class="emphasis"><em>D</em></span> |
| is zero then the result will be a polynomial approximation. There will |
| be N+D+2 coefficients in total, the first coefficient of the numerator |
| is zero if <span class="emphasis"><em>pin</em></span> was set to true, and the first |
| coefficient of the denominator is always one. |
| </p></dd> |
| <dt><span class="term">working-precision N</span></dt> |
| <dd><p> |
| Sets the working precision of NTL::RR to <span class="emphasis"><em>N</em></span> binary |
| digits. Defaults to 250. |
| </p></dd> |
| <dt><span class="term">target-precision N</span></dt> |
| <dd><p> |
| Sets the precision of printed output to <span class="emphasis"><em>N</em></span> binary |
| digits: set to the same number of digits as the type that will be used |
| to evaluate the approximation. Defaults to 53 (for double precision). |
| </p></dd> |
| <dt><span class="term">skew val</span></dt> |
| <dd><p> |
| "Skews" the initial interpolated control points towards one |
| end or the other of the range. Positive values skew the initial control |
| points towards the left hand side of the range, and negative values |
| towards the right hand side. If an approximation won't converge (a |
| common situation) try adjusting the skew parameter until the first |
| step yields the smallest possible error. <span class="emphasis"><em>val</em></span> should |
| be in the range [-100,+100], the default is zero. |
| </p></dd> |
| <dt><span class="term">brake val</span></dt> |
| <dd><p> |
| Sets a brake on each step so that the change in the control points |
| is braked by <span class="emphasis"><em>val%</em></span>. Defaults to 50, try a higher |
| value if an approximation won't converge, or a lower value to get speedier |
| convergence. |
| </p></dd> |
| <dt><span class="term">x-offset val</span></dt> |
| <dd><p> |
| Sets the x-offset to <span class="emphasis"><em>val</em></span>: the approximation will |
| 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> |
| where <span class="emphasis"><em>X</em></span> is the x-offset, <span class="emphasis"><em>S</em></span> |
| is the x-scale and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults |
| to zero. To avoid rounding errors, take care to specify a value that |
| can be exactly represented as a floating point number. |
| </p></dd> |
| <dt><span class="term">x-scale val</span></dt> |
| <dd><p> |
| Sets the x-scale to <span class="emphasis"><em>val</em></span>: the approximation will |
| 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> |
| where <span class="emphasis"><em>S</em></span> is the x-scale, <span class="emphasis"><em>X</em></span> |
| is the x-offset and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults |
| to one. To avoid rounding errors, take care to specify a value that |
| can be exactly represented as a floating point number. |
| </p></dd> |
| <dt><span class="term">y-offset val</span></dt> |
| <dd><p> |
| Sets the y-offset to <span class="emphasis"><em>val</em></span>: the approximation will |
| 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> |
| where <span class="emphasis"><em>X</em></span> is the x-offset, <span class="emphasis"><em>S</em></span> |
| is the x-scale and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults |
| to zero. To avoid rounding errors, take care to specify a value that |
| can be exactly represented as a floating point number. |
| </p></dd> |
| <dt><span class="term">y-offset auto</span></dt> |
| <dd><p> |
| Sets the y-offset to the average value of f(x) evaluated at the two |
| endpoints of the range plus the midpoint of the range. The calculated |
| value is deliberately truncated to <span class="emphasis"><em>float</em></span> precision |
| (and should be stored as a <span class="emphasis"><em>float</em></span> in your code). |
| 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 |
| the x-offset and <span class="emphasis"><em>Y</em></span> is the y-offset. Defaults to |
| zero. |
| </p></dd> |
| <dt><span class="term">graph N</span></dt> |
| <dd><p> |
| Prints N evaluations of f(x) at evenly spaced points over the range |
| being optimised. If unspecified then <span class="emphasis"><em>N</em></span> defaults |
| to 3. Use to check that f(x) is indeed smooth over the range of interest. |
| </p></dd> |
| <dt><span class="term">step N</span></dt> |
| <dd><p> |
| Performs <span class="emphasis"><em>N</em></span> steps, or one step if <span class="emphasis"><em>N</em></span> |
| is unspecified. After each step prints: the peek error at the extrema |
| of the error function of the approximation, the theoretical error term |
| solved for on the last step, and the maximum relative change in the |
| location of the Chebyshev control points. The approximation is converged |
| on the minimax solution when the two error terms are (approximately) |
| equal, and the change in the control points has decreased to a suitably |
| small value. |
| </p></dd> |
| <dt><span class="term">test [float|double|long]</span></dt> |
| <dd><p> |
| Tests the current approximation at float, double, or long double precision. |
| Useful to check for rounding errors in evaluating the approximation |
| at fixed precision. Tests are conducted at the extrema of the error |
| function of the approximation, and at the zeros of the error function. |
| </p></dd> |
| <dt><span class="term">test [float|double|long] N</span></dt> |
| <dd><p> |
| Tests the current approximation at float, double, or long double precision. |
| Useful to check for rounding errors in evaluating the approximation |
| at fixed precision. Tests are conducted at N evenly spaced points over |
| the range of the approximation. If none of [float|double|long] are |
| specified then tests using NTL::RR, this can be used to obtain the |
| error function of the approximation. |
| </p></dd> |
| <dt><span class="term">rescale a b</span></dt> |
| <dd><p> |
| Takes the current Chebeshev control points, and rescales them over |
| a new interval [a,b]. Sometimes this can be used to obtain starting |
| control points for an approximation that can not otherwise be converged. |
| </p></dd> |
| <dt><span class="term">rotate</span></dt> |
| <dd><p> |
| Moves one term from the numerator to the denominator, but keeps the |
| Chebyshev control points the same. Sometimes this can be used to obtain |
| starting control points for an approximation that can not otherwise |
| be converged. |
| </p></dd> |
| <dt><span class="term">info</span></dt> |
| <dd><p> |
| Prints out the current approximation: the location of the zeros of |
| the error function, the location of the Chebyshev control points, the |
| x and y offsets, and of course the coefficients of the polynomials. |
| </p></dd> |
| </dl> |
| </div> |
| </div> |
| <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> |
| <td align="left"></td> |
| <td align="right"><div class="copyright-footer">Copyright © 2006-2010, 2012-2014 Nikhar Agrawal, |
| Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert |
| Holin, Bruno Lalande, John Maddock, Johan Råde, Gautam Sewani, Benjamin Sobotta, |
| Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p> |
| Distributed under the Boost Software License, Version 1.0. (See accompanying |
| 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>) |
| </p> |
| </div></td> |
| </tr></table> |
| <hr> |
| <div class="spirit-nav"> |
| <a accesskey="p" href="polynomials.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals2.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> |
| </div> |
| </body> |
| </html> |