Из Википедии, бесплатной энциклопедии
  (Перенаправлено из метода Эйлера )
Перейти к навигации Перейти к поиску
Иллюстрация метода Эйлера. Неизвестная кривая выделена синим цветом, а ее полигональная аппроксимация - красным.

В математике и вычислительной науке , то метод Эйлер (также называемый вперед методом Эйлера ) представляет собой первый порядок численной процедура решения обыкновенных дифференциальных уравнений (ОДУ) с заданным начальным значением . Это самый основной явный метод для численного интегрирования обыкновенных дифференциальных уравнений и является самым простым методом Рунге-Кутта . Метод Эйлера назван в честь Леонхарда Эйлера , который рассмотрел его в своей книге Institutionum Calculi Integratedis (опубликованной 1768–1870 гг.). [1]

Метод Эйлера - это метод первого порядка, что означает, что локальная ошибка (ошибка на шаг) пропорциональна квадрату размера шага, а глобальная ошибка (ошибка в данный момент времени) пропорциональна размеру шага. Метод Эйлера часто служит основой для построения более сложных методов, например, метода предиктора-корректора .

Неформальное геометрическое описание [ править ]

Рассмотрим задачу вычисления формы неизвестной кривой, которая начинается в данной точке и удовлетворяет данному дифференциальному уравнению. Здесь, дифференциальное уравнение можно рассматривать как формулу , с помощью которого наклон по касательной к кривой может быть вычислена в любой точке на кривой, после того , как положение этой точки было рассчитано.

Идея состоит в том, что, хотя кривая изначально неизвестна, ее начальная точка, которую мы обозначаем как, известна (см. Рисунок вверху справа). Затем из дифференциального уравнения можно вычислить наклон кривой в точке и, таким образом, касательную линию.

Сделайте небольшой шаг по касательной до точки. На этом маленьком шаге наклон не слишком сильно меняется, поэтому он будет близок к кривой. Если мы притворимся, что это все еще на кривой, можно использовать те же рассуждения, что и для пункта выше. После нескольких шагов вычисляется многоугольная кривая . В общем, эта кривая не отклоняется слишком далеко от исходной неизвестной кривой, и ошибку между двумя кривыми можно сделать небольшой, если размер шага достаточно мал и интервал вычислений конечен: [2]

Выберите значение размера каждого шага и установите . Теперь один шаг метода Эйлера от до : [3]

Значение является приближением решения ОДУ в момент времени : . Метод Эйлера является явным , т. Е. Решение является явной функцией для .

Хотя метод Эйлера интегрирует ОДУ первого порядка, любое ОДУ порядка N может быть представлено как система ОДУ первого порядка: для обработки уравнения

,

введем вспомогательные переменные и получим эквивалентное уравнение:

Это система первого порядка по переменной, и ее можно обработать методом Эйлера или, фактически, любой другой схемой для систем первого порядка. [4]

Пример [ править ]

Учитывая проблему начального значения

мы хотели бы использовать метод Эйлера для аппроксимации . [5]

Размер шага равен 1 ( h = 1) [ править ]

Иллюстрацией численного интегрирования уравнения Блю является метод Эйлера; зеленый - метод средней точки ; красный - точное решение. Размер шага h  = 1.0.

Метод Эйлера

поэтому сначала мы должны вычислить . В этом простом дифференциальном уравнении функция определяется как . У нас есть

Выполнив описанный выше шаг, мы нашли наклон линии, касательной к кривой решения в этой точке . Напомним, что наклон определяется как изменение, деленное на изменение , или .

Следующий шаг - умножить указанное выше значение на размер шага , который мы здесь принимаем равным единице:

Поскольку размер шага - это изменение , когда мы умножаем размер шага и наклон касательной, мы получаем изменение значения. Затем это значение добавляется к начальному значению, чтобы получить следующее значение, которое будет использоваться для вычислений.

Вышеуказанные шаги следует повторить, чтобы найти , и .

Из-за повторяющегося характера этого алгоритма может быть полезно организовать вычисления в форме диаграммы, как показано ниже, чтобы избежать ошибок.

The conclusion of this computation is that . The exact solution of the differential equation is , so . Although the approximation of the Euler method was not very precise in this specific case, particularly due to a large value step size , its behaviour is qualitatively correct as the figure shows.

MATLAB code example[edit]

