Explicit and implicit methods: Difference between revisions

Revision as of 02:24, 8 January 2006

Latest revision as of 20:31, 4 January 2025

(100 intermediate revisions by 63 users not shown)

Line 1:

{{Short description|Approaches for approximating solutions to differential equations}}

In [[mathematics]] and applications, '''explicit and implicit methods''' are approaches to [[computer simulation|simulate]] [[physics|physical]] [[process]]es, or to put it mathematically, they are [[numerical analysis|numerical methods]] for solving time-variable [[ordinary differential equation|ordinary]] and [[partial differential equation]]s.

{{more citations needed|date=December 2009}}

'''Explicit and implicit methods''' are approaches used in [[numerical analysis]] for obtaining numerical approximations to the solutions of time-dependent [[ordinary differential equation|ordinary]] and [[partial differential equation]]s, as is required in [[computer simulation]]s of [[Process (science)|physical processes]]. ''Explicit methods'' calculate the state of a system at nexta instance inlater time usingfrom the state of the system at the current time, while an ''implicit methodmethods'' findsfind a itsolution by solving an equation involving both the current system state andof the futuresystem one.and Tothe putlater it inone. symbolsMathematically, if <math>Y(t)</math> is the current system state and <math>Y(t+\Delta t)</math> is the state at the next instance inlater time (<math>\Delta t</math> is a small time step), then, for an explicit method

: <math>Y(t+\Delta t) = F(Y(t))\,</math>

while for an implicit method one solves an equation

: <math>G\Big(Y(t), Y(t+\Delta t)\Big)=0 \quad\quadqquad (1)\,</math>

to find <math>Y(t+\Delta t).</math>

== Computation ==

It is immediate then that implicitImplicit methods require an extra computation (solving the above equation), and they can also be much harder to implement. The reason one uses implicitImplicit methods isare that forused greatbecause many problems (calledarising in practice are [[stiffStiff problemequation|stiff]]s), usingfor which the use of an explicit method requires extremelyimpractically small time steps <math>\Delta t</math> forto keep the error ofin the methodresult to not explode to infinitybounded (see [[numerical stability]]). For such problems, andto thenachieve itgiven isaccuracy, it takes much less computational time to use an implicit method with larger time steps, even taking into account that one needs to solve an equation of the form (1) at each time step. AsThat suchsaid, thewhether choiceone betweenshould whichuse methodan toexplicit useor implicit method depends onupon the specific problem atto hand.be solved.

Since the implicit method cannot be carried out for each kind of differential operator, it is sometimes advisable to make use of the so called operator splitting method, which means that the differential operator is rewritten as the sum of two complementary operators

==Illustration using the forward and backward Euler methods==

