Explicit and implicit methods

Explicit and implicit methods are approaches used in numerical analysis for obtaining numerical approximations to the solutions of ordinary and partial differential equations, as is required in computer simulations of physical processes. Explicit methods calculate the state of a system at a later time from the state of the system at the current time, while implicit methods find a solution by solving an equation involving both the current state of the system and the later one. Mathematically, if Y(t) is the current system state and Y(t+\Delta t) is the state at the later time ( \Delta t is a small time step), then, for an explicit method : Y(t+\Delta t) = F(Y(t))\, while for an implicit method one solves an equation : G\Big(Y(t), Y(t+\Delta t)\Big)=0 \qquad (1)\, to find Y(t+\Delta t).

Explicit and implicit methods are approaches used in numerical analysis for obtaining numerical approximations to the solutions of ordinary and partial differential equations, as is required in computer simulations of physical processes. Explicit methods calculate the state of a system at a later time from the state of the system at the current time, while implicit methods find a solution by solving an equation involving both the current state of the system and the later one. Mathematically, if Y(t) is the current system state and Y(t+\Delta t) is the state at the later time ( \Delta t is a small time step), then, for an explicit method Y(t+\Delta t) = F(Y(t))\, while for an implicit method one solves an equation G\Big(Y(t), Y(t+\Delta t)\Big)=0 \qquad (1)\, to find Y(t+\Delta t). Y(t+\Delta t) = F(Y(t+\Delta t))+G(Y(t)),\, while one is treated explicitly and the other implicitly. For usual applications the implicit term is chosen to be linear while the explicit term can be nonlinear. This combination of the former method is called Implicit-Explicit Method (short IMEX, ).

Illustration using the forward and backward Euler methods

Consider the ordinary differential equation \frac{dy}{dt} = -y^2, \ t\in [0, a]\quad \quad (2) with the initial condition y(0)=1. This problem has the exact solution y = \frac{1}{t+1} , which usually cannot be written down for problems encountered in practice, but in this case allows a comparison with the numerical solutions. Consider a grid t_k=a\frac{k}{n} for 0 ≤ k ≤ n, that is, the time step is \Delta t=a/n, and denote y_k=y(t_k) for each k . Discretize this equation using the simplest explicit and implicit methods, which are the forward Euler and backward Euler methods (see numerical ordinary differential equations) and compare the obtained schemes. Forward Euler method: [[File:Result of applying integration schemes.png|thumb|The result of applying different integration methods to the ODE: y'=-y^2, \; t\in[0, 5], \; y_0=1 with \Delta t = 5/10 .]] The forward Euler method \left(\frac{dy}{dt}\right)_k \approx \frac{y_{k+1}-y_k}{\Delta t} = - y_k^2 yields y_{k+1}=y_k-\Delta t y_k^2 \quad \quad \quad(3)\, for each k=0, 1, \dots, n. This is an explicit formula for y_{k+1} . Backward Euler method: With the backward Euler method \frac{y_{k+1}-y_k}{\Delta t} = - y_{k+1}^2 one finds the implicit equation y_{k+1}+\Delta t y_{k+1}^2=y_k for y_{k+1} (compare this with formula (3) where y_{k+1} was given explicitly rather than as an unknown in an equation). This is a quadratic equation, having one negative and one positive root. The positive root is picked because in the original equation the initial condition is positive, and then y at the next time step is given by y_{k+1}=\frac{-1+\sqrt{1+4\Delta t y_k}}{2 \Delta t}. \quad \quad (4) In the vast majority of cases, the equation to be solved when using an implicit scheme is much more complicated than a quadratic equation, and no analytical solution exists. Then one uses root-finding algorithms, such as Newton's method, to find the numerical solution. Crank-Nicolson method: The Crank-Nicolson method, also known as the trapezoidal rule, can be thought of as an average of the forward and backward Euler methods. For the differential equation considered above, this gives \frac{y_{k+1}-y_k}{\Delta t} = -\frac{1}{2}y_{k+1}^2 -\frac{1}{2}y_{k}^2 leading to the implicit equation y_{k+1}+\frac{1}{2}{\Delta t} y^{2}_{k+1} = y_k - \frac{1}{2}\Delta t y_{k}^2 for y_{k+1} (compare this with formula (3) where y_{k+1} was given explicitly rather than as an unknown in an equation). This can be numerically solved using root-finding algorithms, such as Newton's method, to obtain y_{k+1} . The advantage of this method is its improved accuracy (see diagram above). Both Euler methods are first order, but the trapezoidal method is second order. IMEX methods: Because of the difficulty of solving implicit equations, some methods use an implicit method for linear terms and an explicit method for nonlinear terms. These are called IMEX (Implicit-Explicit) schemes. To illustrate the idea of IMEX schemes, consider a slightly different differential equation: \frac{dy}{dt} = y-y^2, \ t\in [0, a]\quad \quad (5) Using implicit Euler for the linear term and explicit Euler for the nonlinear term gives \frac{y_{k+1}-y_k}{\Delta t}\approx y_{k+1}-y_{k}^2, \ t\in [0, a]. This equation is linear in y_{k+1} so it can be solved to give y_{k+1}=\frac{y_k(1-y_k\Delta t)}{1-\Delta t} \quad\quad(6) for each k=0, 1, \dots, n. This method is sometimes called the Forward-Backward Euler method (see diagram).

See also

Courant–Friedrichs–Lewy condition SIMPLE algorithm, a semi-implicit method for pressure-linked equations

Sources

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367510460 under CC BY-SA 4.0; modifications have been made.