clear; clc; close('all');y0 = 1;t0 = 0;h = 1; % try: h = 0.01tn = 4; % equal to: t0 + h*n, with n the number of steps[t, y] = Euler(t0, y0, h, tn);plot(t, y, 'b');% exact solution (y = e^t):tt = (t0:0.001:tn);yy = exp(tt);hold('on');plot(tt, yy, 'r');hold('off');legend('Euler', 'Exact');function [t, y] = Euler(t0, y0, h, tn) fprintf('%10s%10s%10s%15s\n', 'i', 'yi', 'ti', 'f(yi,ti)'); fprintf('%10d%+10.2f%+10.2f%+15.2f\n', 0, y0, t0, f(y0, t0)); t = (t0:h:tn)'; y = zeros(size(t)); y(1) = y0; for i = 1:1:length(t) - 1 y(i + 1) = y(i) + h * f(y(i), t(i)); fprintf('%10d%+10.2f%+10.2f%+15.2f\n', i, y(i + 1), t(i + 1), f(y(i + 1), t(i + 1))); endend% in this case, f(y,t) = f(y)function dydt = f(y, t) dydt = y;end% OUTPUT:% i yi ti f(yi,ti)% 0 +1.00 +0.00 +1.00% 1 +2.00 +1.00 +2.00% 2 +4.00 +2.00 +4.00% 3 +8.00 +3.00 +8.00% 4 +16.00 +4.00 +16.00% NOTE: Code also outputs a comparison plot

R code example[edit]

Graphical output of the R programming language code for the posed example

Below is the code of the example in the R programming language.

# ============# SOLUTION to# y' = y, where y' = f(t,y)# then:f <- function(ti,y) y# INITIAL VALUES:t0 <- 0y0 <- 1h <- 1tn <- 4# Euler's method: function definitionEuler <- function(t0, y0, h, tn, dy.dt) { # dy.dt: derivative function # t sequence: tt <- seq(t0, tn, by=h) # table with as many rows as tt elements: tbl <- data.frame(ti=tt) tbl$yi <- y0 # Initializes yi with y0 tbl$Dy.dt[1] <- dy.dt(tbl$ti[1],y0) # derivative for (i in 2:nrow(tbl)) { tbl$yi[i] <- tbl$yi[i-1] + h*tbl$Dy.dt[i-1] # For next iteration: tbl$Dy.dt[i] <- dy.dt(tbl$ti[i],tbl$yi[i]) } return(tbl)}# Euler's method: function applicationr <- Euler(t0, y0, h, tn, f)rownames(r) <- 0:(nrow(r)-1) # to coincide with index n# Exact solution for this case: y = exp(t)# added as an additional column to rr$y <- exp(r$ti)# TABLE with results:print(r)plot(r$ti, r$y, type="l", col="red", lwd=2)lines(r$ti, r$yi, col="blue", lwd=2)grid(col="black")legend("top", legend = c("Exact", "Euler"), lwd=2, col = c("red", "blue"))# OUTPUT:## ti yi Dy.dt y# 0 0 1 1 1.000000# 1 1 2 2 2.718282# 2 2 4 4 7.389056# 3 3 8 8 20.085537# 4 4 16 16 54.598150# NOTE: Code also outputs a comparison plot

Using other step sizes[edit]

The same illustration for h = 0.25.

As suggested in the introduction, the Euler method is more accurate if the step size is smaller. The table below shows the result with different step sizes. The top row corresponds to the example in the previous section, and the second row is illustrated in the figure.

The error recorded in the last column of the table is the difference between the exact solution at and the Euler approximation. In the bottom of the table, the step size is half the step size in the previous row, and the error is also approximately half the error in the previous row. This suggests that the error is roughly proportional to the step size, at least for fairly small values of the step size. This is true in general, also for other equations; see the section Global truncation error for more details.

Other methods, such as the midpoint method also illustrated in the figures, behave more favourably: the global error of the midpoint method is roughly proportional to the square of the step size. For this reason, the Euler method is said to be a first-order method, while the midpoint method is second order.

We can extrapolate from the above table that the step size needed to get an answer that is correct to three decimal places is approximately 0.00001, meaning that we need 400,000 steps. This large number of steps entails a high computational cost. For this reason, people usually employ alternative, higher-order methods such as Runge–Kutta methods or linear multistep methods, especially if a high accuracy is desired.[6]

Derivation[edit]

The Euler method can be derived in a number of ways. Firstly, there is the geometrical description above.

Another possibility is to consider the Taylor expansion of the function around :

The differential equation states that . If this is substituted in the Taylor expansion and the quadratic and higher-order terms are ignored, the Euler method arises.[7] The Taylor expansion is used below to analyze the error committed by the Euler method, and it can be extended to produce Runge–Kutta methods.

