1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.12.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 familiar with the Remez method, you should first read 46 the <a class="link" href="../remez.html" title="The Remez Method">brief background article explaining 47 the 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">&</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 © 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å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> 286
