Content deleted Content added
No edit summary |
|||
| (38 intermediate revisions by 26 users not shown) | |||
Line 1:
In [[numerical analysis]] and [[scientific computing]], the '''backward Euler method''' (or '''implicit Euler method''') is one of the most basic [[numerical methods for ordinary differential equations|numerical methods for the solution of ordinary differential equations]]. It is similar to the (standard) [[Euler method]], but differs in that it is an [[explicit and implicit methods|implicit method]]. The backward Euler method has error of order one in time.
== Description ==
Consider the [[ordinary differential equation]]
:<math> \frac{\mathrm{d} y}{\mathrm{d} t} = f(t,y) </math>
with initial value <math> y(t_0) = y_0. </math> Here the function <math>f</math> and the initial data <math>t_0</math> and <math>y_0</math> are known; the function <math>y</math> depends on the real variable <math>t</math> and is unknown. A numerical method produces a sequence <math> y_0, y_1, y_2, \ldots </math> such that <math> y_k </math> approximates <math> y(t_0+kh) </math>, where <math> h </math> is called the step size.
The backward Euler method computes the approximations using
:<math> y_{k+1} = y_k + h f(t_{k+1}, y_{k+1}). </math> <ref>{{harvnb|Butcher|2003|p=57}}</ref>
This differs from the (forward) Euler method in that the forward method uses <math> f(t_k, y_k) </math> in place of <math>f(t_{k+1}, y_{k+1})</math>.
The backward Euler method is an implicit method: the new approximation <math> y_{k+1} </math> appears on both sides of the equation, and thus the method needs to solve an algebraic equation for the unknown <math> y_{k+1} </math>. For non-[[Stiff equation|stiff]] problems, this can be done with [[fixed-point iteration]]:
:<math> y_{k+1}^{[0]} = y_k, \quad y_{k+1}^{[i+1]} = y_k + h f(t_{k+1}, y_{k+1}^{[i]}). </math>
If this sequence converges (within a given tolerance), then the method takes its limit as the new approximation
<math> y_{k+1} </math>.<ref>{{harvnb|Butcher|2003|p=57}}</ref>
Alternatively, one can use (some modification of) the [[Newton's method|Newton–Raphson method]] to solve the algebraic equation.
== Derivation ==
Integrating the differential equation <math> \frac{\mathrm{d} y}{\mathrm{d} t} = f(t,y) </math> from <math> t_n </math> to <math> t_{n+1} = t_n + h </math> yields
: <math> y(t_{n+1}) - y(t_n) = \int_{t_n}^{t_{n+1}} f(t, y(t)) \,\mathrm{d}t. </math>
Now approximate the integral on the right by the right-hand [[rectangle method]] (with one rectangle):
: <math> y(t_{n+1}) - y(t_n) \approx h f(t_{n+1}, y(t_{n+1})). </math>
Finally, use that <math> y_n </math> is supposed to approximate <math> y(t_n) </math> and the formula for the backward Euler method follows.<ref>{{harvnb|Butcher|2003|p=57}}</ref>
The same reasoning leads to the (standard) Euler method if the left-hand rectangle rule is used instead of the right-hand one.
== Analysis ==
[[File:Stability region for BDF1.svg|thumb|The pink region outside the disk shows the stability region of the backward Euler method.]]
The [[local truncation error]] (defined as the error made in one step) of the backward Euler Method is <math> O(h^2) </math>, using the [[big O notation]]. The error at a specific time <math> t </math> is <math> O(h^2) </math>. It means that this method has '''order one'''. In general, a method with <math> O(h^{k+1}) </math> LTE (local truncation error) is said to be of ''k''th order.
The [[Stiff_equation#Runge%E2%80%93Kutta_methods|region of absolute stability]] for the backward Euler method is the complement in the complex plane of the disk with radius 1 centered at 1, depicted in the figure.<ref>{{harvnb|Butcher|2003|p=70}}</ref> This includes the whole left half of the complex plane, making it suitable for the solution of [[stiff equation]]s.<ref>{{harvnb|Butcher|2003|p=71}}</ref> In fact, the backward Euler method is even [[L-stability|L-stable]].
The region for a discrete '''stable''' system by Backward Euler Method is a circle with radius 0.5 which is located at (0.5, 0) in the z-plane.<ref>Wai-Kai Chen, Ed., Analog and VLSI Circuits The Circuits and Filters Handbook, 3rd ed. Chicago, USA: CRC Press, 2009.</ref>
== Extensions and modifications ==
The backward Euler method is a variant of the (forward) [[Euler method]]. Other variants are the [[semi-implicit Euler method]] and the [[exponential Euler method]].
The backward Euler method can be seen as a [[Runge–Kutta method]] with one stage, described by the Butcher tableau:
:<math>
\begin{array}{c|c}
1 & 1 \\
\hline
& 1 \\
\end{array}
</math>
The method can also be seen as a [[linear multistep method]] with one step. It is the first method of the family of [[Adams–Moulton method]]s, and also of the family of [[backward differentiation formula]]s.
==See also==
*[[Crank–Nicolson method]]
== Notes ==
{{reflist}}
== References ==
* {{Citation | last1=Butcher | first1=John C. | author1-link=John C. Butcher | title=Numerical Methods for Ordinary Differential Equations | publisher=[[John Wiley & Sons]] | ___location=New York | isbn=978-0-471-96758-3 | year=2003}}.
{{Numerical integrators}}
[[Category:Numerical differential equations]]
[[Category:Runge–Kutta methods]]
| |||