Forecasting and correction methods (iterative methods) Euler method and Milne method

The methods we studied earlier had one important feature — each method usually corresponds to a certain accuracy class, which we designated as O ⁱ . For example, the Euler method had the first accuracy class O ¹ . This meant that with a step decrease of 10 times (an order of magnitude), the accuracy of the result also increased 10 times (by one order of magnitude). The Runge-Kutta method has 4 order of accuracy - O ⁴ , with decreasing step 10 times, the result is improved 10 000 times. Since this method uses only 4 times more calculations compared to the Euler method, its use is more profitable. Today, methods up to 8 orders of accuracy are known (for example, the Prince Dortmund method), although at the same time it is worth bearing in mind that writing algorithms for them is quite a difficult task. The advantage of all these algorithms is that the amount of computation for them is known in advance.

If you want to achieve ANY accuracy on the step, you should use the methods of forecasting and correction. This approach consists in the fact that the calculation of the trajectory defined by the equation occurs repeatedly at each step. Namely, first, the approximate value of the function is calculated at the end of a step by some simple formula (for example, by the Euler method), then the derivative is calculated at this point, and the calculation is again from the starting point at the step, but with the adjusted derivative value. The last operation - specification of the derivative and function values ​​at the end of a step - occurs MULTIPLELY AT EACH STEP , that is, until the calculated values ​​(function and derivative at the end of the step) stop changing or change slightly, less than the value specified in advance ε . Only then can we say that the accuracy ε is reached.

So, at the expense of an iterative procedure at each separate step , any given accuracy ε can be achieved. You have to pay for such an advantage of the method: unfortunately, it is impossible to say in advance how many iterations are required to achieve a given accuracy ε at a step. Therefore, such methods cannot, for example, be used in real-time systems.

Consider for example two methods from this class. As before, the problem is to find the function y ( t ) from the differential equation dy / dt = f ( y , x , t ) or a set of functions from a system of such equations.

Euler method with iterations

1) The predictive formula calculates (predicts) the value of the function at the right end of the step: y _{k + 1} = y _k + f _k · Δ t .

2) Calculate the derivative at the point k + 1 by substituting the original equation at the k + 1 point: f _{k + 1} = f ( t + Δ t , y _{k + 1} ).

3) The clarifying formula, using the old value of the derivative (from step 1) and refined from step 2, gives the refined value of y _{k + 1} : y _{k + 1} = y _k + ( f _k + f _{k + 1} ) · Δ t / 2 . It also calculates the iterations by the counter i : i : = i + 1.

4) Check accuracy: | y _{k + 1} ^{i -th iteration} - y _{k + 1} ^{( i + 1) -th iteration} | ≤ ε . If the condition is fulfilled and the accuracy ε is reached, then we go to the next step 5), otherwise we go to step 2) and the refinement process is repeated with the new values ​​of y and f , and their old value is taken from the previous iteration.

5) Preparing for a new step: changing the time counter t by the amount Δ t and changing the step number k :
t : = t + Δ t
k : = k + 1.

6) Check the end of calculation: t ≤ T. If the condition is satisfied, the calculation continues for the next point, the transition to 1), otherwise - the end.

Milna method

1) The predictive formula calculates the coarse y value at the right end of the interval: y _{k + 1} : y _{k + 1} = y _{k - 3} + 4/3 · (2 ​​· f _k - f _{k - 1} + 2 · f _{k - 2} ) · Δ t .

2) Calculate the derivative at the k + 1 point: f _{k + 1} = f ( t + Δ t , y _{k + 1} ).

3) Once again, y _{k + 1 is} calculated using the updated formula, using the new value of the derivative at the point k + 1: y _{k + 1} = y _{k - 1} + 1/3 · ( f _{k + 1} + 4 · f _k + f _{k - 1} ) · Δ t .

4) Calculate the derivative at k + 1 point, taking into account the newly calculated more accurate value of y _{k + 1} : f _{k + 1} = f ( t + Δ t , y _{k + 1} ). It also calculates the iterations by the counter i : i : = i + 1.

5) Check accuracy: | y _{k + 1} ^{i -th iteration} - y _{k + 1} ^{( i + 1) -th iteration} | ≤ ε . If the condition is fulfilled, and the accuracy ε is reached, then we go to the next step 6, otherwise the transition to step 3 is made and the refinement process is repeated with new values ​​of y and f , and their old value is taken from the previous iteration.

6) Preparing for a new step: changing the time counter t , changing the step number k :
t : = t + Δ t
k : = k + 1.

7) Check the end of calculation: t ≤ T. If the condition is satisfied, the calculation continues for the next point, and proceeds to step 1, otherwise - the end.