ceph/src/boost/libs/math/doc/html/math_toolkit/remez.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>The Remez Method</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="../backgrounders.html" title="Chapter&#160;17.&#160;Backgrounders">
   9 <link rel="prev" href="lanczos.html" title="The Lanczos Approximation">
  10 <link rel="next" href="refs.html" title="References">
  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="lanczos.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../backgrounders.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="refs.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
  27 <a name="math_toolkit.remez"></a><a class="link" href="remez.html" title="The Remez Method">The Remez Method</a>
  28 </h2></div></div></div>
  29 <p>
  30       The <a href="http://en.wikipedia.org/wiki/Remez_algorithm" target="_top">Remez algorithm</a>
  31       is a methodology for locating the minimax rational approximation to a function.
  32       This short article gives a brief overview of the method, but it should not
  33       be regarded as a thorough theoretical treatment, for that you should consult
  34       your favorite textbook.
  35     </p>
  36 <p>
  37       Imagine that you want to approximate some function f(x) by way of a rational
  38       function R(x), where R(x) may be either a polynomial P(x) or a ratio of two
  39       polynomials P(x)/Q(x) (a rational function). Initially we'll concentrate on
  40       the polynomial case, as it's by far the easier to deal with, later we'll extend
  41       to the full rational function case.
  42     </p>
  43 <p>
  44       We want to find the "best" rational approximation, where "best"
  45       is defined to be the approximation that has the least deviation from f(x).
  46       We can measure the deviation by way of an error function:
  47     </p>
  48 <p>
  49       E<sub>abs</sub>(x) = f(x) - R(x)
  50     </p>
  51 <p>
  52       which is expressed in terms of absolute error, but we can equally use relative
  53       error:
  54     </p>
  55 <p>
  56       E<sub>rel</sub>(x) = (f(x) - R(x)) / |f(x)|
  57     </p>
  58 <p>
  59       And indeed in general we can scale the error function in any way we want, it
  60       makes no difference to the maths, although the two forms above cover almost
  61       every practical case that you're likely to encounter.
  62     </p>
  63 <p>
  64       The minimax rational function R(x) is then defined to be the function that
  65       yields the smallest maximal value of the error function. Chebyshev showed that
  66       there is a unique minimax solution for R(x) that has the following properties:
  67     </p>
  68 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
  69 <li class="listitem">
  70           If R(x) is a polynomial of degree N, then there are N+2 unknowns: the N+1
  71           coefficients of the polynomial, and maximal value of the error function.
  72         </li>
  73 <li class="listitem">
  74           The error function has N+1 roots, and N+2 extrema (minima and maxima).
  75         </li>
  76 <li class="listitem">
  77           The extrema alternate in sign, and all have the same magnitude.
  78         </li>
  79 </ul></div>
  80 <p>
  81       That means that if we know the location of the extrema of the error function
  82       then we can write N+2 simultaneous equations:
  83     </p>
  84 <p>
  85       R(x<sub>i</sub>) + (-1)<sup>i</sup>E = f(x<sub>i</sub>)
  86     </p>
  87 <p>
  88       where E is the maximal error term, and x<sub>i</sub> are the abscissa values of the N+2
  89       extrema of the error function. It is then trivial to solve the simultaneous
  90       equations to obtain the polynomial coefficients and the error term.
  91     </p>
  92 <p>
  93       <span class="emphasis"><em>Unfortunately we don't know where the extrema of the error function
  94       are located!</em></span>
  95     </p>
  96 <h5>
  97 <a name="math_toolkit.remez.h0"></a>
  98       <span class="phrase"><a name="math_toolkit.remez.the_remez_method"></a></span><a class="link" href="remez.html#math_toolkit.remez.the_remez_method">The
  99       Remez Method</a>
 100     </h5>
 101 <p>
 102       The Remez method is an iterative technique which, given a broad range of assumptions,
 103       will converge on the extrema of the error function, and therefore the minimax
 104       solution.
 105     </p>
 106 <p>
 107       In the following discussion we'll use a concrete example to illustrate the
 108       Remez method: an approximation to the function e<sup>x</sup> &#160; over the range [-1, 1].
 109     </p>
 110 <p>
 111       Before we can begin the Remez method, we must obtain an initial value for the
 112       location of the extrema of the error function. We could "guess" these,
 113       but a much closer first approximation can be obtained by first constructing
 114       an interpolated polynomial approximation to f(x).
 115     </p>
 116 <p>
 117       In order to obtain the N+1 coefficients of the interpolated polynomial we need
 118       N+1 points (x<sub>0</sub>...x<sub>N</sub>): with our interpolated form passing through each of those
 119       points that yields N+1 simultaneous equations:
 120     </p>
 121 <p>
 122       f(x<sub>i</sub>) = P(x<sub>i</sub>) = c<sub>0</sub> + c<sub>1</sub>x<sub>i</sub> ... + c<sub>N</sub>x<sub>i</sub><sup>N</sup>
 123     </p>
 124 <p>
 125       Which can be solved for the coefficients c<sub>0</sub>...c<sub>N</sub> in P(x).
 126     </p>
 127 <p>
 128       Obviously this is not a minimax solution, indeed our only guarantee is that
 129       f(x) and P(x) touch at N+1 locations, away from those points the error may
 130       be arbitrarily large. However, we would clearly like this initial approximation
 131       to be as close to f(x) as possible, and it turns out that using the zeros of
 132       an orthogonal polynomial as the initial interpolation points is a good choice.
 133       In our example we'll use the zeros of a Chebyshev polynomial as these are particularly
 134       easy to calculate, interpolating for a polynomial of degree 4, and measuring
 135       <span class="emphasis"><em>relative error</em></span> we get the following error function:
 136     </p>
 137 <p>
 138       <span class="inlinemediaobject"><img src="../../graphs/remez-2.png"></span>
 139     </p>
 140 <p>
 141       Which has a peak relative error of 1.2x10<sup>-3</sup>.
 142     </p>
 143 <p>
 144       While this is a pretty good approximation already, judging by the shape of
 145       the error function we can clearly do better. Before starting on the Remez method
 146       propper, we have one more step to perform: locate all the extrema of the error
 147       function, and store these locations as our initial <span class="emphasis"><em>Chebyshev control
 148       points</em></span>.
 149     </p>
 150 <div class="note"><table border="0" summary="Note">
 151 <tr>
 152 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../doc/src/images/note.png"></td>
 153 <th align="left">Note</th>
 154 </tr>
 155 <tr><td align="left" valign="top">
 156 <p>
 157         In the simple case of a polynomial approximation, by interpolating through
 158         the roots of a Chebyshev polynomial we have in fact created a <span class="emphasis"><em>Chebyshev
 159         approximation</em></span> to the function: in terms of <span class="emphasis"><em>absolute
 160         error</em></span> this is the best a priori choice for the interpolated form
 161         we can achieve, and typically is very close to the minimax solution.
 162       </p>
 163 <p>
 164         However, if we want to optimise for <span class="emphasis"><em>relative error</em></span>,
 165         or if the approximation is a rational function, then the initial Chebyshev
 166         solution can be quite far from the ideal minimax solution.
 167       </p>
 168 <p>
 169         A more technical discussion of the theory involved can be found in this
 170         <a href="http://math.fullerton.edu/mathews/n2003/ChebyshevPolyMod.html" target="_top">online
 171         course</a>.
 172       </p>
 173 </td></tr>
 174 </table></div>
 175 <h5>
 176 <a name="math_toolkit.remez.h1"></a>
 177       <span class="phrase"><a name="math_toolkit.remez.remez_step_1"></a></span><a class="link" href="remez.html#math_toolkit.remez.remez_step_1">Remez
 178       Step 1</a>
 179     </h5>
 180 <p>
 181       The first step in the Remez method, given our current set of N+2 Chebyshev
 182       control points x<sub>i</sub>, is to solve the N+2 simultaneous equations:
 183     </p>
 184 <p>
 185       P(x<sub>i</sub>) + (-1)<sup>i</sup>E = f(x<sub>i</sub>)
 186     </p>
 187 <p>
 188       To obtain the error term E, and the coefficients of the polynomial P(x).
 189     </p>
 190 <p>
 191       This gives us a new approximation to f(x) that has the same error <span class="emphasis"><em>E</em></span>
 192       at each of the control points, and whose error function <span class="emphasis"><em>alternates
 193       in sign</em></span> at the control points. This is still not necessarily the
 194       minimax solution though: since the control points may not be at the extrema
 195       of the error function. After this first step here's what our approximation's
 196       error function looks like:
 197     </p>
 198 <p>
 199       <span class="inlinemediaobject"><img src="../../graphs/remez-3.png"></span>
 200     </p>
 201 <p>
 202       Clearly this is still not the minimax solution since the control points are
 203       not located at the extrema, but the maximum relative error has now dropped
 204       to 5.6x10<sup>-4</sup>.
 205     </p>
 206 <h5>
 207 <a name="math_toolkit.remez.h2"></a>
 208       <span class="phrase"><a name="math_toolkit.remez.remez_step_2"></a></span><a class="link" href="remez.html#math_toolkit.remez.remez_step_2">Remez
 209       Step 2</a>
 210     </h5>
 211 <p>
 212       The second step is to locate the extrema of the new approximation, which we
 213       do in two stages: first, since the error function changes sign at each control
 214       point, we must have N+1 roots of the error function located between each pair
 215       of N+2 control points. Once these roots are found by standard root finding
 216       techniques, we know that N extrema are bracketed between each pair of roots,
 217       plus two more between the endpoints of the range and the first and last roots.
 218       The N+2 extrema can then be found using standard function minimisation techniques.
 219     </p>
 220 <p>
 221       We now have a choice: multi-point exchange, or single point exchange.
 222     </p>
 223 <p>
 224       In single point exchange, we move the control point nearest to the largest
 225       extrema to the absissa value of the extrema.
 226     </p>
 227 <p>
 228       In multi-point exchange we swap all the current control points, for the locations
 229       of the extrema.
 230     </p>
 231 <p>
 232       In our example we perform multi-point exchange.
 233     </p>
 234 <h5>
 235 <a name="math_toolkit.remez.h3"></a>
 236       <span class="phrase"><a name="math_toolkit.remez.iteration"></a></span><a class="link" href="remez.html#math_toolkit.remez.iteration">Iteration</a>
 237     </h5>
 238 <p>
 239       The Remez method then performs steps 1 and 2 above iteratively until the control
 240       points are located at the extrema of the error function: this is then the minimax
 241       solution.
 242     </p>
 243 <p>
 244       For our current example, two more iterations converges on a minimax solution
 245       with a peak relative error of 5x10<sup>-4</sup> and an error function that looks like:
 246     </p>
 247 <p>
 248       <span class="inlinemediaobject"><img src="../../graphs/remez-4.png"></span>
 249     </p>
 250 <h5>
 251 <a name="math_toolkit.remez.h4"></a>
 252       <span class="phrase"><a name="math_toolkit.remez.rational_approximations"></a></span><a class="link" href="remez.html#math_toolkit.remez.rational_approximations">Rational
 253       Approximations</a>
 254     </h5>
 255 <p>
 256       If we wish to extend the Remez method to a rational approximation of the form
 257     </p>
 258 <p>
 259       f(x) = R(x) = P(x) / Q(x)
 260     </p>
 261 <p>
 262       where P(x) and Q(x) are polynomials, then we proceed as before, except that
 263       now we have N+M+2 unknowns if P(x) is of order N and Q(x) is of order M. This
 264       assumes that Q(x) is normalised so that its leading coefficient is 1, giving
 265       N+M+1 polynomial coefficients in total, plus the error term E.
 266     </p>
 267 <p>
 268       The simultaneous equations to be solved are now:
 269     </p>
 270 <p>
 271       P(x<sub>i</sub>) / Q(x<sub>i</sub>) + (-1)<sup>i</sup>E = f(x<sub>i</sub>)
 272     </p>
 273 <p>
 274       Evaluated at the N+M+2 control points x<sub>i</sub>.
 275     </p>
 276 <p>
 277       Unfortunately these equations are non-linear in the error term E: we can only
 278       solve them if we know E, and yet E is one of the unknowns!
 279     </p>
 280 <p>
 281       The method usually adopted to solve these equations is an iterative one: we
 282       guess the value of E, solve the equations to obtain a new value for E (as well
 283       as the polynomial coefficients), then use the new value of E as the next guess.
 284       The method is repeated until E converges on a stable value.
 285     </p>
 286 <p>
 287       These complications extend the running time required for the development of
 288       rational approximations quite considerably. It is often desirable to obtain
 289       a rational rather than polynomial approximation none the less: rational approximations
 290       will often match more difficult to approximate functions, to greater accuracy,
 291       and with greater efficiency, than their polynomial alternatives. For example,
 292       if we takes our previous example of an approximation to e<sup>x</sup>, we obtained 5x10<sup>-4</sup> accuracy
 293       with an order 4 polynomial. If we move two of the unknowns into the denominator
 294       to give a pair of order 2 polynomials, and re-minimise, then the peak relative
 295       error drops to 8.7x10<sup>-5</sup>. That's a 5 fold increase in accuracy, for the same
 296       number of terms overall.
 297     </p>
 298 <h5>
 299 <a name="math_toolkit.remez.h5"></a>
 300       <span class="phrase"><a name="math_toolkit.remez.practical_considerations"></a></span><a class="link" href="remez.html#math_toolkit.remez.practical_considerations">Practical
 301       Considerations</a>
 302     </h5>
 303 <p>
 304       Most treatises on approximation theory stop at this point. However, from a
 305       practical point of view, most of the work involves finding the right approximating
 306       form, and then persuading the Remez method to converge on a solution.
 307     </p>
 308 <p>
 309       So far we have used a direct approximation:
 310     </p>
 311 <p>
 312       f(x) = R(x)
 313     </p>
 314 <p>
 315       But this will converge to a useful approximation only if f(x) is smooth. In
 316       addition round-off errors when evaluating the rational form mean that this
 317       will never get closer than within a few epsilon of machine precision. Therefore
 318       this form of direct approximation is often reserved for situations where we
 319       want efficiency, rather than accuracy.
 320     </p>
 321 <p>
 322       The first step in improving the situation is generally to split f(x) into a
 323       dominant part that we can compute accurately by another method, and a slowly
 324       changing remainder which can be approximated by a rational approximation. We
 325       might be tempted to write:
 326     </p>
 327 <p>
 328       f(x) = g(x) + R(x)
 329     </p>
 330 <p>
 331       where g(x) is the dominant part of f(x), but if f(x)/g(x) is approximately
 332       constant over the interval of interest then:
 333     </p>
 334 <p>
 335       f(x) = g(x)(c + R(x))
 336     </p>
 337 <p>
 338       Will yield a much better solution: here <span class="emphasis"><em>c</em></span> is a constant
 339       that is the approximate value of f(x)/g(x) and R(x) is typically tiny compared
 340       to <span class="emphasis"><em>c</em></span>. In this situation if R(x) is optimised for absolute
 341       error, then as long as its error is small compared to the constant <span class="emphasis"><em>c</em></span>,
 342       that error will effectively get wiped out when R(x) is added to <span class="emphasis"><em>c</em></span>.
 343     </p>
 344 <p>
 345       The difficult part is obviously finding the right g(x) to extract from your
 346       function: often the asymptotic behaviour of the function will give a clue,
 347       so for example the function <a class="link" href="sf_erf/error_function.html" title="Error Functions">erfc</a>
 348       becomes proportional to e<sup>-x<sup>2</sup></sup>/x as x becomes large. Therefore using:
 349     </p>
 350 <p>
 351       erfc(z) = (C + R(x)) e<sup>-x<sup>2</sup></sup>/x
 352     </p>
 353 <p>
 354       as the approximating form seems like an obvious thing to try, and does indeed
 355       yield a useful approximation.
 356     </p>
 357 <p>
 358       However, the difficulty then becomes one of converging the minimax solution.
 359       Unfortunately, it is known that for some functions the Remez method can lead
 360       to divergent behaviour, even when the initial starting approximation is quite
 361       good. Furthermore, it is not uncommon for the solution obtained in the first
 362       Remez step above to be a bad one: the equations to be solved are generally
 363       "stiff", often very close to being singular, and assuming a solution
 364       is found at all, round-off errors and a rapidly changing error function, can
 365       lead to a situation where the error function does not in fact change sign at
 366       each control point as required. If this occurs, it is fatal to the Remez method.
 367       It is also possible to obtain solutions that are perfectly valid mathematically,
 368       but which are quite useless computationally: either because there is an unavoidable
 369       amount of roundoff error in the computation of the rational function, or because
 370       the denominator has one or more roots over the interval of the approximation.
 371       In the latter case while the approximation may have the correct limiting value
 372       at the roots, the approximation is nonetheless useless.
 373     </p>
 374 <p>
 375       Assuming that the approximation does not have any fatal errors, and that the
 376       only issue is converging adequately on the minimax solution, the aim is to
 377       get as close as possible to the minimax solution before beginning the Remez
 378       method. Using the zeros of a Chebyshev polynomial for the initial interpolation
 379       is a good start, but may not be ideal when dealing with relative errors and/or
 380       rational (rather than polynomial) approximations. One approach is to skew the
 381       initial interpolation points to one end: for example if we raise the roots
 382       of the Chebyshev polynomial to a positive power greater than 1 then the roots
 383       will be skewed towards the middle of the [-1,1] interval, while a positive
 384       power less than one will skew them towards either end. More usefully, if we
 385       initially rescale the points over [0,1] and then raise to a positive power,
 386       we can skew them to the left or right. Returning to our example of e<sup>x</sup> &#160; over [-1,1],
 387       the initial interpolated form was some way from the minimax solution:
 388     </p>
 389 <p>
 390       <span class="inlinemediaobject"><img src="../../graphs/remez-2.png"></span>
 391     </p>
 392 <p>
 393       However, if we first skew the interpolation points to the left (rescale them
 394       to [0, 1], raise to the power 1.3, and then rescale back to [-1,1]) we reduce
 395       the error from 1.3x10<sup>-3</sup> &#160;to 6x10<sup>-4</sup>:
 396     </p>
 397 <p>
 398       <span class="inlinemediaobject"><img src="../../graphs/remez-5.png"></span>
 399     </p>
 400 <p>
 401       It's clearly still not ideal, but it is only a few percent away from our desired
 402       minimax solution (5x10<sup>-4</sup>).
 403     </p>
 404 <h5>
 405 <a name="math_toolkit.remez.h6"></a>
 406       <span class="phrase"><a name="math_toolkit.remez.remez_method_checklist"></a></span><a class="link" href="remez.html#math_toolkit.remez.remez_method_checklist">Remez
 407       Method Checklist</a>
 408     </h5>
 409 <p>
 410       The following lists some of the things to check if the Remez method goes wrong,
 411       it is by no means an exhaustive list, but is provided in the hopes that it
 412       will prove useful.
 413     </p>
 414 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 415 <li class="listitem">
 416           Is the function smooth enough? Can it be better separated into a rapidly
 417           changing part, and an asymptotic part?
 418         </li>
 419 <li class="listitem">
 420           Does the function being approximated have any "blips" in it?
 421           Check for problems as the function changes computation method, or if a
 422           root, or an infinity has been divided out. The telltale sign is if there
 423           is a narrow region where the Remez method will not converge.
 424         </li>
 425 <li class="listitem">
 426           Check you have enough accuracy in your calculations: remember that the
 427           Remez method works on the difference between the approximation and the
 428           function being approximated: so you must have more digits of precision
 429           available than the precision of the approximation being constructed. So
 430           for example at double precision, you shouldn't expect to be able to get
 431           better than a float precision approximation.
 432         </li>
 433 <li class="listitem">
 434           Try skewing the initial interpolated approximation to minimise the error
 435           before you begin the Remez steps.
 436         </li>
 437 <li class="listitem">
 438           If the approximation won't converge or is ill-conditioned from one starting
 439           location, try starting from a different location.
 440         </li>
 441 <li class="listitem">
 442           If a rational function won't converge, one can minimise a polynomial (which
 443           presents no problems), then rotate one term from the numerator to the denominator
 444           and minimise again. In theory one can continue moving terms one at a time
 445           from numerator to denominator, and then re-minimising, retaining the last
 446           set of control points at each stage.
 447         </li>
 448 <li class="listitem">
 449           Try using a smaller interval. It may also be possible to optimise over
 450           one (small) interval, rescale the control points over a larger interval,
 451           and then re-minimise.
 452         </li>
 453 <li class="listitem">
 454           Keep absissa values small: use a change of variable to keep the abscissa
 455           over, say [0, b], for some smallish value <span class="emphasis"><em>b</em></span>.
 456         </li>
 457 </ul></div>
 458 <h5>
 459 <a name="math_toolkit.remez.h7"></a>
 460       <span class="phrase"><a name="math_toolkit.remez.references"></a></span><a class="link" href="remez.html#math_toolkit.remez.references">References</a>
 461     </h5>
 462 <p>
 463       The original references for the Remez Method and it's extension to rational
 464       functions are unfortunately in Russian:
 465     </p>
 466 <p>
 467       Remez, E.Ya., <span class="emphasis"><em>Fundamentals of numerical methods for Chebyshev approximations</em></span>,
 468       "Naukova Dumka", Kiev, 1969.
 469     </p>
 470 <p>
 471       Remez, E.Ya., Gavrilyuk, V.T., <span class="emphasis"><em>Computer development of certain approaches
 472       to the approximate construction of solutions of Chebyshev problems nonlinearly
 473       depending on parameters</em></span>, Ukr. Mat. Zh. 12 (1960), 324-338.
 474     </p>
 475 <p>
 476       Gavrilyuk, V.T., <span class="emphasis"><em>Generalization of the first polynomial algorithm
 477       of E.Ya.Remez for the problem of constructing rational-fractional Chebyshev
 478       approximations</em></span>, Ukr. Mat. Zh. 16 (1961), 575-585.
 479     </p>
 480 <p>
 481       Some English language sources include:
 482     </p>
 483 <p>
 484       Fraser, W., Hart, J.F., <span class="emphasis"><em>On the computation of rational approximations
 485       to continuous functions</em></span>, Comm. of the ACM 5 (1962), 401-403, 414.
 486     </p>
 487 <p>
 488       Ralston, A., <span class="emphasis"><em>Rational Chebyshev approximation by Remes' algorithms</em></span>,
 489       Numer.Math. 7 (1965), no. 4, 322-330.
 490     </p>
 491 <p>
 492       A. Ralston, <span class="emphasis"><em>Rational Chebyshev approximation, Mathematical Methods
 493       for Digital Computers v. 2</em></span> (Ralston A., Wilf H., eds.), Wiley, New
 494       York, 1967, pp. 264-284.
 495     </p>
 496 <p>
 497       Hart, J.F. e.a., <span class="emphasis"><em>Computer approximations</em></span>, Wiley, New York
 498       a.o., 1968.
 499     </p>
 500 <p>
 501       Cody, W.J., Fraser, W., Hart, J.F., <span class="emphasis"><em>Rational Chebyshev approximation
 502       using linear equations</em></span>, Numer.Math. 12 (1968), 242-251.
 503     </p>
 504 <p>
 505       Cody, W.J., <span class="emphasis"><em>A survey of practical rational and polynomial approximation
 506       of functions</em></span>, SIAM Review 12 (1970), no. 3, 400-423.
 507     </p>
 508 <p>
 509       Barrar, R.B., Loeb, H.J., <span class="emphasis"><em>On the Remez algorithm for non-linear families</em></span>,
 510       Numer.Math. 15 (1970), 382-391.
 511     </p>
 512 <p>
 513       Dunham, Ch.B., <span class="emphasis"><em>Convergence of the Fraser-Hart algorithm for rational
 514       Chebyshev approximation</em></span>, Math. Comp. 29 (1975), no. 132, 1078-1082.
 515     </p>
 516 <p>
 517       G. L. Litvinov, <span class="emphasis"><em>Approximate construction of rational approximations
 518       and the effect of error autocorrection</em></span>, Russian Journal of Mathematical
 519       Physics, vol.1, No. 3, 1994.
 520     </p>
 521 </div>
 522 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 523 <td align="left"></td>
 524 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2010, 2012-2014 Nikhar Agrawal,
 525       Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert
 526       Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan R&#229;de, Gautam Sewani,
 527       Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p>
 528         Distributed under the Boost Software License, Version 1.0. (See accompanying
 529         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>)
 530       </p>
 531 </div></td>
 532 </tr></table>
 533 <hr>
 534 <div class="spirit-nav">
 535 <a accesskey="p" href="lanczos.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../backgrounders.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="refs.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
 536 </div>
 537 </body>
 538 </html>