43.11.05 · numerical-analysis / 11-finite-difference-pdes

The Lax-Richtmyer equivalence theorem for finite-difference schemes

shipped3 tiersLean: none

Anchor (Master): Richtmyer-Morton 1967 *Difference Methods for Initial-Value Problems* 2e (Interscience) Ch. 3 (the abstract Banach-space formulation: a well-posed linear evolution problem, a consistent family of bounded operators $C(k)$, Lax-Richtmyer stability as uniform power-boundedness, the equivalence theorem proved through the uniform boundedness principle); Lax-Richtmyer 1956 *Survey of the stability of linear finite difference equations* (Comm. Pure Appl. Math. 9) (the original equivalence theorem and the role of the Banach-Steinhaus theorem); Kreiss-Lorenz 1989 *Initial-Boundary Value Problems and the Navier-Stokes Equations* (Academic Press) Ch. 2-3 (well-posedness, the Kreiss matrix theorem, and stability for the constant-coefficient Cauchy problem)

Intuition Beginner

A finite-difference scheme is a recipe that turns the answer at one time level into the answer at the next, over and over, until it reaches the time you care about. Two separate worries hang over such a recipe. First: does each single step copy the true physics closely, so that one short step introduces only a small mistake? Second: as the steps pile up, do those small mistakes stay small, or do they feed on each other and grow? The whole reliability of the scheme rests on these two questions, and this unit is the clean statement of how they combine.

The first worry is called consistency. A scheme is consistent if, over a single tiny step, it matches the true evolution up to a small leftover that shrinks as the step shrinks. Checking it is a local calculation: write down the true answer, write down what one step of the scheme does to it, and compare. The gap is the leftover, and consistency says the gap goes to zero faster than the step itself.

The second worry is called stability. Stability asks whether the scheme keeps a lid on errors as it marches. Picture handing the scheme a small bump and watching it run. A stable scheme never lets that bump grow beyond a fixed bound, no matter how many steps it takes to reach the final time. An unstable scheme lets the bump amplify a little each step, and a little amplification repeated thousands of times turns a whisper into a roar.

Here is the verdict, and it is the heart of the unit. For a problem that is itself well-behaved, the two worries are not just helpful — together they are exactly what you need. A consistent scheme converges to the true answer if and only if it is stable. This is the Lax-Richtmyer equivalence theorem. Its gift is practical: convergence, the thing you actually want, is hard to check head-on, but it splits into two checks you can do — consistency by a short Taylor comparison, and stability by the wave-test of the earlier unit 43.11.03.

Visual Beginner

The picture is a relay race of operators. Each leg is one time step; the baton is the grid of numbers. Consistency controls how cleanly one leg is run; stability controls whether a stumble in an early leg gets magnified by the later legs or stays contained. Convergence is whether the whole relay finishes near the true finish line as you make the legs shorter and more numerous.

The table lines up the three ideas, what each one measures, and how you test it in practice. Reading across, consistency and stability are the two inputs; convergence is the output the theorem hands back.

idea	plain-language meaning	how you check it
consistency	one short step copies the true physics, leftover shrinks fast	local Taylor comparison of one step
stability	piled-up errors stay bounded over all steps to the final time	the wave-test (von Neumann), size of growth factor $\leq 1$
convergence	the computed answer approaches the true answer as the step shrinks	the theorem: consistency and stability together give it

   error after n steps = sum of n small per-step leftovers,
                         each one carried forward by the remaining steps

   true path   E ----E----E----E----E---->  exact answer at time T
                \     \     \     \     \
   per-step      d0    d1    d2    d3    d4     (small consistency leftovers)
   leftovers      \     \     \     \     \
                   \     \     \     \     \
   scheme path  C ----C----C----C----C---->  computed answer at time T

   stable: each leftover d_j is carried forward by C's with size <= M,
           so the total error <= M * (number of steps) * (size of one leftover)
           = M * (T/k) * o(k)  ----> 0 as the step k shrinks.

The takeaway: the error at the final time is built from one small leftover per step, each one passed down the remaining legs of the relay. Stability is the promise that passing a leftover down the relay never magnifies it past a fixed size. With that promise, adding up the leftovers gives the number of steps times a tiny per-step error — and because the per-step error shrinks faster than the step, the total shrinks to zero. That is convergence.

Worked example Beginner

Let us count the total error of a marching scheme and watch consistency and stability combine to send it to zero. We use round, invented numbers so every step is a plain arithmetic check.

Set the final time to $T = 1$ . Suppose we run the scheme with step size $k = 0.001$ , so it takes $T / k = 1000$ steps to reach the end.

Step 1. The per-step leftover. Consistency says each single step copies the true physics up to a small leftover. Suppose for this scheme the leftover at step size $k$ has size $5 \times k \times k$ . At $k = 0.001$ that is $5 \times 0.001 \times 0.001 = 0.000005$ , five millionths, per step.

Step 2. The stability budget. Stability says each leftover, once made, is carried forward to the final time without growing past a fixed factor. Suppose that factor is $M = 2$ : a leftover can at worst double on its way to the finish, never more.

Step 3. Add up the carried-forward leftovers. There are $1000$ leftovers, one per step. Each has size $0.000005$ , and each is carried forward by a factor of at most $2$ . So the total error is at most $1000 \times 2 \times 0.000005 = 0.01$ , one hundredth.

Step 4. Shrink the step and watch the total fall. Halve the step to $k = 0.0005$ . Now there are $2000$ steps, but each leftover is $5 \times 0.0005 \times 0.0005 = 0.00000125$ . The total is at most $2000 \times 2 \times 0.00000125 = 0.005$ , half of before.

What this tells us: halving the step roughly halved the final error. The reason is the bookkeeping of Step 3. The number of steps grows like $1/ k$ , but each leftover shrinks like $k \times k$ , so their product shrinks like $k$ — and the stability factor $M$ just multiplies by a fixed number that never grows. Stability is what keeps $M$ from ballooning with the step count; without that fixed budget, the doubling could become a doubling every step and the sum would explode instead of shrink.

Check your understanding Beginner

Exercise (easy, multiple choice).

The Lax-Richtmyer equivalence theorem says that, for a consistent scheme approximating a well-behaved linear problem, what is equivalent to convergence?

A. Accuracy of the starting value alone. B. Stability — that piled-up errors stay bounded over all steps. C. Using the smallest possible step size. D. Having no leftover at all in a single step.