A closely related derivation is to substitute the forward finite difference formula for the derivative,

in the differential equation . Again, this yields the Euler method.[8] A similar computation leads to the midpoint method and the backward Euler method.

Finally, one can integrate the differential equation from to and apply the fundamental theorem of calculus to get:

Now approximate the integral by the left-hand rectangle method (with only one rectangle):

Combining both equations, one finds again the Euler method.[9] This line of thought can be continued to arrive at various linear multistep methods.

Local truncation error[edit]

The local truncation error of the Euler method is the error made in a single step. It is the difference between the numerical solution after one step, , and the exact solution at time . The numerical solution is given by

For the exact solution, we use the Taylor expansion mentioned in the section Derivation above:

The local truncation error (LTE) introduced by the Euler method is given by the difference between these equations:

This result is valid if has a bounded third derivative.[10]

This shows that for small , the local truncation error is approximately proportional to . This makes the Euler method less accurate (for small ) than other higher-order techniques such as Runge-Kutta methods and linear multistep methods, for which the local truncation error is proportional to a higher power of the step size.

A slightly different formulation for the local truncation error can be obtained by using the Lagrange form for the remainder term in Taylor's theorem. If has a continuous second derivative, then there exists a such that

[11]

In the above expressions for the error, the second derivative of the unknown exact solution can be replaced by an expression involving the right-hand side of the differential equation. Indeed, it follows from the equation that

[12]

Global truncation error[edit]

The global truncation error is the error at a fixed time , after however many steps the methods needs to take to reach that time from the initial time. The global truncation error is the cumulative effect of the local truncation errors committed in each step.[13] The number of steps is easily determined to be , which is proportional to , and the error committed in each step is proportional to (see the previous section). Thus, it is to be expected that the global truncation error will be proportional to .[14]

This intuitive reasoning can be made precise. If the solution has a bounded second derivative and is Lipschitz continuous in its second argument, then the global truncation error (GTE) is bounded by

where is an upper bound on the second derivative of on the given interval and is the Lipschitz constant of .[15]

The precise form of this bound is of little practical importance, as in most cases the bound vastly overestimates the actual error committed by the Euler method.[16] What is important is that it shows that the global truncation error is (approximately) proportional to . For this reason, the Euler method is said to be first order.[17]

Numerical stability[edit]

Solution of computed with the Euler method with step size (blue squares) and (red circles). The black curve shows the exact solution.

The Euler method can also be numerically unstable, especially for stiff equations, meaning that the numerical solution grows very large for equations where the exact solution does not. This can be illustrated using the linear equation

The exact solution is , which decays to zero as . However, if the Euler method is applied to this equation with step size , then the numerical solution is qualitatively wrong: It oscillates and grows (see the figure). This is what it means to be unstable. If a smaller step size is used, for instance , then the numerical solution does decay to zero.

The pink disk shows the stability region for the Euler method.

If the Euler method is applied to the linear equation , then the numerical solution is unstable if the product is outside the region

illustrated on the right. This region is called the (linear) stability region.[18] In the example, is −2.3, so if then which is outside the stability region, and thus the numerical solution is unstable.

This limitation —along with its slow convergence of error with h— means that the Euler method is not often used, except as a simple example of numerical integration.

Rounding errors[edit]

The discussion up to now has ignored the consequences of rounding error. In step n of the Euler method, the rounding error is roughly of the magnitude εyn where ε is the machine epsilon. Assuming that the rounding errors are all of approximately the same size, the combined rounding error in N steps is roughly Nεy0 if all errors points in the same direction. Since the number of steps is inversely proportional to the step size h, the total rounding error is proportional to ε / h. In reality, however, it is extremely unlikely that all rounding errors point in the same direction. If instead it is assumed that the rounding errors are independent random variables, then the expected total rounding error is proportional to .[19]

Thus, for extremely small values of the step size, the truncation error will be small but the effect of rounding error may be big. Most of the effect of rounding error can be easily avoided if compensated summation is used in the formula for the Euler method.[20]

Modifications and extensions[edit]

A simple modification of the Euler method which eliminates the stability problems noted in the previous section is the backward Euler method:

This differs from the (standard, or forward) Euler method in that the function is evaluated at the end point of the step, instead of the starting point. The backward Euler method is an implicit method, meaning that the formula for the backward Euler method has on both sides, so when applying the backward Euler method we have to solve an equation. This makes the implementation more costly.

