Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Godunov's theorem
open-in-new
<h2 id="the-theorem">The theorem</h2> <p>We generally follow Wesseling (2001). </p><p>Aside </p><p>Assume a continuum problem described by a <a href="/facts/Partial_differential_equation/DyPsBlv7">PDE</a> is to be computed using a numerical scheme based upon a uniform computational grid and a one-step, constant step-size, <i>M</i> grid point, integration algorithm, either implicit or explicit. Then if x j = j Δ x {\displaystyle x_{j}=j\,\Delta x} and t n = n Δ t {\displaystyle t^{n}=n\,\Delta t} , such a scheme can be described by </p> <table><tbody><tr><td> ∑ m = 1 M β m φ j + m n + 1 = ∑ m = 1 M α m φ j + m n . {\displaystyle \sum _{m=1}^{M}{\beta _{m}}\varphi _{j+m}^{n+1}=\sum _{m=1}^{M}{\alpha _{m}\varphi _{j+m}^{n}}.} </td> <td></td> <td>1</td></tr></tbody></table> <p>In other words, the solution φ j n + 1 {\displaystyle \varphi _{j}^{n+1}} at time n + 1 {\displaystyle n+1} and location j {\displaystyle j} is a linear function of the solution at the previous time step n {\displaystyle n} . We assume that β m {\displaystyle \beta _{m}} determines φ j n + 1 {\displaystyle \varphi _{j}^{n+1}} uniquely. Now, since the above equation represents a linear relationship between φ j n {\displaystyle \varphi _{j}^{n}} and φ j n + 1 {\displaystyle \varphi _{j}^{n+1}} we can perform a linear transformation to obtain the following equivalent form, </p> <table><tbody><tr><td> φ j n + 1 = ∑ m M γ m φ j + m n . {\displaystyle \varphi _{j}^{n+1}=\sum \limits _{m}^{M}{\gamma _{m}\varphi _{j+m}^{n}}.} </td> <td></td> <td>2</td></tr></tbody></table> <p>Theorem 1: <i>Monotonicity preserving</i> </p><p>The above scheme of equation (2) is monotonicity preserving if and only if </p> <table><tbody><tr><td> γ m ≥ 0 , ∀ m . {\displaystyle \gamma _{m}\geq 0,\quad \forall m.} </td> <td></td> <td>3</td></tr></tbody></table> <p><i>Proof</i> - Godunov (1959) </p><p>Case 1: (sufficient condition) </p><p>Assume (3) applies and that φ j n {\displaystyle \varphi _{j}^{n}} is monotonically increasing with j {\displaystyle j} . </p><p>Then, because φ j n ≤ φ j + 1 n ≤ ⋯ ≤ φ j + m n {\displaystyle \varphi _{j}^{n}\leq \varphi _{j+1}^{n}\leq \cdots \leq \varphi _{j+m}^{n}} it therefore follows that φ j n + 1 ≤ φ j + 1 n + 1 ≤ ⋯ ≤ φ j + m n + 1 {\displaystyle \varphi _{j}^{n+1}\leq \varphi _{j+1}^{n+1}\leq \cdots \leq \varphi _{j+m}^{n+1}} because </p> <table><tbody><tr><td> φ j n + 1 − φ j − 1 n + 1 = ∑ m M γ m ( φ j + m n − φ j + m − 1 n ) ≥ 0. {\displaystyle \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)}\geq 0.} </td> <td></td> <td>4</td></tr></tbody></table> <p>This means that monotonicity is preserved for this case. </p><p>Case 2: (necessary condition) </p><p>We prove the necessary condition by contradiction. Assume that γ p < 0 {\displaystyle \gamma _{p}^{}<0} for some p {\displaystyle p} and choose the following monotonically increasing φ j n {\displaystyle \varphi _{j}^{n}\,} , </p> <table><tbody><tr><td> φ i n = 0 , i < k ; φ i n = 1 , i ≥ k . {\displaystyle \varphi _{i}^{n}=0,\quad i<k;\quad \varphi _{i}^{n}=1,\quad i\geq k.} </td> <td></td> <td>5</td></tr></tbody></table> <p>Then from equation (2) we get </p> <table><tbody><tr><td> φ j n + 1 − φ j − 1 n + 1 = ∑ m M γ m ( φ j + m n − φ j + m − 1 n ) = { 0 , j + m ≠ k γ m , j + m = k {\displaystyle \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)={\begin{cases}0,&j+m\neq k\\\gamma _{m},&j+m=k\\\end{cases}}} </td> <td></td> <td>6</td></tr></tbody></table> <p>Now choose j = k − p {\displaystyle j=k-p} , to give </p> <table><tbody><tr><td> φ k − p n + 1 − φ k − p − 1 n + 1 = γ p ( φ k n − φ k − 1 n ) < 0 , {\displaystyle \varphi _{k-p}^{n+1}-\varphi _{k-p-1}^{n+1}={\gamma _{p}\left({\varphi _{k}^{n}-\varphi _{k-1}^{n}}\right)}<0,} </td> <td></td> <td>7</td></tr></tbody></table> <p>which implies that φ j n + 1 {\displaystyle \varphi _{j}^{n+1}} is NOT increasing, and we have a contradiction. Thus, monotonicity is NOT preserved for γ p < 0 {\displaystyle \gamma _{p}<0} , which completes the proof. </p><p>Theorem 2: <i>Godunov’s Order Barrier Theorem</i> </p><p>Linear one-step second-order accurate numerical schemes for the convection equation </p> <table><tbody><tr><td> ∂ φ ∂ t + c ∂ φ ∂ x = 0 , t > 0 , x ∈ R {\displaystyle {{\partial \varphi } \over {\partial t}}+c{{\partial \varphi } \over {\partial x}}=0,\quad t>0,\quad x\in \mathbb {R} } </td> <td></td> <td>10</td></tr></tbody></table> <p>cannot be monotonicity preserving unless </p> <table><tbody><tr><td> σ = | c | Δ t Δ x ∈ N , {\displaystyle \sigma =\left|c\right|{{\Delta t} \over {\Delta x}}\in \mathbb {N} ,} </td> <td></td> <td>11</td></tr></tbody></table> <p>where σ {\displaystyle \sigma } is the signed <a href="/facts/Courant%E2%80%93Friedrichs%E2%80%93Lewy_condition/f4r00Wca">Courant–Friedrichs–Lewy condition</a> (CFL) number. </p><p><i>Proof</i> - Godunov (1959) </p><p>Assume a numerical scheme of the form described by equation (2) and choose </p> <table><tbody><tr><td> φ ( 0 , x ) = ( x Δ x − 1 2 ) 2 − 1 4 , φ j 0 = ( j − 1 2 ) 2 − 1 4 . {\displaystyle \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}.} </td> <td></td> <td>12</td></tr></tbody></table> <p>The exact solution is </p> <table><tbody><tr><td> φ ( t , x ) = ( x − c t Δ x − 1 2 ) 2 − 1 4 . {\displaystyle \varphi \left({t,x}\right)=\left({{{x-ct} \over {\Delta x}}-{1 \over 2}}\right)^{2}-{1 \over 4}.} </td> <td></td> <td>13</td></tr></tbody></table> <p>If we assume the scheme to be at least second-order accurate, it should produce the following solution exactly </p> <table><tbody><tr><td> φ j 1 = ( j − σ − 1 2 ) 2 − 1 4 , φ j 0 = ( j − 1 2 ) 2 − 1 4 . {\displaystyle \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}.} </td> <td></td> <td>14</td></tr></tbody></table> <p>Substituting into equation (2) gives: </p> <table><tbody><tr><td> ( j − σ − 1 2 ) 2 − 1 4 = ∑ m M γ m { ( j + m − 1 2 ) 2 − 1 4 } . {\displaystyle \left({j-\sigma -{1 \over 2}}\right)^{2}-{1 \over 4}=\sum \limits _{m}^{M}{\gamma _{m}\left\{{\left({j+m-{1 \over 2}}\right)^{2}-{1 \over 4}}\right\}}.} </td> <td></td> <td>15</td></tr></tbody></table> <p>Suppose that the scheme IS monotonicity preserving, then according to the theorem 1 above, γ m ≥ 0 {\displaystyle \gamma _{m}\geq 0} . </p><p>Now, it is clear from equation (15) that </p> <table><tbody><tr><td> ( j − σ − 1 2 ) 2 − 1 4 ≥ 0 , ∀ j . {\displaystyle \left({j-\sigma -{1 \over 2}}\right)^{2}-{1 \over 4}\geq 0,\quad \forall j.} </td> <td></td> <td>16</td></tr></tbody></table> <p>Assume σ > 0 , σ ∉ N {\displaystyle \sigma >0,\quad \sigma \notin \mathbb {N} } and choose j {\displaystyle j} such that j > σ > ( j − 1 ) {\displaystyle j>\sigma >\left(j-1\right)} . This implies that ( j − σ ) > 0 {\displaystyle \left({j-\sigma }\right)>0} and ( j − σ − 1 ) < 0 {\displaystyle \left({j-\sigma -1}\right)<0} . </p><p>It therefore follows that, </p> <table><tbody><tr><td> ( j − σ − 1 2 ) 2 − 1 4 = ( j − σ ) ( j − σ − 1 ) < 0 , {\displaystyle \left({j-\sigma -{1 \over 2}}\right)^{2}-{1 \over 4}=\left(j-\sigma \right)\left(j-\sigma -1\right)<0,} </td> <td></td> <td>17</td></tr></tbody></table> <p>which contradicts equation (16) and completes the proof. </p><p>The exceptional situation whereby σ = | c | Δ t Δ x ∈ N {\displaystyle \sigma =\left|c\right|{{\Delta t} \over {\Delta x}}\in \mathbb {N} } is only of theoretical interest, since this cannot be realised with variable coefficients. Also, integer <a href="/facts/Courant%E2%80%93Friedrichs%E2%80%93Lewy_condition/f4r00Wca">CFL</a> numbers greater than unity would not be feasible for practical problems. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Finite_volume_method/6JfQMucX">Finite volume method</a></li> <li><a href="/facts/Flux_limiter/vWBzcJx0">Flux limiter</a></li> <li><a href="/facts/Total_variation_diminishing/BxKKPAkR">Total variation diminishing</a></li></ul> <ul><li>Godunov, Sergei K. (1954), <i>Ph.D. Dissertation: Different Methods for Shock Waves</i>, Moscow State University.</li> <li>Godunov, Sergei K. (1959), A Difference Scheme for Numerical Solution of Discontinuous Solution of Hydrodynamic Equations, <i>Mat. Sbornik, 47, 271-306</i>, translated US Joint Publ. Res. Service, JPRS 7226, 1969.</li> <li>Wesseling, Pieter (2001). <a href="https://www.worldcat.org/oclc/44972030"><i>Principles of Computational Fluid Dynamics</i></a>. Berlin: Springer-Verlag. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9783540678533. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/44972030">44972030</a>.</li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Hirsch, Ch (1990). <a href="https://www.worldcat.org/oclc/16523972"><i>Numerical Computation of Internal and External Flows</i></a>. Vol. 2. Chichester [England]: Wiley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-91762-1. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/16523972">16523972</a>.</li> <li>Laney, Culbert B. (1998). <a href="https://www.worldcat.org/oclc/664017316"><i>Computational Gasdynamics</i></a>. Cambridge: Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-511-77720-2. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/664017316">664017316</a>.</li> <li>Toro, Elewterio F. (2009). <a href="https://www.worldcat.org/oclc/391057413"><i>Riemann Solvers and Numerical Methods for Fluid Dynamics a Practical Introduction</i></a> (3rd ed.). Berlin. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-25202-3. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/391057413">391057413</a>.{{cite book}}: CS1 maint: location missing publisher (link)</li> <li>Anderson, Dale A.; Tannehill, John C.; Pletcher, Richard H.; Munipalli, Ramakanth; Shankar, Vijaya (2020). <a href="https://www.worldcat.org/oclc/1237821271"><i>Computational Fluid Mechanics and Heat Transfer</i></a> (Fourth ed.). Boca Raton, FL: Taylor & Francis. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-351-12400-3. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/1237821271">1237821271</a>.</li></ul>