Hint

Convergence splits into two checks. One is consistency, already assumed here. What is the other?

Answer

B. Feedback-correct: correct; with consistency assumed, the theorem says convergence holds exactly when the scheme is stable, so stability is the equivalent condition. Feedback-wrong: a tiny step (C) or a perfect single step (D) do not by themselves control how piled-up errors grow; the missing ingredient is stability.

Formal definition Intermediate+

Work in the abstract framework of Lax and Richtmyer. Let $B$ be a Banach space (for finite-difference PDE work, $B = L^{2}$ or $L^{\infty}$ of the spatial domain, or the grid space $ℓ^{2}$ once a mesh is fixed), and let the well-posed linear initial-value problem $$ \frac{du}{dt} = A u, \qquad u(0) = u_0 \in B, $$ have, for initial data in a dense subspace $B_{0} \subseteq B$ , a unique solution given by a strongly continuous one-parameter family of solution operators $E (t)$ , $u (t) = E (t) u_{0}$ , with the well-posedness bound $$ \sup_{0 \le t \le T} |E(t)| =: C_T < \infty. $$ Well-posedness is the hypothesis that the continuous problem itself does not amplify data without bound on $[0, T]$ ; the parabolic and pure-advection problems of 02.13.03 and 02.13.04 are well-posed, and the FD schemes of 43.11.02 are their discretisations.

Definition (one-step scheme and consistency). A one-step finite-difference scheme is a family of bounded operators $C (k) : B \to B$ , indexed by the time step $k > 0$ (with the mesh ratio to the spatial step held fixed), advancing the grid solution by $u^{n + 1} = C (k) u^{n}$ , so $u^{n} = C (k)^{n} u^{0}$ . The scheme is consistent with the problem if, for every $v$ in the dense subspace $B_{0}$ , $$ \left| \frac{C(k) - E(k)}{k}, v \right| \longrightarrow 0 \qquad (k \to 0). $$ The scheme is accurate of order $p$ if the local truncation error $C (k) v - E (k) v$ is $O (k^{p + 1})$ on smooth $v$ . Consistency is the abstract form of the local Taylor comparison; for the schemes of 43.11.02 it is checked by expanding both $C (k)$ and $E (k) = e^{k A}$ in powers of $k$ and matching.

Definition (Lax-Richtmyer stability). The scheme is stable (in the Lax-Richtmyer sense) if the operator powers are uniformly power-bounded up to the final time: $$ \sup\big{, |C(k)^n| ;:; 0 \le nk \le T,\ 0 < k \le k_0 ,\big} =: M < \infty $$ for some $k_{0} > 0$ . Equivalently, there are constants $C_{S}, α$ with $∥ C (k)^{n} ∥ \leq C_{S} e^{α t_{n}}$ for $t_{n} = nk \leq T$ . The bound is uniform in both the step count $n$ and the step size $k$ : it is not enough that each fixed scheme have bounded powers; the bound must not blow up as the grid is refined.

Definition (convergence). The scheme is convergent if, whenever $u^{0} \to u_{0}$ in $B$ as $k \to 0$ , the computed solution tracks the exact one: $$ \big| C(k)^{n} u^0 - E(t),u_0 \big| \longrightarrow 0 \qquad \text{as } k \to 0,\ nk \to t, $$ uniformly for $t \in [0, T]$ . It is convergent of order $p$ if the error is $O (k^{p})$ for data in $B_{0}$ .

The solution operators $E (t)$ , the discrete evolution operators $C (k)$ , the well-posedness constant $C_{T}$ , the stability bound $M$ , the dense subspace $B_{0}$ , and the operator norm $∥ \cdot ∥$ on $B$ are recorded in _meta/NOTATION.md. The framework deliberately mirrors the multistep companion-matrix picture of 43.10.03: there the discrete solution operator was the companion matrix of $ρ$ and power-boundedness was the root condition; here it is the abstract $C (k)$ and power-boundedness is Lax-Richtmyer stability.

Counterexamples to common slips

Stability is uniform in the step, not per-scheme. A single fixed operator $C (k_{0})$ has $∥ C (k_{0})^{n} ∥ < \infty$ for each $n$ automatically; that says nothing. Stability demands one constant $M$ controlling the powers across all small $k$ simultaneously, which is exactly the refinement direction in which an unstable scheme blows up.
Consistency is not convergence. The forward-time centred-space scheme for advection is consistent (order one in the truncation error) yet von Neumann unstable for every Courant number 43.11.03; it does not converge. Consistency is local and necessary; it is the equivalence with stability that promotes it to convergence.
Well-posedness of the continuous problem is a hypothesis, not a conclusion. The theorem assumes the underlying IVP is well-posed. For an ill-posed problem (the backward heat equation, where $∥ E (t) ∥$ is unbounded), a consistent stable-looking scheme can fail to converge to anything physical, because there is no bounded $E (t)$ for it to converge to.
Lax-Richtmyer stability and absolute stability are different objects. Lax-Richtmyer stability is the $k \to 0$ uniform power bound up to a fixed time $T$ . The absolute stability of 43.10.04 is a fixed- $k$ region in the complex plane. A scheme can be Lax-Richtmyer stable under a refinement path (e.g. $k / h^{2}$ fixed for the explicit heat scheme) while its absolute-stability region is bounded.

Key theorem with proof Intermediate+

The signature result is the Lax-Richtmyer equivalence theorem: for a consistent one-step scheme approximating a well-posed linear evolution problem, stability is necessary and sufficient for convergence. Sufficiency is an error-accumulation estimate built on a telescoping identity; necessity is an application of the uniform boundedness principle. The theorem reduces the analytic question of convergence to the two independently checkable conditions of the unit, and it is the PDE counterpart of the Dahlquist equivalence theorem for ODEs 43.10.03, with the companion matrix replaced by the abstract evolution operator $C (k)$ ^{[Lax, P. D. & Richtmyer, R. D. — Survey of the stability of linear finite difference equations; Richtmyer, R. D. & Morton, K. W. — Difference Methods for Initial-Value Problems (2nd ed.)]}.

Theorem (Lax-Richtmyer equivalence). Let $C (k)$ be a one-step finite-difference scheme consistent with the well-posed linear initial-value problem $d u / d t = A u$ on the Banach space $B$ , with solution operators $E (t)$ satisfying $sup_{0 \leq t \leq T} ∥ E (t) ∥ = C_{T} < \infty$ . Then the scheme is convergent if and only if it is stable.

