### Create a StudySoup account

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

Already have a StudySoup account? Login here

# MATH542 MATH542

SDSU

GPA 3.61

### View Full Document

## 35

## 0

## Popular in Course

## Popular in Mathematics (M)

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

## Reviews for MATH542

### 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

t5 Biii ii 13 mum iiu Peter Blomgren blomgren peter gmail com Department of Mathematics and Statistics Dynamicai Systems Grou Computationai Sciences Research Center San Diego State University San Diego CA 9218277720 Peter Blom 1v Min mum 7 3mm 0 Introduction and Recap 0 Linear Multistep Methods Historical Overview 0 ZeroStability 9 Limitations on Achievable Order 0 The First Dahlquist Barrier 0 Example 2step Order 4 Simpson39s Rule 9 Stability Theory 0 Model Problem A Stability Polynomial 0 Visualization The Boundary Locus Method 0 Backward Differentiation Formulas Linear Mullislep Methods Quick Review Higher Order Methods for y fty Taylor When the Taylor series for fty is available we can use the expansion to build higher accurate methods RK If the Taylor series is not available or too expensive but ft 7 y easily can be computed then RK methods are a good option RK methods compute sample measure ft 7 y in a neighborhood of the solution curve and use those a combination of the values to determine the final step from fniyn t0 fn17yn1 LMM If the Taylor series is not available and fty is expensive to compute could be a lab experiment7 then LMMs are a good idea Only one new evaluation of fty needed per iteration LMMs use more of the history tnkynk k 07 75 to build up the step 53g Peter Blomgren Linear Mullislep Methods Introduction and Recap Limitations Order 1 eon Linear Mullislep Methods Historical Overview Chronology Methods 1883 Adams and Bashforth introduce the idea of improving the Euler method by letting the solution depend on a longer history of computed values Now known as AdamsBashforth schemes 1925 Nystrom proposes another class of LMM methods M0 k 7 explicit 1926 Moulton developed the implicit version of Adams and Bashforth39s idea Now known as AdamsMoulton schemes 1952 Curtiss and Hirschenfelder Backward difference methods 1953 Milne39s methods plt 4 7 4 implicit Modern Theorx 1956 Dahlquist 1962 Henrici 5351 Peter Blomgren Linear Multislep Methods Introducing Zero Stability Review Consider the LMM applied to a noise free problem k k 2 ajynH 7 2 Wm j0 10 yeneh7 0717m7k71 and the same LMM applied to a slightly perturbed system k k 2 ajynH 7 2 Wm 5nk j0 j0 yenph6p 0717k71 Ptbt39 t39lld td39 t39t39 d d fF er ur a Ions are ypica y ue o Iscre Iza Ion an roun o m Peter Blomgren Linear MulLislep Methods Introduclio Limitations on Aciii iiwnmf feim rwab itgyj Let 6n7n01N and 62n01N be anytwo perturbations of the LMM and let yn7 n 017 7 N and y 7 n 017 7 N be the resulting solutions If there eXists constants 5 and he such that for all h E 07 ho iiyn YZii S 567 0 n N whenever M 7 52H S 67 0 g n lt N the method is said to be zero Peter Blomgren rump Mill law Review Limitatici Applying the LMM to zn yn 7y I m k 2 CUan 5nk j0 2M6M71U3901 7 6n 6n 7 6 gives Formalized That is zero stability guarantees that a zero forced system with noise In infinite precision the solution stays at zero Peter Blomgren zero starting values produces errors bounded by the round off Limitatici Review iinmgika Ci i ta kot i 5 If the roots of the characteristic polynomial k Zajym 07 gt pC 0 j0 satisfies the root criterion ioi 1 112k then the method is zero stable 4 The method is convergent if and only if it is consistent and zero stable Peter Blomgren Innrod czi nd Recap Limitations on Achlevahle Order Stability Theory 7 WI I39I Tm Qermmwmdi i k lm m 1 No zero stable s step method can have order exceeding 5 1 When 5 is odd and s 2 When 5 is even mm 3 szni wm 24mm Statement lbwmm A zero stable s step method is said to be 3 i u s 2 Peter Blomgren Introduction and Recap Limitations on Achievahle Order Stability Theory We rst D Qihqu iiuhEi Qgimmmmdi eniiiikiimuei 116 No zero stable s step method can have order exceeding 5 i 1 When 5 is odd and s i 2 When 5 is even mm M aiiiiiiiiiw swimi Statement anm fiim A zero stable s step method is said to be a s 2 Wemm Simpson39s rule is optimal to be shown E if it is of order Q J h Yn2 Yn g fn2 4n1 i fn Waite Zero stability does not give us the whole picture see ab solute stability coming right up Peter Blomgren i i 7 7 is w Inni39oducziori and R39scap Limitations on Achievahle Order Stability Theory mm uiimiim 444474 We 1 Dahiiq iiuh iiijii The first Dahlquist barrier reminds us of something from Math 541 Tram Ermrs its me 0W Ferrimm es Suppose that 20 afx denotes the n 1 point closed Newton Cotes formula with X0 a Xn b and h b 7 an Then there existsE 6 37 b for which 1 n fxdx Zai xi fit is every and f E C 2a7 b and hn3fn25 n2 0nt2t71t7ndt b n 7 2cn1 xidx 22mm 5 quot 1 Ontt71t7ndt ifmi is add and f E C 1a7 b Peter Blomgren i wimp mm mum NewtonCotes Errors i The First Dahlquisl Barrier 4 way i irii Introdu and 1 Limitations on Achievahle Order 51 y Theory The First Dahlquist Barrier llllll Comments 0 For the Newton Cotes39 formulas when n is an even integer the degree of precision higher order polynomial for which the formula is exact is n l 1 When n is odd the degree of precision is only n 0 For zero stable s step LMMs when 5 is even the order is at most 5 l 2 when sis odd the order is at most 5 1 Coincidence Linear Mul 39 Introxh 39 Limitations on Acl St The First Dahlquist Barrier llllll Comments o For the Newton Cotes39 formulas when n is an even integer the degree of precision higher order polynomial for which the formula is exact is n l 1 When n is odd the degree of precision is only n 0 For zero stable s step LMMs when 5 is even the order is at most 5 l 2 when sis odd the order is at most 5 1 Coincidence Unlikely The LM Ms get the next yk1 by integrating over the solution history and the Newton Cotes39 formulas give the numerical integral over an interval Peter Blomgren Linear Mullislep Methods 9quot Order 4 7 Simpson39s Rule Introxh 39 Limitations on Ad 51 Simpson39s Rule yn1 7 yn1 fn1 4fn fn1 For notational convenience the points have been re numbered index lowered by one and we expand around the center point thn 2 3 4 4 5 5 yn yn hy H w w gt Wy 0h6 2 3 4 4 5 5 ynel yn hy h7y2 had y 7 fwy 0h6 LHS N 2hy hgyg 35 0h7 Peter Blomgren Linear MulLislep Methods Introd 39 H H Y 39 Limitations on c a i V N St my Tm lep Order 4 7 simmn t Rule Simpson39s Rule yn1 7 yn1 fn1 4fn fn1 For notational convenience the points have been re numbered index lowered by one and we expand around the center point thn 2 3 4 4 5 5 ynii N yn hy H w w gt Wy 0h6 2 3 4 4 5 5 yn71 yn hy h7y2 had y 7 fwy 0h6 LHS N 2hy hgyg 35 0h7 H N fn 7 mg 2226 7 an 37112097 f 5 0h6 4f N 4f mi N fn hf Ag an 371 55 0h6 RHS N g 622 an 74222 Oh6 Peter Blomgren Linear Mullislep Methods Innrndu d r Limitations on Ach able Order 51 39Theoi y 7 Simpson39s Rule Simpson39s Rule yn1 7 yn1 fn1 4fn fn1 LHS N 2hy hgyg 35 0h7 RHS N g 61 hzfn 12an 0076 Linear Mullislep Methods IIIV leltauons 0quot step Order 4 7 Simpson39s Rule Simpson39s Rule yn1 7 yn1 fn1 4fn fn1 H h m LHS N 2hyg 3y y50h7 RHS N g 622 W 1222 0076 Use the equation y t ft7 y ltgt yk1t fkty LHS N 2hfni fgggf 40h7 RHS N 2hfni fggjf 4oh7 LHS 7 RHS 4 h h4 714fn0h6 Linear Mullislep Methods Peter Blomgren IIIV leltauons 0quot step Order 4 7 Simpson39s Rule Simpson39s Rule yn1 7 yn1 fn1 l 4fn l fn1 ll h m LHS N 2hyg 3y y50h7 RHS N g 622 W 1222 0076 Use the equation y t ft 7 y ltgt yk1t fkty LHS N 2hfni fgggf 40h7 RHS N 2hfni fggjf 4oh7 LHS 7 RHS 4 h New fn 0h6 Simpson39s Rule Local Truncation Error LTESWWM 0 07 Linear Mullislep Methods Peter Blomgren and search for the region F h where the LMM does not grow exponentially Peter Blomgren Linear MulLislep Methods and search for the region F h where the LMM does not grow exponentially We get k k k 2 ajynj h 2 31an 7 Z BjVn 39 j0 j0 j0 Thus k 2 a1 BiWm 0 10 55 Peter Blomgren Linear MulLislep Methods Liiuitauoi Linear Stability Theory for LMMs ll We have k 2 on h jAlYHH 0 j0 A general solution of this difference equation is yn rOrn where r is a root of the characteristic polynomial k 0 2 a1 a hm r pm a hair a h j0 7rrh is called the stability polynomial m Peter Blomgren Linear MulLislep Methods am We graham A linear multistep method is said to be absr lately stable for a given if for that h all the roots of the stability polynomial 7rrh satisfy lt 1 j 12s and to be absolutely unstable for that h otherwise Peter Blomgren lDz llimlhEm We A linear multistep nlethod is said to be absolutely stable for a giveth if for that h all the roots of the stability polynomial 7rr7 h satisfy lt 1 j 12s and to be absolutely unstable for that h otherwise libxi n lf f 3 Region massage St lbl ityj The LMM is said to have the Elf RA where RA is a region in the complex h plane if it is absolutely stable for all h 6 RA The intersection of RA with the real aXis is called the inter of absolute N Peter Blomgren I i 1 ualixalion he Boundary Locus Method 39 39 is The Boundary Locus Method The boundary of RA deAnoted 872A is given by the points where one of the roots of 7rr7 h is em 872A is 3 such that 7rei97 pei9 dei 07 0 e 027r Solving for 3 gives Method Boundary Locus R0 Mei 0 e 027r Peter Blomgren Linear MulLislep Methods y The Region of Absolute Stability for Simpson39s Method Consider Simpson39s Rule and its characteristic polynomials h Yn2 Yn g fn2 4n1 l fn 1 plt lt2 717 00 5 lt2 4c1 The 872A is given by A e2i9 71 e 7 e49 6isin 0 3isin0 h0 a 7 e2ie4ei9 1 e 94e 9 42cos0 2cos0 Hence 872A is the segment 7 37 of the imaginary axis Simpson s Rule has a zero area region of absolute stability Bummer 53g Peter Blomgren Linear MulLislep Methods i r ap i A la Order Stability Theory gt I i I The Boundary Locus Method v ii Optimal Methods are not so Optimal after all 0 All optimal methods have regions of absolute stability which are either empty or essentially useless they do not contain the negative real axis in the neighborhood of the origin 0 By squeezing out the maximum possible order subject to zero stability the region of absolute stability get squeezed flat 0 Optimal methods are essentially useless Linear Mullislep Methods AdamsBashfo h Methods Stability Regions AdamsBashfo h Methods Stability Regions AdamsBashfo h Methods Stability Regions AdamsBashfo h Methods Stability Regions AdamsBashfo h Methods Stability Regions AdamsBashfo h Methods Stability Regions w w w Peter Blom Adam s S Moulton Methods t ability Regions 5 4 The Exterior of the circle Linear Mul 39 Adam sM S oulton Methods t ability Regions Linear Mul 39 Stability Regio Adam s S M oulton Methods t ability Regions Peter Blom Stability Regio Adam s S M oulton Methods t ability Regions Peter Blom Stability Regio Adam s S M oulton Methods t ability Regions Peter Blom Adam sMoulton Methods Stability Regions Peter Blom Linear Mul 39 I i I he Boundary Locus Method v 39 ii ualixalion So far we have seen only two methods which produce bounded solutions to the ODE for all Re lt 0 Implicit Euler Adams Moulton n 1 Yn1 Yr hfn1 Trapezoidal Rule Adams Moulton n 2 yn1 yn l 2 fn1 l fn The size of the stability region located in the left half plane tends to shrink as we require higher order accuracy requiring a smaller stepsize h Peter Blomgren Linear Mullislep Methods 5351 Backward Differentiation Form u las Can we find high order methods with large stability regions Yes The class of Backward Differentiation Formulas BDF defined by k ajynj h kfnk 10 have large regions of absolute stability Note that the right hand side is simple but the left hand side is more complicated the opposite of Adams methods Peter Blomgren Linear MulLislep Methods Deriving BDF llV The kth order BDF is derived by constructing the polynomial interpolant through the points tn17yn17 tnvyn7 7 tnik17nik17 ie after re numbering the points 07 17 7 k fifl k Pklt ZynmLkmt7 Where Lkmt 7 fl m0 l0l7m t and then computing the derivative of this polynomial at the point corresponding to tn1 and setting it equal to fn1 Peter Blomgren Linear MulLislep Methods Liiuitauoi Deriving BDF IIIV Newton s Backward Difference Formula Math 541 comes in handy We can write the interpolating polynomial k 5 Pkfn1 5h Yn1 Z1Jlt J gtijn1 11 where Newton39s divided differences are 1 VYnJrl Yn1 Yn V2YnJrl E VYnJrl 7 VYn7 Peter Blomgren Linear MulLislep Methods Deriving BDF IIIIV The binomial coefficient is given by is 7575717sij171jss1sjil j j 139 In order to compute PLtn1 we need to compute i 5 d5 j 50 Massive application of the product rue gives us d is 171 41 i 1 17 7 ds lt j gt 39 50 That is 1 21 k 1 hPLfn1 j V yn1 Zjvjyn j 1 j1 Peter Blomgren M Linear Mullislep Methods I39 I is Orr in 1 i V 1 Stability Theory Backward D rentialion Formulas Deriving BDF IVIV We now have R 1 I Z ijyn1 hfn1 1 J j Making sure that the coefficient for yn1 is 1 71 71 k 1 k 1 J k 1 Z i 2 TV yn1 h i fn1 11 J 11 J 11 J Peter Blon ren 1 Methods BDFs k126 k BDF LTE 1 Yn1 Yn hfn1 h 2 Yn1 Yn Yn71 h w1 7th 3 Yn1 Yn Yn71 Yn72 h 11 23773 4 Yn1 Yn gig il EigYniz 23 5Yn73 h 11 h4 5 Yn1 Yn Yn71 Yn72 Yn73 Yn74 hfn1 h5 6 Yn1 Yn Yn71 Yn72 Yn73 Yn74 Yn75 hfn1 Eh These are all zero stable BDFs for k 2 7 are not zerostable Peter Blom Linear Mul 39 nu 0rd in y n i V i Stability Theory Backward Di erenLialion Formulas Stability Regions for BDF Methods BDF Methods Stability Regions i i The Exteriors Linear Mul nu 0rd in y n i V i Stability Theory Backward Di erenLialion Formulas Stability Regions for BDF Methods BDF Methods Stability Regions i i The Exteriors Linear Mul nu orii ill Stability Theory Backward Di Stability Regions for BDF Methods BDF Methods Stability Regions i The Exteriors Part of Left Half Plane Linear Mul DF Methods Stability Regions The Exteriors Part of Left Half Plane Linear Mulu lep Method nu orii ill Stability Theory Backward Di Stability Regions for BDF Methods BDF Methods Stability Regions The Exteriors Part of Left Half Plane Linear Mul BDF Methods Stability Regions Linear Mulu lep Method

### 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

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

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

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