Backward Euler method: Difference between revisions

Revision as of 23:18, 15 December 2011

Revision as of 12:03, 24 March 2012

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 method 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 order one and is [[A-stability|A-stable]].

#REDIRECT [[Numerical methods for ordinary differential equations]]

== Description ==

Consider the [[ordinary differential equation]] <math> y' = f(t,y) </math> with initial value <math> y(t_0) = y_0. </math> 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 latter uses <math> f(t_k, y_k) </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. Sometimes, this can be done by [[fixed-point iteration]]:

:<math> y_{k+1}^{[0]} = y_k, \quad y_{k+1}^{[i+1]} = y_k + h f(t_{k+1}^{[i]}, 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> y' = f(t,y) </math> from <math> t_k </math> to <math> t_{k+1} = t_k + h </math> yields

: <math> y(t_{k+1}) - y(t_k) = h \int_{t_k}^{t_{k+1}} f(\tau, y(\tau)) \,\mathrm{d}\tau. </math>

Now approximate the integral on the right by the right-hand [[rectangle method]] (with one rectangle):

: <math> y(t_{k+1}) - y(t_k) \approx h f(t_{k+1}, y(t_{k+1})) \,\mathrm{d}\tau. </math>

Finally, use that <math> y_k </math> is supposed to approximate <math> y(t_k) </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 backward Euler method has order one. It is [[A-stability|A-stable]] and even [[L-stability|L-stable]], making it suitable for the solution of [[stiff equation]]s.

== 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 backward Euler 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.

== 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}}

#REDIRECT [[Category:Numerical methods for ordinary differential equations]]

[[Category:Runge–Kutta methods]]