Proof. Sufficiency (stability $\Rightarrow$ convergence). Fix $t \in (0, T]$ and a sequence $k \to 0$ , $n \to \infty$ with $nk = t$ (the general $nk \to t$ case differs only by a vanishing $E$ -continuity term). Take data $v \in B_{0}$ . The global error decomposes by telescoping the difference of $n$ scheme steps against $n$ exact steps: $$ C(k)^n - E(k)^n = \sum_{j=0}^{n-1} C(k)^{,n-1-j},\big(C(k) - E(k)\big),E(k)^{j}. $$ This identity is checked by expanding the sum: the $j$ -th and $(j + 1)$ -th terms share the boundary $C (k)^{n - 1 - j} E (k)^{j + 1}$ , and the sum collapses to $C (k)^{n} - E (k)^{n}$ .

Since $E (k)^{j} = E (j k)$ (the solution operators form a semigroup), apply the identity to $v$ and take norms: $$ \big|\big(C(k)^n - E(nk)\big)v\big| \le \sum_{j=0}^{n-1} \big|C(k)^{,n-1-j}\big|;\big|\big(C(k) - E(k)\big)E(jk),v\big|. $$ Stability bounds each operator power by $M$ . For the middle factor, consistency gives, for each fixed $w \in B_{0}$ , $∥ (C (k) - E (k)) w ∥ = k η_{k} (w)$ with $η_{k} (w) \to 0$ ; applying this to $w = E (j k) v \in B_{0}$ and writing $η_{k} := sup_{0 \leq s \leq T} η_{k} (E (s) v)$ (finite and $\to 0$ by consistency together with the strong continuity of $s \mapsto E (s) v$ on the compact interval) yields $∥ (C (k) - E (k)) E (j k) v ∥ \leq k η_{k}$ . Hence $$ \big|\big(C(k)^n - E(nk)\big)v\big| \le \sum_{j=0}^{n-1} M,k,\eta_k = M,(nk),\eta_k = M,t,\eta_k \longrightarrow 0. $$ So $C (k)^{n} v \to E (t) v$ for $v \in B_{0}$ . For general data, write $C (k)^{n} u^{0} - E (t) u_{0} = C (k)^{n} (u^{0} - v) + (C (k)^{n} - E (t)) v + E (t) (v - u_{0})$ ; choose $v \in B_{0}$ with $∥ v - u_{0} ∥$ small, bound the first term by $M ∥ u^{0} - v ∥$ (stability) and the third by $C_{T} ∥ v - u_{0} ∥$ (well-posedness), and let $k \to 0$ . The density of $B_{0}$ makes the error arbitrarily small, so the scheme converges.

Necessity (convergence $\Rightarrow$ stability). Argue by contraposition through the uniform boundedness principle. Suppose the scheme converges but is not stable: the operator family ${C (k)^{n} : 0 \leq nk \leq T, 0 < k \leq k_{0}}$ is unbounded in operator norm. Convergence means that for each fixed $u_{0} \in B$ the net $C (k)^{n (k)} u_{0}$ (with $n (k) k \to t$ ) converges, hence is bounded in $B$ for that $u_{0}$ ; in particular the family ${C (k)^{n}}$ is pointwise bounded — $sup ∥ C (k)^{n} u_{0} ∥ < \infty$ for each $u_{0}$ . The Banach-Steinhaus theorem states that a pointwise-bounded family of bounded operators on a Banach space is uniformly norm-bounded. This contradicts the assumed unboundedness of ${C (k)^{n}}$ in operator norm. Therefore a convergent scheme is stable. $□$

Bridge. This theorem is the foundational reason convergence of a finite-difference scheme is never checked directly: the telescoping identity shows the global error is a stability-weighted sum of consistency errors, so $∥ C (k)^{n} - E (nk) ∥ ≲ M t η_{k}$ , and convergence follows the moment the two factors $M$ (stability) and $η_{k}$ (consistency) are each controlled. This is exactly the error-accumulation argument of the one-step and multistep ODE theory 43.10.03 lifted from a scalar amplification or companion matrix to the abstract operator $C (k)$ , and the necessity half is dual to the sufficiency half: sufficiency builds convergence out of stability by summation, while necessity extracts stability back out of convergence by the uniform boundedness principle, so the two implications are the same equivalence read in opposite directions. The central insight is that "consistency plus stability equals convergence" is one template realised across every linear discretisation — companion-matrix power-boundedness for multistep ODEs, von Neumann symbol-boundedness for constant-coefficient FD schemes, abstract operator power-boundedness here. Putting these together, von Neumann analysis 43.11.03 is precisely the computation of the stability constant $M$ mode by mode on a periodic grid; this builds toward the master-tier identification of stability with uniform power-boundedness via the Kreiss matrix theorem, and the bridge is that the abstract hypothesis $∥ C (k)^{n} ∥ \leq M$ appears again in every chapter that discretises a well-posed evolution problem.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

For a constant-coefficient scheme on the periodic grid with amplification factor $g (ξ)$ , the $ℓ^{2}$ operator norm is $∥ C (k) ∥_{ℓ^{2}} = sup_{ξ} ∣ g (ξ) ∣$ 43.11.03. Show that the von Neumann condition $sup_{ξ} ∣ g (ξ) ∣ \leq 1 + C k$ implies Lax-Richtmyer stability, making von Neumann analysis a verification of the theorem's hypothesis.

Hint

$∥ C (k)^{n} ∥_{ℓ^{2}} = sup_{ξ} ∣ g (ξ) ∣^{n}$ ; bound $(1 + C k)^{n}$ as in Exercise 4.

Answer

By Fourier diagonalisation 43.11.03, $∥ C (k)^{n} ∥_{ℓ^{2}} = sup_{ξ} ∣ g (ξ)^{n} ∣ = (sup_{ξ} ∣ g (ξ) ∣)^{n}$ . If $sup_{ξ} ∣ g (ξ) ∣ \leq 1 + C k$ , then $∥ C (k)^{n} ∥_{ℓ^{2}} \leq (1 + C k)^{n} \leq e^{C k n} = e^{C t_{n}} \leq e^{C T}$ for $t_{n} \leq T$ , uniformly in $n, k$ . Hence the von Neumann condition gives Lax-Richtmyer stability with $M = e^{C T}$ , and the equivalence theorem then upgrades a consistent von Neumann-stable scheme to a convergent one. This is the precise sense in which von Neumann analysis is the computable engine of the abstract theorem. Rubric: full credit for the diagonalisation step, the exponential bound, and the identification of $M$ .

