]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 17. 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>   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>   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>  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 © 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å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> |