c5-12 (779496), страница 2
Текст из файла (страница 2)
and Wilf, H.S. 1960, Mathematical Methods for Digital Computers (New York: Wiley),p. 14.Cuyt, A., and Wuytack, L. 1987, Nonlinear Methods in Numerical Analysis (Amsterdam: NorthHolland), Chapter 2.Graves-Morris, P.R. 1979, in Padé Approximation and Its Applications, Lecture Notes in Mathematics, vol. 765, L. Wuytack, ed. (Berlin: Springer-Verlag). [1]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).void lubksb(float **a, int n, int *indx, float b[]);void ludcmp(float **a, int n, int *indx, float *d);void mprove(float **a, float **alud, int n, int indx[], float b[],float x[]);int j,k,*indx;float d,rr,rrold,sum,**q,**qlu,*x,*y,*z;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 have.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
