---
tag: 559N53ZTMV
kind: statement
role: theorem
name: Godunov's theorem
msc: [65M06, 65M12, 35L65]
uses: [PVD7VZJZ9B, X7HYEBA5SA, MTCRZC5QKT, YHZ9BCNDRZ, NX8RE9B72A]
about: [X7HYEBA5SA]
sources:
  - url: https://en.wikipedia.org/wiki/Godunov%27s_theorem
---

## Statement

Let $a \in \R$, and consider the [[transport equation|PVD7VZJZ9B]] $u_t + a u_x = 0$.
Fix $\Delta x, \Delta t > 0$ and put $\nu = a \Delta t / \Delta x$.
Consider a linear explicit scheme
$$u_j^{n+1} = \sum_{k=-K}^{K} c_k\, u_{j+k}^n, \qquad j \in \Z,$$
with real coefficients $c_k$ that depend only on $\nu$.
Call the scheme monotone if $c_k \ge 0$ for all $k$, and of order at least $2$ if
$$\sum_k c_k\, k^m = (-\nu)^m \qquad \text{for } m = 0, 1, 2.$$
If the scheme is monotone and of order at least $2$, then $\nu$ is an integer and the scheme is the exact shift $u_j^{n+1} = u_{j - \nu}^n$.
In particular, for $\nu \notin \Z$, a monotone linear scheme is at most first-order accurate.

## Remarks

The conditions for $m = 0, 1, 2$ say that the scheme is exact on polynomials of degree at most $2$, which is the same as a local truncation error $O(\Delta x^3)$ for smooth solutions.
Proof: the numbers $c_k \ge 0$ sum to $1$, so they are the weights of a probability distribution on the integers $k$, with mean $-\nu$ and second moment $\nu^2$.
So its variance is $0$, and all the weight sits on the single point $k = -\nu$, which must then be an integer.
For a linear scheme, monotone is the same as monotonicity preserving: an increasing step $u_i = 1$ for $i > J$ and $0$ otherwise gives $u_{j+1}^{n+1} - u_j^{n+1} = c_{J-j}$.
Examples: the [[upwind scheme|MTCRZC5QKT]] with $0 \le \nu \le 1$ is monotone and of first order.
The [[Lax–Wendroff method|YHZ9BCNDRZ]] is of second order, has the negative coefficient $c_1 = -\nu(1 - \nu)/2$ for $0 < \nu < 1$, and oscillates near jumps.

## Explanations

### L1 human

When a computer simulates a moving sharp front, simple schemes either smear the front or create wiggles next to it.
Godunov's theorem says that, for linear schemes, this is unavoidable: a linear scheme that never creates new wiggles is at best first-order accurate, and so it smears.
To have both sharp fronts and no wiggles, one must use schemes whose coefficients depend on the solution itself.

### L2 human

Godunov proved this in 1959, and it is the reason why modern high-resolution schemes are nonlinear.
[[Total variation diminishing|NX8RE9B72A]] schemes, flux limiters, MUSCL and ENO/WENO schemes switch to a first-order monotone flux near discontinuities and use a higher-order flux in smooth regions.
The theorem is a statement about linear schemes; it does not limit nonlinear ones, which can be second order away from extrema.