Lax–Friedrichs method

The Lax–Friedrichs method, named after Peter Lax and Kurt O. Friedrichs, is a numerical method for the solution of hyperbolic partial differential equations based on finite differences. The method can be described as the FTCS (forward in time, centered in space) scheme with a numerical dissipation 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 u ( x , t ) {\displaystyle u(x,t)} of the form:

u t + a u x = 0 {\displaystyle u_{t}+au_{x}=0}
on the domain
b ≤ x ≤ c , 0 ≤ t ≤ d {\displaystyle b\leq x\leq c,\;0\leq t\leq d}
with initial condition
u ( x , 0 ) = u 0 ( x ) {\displaystyle u(x,0)=u_{0}(x)\,}
and the boundary conditions
u ( b , t ) = u b ( t ) u ( c , t ) = u c ( t ) . {\displaystyle {\begin{aligned}u(b,t)&=u_{b}(t)\\u(c,t)&=u_{c}(t).\end{aligned}}}

If one discretizes the domain ( b , c ) × ( 0 , d ) {\displaystyle (b,c)\times (0,d)} to a grid with equally spaced points with a spacing of Δ x {\displaystyle \Delta x} in the x {\displaystyle x} -direction and Δ t {\displaystyle \Delta t} in the t {\displaystyle t} -direction, we introduce an approximation u ~ {\displaystyle {\tilde {u}}} of u {\displaystyle u}

u i n = u ~ ( x i , t n )      with      x i = b + i Δ x , t n = n Δ t      for      i = 0 , … , N , n = 0 , … , M , {\displaystyle u_{i}^{n}={\tilde {u}}(x_{i},t^{n})~~{\text{ with }}~~{\begin{array}{l}x_{i}=b+i\,\Delta x,\\t^{n}=n\,\Delta t\end{array}}~~{\text{ for }}~~{\begin{array}{l}i=0,\ldots ,N,\\n=0,\ldots ,M,\end{array}}}
where
N = c − b Δ x , M = d Δ t {\displaystyle N={\frac {c-b}{\Delta x}},\,M={\frac {d}{\Delta t}}}
are integers representing the number of grid intervals. Then the Lax–Friedrichs method to approximate the partial differential equation is given by:
u i n + 1 − 1 2 ( u i + 1 n + u i − 1 n ) Δ t + a u i + 1 n − u i − 1 n 2 Δ x = 0 {\displaystyle {\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}

Or, rewriting this to solve for the unknown u i n + 1 , {\displaystyle u_{i}^{n+1},}

u i n + 1 = 1 2 ( u i + 1 n + u i − 1 n ) − a Δ t 2 Δ x ( u i + 1 n − u i − 1 n ) {\displaystyle u_{i}^{n+1}={\frac {1}{2}}\left(u_{i+1}^{n}+u_{i-1}^{n}\right)-a{\frac {\Delta t}{2\,\Delta x}}\left(u_{i+1}^{n}-u_{i-1}^{n}\right)}

Where the initial values and boundary nodes are taken from

u i 0 = u 0 ( x i ) u 0 n = u b ( t n ) u N n = u c ( t n ) . {\displaystyle {\begin{aligned}u_{i}^{0}&=u_{0}(x_{i})\\u_{0}^{n}&=u_{b}(t^{n})\\u_{N}^{n}&=u_{c}(t^{n}).\end{aligned}}}

Extensions to Nonlinear Problems

A nonlinear hyperbolic conservation law is defined through a flux function f {\displaystyle f} :

u t + ( f ( u ) ) x = 0. {\displaystyle u_{t}+(f(u))_{x}=0.}

In the case of f ( u ) = a u {\displaystyle f(u)=au} , we end up with a scalar linear problem. Note that in general, u {\displaystyle u} is a vector with m {\displaystyle m} equations in it. The generalization of the Lax-Friedrichs method to nonlinear systems takes the form[1]

u i n + 1 = 1 2 ( u i + 1 n + u i − 1 n ) − Δ t 2 Δ x ( f ( u i + 1 n ) − f ( u i − 1 n ) ) . {\displaystyle u_{i}^{n+1}={\frac {1}{2}}\left(u_{i+1}^{n}+u_{i-1}^{n}\right)-{\frac {\Delta t}{2\,\Delta x}}\left(f(u_{i+1}^{n})-f(u_{i-1}^{n})\right).}

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:

u i n + 1 = u i n − Δ t Δ x ( f ^ i + 1 / 2 n − f ^ i − 1 / 2 n ) , {\displaystyle u_{i}^{n+1}=u_{i}^{n}-{\frac {\Delta t}{\Delta x}}\left({\hat {f}}_{i+1/2}^{n}-{\hat {f}}_{i-1/2}^{n}\right),}
where
f ^ i − 1 / 2 n = 1 2 ( f i − 1 + f i ) − Δ x 2 Δ t ( u i n − u i − 1 n ) . {\displaystyle {\hat {f}}_{i-1/2}^{n}={\frac {1}{2}}\left(f_{i-1}+f_{i}\right)-{\frac {\Delta x}{2\Delta t}}\left(u_{i}^{n}-u_{i-1}^{n}\right).}

Without the extra terms u i n {\displaystyle u_{i}^{n}} and u i − 1 n {\displaystyle u_{i-1}^{n}} in the discrete flux, f ^ i − 1 / 2 n {\displaystyle {\hat {f}}_{i-1/2}^{n}} , one ends up with the FTCS scheme, which is well known to be unconditionally unstable for hyperbolic problems.

Stability and accuracy

Example problem initial condition
Lax-Friedrichs solution

This method is explicit and first order accurate in time and first order accurate in space ( O ( Δ t ) + O ( Δ x 2 / Δ t ) ) {\displaystyle O(\Delta t)+O({\Delta x^{2}}/{\Delta t}))} provided u 0 ( x ) , u b ( t ) , u c ( t ) {\displaystyle u_{0}(x),\,u_{b}(t),\,u_{c}(t)} are sufficiently-smooth functions. Under these conditions, the method is stable if and only if the following condition is satisfied:

| a Δ t Δ x | ≤ 1. {\displaystyle \left|a{\frac {\Delta t}{\Delta x}}\right|\leq 1.}

(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.[2] For functions that have discontinuities, the scheme displays strong dissipation and dispersion;[3] see figures at right.

References

  1. ^ LeVeque, Randall J. (1992). Numerical methods for conservation laws. Basel: Birkhäuser Verlag. p. 125. ISBN 978-3-0348-8629-1. OCLC 828775522.
  2. ^ Chu, C. K. (1978), Numerical Methods in Fluid Mechanics, Advances in Applied Mechanics, vol. 18, New York: Academic Press, p. 304, ISBN 978-0-12-002018-8
  3. ^ Thomas, J. W. (1995), Numerical Partial Differential Equations: Finite Difference Methods, Texts in Applied Mathematics, vol. 22, Berlin, New York: Springer-Verlag, §7.8, ISBN 978-0-387-97999-1
  • DuChateau, Paul; Zachmann, David (2002), Applied Partial Differential Equations, New York: Dover Publications, ISBN 978-0-486-41976-3
  • Press, William H; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 20.1.2. Lax Method", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
  • v
  • t
  • e
Finite difference
Parabolic
Hyperbolic
Others
Finite volumeFinite elementMeshless/MeshfreeDomain decompositionOthers