Exercise 6 (medium, symbolic).

Show that the forward-time centred-space (FTCS) scheme for the advection equation $u_{t} + a u_{x} = 0$ , which has $g (ξ) = 1 - i ν sin ξ h$ with $∣ g (ξ) ∣^{2} = 1 + ν^{2} sin^{2} ξ h$ 43.11.03, is consistent yet not convergent, and reconcile this with the equivalence theorem.

Hint

Consistency holds (the truncation error is $O (k)$ ). Is $sup_{ξ} ∣ g ∣$ bounded by $1 + C k$ ? What does the theorem conclude for an inconsistent-with-stability scheme?

Answer

A Taylor expansion of the truncation error shows the centred scheme is consistent of order one, so it meets the theorem's consistency hypothesis. But $sup_{ξ} ∣ g (ξ) ∣^{2} = 1 + ν^{2} sin^{2} ξ h$ attains $1 + ν^{2}$ at $ξ h = π /2$ , so $sup_{ξ} ∣ g ∣ = 1 + ν^{2} > 1$ by a fixed amount independent of $k$ ; this violates $sup_{ξ} ∣ g ∣ \leq 1 + C k$ , so the scheme is not Lax-Richtmyer stable. By the necessity half of the equivalence theorem, an unstable consistent scheme cannot converge — and indeed its high-wavenumber modes grow like $(1 + ν^{2})^{n /2}$ , swamping the solution. This is consistent with the theorem: it is the contrapositive of necessity. Rubric: full credit for the consistency note, the instability from the fixed-size excess over $1$ , and the appeal to necessity.

Exercise 7 (hard, symbolic).

Prove the necessity half of the equivalence theorem in detail: a consistent convergent scheme is Lax-Richtmyer stable. State precisely where the Banach-Steinhaus theorem enters.

Hint

Pointwise boundedness comes from convergence; uniform boundedness comes from Banach-Steinhaus. Build the family of operators indexed by $(k, n)$ with $nk \leq T$ .

Answer

Consider the family $T = {C (k)^{n} : 0 < k \leq k_{0}, 0 \leq nk \leq T}$ of bounded operators on $B$ . Fix $u_{0} \in B$ . Convergence asserts that along any admissible sequence $k_{m} \to 0$ , $n_{m} k_{m} \to t$ , the vectors $C (k_{m})^{n_{m}} u_{0}$ converge in $B$ to $E (t) u_{0}$ ; a convergent sequence is bounded, and since $[0, T]$ is compact and the limit $E (t) u_{0}$ is continuous in $t$ , $sup_{T \in T} ∥ T u_{0} ∥ < \infty$ for each fixed $u_{0}$ (any unbounded subfamily would contain a sequence violating convergence to the bounded limit). Thus $T$ is pointwise bounded: $sup_{T \in T} ∥ T u_{0} ∥ < \infty$ for every $u_{0} \in B$ . The Banach-Steinhaus (uniform boundedness) theorem applies precisely here — $B$ is a Banach space and $T$ is a family of bounded linear operators that is pointwise bounded — to conclude $sup_{T \in T} ∥ T ∥ < \infty$ . That supremum is the Lax-Richtmyer stability constant $M$ . Banach-Steinhaus is the load-bearing step: it converts the pointwise (per-datum) bound, which convergence hands us for free, into the uniform operator-norm bound that is stability. Rubric: full credit for constructing $T$ , deriving pointwise boundedness from convergence, the explicit invocation of Banach-Steinhaus on a Banach space, and identifying the resulting bound as $M$ .

Exercise 8 (hard, symbolic).

For the explicit (FTCS) scheme for the heat equation $u_{t} = u_{xx}$ with mesh ratio $r = k / h^{2} \leq 1/2$ held fixed under refinement, assemble a full convergence proof from the equivalence theorem: state consistency, state stability, and combine.

Hint

Consistency: truncation error $O (k) + O (h^{2}) = O (k)$ at fixed $r$ . Stability: $sup_{ξ} ∣ g ∣ = 1$ for $r \leq 1/2$ from 43.11.03. Then apply the sufficiency half.

Answer

Consistency. Taylor-expanding the FTCS truncation error gives $τ = \frac{k}{2} u_{tt} - \frac{h ^{2}}{12} u_{xxxx} + \dots = O (k) + O (h^{2})$ ; with $r = k / h^{2}$ fixed, $h^{2} = k / r$ , so $τ = O (k)$ , and the consistency error $η_{k} = ∥ τ ∥ \to 0$ . Stability. The amplification factor is $g (ξ) = 1 - 4 r sin^{2} (ξ h /2)$ , with $g \in [1 - 4 r, 1]$ ; for $r \leq 1/2$ , $1 - 4 r \geq - 1$ , so $sup_{ξ} ∣ g ∣ = 1$ and $∥ C (k)^{n} ∥_{ℓ^{2}} = 1$ for all $n$ — Lax-Richtmyer stable with $M = 1$ . Combine. The continuous heat problem is well-posed on $L^{2}$ 02.13.03, $E (t) = e^{t \partial_{xx}}$ with $∥ E (t) ∥ \leq 1$ ; the scheme is consistent and stable; by the sufficiency half of the equivalence theorem the global error obeys $∥ C (k)^{n} - E (nk) ∥ \leq M t η_{k} = t \cdot O (k) \to 0$ , so FTCS converges at first order in $k$ (second order in $h$ ) for $r \leq 1/2$ . The whole convergence proof is two one-line checks fed into the theorem. Rubric: full credit for the consistency order at fixed $r$ , the stability constant $M = 1$ from $sup ∣ g ∣ = 1$ , and the assembled convergence conclusion with rate.

Advanced results Master

