Press, Teukolsly, Vetterling, Flannery - Numerical Recipes in C (523184), страница 33
Текст из файла (страница 33)
xx must be monotonic, either increasing or decreasing. j=0 or j=n is returnedto indicate that x is out of range.{unsigned long ju,jm,jl;int ascnd;}jl=0;Initialize lowerju=n+1;and upper limits.ascnd=(xx[n] >= xx[1]);while (ju-jl > 1) {If we are not yet done,jm=(ju+jl) >> 1;compute a midpoint,if (x >= xx[jm] == ascnd)jl=jm;and replace either the lower limitelseju=jm;or the upper limit, as appropriate.}Repeat until the test condition is satisfied.if (x == xx[1]) *j=1;Then set the outputelse if(x == xx[n]) *j=n-1;else *j=jl;and return.A unit-offset array xx is assumed.
To use locate with a zero-offset array,remember to subtract 1 from the address of xx, and also from the returned value j.Search with Correlated ValuesSometimes you will be in the situation of searching a large table many times,and with nearly identical abscissas on consecutive searches. For example, youmay be generating a function that is used on the right-hand side of a differentialequation: Most differential-equation integrators, as we shall see in Chapter 16, call118Chapter 3.1(a)Interpolation and Extrapolation3264513281(b)hunt phase7 10142238bisection phaseFigure 3.4.1. (a) The routine locate finds a table entry by bisection. Shown here is the sequenceof steps that converge to element 51 in a table of length 64. (b) The routine hunt searches from aprevious known position in the table by increasing steps, then converges by bisection.
Shown here is aparticularly unfavorable example, converging to element 32 from element 7. A favorable example wouldbe convergence to an element near 7, such as 9, which would require just three “hops.”for right-hand side evaluations at points that hop back and forth a bit, but whosetrend moves slowly in the direction of the integration.In such cases it is wasteful to do a full bisection, ab initio, on each call. Thefollowing routine instead starts with a guessed position in the table. It first “hunts,”either up or down, in increments of 1, then 2, then 4, etc., until the desired value isbracketed. Second, it then bisects in the bracketed interval.
At worst, this routine isabout a factor of 2 slower than locate above (if the hunt phase expands to includethe whole table). At best, it can be a factor of log2 n faster than locate, if the desiredpoint is usually quite close to the input guess. Figure 3.4.1 compares the two routines.void hunt(float xx[], unsigned long n, float x, unsigned long *jlo)Given an array xx[1..n], and given a value x, returns a value jlo such that x is betweenxx[jlo] and xx[jlo+1]. xx[1..n] must be monotonic, either increasing or decreasing.jlo=0 or jlo=n is returned to indicate that x is out of range. jlo on input is taken as theinitial guess for jlo on output.{unsigned long jm,jhi,inc;int ascnd;ascnd=(xx[n] >= xx[1]);True if ascending order of table, false otherwise.if (*jlo <= 0 || *jlo > n) {Input guess not useful.
Go immediately to bisec*jlo=0;tion.jhi=n+1;} else {inc=1;Set the hunting increment.if (x >= xx[*jlo] == ascnd) { Hunt up:if (*jlo == n) return;jhi=(*jlo)+1;while (x >= xx[jhi] == ascnd) {Not done hunting,*jlo=jhi;inc += inc;so double the incrementjhi=(*jlo)+inc;if (jhi > n) {Done hunting, since off end of table.jhi=n+1;break;}Try again.3.4 How to Search an Ordered Table119}Done hunting, value bracketed.} else {Hunt down:if (*jlo == 1) {*jlo=0;return;}jhi=(*jlo)--;while (x < xx[*jlo] == ascnd) {Not done hunting,jhi=(*jlo);inc <<= 1;so double the incrementif (inc >= jhi) {Done hunting, since off end of table.*jlo=0;break;}else *jlo=jhi-inc;}and try again.}Done hunting, value bracketed.}Hunt is done, so begin the final bisection phase:while (jhi-(*jlo) != 1) {jm=(jhi+(*jlo)) >> 1;if (x >= xx[jm] == ascnd)*jlo=jm;elsejhi=jm;}if (x == xx[n]) *jlo=n-1;if (x == xx[1]) *jlo=1;}If your array xx is zero-offset, read the comment following locate, above.After the HuntThe problem: Routines locate and hunt return an index j such that yourdesired value lies between table entries xx[j] and xx[j+1], where xx[1..n] is thefull length of the table.
But, to obtain an m-point interpolated value using a routinelike polint (§3.1) or ratint (§3.2), you need to supply much shorter xx and yyarrays, of length m. How do you make the connection?The solution: Calculatek = IMIN(IMAX(j-(m-1)/2,1),n+1-m)(The macros IMIN and IMAX give the minimum and maximum of two integerarguments; see §1.2 and Appendix B.) This expression produces the index of theleftmost member of an m-point set of points centered (insofar as possible) betweenj and j+1, but bounded by 1 at the left and n at the right. C then lets you call theinterpolation routine with array addresses offset by k, e.g.,polint(&xx[k-1],&yy[k-1],m,. .
. )CITED REFERENCES AND FURTHER READING:Knuth, D.E. 1973, Sorting and Searching, vol. 3 of The Art of Computer Programming (Reading,MA: Addison-Wesley), §6.2.1.120Chapter 3.Interpolation and Extrapolation3.5 Coefficients of the Interpolating PolynomialOccasionally you may wish to know not the value of the interpolating polynomialthat passes through a (small!) number of points, but the coefficients of that polynomial. A valid use of the coefficients might be, for example, to computesimultaneous interpolated values of the function and of several of its derivatives (see§5.3), or to convolve a segment of the tabulated function with some other function,where the moments of that other function (i.e., its convolution with powers of x)are known analytically.However, please be certain that the coefficients are what you need.
Generally thecoefficients of the interpolating polynomial can be determined much less accuratelythan its value at a desired abscissa. Therefore it is not a good idea to determine thecoefficients only for use in calculating interpolating values. Values thus calculatedwill not pass exactly through the tabulated points, for example, while valuescomputed by the routines in §3.1–§3.3 will pass exactly through such points.Also, you should not mistake the interpolating polynomial (and its coefficients)for its cousin, the best fit polynomial through a data set. Fitting is a smoothingprocess, since the number of fitted coefficients is typically much less than thenumber of data points.
Therefore, fitted coefficients can be accurately and stablydetermined even in the presence of statistical errors in the tabulated values. (See§14.8.) Interpolation, where the number of coefficients and number of tabulatedpoints are equal, takes the tabulated values as perfect. If they in fact contain statisticalerrors, these can be magnified into oscillations of the interpolating polynomial inbetween the tabulated points.As before, we take the tabulated points to be yi ≡ y(xi ). If the interpolatingpolynomial is written asy = c0 + c1 x + c2 x2 + · · · + cN xN(3.5.1)then the ci ’s are required to satisfy the linear equation1x01...1x20x1...x21...xNx2N c· · · xN00N · · · x 1 c1·..
....· · · xNcNNy0 y1= . ..yN(3.5.2)This is a Vandermonde matrix, as described in §2.8. One could in principle solveequation (3.5.2) by standard techniques for linear equations generally (§2.3); howeverthe special method that was derived in §2.8 is more efficient by a large factor, oforder N , so it is much better.Remember that Vandermonde systems can be quite ill-conditioned. In such acase, no numerical method is going to give a very accurate answer. Such cases donot, please note, imply any difficulty in finding interpolated values by the methodsof §3.1, but only difficulty in finding coefficients.Like the routine in §2.8, the following is due to G.B. Rybicki. Note that thearrays are all assumed to be zero-offset.3.5 Coefficients of the Interpolating Polynomial121#include "nrutil.h"void polcoe(float x[], float y[], int n, float cof[])Given arrays x[0..n] and y[0..n] containing a tabulated function yi = f (xi ), this routine"returns an array of coefficients cof[0..n], such that yi = j cofj xji .{int k,j,i;float phi,ff,b,*s;s=vector(0,n);for (i=0;i<=n;i++) s[i]=cof[i]=0.0;s[n] = -x[0];for (i=1;i<=n;i++) {Coefficients si of the master polynomial P (x) arefor (j=n-i;j<=n-1;j++)found by recurrence.s[j] -= x[i]*s[j+1];s[n] -= x[i];}for (j=0;j<=n;j++) {phi=n+1;%for (k=n;k>=1;k--)The quantity phi = j=k (xj − xk ) is found as aphi=k*s[k]+x[j]*phi;derivative of P (xj ).ff=y[j]/phi;b=1.0;Coefficients of polynomials in each term of the Lagrange formula are found by synthetic division offor (k=n;k>=0;k--) {P (x) by (x − xj ).
The solution ck is accumucof[k] += b*ff;b=s[k]+x[j]*b;lated.}}free_vector(s,0,n);}Another MethodAnother technique is to make use of the function value interpolation routinealready given (polint §3.1). If we interpolate (or extrapolate) to find the value ofthe interpolating polynomial at x = 0, then this value will evidently be c0 . Nowwe can subtract c0 from the yi ’s and divide each by its corresponding xi . Throwingout one point (the one with smallest xi is a good candidate), we can repeat theprocedure to find c1 , and so on.It is not instantly obvious that this procedure is stable, but we have generallyfound it to be somewhat more stable than the routine immediately preceding.
Thismethod is of order N 3 , while the preceding one was of order N 2 . You willfind, however, that neither works very well for large N , because of the intrinsicill-condition of the Vandermonde problem. In single precision, N up to 8 or 10 issatisfactory; about double this in double precision.#include <math.h>#include "nrutil.h"void polcof(float xa[], float ya[], int n, float cof[])Given arrays xa[0..n] and ya[0..n] containing a tabulated function yai = f (xai ), this"jroutine returns an array of coefficients cof[0..n] such that yai = j cofj xai .{void polint(float xa[], float ya[], int n, float x, float *y, float *dy);int k,j,i;float xmin,dy,*x,*y;122Chapter 3.Interpolation and Extrapolationx=vector(0,n);y=vector(0,n);for (j=0;j<=n;j++) {x[j]=xa[j];y[j]=ya[j];}for (j=0;j<=n;j++) {polint(x-1,y-1,n+1-j,0.0,&cof[j],&dy);Subtract 1 from the pointers to x and y becauseextrapolate to x = 0.xmin=1.0e38;k = -1;for (i=0;i<=n-j;i++) {if (fabs(x[i]) < xmin) {xmin=fabs(x[i]);k=i;}if (x[i]) y[i]=(y[i]-cof[j])/x[i];}for (i=k+1;i<=n-j;i++) {y[i-1]=y[i];x[i-1]=x[i];}}free_vector(y,0,n);free_vector(x,0,n);polint uses dimensions [1..n].
WeFind the remaining xi of smallestabsolute value,(meanwhile reducing all the terms)and eliminate it.}If the point x = 0 is not in (or at least close to) the range of the tabulated xi ’s,then the coefficients of the interpolating polynomial will in general become very large.However, the real “information content” of the coefficients is in small differencesfrom the “translation-induced” large values. This is one cause of ill-conditioning,resulting in loss of significance and poorly determined coefficients. You shouldconsider redefining the origin of the problem, to put x = 0 in a sensible place.Another pathology is that, if too high a degree of interpolation is attempted ona smooth function, the interpolating polynomial will attempt to use its high-degreecoefficients, in combinations with large and almost precisely canceling combinations,to match the tabulated values down to the last possible epsilon of accuracy.
Thiseffect is the same as the intrinsic tendency of the interpolating polynomial values tooscillate (wildly) between its constrained points, and would be present even if themachine’s floating precision were infinitely good. The above routines polcoe andpolcof have slightly different sensitivities to the pathologies that can occur.Are you still quite certain that using the coefficients is a good idea?CITED REFERENCES AND FURTHER READING:Isaacson, E., and Keller, H.B. 1966, Analysis of Numerical Methods (New York: Wiley), §5.2.1233.6 Interpolation in Two or More Dimensions3.6 Interpolation in Two or More DimensionsIn multidimensional interpolation, we seek an estimate of y(x1 , x2 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
