In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
and
scientific computing
Computational science, also known as scientific computing or scientific computation (SC), is a field in mathematics that uses advanced computing capabilities to understand and solve complex problems. It is an area of science that spans many disc ...
, the backward Euler method (or implicit Euler method) is one of the most basic
numerical methods for the solution of ordinary differential equations. It is similar to the (standard)
Euler method
In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit met ...
, but differs in that it is an
implicit method
Explicit and implicit methods are approaches used in numerical analysis for obtaining numerical approximations to the solutions of time-dependent ordinary and partial differential equations, as is required in computer simulations of physical p ...
. The backward Euler method has error of order one in time.
Description
Consider the
ordinary differential equation
In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast w ...
:
with initial value
Here the function
and the initial data
and
are known; the function
depends on the real variable
and is unknown. A numerical method produces a sequence
such that
approximates
, where
is called the step size.
The backward Euler method computes the approximations using
:
This differs from the (forward) Euler method in that the forward method uses
in place of
.
The backward Euler method is an implicit method: the new approximation
appears on both sides of the equation, and thus the method needs to solve an algebraic equation for the unknown
. For non-
stiff problems, this can be done with
fixed-point iteration
In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.
More specifically, given a function f defined on the real numbers with real values and given a point x_0 in the domain of f, the fixed-point iterat ...
:
:
If this sequence converges (within a given tolerance), then the method takes its limit as the new approximation
.
Alternatively, one can use (some modification of) the
Newton–Raphson method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valu ...
to solve the algebraic equation.
Derivation
Integrating the differential equation
from
to
yields
:
Now approximate the integral on the right by the right-hand
rectangle method
In mathematics, a Riemann sum is a certain kind of approximation of an integral by a finite sum. It is named after nineteenth century German mathematician Bernhard Riemann. One very common application is approximating the area of functions or lin ...
(with one rectangle):
:
Finally, use that
is supposed to approximate
and the formula for the backward Euler method follows.
The same reasoning leads to the (standard) Euler method if the left-hand rectangle rule is used instead of the right-hand one.
Analysis
The
local truncation error
Truncation errors in numerical integration are of two kinds:
* ''local truncation errors'' – the error caused by one iteration, and
* ''global truncation errors'' – the cumulative error caused by many iterations.
Definitions
Suppose we have ...
(defined as the error made in one step) of the backward Euler Method is
, using the
big O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
. The error at a specific time
is
. It means that this method has order one. In general, a method with
LTE (local truncation error) is said to be of ''k''th order.
The
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. This includes the whole left half of the complex plane, making it suitable for the solution of
stiff equation
In mathematics, a stiff equation is a differential equation for which certain numerical methods for solving the equation are numerically unstable, unless the step size is taken to be extremely small. It has proven difficult to formulate a precise ...
s. In fact, the backward Euler method is even
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.
[Wai-Kai Chen, Ed., Analog and VLSI Circuits The Circuits and Filters Handbook, 3rd ed. Chicago, USA: CRC Press, 2009.]
Extensions and modifications
The backward Euler method is a variant of the (forward)
Euler method
In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit met ...
. Other variants are the
semi-implicit Euler method In mathematics, the semi-implicit Euler method, also called symplectic Euler, semi-explicit Euler, Euler–Cromer, and Newton–Størmer–Verlet (NSV), is a modification of the Euler method for solving Hamilton's equations, a system of ordinary d ...
and the
exponential Euler method
Numerical methods for ordinary differential equations are methods used to find numerical approximations to the solutions of ordinary differential equations (ODEs). Their use is also known as "numerical integration", although this term can also ...
.
The backward Euler method can be seen as a
Runge–Kutta method with one stage, described by the Butcher tableau:
:
The method can also be seen as a
linear multistep method
Linear multistep methods are used for the numerical solution of ordinary differential equations. Conceptually, a numerical method starts from an initial point and then takes a short step forward in time to find the next solution point. The proce ...
with one step. It is the first method of the family of
Adams–Moulton method
Linear multistep methods are used for the numerical solution of ordinary differential equations. Conceptually, a numerical method starts from an initial point and then takes a short step forward in time to find the next solution point. The proce ...
s, and also of the family of
backward differentiation formula The backward differentiation formula (BDF) is a family of implicit methods for the numerical integration of ordinary differential equations. They are linear multistep methods that, for a given function and time, approximate the derivative of that f ...
s.
See also
*
Crank–Nicolson method
In numerical analysis, the Crank–Nicolson method is a finite difference method used for numerically solving the heat equation and similar partial differential equations. It is a second-order method in time. It is implicit in time, can be wri ...
Notes
References
* .
{{Numerical integrators
Numerical differential equations
Runge–Kutta methods