Theorem 1 (Lax-Richtmyer equivalence, abstract form). For a one-step scheme $C (k)$ consistent with a well-posed linear initial-value problem $d u / d t = A u$ on a Banach space $B$ , with solution semigroup $E (t)$ bounded on $[0, T]$ , stability — uniform power-boundedness $sup {∥ C (k)^{n} ∥ : 0 \leq nk \leq T, 0 < k \leq k_{0}} < \infty$ — is necessary and sufficient for convergence. Sufficiency is the telescoping estimate $∥ (C (k)^{n} - E (nk)) v ∥ \leq M t η_{k}$ ; necessity is the Banach-Steinhaus deduction that a convergent (hence pointwise-bounded) operator family is uniformly bounded ^{[Lax, P. D. & Richtmyer, R. D. — Survey of the stability of linear finite difference equations]}.

Theorem 2 (Kreiss matrix theorem — stability made verifiable). For a constant-coefficient one-step scheme for a first-order system on the whole line, Fourier transformation reduces stability to uniform power-boundedness of the amplification matrix family ${G (ξ) : ξ \in R}$ : $sup_{ξ} sup_{n} ∥ G (ξ)^{n} ∥ < \infty$ . The Kreiss matrix theorem characterises this by four mutually equivalent conditions — (a) the uniform power bound itself; (b) a resolvent condition* $∥ (z I - G (ξ))^{- 1} ∥ \leq K / (∣ z ∣ - 1)$ for all $∣ z ∣ > 1$ and all $ξ$ ; (c) a numerical-range / Lyapunov condition with a uniformly bounded Hermitian $H (ξ) ≻ 0$ satisfying $G^ H G \preceq H $; (d) u ni f or m d ia g o na l i s abi l i t y w i t hb o u n d e d t r an s f or ma t i o n s . T h esc a l a r v o n N e u mann co n d i t i o n$ \sup_\xi|g(\xi)| \le 1 + Ck $i s t h e n or ma l - ma t r i x s p ec ia l c a se; f or n o n - n or ma l$ G(\xi) $t h es p ec t r a l r a d i u s a l o n e i s in s u f f i c i e n t b ec a u seo f t r an s i e n t g r o w t h$ |G^n| \gg \rho(G)^n$. This is the master link from the abstract stability hypothesis of Theorem 1 to a decidable test ^{[Richtmyer, R. D. & Morton, K. W. — Difference Methods for Initial-Value Problems (2nd ed.)]}.

Theorem 3 (order of convergence equals order of accuracy under stability). If, in addition to consistency, the scheme is accurate of order $p$ — local truncation error $O (k^{p + 1})$ on $B_{0}$ — and stable, then the global error is $O (k^{p})$ : $∥ C (k)^{n} u^{0} - E (nk) u_{0} ∥ \leq M (∥ u^{0} - u_{0} ∥ + t max_{j} ∥ τ^{j} ∥/ k) = O (k^{p})$ when starting errors are $O (k^{p})$ . The proof is the telescoping estimate of Theorem 1 with $η_{k}$ replaced by the $O (k^{p})$ per-step accuracy, the factor $t = nk$ absorbing the step count. This is the exact PDE analogue of the order-preservation statement of the multistep convergence theorem 43.10.03 ^{[Strikwerda, J. C. — Finite Difference Schemes and Partial Differential Equations (2nd ed.)]}.

Theorem 4 (well-posedness is indispensable). If the continuous problem is ill-posed on $[0, T]$ — $sup_{0 \leq t \leq T} ∥ E (t) ∥ = \infty$ , as for the backward heat equation $u_{t} = - u_{xx}$ whose high modes grow like $e^{+ ξ^{2} t}$ — the equivalence theorem does not apply, and a scheme that is consistent and (formally) stable in the Lax-Richtmyer sense need not converge to a meaningful solution: there is no bounded $E (t)$ to converge to, and the natural discretisations themselves inherit the unbounded amplification. Well-posedness of the target problem is therefore a genuine hypothesis, not a technical convenience; the theorem is a statement about approximating problems that have a stable continuous solution operator in the first place ^{[Richtmyer, R. D. & Morton, K. W. — Difference Methods for Initial-Value Problems (2nd ed.)]}.

Theorem 5 (the Lax-Milgram / coercivity parallel and the inf-sup analogue). The equivalence theorem has a structural sibling in the variational theory of 24.01.03: there Lax-Milgram coercivity guarantees a stable inverse $∥ A_{h}^{- 1} ∥ \leq 1/ α$ for the discrete elliptic operator, and Céa's lemma turns that stability plus approximation (the variational analogue of consistency) into convergence. In both stories convergence is stability times approximation: the inf-sup constant or coercivity bound plays the role of the inverse stability constant $M$ , and the best-approximation error plays the role of the consistency error $η_{k}$ . The finite-difference and finite-element discretisations of the same PDE are thus governed by one principle in two grammars — power-boundedness of an evolution operator for time-stepping, boundedness of an inverse for the steady variational problem ^{[Strikwerda, J. C. — Finite Difference Schemes and Partial Differential Equations (2nd ed.)]}.

Synthesis. The foundational reason the entire convergence theory of linear finite-difference schemes collapses to two independent checks is the telescoping identity: the global error is a stability-weighted sum of per-step consistency errors, $∥ C (k)^{n} - E (nk) ∥ \leq M t η_{k}$ , so once stability bounds the operator powers by a fixed $M$ and consistency drives $η_{k}$ to zero, convergence is automatic. This is exactly the structure met for ordinary differential equations in 43.10.03, where the abstract operator $C (k)$ specialised to the companion matrix of $ρ$ and Lax-Richtmyer stability specialised to the root condition; the central insight is that "consistency plus stability equals convergence" is one template realised across multistep ODE methods, constant-coefficient FD schemes, and abstract evolution problems, with stability meaning power-boundedness of a single solution operator in each case. The two halves of the theorem are dual: sufficiency manufactures convergence from stability by summation, and necessity recovers stability from convergence by the Banach-Steinhaus theorem, so the equivalence is one fact read forward and backward. Putting these together, von Neumann analysis 43.11.03 is the constant-coefficient computation of $M$ mode by mode, the Kreiss matrix theorem is its non-normal-systems completion, and the Lax-Milgram coercivity story of 24.01.03 is the steady-state sibling — convergence as stability times approximation in every grammar. The bridge to the rest of numerical PDE is that this single power-boundedness hypothesis $∥ C (k)^{n} ∥ \leq M$ is what every chapter that discretises a well-posed evolution problem must establish, by whatever computable test the structure of the scheme allows.

Full proof set Master

