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

### View Full Document

## 19

## 0

## Popular in Course

## Popular in Mathematics (M)

This 26 page Class Notes was uploaded by Miss Gladys Lubowitz 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 19 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

i iiiaii g m M ii iii n 5 team U M 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 PelerBlom 7 ma L initial Value Pr Outline 0 Linear Multistep Methods amp Stiffness a Limited Stability Regions 0 The 2nd Dahlquist Barrier 0 Trapezoidal Rule with Enhancements a LM Ms amp Stiffness ctd 0 Widlund39s LMM Limitation 0 BDF Methods 9 Initial Value Problems pass 1 Wrap up 0 Checking the Road Map 0 Quick Summary and Recap 0 Key Building Block The Newton Solver Peter Blomgren Linear Multistep Methods for Stiff Systems 7 225 Today39s Lecture 0 Wrap up the discussion of solutions of stiff initial value problems 0 An overview of how to use linear multistep methods for stiff problems 0 How to build an efficient scheme for stiff ODEs Linear Mul 39 lep Method 39or Stiff 5y en Linear Mullislep Methods 8 539 n LMM cl initial Value Problem 1 7 W 17in Linear Multistep Methods and Stiffness Linear Multistep Methods tend to have small regions of absolute stability and are therefore not particularly well suited for stiff problems The notable exception are the Backward Differentiation Formula BDF methods BDF Methods Stability Regan Linear Mul 39 lep Method 39or Stiff 5y en Linear Mullislep Methods 8 Sli es atiff c Vim Mi zjnzmmamu c wnmr Dahlquist 1963 quantified how difficult it is for Linear Multistep Methods to achieve A stability The limb twig 0 An explicit linear multistep method cannot be A stable C9 The order of an A stable linear multistep method cannot exceed 2 Q The second order A stable linear multistep method With smallest error constant is the Trapezoidal Rule imle Mm law Peter Blomgren Linear MulLislep Methods 8 539 n LMM cl i initial lalue Prohlen 1 7 W Hip Trapezoidal Rule with Enhancements Implementing Trapezoidal Rule for Stiff Systems Recall Trapezoidal rule is not L stable and if we have an eigen value with large negative real part we may have a damped oscillatory behavior until the associated transient has de cayed Real world implementation of Trapezoidal rule for stiff systems usually employ 3 tricks 9 A smoothing procedure to lessen the oscillatory behavior Extrapolation to raise the order to 4 9 Local error estimation by Richardson Extrapolation Linear Mul 39 lep Method 39or Stiff 5y en Linear Multislep LM initial Value Pl39ol39 Trapez lal hancemems Smoothing for the Trapezoidal Rule The oscillations for the fast transients can be alleviated in two ways O by taking a smaller step initially adaptive scheme or 9 by smoothing the solution The smoothing idea was introduced by Lindberg 1971 We replace yquot by A 7 Ynil 2YnYn1 yni f and then propagate the solution This weighted average smooths out the oscillations Peter Blomgren Linear Multislep Methods for sun Systems 7 725 ihvziwmxlm mm The smoothing procedure is active for the first couple of steps while the fast transients are still alive andor introduced automatically whenever the solution exhibits lack of smoothness Of course the smoothing affects the local truncation error the complete analysis is in Lindberg39s paper B Lindberg On Smoothing and Extrapolation for the Trapezoidal Rule BlT 11 pp 29 52 1971 BIT is a suitable permutation of the letters T and B from Nordisk Tidskrift for Informations Behanding Obviously Peter Blomgren mm mm mm u KL swims MMs xi SLiiTneS cld 39 1 7 Wr up Lquotquot quotquot quotquotquotluml M9 vii4mm ll MHKul tumw ii initial Value Problems n 1 er Theorem Lime Iltjstep Methods If we relax the requirement for complete A stability there are some options mum 1 0 An explicit linear multistep method cannot be A0 stable Q There is only one A0 stable linear k step method Whose order exceeds k the Trapezoidal Rule 0 For all 04 E 07 7r2 there exists Aa stable linear k step methods oforder p for Which k p 3 and k p 4 If we relax the for all requirement in Peter Blomgren mm mm mm u Liquot Widlund39s LMM Limitation 39 ms initial Value Prohlen 7 W yup Another Theorem for Linear Multistep Methods If we relax the for all requirement in then we can find k step methods of order k gt 4 that are Aa stable for some value of Oz most notably the BDF methods for k 47 57 6 Recall that the BDF methods are zero stable for k g 6 Linear Mul 39 lep Method 39or Stiff 5y en Recall The stability polynomial for a linear multistep method is M a Fair 7rr7 h For a stiff system is very large hence the stability properties would be dominated by 0r For stability we want the roots of 0r to be inside the unit circle The safest place would be the center of the unit circle With 0r rquot we achieve just that 0r rk amp implicit method amp maximal order BDF methods Linear Mullislep Methods for SLi Peter Blomgren 5351 initial lalue Pr Building an Efficient Algorithm for Stiff Problems We will use the BDF methods to construct an efficient algorithms for the solution of stiff ODEs Starting from the predictor corrector PEC framework 9 The BDF method will play the role of the corrector C in the Adams Bashforth Moulton predictor corrector framework 0 The fixed point iteration ECf is replaced by a Newton iteration pursued to convergence thus the stability properties of the predictor does not influence the overall stability properties Peter Blomgren Linear MulLislep Methods for SLi Linear Mnlli initial Value Pl39ol39 i J 7 mg an lrt forEtifF Problems lllll Newton iteration advantage convergence Newton iteration converges quadratically doubling the number of accurate digits in each iteration whereas fixed point iteration converges linearly Newton iteration disadvantage starting point Unlike the fixed point iteration the Newton iteration does not converge for arbitrary starting values a good starting value is required Warming l An explicit predictor is likely not to give a good enough starting value Peter Blomgren V Initial Value P M BDF Method Building an Efficient Algorithm for Stiff Problems IllIll 3 We replace the AdamsBashforth Predictor P by an extrapolation of previously computed y values For a k step k order method the extrapolation must be based on the previous k l 1 points ynk1ynk2 yn1 k 0 yilk Zvlynk71 i0 This interpolant predictor has an error constant C 1 1 hence the Milne39s estimate for the principal part of the local truncation error is still available Ck1 o LTE N 7 n 7 17 Ck1 y k ynkl Peter Blomgren Linear Multislep Methods for sun Systems 7 1425 Putting it Together BDF based Solver for Stiff ODEs P EXtrapolate to get an initial value for the Newton itera tion k ylglk Zviynlnkil i0 EC ltgt Use the implicit BDF method as the corrector and solve to convergence using a quadratically convergent Newton solver Err Estimate the error using Milne39s Error estimate Ck1 o LTE N 7 n 7 17 CH1 ly tk ynkl Tol Is the error small enough If not either 1 reduce the step size or 2 increase the order of the method 535 Peter Blomgren Linear MulLislep Methods for SLi 51 LMM cl Initial Value Problems pass 1 7 Wraprup Checking the Road Map Besides covering the Newton solver which we need both for the BDF based solver and for the Implicit Runge Kutta methods we have covered the solution of the Initial Value Problem for ODEs in quite a bit of detail Before reviewing Newton39s Method lets summarize what we have found so far Linear Mul 39 lep Method 39or Stiff 5y en LM Initial Value Problems pa Summary Numerical Solution to the Initial Value Problem The Initial Value Problem y f ff7yf7 yfo yo Taylor Series Methods Best used when the Taylor expansion of ftyt is available and cheapeasy to compute Stiffness Small stability region Step size h very restrictive Linear Mullislep Methods l 39L N s c Initial Value Problems 1 7 WrapHip 1 ick Summary and Summary Numerical Solution to the NP Runge Kutta Methods When the Taylor expansion of ftyt is not easily computable or prohibitively expensive but multiple evaluation of ftyt incur a reasonable amount of work then RK methods are a good choice Stiffness When the problem is stiff we have to use fully implicit RK methods We have seen that there are A stable s stage 25 order methods GaussLegendre for arbitrary s as well as L stable s stage 2sil order methods Radau l A and ll A Peter Blomgren Linear MulLislep Methods for SLi inear Multistep Initial Value Problems pa Summary Numerical Solution to the NP IllIll Linear Multistep Methods Explicit LM Ms only require one new function evaluation per step making then very competitive fast and cheap Used in the predictor corrector context PEC only 1u evaluations per step are required The main drawback is that LMMs are not self starting so we need an RK or Taylor series method possibly with Richardson Extrapolation to generate enough accurate starting information Stiffness lfwhen we can live with an Aa stable method im plementing efficient LMM based stiff solvers is quite straight for ward at least up to order 5351 Peter Blomgren Linear Multistep Methods for Stiff Systems 7 1925 Lin lVlHlllStep l N quotno u i i Initial Value Problems p Tl Newton Solver The Final Piece the Newton Solver In both implicit RK methods and the BDF based LMM methods for stiff problems we run into the problem of solving a non linear equation F9n17 C9n17 we can always rewrite this problem as fl9n1l F n17 G9n17 0 which means we are trying to solve f7n1 0 If our problem is scalar one dimensional then n1 yn1 is a scalar and we can use Newton39s method as described in Math 541 Peter Blomgren Linear Multistep Methods for Stiff Systems 7 Zn25 Lina 39 tistep LM a u we v Initial Value Problems 1 1 7 WrapHip Key B 7 Newton Solver Newton39s Method for Scalar Problems We are trying to find the roots y of the equation fy 0 ifwhen we have a guess close to a root ie ly 7yl is small then we can formally Taylor expand around y and get y 7 y 2 W 7 W w 7 yf y mmgt 500 6 miny7y7 maXy7y Since ly 7 yl is small ly 7 y kl2 is even smaller so we neglect the quadratic term in the expansion Also fy O by assumption hence we have 0 x f 7 f y y y y m Peter Blomgren Linear Multistep Methods for Stiff Systems 7 2125 Skiff 7 c u K 1 7 WrapHip Key Builr g Bloc The Newton Solver Newton39s Method for Scalar Problems ll We solve for y and get y z y 7 y y A Newton iterative solver implements yy1 yM 7 flyM PM and converges quadratically as long as f y 7 0 If a priori we know that the derivative will be zero at the root then we can implement the more costly version of Newton39s method yy1 yM 7 flylvllfylvll WWW f yl lfyl l 535a Peter Blomgren Linear MulLislep Methods for SLi LMR quotin chl v n Initial Value Problems pa 1 7 WrapHip Key Bui Block The Newton Solver Newton39s Method for more Than One Dimension When we have n simultaneous ODEs yf g1y177ynt Mt gny17 yn t by the same procedure Taylor expansion for a vector valued function of a vector valued argument we get 8f 8 0 e H9 7 l ml 19 rc The matrix JG is usually referred to as the Jacobian Linear Mullislep Methods I LMM a u 7 Initial Value Problems pass 1 7 WrapHip Key Building Block The Newton Solver Newton39s Method for more Than One Dimension Again we solve for y and define our iterative scheme 9W J9 l 19 How to solve this iteration efficiently especially for large systems is a matter which will be covered in Math 693a and Math 543 Linear Mul 39 lep Method 39or Stiff 5y en LMM ci v V Initial Value Problems pass 1 7 WrapHip Key Building Bloc The Newton Solver Wrapping Up lVPs 0 We now have a pretty complete picture of how to solve the initial value problem even when it fights back stiff problems 0 The past few lectures on stiff problems have covered some pretty adult topics which put together quite a few ideas from vector calculus complex analysis previous knowledge of numerical methods etc Linear Mul 39 lep Method 39or Stiff 5y en Lil illi e LMM Initial Value Problems pass 1 The Newton Solver Wrapping Up lVPs 0 Being a quotcomputational scientistquot means you have to understand how your problem fits into the numerical framework and make sure your starting methods error checking and stability analysis are done right At some point you have to understand every aspect of the problem in enough detail that you can implement it in your favorite computer language 0 Given the complexity of the methods we have covered it is a daunting task to try to give non silly examples of all of them However in the next lectures some examples will be given

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

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

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