Godunovs teorem

Inom numerisk analys och beräkningsvätskedynamik är Godunovs sats - även känd som Godunovs ordningsbarriärsats - en matematisk sats som är viktig i utvecklingen av teorin om högupplösningsscheman för den numeriska lösningen av partiella differentialekvationer .

Teoremet säger att:

Linjära numeriska scheman för att lösa partiella differentialekvationer (PDE), som har egenskapen att inte generera nya extrema (monotone scheman), kan vara högst första ordningens korrekta.

Professor Sergei K. Godunov bevisade ursprungligen teoremet som en doktorsexamen. student vid Moscow State University . Det är hans mest inflytelserika arbete inom området tillämpad och numerisk matematik och har haft en stor inverkan på naturvetenskap och ingenjörsvetenskap, särskilt i utvecklingen av metoder som används inom beräkningsvätskedynamik (CFD) och andra beräkningsområden. Ett av hans viktigaste bidrag var att bevisa satsen (Godunov, 1954; Godunov, 1959), som bär hans namn.

Teoremet

Vi följer i allmänhet Wesseling (2001).

Åt sidan

Antag att ett kontinuumproblem som beskrivs av en PDE ska beräknas med användning av ett numeriskt schema baserat på ett enhetligt beräkningsrutnät och en enstegs, konstant stegstorlek, M rutnätspunkt, integrationsalgoritm, antingen implicit eller explicit. Sedan om $x_{j}=j\,\Delta x$ och $t^{n}=n\,\Delta t$ , ett sådant schema kan beskrivas av

$\sum \limits _{m=1}^{M}{\beta _{m}}\varphi _{j+m}^{n+1}=\sum \limits _{m =1}^{M}{\alpha _{m}\varphi _{j+m}^{n}}.\quad \quad (1)$

Med andra ord är lösningen $\varphi _{j}^{n+1}$ vid tidpunkten $n+1$ och plats $j$ en linjär funktion av lösningen vid föregående tidssteg $n$ . Vi antar att $\beta _{m}$ bestämmer $\varphi _{j}^{n+1}$ unikt. Eftersom ovanstående ekvation representerar ett linjärt samband mellan $\varphi _{j}^{n}$ och $\varphi _{j}^{n+1}$ vi kan utföra en linjär transformation för att erhålla följande ekvivalenta form,

$\varphi _{j}^{n+1}=\sum \limits _{m}^{M}{\gamma _{m}\varphi _{j+m}^{n} }.\quad \quad (2)$

Sats 1: Monotonicitetsbevarande

Ovanstående schema i ekvation (2) är monotoni som bevarar om och endast om

$\gamma _{m}\geq 0,\quad \forall m.\quad \quad (3)$

Bevis - Godunov (1959)

Fall 1: (tillräckligt skick)

Antag att (3) gäller och att $\varphi _{j}^{n}$ ökar monotont med $j$ .

Sedan, eftersom $\varphi _{j}^{n}\leq \varphi _{j+1}^{n}\leq \ cdots \leq \varphi _{j+m}^{n}$ det följer därför att $\varphi _{ j}^{n+1}\leq \varphi _{j+1}^{n+1}\leq \cdots \leq \varphi _{j+m}^{n+1}$ eftersom

$\varphi _{j}^ {n+1}-\varphi _{j-1}^{n+1}=\summa \limits _{m}^{M}{\gamma _{m}\left({\varphi _{j+ m}^{n}-\varphi _{j+m-1}^{n}}\right)}\geq 0.\quad \quad (4)$

Detta innebär att monotoniteten bevaras för detta fall.

Fall 2: (nödvändigt villkor)

Vi bevisar det nödvändiga villkoret genom motsägelse. Antag att $\gamma _{p}^{}<0$ för vissa $p$ och välj följande monotont ökande $\varphi _{j}^{n} \quad$ ,

$\varphi _{i}^{n}=0,\quad i<k;\quad \varphi _{i}^{n}=1,\quad i\geq k.\quad \ fyrhjuling (5)$

Sedan får vi från ekvation (2).