Proposition 1 (telescoping error identity and the stability-weighted bound). Let $C, E$ be bounded operators on a Banach space $B$ . Then for every $n \geq 1$ , $$ C^n - E^n = \sum_{j=0}^{n-1} C^{,n-1-j},(C - E),E^{j}, $$ and consequently $∥ C^{n} - E^{n} ∥ \leq (max_{0 \leq m \leq n - 1} ∥ C^{m} ∥) \sum_{j = 0}^{n - 1} ∥ (C - E) E^{j} ∥$ .

Proof. Set $a_{j} = C^{n - j} E^{j}$ for $0 \leq j \leq n$ , so $a_{0} = C^{n}$ and $a_{n} = E^{n}$ . The $j$ -th summand is $$ C^{n-1-j}(C-E)E^j = C^{n-1-j}\big(CE^j - EE^j\big) = C^{n-j}E^j - C^{n-1-j}E^{j+1} = a_j - a_{j+1}. $$ No commutativity of $C$ and $E$ is used. Summing over $j = 0, \dots, n - 1$ telescopes: $\sum_{j = 0}^{n - 1} (a_{j} - a_{j + 1}) = a_{0} - a_{n} = C^{n} - E^{n}$ . For the bound, take norms term by term, factor $∥ C^{n - 1 - j} ∥ \leq max_{0 \leq m \leq n - 1} ∥ C^{m} ∥$ out of each, and sum. $□$

Proposition 2 (sufficiency: stability and consistency give convergence with rate). Let $C (k)$ be consistent with the well-posed problem $d u / d t = A u$ (solution operators $E (t)$ , $sup_{[0, T]} ∥ E (t) ∥ = C_{T}$ ) and stable with constant $M$ . Fix $t \in (0, T]$ , $v \in B_{0}$ , and admissible $k \to 0$ , $nk \to t$ . Then $∥ C (k)^{n} v - E (t) v ∥ \to 0$ . If moreover the scheme is accurate of order $p$ , the bound is $O (k^{p})$ .

Proof. By Proposition 1 with $C = C (k)$ , $E = E (k)$ , and $E (k)^{j} = E (j k)$ , $$ |C(k)^n v - E(nk)v| \le M \sum_{j=0}^{n-1}\big|(C(k)-E(k))E(jk)v\big|. $$ Consistency gives $∥ (C (k) - E (k)) w ∥ = k η_{k} (w)$ with $η_{k} (w) \to 0$ for each $w \in B_{0}$ ; set $η_{k} = sup_{0 \leq s \leq T} η_{k} (E (s) v)$ , finite because $s \mapsto E (s) v$ is a continuous (hence compact-image) curve in $B_{0}$ and $η_{k} (\cdot)$ is bounded on it, and $η_{k} \to 0$ by consistency. Each summand is then $\leq k η_{k}$ , so the sum is $\leq nk η_{k} = t η_{k}$ , giving $∥ C (k)^{n} v - E (nk) v ∥ \leq M t η_{k} \to 0$ . Finally $∥ E (nk) v - E (t) v ∥ \to 0$ by strong continuity, closing the estimate. If the scheme is accurate of order $p$ , then $η_{k} = O (k^{p})$ on $B_{0}$ , so the bound is $M t O (k^{p}) = O (k^{p})$ . $□$

Proposition 3 (necessity: convergence forces uniform power-boundedness). If $C (k)$ is consistent with the well-posed problem and convergent, then $sup {∥ C (k)^{n} ∥ : 0 \leq nk \leq T, 0 < k \leq k_{0}} < \infty$ .

Proof. Let $T = {C (k)^{n} : 0 < k \leq k_{0}, 0 \leq nk \leq T}$ , a family of bounded operators on the Banach space $B$ . Fix $u_{0} \in B$ . For any sequence $(k_{m}, n_{m})$ with $k_{m} \to 0$ , $n_{m} k_{m} \to t \in [0, T]$ , convergence gives $C (k_{m})^{n_{m}} u_{0} \to E (t) u_{0}$ , so $sup_{m} ∥ C (k_{m})^{n_{m}} u_{0} ∥ < \infty$ . Were $sup_{S \in T} ∥ S u_{0} ∥ = \infty$ , one could extract a sequence $S_{m} = C (k_{m})^{n_{m}} \in T$ with $∥ S_{m} u_{0} ∥ \to \infty$ ; passing to a subsequence so that $n_{m} k_{m} \to t$ (possible since the times lie in the compact $[0, T]$ ) contradicts the convergence of $C (k_{m})^{n_{m}} u_{0}$ to the finite limit $E (t) u_{0}$ . Hence $sup_{S \in T} ∥ S u_{0} ∥ < \infty$ for every $u_{0} \in B$ : the family $T$ is pointwise bounded. The Banach-Steinhaus theorem (uniform boundedness principle), valid because $B$ is complete, upgrades pointwise boundedness of a family of bounded operators to uniform boundedness: $sup_{S \in T} ∥ S ∥ < \infty$ . That supremum is the stability constant. $□$

Proposition 4 (von Neumann stability implies Lax-Richtmyer stability on the periodic grid). Let $C (k)$ be a constant-coefficient one-step scheme on the periodic grid with amplification factor $g_{k} (ξ)$ and $∥ C (k) ∥_{ℓ^{2}} = sup_{ξ} ∣ g_{k} (ξ) ∣$ . If $sup_{ξ} ∣ g_{k} (ξ) ∣ \leq 1 + C k$ uniformly in small $k$ , then $C (k)$ is Lax-Richtmyer stable with $M = e^{C T}$ .

Proof. Fourier diagonalisation 43.11.03 gives $∥ C (k)^{n} ∥_{ℓ^{2}} = sup_{ξ} ∣ g_{k} (ξ)^{n} ∣ = (sup_{ξ} ∣ g_{k} (ξ) ∣)^{n}$ , since raising the multiplier to the $n$ -th power raises its supremum to the $n$ -th power for a scalar symbol. By hypothesis this is $\leq (1 + C k)^{n}$ . Using $1 + x \leq e^{x}$ , $(1 + C k)^{n} \leq e^{C k n} = e^{C t_{n}} \leq e^{C T}$ for all $t_{n} = nk \leq T$ . The bound is independent of $n$ and $k$ , so $sup {∥ C (k)^{n} ∥ : 0 \leq nk \leq T, 0 < k \leq k_{0}} \leq e^{C T} =: M < \infty$ . $□$

