View source for Courant–Friedrichs–Lewy condition

{{Short description|Mathematical condition for convergence}}
In [[Mathematics|mathematics]], the '''convergence condition by Courant–Friedrichs–Lewy''' is a necessary condition for convergence while solving certain [[Partial differential equation|partial differential equation]]s (usually [[Hyperbolic partial differential equation|hyperbolic PDE]]s) numerically. It arises in the [[Numerical analysis|numerical analysis]] of explicit time integration schemes, when these are used for the numerical solution. As a consequence, the time step must be less than a certain upper bound, given a fixed spatial increment, in many explicit time-marching [[Computer simulation|computer simulation]]s;  otherwise, the simulation produces incorrect or [[Numerical stability|unstable]] results. The condition is named after [[Biography:Richard Courant|Richard Courant]], Kurt Friedrichs, and [[Biography:Hans Lewy|Hans Lewy]] who described it in their 1928 paper.<ref>See reference {{harvnb|Courant|Friedrichs|Lewy|1928}}. There exists also an [[Social:English language|English]] [[Philosophy:Translation|translation]] of the 1928 [[Social:German language|German]] original: see references {{harvnb|Courant|Friedrichs|Lewy|1956}} and {{harvnb|Courant|Friedrichs|Lewy|1967}}.</ref>

==Heuristic description==
The principle behind the condition is that, for example, if a wave is moving across a discrete spatial grid and we want to compute its [[Physics:Amplitude|amplitude]] at discrete time steps of equal duration,<ref>This situation commonly occurs when a [[Hyperbolic partial differential equation|hyperbolic partial differential operator]] has been [[Approximation theory|approximated]] by a [[Finite difference|finite difference equation]], which is then solved by [[Numerical linear algebra|numerical linear algebra]] methods.</ref> then this duration must be less than the time for the wave to travel to adjacent grid points. As a corollary, when the grid point separation is reduced, the upper limit for the time step also decreases. In essence, the numerical domain of dependence of any point in space and time (as determined by initial conditions and the parameters of the approximation scheme) must include the analytical domain of dependence (wherein the initial conditions have an effect on the exact value of the solution at that point) to assure that the scheme can access the information required to form the solution.

==Statement==
To make a reasonably formally precise statement of the condition, it is necessary to define the following quantities:
*''Spatial coordinate'': one of the coordinates of the physical space in which the problem is posed
*''Spatial dimension of the problem'': the number <math>n</math> of spatial dimensions, i.e., the number of spatial coordinates of the physical space where the problem is posed. Typical values are <math>n=1</math>, <math>n=2</math> and <math>n=3</math>.
*''Time'': the coordinate, acting as a [[Parameter|parameter]], which describes the evolution of the system, distinct from the spatial coordinates
The spatial coordinates and the time are discrete-valued independent [[Variable (mathematics)|variables]], which are placed at regular distances called the ''interval length''<ref>This quantity is not necessarily the same for each spatial variable, as it is shown in "[[Courant–Friedrichs–Lewy condition#The two and general ''n''–dimensional case|The two and general ''n''–dimensional case]]" section of this entry: it can be selected to somewhat relax the condition.</ref>  and the ''time step'', respectively. Using these names, the CFL condition relates the length of the time step to a function of the interval lengths of each spatial coordinate and of the maximum speed that information can travel in the physical space.

Operatively, the CFL condition is commonly prescribed for those terms of the finite-difference approximation of general [[Partial differential equation|partial differential equation]]s that model the [[Advection|advection]] phenomenon.<ref>Precisely, this is the hyperbolic part of the PDE under analysis.</ref>

===The one-dimensional case===
For the one-dimensional case, the continuous-time model equation (that is usually solved for <math>w</math>) is:
: <math>\frac {\partial w} {\partial t} = u \frac {\partial w} {\partial x}. </math>

The CFL condition then has the following form:
: <math>C = \frac {u\,\Delta t} {\Delta x} \leq C_\max </math>

where the dimensionless number <math>C</math> is called the '''Courant number''',

