Numerical Integration

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Slide 1: 

1 ME 310 Spring 2004 Integration These presentations are prepared by Dr. Cuneyt Sert Mechanical Engineering Department Middle East Technical University Ankara, Turkey csert@metu.edu.tr

Slide 2: 

2 Idea: Replace a complicated function or a tabulated data with an approximating (interpolating) function. Newton-Cotes Integration Formulas where fn(x) is an nth order interpolating polynomial.

Slide 3: 

3 Trapezoidal Rule: All Newton-Cotes formulas can be written in the form “Average height * width”. Different formulas will have different expressions for average height. Newton-Cotes formulas can be derived by integrating Newton’s Interpoating Polynomials. Newton-Gregory version can be used for equispaced data points. These derivations also provide an estimate for the truncation error. Newton’s Divided Difference Interpolating Polynomials fn(x) = f(x0) + (x - x0) f[x1, x0] + (x - x0)(x - x1) f[x2, x1, x0] + . . . + (x - x0)(x - x1) . . . (x - xn-1) f[xn, xn-1, . . ., x1, x0] Newton-Gregory Formula fn(x) = f(x0) + Df(x0) a + D2f(x0) a(a - 1) / 2! + . . . + Dnf(x0) a(a - 1) . . . (a - n + 1) / n! + Rn where a = (x - x0) / h , Rn = f (n+1)(x) hn+1 a(a - 1) . . . (a - n) / (n+1)! and Dfn(x0) is the nth forward difference.

Slide 4: 

4 Derivation of the Trapezoidal Rule using Newton-Gregory Formula: Change integration limits from x to a. Trapezoidal Rule is first order accurate. It can integrate linear polynomials exactly.

Slide 5: 

5 Error Estimation for the Trapezoidal Rule: Usually f ?(x) in the error term can not be evaluated since x is not known. If the function f is known than f ?(x) can be approximated with an average 2nd derivative Example: Integrate f(x)= ex from a=1.5 to a=2.5 using the Trapezoidal Rule. Estimate the error. True value is e2.5 – e1.5 = 7.700805 Using the trapezoidal rule: a = 1.5, b = 2.5, h = 2.5 – 1.5 = 1.0 Et = - 0.631287, et = - 8.2 % Estimated error:

Slide 6: 

6 Multiple application of the Trapezoidal Rule: In general we have n+1 points and n intervals (segments). If the points are equispaced h = (b-a)/n The last equation is again of the form “Width * Average height”

Slide 7: 

7 Error Estimation for the Multiple Application of the Trapezoidal Rule: Use a single x for the entire interval ? This is of order h2. Compare it with the true error of the single application of the Trapezoidal Rule which was of order h3. Similar to the single application of the trapezoidal rule, if the function f is known than f ?(x) can be approximated with an average 2nd derivative Add the individual errors for each interval ?

Slide 8: 

8 Example: Integrate f(x)= ex from a=1.5 to a=2.5 using the Trapezoidal Rule. Use a step size of 0.25. True value of the integral is 7.700805. a = 1.5, b = 2.5, h = 0.25 than we have n=4 intervals. I ? 7.740872 , Et = - 0.040067, et = - 0.5 % Estimated error: Note that the calculation of Ea requires the evaluation of the same integral that the question asks for. Of course the integral in Ea can also be calculated numerically. This approach gives

Slide 9: 

9 Simpson’s 1/3 Rule: This can be derived using the second order Newton-Gregory formula where the remainder is The derivation yields (see page 597 for details)

Slide 10: 

10 Simpson’s 1/3 Rule uses 3 points, therefore it is expected to integrate 2nd order polynomials exactly. However it can integrate cubics exactly. This is due to the vanishing third term in integrating the Newton-Gregory polynomial. Multiple application of Simpson’s 1/3 Rule Rule: In general we have n+1 points and n intervals. If the points are equispaced h = (b-a)/n If there are even number of points the integration can not be done with Simpson’s 1/3 rule only.

Slide 11: 

11 Example: Calculate using (a) Trapezoidal Rule with n=2, n=4 and n=6. (b) Simpson’s 1/3 Rule with n=2, n=4 and n=6. (a) For n=2, h=p/2, Note that Et = 0.429204 (b) For n=4, h=p/4, Note that Et = 0.004560 Exercise: Complete the solution of this example.

Slide 12: 

12 Simpson’s 3/8 Rule: Exercise: Derive this formula by integrating the proper Newton-Gregory polynomial. Exercise: Derive the formula for the multiple application of Simpson’s 3/8 Rule. Note that 3/8 Rule uses 4 points and it is third order accurate (can integrate cubic polynomials exactly). 1/3 Rule does this with 3 points and it is preferred. 3/8 rule is useful if there are even number of points. 1/3 and 3/8 can be used together, but mixing them with the Trapezoidal Rule is not suggested. Because the accuracy of the Trapezoidal rule is only first order. Exercise: Perform an efficient third order accurate calculation for the previous example with n=7. Use an efficient proper combiation of 1/3 and 3/8 Rules.

