Godunov's theorem

Godunov's theorem 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.

Conteúdo 1 O teorema 2 Veja também 3 Referências 4 Further reading 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. Então se {estilo de exibição x_{j}=j,Delta x} e {displaystyle t^{n}=n,Delta t} , such a scheme can be described by {displaystyle sum limits _{m=1}^{M}{beta _{m}}varphi_{j+m}^{n+1}=soma limites _{m=1}^{M}{alfa _{m}varphi_{j+m}^{n}}.quad quad (1)} Em outras palavras, the solution {estilo de exibição varphi _{j}^{n+1}} at time {displaystyle n+1} and location {estilo de exibição j} is a linear function of the solution at the previous time step {estilo de exibição m} . We assume that {estilo de exibição beta _{m}} determines {estilo de exibição varphi _{j}^{n+1}} uniquely. Agora, since the above equation represents a linear relationship between {estilo de exibição varphi _{j}^{n}} e {estilo de exibição varphi _{j}^{n+1}} we can perform a linear transformation to obtain the following equivalent form, {estilo de exibição varphi _{j}^{n+1}=soma limites _{m}^{M}{gama _{m}varphi_{j+m}^{n}}.quad quad (2)} Teorema 1: Monotonicity preserving The above scheme of equation (2) is monotonicity preserving if and only if {displaystyle gamma _{m}geq 0,quad forall m.quad quad (3)} Prova - Godunov (1959) Caso 1: (sufficient condition) Presumir (3) applies and that {estilo de exibição varphi _{j}^{n}} is monotonically increasing with {estilo de exibição j} .

Então, Porque {estilo de exibição varphi _{j}^{n}leq varphi _{j+1}^{n}leq cdots leq varphi _{j+m}^{n}} it therefore follows that {estilo de exibição varphi _{j}^{n+1}leq varphi _{j+1}^{n+1}leq cdots leq varphi _{j+m}^{n+1}} Porque {estilo de exibição varphi _{j}^{n+1}-varphi_{j-1}^{n+1}=soma limites _{m}^{M}{gama _{m}deixei({varphi_{j+m}^{n}-varphi_{j+m-1}^{n}}certo)}geq 0.quad quad (4)} This means that monotonicity is preserved for this case.

Caso 2: (necessary condition) We prove the necessary condition by contradiction. Assuma isso {displaystyle gamma _{p}^{}<0} for some {displaystyle p} and choose the following monotonically increasing {displaystyle varphi _{j}^{n}quad } , {displaystyle varphi _{i}^{n}=0,quad i0,quad xin mathbb {R} quad quad (10)} cannot be monotonicity preserving unless {displaystyle sigma =left|cright|{{Delta t} sobre {Delta x}}em matemática {N} ,quad quad (11)} Onde {estilo de exibição sigma } is the signed Courant–Friedrichs–Lewy condition (CFL) número.

Prova - Godunov (1959) Assume a numerical scheme of the form described by equation (2) and choose {displaystyle varphi left({0,x}certo)= esquerda({{x over {Delta x}}-{1 sobre 2}}certo)^{2}-{1 sobre 4},quad varphi _{j}^{0}= esquerda({j-{1 sobre 2}}certo)^{2}-{1 sobre 4}.quad quad (12)} The exact solution is {displaystyle varphi left({t,x}certo)= esquerda({{{x-ct} sobre {Delta x}}-{1 sobre 2}}certo)^{2}-{1 sobre 4}.quad quad (13)} If we assume the scheme to be at least second-order accurate, it should produce the following solution exactly {estilo de exibição varphi _{j}^{1}= esquerda({j-sigma -{1 sobre 2}}certo)^{2}-{1 sobre 4},quad varphi _{j}^{0}= esquerda({j-{1 sobre 2}}certo)^{2}-{1 sobre 4}.quad quad (14)} Substituting into equation (2) dá: {estilo de exibição à esquerda({j-sigma -{1 sobre 2}}certo)^{2}-{1 sobre 4}=soma limites _{m}^{M}{gama _{m}deixei{{deixei({j+m-{1 sobre 2}}certo)^{2}-{1 sobre 4}}certo}}.quad quad (15)} Suppose that the scheme IS monotonicity preserving, then according to the theorem 1 acima de, {displaystyle gamma _{m}geq 0} .

Agora, it is clear from equation (15) este {estilo de exibição à esquerda({j-sigma -{1 sobre 2}}certo)^{2}-{1 sobre 4}geq 0,quad forall j.quad quad (16)} Presumir {displaystyle sigma >0,quad sigma notin mathbb {N} } and choose {estilo de exibição j} de tal modo que {displaystyle j>sigma >left(j-1right)} . This implies that {estilo de exibição à esquerda({j-sigma }certo)>0} e {estilo de exibição à esquerda({j-sigma -1}certo)<0} . It therefore follows that, {displaystyle left({j-sigma -{1 over 2}}right)^{2}-{1 over 4}=left(j-sigma right)left(j-sigma -1right)<0,quad quad (17)} which contradicts equation (16) and completes the proof. The exceptional situation whereby {displaystyle sigma =left|cright|{{Delta t} over {Delta x}}in mathbb {N} } is only of theoretical interest, since this cannot be realised with variable coefficients. Also, integer CFL numbers greater than unity would not be feasible for practical problems. See also Finite volume method Flux limiter Total variation diminishing References Godunov, Sergei K. (1954), Ph.D. Dissertation: Different Methods for Shock Waves, Moscow State University. Godunov, Sergei K. (1959), A Difference Scheme for Numerical Solution of Discontinuous Solution of Hydrodynamic Equations, Mat. Sbornik, 47, 271-306, translated US Joint Publ. Res. Service, JPRS 7226, 1969. Wesseling, Pieter (2001), Principles of Computational Fluid Dynamics, Springer-Verlag. Further reading Hirsch, C. (1990), Numerical Computation of Internal and External Flows, vol 2, Wiley. Laney, Culbert B. (1998), Computational Gas Dynamics, Cambridge University Press. Toro, E. F. (1999), Riemann Solvers and Numerical Methods for Fluid Dynamics, Springer-Verlag. Tannehill, John C., et al., (1997), Computational Fluid mechanics and Heat Transfer, 2nd Ed., Taylor and Francis. Categories: Numerical differential equationsTheorems in analysisComputational fluid dynamics