:<math>Y(t+\Delta t) = F(Y(t+\Delta t))+G(Y(t)),\,</math>

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,<ref>U.M. Ascher, S.J. Ruuth, R.J. Spiteri: ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.1525&rep=rep1&type=pdf Implicit-Explicit Runge-Kutta Methods for Time-Dependent Partial Differential Equations]'', Appl Numer Math, vol. 25(2-3), 1997</ref><ref>L.Pareschi, G.Russo: ''[https://www.researchgate.net/profile/Lorenzo_Pareschi/publication/230865813_Implicit-Explicit_Runge-Kutta_schemes_for_stiff_systems_of_differential_equations/links/0046352a03ba3ee92a000000.pdf Implicit-Explicit Runge-Kutta schemes for stiff systems of differential equations]'', Recent Trends in Numerical Analysis, Vol. 3, 269-289, 2000</ref><ref>Sebastiano Boscarino, Lorenzo Pareschi, and Giovanni Russo: ''Implicit-Explicit Methods for Evolutionary Partial Differential Equations'', SIAM, ISBN 978-1-61197-819-3 (2024).</ref>).

==Illustration using the forward and backward Euler methods==

Consider the [[ordinary differential equation]]

: <math>\frac{dy}{dt} = -y^2, \ yt\in [0, a]\quad \quad (2)</math>

with the initial condition <math>y(0)=1.</math> Consider a grid <math>t_k=ka/a\frac{k}{n}</math> for 0&lenbsp;≤&nbsp;''k''&lenbsp;≤&nbsp;''n'', that is, the time step is <math>\Delta t=a/n,</math> and denote <math>y_k=y(t_k)</math> for each <math>k</math>. [[Discretization|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:

[[Discretization|Discretize]] this equation using the simplest explicit and implicit methods, which are the ''backward Euler'' and ''forward Euler '' methods (see [[ordinary differential equation]]s). The forward Euler method

[[File:Result of applying integration schemes.png|thumb|The result of applying different integration methods to the ODE: <math> y'=-y^2, \; t\in[0, 5], \; y_0=1 </math> with <math>\Delta t = 5/10</math>.]]

:<math>\frac{y_{k+1}-y_k}{\Delta t} = - y_k^2</math>

The forward [[Euler method]]

:<math>\left(\frac{dy}{dt}\right)_k \approx \frac{y_{k+1}-y_k}{\Delta t} = - y_k^2</math>

yields

: <math>y_{k+1}=y_k-\Delta t y_k^2 \quad \quad \quad(3)\, </math>

for each <math>k=0, 1, \dots, n,.</math> whileThis withis thean backwardexplicit Eulerformula methodfor <math>y_{k+1}</math>.

;Backward Euler method:

With the [[backward Euler method]]

:<math>\frac{y_{k+1}-y_k}{\Delta t} = - y_{k+1}^2</math>

one finds the implicit equation

: <math>y_{k+1}+\Delta t y_{k+1}^2=y_k</math>

for <math>y_{k+1}</math>. (compare this with formula (3) where <math>y_{k+1}</math> was given explicitly rather than as an unknown in an equation).

This is a [[quadratic equation]], having one negative and one positive [[Root of a function|root]]. The positive root is picked because in the original equation the initial condition is positive, and then <math>y</math> at the next time step is given by

: <math>y_{k+1}=\frac{-1+\sqrt{1+4y_k4\Delta t y_k}}{42 \Delta t}. \quad \quad (4)</math>

(compare this with formula (3)).

In the vast majority of cases, the equation to be solved forwhen using an implicit scheme is much more complicated than a quadratic equation, and no exactanalytical solution exists. Then one uses [[root-finding algorithm]]s, such as [[Newton's method]], to find the numerical solution.

;Crank-Nicolson method:

With the [[Crank-Nicolson method]]

:<math>\frac{y_{k+1}-y_k}{\Delta t} = -\frac{1}{2}y_{k+1}^2 -\frac{1}{2}y_{k}^2</math>

one finds the implicit equation

: <math>y_{k+1}+\frac{1}{2}{\Delta t} y^{2}_{k+1} = y_k - \frac{1}{2}\Delta t y_{k}^2</math>

for <math>y_{k+1}</math> (compare this with formula (3) where <math>y_{k+1}</math> was given explicitly rather than as an unknown in an equation). This can be numerically solved using [[root-finding algorithm]]s, such as [[Newton's method]], to obtain <math>y_{k+1}</math>.

Crank-Nicolson can be viewed as a form of more general IMEX (''Im''plicit-''Ex''plicit) schemes.

;Forward-Backward Euler method:

[[File:Comparison_between_Foward-Backward-Euler_and_Foward-Euler.png|thumb|400px|The result of applying both the Forward Euler method and the Forward-Backward Euler method for <math>a = 5</math> and <math>n = 30</math>.]]

In order to apply the IMEX-scheme, consider a slightly different differential equation:

: <math>\frac{dy}{dt} = y-y^2, \ t\in [0, a]\quad \quad (5)</math>

It follows that

: <math>\left(\frac{dy}{dt}\right)_k \approx y_{k+1}-y_{k}^2, \ t\in [0, a]</math>

and therefore

: <math>y_{k+1}=\frac{y_k(1-y_k\Delta t)}{1-\Delta t} \quad\quad(6)</math>

for each <math>k=0, 1, \dots, n.</math>

==See also==

* [[Courant–Friedrichs–Lewy condition]]

* [[SIMPLE algorithm]], a semi-implicit method for pressure-linked equations

==Sources==

In the vast majority of cases the equation to be solved for is much more complicated than a quadratic equation, and no exact solution exists. Then one uses [[root-finding algorithm]]s, such as [[Newton's method]].

{{reflist}}

{{DEFAULTSORT:Explicit And Implicit Methods}}

{{math-stub}}

[[Category:Numerical analysis]] [[Category:Ordinary differential equations]] [[Category:Partial differential equations]]