View source for Lax–Friedrichs method

The '''Lax–Friedrichs method''', named after [[Peter Lax]] and [[Kurt O. Friedrichs]], is a [[numerical analysis|numerical]] method for the solution of [[hyperbolic partial differential equation]]s based on [[finite difference]]s.  The method can be described as the [[FTCS scheme|FTCS (forward in time, centered in space) scheme]] with an [[artificial viscosity]] term of 1/2.  One can view the Lax–Friedrichs method as an alternative to [[Godunov's scheme]], where one avoids solving a [[Riemann problem]] at each cell interface, at the expense of adding artificial viscosity.

==Illustration for a Linear Problem==
Consider a one-dimensional, linear hyperbolic partial differential equation for <math>u(x,t)</math> of the form:

: <math> u_t + au_x = 0\,</math>

on the domain

: <math> b \leq x \leq c,\; 0 \leq t \leq d</math>

with initial condition

: <math>u(x,0) = u_0(x)\,</math>

and the boundary conditions

: <math>u(b,t) = u_b(t)\,</math> 
: <math>u(c,t) = u_c(t).\,</math>

If one discretizes the domain <math>(b, c) \times (0, d)</math> to a grid with equally spaced points with a spacing of <math>\Delta x</math> in the <math>x</math>-direction and <math>\Delta t</math> in the <math>t</math>-direction, we define 

: <math>u_i^n = u(x_i, t^n) \text{ with } x_i = b + i\,\Delta x ,\, t^n = n\,\Delta t \text{ for } i = 0,\ldots,N ,\, n = 0,\ldots,M,</math> 

where 

: <math>N = \frac{c - b}{\Delta x} ,\, M = \frac{d}{\Delta t}</math> 

are integers representing the number of grid intervals.  Then the Lax–Friedrichs method for solving the above partial differential equation is given by:

: <math>\frac{u_i^{n+1} - \frac{1}{2}(u_{i+1}^n + u_{i-1}^n)}{\Delta t} + a\frac{u_{i+1}^n - u_{i-1}^n}{2\,\Delta x} = 0</math>

Or, rewriting this to solve for the unknown <math>u_i^{n+1},</math>

: <math> u_i^{n+1} = \frac{1}{2}(u_{i+1}^n + u_{i-1}^n) - a\frac{\Delta t}{2\,\Delta x}(u_{i+1}^n - u_{i-1}^n)\,</math>

Where the initial values and boundary nodes are taken from

: <math>u_i^0 = u_0(x_i)</math>
: <math>u_0^n = u_b(t^n)</math>
: <math>u_N^n = u_c(t^n).</math>

== Extensions to Nonlinear Problems ==

A nonlinear hyperbolic conservation law is defined through a flux function <math> f </math>:

: <math> u_t + ( f(u) )_x = 0. </math>

In the case of <math> f(u) = a u </math>, we end up with a scalar linear problem.  Note that in general, <math> u </math> is a vector with <math>m</math> equations in it.
The generalization of the Lax-Friedrichs method to nonlinear systems takes the form<ref>LeVeque, Randall J. ''Numerical Methods for Conservation Laws", Birkhauser Verlag, 1992, p. 125.</ref>

: <math>  u_i^{n+1} = \frac{1}{2}(u_{i+1}^n + u_{i-1}^n) - \frac{\Delta t}{2\,\Delta x}( f( u_{i+1}^n ) - f( u_{i-1}^n ) ).</math>

This method is conservative and first order accurate, hence quite dissipative.  It can, however be used as a building block for building high-order numerical schemes for solving hyperbolic partial differential equations, much like Euler time steps can be used as a building block for creating high-order numerical integrators for ordinary differential equations.

We note that this method can be written in conservation form:

:<math> u_i^{n+1} = u^n_i - \frac{\Delta t}{ \Delta x} \left( \hat{f}^n_{i+1/2} - \hat{f}^n_{i-1/2} \right), </math>

where

:<math> \hat{f}^n_{i-1/2} = \frac{1}{2} \left( f_{i-1} + f_{i} \right) - \frac{ \Delta x}{ 2 \Delta t  } \left( u^n_{i} - u^n_{i-1} \right). </math>

Without the extra terms <math> u^n_i </math> and <math> u^n_{i-1} </math>  in the discrete flux, <math> \hat{f}^n_{i-1/2} </math>, one ends up with the [[FTCS scheme]], which is well known to be unconditionally unstable for hyperbolic problems.

==Stability and accuracy==
[[File:LF-Initial.png|thumb | 200px | Example problem initial condition]]
[[File:LF-Solution.png|thumb| 200px | Lax-Friedrichs solution]]

This method is [[explicit method|explicit]] and [[Orders of approximation|first order accurate in time]] and [[Orders of approximation|first order accurate in space]] (<math> O(\Delta t) + O(\frac{\Delta x^2}{\Delta t})) </math>  provided <math>u_0(x),\, u_b(t),\, u_c(t)</math> are sufficiently-smooth functions.   Under these conditions, the method is [[numerical stability|stable]] if and only if the following condition is satisfied:

:<math> \left| a\frac{\Delta t}{\Delta x} \right| \leq 1. </math>

(A [[von Neumann stability analysis]] can show the necessity of this stability condition.)  The Lax–Friedrichs method is classified as having second-order [[dissipation]] and third order [[dispersion relation|dispersion]] {{harv|Chu|1978|loc=pg. 304}}. For functions that have [[discontinuity (mathematics)|discontinuities]], the scheme displays strong dissipation and dispersion {{harv|Thomas|1995|loc=§7.8}}; see figures at right.

==References==

{{reflist}}
* {{Citation | last1=DuChateau | first1=Paul | last2=Zachmann | first2=David | title=Applied Partial Differential Equations | publisher=[[Dover Publications]] | location=New York | isbn=978-0-486-41976-3 | year=2002 | url-access=registration | url=https://archive.org/details/appliedpartialdi00duch }}.
* {{Citation | last1=Thomas | first1=J. W. | title=Numerical Partial Differential Equations: Finite Difference Methods | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Texts in Applied Mathematics | isbn=978-0-387-97999-1 | year=1995 | volume=22}}.
* {{Citation | last1=Chu| first1=C. K. | title=Numerical Methods in Fluid Mechanics | publisher=[[Academic Press]] | location=New York | series=Advances in Applied Mechanics | isbn=978-0-12-002018-8 | year=1978 | volume=18}}.
*{{Citation | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press |  publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 10.1.2. Lax Method | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=1034}}

{{Numerical PDE}}

{{DEFAULTSORT:Lax-Friedrichs method}}
[[Category:Numerical differential equations]]
[[Category:Computational fluid dynamics]]