### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# INTRONUMANALYS&COMPUT MATH541

SDSU

GPA 3.61

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Mathematics (M)

This 45 page Class Notes was uploaded by Camryn Rogahn on Tuesday October 20, 2015. The Class Notes belongs to MATH541 at San Diego State University taught by P.Blomgren in Fall. Since its upload, it has received 24 views. For similar materials see /class/225269/math541-san-diego-state-university in Mathematics (M) at San Diego State University.

## Popular in Mathematics (M)

## Reviews for INTRONUMANALYS&COMPUT

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/20/15

Numerical Analysis and Computing Lecture Notes 08 Numerical Differentiation and Integration Composite Numerical Integration Rom berg Integration Adaptive Quadrature Gaussian Quadrature Peter BIomgren blomgren peter gmail com Department of Mathematics and Statistics DynamicaI Systems Group ComputationaI Sciences Research Center San Diego State University San Diego CA 9218277720 httpterminussdsuedu ComposileRombergrAdapliverGaussian Outline 0 Composite Quadrature 0 Divide and Conquer Example 7 Simpson39s Rule 0 Generalization 0 Collecting the Error 0 Summary Algorithm Homework 7 version 1 a Romberg Quadrature 0 Applying Richardson39s Extrapolation 0 Romberg Quadrature 7 Code Outline 9 Adaptive Quadrature 0 Introduction 0 Building the Adaptive CSR Scheme 0 Example 0 Putting it Together a Gaussian Quadrature 0 Ideas 0 Zipoint Gaussian Quadrature 0 Higheriorder Gaussian Quadrature i Legendre Polynomials 0 Exam les Gaussian uadrature in Action HW 7 P Q 39 5351 ComposileRombergrAdapliverGaussian 7 245 Divide and Conquer with Simpson39s Rule The exact solution 4 exdx e4 7 e0 5359815 0 Simpson39s Rule with h 2 4 2 exdx z 5so 4e2 e4 5676958 0 The error is 7317143 592 Divideand Conquer Simpson39s Rule with h 1 2 4 1 1 exdx exdx z ge04e1e2 e24e3e4 5386385 0 2 The error is 7026570 050 Improvement by a factor of 10 m ComposileRombergrAdapliverGaussian 7 345 Divide and Conquer with Simpson39s Rule The exact solution 4 ede e4 7 e0 5359815 0 Divideand Conquer Simpson39s Rule with h 12 1 2 3 4 exm 0 1 2 3 1 6 2092 4e52 e3 2093 4e72 e4 5361622 The error has been reduced to 7001807 0034 1 e0 4e12 1 el 6e1 4e32 1 e2 h abserror errh errh2 errh3 errh4 2 317143 1585715 0792857 0396429 0198214 1 026570 0265700 0265700 0265700 0265700 12 001807 0036140 0072280 0144560 0289120 ComposileRombergrAdapliverGaussian 7 445 Divide and Conquer with Simpson39s Rule llllll Extending the table h abserror errh errh errh errh4 err 5 3 171433 1 585716 0 792858 0 396429 0193215 0 099107 0 265696 0 265696 0 265696 0 265696 0265696 0 265696 12 0 018071 0 036142 0 072283 0 144566 0239132 0 578264 14 0 001155 0 004618 0 018473 0 073892 0295566 1 182266 18 0 000073 0 000580 0 004644 0 037152 0297215 2 377716 D N Clearly the errh4 column seems to converge to a non zero constant as h 0 The columns to the left seem to converge to zero and the errh5 column seems to grow This is numerical evidence that the composite Simpson39s rule has a convergence rate of O h4 But isn39t Simpson39s rule 5th order 5351 CompositeRombergrAdapliverGaussian 7 545 Generalized Composite Simpson39s Rule lll For an even integer n Subdivide the interval 37 b into n subintervals and apply Simpson39s rule on each consecutive pair of sub intervals With h b7 an and X a jh j 017 7 n we have n2 abfxdx ZXQ fxdx nz j1 X272 7 75 4 2 g fX21724fX2171flxzj Equot 51 7 11 for some 5 E X2j727X2j if f E C4a7 b Since all the interior even XQJ39 points appear twice in the sum we can simplify the eXpression a bit m CompositeRombergrAdapliverGaussian 7 545 Generalized Composite Simpson39s Rule nZ b h fxdx 5 fx0 7 x Z Mm1 2am j1 h5 n2 4 E Z A M51 j1 The error term is h5 n2 EU E Z 14105 51 E X21727X2J39 11 ComposileRombergrAdapliverGaussian 7 745 The Error for Composite Simpson39s Rule If f E C4a7 b the Extreme Value Theorem implies that f4 assumes its max and min in 37 b Now since min f4x S f45j S max f4x7 XQM X6ab n2 39 4 4 4 i2i xgilafib f X S f 5 S i2i x3232 f XL n2 2 39 4 lt 7 E 4 lt 4 xgilaljbf X inij1f EJLXZ SW XL By the Intermediate Value Theorem 3 6 37 b so that nZ nZ WW 2 We gt 9 2 W5 j1 11 ComposileRombergrAdapliverGaussian 7 345 The Error for Composite Simpson39s Rule llll We can now rewrite the error term 75 W 4 75 4 Elf ng 51 mnf 07 or since h b7 an ltgt n b7 ah we can write 7 hie 4 4 Ef 7 180 h f Hence Composite Simpson s Rule has degree of accuracy 3 since it is exact for polynomials up to order 3 and the error is proportional to h4 Convergence Rate 9 h4 CompositeRombergrAdapliverGaussian 7 945 Composite Simpson39s Rule Summary Theorem Composite Simpson39s Rule Let f E C4a7 b n be even h b 7 an ande ajh j 017n There exists In 6 37 b for which the Composite Simpson s Rule for n subntervals can be written With its error term as b h n2 3 fx dx 5 fa 7 fb 14fxzj1 2am J ilb 3 4 4 180 h f 039 Note X0 a and Xn b 5351 ComposileRombergrAdapliverGaussian 7 1045 Composite Simpson39s Rule Algorithm Algorithm Composite Simpson39s Rule Given the end points a and b and an even positive integer n 1 h b7 an 2 ENDPTS faf b ODDPTS 0 EVENPTS 0 3 FOR 139 17 7 n 7 1 7 interior points X a l i h if i is even EVENPTS fx if i is odd ODDPTS fx END 4 INTAPPROX h ENDPTS2EVENPTS4ODDPTS 3 ComposileRombergrAdapliverGaussian 7 1145 Homework 7 Due Friday 11132009 12 noon Part 1 Implement Composite Simpson39s Rule and use your code to solve BF443abcd ComposileRombergrAdapliverGaussian 7 1245 Rom berg Integration The Return of Richardson39s Extrapolation Rom berg Integration is the combination of the Composite Trapezoidal Rule CTR b i a 12 b h n71 a fxdx 5 fa fb21fXj 7 WW J and Richardson Extrapolation Here we know that the error term for regular Trapezoidal Rule is 9h3 By the same argument as for Composite Simpson39s Rule this gets reduced to 9h2 for the composite version ComposileRombergrAdapliverGaussian 7 1345 Rom berg Integration Step1 CTR Refinement Let Rm denote the Composite Trapezoidal Rule with 2 1 sub intervals and hk b7 a2k 1 We get R11 3 fb R11 fa 2fa hz fb aawamw whz RL1 h1fa h2 2k72 1 Rm E Rk711 hke1 fa 21hk Update formula using previous value new points ComposileRombergrAdapliverGaussian 7 1445 Example Rm for fowsinxdx Rm 0 1 5707963267949 NOWgtme H u l gt m 0 m o H u gt m m 1 9995983886400 ComposileRombergrAdapliverGaussian 7 1545 Extra polate using Richardson We know that the error term is 0h2 so in order to eliminate this term we combine to consecutive entries Rk11 and Rm to form a higher order approximation Rid of the integral Rk2 Rk1 Rk1 Rk711 2271 Rky170h 0 1 5707963267949 1 8961188979370 1 9742316019455 1 9935703437723 1 9983933609701 1 9995983886400 Rm 0 2 09439510239 2 00455975498 2 00026916994 2 00001659104 2 00000103336 2 00000006453 CompositeRombergrAdapliverGaussian 7 1545 EXtrapolate again It turns out Taylor expand to check that the complete error term for the Trapezoidal rule only has even powers of h b 00 fx Rm 7 Z 52mgquot 3 i1 Hence the Rid approximations have error terms that are of size 0h4 To get 9h6 approximations we compute R 7 R Rk3 Rk2 k 242 ikl 1 2 CompositeRombergrAdapliverGaussian 7 1745 Extra polate yet again In general since we only have even powers of h in the error expansion Rk 3971 Rkil 3971 R R quot 1 kJ kJ 1 4397 7 1 Revisiting f0 sinxdx RM 7 0 h Rm 7 0 H Rm 7 0 h Rm 7 0 h 1 570796326794897 2 094395102393195 1 896118897937040 2 004559754984421 1 998570731823836 1 974231601945551 2 000269169948388 1 999983130945986 2 000005549979671 1 cg I Vows I o cu 2 935 1 2 1 998393360970145 2 000001033369413 1 999999996190845 2 000000000059674 1 2 1 2 000000000000229 5351 ComposileRombergrAdapliverGaussian 7 1345 Homework7 No enough already 7 Here39s the code outline39 Code Romberg Quadrature 397 Kornberg Integration for sinx over 0131 0 quot Th Endpoints R zeros77 R11 bia2 sina sinb for k2 7 h b7 a2k 1 Rk112 Rk 7 11 2 m Zsina 2 1 N Qm 7 1 h end for j 2 7 for k j 7 Raw Rme 1 Mme 1 7 We we 140 171 end end dispR ComposileRombergrAdapliverGaussian 7 1945 More Advanced Numerical Integration Ideas Adaptive and Gaussian Quadrature ComposileRombergrAdapliverGaussian 7 2045 Introduction Adaptive Quadrature The composite formulas require equally spaced nodes This is not good if the function we are trying to integrate has both regions with large fluctuations and regions with small variations We need many points where the function fluctuates but few points where it is close to constant or linear 5351 CompositeRombergrAdapliverGaussian 7 2145 Introduction Adaptive Quadrature Methods Idea Cleverly predict or measure the amount of variation and au tomatically add more points where needed We are going to discuss this in the context of Composite Simpson39s rule but the approach can be adopted for other integration schemes First we are going to develop a way to measure the error a numerical estimate of the actual error in the numerical integration Note just knowing the structure of the error term is not enough We will however use the structure of the error term in our derivation of the numerical error estimate Then we will use the error estimate to decide whether to accept the value from CSR or if we need to refine further recompute with smaller h m CompositeRombergrAdapliverGaussian 7 2245 Some Notation Onestep Simpson39s Rule fab Notation One step Simpson s Rule abfx where f a7 b h5 dX 51 37 b 9 011 m 6 37 b q Efvh1m b7 6 3 1 WW Nb 7 ComposileRombergrAdapliverGaussian 7 2345 Composite Simpson39s Rule CSR With this notation we can write CSR with n 4 and hg b7 a4 h12I b fx dx f a agb f 3 b 7 Ef hwz We can squeeze out an estimate for the error by noticing that 1 hi 4 E git 2 Now assuming f4u1 z f4u2 we do a little bit of algebra magic with our two approximations to the integral Efh27i 2 i 1 EEU h17 M2 ComposileRombergrAdapliverGaussian 7 2445 Wait Wait Wait I pulled a fast one 1 him 1 1 hi 4 2 Efh27I2 Elf 2 5 Elf 2 where if E 3735b 5 E 717 If f E C4a7 b then we can use our old friend the intermediate value theorem 4 1 144 2 HMEl v glclavbh Mew So it follows that Efh ii if 27M216 90 M2 ComposileRombergrAdapliverGaussian 7 2545 Back to the Error Estimate Now we have a a 1 h5 50 a 3b sif 2 b a E gig wim is f b f a a 90 1 Now use the assumption f4u1 z f4u2 and replace 1 and M2 by M3 5 flt4gtm m g ism a b5f a aw275m ab2 bi notice that 144M Ef h17p16Ef hgnu Hence Ef hgnu z f 37b7f aab27f a i b27 ComposileRombergrAdapliverGaussian 7 2545 Finally we have the error estimate in hand Using the estimate of ggf4p we have Error Estimate for CSR bfxdx 7 Sf a a b2 7 Sf a b2 b as 37 b 5 37 a b2 Sf a b2 b Notice f a7 a i b2 i f a i b27 b approximates fab fxdx 15 times better than it agrees with the known quantity f a7 b m ComposileRombergrAdapliverGaussian 7 2745 Example Error Estimates We will apply Simpson39s rule to 7r2 sinx dx 1 0 Here Slsinx 07r2 sinx 07r2 mm 4sin7r4 sin7r2 112 2 1 100227987749221 Sgsinx 07r2 sinx 07r4 sinx 7r477r2 24 sin0 4sin7r8 2sin7r4 4sin37r8 sin7r2 100013458497419 5351 ComposileRombergrAdapliverGaussian 7 2345 Example Error Estimates The error estimate is given by T15 s1sinx 07r2 782sinx 07r2 1 000014301950120 i51002279877492217 100013458497419 This is a very good approximation of the actual error which is 000013458497419 OK we know how to get an error estimate How do we use this to create an adaptive integration scheme ComposileRombergrAdapliverGaussian 7 2945 Adaptive Quadrature We want to approximate I fab fx dx with an error less than 6 a specified tolerance 1 Compute the two approximations Slfx a7 b fx a7 b and S21 xaub 5fx a sh 5fx b 2 Estimate the error if the estimate is less than 6 we are done Otherwise 3 Apply steps 1 and 2 recursively to the intervals 37 and 342 7 b with tolerance 62 CompositeRombergrAdapliverGaussian 7 3045 Adaptive Quadrature Interval Refinement Example 1 The funny figure above is supposed to illustrate a possible sub interval refinement hierarchy Red dashed lines illustrate failure to satisfy the tolerance and black lines illustrate satisfied tolerance level tol interval 1 a b 2 52 aab2 abia2b 3 64 aa aal CompositeRombergrAdapliverGaussian 7 3145 Adaptive Quadrature Interval Refinement Example 2 Refnanem Lwel Figure Application of adaptive CSR to the function fX 17 43 X 7 2 Here we have required that the estimated error be less than 10 6 The left panel shows the function and the right panel shows the number of refinement levels needed to reach the desired accuracy At completion we have the value of the integral being 0 61692712 with an estimated error of 393 10 7 m ComposileRombergrAdapliverGaussian 7 3245 Gaussian Quadrature Idea Evaluate the function at a set of optimally chosen points in the interval We will choose X07X17 7Xn 6 37 b and coefficients 6 so that the approximation 1 n fxdx m Zci xi is exact for the largest class of polynomials possible We have already seen that the open Newton Cotes formulas sometimes give us better bang for buck than the closed formulas eg the mid point formula uses only 1 point and is as accurate as the two point trapezoidal rule Gaussian quadrature takes this one step further CompositeRombergrAdapliverGaussian 7 3345 Quadrature Types A Comparison The mid point rule 1 Trapezoidal rule Simpson39s rule The mid oint rule is the onl o timal scheme we have see so far p y p 535 ComposileRombergrAdapliverGaussian 7 3445 Gaussian Quadrature Example ZPoint Formula Suppose we want to find an optimal two point formula fx dx 1fX1 CQfX2 Since we have 4 parameters to play with we can generate a formula that is exact up to polynomials of degree 3 We get the following 4 equations 1 1 dx 2 c1 c2 C1 1 71 1 C2 1 X dx O clxl czxz 2 2 2 2 X1 7 7 X dx g clx1 czx2 3 11 X3 dx O clxl3 szg X2 Y 71 m ComposileRombergrAdapliverGaussian 7 3545 Higher Order Gaussian Quadrature Formulas We could obtain higher order formulas by adding more points computing the integrals and solving the resulting non linear system of equations but it gets very painful very fast The Legendre Polynomials come to our rescue The Legendre polynomials Pnx are orthogonal on 711 with respect to the weight function WX 1 ie fl PquotXPmx dx an nm 0 m 73 n an m n lf PX is a polynomial of degree less than n then 1 PnxPx dx 0 71 CompositeRombergrAdapliverGaussian 7 3545 A Quick Note on Legendre Polynomials We will see Legendre polynomials in more detail later For now all we need to know is that they satisfy the property 1 PnXPmX dx an6nm 71 and the first few Legendre polynomials are P0X 1 P1X X P2X X2 713 P3X X3 7 3ng P4X X476X 7335 P5X X5710X395X21 It turns out that the roots of the Legendre polynomials are the nodes in Gaussian quadrature ComposileRombergrAdapliverGaussian 7 3745 Higher Order Gaussian Quadrature Formulas Theorem Suppose that X17X27 7Xn are the roots of the nth Legendre polynomial Pnx and that for each i 127 7 n the coef cients c are defined by 1 n X Xi d CI 71 Xi XJ39 X j 1 i it i If PX is any polynomial of degree less than 2n then 1 n PXdx ZCPX39 1 i1 ComposileRombergrAdapliverGaussian 7 3345 Proof of the Theorem llll Let us first consider a polynomial PX with degree less than n PX can be rewritten as an n7 1 st Lagrange polynomial with nodes at the roots of the nth Legendre polynomial Pnx This representation is exact since the error term involves the nth derivative of PX which is zero Hence A Pxdxj1 g mwl dx i1j 1 17 n 1 n x 7 Xj n d P P 11H Hj xl 9 2c ix 171 J 1 171 17 which verifies the result for polynomials of degree less than n m CompositeRombergrAdapliverGaussian 7 3945 Proof of the Theorem lllll If the polynomial PX of degree n2n is divided by the nth Legendre polynomial Pnx we get PX QXPnX RX where both QX and R X are of degree less than n 1 Since degQX lt n 711QXPnxdx 0 2 Further since X is a root of Pnx PX QX PnXi RX RX ComposileRombergrAdapliverGaussian 7 4045 Proof of the Theorem llllll 3 Now since degRX lt n the first part of the proof implies 1 n R X dx ciR X I Putting 1 2 and 3 together we arrive at 1 1 PX dx QXPnX l RX dx 71 71 1 n R X dx ciR X A Z PX 7 i1 which shows that the formula is exact for all polynomials PX of degree less than 2n D m ComposileRombergrAdapliverGaussian 7 4145 Gaussian Quadrature beyond the interval 711 By a simple linear transformation 2xiaib Ct X7 biat l b l a7 f 7 bia 2 we can apply the Gaussian Quadrature formulas to any interval abfxdX711fltbiat2wgt dt39 ComposileRombergrAdapliverGaussian 7 4245 Examples Degree Pquotx Roots Quadrature points 2 x2713 71J3 1 3 3 x3 7 3x5 fl35 0 l35 4 xquot 7 6x27 335 7086114 7033998 033998 086114 Table Quadrature points on standard interval 0642699081698724 1 Coefficients H Degree l Quadrature points l 2 l 16597 061942 l H 3 l 0 08851 0 39270 0 69688 l 0 55556 0 88889 0 55556 4 l 0 05453 0 25919 0 52621 0 73087 l 0 34785 0 65215 0 65215 0 34785 Table Quadrature points translated to interval of interest with weight coefficients CompositeRombergrAdaptiverGaussian 7 4345 Examples 7r4 665002 dx E 8 0642699081698724 0 Coefficients l H Degree l Quadrature points l l 2 l 16597 061942 l 1 1 H 3 l 0 08851 0 39270 0 69688 l 0 55556 0 88889 0 55556 4 l 0 05453 0 25919 0 52621 0 73087 l 0 34785 0 65215 0 65215 0 34785 Table Quadrature points translated to interval of interest with weight coefficients Integral approximation Error 0 642317235049753 0 0003818466489 0 642701112090729 0 0000020303920 0 642699075999924 0 0000000056988 Table Approximation and Error for GQ CompositeRombergrAdaptiverGaussian 7 4445 Homework 7 Due Friday 11132009 12 noon Part 1 Implement Composite Simpson39s Rule and use your code to solve BF443abcd Part 2 BF471ab BF472ab BF473ab BF474ab Coming up Multiple integrals and Improper Integrals ComposileRombergrAdapliverGaussian 7 4545

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.