In numerical analysis and computational fluid dynamics, Godunov's theorem — also known as Godunov's order barrier theorem — is a mathematical theorem important in the development of the theory of high resolution schemes for the numerical solution of partial differential equations.
The theorem states that:
Linear numerical schemes for solving partial differential equations (PDE's), having the property of not generating new extrema (monotone scheme), can be at most first-order accurate.Professor Sergei K. Godunov originally proved the theorem as a Ph.D. student at Moscow State University. It is his most influential work in the area of applied and numerical mathematics and has had a major impact on science and engineering, particularly in the development of methods used in computational fluid dynamics (CFD) and other computational fields. One of his major contributions was to prove the theorem (Godunov, 1954; Godunov, 1959), that bears his name.
The theorem
We generally follow Wesseling (2001).
Aside
Assume a continuum problem described by a PDE is to be computed using a numerical scheme based upon a uniform computational grid and a one-step, constant step-size, M grid point, integration algorithm, either implicit or explicit. Then if
In other words, the solution
Theorem 1: Monotonicity preserving
The above scheme of equation (2) is monotonicity preserving if and only if
Proof - Godunov (1959)
Case 1: (sufficient condition)
Assume (3) applies and that
Then, because
This means that monotonicity is preserved for this case.
Case 2: (necessary condition)
We prove the necessary condition by contradiction. Assume that
Then from equation (2) we get
Now choose
which implies that
Theorem 2: Godunov’s Order Barrier Theorem
Linear one-step second-order accurate numerical schemes for the convection equation
cannot be monotonicity preserving unless
where
Proof - Godunov (1959)
Assume a numerical scheme of the form described by equation (2) and choose
The exact solution is
If we assume the scheme to be at least second-order accurate, it should produce the following solution exactly
Substituting into equation (2) gives:
Suppose that the scheme IS monotonicity preserving, then according to the theorem 1 above,
Now, it is clear from equation (15) that
Assume
It therefore follows that,
which contradicts equation (16) and completes the proof.
The exceptional situation whereby