c5-13 (779497)
Текст из файла
204Chapter 5.Evaluation of Functions5.13 Rational Chebyshev ApproximationR(x) ≡p0 + p1 x + · · · + pm xm≈ f (x)1 + q1 x + · · · + qk xkfor a ≤ x ≤ b(5.13.1)The unknown quantities that we need to find are p0 , . . . , pm and q1 , . . . , qk , that is, m + k + 1quantities in all. Let r(x) denote the deviation of R(x) from f (x), and let r denote itsmaximum absolute value,r(x) ≡ R(x) − f (x)r ≡ max |r(x)|a≤x≤b(5.13.2)The ideal minimax solution would be that choice of p’s and q’s that minimizes r. Obviouslythere is some minimax solution, since r is bounded below by zero. How can we find it, ora reasonable approximation to it?A first hint is furnished by the following fundamental theorem: If R(x) is nondegenerate(has no common polynomial factors in numerator and denominator), then there is a uniquechoice of p’s and q’s that minimizes r; for this choice, r(x) has m + k + 2 extrema ina ≤ x ≤ b, all of magnitude r and with alternating sign.
(We have omitted some technicalassumptions in this theorem. See Ralston [1] for a precise statement.) We thus learn that thesituation with rational functions is quite analogous to that for minimax polynomials: In §5.8we saw that the error term of an nth order approximation, with n + 1 Chebyshev coefficients,was generally dominated by the first neglected Chebyshev term, namely Tn+1 , which itselfhas n + 2 extrema of equal magnitude and alternating sign. So, here, the number of rationalcoefficients, m + k + 1, plays the same role of the number of polynomial coefficients, n + 1.A different way to see why r(x) should have m + k + 2 extrema is to note that R(x)can be made exactly equal to f (x) at any m + k + 1 points xi . Multiplying equation (5.13.1)by its denominator gives the equationskp0 + p1 xi + · · · + pm xmi = f (xi )(1 + q1 xi + · · · + qk xi )i = 1, 2, .
. . , m + k + 1(5.13.3)This is a set of m + k + 1 linear equations for the unknown p’s and q’s, which can besolved by standard methods (e.g., LU decomposition). If we choose the xi ’s to all be inthe interval (a, b), then there will generically be an extremum between each chosen xi andxi+1 , plus also extrema where the function goes out of the interval at a and b, for a totalof m + k + 2 extrema. For arbitrary xi ’s, the extrema will not have the same magnitude.The theorem says that, for one particular choice of xi ’s, the magnitudes can be beaten downto the identical, minimal, value of r.Instead of making f (xi ) and R(xi ) equal at the points xi , one can instead force theresidual r(xi ) to any desired values yi by solving the linear equationskp0 + p1 xi + · · · + pm xmi = [f (xi ) − yi ](1 + q1 xi + · · · + qk xi )i = 1, 2, .
. . , m + k + 1(5.13.4)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).In §5.8 and §5.10 we learned how to find good polynomial approximations to a givenfunction f (x) in a given interval a ≤ x ≤ b.
Here, we want to generalize the task to findgood approximations that are rational functions (see §5.3). The reason for doing so is that,for some functions and some intervals, the optimal rational function approximation is ableto achieve substantially higher accuracy than the optimal polynomial approximation with thesame number of coefficients. This must be weighed against the fact that finding a rationalfunction approximation is not as straightforward as finding a polynomial approximation,which, as we saw, could be done elegantly via Chebyshev polynomials.Let the desired rational function R(x) have numerator of degree m and denominatorof degree k.
Then we have5.13 Rational Chebyshev Approximation205In fact, if the xi ’s are chosen to be the extrema (not the zeros) of the minimax solution,then the equations satisfied will bekp0 + p1 xi + · · · + pm xmi = [f (xi ) ± r](1 + q1 xi + · · · + qk xi )i = 1, 2, . . . , m + k + 2(5.13.5)Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).where the ± alternates for the alternating extrema. Notice that equation (5.13.5) is satisfied atm + k + 2 extrema, while equation (5.13.4) was satisfied only at m + k + 1 arbitrary points.How can this be? The answer is that r in equation (5.13.5) is an additional unknown, so thatthe number of both equations and unknowns is m + k + 2.
True, the set is mildly nonlinear(in r), but in general it is still perfectly soluble by methods that we will develop in Chapter 9.We thus see that, given only the locations of the extrema of the minimax rationalfunction, we can solve for its coefficients and maximum deviation.
Additional theorems,leading up to the so-called Remes algorithms [1], tell how to converge to these locations byan iterative process. For example, here is a (slightly simplified) statement of Remes’ SecondAlgorithm: (1) Find an initial rational function with m + k + 2 extrema xi (not having equaldeviation). (2) Solve equation (5.13.5) for new rational coefficients and r. (3) Evaluate theresulting R(x) to find its actual extrema (which will not be the same as the guessed values).(4) Replace each guessed value with the nearest actual extremum of the same sign. (5) Goback to step 2 and iterate to convergence.
Under a broad set of assumptions, this method willconverge. Ralston [1] fills in the necessary details, including how to find the initial set of xi ’s.Up to this point, our discussion has been textbook-standard. We now reveal ourselvesas heretics. We don’t much like the elegant Remes algorithm. Its two nested iterations (onr in the nonlinear set 5.13.5, and on the new sets of xi ’s) are finicky and require a lot ofspecial logic for degenerate cases. Even more heretical, we doubt that compulsive searchingfor the exactly best, equal deviation, approximation is worth the effort — except perhaps forthose few people in the world whose business it is to find optimal approximations that getbuilt into compilers and microchips.When we use rational function approximation, the goal is usually much more pragmatic:Inside some inner loop we are evaluating some function a zillion times, and we want tospeed up its evaluation.
Almost never do we need this function to the last bit of machineaccuracy. Suppose (heresy!) we use an approximation whose error has m + k + 2 extremawhose deviations differ by a factor of 2. The theorems on which the Remes algorithmsare based guarantee that the perfect minimax solution will have extrema somewhere withinthis factor of 2 range – forcing down the higher extrema will cause the lower ones to rise,until all are equal. So our “sloppy” approximation is in fact within a fraction of a leastsignificant bit of the minimax one.That is good enough for us, especially when we have available a very robust methodfor finding the so-called “sloppy” approximation.
Such a method is the least-squares solutionof overdetermined linear equations by singular value decomposition (§2.6 and §15.4). Weproceed as follows: First, solve (in the least-squares sense) equation (5.13.3), not just form + k + 1 values of xi , but for a significantly larger number of xi ’s, spaced approximatelylike the zeros of a high-order Chebyshev polynomial. This gives an initial guess for R(x).Second, tabulate the resulting deviations, find the mean absolute deviation, call it r, and thensolve (again in the least-squares sense) equation (5.13.5) with r fixed and the ± chosen to bethe sign of the observed deviation at each point xi .
Third, repeat the second step a few times.You can spot some Remes orthodoxy lurking in our algorithm: The equations we solveare trying to bring the deviations not to zero, but rather to plus-or-minus some consistentvalue. However, we dispense with keeping track of actual extrema; and we solve only linearequations at each stage. One additional trick is to solve a weighted least-squares problem,where the weights are chosen to beat down the largest deviations fastest.Here is a program implementing these ideas. Notice that the only calls to the function fnoccur in the initial filling of the table fs. You could easily modify the code to do this fillingoutside of the routine.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