Other modifications of the Euler method that help with stability yield the exponential Euler method or the semi-implicit Euler method.

More complicated methods can achieve a higher order (and more accuracy). One possibility is to use more function evaluations. This is illustrated by the midpoint method which is already mentioned in this article:

.

This leads to the family of Runge–Kutta methods.

The other possibility is to use more past values, as illustrated by the two-step Adams–Bashforth method:

This leads to the family of linear multistep methods. There are other modifications which uses techniques from compressive sensing to minimize memory usage[21]

In popular culture[edit]

In the film Hidden Figures, Katherine Goble resorts to the Euler method in calculating the re-entry of astronaut John Glenn from Earth orbit.[22]

See also[edit]

  • Crank–Nicolson method
  • Gradient descent similarly uses finite steps, here to find minima of functions
  • List of Runge-Kutta methods
  • Linear multistep method
  • Numerical integration (for calculating definite integrals)
  • Numerical methods for ordinary differential equations

Notes[edit]

  1. ^ Butcher 2003, p. 45; Hairer, Nørsett & Wanner 1993, p. 35
  2. ^ Atkinson 1989, p. 342; Butcher 2003, p. 60
  3. ^ Butcher 2003, p. 45; Hairer, Nørsett & Wanner 1993, p. 36
  4. ^ Butcher 2003, p. 3; Hairer, Nørsett & Wanner 1993, p. 2
  5. ^ See also Atkinson 1989, p. 344
  6. ^ Hairer, Nørsett & Wanner 1993, p. 40
  7. ^ Atkinson 1989, p. 342; Hairer, Nørsett & Wanner 1993, p. 36
  8. ^ Atkinson 1989, p. 342
  9. ^ Atkinson 1989, p. 343
  10. ^ Butcher 2003, p. 60
  11. ^ Atkinson 1989, p. 342
  12. ^ Stoer & Bulirsch 2002, p. 474
  13. ^ Atkinson 1989, p. 344
  14. ^ Butcher 2003, p. 49
  15. ^ Atkinson 1989, p. 346; Lakoba 2012, equation (1.16)
  16. ^ Iserles 1996, p. 7
  17. ^ Butcher 2003, p. 63
  18. ^ Butcher 2003, p. 70; Iserles 1996, p. 57
  19. ^ Butcher 2003, pp. 74–75
  20. ^ Butcher 2003, pp. 75–78
  21. ^ Unni, M. P.; Chandra, M. G.; Kumar, A. A. (March 2017). "Memory reduction for numerical solution of differential equations using compressive sensing". 2017 IEEE 13th International Colloquium on Signal Processing Its Applications (CSPA): 79–84. doi:10.1109/CSPA.2017.8064928. ISBN 978-1-5090-1184-1. S2CID 13082456.
  22. ^ Khan, Amina. "Meet the 'Hidden Figures' mathematician who helped send Americans into space". Los Angeles Times. Retrieved 12 February 2017.

References[edit]

  • Atkinson, Kendall A. (1989). An Introduction to Numerical Analysis (2nd ed.). New York: John Wiley & Sons. ISBN 978-0-471-50023-0.
  • Ascher, Uri M.; Petzold, Linda R. (1998). Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-412-8.
  • Butcher, John C. (2003). Numerical Methods for Ordinary Differential Equations. New York: John Wiley & Sons. ISBN 978-0-471-96758-3.
  • Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993). Solving ordinary differential equations I: Nonstiff problems. Berlin, New York: Springer-Verlag. ISBN 978-3-540-56670-0.
  • Iserles, Arieh (1996). A First Course in the Numerical Analysis of Differential Equations. Cambridge University Press. ISBN 978-0-521-55655-2.
  • Stoer, Josef; Bulirsch, Roland (2002). Introduction to Numerical Analysis (3rd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-95452-3.
  • Lakoba, Taras I. (2012), Simple Euler method and its modifications (PDF) (Lecture notes for MATH334), University of Vermont, retrieved 29 February 2012
  • Unni, M P. (2017). "Memory reduction for numerical solution of differential equations using compressive sensing". 2017 IEEE 13th International Colloquium on Signal Processing & its Applications (CSPA). IEEE CSPA. pp. 79–84. doi:10.1109/CSPA.2017.8064928. ISBN 978-1-5090-1184-1. S2CID 13082456.

External links[edit]

  • Media related to Euler method at Wikimedia Commons
  • Euler method implementations in different languages by Rosetta Code
  • "Euler method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]