New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Burnice Ratke


Burnice Ratke
GPA 3.72


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 13 page Class Notes was uploaded by Burnice Ratke on Tuesday October 20, 2015. The Class Notes belongs to MATH 541 at San Diego State University taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/225274/math-541-san-diego-state-university in Mathematics (M) at San Diego State University.




Report this Material


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 07 Numerical Differentiation and Integration Differentiation Richardson s Extrapolation Integration Peter Blomgren ltblomgrenpeter gmail com Department of Mathematics and Statistics Dynamical Systems roup Computational Science Raearch Center San Diego State University San Diego CA 921827720 httpterminussdsuedu Outline 9 Numerical Differentiation 0 Ideas and Fundamental Tools 0 Moving Along a Richardson39s Extrapolation 0 A Nice Piece of Algebra Magic 0 Homework 6 Preliminary Version 9 Numerical Integration Quadrature 0 The Why and Introduction 0 Trapezoidal amp Simpson39s Rules 0 Newton Cotes Formulas O Homework 6 Final Version Richardson39s Extrapolation f fgtltdgtlt 7 151 Richardson39s Extrapolation f fgtltdgtlt 7 251 Numerical Differentiation The Big Picture Numerical Differentiation Definition Derivative as a limit The goal of numerical differentiation is to compute an accurate The derlvatlve Of f at X0 395 approximation to the derivatives of a function XO h XO fXo imof A Given measurements 0 of the underlying function fX at the node values Xi0 our task is to estimate fx and later higher derivatives in the same nodes The obvious approximation is to fix h small and compute The strategy Fit a polynomial to a cleverly selected subset of the fXO m M nodes and use the derivative of that polynomial as h the approximation Of the derivative Problems Cancellation and roundoff errors For small values Richardson39s Extrapolation ffxdx m 351 of h fX0 h m fX0 so the difference may have very few significant digits in finite precision arithmetic gt smaller h not necessarily better numerically 535 7451 2 Richardson39s Extrapolation f fgtltdgtlt Main Tools for Numerical Differentiation lof2 Main Tools for Numerical Differentiation 2 of 2 In the discussion on Numerical Differentiation and later Integration we will rely on our old friend nemesis the Taylor expansions Theorem Taylor s Theorem Suppose f E Cquota7 b f 13 on a7 b and X0 6 a7 b Then VX 6 a7 b 35X E minX0X7 maxX0X with f X PnX RnX where quot k quot1 Px if X x 7 w Rnx f n g x 7 X0quot1 PX is the Taylor polynomial of degree n and RX is the remainder term truncation error Our second tool for building Differentiation and Integration schemes are the Lagrange Coefficients Recall Ln7kX is the nth degree polynomial which is 1 in Xk and O in the other nodes Xj7 j i k Previously we have used the family Ln70X Ln71X Ln7X to build the Lagrange interpolating polynomial A good tool for discussing polynomial behavior but not necessarily for computing polynomial values cf Newton39s divided differences Now lets combine our tools and look at differentiation AR m Richardson39s Extrapolation f fxdgtlt 7 551 Richardson39s Extrapolation f fgtltdgtlt 7 651 Getting an Error Estimate Taylor Expansion Using Higher Degree Polynomials to get Better Accuracy Suppose X0X17 7X are distinct points in an interval I and f E C 1I we can write f X h 7 f X W fXo hfXo hgf x fxo n H X Xk k 7 fXo gf 5x fx k axonx W wkax 0 t 1 If f X is bounded le Lagrange Interpi Poly Error Term f X lt M7 V500 E XOVXO h Formal differentiation of this expre55lon glves h h f f L d Hid 9 fltn1gtlsl X X X 7 X t en we ave 70 k quot k dX n 1 fX0h7fX0 Mlhl T m f X0 N f With an error less than HZOX 7Xk i fn1EX 39 n 1 dX Thls 395 the apprOleatlon error39 Note When we evaluate f ltj at the node points the last term Roundoff error emach x 10 not taken into account m gives no contribution 2 we don39t have to worry about it Richardson39s Extrapolation f fxdgtlt 7 751 2 Richardson39s Extrapolation f fxdgtlt 7 351 Exercising the Product Rule for Differentiation a l iriing 1 n 1 1 n n W H Hr 10 kok j Now if we let X X for some particular value of 6 only the product which skips that value ofj E is non zero eg 1 n n W H Hr 10 kok j Example 3 point Formulas llll Building blocks X 7 MW 7 X2 L2ox 7 my 7 W L21X 7 X1 7 x0X1 X27 i w L22X X2 7 X0X2 X07 Formulas fXj too i fX2 X7X1X7X2X7Xnx7xox7xzX7Xnml 1 I1 x Homoq 7 Xk 539 Richardson39s Extrapolation ffxdx 2X1 7 X1 7 X2 X0 X1X0 7 X2 2X1 7 X0 7 X1 X2 7 X0X2 7 X1 Richardson39s Extrapolation ffxdx The n 1 point formula for approximating fXj Putting it all together yields what is known as the n 1 point formula for approximating fXj2 WW5 f X39 f X L X39 7 X 7X J g k nk J n J k J Note The formula is most useful when the node points are equally spaced it can be computed once and stored ie Xk X0 kh Now we have to compute the derivatives of the Lagrange coefficients ie LnykX We can no longer dodge this task m Richardson39s Extrapolation f fgtltdgtlt 7 1051 Example 3 point Formulas lllll When the points are equally spaced 1 h2 f xo 73fxo W1 7 fX2 gram 1 h2 3 f X1 7 7fXo fX2l 7 gf 51 1 h2 3 f ltle fxo 7 W1 3fX2 f 52 Use X0 as the reference point Xk X0 l kh 1 h2 f xo 73fxo 4fxo h a We 2h Ftwo 1 h2 r x0 h E 400 fx0 2h 7 Erma 1 h2 r x0 2h fx0 7 4fx0 h 3fx0 2h Fl 352 2g Richardson39s Extrapolation f fgtltdgtlt 7 1251 Example 3 point Formulas IIIIII 1 h2 f x0 73fx0 4fx0 h 7 fX0 2h 714350 96 1 hz 3 f X0 E I flxo h quot0 II ff 51 1 I72 3 f x0 7 g m 7 2h 7 X0 7 h 3m l at 52 After the substitution X0 7l7 h 7 X3 in the second equation and X0 7l7 2h 7 X in the third equation Note1 The third equation can be obtained from the first one by setting h 7gt 7h Note2 The error is smallest in the second equation Note3 The second equation is a twosided approximation the first and third one si ed approximations Note4 We can drop the superscripts f m Richardson39s Extrapolation ffxdx 7 1351 3 point Formulas Illustration Forward Formula 3 point Formulas Illustration Centered Formula fxo 7 7fxo 7 h x0 h 7 2f351 m Richardson39s Extrapolation f fgtltdgtlt 7 1451 3 point Formulas Illustration Backward Formula 2 fxo 7 217h73fxo 4fx0 h 7 x0 2h gram 2 Richardson39s Extrapolation ffxdx 7 1551 fxo 7 2717 fx0 7 2h 7 4fxo 7 h 3fxo hgfmaz gas 7 Richardson39s Extrapolation f fgtltdgtlt 7 1651 5 point Formulas 5 point Formulas Illustration Centered Formula If we want even better approximations we can go to 4 point 5 point 6 point etc formulas The most accurate smallest error term 5 point formula is fXO W f55 Sometimes eg for end point approximations like the clamped splines we need one sided formulas fXO 725fx048fx0h736fxi12h16fx03h73fx04h i 54 1435 fXO W f55 539 Richardson39s Extrapolation f fgtltdgtlt 7 1751 Richardson39s Extrapolation f fgtltdgtlt 7 1351 Higher Order Derivatives Wrapping Up Numerical Differentiation We now have the tools to build high order accurate approximations We can derive approximations for higher order derivatives in the t0 the derivative same way Fit a kth degree polynomial to a cluster of points Xi7 fXrilIlt1i and compute the appropriate derivative of the We Will use these tools and Similar techniques in building Polynomial in the POint of interest integration schemes in the followmg lectures The standard centered approximation of the second derivative is Also these aPPrOleatlons are the baCkbone Of nite difference given by methods for numerical solution of differential equations see Math 542 and Math 693b f X h 7 2f X f X 7 h fX0 W Oh2 Next we develop a general tool for combining low order accurate approximations to derivatives integrals anything almost in order to hierarchically constructing higher order approximations m 5393 2 Richardson39s Extrapolation f fgtltdgtlt 7 1951 25 Richardson39s Extrapolation f fgtltdgtlt 7 2051 Richardson s Extrapolation Building High Accuracy Approximations lV What it is A general method for generating high accuracy results using low order formulas Applicable when The approximation technique has an error term of predictable form eg 00 M 7 VJh Z Ekhk k7 where M is the unknown value we are trying to approximate and the approximation which has an error Ohj Consider two first order approximations to M M 7 N1h Z Ekhquot k1 and w hk M 7 N1h2 Z Ek27k k1 If we let N2h 2N1h2 7 N1h then H M 7 N2h 7 2E 7 E1hZEEhk k2 Procedure Use two approximations of the same order but with 0 different h eg Njh and Combine the two Where approximations in such a way that the error terms of ES Ek lt klil 7 1gt order h cancel 2 99 Hence N2h is now a second order approximation to M m Richardson39s Extrapolation f fgtltdgtlt 7 2151 Richardson39s Extrapolation f fgtltdgtlt 7 2251 Building High Accuracy Approximations llV Building High Accuracy Approximations IllV We can play the game again and combine N2h with N2h2 to get a Let s derive the general update formula Given third order accurate approximation etc M 7 NJh Ejhi 0 W1 4Nh27Nh Nh27Nh N3h42 2 N2h2 2 3 2 h hm MMh2 LilTm N h 2 7 N h N40 N3h2 M We let mi 7 Ami2 Nj1h aJNJh two2 In geilertal Zombining 39twot39jth order approximations to get a However if we want Nj1h to approximate My we must have J s or er apprOXIma ion aj j 1 Therefore Nhz A Nlh Nj1h lehZ J h 2171 M7N h Eh 17 E7 Cir1 l m 11 0 11 0 1 121 l m Richardson39s Extrapolation f fgtltdgtlt 7 2351 2 Richardson39s Extrapolation f fgtltdgtlt 7 2451 Building High Accuracy Approximations lVV Now 1 M 7 Vj1h Ejh la 1 7 04 0W We want to select 09 so that the expression in the bracket is zero This gives 71 2139 217 1 1 1 WE l ai W12J71 Therefore Nj1h two2 Building High Accuracy Approximations VV The following table illustrates how we can use Richardson39s extrapolation to build a 5th order approximation using five lst order approximations 0h 0012 0013 0014 9015 N107 N1h2 N207 N1h4 N2h2 N3h N1h8 N2h4 N3h2 N407 N1h16 N2h8 N3h4 N4h2 N507 T Measurements T Extrapolations T 539 53539 Richardson39s Extrapolation f fxdgtlt 7 2551 Richardson39s Extrapolation f fgtltdgtlt 7 2651 Example cf slide13 and slide17 Example fX XZGX The centered difference formula approximating f x0 can be expressed fx h 7 fx7 h h2 fx 2xX2eX f Xo 7 if 5 0h4 i 2 7 2h 6 X 0 f 2 7 8e 7 59112 N2h error term 1 7O 15 8197 f I I w i 64 566 Fwd Difference 2 7 Pt In order to eliminate the h2 part of the error we let our new 13980 196009 0 1 aPPlemath be 13990 24391361 w 59384 Ctr Difference 3pt N h 2 N h 200 295562 0 2 N3h N2h2 210 360128 60201 Ctr Difference 220 436811 f h f h fxh7fx7h7fx2h7fx72h 230 521634 459384 602013 59111 Richardson 7 X i X 2n 4n N32h 7 2n 3 r1s7sr19sr217r22 59 111 5Pt 7 sfxh7sfx7h 7 fx2h7fx72h 12 39 39 6h 6h 1hfx 7 2h 7 8fx 7 h 8fx h 7 fx 2h 93 535 Richardson39s Extrapolation f fxdgtlt 7 2751 2 Richardson39s Extrapolation f fxdgtlt 7 2351 Wrap up Homework 6 Due Friday 1162009 12 noon We are going to use Richardson extrapolation in combination with some of the simpler integration schemes we will develop in order to generate general schemes for numerically computing integrals up to high order Note In order to use Richardson extrapolation we must know the form of the error hence finding error terms in our approximations turns out to have a very practical use Integration lntroduction The quotWhyquot After taking calculus I thought I could differentiate andor integrate every function Then came physics mechanical engineering etc The need for numerical integration was painfully obvious Sometimes most of the time the anti derivative is not available in closed form Part 1 x dX FX c BF 415 Iv I BF4 1 AntkDetlvatlve BF4 2 9 539 53539 Richardson39s Extrapolation f fxdgtlt 7 2951 Richardson39s Extrapolation f fgtltdgtlt 7 3051 Numerical Quadrature Building Integration Schemes with Lagrange Polynomials Given the nodes X0X1 Xn we can use the Lagrange The basic idea is to replace integration by clever summation interpolating polynomial b i quot fltn1gts 1 quot fX dX 7 af P X X fL 39X With error E X xix a 0 n I nl 7 n n I l0 l0 where a 3 X0 lt X1 lt lt X S b f fX to Obtain b b b H The coefficients a and the nodes X are to be selected fx dx PX dX EX dx 2 a a hV l The Approximation The Error Estimate 5331 535 Richardson39s Extrapolation f fxdgtlt 7 3151 2 Richardson39s Extrapolation f fxdgtlt 7 3251 Identifying the Coefficients b b n n b n PX dX Z LnHX dX Z 25 Lnx dX 2 ag a a 0 0 a 70 3i Hence we write b n fX dx x Zam a 0 with error given by b b n1 X n Ef EXdx gvix dx Example 1 Trapezoidal Rule llll Let a X0 lt X1 b and use the linear interpolating polynomial P1XfbiX1f1X7XO 7X1 X1 X0 Note Can we change the order of integration f and summation E as we did above In this case where we are integrating a polynomial over a finite interval it i OK For technical details see a class on real analysis eg Math 5348 m m Richardson39s Extrapolation ffxdx 7 3351 Richardson39s Extrapolation f fxdx 7 3451 Example 1 Trapezoidal Rule lllll Example 1 Trapezoidal Rule llllll Thequot Hence b X1 X 7 X1 X 7 X0 b 2 2 X1 3 wa fo X X X X dx poo fol wax loll M H finE a X3 X1 0 1 1 0 a 2X0 7 X1 2X1 7 X0 X0 12 7 f sxx a xoxx 7 x1 dx X 7 X h3 2 Xe M lfo a 7 4W5 2 12 The error term use the Weighted Mean Value Theorem x1 X1 b 3 f f h f sxx a xoxx 7 x1 dx We x a xoxx 7x1 dx ax dx h M 7 7W5 h b a a x0 x0 a 2 12 3 X1 3 7w Xi mxz X0X1X2 iifK il 3 2 X0 6 where hX1 7X0 bia 39739 S353 Richardson39s Extrapolation ffxdx 7 3551 Richardson39s Extrapolation f fxdx 73651 Example Za Simpson s Rule suboptimal error bound Let X0 a X1 7 X2 b let h and use the quadratic interpolating polynomial X 7 MW 7 X2 X 7 XoX 7 X2 b X2 W x lflxolm i X fag X X0 X1 dX X2 7 X0X2 X1 ngg ig g hmgvam WuwxhF i g i qomnman Example Qb Simpson s Rule optimal error bound The optimal error bound for Simpson s rule can be obtained by Taylor expanding fX about the mid point X1 X W X A X M xii mm 7 x1 7 2 1x 7 x1 7 5 7 x03 if 5 x 7 x04 Then formally integrating this expression fgtlt1X 7 X02 fHX1 3 x x 2 6 1 4 X fab lfx1fx1x7x1 7 5 Mimi ax After use of the weighted mean value theorem and thezthe approximation f X1 h712fxo 7 2fX1 fX2 7 f4 and a whole lot of algebra see BF pp 189 190 we end up with X2 X X fX04fX1fX2 7L5 X0fd h 3 90f 5 99 Richardson39s Extrapolation f fgtltdgtlt 7 3751 Richardson39s Extrapolation f fgtltdgtlt 7 3351 Example 2 Simpson s Rule Integration Examples b X0 4fX1 fX2 5 4 dX h l fX ab 7 fxdx Trapezoidal Error Simpson Error a x 01 12 0 05 0 x2 01 13 05 016667 033333 0 x3 01 14 05 025000 025000 0 x4 01 15 05 030000 020833 00083333 ex 01 6 7 1 18591 014086 17189 00005793 x XVSimpsm sRule The Trapezoidal rule gives exact solutions for linear functions The error terms contains a second derivative Simpson s rule gives exact solutions for polynomials of degree less than 4 The error term contains a fourth derivative 5331 535 Richardson39s Extrapolation f fgtltdgtlt 7 3951 f X Richardson39s Extrapolation f fgtltdgtlt 7 4051 Degree of Accuracy Precision Definition Degree of Accuracy The Degree of Accuracy or precision of a quadrature formula is the largest positive integer n such that the formula is exact for Xk k01n Newton Cotes Formulas Two Types Closed The n 1 point closed NCF uses nodes X X0 1h 139 01 7n whereXO a X band h bian It is called closed since the endpoints are included as nodes Closed p With this definition I Scheme Degree of Accuracy Trapezoidal 1 Simpson s 3 Trapezoidal and Simpson s are examples of a class of methods l i7 i l 7 Xll Ii 392 39n l le 7 39 known as Newton Cotes formulas m 53539 Richardson39s Extrapolation f fgtltdgtlt 7 4151 Richardson39s Extrapolation f fgtltdgtlt 7 4251 Newton Cotes Formulas Two Types Open Closed Newton Cotes Formulas Open The n 1 point open NCF uses nodes X X0 ih iO1nwhere hbian2 and X0 ah Xn b 7 h We label X11 a Xn1 b The approximation is b n fX dxm Zai xi a 0 where n Xquot Xquot X 7 X a L 739XdX ijdx I X quotI x w 1 Note The Lagrange polynomial Ln739X models a function which takes the value 0 at all Xj j i i and 1 at X Hence the l l l u39i Nu xi x2 In xiib I coef CIent a captures the Integral of a function which is 1 nu in X and zero in the other node points 535 Richardson39s Extrapolation f fgtltdgtlt 7 4351 2 Richardson39s Extrapolation f fgtltdgtlt 7 4451 Closed Newton Cotes Formulas Error Theorem Suppose that 20 afX denotes the n l 1 point closed Newton Cotes formula With X0 a Xquot b and h b 7 an Then there exists 5 6 a7 b for which 17 7 quot hn3fn25 A fxdx 7 afx W quott2t7 1t7 ndt 0 ifn is even and f E Cquot2a7 b and hn2fn15 b n A fxdx gamer H 1 quottt71t7ndt 0 Closed Newton Cotes Formulas Examples n 2 Simpson s Rule h h5 4 7 fXo 4fX1 fX2 if 5 3 90 n 3 Simpson s g Rule 3h 375 g fxo 3fx1 3fx2 fXs a Erma n 4 Boole s Rule ifn is odd and f 6 CW1 a b 2h 8h7 l l E mm 7 32 7 12mg 7 32fX3 7 7fX4 7 ning N t th t h 39 39 t th d f 39 39 39 1 o e a w en n Is an even ln eger e egree o preCI5lon ls n When n ls odd the degree of preCI5lon ls only n Richardson39s Extrapolation f fgtltdgtlt 7 4551 Richardson39s Extrapolation f fgtltdgtlt 7 4651 Open Newton Cotes Formulas Open Newton Cotes Formulas Error Theorem Su ose that Z afX denotes the n 1 point open Newton Cotes Th t pp 0 e approx39ma Ion ls formula With X71 a Xn1 b and h b 7 an l 2 Then there b Xn n existsE 6 a7 b for Which a x dx 7 X x dX m Zarnxr W wm 2 1 0 fxdx 2am n 2 I t t7 1 t7 ndt where ifn is even and f E Cquot2a7 b and Xn1 xquot 7 X 7 X a Ln739X dX 7 dx 7 7 quot hquot2fquot15 quot1 X71 X0 111 XI 7 X1 fxdx7 ganxw W 71 tt 7 1 t 7 ndt j 7b i ifn is odd and f E Cr39l1a7 b Note that when n is an even integer the degree of precision is n l 1 m When n is odd the degree of precision is only n m Richardson39s Extrapolation f fgtltdgtlt 7 4751 2 Richardson39s Extrapolation f fgtltdgtlt 7 4351 Open Newton Cotes Formulas Examples Divide and Conquer Say you want to compute hs 100 n 0 2hfx0 3l g 0 f X dX Is it a Good ldeaTM to directly apply your favorite Newton Cotes 3h 3h3 formula to this integral 1 7 f f if n 2 l x0 ml 4 s No 5 With the closed 5 point NCF we have h 25 and h590 105 so n 2 2fx0 7 fx1 2fX2 414h 744 even with a bound on f6 the error will be large 3 45 Better Apply the closed 5 point NCF to the integrals 4i1 5h 9575 n 3 1mm fX1 xz 11mg rms fx dxy I 0717 724 I m then sum Composite Numerical Integration next time m Richardson39s Extrapolation f fgtltdgtlt 7 4951 Richardson39s Extrapolation f fgtltdgtlt 7 5051 Homework 6 Due Friday 1162009 12 noon Part 1 BF4 1 5 BF4 1 27 BF4 2 9 Part 2 BF 431 ab BF 435 ab m 2 Richardson39s Extrapolation ffxdx 7 5151


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

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


"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.