In multidimensional interpolation, we seek an estimate of y(x1 , x2 , . . . , xn ) from an n-dimensional grid of tabulated values y and n one-dimensional vectors giving the tabulated values of each of the independent variables x1 , x2, . . . , xn . | Interpolation in Two or More Dimensions 123 Interpolation in Two or More Dimensions In multidimensional interpolation we seek an estimate of y x1 x2 . xn from an n-dimensional grid of tabulated values y and n one-dimensional vectors giving the tabulated values of each of the independent variables x1 x2 . xn. We will not here consider the problem of interpolating on a mesh that is not Cartesian . has tabulated function values at random points in n-dimensional space rather than at the vertices of a rectangular array. For clarity we will consider explicitly only the case of two dimensions the cases of three or more dimensions being analogous in every way. In two dimensions we imagine that we are given a matrix of functional values ya . We are also given an array x1a and an array x2a . The relation of these input quantities to an underlying function y x1 x2 is ya j k y x1a j x2a k We want to estimate by interpolation the function y at some untabulated point xi x2 . An important concept is that of the grid square in which the point x1 x2 falls that is the four tabulated points that surround the desired interior point. For convenience we will number these points from 1 to 4 counterclockwise starting from the lower left see Figure . More precisely if x1a j xi x1a j 1 x2a k x2 x2a k 1 defines j and k then yi ya j k y2 ya j 1 k ys ya j 1 k 1 y4 ya j k 1 The simplest interpolation in two dimensions is bilinear interpolation on the grid square. Its formulas are t xi - x1a j x1a j 1 - x1a j u x2 x2a k x2a k 1 x2a k Sample page from NUMERICAL RECIPES IN C THE ART OF SCIENTIFIC COMPUTING ISBN 0-521-43108-5 so that t and u each lie between 0 and 1 and y xi x 1 t 1 u yi t 1 u y2 tuy3 1 t uy4 Bilinear interpolation is frequently close enough for government work. As the interpolating point wanders from grid square to grid square the interpolated 124 Chapter 3. Interpolation and Extrapolation a Figure . a Labeling of
