M427K Handout: Advanced Numerical MethodsSalman ButtApril 21, 2006Runge-Kutta MethodThis method is given by the formulaIts global truncation error is bounded by a constant multiple of h4and its local truncation error ison the order of h5.Multi-step Method 1: Adams Meth odsThe Adams method is a multistep metho d. We fix a step size h. Adams methods use apolynomial of degree k denoted Pk(t) to approximate φ0(t) in the equationφ(tn+1) − φ(tn) =Ztn+1tnφ0(t)dtWe take the simple case with k = 1 and set P1(t) = At + B. We require P1(tn) = f (tn, yn) andP1(tn−1) = f (tn−1, yn−1). Plugging in for P1and solving for A and B, we findPlugging this into our integral equation, integrating, and plugging y’s in for the φ’s , we get theequationThis is the second order Adams-Bashforth formula. It requires knowing ynand yn−1. Its localtruncation error is on the order of h3. Note that the first order Adams-Bashforth formula (i.e.when k = 0) is merely Euler’s method. Note also that the accuracy of this method increases as youincrease k.Varying this formula slightly by forcing P1(tn+1) to be equal to f(tn+1, yn+1), we get a newformula:1This is the second order Adams-Moulton formula. Note this is an implicit equation with localtruncation error on the order of h3. We can increase the degree of the polynomial as in A-B to getmore accurate results. Note that the first order A-M formula (i.e. k = 0) is just the backward Eulermethod. Though it has the same LTE as the A-B method, A-M is considerably more accurate formoderate orders, though it is slower. What method to use depends on the given problem.These two methods can be used together as a predictor-corrector method. A-B is the predictor,while A-M plays the role of the corrector. We use A-B to compute the first approximation yn+1.We then compute fn+1for A-M and get a more accurate value of yn+1. If the difference betweenthese two values is too large, we use A-M again. If we have to use A-M more than once or twice,our step size h is too large and must be decreased.In order to compute the first few terms needed for the multi-step methods, you can use a one-step method to compute these values. Another approach is to use a low order method with a verysmall step size to calculate some initial values, and then increase the order and step size graduallyuntil enough values have been c omputed to use the higher order method.Multi-step Method 2: Backward Differentiation FormulaIn this method, the idea is use a polynomial of degree k, denoted Pk(t), to approximate φ(t),as opposed to φ0(t) for the formula φ0(t) = f (t, y). We then differentiate P and set P01(tn+1) =f(tn+1, yn+1) to get an implicit formula for yn+1. Taking the k = 1 case, we require P1(tn, yn) =f(tn, yn) and P1(tn+1, yn+1) = f(tn+1, yn+1) as well as the condition on P01. Plugging all this in toour equation, we get the formulaNote this is just the backward Euler formula. Increasing the degree of the polynomial yields moreaccurate backward differentiation formulas. For example, the second order formula is given bySee the end of section 8.4 for a discussion of relative merits of R-K and these multi-step methods.Here’s a brief