Connections Master

The zero-stability and Dahlquist equivalence theory of 43.10.03 is the ordinary-differential-equation prototype this unit lifts to partial differential equations: there a consistent linear multistep method converges if and only if it is zero-stable (the root condition), with the discrete solution operator the companion matrix of $ρ$ and stability its power-boundedness. Here the discrete solution operator is the abstract one-step operator $C (k)$ and stability is its uniform power-boundedness; the telescoping/variation-of-constants error estimate and the "consistency plus stability equals convergence" verdict are the same argument in both, which is why this unit and 43.10.03 are written as the matched ODE and PDE capstones of their chapters.
The von Neumann stability analysis of 43.11.03 is the computable engine that verifies this theorem's stability hypothesis: on a periodic grid the Fourier transform diagonalises a constant-coefficient scheme, so $∥ C (k)^{n} ∥_{ℓ^{2}} = sup_{ξ} ∣ g (ξ) ∣^{n}$ and the abstract bound $∥ C (k)^{n} ∥ \leq M$ becomes the pointwise symbol check $sup_{ξ} ∣ g (ξ) ∣ \leq 1 + C k$ . Von Neumann analysis is to the Lax-Richtmyer theorem what the root condition is to the Dahlquist theorem — the finite, checkable form of the stability hypothesis.
The method of lines and the explicit/implicit/Crank-Nicolson heat schemes of 43.11.02 supply the concrete one-step operators $C (k)$ to which this theorem is applied: that unit constructs the schemes and computes their stability restrictions, and this unit certifies that those stable, consistent schemes therefore converge, closing the loop the parabolic chapter opened. The elliptic discretisation of 43.11.01, whose convergence rests on a discrete maximum principle and the bound $∥ A_{h}^{- 1} ∥ = O (1)$ , is the steady-state companion: there stability is boundedness of an inverse rather than power-boundedness of an evolution, the same principle for the time-independent problem.
The Lax-Milgram and inf-sup theory of 24.01.03 is the variational sibling of this theorem: Céa's lemma turns discrete coercivity (stability, $∥ A_{h}^{- 1} ∥ \leq 1/ α$ ) plus best approximation (the variational consistency) into finite-element convergence, exactly the "convergence equals stability times approximation" structure here. The finite-difference and finite-element discretisations of the same well-posed PDE are governed by one equivalence principle expressed in two grammars.
The eigenvalue and operator-power theory of 01.01.08 underlies the stability analysis at every level: stability is power-boundedness of $C (k)$ , decided for normal operators by the moduli of eigenvalues (the von Neumann symbol) and for non-normal amplification matrices by the Kreiss matrix theorem's resolvent and Lyapunov characterisations, which refine the spectral-radius criterion to account for transient growth.

Historical & philosophical context Master

The equivalence theorem is due to Peter Lax and Robert Richtmyer, whose 1956 paper Survey of the stability of linear finite difference equations in Communications on Pure and Applied Mathematics ^{[Lax, P. D. & Richtmyer, R. D. — Survey of the stability of linear finite difference equations]} formulated the abstract Banach-space framework — a properly posed linear initial-value problem, a consistent family of one-step difference operators, and Lax-Richtmyer stability as uniform power-boundedness — and proved that, under consistency, stability is necessary and sufficient for convergence. The necessity argument's use of the Banach-Steinhaus / uniform boundedness principle was the conceptual innovation: it converts the pointwise convergence that one wants into the uniform operator bound that one can check. The same year, Germund Dahlquist ^{[Lax, P. D. & Richtmyer, R. D. — Survey of the stability of linear finite difference equations]} published the analogous equivalence for linear multistep methods for ordinary differential equations, and the structural parallel between the two 1956 theorems was noticed at once.

The abstract theory was systematised by Robert Richtmyer and Keith Morton in their 1967 monograph Difference Methods for Initial-Value Problems, which gave the full Banach-space treatment, the telescoping error identity, and the connection to the semigroup theory of Einar Hille and Kōsaku Yosida. The verifiable stability criterion for constant-coefficient systems is the Kreiss matrix theorem, proved by Heinz-Otto Kreiss in 1962, characterising uniform power-boundedness of a parametrised matrix family through equivalent resolvent, numerical-range, and Lyapunov conditions; its extension to initial-boundary-value problems is the Gustafsson-Kreiss-Sundström theory. The Courant-Friedrichs-Lewy condition of 1928, which predates the equivalence theorem, is the necessary geometric shadow of stability for explicit hyperbolic schemes that the theorem subsumes.

Bibliography Master

@article{laxrichtmyer1956,
  author  = {Lax, Peter D. and Richtmyer, Robert D.},
  title   = {Survey of the stability of linear finite difference equations},
  journal = {Communications on Pure and Applied Mathematics},
  volume  = {9},
  number  = {2},
  year    = {1956},
  pages   = {267--293}
}

@book{richtmyermorton1967,
  author    = {Richtmyer, Robert D. and Morton, K. W.},
  title     = {Difference Methods for Initial-Value Problems},
  edition   = {2},
  publisher = {Interscience Publishers (John Wiley \& Sons)},
  year      = {1967}
}

@book{strikwerda2004,
  author    = {Strikwerda, John C.},
  title     = {Finite Difference Schemes and Partial Differential Equations},
  edition   = {2},
  publisher = {Society for Industrial and Applied Mathematics (SIAM)},
  year      = {2004}
}

