Shampine, Allen, Pruess - Fundamentals of Numerical Computing (523185), страница 25
Текст из файла (страница 25)
In this special, but quiteuseful, case, the fundamental polynomials or shape functions are easily constructedfrom the functions in one variable. Recalling (3.3), letThen an interpolant Q(x,y) such that(3.45)3.6 INTERPOLATION IN THE PLANE121Figure 3.14 Data on a rectangular grid (n = 4, m = 5).is given by(3.46)If Q(x,y) is multiplied out, it clearly has the form(3.47)We now show that the coefficients ast are uniquely determined by the interpolationconditions (3.45).
Choose any i with 1 < i < n and consider the polynomial in the onevariable y:We know that there is exactly one polynomialthat interpolates the values fij at yj for j = 1,. . . , m. Because Q(xi ,y) does this, it mustbe that122CHAPTER 3INTERPOLATIONThis equation holds for each i.
Now choose a t with 0 < t < m. There is exactly onepolynomialsuch thatR(xi) = bit for i = l, . . . ,n.Because the polynomialdoes this, it must be the case that cst = ast for 0 < s < n and for any 0 < t < m. Thus thecoefficients ast are uniquely determined by the interpolation coefficients as we wantedto show.As a simple example, let us consider interpolation at the four comers of a rectangle: (x 1 ,y l ) (x l ,y 2 ), (x 2 ,y 1 ) (x 2 ,y 2 ).(3.48)Figure 3.15 displays a typical interpolant for n = 4 and m = 3.Interpolants constructed in this way are called tensor product interpolants. Theexample (3.48) is said to be a bilinear interpolant over a rectangle because it has theforma00 + a10x + a01y + a11xy,(3.49)that is, it is linear in each variable when the other is held fixed.
The general first degreepolynomial has the form (3.49) with a11 = 0. A biquadratic has the formwhile the general second degree polynomial has here a21 = a22 = a12 = 0. Generalizations to bicubic versus cubic and higher degrees should be clear.In studying how well a function of two variables is approximated by a particularkind of interpolating polynomial, a critical matter is the highest degree for which theapproximation is exact. For example, in the rectangle of Figure 3.16, we can interpolate at the nine indicated points using a biquadratic.
However, it is exact only forsecond degree polynomials in spite of the presence of the higher degree terms x2y, yx2,and x2y2. In fact only six interpolating points are needed to construct a quadratic interpolating polynomial that is exact to second degree. It is not at all clear how to choose3.6 INTERPOLATION IN THE PLANE123Figure 3.15 A typical bilinear interpolating function.the six points symmetrically from the rectangular grid. Because of this, biquadraticsor bicubics are generally used for interpolation on rectangular grids.Just as in the case of one variable, piecewise polynomial interpolation may providemore satisfactory interpolants than a polynomial interpolant over the whole region.
Ifthe region can be broken up into rectangles, tensor product interpolants can be usedon each piece. In the case of one variable, two pieces connect at a single point, butin the plane they connect along a line, and more than one piece can touch at a point.In contrast to the ease with which the polynomial pieces could be connected smoothlyin the case of one variable, it is hard to get much smoothness where polynomials inseveral variables are joined.Figure 3.16 Interpolation points for biquadratics.124CHAPTER 3 INTERPOLATIONFigure 3.17 Two triangulations for the data in Figure 3.13.In piecewise polynomial interpolation the idea is to work with regions for whichinterpolants are readily constructed and to decompose the region of interest into regions of this kind.
A popular alternative to rectangles is triangles. For example, onemight triangulate the region of Figure 3.13 in the two ways sketched in Figure 3.17. Asa rule it is best to avoid the “skinny” triangles of the second possibility, and routinesfor triangulating regions generally try to avoid nearly degenerate triangles. It is nothard to write down the shape functions for linear interpolation on the general triangleof Figure 3.18. They arewhereand A is the area of the triangle. Then the linear function that has given values at thecomersfi given at (xi ,yi ), i = 1,2,3,isNote that on this triangle Q has the formQ(x,y) = a + bx + cy(3.50)for some a, b, and C.
See Figure 3.19 for an illustration of piecewise linear interpolationon a triangular grid.3.6 INTERPOLATION IN THE PLANE125Figure 3.18 A general triangle.Figure 3.19 Linear interpolation on a triangular grid.In finite element analysis one tries to determine a piecewise polynomial approximation to the solution of an ordinary or partial differential equation.
Polynomialapproximations over subregions prove to be very convenient in computation. Also,representing solutions in the Lagrangian, or nodal, formis convenient because the fi are approximate solution values at the nodes (x i ,y i ). Onedifficulty is that rectangles or triangles are too restrictive.
A way to accommodatesubregions with curved sides is to transform the region to a “standard,” “reference,”or “master” region. For example, we might choose to work with a standard trianglesuch as the one given in Figure 3.20. Suppose we want to represent a function f ( x , y)on a regionIf it is known how to map the region onto the standard triangle, then126CHAPTER 3 INTERPOLATIONFigure 3.20 Mapping from the standard triangle.interpolation can be done.
Let T be a mapping such thatand asranges over the standard triangle, the values (x,y) range overf(x,y) for (x,y) inhasThenand we can simply interpolateover the triangle. Of course, the mapping must be aproper one, meaning that asranges over the triangle, the (x,y) cover all ofand there is no overlap [differentgo into different (x,y)]. A nice idea used forfinite elements is to construct the mapping by interpolation, too.
As an example, let usconstruct the mapping from the standard triangle to the general triangle of Figure 3.20.The shape functions for the standard triangle are obviouslywhen we letnode 1 be (1,0)node 2 be (0,1)node 3 be (0,0)because, for example,3.6 INTERPOLATION IN THE PLANE127Interpolating x we haveand, similarly,In this particular case the mapping carries straight lines into straight lines and thereis no difficulty about a proper mapping. If higher degree interpolation were used, thetriangle would be mapped into a region with curved sides.
Roughly speaking, if theregion is not too different from a triangle, the mapping will be proper. Continuingwith the example, suppose we interpolate the fi by the same basis functions used toconstruct the mapping. The interpolant Q(x,y) isIf we were to solve the relationto get the inverse mappingand eliminate and η in this interpolant, we would get the expression earlier for thebilinear interpolant.
This seems a complicated way to get a simple result. The virtue ofthe procedure is that interpolation is done on regions with curved boundaries by transforming them to a simple, standard region for which interpolation is comparativelyeasy. In finite element computations it is found that the process is easily programmedand very powerful. All we aim to do here is sketch the process. For details the readermay consult one of the great many books devoted to finite elements. The books span agreat range of mathematical sophistication; a good introduction is [1].EXERCISES3.37 The formula (3.48) could be called a Lagrange form 3.38 Show that Q(x,y), which is a quadratic polynomial inx and y [generalizing (3.50)], has six coefficients.
On aof the bilinear interpolating polynomial; consider the“Newton form”triangle, its interpolating points are usually chosen tobe the three triangle vertices and the three edge midpoints. For the triangle with vertices (0,0), (1,0), and(0,l) compute the shape function that is one at (0,0)Solve for a, b, c, and d so that Q interpolates aand zero at the remaining five interpolating points.function f(x,y) at the four corners.
As in (3.48) let128CHAPTER 3INTERPOLATION3.7 CASE STUDY 3This case study has two parts, one applying continuous splines and the other, smoothsplines. Integrals of the formwith finite a and b are called finite Fourier integrals. For large ω such integrals presentspecial difficulties for numerical methods because of the rapid oscillation of the integrand. Filon’s method [8] for approximating finite Fourier integrals will be developedhere by means of a continuous spline. Accurate evaluation of the coefficients of themethod was discussed in Chapter 1. Other aspects of the task will be discussed inChapter 5. The second part of the case study takes up the use of smooth splines forfitting data with curves instead of functions.Broadly speaking, Filon approximates finite Fourier integrals in a manner like thatused in Chapter 5 for integrals of the formwhen w(x) presents some difficulty.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
