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

### View Full Document

## 10

## 0

## Popular in Course

## Popular in Mathematics (M)

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

## Popular in Mathematics (M)

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

Ei Peter Blomgren blomgren peter gmail com namicai Syste Department of Mathematics and Statistics Dy Group Computationai Sciences Research Center 8 an Diego tate University San Diego CA 921827 720 Spring 2009 Peter Blom gumyr Outline 0 Recap Last Lecture 0 Finding Stability Regions 0 Euler39s Method 0 Taylor Series Methods 9 RungeeKutta Methods 0 Introduction 0 Derivation Peter Blom Last Lecture Quick Review Euler s Method 0 Analysis Local Truncation Error LTE Consistency Accuracy Stability Region of Stability Convergence Improvements 0 Higher order Taylor Series Methods 0 Multi Point Methods 0 Heun39s Method 9 Euler39s Midpoint Method Peter Blomgren quot i amp RKrMeduods 7 334 Sta bility Regions Revisited Recall Euler39s Method Yn1 Yn l hftn7n7 yt0 YO applied to t MU gives yn1 yn hAyn 1 Wyn 1 meo The stability criterion is non exponential growth l1hl1 Peter Blomgren Stability Regions Revisited 8 RK MQ39JIOdS 7 434 R L Findin su Euler Method yRe 1 Fun Knua Mo Finding the Stability Reion How do we find the stability region from the expression i1 hi S 1 The boundary of the region is given by 1hei9 cgt hequot971 ee027r i i a 7 Eulu39s Mama ed amp RKrMeduods 7 534 in tahi Re IS j V RilngeKntta Methods Tay39 quot9 M quot l Order Taylor Series Methods Stability Regions for Higher Consider n hk k hn1 n1 Yfi1 2 my ti my 507 5i 6 1771741 0 t yt we have y f Ayf AZYU k Now with y So WW Yf And it follows that h n1 yn15i7 5i 6 1771741 n 5351 Peter Blomgrel Stability Regions Revisited 8 RK MQ39JIOdS 7 534 The stability criterion is given by the relation n k i1 Yfi1 yf0 i k0 lt1 hquot 2 k0 Again the boundary is given by Peter Blomgren IS Revisited 8 RKeMemods 7 734 Metho ls Plotting the Boundary of the Stability Region For n 4 we have W m3 24 l 6 2 hlie 90 matlabgtgt zroots124 16 12 1 1expi0 Now vary 0 in the interval 07 27139 collect all the roots and plot in the complex plane X realz y imagz quot 2 Figure The circle corresponding to Euler39s Method is included for 72 comparison Peter Blomgren Stability Regions Revisited 8 RK MQ39JIOdS 7 334 y R j V um Me Methods Rm Findinlk Slahi 539 Some Comments on Higher Order Taylor Series Methods In the cases where the derivatives fkty can be computed higher order n gt 1 Taylor series method are superior to Euler39s method Taylor order 1 for two reasons 0 The local truncation error is smaller N 9h e The region of stability is larger allowing for slightly larger step sizes h Next slide shows the stability regions for Taylor39s Method of orders 1 through 8 Peter Blomgren IS Revisited 8 RKeMemods 7 934 t L tL n 3 Stability R ons Fhln Kan Methoda Tay39 59 M quotS Regions of Stability for Taylor39s Method 7 12 i i i b i Euler s Method O Taylor n2 Taylor n3 Taylor n4 2 7 Taylor n5 7 Taylor n6 7 Taylor n7 7 Taylor n8 Improving Euler39s Method Alternatives When the derivatives of fty cannot be computed f may be a result of measurements andor is too expensive to computeevaluate we need alternative approaches to improve on Euler39s Method We are going to explore the following approaches 0 Runge Kutta Methods 0 Linear Multistep Methods 0 Predictor Corrector Methods There is significant overlap between these different approaches hence we will rediscover some methods in several contexts Peter Blomgren quot i amp RKrMeduods 7 1134 F39 St iLy RungeKuua Methods Ru nge Kutta Methods Runge Kutta RK methods 0 One step methods moving from time tn to time tn Still easy to build adaptive methods ifwhen necessary step length changes on the fly are easy 0 Breakscomplicates linearity the structure of the local error becomes more complicated Catch 22 Easy to change step size since it is a onestep method but hard to tell when it is needed local error compli cated Peter Blomgren quot i amp RKrMeduods 7 1234 Linear Multistep Methods Reverse Catch 22 When we look at Linear Multistep Methods which use multiple points yn yn1 yrkk in order to compute n1 we will see that they have the reverse problem 0 for this class of methods it is easy to estimate the local error a easy to know when a change in step size is necessary to maintain a certain level of local accuracy 0 but the multistep structure makes it hard to change the step size Peter Blomgren quot i amp RKrMeduods 7 1334 A General s stage RK method A general s stage RK method for the problem y f ff7y7 yfo yo is defined by yn1 yn h biki i1 where the kis are multiple estimates of the right hand side ft 7 y S kf tncih7ynhZaUkJ 12s j1 with the following row sum condition 5 Ci E aid 172775 11 Peter Blomgren IS Revisited 8 RKeMemods 7 1434 lt Sm Ly RungeKulla Methods k1 fU mYn 6107 alj0 k2 ftnhynhk1 scz1 3211 3220 k k 1 yn1 ynhii b1b2 The Butcher Array describing Heun39s Method C1 311 312 0 O 0 am 312 1 1 0 Peter Blomgren Stability Regions Revisited 8 RKrMedlods 7 1534 Exam ple k1 ftn7n gt Cl 07 31 7 h k h k2 flttn 7yn 62 7 321 7 3220 yn1 yn hkg gt b1 07 b2 1 The Butcher Array describing Euler39s Midpoint Method Peter Blomgren IS Revisited amp RKrMemods 7 1534 14 take RKrmelhods r m Kuua Methods The Butcher Array The Butcher array for a general s stage RK method is 311 312 315 321 322 325 n gt 6391 1 355 b1 b2 b We define the s dimensional vectors b E and the s x s matrix A E b1b2bs7 a c17c2csT A aw131 d 8 RKrMedlods m Kuua Methods 3 Types of RK methods Illl 0 Explicit eg Heun39s and Midpoint o If each only depends on previously computed k i ltj then the method is explicit and the matrix A is strictly lower triangular Le the elements on and above the diagonal are zero F39 sx iLy RungeKuua Methods 3 Types of RK methods IIIII o Semi implicit o If A is lowertriangular with nonzero entries on the diagonal then each k is defined by a nonlinear system i kf tncih7ynZaika 172ius We have to solve s nonlinear but uncoupled systems of equations in each iteration Butcher 1965 calls these methods Semi implicit Norsett 1974 Semi explicit and Alexander 1977 Diagonally Implicit RK or DIRK methods Peter Blomgren quot I x RKrMediods 7 1934 L t I ability V 39 V Km Methods Types oi RKrmeuwds 3 Types of RK methods IIIIII 0 Implicit a If A is a general matrix nonzeros above the diagonal then each k is defined by a nonlinear system 5 kif tncih7ynZaika 1727m7 11 We have to solve s nonlinear coupled systems of equations in each iteration This is a daunting computational task which we will try to avoid 39 iled 8 RK Mediod F39 sx iLy RungeKuua Methods A Remark on RK methods One Point of View RK methods constitute a sensible idea The unique solution to a well posed initial value ODE problem y f ff7y7 yfo yo is a single curve in ty space Solutions to the same ODE with slightly different initial conditions form a family of solutions Peter Blomgren quot i amp RKrMeduods 7 2134 A Remark on RK methods One Point of View Due to numerical errors truncation and roundoff errors any numerical solution wanders off the exact solution curve The numerical solution is affected by neighboring solutions RK methods gather information information about this familY39 of solution curves An explicit RK method sends out feelers into solution space gathering samples of the derivative and then decides in what direction to take the final Euler like step Paraphrased from JD Lambert quotNumerical Solutions for Ordinary Differential Systems the Initial Value Problem Peter Blomgren quot l 8 RKrMedlods F39 St iLy RungeKuua Methods Derivation Deriving Explicit 1 stage RK methods The Butcher array for an 1 stage RK method has the form C1 311 b1 If we want an explicit scheme then an 0 and since 1 ELI 31 s we have 1 0 Further consistency requires that Z bj 1 so b1 1 We are left with 0 0 1 k1 ftn7n yr yn l hkl yn l hft ryn7 Euler s Method We have yet to prove this condition Peter Blomgren quot i amp RKrMeduods 7 2334 Sm Ly lt s RungeKutta Methods Derivation Deriving Explicit 2 stage RK methods llll The Butcher array for a 2 stage explicit RK method has the form 0 0 0 0 0 0 Cg all 0 N Cg CQ 0 l b1 b2 l b1 17 b1 Hence k1 ftn7n k2 ftn 9th 2hk1 yn1 yn h b1k1 1 b1k2 describes all possible explicit 2 stage RK methods How do we choose the parameters 2 and b1 Taylor Expansion of course m Peter Blomgren Stability Regions Revisited 8 RK MQ39JIOdS 7 2434 Sm Ly lt s RungeKutta Methods Derivation Deriving Explicit 2 stage RK methods lllll With the following Taylor expansions yn 7 yn hf Lia 0h3 k1 n k2 ffn Cgh7yn Cghkl fn 62hffniyn Czhfnaiyftn7yn 0W We can define the Local Truncation Error LTEh 7 7 blkl 717 bakz if 0h2 7 8 8 7lb1fn 717 b1 mmv lam 67fquot h 7 a a a a 2 7 E bZCZh Oh Peter Blomgren Stability Regions Revisited 8 RK7MetJ10ds 7 2534 lt Sm Ly RungeKutta Methods Derivation Deriving Explicit 2 stage RK methods IIIIII We have 7 h a a a a 2 LTEh 7 5 am 6721217 b2C27 am 12 22 007 Now if 27 bgCgh O ltgt2bgCg 1 we get LTEh N 9h2 ie our 2 stage RK method is second order The corresponding family of Butcher arrays is O O O Cg Cg O 1712C2 12Cg Sanity check Cg 12 gives Euler39s Midpoint Method and Cg 1 7 2534 gives Heun39s Method Stability Regions Revisited 8 RKrMetJIods Peter Blomgren inethods We can use the same approach Taylor expansion and parameter matching to find higher order explicit RK methods n matura questicm Is this the best way of deriving the RK methods There are more elegant methods for deriving the RK methods Most of the work was done by Butcher starting in the mid 1960s The methods depend on defining the Frechet derivative and also requires some basic under standing of graph theory rooted trees Butcher JC 1987 The Numerical Analysis of Ordinaiy Differential Equations Runge Kutta and General Linear Methods Wiley Chichester Peter Blomgren lt Sm Ly RungeKuua Methods Derivation Example 3 stage RK method C1 311 312 313 0 O 0 0 62 321 322 323 12 12 0 0 63 331 332 333 7 1 71 2 0 b1 b2 b3 16 23 16 1 ftnyn amp k2 flttn27yn 2 k3 f tn hyn 7 hkl 2th Yn1 Yr k1 4k2 k3 See next slide for visualization Peter Blomgren Stability Regions Revisited 8 RKrMedlods 7 2334 Example 3 stage RK method One Step Figure Different stages of one step of the 3stage RK method 39 iled 8 RK Medlod L0 re F39 taini 9 RungeKutta Methods Derivation Example 4 stage RK method Attributed to Runge Cl 311 312 313 314 0 0 0 0 O 62 321 322 323 32 12 12 0 0 0 63 331 332 333 33A 12 0 12 0 0 C4 34 343 343 a44 1 0 0 1 0 ibl b2 b3 b4 i16 13 13 16 1 ftnyn kg 2 tn gm L51 k3 2 tn gm L k4 f tn hyn hkg yn1 yngk12k22k3k4 5353 Peter Blomgrel Stability Regions Revisited 8 RK MQ39JIOdS 7 Bil34 Example Runge s 4 stage method One Step Peter Blom L0 re F39 taini 9 RungeKutta Methods Derivation Example 4 stage RK method Attributed to Kutta Cl 311 312 313 314 0 0 0 0 O 62 321 322 323 32 13 13 0 0 0 63 331 332 333 33 23 713 1 0 0 C4 34 343 343 a44 1 1 71 1 0 i b1 b2 b3 b4 i 18 38 38 18 k1 fundn k2 tn ynL 1gt tn hyn L hkz k4 ftn hiyn hk1 hkz hks yn1 yn gk1 3kg 3k3 k4 k3 Peter Blomgrel Stability Regions Revisited 8 RK MQ39JIOdS 7 3234 Example Kutta39s 4 stage method One Step Peter Blom m Kuua Methods Derivation Next Lecture Residual Issues We have some important residual issues related to Runge Kutta methods to clear up next time 0 Consistency condition The requirement 2 b 1 0 Error estimation using Richardson39s Extrapolation 0 Stability Analysis 9 Some more examples of RK methods in action Future topic 0 Deriving RK methods using rooted trees d 8 RKrMedlods Numerical Solutions to Differential Equations Lecture Notes 4 Stability Regions Revisited amp Runge Kutta Methods Peter Blomgren ltblomgrenpeter gmail comgt Department of Mathematics and Statistics y mlcal Systems Gr up Computational Science Rsearch Center San Diego State University San Diego CA 921827720 httpterminussdsuedu Outline 0 Recap Last Lecture 9 Finding Stability Regions 0 Euler s Method 9 Taylor Series Methods 9 Runge Kutta Methods 0 Introduction 0 sstage RK methods 0 Types of RKmethods 0 Derivation Spring 2009 539 5351 Stability Regions Revisited 84 RKrMethods 7 134 Stability Regions Revisited 84 RKrMethods 7 234 Last Lecture Quick Review Stability Regions Revisited Recall Euler39s Method Euler s Method 0 Analysis Local Truncation Error LTE Consistency Vn1 Yn hftn7n7 YUO YO Accuracy Stability Region of Stability Convergence applied to yt yt Improvements gives 0 Higher order Taylor Series Methods Yn1 Yn l hAYn 1 l hAyn 1 l hAn1O O MultI Pomt Methods 9 Heun39s Method The stability criterion is non exponential growth 0 Euler39s Midpoint Method 1 h S 1 m 5393 Stability Regions Revisited 84 RKrMethods 7 334 Stability Regions Revisited 84 RKrMethods 7 434 Finding the Stability Region Stability Regions for Higher Order Taylor Series Methods How do we find the stability region from the expression Consider 7 k n1 1h 1 7 I k h n1 l l Ytl1 Q My t1 l n l y 07 1 E tl7tl1 The boundary of the region is given by T Now with yt Ayt we have 1he 9 lt2 hAe 9717 6 0727r WU Ayt 2yt 0 So 2 7 WW yt D O And it follows that 7 k 1 7 i M h n1 7 7 yti1 7 Z k YO my 507 5i 6 ltiy ti1l quot i i i i i m k0 5351 Stability Regions Revisited 84 RKrMethods 7 534 Stability Regions Revisited 84 RKrMethods 7 634 Stability Regions for Higher Order Taylor Series Methods Plotting the Boundary of the Stability Region The stability criterion is given by the relation For n 4 we have h 4 h 3 h 2 n k 1 h176100 M 24 6 2 Vti1 7 yto Z k k0 39 matlabgtgt zroots124 16 12 1 1eXpi6l lei Now vary 6 in the interval 07270 collect all the roots and plot in 1 wok lt 1 the complex plane X realz y imagz 7 o H k Again the boundary is given by 27 7 Figure The circle corresponding to Euler39s Method is included for E i 10 7 2 comparison k k0 5331 A 2 Di 2 A 39 5353 Stability Regions Revisited 84 RKrMethods 7 734 Stability Regions Revisited 84 RKrMethods 7 334 Some Comments on Higher Order Taylor Series Methods Regions of Stability for Taylor39s Method n 127 78 In the cases where the derivatives 1 kt7 y can be computed higher order n gt 1 Taylor series method are superior to Euler39s method Taylor order 1 for two reasons 0 The local truncation error is smaller Oh 9 The region of stability is larger allowing for slightly larger step sizes h Next slide shows the stability regions for Taylor39s Method of orders l l l b l 4 7 O Euler s Method 0 Taylor n2 Taylor n3 Taylor nil 2 7 Taylor 115 1 Taylor n6 7 Taylor n7 Taylor 118 1 through 8 O 4 7 O 7 l l l 9 l 539 4 2 0 2 4 m Stability Regions Revisited 84 RKrMethods 7 934 Stability Regions Revisited 84 RKrMethods 7 1034 lmproving Euler39s Method Alternatives Runge Kutta Methods When the derivatives of fty cannot be computed f may be a result of measurements andor is too expensive to computeevaluate we need alternative approaches to improve on Euler39s Method We are going to explore the following approaches 0 Runge Kutta Methods 0 Linear Multistep Methods 0 Predictor Corrector Methods There is significant overlap between these different approaches hence we will re discoverquot some methods in several contexts Stability Regions Revisited 84 RKrMethods wD I 7 1134 Runge Kutta RK methods 0 One step methods moving from time tn to time tn Still easy to build adaptive methods ifwhen necessary step length changes on the fly are easyquot 0 Breakscomplicates linearity the structure of the local error becomes more complicated Catch 22 Easy to change step size since it is a one step method but hard to tell when it is needed local error compli cated 5353 Stability Regions Revisited 84 RKrMethods 7 1234 Linear Multistep Methods Reverse Catch 22 When we look at Linear Multistep Methods which use multiple points y yn1 ykk in order to compute yn1 we will see that they have the reverse problem o for this class of methods it is easy to estimate the local error 5 easy to know when a change in step size is necessary to maintain a certain level of local accuracy 0 but the multistep structure makes it hard to change the step size A General s stage RK method A general s stage RK method for the problem yt to7 1030 yo is defined by 5 ml yn h talk 1 where the kis are multiple estimates of the right hand side ft7y S k f tnch7 yn hZaWkj 7 i 1727 j1 with the following row sum condition 539 j1 m Stability Regions Revisited 84 RKrMethods 7 1334 Stability Regions Revisited 84 RKrMethods 7 1434 Example Heun39s Method is an RK 2 stage Method Example Euler39s Midpoint Method k1 ftn7n 5 Cl 07 81439 0 k1 ft7y gt C1 07 3171 0 k2 fth7hk1 70217821178220 h kh quot quot k2 ftn 7yn17 7c27 a217 a220 k1 2 1 n1 ynh7 7b1b2 yn1 ynhk2 b107b21 The Butcher Array describing Heunxs Method The Butcher Array describing Euler s Midpoint Method 0 O 0 Cl 811 812 0 O 1 1 O 02 821 822 12 12 0 12 12 l 91 92 l 0 1 531 5393 Stability Regions Revisited 84 RKrMethods 7 1534 Stability Regions Revisited 84 RKrMethods 7 1634 The Butcher Array 3 Types of RK methods llll The Butcher array for a general s stage RK method is 01 811 812 C2 821 822 We define the s dimensional vectors E and the 5 gtlt s matrix A 0 Explicit eg Heun39s and Midpoint o If each kj only depends on previously computed k i ltj then the method is explicit and the matrix A is strictly lower triangular Le the elements on and above the diagonal are zero b 19171927 7b51T7 a c17c27 7c51T7 A mu131 539 5351 Stability Regions Revisited 84 RKrMethods 7 1734 Stability Regions Revisited 84 RKrMethods 7 1334 3 Types of RK methods lllll 3 Types of RK methods llllll o Semi implicitquot o If A is lower triangular with non zero entries on the diagonal 9 mpicit then each k is defined b a non linear s stem I y y o If A is a general matrix non zeros above the diagonal then each k is defined by a non linear system kf 1 oh ak i12s I nI7YHjZ IJj 7 77 7 s k f rncihynzaka i 12s We have to solve s non linear but uncoupled systems of 11 1139 I h It 1139 equa Ions m eac l era Ion We have to solve s non linear coupled systems of equations In each iteration This is a daunting computational task which Butcher 1965 calls these methods Semi implicitquot Norsett we will try to avoid 1974 Semi explicitquot and Alexander 1977 Diagonally lmplicit RKquot or DIRK methods 5331 5353 Stability Regions Revisited 84 RKrMethods 7 1934 Stability Regions Revisited 84 RKrMethods 7 2034 A Remark on RK methods One Point of View III A Remark on RK methods One Point of View RK methods constitute a sensible idea The unique solution to a well posed initial value ODE problem yt Hay M730 yo is a single curve in ty space Solutions to the same ODE with slightly different initial conditions form a family of solutions Due to numerical errors truncation and roundoff errors any numerical solution wanders offquot the exact solution curve The numerical solution is affected by neighboring solutions RK methods gather information information about this family of solution curves An explicit RK method sends out feelers into solution space gathering samples of the derivative and then decides in what direction to take the final Euler like step Paraphrased from JD Lambert quotNumerical Solutions for Ordinary Differential Systems the Initial Value Problemquot 539 m Stability Regions Revisited 84 RKrMethods 7 2134 Stability Regions Revisited 84 RKrMethods 7 2234 Deriving Explicit l stage RK methods Deriving Explicit 2 stage RK methods llll The BUtCher array for an 139Stage RK methOd has the form The Butcher array for a 2 stage explicit RK method has the form Cl 3171 o o o o o o 1 C2 8271 O N C2 C2 0 If we want an explicit scheme then an O and since l b1 m l b1 1 7 b1 c1 2111 a175 we have c1 0 Further consistencyquot requires that Z bj 1 so b1 1 We are left with Hence k1 ftn7yn 3 k2 ft 62hy Cghkl Yn1 Yn hlblkl 1 T b1k2l or describes all ossible ex licit 2 sta e RK methods k1 ftn7n P P g yn1 y hkl y hfty7 Euler s Method How do we choose the parameters c2 and b1 39 I We have yet to prove this condition W Taylor EXPan5lon39 Of course39 5353 Stability Regions Revisited 84 RKrMethods 7 2334 Stability Regions Revisited 84 RKrMethods 7 2434 Deriving Explicit 2 stage RK methods lllll With the following Taylor expansions Yn1 Yn l hfn l h zfil l OUls k1 n k2 7tn l 52h7Yn l CZh1 fn 7L 52hftn7yn 7L Cthnlg7ftn7n l 0072 We can define the Local Truncation Error LTEh w 7 blkl 7 1 7 b1k2 h ifquot if 0072 7 new Deriving Explicit 2 stage RK methods llllll We have i h 8 8 8 8 2 LTEh 7 E 512 1542 7 bzczh 512 Eff12 0h Now if g7b262l70 ltgt2b2 21 we get LTEh Oh2 ie our 2 stage RK method is second order The corresponding family of Butcher arrays is O O O 2 2 O 1 7 1262 1262 E 2fquot 31545 7 32527 2fquot 1 31545 1 9072 Sanity check c2 12 gives Euler s Midpoint Method and c2 1 2 191 y 191 y gives Heun 5 Method Stability Regions Revisited amp RKrMethods 7 2534 Stability Regions Revisited amp RKrMethods 7 2634 Deriving Explicit Higher Order RK methods Example 3 stage RK method We can use the same approach Taylor expansion and parameter matching to find higher order explicit RK methods C1 8171 3172 3173 O O O O 02 821 822 823 12 12 0 0 Natural question Is this the best way of deriving the RK C3 as 1 332 as 3 i 1 1 2 0 methods b1 b2 b3 16 23 16 Answer There are more elegant methods for deriving the RK k f methods Most of the work was done by Butcher starting 1 T tm y In the Wild 19605 The methods depend on defining the IQ f tn gyyn Frechet derivative and also requires some ba5ic under standing of graph theory rooted treesquot k3 f tn l hin 7 hkl l 2hk2 h 7 k 4k k Butcher JC 1987 The Numerical Analysis of Ordinary Differential ynll y 6 1 2 3 Equations Runge Kutta and General Linear Methods Wiley Chichester See next slide for Visualization 5393 Stability Regions Revisited 84 RKrMethods 7 2734 Stability Regions Revisited 84 RKrMethods 7 2834 Example 3 stage RK method One Step Example 4 stage RK method Attributed to Runge 01 811 812 813 814 0 O O O O 02 821 822 823 824 12 12 0 O O Cs 831 832 833 834 12 0 12 0 0 C4 841 842 843 844 1 O O 1 O l b1 b2 b3 b4 l16 13 13 16 k1 ftn7n k2 ftn 7ynh7kl k3 f 21 37y Figure Different stages of one step of the 3 stage RK method k4 f tn h7n MG 99 Yn1 Yn k1 2k2 2k3 k4 m Stability Regions Revisited 84 RKrMethods 7 2934 Stability Regions Revisited 84 RKrMethods 7 3034 Example Runge s 4 stage method One Step Example 4 stage RK method Attributed to Kutta 01 811 812 813 814 0 O O O O 02 821 822 823 824 13 13 0 O O Cs 831 832 833 834 23 713 1 O 0 C4 841 842 843 844 1 1 1 1 O l b1 b2 b3 b4 l 18 38 38 18 k1 ftn7n k2 f tn gyyn k3 f 21 imr th1 712 4 ftn h7n hkl hk2 hkg n1 yn gk1 3kg 343 k4 m Stability Regions Revisited 84 RKrMethods 7 3134 Stability Regions Revisited 84 RKrMethods 7 3234 Example Kutta s 4 stage method Stability Regions Revisited 84 RKrMethods One Step v39 7 3334 Next Lecture Residual Issues We have some important residual issues related to Runge Kutta methods to clear up next time 0 Consistency condition The requirement 2 b 1 0 Error estimation using Richardson s Extrapolation 0 Stability Analysis 0 Some more examples of RK methods in action Future topic 0 Deriving RK methods using rooted trees 5351 Stability Regions Revisited 84 RKrMethods 7 3434 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

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

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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