$\varphi _{j}^{n+1}-\varphi _{j-1}^{n+1}=\sum \limits _{m}^{M} {\gamma _{m}}\left({\varphi _{j+m}^{n}-\varphi _{j+m-1}^{n}}\right)=\left\{{\ börja{array}{*{20}c}{0,}&{\left[{j+m\neq k}\right]}\\{\gamma _{m},}&{\left[{j +m=k}\right]}\\\end{array}}\right.\quad \quad (6)$

Välj nu $j=kp$ , för att ge

$\varphi _{kp}^{n+1 }-\varphi _{kp-1}^{n+1}={\gamma _{p}\left({\varphi _{k}^{n}-\varphi _{k-1}^{n }}\right)}<0,\quad \quad (7)$

vilket innebär att $\varphi _{j}^{n+1}$ INTE ökar , och vi har en motsägelse. Således inte monotoniteten för ${\displaystyle \gamma _{p}<0} ,$ vilket fullbordar beviset.

Sats 2: Godunovs ordningsbarriärsats

Linjära enstegs andra ordningens noggranna numeriska scheman för konvektionsekvationen

${{\partial \varphi } \over {\partial t}}+c{{\partial \varphi } \over {\partial x}}=0,\quad t>0,\quad x\in \mathbb {R} \quad \quad (10)$

kan inte vara monotonisk bevarande om inte

$\sigma =\left|c\right|{{\Delta t} \över {\Delta x}}\in \mathbb {N} ,\quad \quad ( 11)$

där $\sigma$ är det undertecknade Courant–Friedrichs–Lewy condition- numret (CFL).

Bevis - Godunov (1959)

Antag ett numeriskt schema av den form som beskrivs av ekvation (2) och välj

$\varphi \left({0,x}\right)=\left({{x \over {\Delta x}}-{1 \over 2}}\right)^{2}- {1 \over 4},\quad \varphi _{j}^{0}=\left({j-{1 \over 2}}\right)^{2}-{1 \over 4}.\quad \quad (12)$

Den exakta lösningen är

$\varphi \left({t,x}\right)=\left({{{x-ct} \over {\Delta x}}-{1 \over 2}}\right)^ {2}-{1 \över 4}.\quad \quad (13)$

Om vi ​​antar att schemat är åtminstone andra ordningens korrekt, bör det producera följande lösning exakt

$\varphi _{j}^{1}=\left({j-\sigma -{1 \over 2}}\right)^{2}-{1 \over 4},\quad \varphi _{j}^{0}=\left({j-{1 \over 2}}\right)^{2}-{1 \over 4}.\quad \quad (14)$

Substitution i ekvation (2) ger:

$\left({j-\sigma -{1 \over 2}}\right)^{2}-{1 \over 4}=\summa \limits _{m}^{M}{ \gamma _{m}\left\{{\left({j+m-{1 \over 2}}\right)^{2}-{1 \over 4}}\right\}}.\quad \ fyrhjuling (15)$

Antag att schemat ÄR monotonisk bevarande, då enligt sats 1 ovan, $\gamma _{m}\geq 0$ .

Nu är det klart från ekvation (15) att

$\left({j-\sigma -{1 \over 2}}\right)^{2}-{1 \over 4}\geq 0,\quad \forall j.\quad \quad (16)$

Antag $\sigma >0,\quad \sigma \notin \mathbb {N}$ och välj $j$ så att $j >\sigma >\left(j-1\right)$ . Detta innebär att $\left({j-\sigma }\right)>0$ och $\left({j-\sigma -1} \right)<0$ .

Det följer därför att,

$\left({j-\sigma -{1 \over 2}}\ höger)^{2}-{1 \över 4}=\left(j-\sigma \right)\left(j-\sigma -1\right)<0,\quad \quad (17)$

som motsäger ekvation (16) och kompletterar beviset.

Den exceptionella situationen där ${\displaystyle \sigma =\left|c\right|{{\Delta t} \over {\Delta x}}\in \mathbb {N} } är endast av teoretiskt intresse, eftersom detta inte$ kan realiseras med variabla koefficienter. Dessutom skulle heltals CFL- tal större än enhet inte vara genomförbara för praktiska problem.

Se även

• Metod med ändlig volym
• Fluxbegränsare
• Total variation minskar

• Godunov, Sergei K. (1954), Ph.D. Avhandling: Different Methods for Shock Waves, Moscow State University.
• Godunov, Sergei K. (1959), Ett skillnadsschema för numerisk lösning av diskontinuerlig lösning av hydrodynamiska ekvationer, Mat. Sbornik, 47, 271-306 , översatt US Joint Publ. Res. Service, JPRS 7226, 1969.
• Wesseling, Pieter (2001), Principles of Computational Fluid Dynamics , Springer-Verlag.

Vidare läsning

• Hirsch, C. (1990), Numerical Computation of Internal and External Flows , vol 2, Wiley.
• Laney, Culbert B. (1998), Computational Gas Dynamics , Cambridge University Press.
• Toro, EF (1999), Riemann Solvers and Numerical Methods for Fluid Dynamics, Springer-Verlag.
• Tannehill, John C., et al., (1997), Computational Fluid mechanics and Heat Transfer , 2:a upplagan, Taylor och Francis.