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

## 56

## 0

## Popular in Course

## Popular in Mathematics (M)

This 54 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 56 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

oduclion F5 Shooting for Sys Alternative quotPurelyquot Numenea Shooung Peter Blomgren blomgren peter gmail com Department of Mathematics and Statistics D namicai Systems Group Computationai Sciences Research Center San Diego State University San Diego CA 9218277720 impterminussdsu3du Spring 2009 Peter Blom u39w WadiMi mm 7 Hi VH Outline 0 Introduction 0 Recap 0 Rough Roadmap for This Lecture and Beyond 0 Shooting for Systems of ODEs 0 Convert BVP w NP 0 Taylor Expanding 0 Additional ODEs for the Sensitivity Functions 0 The Final Formulation 9 Alternative Purely Numerical Shooting 0 The Idea 0 Example Euler Bernoulli Beam Deflection Peter Blomgren BVP The Shootng Method continued Quick Recap Boundary Value Problems Last time 0 Physical motivation for boundary value problems bending beams constructing bridges and buildings cooling fins keeping those processors running 0 The shooting method convert a BVP into a sequence of lVPs and apply techniques from the first half of the semester Variational approach add ODEs for the sensitivity variables Finite difference approach approximate the sensitivity by differences of the results of different initial guesses 5351 Peter Blomgren BVP The Shooting Method continued Rough Roadmap for This Lecture and Beyond 39 UDE Nuan ai Shooting AlLei39Iiativ Today39s Lecture 0 Theory 0 Generalize shooting methods to larger systems n simultaneous ODEs 0 Example 0 Shooting for a 4th order ODE Beam Bending 0 Other Approaches a Finite Difference Methods next time BVP The Shoolin Melliolt continued Convert BV lnuodl Ion Shooting for Systems of AlLei39nativo quotPurelyquot Numerical Shooti r Given a system of simultaneous ODEs 4le f1X7YI7YZ77Yn y X f2xiy17y277yn xeab y X fnX7y17y27397Yn with boundary conditions yb yib i 12k Ma y k17k277n In order to convert this to an initial value problem we have to replace the first k terminal conditions with k guessed initial conditions Peter Blomgren BVP The Shooting Method continued Convert BV lnuedl ion Shooting for Systems of Alternative pm 39elyquot Numerical Shooti r k dimensional Initial Guesses We want to find k initial guesses ma Y i12k so that the solution to the initial value problem Mllxl f1X7YI7YZ77Yn Y X f2X7y17y277yn xeab MX fnlxiyhyziwyn with initial conditions ma Y i12k Ma yfi k17k277n Satisfies the terminal conditions yb yIb7 139 127 7 k m BVP The Shooting Method continued Peter Blomgren Introduction Shoo or Systems a Alternative quotrm Nu or o lthootiug k dimensional Discrepancy Functions 0 Let Y Y17 Y2 YkT be the vector of guessed initial values 0 Let yb7 i12k be the terminal values 0 Define h yb iyib 139 127 7 k be the discrepancy functions measuring how far off the computed terminal solutions are from the desired values of the terminal conditions 0 We are now looking for a correction A to the guesses so that the corrected initial conditions lead to a solution with hY AY O 0 We use our favorite mathematical tool the Taylor Expansion to get an equation for the correction 5351 Peter Blomgren BVP The Shootng Method continued Sho Alternative quotPure Taylor Expanding and Truncating We Taylor expand and throw out terms of order 2 2 just as in the Taylor derivation of Newton39s Method Math 541 k ah 0hYAYhYj 1anAlG 112k We end up with the following k X k system of equations 671 671 671 7 671 AY1 672 AYz W An 7 471m 672 672 am 7 671 AY1 672 AYz W An 7 ihzm Bhk Bhk ahk 7 quot laTlA l l quot39l l k hk sosa BVP The Shooting Method continued Peter Blomgren SI Alternative A Little Bit of Matrix Notation 0 Let A AY17AY27 7AYkT be the vector of updates 9 Let Ho h1h2hkT be the vector of discrepancy functions 0 Let the matrix J7 b be the matrix the Jacobian with entries X H w Peter Blomgren BVP The Shootng Method continued mu ul Shooting for Systems or Alternative quotPurelyquot Numerical Shooti V the The entries of the Jacobian are the partial derivatives of the discrepancy functions with respect to the guessed initial values computed at the terminal point As in the oneconstraint problem we looked at last time we have to derive additional ODEs to get equations for the needed values We differentiate the ODEs we already have with respect to the guessed initial values apply the chain rule and the fact that we can switch the order of differentiation we get 1e18yi 8 8V dx 7 8V 7 8yk8Yj k1 wherei12nandj12k Peter Blomgren i In ion oolin for Systems of ODE Pu Nun 39 1i Shooting 39me Sensmmy Funcllons Equations for the Sensitivity Functions We define the sensitivity functions 78h g39J YJ 73 and get the following set of n x k ODEs amp dx Method con 39med I n s oolin forSyslems oiona V AlLei39Iiativ Pu Nunm ai Shooting 5quotquot f quotfquotpna Mme 5 quot39quot quot y Fquotquot quot Equations for the Sensitivity Functions The initial conditions for the sensitivity functions are 1 ifi39 gUO W74 112n 112k This makes sense since at X a there is no mixing of the guessed values oyaEYil2kand 0yayiaik1k2n BVP The Shoolin Melholt continued Sl Alternative 39 The Final Formulation Putting the Pieces Together Now we solve the following lVP consisting of n l n x k simultaneous ODEs YX X7y17y277yn y X 6X7y17y27m7yn MX fnlx7y17y277yn g6 21 gkj 12n j12k with initial conditions Yiayi 17277k yayi ik17k2n 7 1 ifij 7 7 gui O ifiy j 171727 n7 171727k Peter Blomgren BVP The Shootng Method continued lnuedl ion Shootng for Systems of Alternative quotPurelyquot Numerical Shooti 7 ii The Final Formulation Putting the Pieces Together At the terminal point X b we compute the discrepancy functions hY and the entries of the Jacobian JU galb If gt tolerance or other stopping criteria then we update the guess 71 ys1 ys JY57 7 hys and start over Peter Blomgren BVP The Shooting Method continued lnuedl ion Shootng for Systems of Alternative quotPurelyquot Numerical Shooti 7 ll The Final Formulation Comments 0 We started with n ODEs 0 The equations for the sensitivity functions added n x k ODEs 0 That can be a high price to pay If n 1000 and k 500 a very reasonably sized problem then the extended system has 501000 equations 0 The good news The ODEs and initial conditions for the additional equations are very easy to write down Yk 7 8f 7 7 k got gkjai 112n 112 k1 Peter Blomgren BVP The Shootng Method continued Alternative The Numerical Alternative O lfWhen the price is too high we can compute numerical difference approximations of the terminal values of the sensitivity functions 0 Let e61j62j 765 ie the vector of all zeros except the value 6 in thejth position 0 If we solve the initial value problem for the two initial guesses Y and V l we can compute the difference approximations ahi z 7 I12k Xb E Letj 17 27 7 k gives us approximations to all entries of the Jacobian o The price Solving the system of n ODEs k l 1 times 5351 BVP The Shooting Method continued Peter Blomgren Anemalive ple EulerrBemoulli Beam Deflection Example Shooting for the Euler Bernoulli Beam Equation Transverse deflection of a beam WX subject to distributed load W 2 2 d d WX 7 ECOX 7 P00 Here we will assume a uniform beam ie EX and IX are constant For simplicity EXIX 1 We39ll let the beam have length L 1 and be fixed at the end points like a book shelf We use a non uniform load function PL2 px 9 Us Peter Blomgren BVP The Shootng Method continued 39 Example EulerrBemoulli Beam Deflection al Shooll 7 Shooting for Beam Bending Equations Our problem is 4 7 2 d WX LL862 W 9 Subject to WO WO W1 Wl 0 We introduce y 1 1727374 and get the following system of ODEs Y1 yz Y1 0 d M l y3 j PL2 Y4 dx BVP The Shooting Method continued Peter Blomgren 39 Example EulerrBemoulli Beam Deflection al Shooll r Shooting for Beam Bending lVP We are going to solve the following lVP Y1 y Y10 0 i YZ 7 m YQ0 0 y4 7 dx ya PM mm A Y4 9 Us y40 B and numerically determine the parameters A and B so that the terminal conditions y11 O and y21 0 Peter Blomgren BVP The Shooting Method continued D Altman Purelyquot Example EulerrBemoulll Beam Deilecuon Code RKF45 Shooting for Beam Bending 397 Example Shooting for a uniform fixed Beam 397 397 Ex Constant 1X Constant 7 Octave Code wwwoctaveorg c ear a 1 397 Length of the Beam glob 397 Shooting with RKFi45 397 The Load Function function F px a1 exp xi2 xi2 L8 L8 endfunct ion 397 The Forcing Function of the System of UDEs function rhslkf45 rhslkf45xw rhslkf45 w24 px endfunction BVP The Shoolin Melholt continued funcnon yxv RKF45yOxOL c 014 38 1213 1 12 0140 0 00 0 332 932 00 0 0 11 19322197 772002197 72962197 0 0 0 A 7 11 439216 78 3680513 845 1 4 1 827 2 36442566 18594104 71140 0 25216 0 14082565 2197 4104 71 5 0 52 16135 0 665612825 2856156430 7950 255 E 1360 0 71284275 7219775240 150 255 L 1e 12 770 yMyo xvx0 xx0 5 7 k6 rhukf45lt xhc6 yMhA6k The Shooll continued Altman Purelyquot Example EulerrBemoulll Beam De ection Code RKF45 Shooting for Beam Bending yNext y hb1k yErr hEk yErrAbs normyErr if yErrAbs lt TUL y y yNext y yNext xv xv xh X Xh if yErrAbsQO lt TUL h 112 Zprintf 1ncreasing the step size to hfn h end else 7 h2 Zprintf Reducing the step size to hfn h end endfunction BVP The Shoolin Melholt continued Allemaliv Purelyquot Code RKF45 Shooting for Beam Bending 7 Initial initial Values wO 0 0 0 0 tol 1ei8 Perturb 10tol Err 2 tol while Err gt tol yxv RKF45w00L d Y y lengthxv norm WLdiscr W2discr 397 Skip out of the loop when tolerance is met if Err lt tol break end wO wA03 wA03 Perturb yxv RKF45wA00L Yperturbw3 Yw3jinal Y y lengthxv BVP The Shoolin Melho continued Allemaliv Purelyquot Code RKF45 Shooting for Beam Bending WBO wO WBO4 WBO4 Perturb yxV RKF45WB00L Y2perturb2w4 y Y7w4 final y 1engthxv J11 Y2w32fina11Ympfina11 Perturb J12 Y2w42fina11Ympfina11 Perturb J21 Y2w32fina12Ympfina12 Perturb J22 Y2w42fina12Ympfina12 Perturb Ja J11 J12 J21 J22 w034 w034 Ja W1discr W22discr end BVP The Shoolin Melholt continued Allemaliv Purelyquot Beam Bending Numerical Results 0029003 17206e 11 n8 n5 n4 n2 n2 n4 n5 I8 FIGURE 1 The distributed load BVP The Shoolin Melholt continued 3 lb Sys 39 V EulerrBemoulli Beam Deflection Alternative yquot Numerlca Beam Bending Numerical Results The Displacement l l l l l 0 0005 i i 0 001 i i 0 0015 i i a i l i l i l i l i 0 2 0 4 0 6 0 8 FIGURE 2 The displacement due to the load WX yl m Peter Blom BVP The Shoolil onlinued In red hon Example EulerrBernoulli Bean Deflection S for S U Alternative Purer Numerical Shooti Beam Bending Numerical Results W 0 004 i V V V V 0 002 0 002 0 004 i i i i i i i i Peter Bloln continued In red hon Example EulerrBernoulli Bean Deflection S for S U Alternative Purer Numerical Shooti Beam Bending Numerical Results C rvature W 0 03 i i i i i i i i Peter Bloln continued In red hon Example EulerrBernoulli Bean Deflection S for S U Alternative Purer Numerical Shooti Beam Bending Numerical Results W Peter Bloln continued Numerical Solutions to Differential Equations Lecture Notes 20 Nonlinear Equations Peter Blomgren ltblomgrenpeter gmail comgt Department of Mathematics and Statistics Dynamical Systems roup Computational Science Rsearch Center San Diego State University San Diego CA 921827720 httpterminussdsuedu Outline 0 Nonlinear Boundary Value Problems 0 An Alternative Model For Beam Bending 0 Model Problem General 2nd Order Nonlinear BVP Does Well Behaved Solutions Exist O Finite Time Blowup 0 Existence and Uniqueness a ODE w Nonlinear Algebraic System 0 Finite Differencing 0 Nonlinear System and Uniqueness Condition 0 The Return of Newton s Method 0 Example Spring 2009 0 Code m 0 Numerical Results m Nonlinear Equations 7 119 Nonlinear Equations 7 219 Nonlinear Boundary Value Problems Nonlinear BVPs ll So far we have exclusively looked at Linear BVPs We will now consider some non near Problems 0 Quite a few of the linear models we use are Simplifications of more accurate nonlinear models Burden Faires p672 suggests that 0 Usually the linear model is valid in a limited regime eg small 1 S X 39 39 WX iWX Cl X 7 L Wm WL O deflection of the beam whereas the non linear models have 31 wX El 2E larger regimes of validity 395 a more aPPrOPrlaFe equatlorl for the defleCtlon Of a SUPported 0 Since closed form solutions for non linear equations are hard beam subject to uniform loading to find finding numerical solutions seem like a good Idea Note that the original forth order beam equation has been integrated twice to give a second order equation 5331 5393 Nonlinear Equations 7 319 Nonlinear Equations 7 419 General Second Order Non linear BVP Controlling the Solution 5 Need For Analysis 0 We are going to look at the general second order nonlinear BVP yXfX7yX7yX7 XelavblV yaya ybyb 0 We are going to apply our trusted finite difference methods to this problem 0 In this setting we get a non linear system of algebraic equations 0 In order to solve this system we need an iterative process 5393 Nonlinear Equations 7 519 Even a very benign looking non linear ODE can produce solutions which blow upquot reach infinite values Consider the initial value problem yt tzy y0 yo gt 0 which has the solution 1 yt i 7 t Yo and lim yt 00 177 Y0 We need some restrictions in order to guarantee the existence of a unique solution m Nonlinear Equations 7 619 Existence and Uniqueness of the Solution Constructing the Nonlinear Algebraic System We are studying yXfX7yX7yX7 XelavblV yaya ybyb If we assume 1 f and the partial derivatives fy and fy are continuous on DX7y7agxgbyiooltyltooyiooltyltoo 2 l nyyy 2 6 gt O on D 3 Constants k and L exist with the properties f d L f nya3ltEDlyX7y7yl an max lynyry XvWED Then the existence of a unique solution is guaranteed m Nonlinear Equations 7 719 We subdivide the interval a7 b into N 7 1 subintervals bia Xn7an 1h7 n717277N h7N71 We apply second order centered differences and get Vn1 2Vn 7L Vn71 i Vn1 Vn71 72 I72 4 f i f ananT 3y Tin y 5n Where 77175 6 Xn717Xn1 The error terms make the assumption that yX E C4a7 b The finite difference method is the result of dropping the error terms and adding the boundary conditions Y1ar YNb 5353 Nonlinear Equations 7 319 The System Solving the System We vaguely remember talking about using Newton39s method for systems in the context of Implicit Linear Multistep Methods for yl Ya ys 7 2n 7 yl hgf Xzyyzy y327hy1 Stiff ODEs lecture 12 M 7 213 y2 hzf X37y37y4271y2 Define y y17y27 7yNT and write the vector equation 2 HWYV72 M T ya YN QYN71YN72 h fXN71rN71r 2 y372y2y1 h2fX2727y327y1 YN yb 7 y4i2y3y2 h2fX37y37y427y2 F0 5 0 This system has a unique solution provided h lt 2L yN 7 2yN71 7 yN72 7 hgf XN717yN717 may1N4 Keller HB Numerical Methods for Two Point Boundary Value YN Yb Probems Blaisdell Waltham MA 1968 m 5331 Nonlinear Equations 7 919 Nonlinear Equations 7 1019 Applying Newton s Method Newton s Method A General Row of the Jacobian Newton39s method applied to F07 0 is For n 2737 7 N 7 1 we have the non linear equation 1 7 71 7 1 yquot 7 yquot a My Fm my y 7 2y 17 W M where J07 is the Jacobian of F07 Hence a 359 Jquot 77 1717277N s h y1iye1 Uy J Jnn71y 1 573 Xman The first and last row of F are ver sim le 7 1 y P Jnny 2 T hzfyn Xman yl Ya F gtJ J 1 h y1iy71 Mm l YN Yb l 1 1 N N Jnn1Y 1 Efyi mem n 2h n gt The remaining entries on the rst and last Nth rows are zero39 Since J is tridiagonal the Newton iteration is not that expensive m N onllnear Equations 7 1119 Nonlinear Equations 7 1219 Exa m ple y e siny 0 l Nonlinear BVP 394 Example 1 39A A y expxy siny 0 0 Z y1 y2 X6 172 10 32 0 Example N f inline expxysinyp x y yp fy inline x exp xy x y yp gt feyp 1n11ne cosyp x y y39p ERR TOL2 while ERR gt TUL yp 0 y3Ny1N 22h 0 a 1 ya 0 ypp 0 y1N 2 2y2N1 y3N o b 2 yb0 F ypp hh fltxyypgti F1 Or TUL 000000001 For o N 64 J zerosNN h b aN1 J11 1 x ahb JNN 1 y yayb yab ax a y1 ya yN yb 539 5331 Nonlinear Equations 7 1319 Nonlinear Equations 7 1419 Example I Results l l l l i i l l l l l l l l for n 2N 1 Jnn 1 1 h2 fey39p xn yn ypn I15 I157 Jnn 2 hh fey xn yn y39pn Jnn1 1 h2 fey39p xn yn ypn end l1 l1 deltaY JF plotxF b xy r ERR normdeltaY y y deltaY 395 395 7 end i l l l l l l l 12 14 16 18 12 14 16 18 nl 5393 Nonlinear Equations 7 1519 Nonlinear Equations 71619 Results iteraan 1mm 2e77 7 iterauun 4 Error 22715 Next Time A Different Point of View A different approach to Boundary Value Problems The Rayleigh Ritz Method the Finite Element Method The Boundary Value Problem is reformulated as a problem of choosing from the set of all sufficiently differentiable functions satisfying the boundary conditions the function which minimizes a certain integral m m Nonlinear Equations 7 1719 Nonlinear Equations 7 1319 Project Presentation Schedule w I Nonlinear Equations 7 1919 Numerical Solutions to Differential Equations Lecture Notes 11 Runge Kutta Methods for Stiff ODEs Peter Blomgren ltblomgrenpeter gmail comgt Department of Mathematics and Statistics y mlcal Systems Group Computational Science Rsearch Center San Diego State University San Diego CA 921827720 httpterminussdsuedu Outline 0 Introduction 0 Review Stability for Explicit Runge Kutta Methods 0 Stability of Semi Implicit RK Methods a Approximations of ex 0 Optimal Polynomial Approximations 0 Optimal Rational Pade Approximations 0 Rational Approximations Classification and Properties Implicit RK Methods for Stiff Problems 0 Examples Gauss Legendre Methods 0 Wishing for L stability The Radau Methods Spring 2009 m m RungeKutta Methods for Stiff ODE 7 131 RungeyKutta Methods for Stiff ODE 7 231 Recall Stability Analysis for Explicit RK methods Recall Stability of Heun39s Method lll By applying the RK methods to the scalar test problem yt yt7 yt0 yo we will find the regions of stability for The lteratlon 395 glven by the methods ynH RUM Eg Heun s Method 0 O O and the stability region is given by R hA 1 hA 7 lt 1 1212 lll2 Hence 1 tmyn Ayn We find the boundary of the region by find the complex roots of k2 ftn l h7n l hkl Yn l hkl AYn l hAZYn 2 h My 17el6hA 0 yn1yn1 2h2yn1hT 2 ROM for all values of 6 E 07270 RungeKutta Methods for Stiff ODE 7 331 RungeyKutta Methods for Stiff ODE 7 431 Recall Stability of Heun s Method We find the boundary of the region by find the complex roots of 2 17e 9h0 V O27r i i i i i i 4 7 Eula Method Heun s Method 2 l i l i l i l i l 74 72 o 2 4 RungeKutta Methods for Stiff ODEs Recall Stability Regions for General RK methods We have yn1 4 hbTE y 35TH 7 hA 11y Thus the stability function is Stability Function RG 1 36TH i FArli As usual the method is stable for f such that S 1 For explicit methods A strictly lower triangular the quantity 539 531 Recall Stability Regions for General RK methods lll For notational convenience we absorb hA 7 Using the A from the Butcher array we can write the k s k1 1 s k2 s A s s k ynl hAk7 where 1 kS 1 Further Yn1 YnFBTEYnf7ETI f7Ailin m RungerKutta Methods for Stiff ODEs 7 631 The Stability Function As we have seen the stability functions for explicit RK methods are polynomials Lets consider the stability analysis for a semi implicit method defined by the following Butcher array We get k1 tn C1h7n hham yn Fanlt1 k2 tn C2h7n h1821 h2822 yn h821 k1 822k2 s i A it A A d 7 I 7 hA 1 1 1 7 ham 7 ha271 k1 7 AVny k2 F 5 is easily computable using forward substitution m 1 7 3171 1 7 3171 7 3272 535 RungeKutta Methods for Stiff ODEs 7 731 Runge7Kutta Methods for Stiff ODEs 7 331 The Stability Function Rh 7 Semi Implicit RK With these values of k1 kg 1 7 F 7 3 k1 Ayn k2 A 1 ham 1 7 MW 7 922 the final step becomes yn 1 hb1k1 hbzkzl Yn1 7 y 1 3 7 21 171 1 7 ham 1 7 781711 7 78272 Ra Clearly is a rational function RungeKutta Methods for Stiff ODEs Summarizing The exact solution to the test equation is yt KeM7 K constant initial conditions hence the exact solution to the iteration is y31 eAhyn e yn We can express the truncation error as LTEG e3 7 RF y 0 HP for a pth order method RungeKutta Methods for Stiff ODEs ms 7 931 5351 7 1131 Summarizing lll We have seen that when we apply an RK method to the test equation yt iyt we get the discrete iteration y1 Rhy F hA A e c where o for explicit RK methods is a polynomial and o for semi and fully implicit RK methods it is a rational function 53539 RungeyKutta Methods for sun ODEs 7 1031 Polynomial Approximations to the Exponential Clearly the truncation error waitieiRltiiiynoltii1gt I only depends on how well approximates the expo nential eh Hence if we know how to find a good approximation to the exponential we can back track and build a high order scheme hopefully with good stability properties The optimal polynomial approximations come directly from the Taylor expansion of eh 1 quotk Eh 0 5353 7 1231 02 ll M8 x l l RungeyKutta Methods for Stiff ODEs Rational Approximations to the Exponential lll Rational Approximations to the Exponential llll we are now mtli7 atthll to look at Rational ApprOleatlons to The maximum order of approximation of the exponential for a the Exponent39al 39 rational function Rig h is T S Value Add Stron Connection to Stabilit A A A 7 g 77 eh7RhOhP17 pgTs The value add is that we are working directly With the stability g A A function Once we find high order apprOXImationsto e with if p 5 T then R75h is called a pad Approximation of eh de5irable stability properties we go back and identify coef CIents to I build the corresponding finitedifference scheme Butcher 1987 figured out what the coef CIents for the Pade r approximations are Let S 5Tii 12 5 a 7 I A 5 A T N 7 5 T i57i 7 7 7 7 Rim Zam39 ijh a0b017a5 07br 0 I 0 F0 b71j T 5 T71 j1 2 T A 1 Sn jTej 7 denote a rational approximation of eh m m RungeKutta Methods for Stiff ODE 7 1331 RungeyKutta Methods for Stiff ODE 7 1431 Examples Some Pad Approximations Order 3 The Associated Stability Regions 1 437 i i i i i i 0 A 7 2 7 R307 7 1 73 2 7 3 A 1 1 R21h 2 3 1A2 77 7 7 g 6 i i i i i i i 1 A 32 Rgh interior interior 1 i h A A 1 1 7 7 R3h 1h732733 2 6 n n As usual the boundaries of the stability regions are given by 2 2 REG e707 9 E 072 L i n 2 L i i i 2 m R21 exterior Rgh exterior m RungeKutta Methods for Stiff ODE 7 1531 RungeyKutta Methods for Stiff ODE 7 1631 Definition Acceptability of Approximation Theorems Acceptability of Pad Approximations Definition Ehle 1969 A rational approximation to e3 is said to be 0 A acceptable if lt 1 whenever Reh lt O 9 Ao acceptable if lt 1 whenever h is real and negative 0 L aticeptable if it is A acceptable and a O as Reh a foo Clearly the associated numerical methods are A stable Ao stable and L stable Theorem Varga 1961 If T 2 S then is Ao acceptabe Theorem Birkhoff and Varga 1965 If T S then is A acceptabe Theorem Ehle 1969 If T S 1 or T S 2 then is L acceptabe Theorem Wanner Hairer N rsett 1978 is A acceptabe if and only if T 7 2 S S S T quotThe Ehe Conjecturequot 1965 m E RungeKutta Methods for Stiff ODE 7 1731 RungeyKutta Methods for Stiff ODE 7 1331 Theorems Visualized Theorems Note 0 A 0 A Note Even though lImReaMRHiOO le a O R3h IS not L acceptable since it is not A acceptable The left half plane of the region of absolute stability has two small cut outsquot It is Aa acceptable where a m g 7 0031 5353 RungeKutta Methods for Stiff ODE 7 1931 RungeyKutta Methods for Stiff ODE 7 2031 Implicit RK methods Suitable for Stiff Systems Finding the RK method from Given the preceding detour into approximation of the ex ponential we are now ready to take another look at RK methods Given an RK method with its associated Butcher array E A ET we recall that we can express the stability function as RG 1 FBT 73A 1i or R6 7 detl 73A 7 EU 7 detl 7 FA RungeKutta Methods for Stiff ODEs m 7 2131 0 Whereas it is possible in some cases but extremely tedious in all cases to take a rational function Rh and quotreverse engineerquot a numerical method this is not the path we will take 0 We are going to look at the fully implicit Gauss or Gauss Legendre Methods 0 By optimally selecting the points where f is evaluated the entries in the matrix A which occurs in the Butcher array an s stage Gauss method achieves order 25 Note The optimal placement of the points comes out of an analysis very similar to the one for Gaussian numerical integrationM hm m RungeyKutta Methods for Stiff ODEs 7 2231 Gauss Legendre Methods Gauss Legendre Methods lllll Since there is a unique rational approximation to order 25 of eh namely the Pad approximation it follows that the stability function for the Gauss methods must be the Pad approximation Since 5 T all Gauss methods are A stable Birkhoff Varga Example Implicit Mid point Rulequot The Implicit Mid point Rulequot is a l stage 2nd order Gauss method 1 5 i MlH 1 1 Yn1 Yn l hf tn l 57750 Yn1 RungeKutta Methods for Stiff ODEs SR 7 2331 Example 2 stage 4th order Gauss method v 5353 RungeyKutta Methods for Stiff ODEs 7 2431 Gauss Legendre Methods Gauss Legendre Methods The Final Wish Example 3 stage 6th order Gauss method aim aim Ponder how much fun would it be to reverse engineer this 3 6 method from the Pad approximation R336 0 If want to find something quotwrongquot with the Gauss methods it would be that they are not L stable It turns out we can trade one order of approximation for L stability The Radau l A and Radau ll A s stage methods are order 25 7 1 and L stable The Radau l A methods are derived just like the Gaussian methods but require the left endpoint to be part of the interval c1 O The Radau ll A methods require the right endpoint to be part of the interval c1 1 m RungeyKuua Methods for Stiff ODE 7 2631 Radau ll l A Methods Radau lll A Methods Examples llll Example l stage lst order Radau ll A L stable method Example 3 stage 5th order Radau l A L stable method am am NH O 1 717 4M6 9 18 18 67 1 887 88436 10 9 360 360 6 1 8843 884 10 9 360 360 5353 RungeyKulla Methods for Stiff ODE 7 2831 RK methods Wrap up lll RK methods Wrap up llll 0 Clearly constructing A or L stable implicit RK methods is not an insurmountable task 0 Further implementing the methods is also quite straight forward 0 Either with the help of Richardson Extrapolation or by RKF45 like methods we can get good error estimates and thus construct adaptive algorithms that change the step size h on the fly 0 These methods will work and can be designed to be very robust 0 However in terms of efficiency they fall short of fine tuned BDF LMM methods 0 To make RK methods competitive the computational handling of the implicitness must be cut down There are a number of quottricksquot transformations that can be applied to reduce the computational burden 539 m RungeKuua Methods for Stiff ODE 7 2931 Rungerkuua Methods for Stiff ODE 7 3031 Next couple of lectures 0 Linear Multistep Methods for Stiff ODEs 0 Review and examples 0 Hybrid Methods 0 Tie up loose ends 0 Start thinking about projects m RungeKulla Methods for Stiff ODE 7 3131 Numerical Solutions to Differential Equations Lecture Notes 2 Calculus and Math 541 Review Peter Blomgren ltblomgrenpeter gmail comgt Department of Mathematics and Statistics Dynamical Systems Group Computational Science Rsearch Center San Diego State University San Diego CA 921827720 httpterminussdsuedu Outline o Calculus Review 0 Limits Continuity and Convergence 0 Differentiability Rolle s and the Mean Value Theorem 0 Extreme Value Intermediate Value and Taylor s Theorem 9 Math 541 Review 0 Interpolation Differentiation Extrapolation 0 Integration Degree of Accurac 0 NewtonCotes Formulas Composite Integration Spring 2009 ms 53539 Calculus and Math 541 Review 7 146 Calculus and Math 541 Review 7 246 Current Lecture Reviewing Math 541 and Calculus Background Material A Crash Course in Calculus Key concepts from Calculus 9 Limits The purpose of this lecture ls to warm up by reVIewmg some Continuity forgotten material from the past 9 Convergence Note that complete lecture notes for Math 541 which is being 0 Differentiability offered concurrently Will be available on Ilne at Rollels Theorem http termlnus sdsu eduSDSU Math5412009 9 Mean Value Theorem 9 Extreme Value Theorem 9 Intermediate Value Theorem 9 Taylor s Theorem m 5353 Calculus and Math 541 Review 7 346 Calculus and Math 541 Review 7 446 Limit Continuity Definition Limit A function f defined on a set X of real numbers X C R has the limit L at X0 written lim fX L XgtX0 if given any real number 5 gt 0 V5 gt 0 there exists a real number 6 gt O 36 gt 0 such that lfX 7 Ll lt 5 whenever X E X and Olt lX7X0l lt6 Definition Continuity at a point Let f be a function defined on a set X of real numbers and X0 6 X Then f is continuous at X0 if Xllnx0 fX fX0 Example Continuity at X0 Here we see how the limit X a X0 where X0 05 exists for the 1 393 functlon fX X 5 sm27rX Calculus and Math 541 Review 7 546 Calculus and Math 541 Review 7 646 Examples Jump Discontinuity Examples quotSpikequot Discontinuity le l8i 15 7 l6 7 17 T Mr 7 use 7 Elli l l l l l l l l l2 l4 l6 l8 l2 l4 l6 l8 The function The limit exists but The functlon 1 X 05 L X X5In27rX XltO5 X 0 Xi Xlgg xkoil T xsin27rXl XgtO5 39 has a jump discontinuity at X0 0395 nu has a dlscontlnulty at X0 05 535 Calculus and Math 541 Review 7 746 Calculus and Math 541 Review 7 346 Continuity Convergence Illustration Convergence of a Complex Sequence Definition Continuity in an interval The function f is continuous on the set X f E CX if it is continuous at each point X in X Definition Convergence of a sequence Let x Xn f11 be an infinite sequence of real or complex numbers The sequence x converges to X has the limit X if V5 gt O 3Ne E Z an 7 Xl lt e Vn gt Ne The notation lim Xn X H00 means that the sequence Xn1 converges to X z o 3 o 4 o o N z o kgtN o o N l 0 O o o A sequence in g 2521 converges to 20 E C the black dot if for any 5 the radius of the circle there is a value N which depends on a so that the tail of the sequence A zk ilv is as inside the circle Calculus and Math 541 Review 7 946 Calculus and Math 541 Review 7 1046 Differentiability lllustration Differentiability Theorem If f is a function defined on a set X of real numbers and X0 6 X the the following statements are equivalent 8 t a f is continuous at X0 1 Ifxn 1 is any sequence in X converging to X0 then limn oo fXquot fXo M Definition Differentiability at a point 394 7 Let f be a function defined on an open interval containing X0 2 lt X0 lt b 1 is M differentiable at X0 if T T f 7 f l l l l fXO m X X0 exists n2 n4 n6 I8 Xm xo X 7 X0 If the limit exists fXo is the derivative at X0 Here we see that the llmlt m fX 7 fX0 Definition Differentiability in an interval X7gtXo X 7 X0 If f X exists V E X then f is differentiable on X l 0 X0 R eXIsts and approaches the slope derlvatlve at X0 fXo 535 Calculus and Math 541 Review 7 1146 Calculus and Math 541 Review 7 1246 Continuity Rolle s Theorem Mean Value Theorem Theorem Differentiability 5 Continuity Theorem Mean Value Theorem Wlklerk ff 6 Ca7 b and f is differentiable on a7 b then 3c 6 a7 b If f is differentiable at X0 then f is continuous at X0 Theorem Rolle39s Theorem WIkIerk fc w 7 a Suppose f E Ca7 b and that f is differentiable on a7 b If fa fb then 3c 6 a7 b fc O m m Calculus and Math 541 Review 7 1346 Calculus and Math 541 Review 7 1446 Extreme Value Theorem Intermediate Value Theorem Theorem Extreme Value Theorem WIkIerk ff 6 Ca7 b then ElCl7C2 E ayb fc1 S fX S fc2 VX 6 a7 b Iff is differentiable on a7 b then the numbers c17 c2 occur either at the endpoints of a7 b or Where fX O Theorem Intermediate Value Theorem WIkIerk iff E Ca7 b and K is any number between fa and fb then there exists a number c in a7 b for Which fc K l l ll m 5353 Calculus and Math 541 Review 7 1546 Calculus and Math 541 Review 7 1646 Taylor39s Theorem Theorem Taylor s Theorem WIkIerk Suppose f E Cquota7 b f 13 on a7 b and X0 6 a7 b Then VX 6 37 b 35X E X07X with fX PnX RnX where n k X PM Z quotTWHOK Rm fn n 411513 X Xoquot1 PX is called the Taylor polynomial of degree n and Rnx is the remainder term truncation error fX sinX Illustration Taylor s Theorem M 1 1 P5 X 1 1 1 1 1 1 P X X7 7X3 7X5 77x7 7X9 77X 7X13 l 3 5 7 9 11 13 This theorem is extremely Important for numerical anay5ls P X Taylor expansion is a fundamental step in the derivation of many 5V z of the algorithms we see in this class and in Math 6933b m P900 m Calculus and Math 541 Review 7 1746 Calculus and Math 541 Review 7 1846 Background Material Math 541 Review Key concepts from Math 541 Key topics P 39 t t39 d A 39 t39 Oynomla erp a Ion an PPrOlea Ion Lagrange Coef CIents Lagrange Polynomials 7 ApprOXImatlon of Derivatives Newton39s Divided Differences An expression for the polynomial Numerlcal Inlegrallon Using polynomials to approximate fX 7 ApprOXImatlon of Richardson s Extrapolation ti 1 fad77 39 t 39 7yn dt Numerical Integration Return of the Lagrange Polynomials ti 5331 5393 Calculus and Math 541 Review 7 2046 Calculus and Math 541 Review 7 1946 Interpolation Lagrange Polynomials Instead of working hard at one point Taylor polynomials we are going to construct a polynomial passing through the points X07fXo X17fX1 X27fX2 Xn7fXn We define Definition the Lagrange coefficients Ln7kX n X i X39 LnkX H I 7 0 k Xk 7 X Ln7kX have the properties Ln739Xj 6M and we use them as building blocks for the Lagrange interpolating polynomial Pnx 2 WWW kio The Lagrange Coefficients Ln7kX Eg L67kX39 691 Xi0 i 539 1 2 3 4 5 6 m Calculus and Math 541 Review 7 2146 Calculus and Math 541 Review 7 2246 Newton39s Divided Differences Newton s Divided Differences Compute the Polynomial Zeroth Divided Difference We can write the interpolating polynomial with the help of the leil fXi divided differences First Divided Difference n k1 I I PX XO 2 X0 Xk HX e xm leI1l leIl 7 fXX391 i k1 m70 Xi1 Xi Second Divided Difference where fX0 Xk are the diagonal entries from the divided dlfference table f Xi1 Xi2l lei Xi1l f 7 7 lelelll XI2 Xj2 7 Xquot X0 le0 X1 f lxll le07X1 fX1X2 7 fX0X1 kth DlVlded leference X2 1le fX17X2 fX07X17X2 W lei7Xi177XiKl leilllXIHl 39 i 39 lXilrkiiflI7Xi17 39 i 39 7Xik71l 39 I 39 39 5353 Calculus and Math 541 Review 7 2346 Calculus and Math 541 Review 7 2446 Numerical Differentiation Using Polynomials Suppose X0X1 f E C 1I we can write quot Hquot X Xk f 2 f L H WU X k0 Xk kX n1 5 Formal differentiation gives X n X X i HZ0X Xlt n1 m gumwdxl n1 if s Since we will be evaluating fXj the last term gives no contribution Calculus and Math 541 Review Example 3 point Formulas llll Building blocks X X1X X2 2X 7X1 7 x2 X are distinct points in an interval I and m 7 2546 The n 1 point formula for approximating fXj WW5 f 39 n f L 39 xJ g xk ka n1 HXjXk k0 k7 The formula is most useful when the node points are equally spaced ie Xk X0 kh m Calculus and Math 541 Review 7 2646 Example 3 point Formulas lllll we 7 g 73 W1 7 M 3 L L 2000 X0 X1Xo X27 Z le X0 X1Xo X2 1 h2 X 7 X0X 7 X2 2X 7 x0 7 x2 fXI l flxol flxzl gfml l L21X Xi 77 L21X f 1 XoX1 X2 X1 XoX1 X2 1 hz 3 L 7 X 7 X0X 7 X1 L 7 2X 7 X0 7 X1 1rX2 lflxol 4fX1 3flx2ll 3 4 52 272X 7 X2 X0X2 X17 2 2X 7 X2 X0X2 X1 Use Xk X0 khi Formulas 1 hz 7 7 7 7 f x773f 4fqh7fx 2h7f3g fXj W0 W1 0 2h 0 3 0 X0 7 X1Xo 7 X2 X1 7 XoX1 7 X2 1 hz 3 2X 7 X0 7X1 143 2 1rX0 h 400 flxo 27 gf 51 fX2 09 XOXXZ 7X0 6 J H gt9 7 Xk 1 hz ii f x0 2h fx0 7 4fx0 h 3fx0 2h 324 Calculus and Math 541 Review 7 2746 Calculus and Math 541 Review 7 2346 Example 3 point Formulas llllll Richardson39s Extrapolation fXO 73fxo 7 4fx0 7 h 7 fX0 7 2h 7 gf kgo fXo 4xo e h We h e quotg mu 1 h2 fXO fX0 7 2h 7 4fx0 7 h 7 3fx0 7 243 After the substitution X0 h a X0 in the second equation and X0 2h a X0 in the third equation Note1 The third equation can be obtained from the first one by setting h gt 7h Note2 The error is smallest in the second equation Note3 The second equation is a two sided approximation the first What it is A 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 NJh Z Ekhl kj where M is the unknown value we are trying to approximate and the approximation which has an error OH and third one sided approximations m Calculus and Math 541 Review 7 2946 Calculus and Math 541 Review 7 3046 Building High Accuracy Approximations lll Building High Accuracy Approximations llll C0 5lder3 00 We can play the game again and combine N2h with N2h2 to M 7 N10 Z Ekhk7 get a third order accurate approximation etc k1 and 4Nh27Nh Nh27Nh oo hk 2 2 2 3 2 M 7 N1h2 Z Ek27 k1 If we let N2h 2N1h2 7 N1h then NM NEW2 Nah2 Nsh h n 2 k M7N2h2E177E1hZEk h N4h2N4h J e2 Nsh N4h2 W where N h 2 7 N h e 1 Nj1h two2 Ek Ek 7 7 l 21 i 1 2k 53339 5353 Calculus and Math 541 Review 7 3146 Calculus and Math 541 Review 7 3246 Building Integration Schemes with Lagrange Polynomials Identifying the Coefficients Given the nodes X07X17 polynomial 7Xn we use the Lagrange interpolating b b n n b n PX dX Z LX dX Z 25 L39X dX Z 253 a a 0 0 L i0 3 n n n1 X Pnx Z fLX7 with error EnX X7X Hence We WV39te 0 n l 0 b n to obtain fX dx x Z af a 0 b b b with error given by fX dX PnX dX EX dx 2 a a b b f 1EX quot Ef EXdx Wl xemdx m a a 0 m Calculus and Math 541 Review 7 3346 Calculus and Math 541 Review 7 3446 Example 1 Trapezoidal Rule Example 2 Simpson39s Rule with optimal error bound Let a X0 lt X1 b and use the linear interpolating polynomial quot2 fxdx h fx0 4fx1 fxz 7 Ii foggy 3 90 X7X X7X P1Xf0 1 f1 Oly Then X0 7 X1 X1 7 X0 Taylor expand fx about X1 X W X 4 X b M 7 W1 New 7 x1gt lx 7 x1 melx 7 m3 x 7 M f x f x h3 fx dx h 7 f 57 h b 7 a Integrating the error term gives a b Max A 7 We 5 ATX7X1 4x Th Using the approximation fx1 21fx07 2fx1 am gmm x 3 2 4 f fxdx 7 2hfX1 l Elam 7 2M 4le 7 3 67251th rx04rx1rxQ h5 A h 7 7f 5 q l 3 l 90 m Calculus and Math 541 Review 7 3546 Calculus and Math 541 Review 7 3646 Degree of Accuracy Precision of an Integration Scheme Newton Cotes Formulas Two Types 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 Vk07177n With this definition Scheme Degree of Accuracy Trapezoidal 1 Simpson s 3 Trapezoidal and Simpson s are examples of a class of methods known as Newton Cotes formulas Two types of Newton Cotes Formulas Closed The n 1 point closed NCF uses nodes X X0 h i 0717 7n whereXO a X band h bian It is called closed since the endpoints are included as nodes Open The n 1 point open NCF uses nodes X X0 h 07177nwhere h bian2 and X0 ah Xn b 7 h We label X11 a Xn1 b m m Calculus and Math 541 Review 7 3746 Calculus and Math 541 Review 7 3846 Closed Newton Cotes Formulas Closed Newton Cotes Formulas Error Theorem Newton Cotes Formulas Error Term Suppose that 20 aifX denotes the n l 1 point closed Th t Newton Cotes formula With X0 a Xquot b and h b 7 an Then e aPPrOlea Ion 395 there existsE 6 37 b for Which b n b n hn3 fn2 n fX dX ZenW07 fxdx Emu I5 7 1 t e ndt a 0 a 0 n 2 0 where n ifn is even and f E Cquot2a7 b and Xquot Xquot X 7 X1 a Ln739X dX H dX b n hn2fn15 n Xe x0 129 I 1 fxdxZafXW tt71t7ndt 1 3e I 9 i0 39 0 ifn is odd and f E Cquot1a7 b Note that when n is an even integer the degree of precision is n 1 When n is m odd the degree of precision is only n Calculus and Math 541 Review 7 3946 Calculus and Math 541 Review 7 4046 Closed Newton Cotes Formulas Examples Composite Simpson s Rule lll n 2 Simpson s Rule 5 gfX0 4fX1 l fX2 7 3 l l w Simpson s g Rule 3h 375 g flxol 3fx1 324le flxsll e 4445 n 4 Boole s Rule For an even integer n Subdivide the interval a7 b into n sub intervals and apply Simpson s rule on each consecutive pair of sub intervals With h b 7 an and Xj a jh j O7 17 n we have b quot2 X2 fXdX fXdX a j1 X2172 n2 5 Z 09172 409171 091 f4517 j1 for some 51 E X2j2X21 if f E C4ab 2h 8h7 6 E 7fX0 l 32fX1 l 12fX2 l 32fX3 l 7fX4 7 5 Since all the interior even ng points appear twice in the sum we 95 can simplify the expression a bit 53g Calculus and Math 541 Review 7 4146 Calculus and Math 541 Review 7 4246 Composite Simpson39s Rule llll Romberg Integration quot2 5 quot2 fwdx 2 we 7 axquot f la1 24ml 7 g 4 Romberg Integration is the combination of the Composite Trapezoidal Rule CTR Theorem Composite Simpson s Rule Let f E C4a7 b n be even h b7 an and X39 a jh 7 J b h 7 1 b a j O7 17 n There eXsts p 6 a7 b for which the CompOSIte fXdX 7 8 Nb 2 Z 7 yM Slmpson s Rule for n sub Intervals can be written With Its error a 2 F1 12 term as and Richardson Extrapolation b h n2 a fXdX 3 8 7 Kb l l2fX2j l 4fX2j1l lt yields a method for generating high accuracy integral 1 1 approximations using several measurements using the relatively b 7 a h4f4p39 crude inaccurate Trapezoidal Rule 180 m 5393 Calculus and Math 541 Review 7 4346 Calculus and Math 541 Review 7 4446 Romberg Integration Implemented Next Time and Beyond 394 Romberg Integration for sinx over 0pi a O b pi 39A The Endpoints R zeros77 R11 b 7 a2 sina sinb for k 2 k h b7a 2 1 Mk lZ RM 17 1 2 M 2sina 2 1 2mm 7 1 h Slmulatlng ODEs usmg Euler 5 method and Improvements end 39 7 1 Rm 7 1 7 RM 7 1 7 W7 117 14J1gt71 di sp R m Calculus and Math 541 Review 5351 7 4546 Calculus and Math 541 Review 7 4646

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

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

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