Appendix C — Lax Equivalence Theorem

The Lax Equivalence Theorem is usually phrased roughly as

A numerical scheme converges to the true solution if, and only if, it is consistent and stable.

There are a number of different versions of this theorem. The main result is the Lax-Richtmyer case which holds for linear numerical methods applied to well-posed, linear partial differential equations with periodic boundaries (or infinite domains where the data has compact support). There are extensions (for example, the Lax-Wendroff case) which at least partially lift these restrictions, but well-posedness remains essential and results in the nonlinear case are limited.

We sketch the Lax-Richtmyer case.

As a motivating example, think of the advection equation

\[ \partial_t \phi + v \partial_x \phi = 0 \tag{C.1}\]

with \(v > 0\) constant, approximated by the standard FTBS scheme

\[ \phi^{n+1}_{i} = \phi^{n}_{i} + \frac{v \, \Delta t}{\Delta x} \left( \phi^{n}_{i} - \phi^{n}_{i-1} \right) = \mathcal{L}_{\Delta t} \left( \left\{ \phi^{n}_{i} \right\} \right)_i = \mathcal{L}_{\Delta t} \left( \symbf{\phi}^{n} \right)_i \, . \tag{C.2}\]

We have introduced the operator notation \(\mathcal{L}_{\Delta t}\). The discrete solution at time \(t^n = n \, \Delta t\) is given by the vector \(\symbf{\phi}^n\). The discrete solution at the next timestep, \(\symbf{\phi}^{n+1}\), is given by applying the operator to the solution at the current timestep,

\[ \symbf{\phi}^{n+1} = \mathcal{L}_{\Delta t} \symbf{\phi}^{n}. \tag{C.3}\]

This is therefore a linear map on a vector space, whose vectors are (potential) discrete solutions to the PDE. Note that the map depends only on the timestep \(\Delta x\), as it is assumed that the grid (here \(\Delta x\), but it extends to arbitrary dimensions and unstructured grids) depends directly, if implicitly, on \(\Delta x\).

C.1 Banach spaces

A Banach space is a complete normed vector space. For our purposes, this will be the space of discrete approximations to the PDE. The norm will be some measure of the “size” of the solution, such as the infinity norm

\[ \| \symbf{\phi} \|_\infty = \max_i \phi_i \, , \tag{C.4}\]

or the 2-norm

\[ \| \symbf{\phi} \|_2 = \sum_i \sqrt{ (\phi_i)^2 \, \Delta x } \, . \tag{C.5}\]

This allows us to formally, but abstractly, state our two key conditions and our goal.

C.2 Consistency

A numerical approximation is consistent if it correctly represents the PDE in the continuum limit. Formally, let \(\symbf{\phi}\) be the exact solution to the PDE, sampled onto the discrete grid as appropriate. Also let \(\mathcal{L}\) be the formal operator that evolves the exact solution forward in time. Therefore

\[ \mathcal{L}(T) \symbf{\phi}(0) = \symbf{\phi}(T) \, , \tag{C.6}\]

and

\[ \mathcal{L}(\Delta t) \symbf{\phi}(T) = \symbf{\phi}(T + \Delta t) \, . \tag{C.7}\]

Then the numerical scheme is consistent if

\[ \lim_{\Delta t \to 0} \left\| \left(\mathcal{L}(\Delta t) - \mathcal{L}_{\Delta t} \right) \symbf{\phi}(T) \right\| \to 0 \, . \tag{C.8}\]

For later purposes we write that the scheme is consistent if there exists a constant \(K \in [0, \infty)\) such that

\[ \left\| \left( \mathcal{L}(\Delta t) - \mathcal{L}_{\Delta t} \right) \symbf{\phi}(T) \right\| \le K_{C} \, \Delta t \tag{C.9}\]

and \(K_C\) is independent of \(\Delta t\).

C.3 Stability

A numerical approximation is stable if it does not blow up “too fast”. This needs some care, as it is possible that the exact solution to the PDE grows quickly, even exponentially or instantaneously in special cases. Therefore the most general stability criteria that we can work with is to state that the scheme is stable at time \(T = N \, \Delta t\) if

\[ \left\| \left( \mathcal{L}_{\Delta t} \right)^N \symbf{\phi}(0) \right\| \le K_T \left\| \symbf{\phi}(0) \right\| + D \, \Delta t \, . \tag{C.10}\]

Again, the constants \(K_T, D \in [0, \infty)\) and must be independent of \(\Delta t\) (although they can depend on the finite time \(T\)). The term involving \(K_T\) ensures that the numerical approximation does not grow too fast compared to the true solution, but does allow for bounded growth. The term involving \(D\) allows for purely numerical growth even if the true solution is bounded, but ensures that any such growth converges to zero in the continuum limit.

C.4 Convergence

Our goal, via the Lax Equivalence Theorem, is to show that the continuum limit of the numerical scheme is the true solution. This means the numerical scheme converges. The scheme is said to be convergent at time \(T = N \, \Delta t\) if

\[ \lim_{\Delta t \to 0} \left\| \left( \mathcal{L}(T) - \left( \mathcal{L}_{\Delta t} \right)^N \right) \symbf{\phi}(0) \right\| \to 0 \, . \tag{C.11}\]

More precisely, the scheme converges if there exists a constant \(K \in [0, \infty)\) such that

\[ \left\| \left( \mathcal{L}(T) - \left( \mathcal{L}_{\Delta t} \right)^N \right) \symbf{\phi}(0) \right\| \le K \, \Delta t. \tag{C.12}\]

Again, the constant \(K\) must be independent of \(\Delta t\).

The key point that distinguishes convergence from consistency is the number of steps taken by the discrete scheme. To be consistent the error needs to converge over a single discrete step. For convergence the error needs to converge after \(N\) steps at fixed \(T\), and in the continuum limit \(\Delta t \to 0\) this means \(N \to \infty\).

C.5 Lax Equivalence Theorem

With the formal machinery set up, the Lax theorem follows.

Theorem C.1 (Lax Equivalence Theorem) Given a well-posed, linear, initial value problem, and a consistent numerical scheme to that problem, stability is necessary and sufficient for convergence.

Proof. First note that

\[ \begin{aligned} \left\| \left( \mathcal{L}(T) - \left( \mathcal{L}_{\Delta t} \right)^N \right) \symbf{\phi}(0) \right\| &= \left\| \left( \mathcal{L}(\Delta t) - \mathcal{L}_{\Delta t} \right) \symbf{\phi}(T - \Delta t) + \right. \\ & \qquad \left. \mathcal{L}_{\Delta t} \symbf{\phi}(T - \Delta t) - \left( \mathcal{L}_{\Delta t} \right)^N \symbf{\phi}(0)\right\| \\ & \le K_C \, \Delta t + \left\| \mathcal{L}_{\Delta t} \left( \mathcal{L}(T - \Delta t) - \left( \mathcal{L}_{\Delta t} \right)^{N-1} \right) \symbf{\phi}(0)\right\| \\ & \le K_C \, \Delta t + K_T \left\| \left( \mathcal{L}(T - \Delta t) - \left( \mathcal{L}_{\Delta t} \right)^{N-1} \right) \symbf{\phi}(0) \right\| + \\ & \quad D \, \Delta t. \end{aligned} \tag{C.13}\]

By induction, and using that the initial error is zero, this allows us to write all terms as \(\propto \Delta t\) and hence say that consistency plus stability imply convergence.

In the other direction, it is immediate that convergence implies stability.