1、Ch 8.4: Multistep Methods,Consider the initial value problem y = f (t, y), y(t0) = y0, with solution (t). So far we have studied numerical methods in which data at the point tn is used to approximate (tn+1). Such methods are called one-step methods. Multistep methods use previously obtained approxim
2、ations of (t) to find the next approximation of (t). That is, the approximations y1, , yn at t1, , tn, respectively, may be used to find yn+1 at tn+1. In this section we discuss two types of multistep methods: Adams methods and backward differentiation formulas. For simplicity, we will assume the st
3、ep size h is constant.,Adams Methods,Recall thatThe basic idea of an Adams method is to approximate (t) in the above integral by a polynomial Pk(t) of degree k. The coefficients of Pk(t) are determined by using the k +1 previously calculated data points. For example, for P1(t) = At + B, we use (tn-1
4、, yn-1) and (tn, yn), with P1(tn-1) = f (tn-1, yn-1) = fn-1 and P1(tn) = f (tn, yn) = fn. Then,Second Order Adams-Bashforth Formula,From the discussion on the previous slide, it follows thatevaluates toAfter simplifying, we obtain This equation is the second order Adams-Bashforth formula. It is an e
5、xplicit formula for yn+1 in terms of yn and yn-1, and has local truncation error proportional to h3. We note that when a constant polynomial P0(t) = A is used, the first order Adams-Bashforth formula is just Eulers formula,Fourth Order Adams-Bashforth Formula,More accurate Adams formulas can be obta
6、ined by using a higher degree polynomial Pk(t) and more data points. For example, the coefficients of a 3rd degree polynomial P3(t) are found using (tn, yn), (tn-1, yn-1), (tn-2, yn-2), (tn-3, yn-3). As before, P3(t) then replaces (t) in the integral equationto obtain the fourth order Adams-Bashfort
7、h formula The local truncation error of this method is proportional to h5.,Second Order Adams-Moulton Formula,A variation on the Adams-Bashforth formulas gives another set of formulas called the Adams-Moulton formulas. We begin with the second order case, and use a first degree polynomial Q1(t) = t
8、+ to approximate (t). To determine and , we now use (tn, yn) and (tn+1, yn+1): As before, Q1(t) replaces (t) in the integral equation to obtain the second order Adams-Moulton formula Note that this equation implicitly defines yn+1. The local truncation error of this method is proportional to h3.,Fou
9、rth Order Adams-Moulton Formula,When a constant polynomial Q0(t) = is used, the first order Adams-Moulton formula is just the backwards Euler formula. More accurate higher order formulas can be obtained using a polynomial of higher degree. For example, the fourth order Adams-Moulton formula isThe lo
10、cal truncation error of this method is proportional to h5.,Comparison of Methods,The Adams-Bashforth and Adams-Moulton formulas both have local truncation errors proportional to the same power of h, but moderate order Adams-Moulton formulas are more accurate. For example, for the fourth order method
11、s, the proportionality constant on h5 for the Adams-Moulton formula is less than 1/10 that of the Adams-Bashforth formula. The Adams-Bashforth formula explicitly defines yn+1 and thus is faster than the more accurate Adams-Moulton formula, which implicitly defines yn+1. Which method to use depends o
12、n whether, by using the more accurate method, the step size can be increased to reduce the number of computations required. A predictor-corrector method combines both approaches.,Predictor-Corrector Method,Consider the fourth order Adams-Bashforth and Adams-Moulton formulas, respectively: Once yn-3,
13、 yn-2, yn-1, yn are known, we compute fn-3, fn-2, fn-1, fn and use Adams-Bashforth formula (predictor) to obtain yn+1. We then compute fn+1, and use the Adams-Bashforth formula (corrector) to obtain an improved value of yn+1. We can continue to use corrector formula if the change in yn+1 is too larg
14、e. However, if it is necessary to use the corrector formula more than once or perhaps twice, the step size h is likely too large and should be reduced.,Starting Values for Multistep Methods,In order to use any of the multistep methods, it is necessary to first to calculate a few yk by some other met
15、hod. For example, the fourth order Adams-Moulton method requires values for y1 and y2, while the fourth order Adams-Bashforth method also requires a value for y3. One way to proceed is to use a one-step method of comparable order to calculate the necessary starting values. For example, for a fourth
16、order multistep method, use a fourth order Runge-Kutta method to calculate the starting values. Another approach is to use a low order method with a very small h to calculate y1, and then to increase gradually both the order and step size until enough starting values are obtained.,Example 1: Initial
17、 Value Problem (1 of 6),Recall our initial value problem With a step size of h = 0.1, we will use the methods of this section to approximate the solution solution (t) at t = 0.4. We use the Runge-Kutta method to find y1, y2 and y3. These values are given in Table 8.3.1. The corresponding values for
18、f (t, y) = 1 t 4y can then be computed, with results below.,Example 1: Adams-Bashforth Method (2 of 6),The values of fk from the previous page areUsing the fourth order Adams-Bashforth formula, we haveThe exact value of (0.4) can be found using the solution,and hence the error in this case is -0.010
19、5955, with a relative error of 0.183%.,Example 1: Adams-Moulton Method (3 of 6),Recall the fourth order Adams-Moulton formula:Using the previously calculated values of fkthe fourth order Adams-Moulton formula reduces toSolving this linear implicit equation for y4, we obtain Recall that the exact val
20、ue to seven decimal places is The error in this case is therefore 0.0000416, with a relative error of 0.0072%.,Example 1: Predictor-Corrector Method (4 of 6),Recall our fourth order equations:Using the first equation, we predict y4 = 5.7836305, as before. Then f4 = 1 0.4 + 4(5.7836305) = 23.734522.
21、Using the second equation as a corrector, we obtain The error is -0.0015539, with a relative error of 0.02682%. The error for the corrected y4 has been reduced by a factor of approximately 7 when compared to the error of predicted y4.,Example 1: Summary of Results (5 of 6),The Adams-Bashforth method
22、 is the simplest and fastest of these methods, but is also the least accurate. Using the Adams-Moulton formula as a corrector increases the amount of calculation required, but still is explicit in y4. For this problem, the error in corrected value of y4 is reduced by a factor of 7 when compared to t
23、he error in predicted y4. The Adams-Moulton method yields the best result, with an error that is about 1/40 the error of predictor-corrector result. The Adams-Moulton method is implicit in y4, and hence an equation must be solved at each step. For this problem, the equation was linear with y4 easily
24、 found. In other problems, this part of the procedure may be more time consuming.,Example 1: Comparison with Runge-Kutta Method (6 of 6),The Runge-Kutta method for h = 0.1 gives y4 = 5.7927853, as seen in Table 8.3.1. The corresponding error is -0.0014407, with a relative error of 0.02686%. Thus the
25、 Runge-Kutta method is comparable in accuracy to the predictor-corrector method for this example.,Backward Differentiation Formulas,Another type of multistep method uses a polynomial Pk(t) to approximate the solution (t) instead of its derivative (t). We then differentiate Pk(t) and set Pk(tn+1) = f
26、(tn+ 1, yn+1) to obtain an implicit formula for yn+1. These are called backward differentiation formulas. The simplest case uses a first degree P1(t) = At + B. The values of A and B are chosen to match the computed solution values yn and yn+1:Also, we set Pk(tn+1) = A = f(tn+ 1, yn+1), as mentioned
27、above.,Backward Differentiation: First Order Formula,We thus have A = f (tn+ 1, yn+1) and From these two equations for A, it follows thatNote that this is the backward Euler formula.,Higher Order Formulas,By using higher order polynomials and correspondingly more data points, backward differentiatio
28、n formulas of any order can be obtained. The second order formula isThe local truncation error of this method is proportional to h3. The fourth order formula isThe local truncation error of this method is proportional to h5.,Example 2: Fourth Order Backward Differentiation Method (1 of 2),Recall our
29、 initial value problem Use the fourth order backward differentiation formula with h = 0.1 to approximate the solution solution (t) at t = 0.4. From Example 1, we have the following data:Thusand hence,Example 2: Results (2 of 2),Our fourth order backward differentiation approximation is Recall that t
30、he exact value to seven decimal places is The error in this case is therefore 0.0025366, with a relative error of 0.0438%. These results are somewhat better than the Adams-Bashforth method, but not as good as using the predictor-corrector method, and not nearly as good as the result using the Adams-
31、Moulton method.,Comparison of One-Step and Multistep Methods (1 of 2),In comparing methods, we first consider the number of evaluations of f at each step: The fourth order Runge-Kutta method requires four calculations of f. The fourth order Adams-Bashforth method, once past the starting values, requ
32、ires only one evaluation of f. The predictor-corrector method requires two evaluations of f. Thus, for a given step size h, the latter two methods may be faster than Runge-Kutta. However, if Runge-Kutta is more accurate and can therefore use fewer steps, then the difference in speed will be reduced
33、and perhaps eliminated. The Adams-Moulton and backward differentiation formulas also require that the difficulty in solving the implicit equation at each step be taken into account.,Comparison of One-Step and Multistep Methods (2 of 2),All multistep methods have the possible disadvantage that errors
34、 in earlier steps can feed back into later calculations. On the other hand, the underlying polynomial approximations in multistep methods make it easy to approximate the solution at points between the mesh points, if desirable. Multistep methods have become popular largely because it is relatively easy to estimate the error at each step and adjust the order or the step size to control it.,
