HOME

TheInfoList



OR:

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 ...
: \frac = f(t,y) with initial value y(t_0) = y_0. Here the function f and the initial data t_0 and y_0 are known; the function y depends on the real variable t and is unknown. A numerical method produces a sequence y_0, y_1, y_2, \ldots such that y_k approximates y(t_0+kh) , where h is called the step size. The backward Euler method computes the approximations using : y_ = y_k + h f(t_, y_). This differs from the (forward) Euler method in that the forward method uses f(t_k, y_k) in place of f(t_, y_). The backward Euler method is an implicit method: the new approximation y_ appears on both sides of the equation, and thus the method needs to solve an algebraic equation for the unknown y_ . 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 ...
: : y_^ = y_k, \quad y_^ = y_k + h f(t_, y_^). If this sequence converges (within a given tolerance), then the method takes its limit as the new approximation y_ . 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 \frac = f(t,y) from t_n to t_ = t_n + h yields : y(t_) - y(t_n) = \int_^ f(t, y(t)) \,\mathrmt. 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): : y(t_) - y(t_n) \approx h f(t_, y(t_)). Finally, use that y_n is supposed to approximate y(t_n) 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 O(h^2) , 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 t is O(h^2) . It means that this method has order one. In general, a method with O(h^) 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: : \begin 1 & 1 \\ \hline & 1 \\ \end 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