*<math>u</math> is the [[Magnitude (mathematics)|magnitude]] of the velocity (whose [[Dimensional analysis#Definition|dimension]] is length/time)
*<math>\Delta t</math> is the time step (whose [[Dimensional analysis#Definition|dimension]] is time)
*<math>\Delta x</math> is the length interval (whose [[Dimensional analysis#Definition|dimension]] is length).

The value of <math>C_\max</math> changes with the method used to solve the discretised equation, especially depending on whether the method is [[Explicit and implicit methods|explicit or implicit]]. If an explicit (time-marching) solver is used then typically <math>C_\max = 1</math>. Implicit (matrix) solvers are usually less sensitive to numerical instability and so larger values of <math>C_\max</math> may be tolerated.

===The two and general ''n''-dimensional case===
In the two-dimensional case, the CFL condition becomes

:<math>C = \frac {u_ x\,\Delta t}{\Delta x} + \frac {u_ y\,\Delta t}{\Delta y} \leq C_\max </math>

with the obvious meanings of the symbols involved. By analogy with the two-dimensional case, the general CFL condition for the <math>n</math>-dimensional case is the following one:

:<math>C = \Delta t \left( \sum_{i=1}^n\frac{u_{i}}{\Delta x_i} \right) \leq C_\max. </math>

The interval length is not required to be the same for each spatial variable <math>\Delta x_i, i = 1, \ldots , n</math>. This "[[Chemistry:Degrees of freedom (physics and chemistry)|degree of freedom]]" can be used to somewhat optimize the value of the time step for a particular problem, by varying the values of the different interval to keep it not too small.

== Notes ==
{{reflist|30em}}

== References ==
*{{Citation
  | last1 = Courant
  | first1 = R.
  | last2 = Friedrichs
  | first2 = K.
  | last3 = Lewy
  | first3 = H.
  | title = Über die partiellen Differenzengleichungen der mathematischen Physik
  | journal = [[Mathematische Annalen]]
  | volume = 100
  | issue = 1
  | pages = 32–74
  | year = 1928
  | language = de
  | url = http://resolver.sub.uni-goettingen.de/purl?GDZPPN002272636
  | doi = 10.1007/BF01448839
  | jfm = 54.0486.01
  | mr = 1512478
 |bibcode = 1928MatAn.100...32C | s2cid = 120760331
 }}.
*{{Citation
  | last1 = Courant
  | first1 = R.
  | last2 = Friedrichs
  | first2 = K.
  | last3 = Lewy
  | first3 = H.
  | title = On the partial difference equations of mathematical physics
  | place = New York
  | publisher = AEC Computing and Applied Mathematics Centre – [[Organization:Courant Institute of Mathematical Sciences|Courant Institute of Mathematical Sciences]]
  | series = AEC Research and Development Report
  | volume = NYO-7689
  | orig-year = 1928
  |date=September 1956
  | pages = V + 76
  | url = https://archive.org/details/onpartialdiffere00cour
  | archive-url = https://archive.org/stream/onpartialdiffere00cour#page/n0/mode/2up
  | archive-date = October 23, 2008
}}.: translated from the [[Social:German language|German]] by Phyllis Fox. This is an earlier version of the paper {{harvnb|Courant|Friedrichs|Lewy|1967}}, circulated as a research report.
*{{Citation
  | last1 = Courant
  | first1 = R.
  | last2 = Friedrichs
  | first2 = K.
  | last3 = Lewy
  | first3 = H.
  | title = On the partial difference equations of mathematical physics
  | journal = IBM Journal of Research and Development
  | volume = 11
  | issue = 2
  | pages = 215–234
  | orig-year = 1928
  |date=March 1967
  | url = http://domino.research.ibm.com/tchjr/journalindex.nsf/a3807c5b4823c53f85256561006324be/769774a3c9f3685f85256bfa00683f8a!OpenDocument
  | mr = 0213764
  | zbl = 0145.40402
|bibcode = 1967IBMJ...11..215C |doi = 10.1147/rd.112.0215 }}. A freely downloadable copy can be found [http://www.stanford.edu/class/cme324/classics/courant-friedrichs-lewy.pdf here].

* Carlos A. de Moura and Carlos S. Kubrusly (Eds.): "The Courant-Friedrichs-Lewy (CFL) Condition: 80 Years After Its Discovery", Birkhauser, ISBN 978-0-8176-8393-1 (2013).

== External links ==
*{{springer
 | title=Courant–Friedrichs–Lewy condition
 | id= C/c026760
 | last= Bakhvalov
 | first= N. S.
}}
*{{MathWorld |title=Courant-Friedrichs-Lewy Condition |id=Courant-Friedrichs-LewyCondition}}

{{DEFAULTSORT:Courant-Friedrichs-Lewy condition}}
[[Category:Numerical differential equations]]
[[Category:Computational fluid dynamics]]

{{Sourceattribution|Courant–Friedrichs–Lewy condition}}