Heath - Scientific Computing (523150), страница 68

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 68)

The inclusion of one of the triangles compensates exactly for theomission of the other. A similar phenomenon occurs for the cubic polynomial, where thetwo shaded regions also have equal areas, so that the addition of one compensates for thesubtraction of the other. Such cancellation does not occur, however, for even-order NewtonCotes rules. Thus, in general, an n-point Newton-Cotes rule is of polynomial degree n − 1if n is even, but of polynomial degree n if n is odd............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................a|mb....................................................................................... ................................................................................................... ................................... ............................................................................ .............................

.........................................................................................................................................................................................................................................a|mbFigure 8.2: Cancellation of errors in the midpoint (left) and Simpson (right) rules.8.38.3.1Gaussian QuadratureGaussian Quadrature RulesNewton-Cotes quadrature rules are simple and often effective, but they have a number ofdrawbacks:• The use of a large number of equally spaced nodes in a high-order Newton-Cotes rulemay incur the erratic behavior and unsatisfactory results often associated with highdegree polynomial interpolation.

For example, some of the weights for a high-order rulemay be negative, potentially leading to catastrophic cancellation in the summation.• Closed Newton-Cotes rules require evaluation of the integrand function at the endpointsof the interval, where singularities often lie.• In general, Newton-Cotes rules are not of the highest polynomial degree possible for thenumber of nodes used.These drawbacks are largely overcome by Gaussian quadrature rules.

Gaussian rules arebased on polynomial interpolation, but the nodes are not equally spaced within the interval.Instead, the locations of the nodes are chosen to maximize the polynomial degree of theresulting rule. In particular, the nodes tend to be bunched near the endpoints but donot include the endpoints themselves. These two properties avoid both singularities atthe endpoints and unwanted oscillation in the polynomial interpolant, keeping the weightspositive and of reasonable magnitude.An example of a Gaussian quadrature rule is the two-point rule on the interval [a, b], b−aa+b b−aa+b b−aI(f ) ≈ G2 (f ) =f− √+f+ √,2222 32 3252CHAPTER 8. NUMERICAL INTEGRATION AND DIFFERENTIATIONwhich has polynomial degree three.

In general, for each n there is a unique n-point Gaussianrule, and it is of polynomial degree 2n − 1. The nodes and weights for many Gaussianquadrature rules are tabulated in [1, 251, 282].Gaussian quadrature rules are significantly more difficult to derive than Newton-Cotesrules. In particular, the system of equations that determines the nodes and weights isnonlinear, and the resulting values are usually irrational numbers even if the endpoints a andb are rational, as the foregoing two-point rule illustrates. The latter feature makes Gaussianrules relatively inconvenient for hand computation, compared with using the weights forsimple Newton-Cotes rules.

When using a computer, however, the nodes and weights areusually tabulated in advance and stored in a subroutine that is called when needed, so theuser need not know their actual values.Example 8.4 Gaussian Quadrature Rule. To illustrate the derivation of a Gaussianquadrature rule, we consider the case of a two-point rule on the interval [−1, 1]. We seek aquadrature rule of the formZ 1f (x) dx ≈ w1 f (x1 ) + w2 f (x2 ),−1where the nodes xi and weights wi are to be chosen to maximize the polynomial degree ofthe resulting quadrature rule.We again use the method of undetermined coefficients, but now the nodes as well as theweights are unknown parameters to be determined.

Four parameters are to be determined,so we would expect to be able to integrate cubic polynomials exactly because a cubic dependson four parameters (its coefficients). Thus, we force the quadrature rule to be exact for eachmember of a basis for the set of polynomials of degree three or less, and hence, by linearity,exact for all cubic polynomials.

Requiring the rule to integrate the first four monomialsexactly gives the system of four equationsZ 1w1 + w2 =1 dx = x|1−1 = 1 + 1 = 2,−11w1 x1 + w2 x2w1 x21 + w2 x22w1 x31 + w2 x3211 1x2 = − = 0,=x dx =2 −1 2 2−11Z 1x3 1 122=x dx == + = ,3 −1 3 33−1Z 11x4 1 1=x3 dx == − =04 −1 4 4−1Zin the four unknowns. One solution for this nonlinear system is given by√√x1 = −1/ 3, x2 = 1/ 3, w1 = 1, w2 = 1,and the other solution is obtained by reversing the signs of x1 and x2 (see ComputerProblem 5.14).

Thus, the Gaussian quadrature rule has the formZ 1√√f (x) dx ≈ f (−1/ 3 ) + f (1/ 3 )−18.3. GAUSSIAN QUADRATURE253and has polynomial degree three.Alternatively, the nodes of a Gaussian quadrature rule can be obtained by using orthogonal polynomials. If p is a polynomial of degree n such thatZbp(x)xk dx = 0,k = 0, . . . , n − 1,aand hence p is orthogonal on [a, b] to all polynomials of degree less than n, then it is fairlyeasy to show (see Exercise 8.6) that1. The n zeros of p are real, simple, and lie in the open interval (a, b).2. The n-point interpolatory quadrature rule on [a, b] whose nodes are the zeros of p haspolynomial degree 2n − 1; i.e., it is the unique n-point Gaussian rule.The nth Legendre polynomial (see Section 7.2.4) provides a suitable polynomial p.

Forthis reason, the resulting rule is often called a Gauss-Legendre quadrature rule. Of course,the zeros of the Legendre polynomial must still be computed, and then the correspondingweights for the quadrature rule can be determined in the usual way. This method alsoextends naturally to various other weight functions and intervals corresponding to otherfamilies of orthogonal polynomials. Of particular interest for semi-infinite or infinite intervals are Gauss-Laguerre and Gauss-Hermite quadrature rules. The nodes and weightsfor a Gaussian quadrature rule can also be computed by means of an eigenvalue problemassociated with the corresponding orthogonal polynomials and weight function [105].8.3.2Change of IntervalGaussian rules are somewhat more difficult to apply than Newton-Cotes rules because theweights and nodes are usually derived for some specific interval, such as [0, 1] or [−1, 1], andthus the given interval of integration [a, b] must be transformed into a standard interval forwhich the nodes and weights have been tabulated.

If we wish to use a quadrature rule thatis tabulated on the interval [α, β],Zβf (x) dx ≈αnXwi f (xi ),i=1to approximate an integral on the interval [a, b],I(g) =Zbg(t) dt,athen we must use a change of variable from x in [α, β] to t in [a, b]. Many such transformations are possible, but a simple linear transformationt=(b − a)x + aβ − bαβ−α254CHAPTER 8. NUMERICAL INTEGRATION AND DIFFERENTIATIONhas the advantage of preserving the polynomial degree of the rule. The integral is thengiven byZb−a β(b − a)x + aβ − bαI(g) =gdxβ−α αβ−αnb−a X(b − a)xi + aβ − bα≈wi g.β−αβ−αi=1Example 8.5 Change of Interval.

Характеристики

Список файлов книги