Slide 13: 

13 Richardson Extrapolation for Integration Similar to the discussion we made for differentiation, I: Exact integral (usually not known) I = I1 + E1 where I1: Estimated integral using h=h1. E1: Error of the estimation I1. I = I2 + E2 where I2: Estimated integral using h=h2. E2: Error of the estimation I2. If multiple application of the Trapezoidal Rule is used to get the estimates I1 and I2, than E1 = O(h12) , E2 = O(h22) Using these, I1 and I2 can be combined to get a better estimate such as This new estimate is O(h4) accurate. A special case of h2 = h1/2 results in

Slide 14: 

14 Romberg Integration Apply multiple Richardson Extrapolation one after the other. If we use Trapezoidal Rule and successively halve the step size I1,1 is the integral obtained by h. Usually we start with a single segment, i.e, h = b - a I2,1 is the integral obtained by h/2. I3,1 is the integral obtained by h/4. etc. Combine I1,1 and I2,1 to get I1,2 I1,2 = 4/3 I2,1 - 1/3 I1,1 Combine I1,2 and I2,2 to get I1,3 I1,3 = 16/15 I2,2 - 1/15 I1,2 Combine I1,3 and I2,3 to get I1,4 I1,4 = 64/63 I2,3 - 1/63 I1,3 etc. O(h2) O(h4) O(h6) O(h8) O(h10) I1,1 I1,2 I1,3 I1,4 I1,5 I2,1 I2,2 I2,3 I2,4 I3,1 I3,2 I3,3 I4,1 I4,2 I5,1 Valid if Trapezoidal Rule with successive halving of the step size is used to get the first column.

Slide 15: 

15 Example: Perform 4 levels of Romberg Integration to integrate sin(x) over the interval [0,p]. Use Trapezoidal Rule. h=p , I1,1 = p/2 [sin(0) + sin(p)] = 0.0 h=p/2 , I1,2 = (p/2)/2 [sin(0) + 2sin(p/2) + sin(p)] = 1.57079633 h=p/4 , I1,3 = (p/4)/2 [sin(0) + 2sin(p/4) + 2sin(p/2) + 2sin(3p/4) + sin(p)] = 1.89611890 h=p/8 , I1,4 = 1.97423160 Exercise: The true error of the final result is about 6x10-6. We can estimate the number of segments to be used to achieve this accuracy with the Trapezoidal Rule. Sample Error Calculation

Slide 16: 

16 Gauss-Quadrature Integration Trapezoidal rule uses two points to perform the integration. These two points are the end points of the interval. What if we use some other points? Gauss-Quadrature uses special points in the interval [a,b] to achieve higher accuracy than Newton-Cotes formulas. But it is not suitable for integrating tabulated data, it can be used if the function is known. The special points (x0, x1) and the weights (c0, c1) can be determined using a technique called Method of Undetermined Coefficients.

Slide 17: 

17 Derivation of the Two Point Gauss-Quadrature Formula Using the Method of Undetermined Coefficients Consider the calculation of the integral of f(x) over the interval [-1,1] I ? c0 f(x0) + c1 f(x1) We have 4 unknowns. We need 4 equations to find them. We will get these equations by assuming that this formula calculates constant, linear, parabolic and cubic functions exactly (Note that Trapezoidal Rule also uses two points and can only calculate constant and linear functions exactly).

Slide 18: 

18 Note that this formula integrates over the domain xd ? [-1,1]. This is done to simplify the mathematics and to get a general formula that can be applied to any domain with a change of variable. To apply this formula to a domain of x ? [a,b] we need to change the variable as Example: Integrate sin(x) over [0,p] using two-point Gauss Quadrature. For this calculation |Et|= 0.064. To achieve this accuracy with the Trapezoidal Rule we approximately need 5 segments.

Slide 19: 

19 Higher Order Gauss-Quadrature Formulas The general version of Gauss-Quadrature that uses n points is I ? c0 f(x0) + c1 f(x1) + . . . + cn-1 f(xn-1) We can use the method of undetermined coefficients to get 2n equations to solve for 2n unknowns. Table 22.1 shows the weighting factors and integration points up to n=6. Notice the symmetric pattern of them. n-point Gauss-Quadrature formula can integrate (2n-1) order polynomials exactly. There are several versions of Gauss-Quadrature. The version we learned is actually called Gauss-Legendre-Quadrature. Exercise: Derive the 3-point Gauss-Quadrature formula. Exercise: Use this formula to integrate sin(x) over [0,p]. Approximately how many segments are necessary to get the same accuracy with the Trapezoidal Rule, Simpson’s 1/3 Rule and Simpson’s 3/8 Rule? Exercise: Pick a 5th order polynomial and show that the 3-point Gauss-Quadrature can integrate it exactly.