@article{kreiss1962,
  author  = {Kreiss, Heinz-Otto},
  title   = {\"{U}ber die Stabilit\"{a}tsdefinition f\"{u}r Differenzengleichungen die partielle Differentialgleichungen approximieren},
  journal = {BIT Numerical Mathematics},
  volume  = {2},
  number  = {3},
  year    = {1962},
  pages   = {153--181}
}

@book{kreisslorenz1989,
  author    = {Kreiss, Heinz-Otto and Lorenz, Jens},
  title     = {Initial-Boundary Value Problems and the Navier-Stokes Equations},
  publisher = {Academic Press},
  series    = {Pure and Applied Mathematics},
  volume    = {136},
  year      = {1989}
}

@book{leveque2007fdm,
  author    = {LeVeque, Randall J.},
  title     = {Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems},
  publisher = {Society for Industrial and Applied Mathematics (SIAM)},
  year      = {2007}
}

@article{courantfriedrichslewy1928,
  author  = {Courant, Richard and Friedrichs, Kurt and Lewy, Hans},
  title   = {\"{U}ber die partiellen Differenzengleichungen der mathematischen Physik},
  journal = {Mathematische Annalen},
  volume  = {100},
  number  = {1},
  year    = {1928},
  pages   = {32--74}
}

Prerequisites

43.11.03
43.11.02

Tier anchors

beginner: LeVeque 2007 *Finite Difference Methods for Ordinary and Partial Differential Equations* (SIAM) §9.5, §10.1 (the convergence picture: a consistent scheme converges exactly when it does not amplify errors, and the Lax theorem stated as consistency + stability gives convergence); Strikwerda 2004 *Finite Difference Schemes and Partial Differential Equations* 2e (SIAM) §1.5, §10.1 (the informal statement that a consistent, stable scheme is convergent, illustrated on the heat and advection equations)
intermediate: Strikwerda 2004 *Finite Difference Schemes and Partial Differential Equations* 2e (SIAM) §10.1-10.5 (the Lax-Richtmyer equivalence theorem stated for one-step schemes via the solution operators $C(k)$, with the consistency, stability, and convergence definitions and the telescoping error-accumulation proof); LeVeque 2007 *Finite Difference Methods for Ordinary and Partial Differential Equations* (SIAM) §9.5 (Lax-Richtmyer stability $\|C(k)^n\|\le M$ for $nk\le T$ and the equivalence with convergence for a consistent scheme)
master: Richtmyer-Morton 1967 *Difference Methods for Initial-Value Problems* 2e (Interscience) Ch. 3 (the abstract Banach-space formulation: a well-posed linear evolution problem, a consistent family of bounded operators $C(k)$, Lax-Richtmyer stability as uniform power-boundedness, the equivalence theorem proved through the uniform boundedness principle); Lax-Richtmyer 1956 *Survey of the stability of linear finite difference equations* (Comm. Pure Appl. Math. 9) (the original equivalence theorem and the role of the Banach-Steinhaus theorem); Kreiss-Lorenz 1989 *Initial-Boundary Value Problems and the Navier-Stokes Equations* (Academic Press) Ch. 2-3 (well-posedness, the Kreiss matrix theorem, and stability for the constant-coefficient Cauchy problem)

References

Lax, P. D. & Richtmyer, R. D. — Survey of the stability of linear finite difference equations · Communications on Pure and Applied Mathematics 9 (1956), pp. 267-293. Sets the abstract framework: a well-posed linear initial-value problem $du/dt = Au$ on a Banach space $B$, with solution operators $E(t)$ forming a strongly continuous semigroup bounded by $\|E(t)\|\le C_T$ for $0\le t\le T$, is approximated by a one-step finite-difference scheme $u^{n+1} = C(k)u^n$ with $C(k)$ a bounded operator depending on the time step $k$. Consistency is the requirement that $C(k)$ reproduce $E(k)$ to first order on smooth data, $\|(C(k)-E(k))v\|/k \to 0$ as $k\to0$; (Lax-Richtmyer) stability is the uniform power-boundedness $\|C(k)^n\|\le M$ for all $0\le nk\le T$ and $0<k\le k_0$; convergence is $\|C(k)^{n}u^0 - E(t)u_0\|\to0$ for $nk\to t$ as $k\to0$ with $u^0\to u_0$. The equivalence theorem: for a consistent scheme approximating a well-posed problem, stability is necessary and sufficient for convergence. Sufficiency is the telescoping/Lady Windermere's-fan error decomposition; necessity uses the Banach-Steinhaus (uniform boundedness) principle — a convergent unstable scheme would yield an unbounded family of operators on a fixed vector, contradicting pointwise boundedness.
Richtmyer, R. D. & Morton, K. W. — Difference Methods for Initial-Value Problems (2nd ed.) · Interscience/Wiley 1967. Ch. 3 develops the abstract theory in full. The problem $du/dt = Au$, $u(0)=u_0$ is properly posed on a Banach space $B$ over a finite interval $[0,T]$ if a unique solution exists for $u_0$ in a dense subspace and depends continuously on the data, equivalently the generated operators $E(t)=e^{tA}$ satisfy $\sup_{0\le t\le T}\|E(t)\|<\infty$. A difference scheme $u^{n+1}=C(k)u^n$ is consistent with the problem if $\|(C(k)-E(k))E(t)u_0\| = o(k)$ uniformly on $[0,T]$ for $u_0$ in the dense subspace, and accurate of order $p$ if the local error is $O(k^{p+1})$. Stability is $\{C(k)^n : 0\le nk\le T, 0<k\le k_0\}$ uniformly bounded. Theorem (Lax equivalence): given consistency with a properly posed problem, stability is equivalent to convergence. The proof of necessity invokes the uniform boundedness principle; sufficiency uses the identity $C(k)^n - E(nk) = \sum_{j=0}^{n-1}C(k)^{n-1-j}(C(k)-E(k))E(jk)$ and bounds each term by stability times the consistency error. The Kreiss matrix theorem supplies the verifiable characterisation of stability for constant-coefficient systems on the whole line.
Strikwerda, J. C. — Finite Difference Schemes and Partial Differential Equations (2nd ed.) · SIAM 2004. §10.1-10.5 give the equivalence theorem in the form most used in practice. For a one-step scheme written $v^{n+1}=Q v^n$ (with $Q$ depending on $k,h$ and the mesh ratio held fixed) approximating a well-posed constant-coefficient Cauchy problem, the scheme is stable in $L^2$ if there are constants $C_S,\alpha$ with $\|Q^n\| \le C_S e^{\alpha t_n}$ uniformly for $0\le t_n\le T$ and mesh parameters small; consistency is the order-of-accuracy condition from the truncation error. Theorem 10.1.2 (Lax-Richtmyer): a consistent scheme for a well-posed linear initial-value problem is convergent if and only if it is stable. §10.5 connects the abstract stability to the von Neumann condition: for constant-coefficient schemes on a periodic or whole-line grid, $L^2$ stability is exactly $\sup_\xi|g(\xi)|\le1+Ck$ (scalar) or uniform power-boundedness of the amplification matrix $G(\xi)$ (systems), so von Neumann analysis is the computable engine that checks the stability hypothesis of the theorem.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m