Godunov's theorem

В численном анализе и вычислительной гидродинамике , теорема Годунова также известная как теорема о барьере порядка Годунова , является математической теоремой, важной в развитии теории схем высокого разрешения для численного решения уравнений в частных производных .

Теорема утверждает, что:

Линейные численные схемы решения уравнений в частных производных (ЧДУ), обладающие свойством не генерировать новые экстремумы ( монотонные схемы ), могут иметь точность не более первого порядка.

Профессор Сергей Годунов первоначально доказал эту теорему в качестве доктора философии. студент Московского государственного университета . Это его самая влиятельная работа в области прикладной и численной математики, которая оказала большое влияние на науку и технику, особенно на разработку методов, используемых в вычислительной гидродинамике (CFD) и других вычислительных областях. Одним из его крупнейших вкладов было доказательство теоремы (Годунов, 1954; Годунов, 1959), носящей его имя.

Теорема

Обычно мы следуем Весселингу (2001).

В сторону

Предположим, что непрерывная задача, описываемая PDE, должна быть вычислена с использованием числовой схемы, основанной на однородной вычислительной сетке и одношаговом алгоритме интегрирования с постоянным размером шага и точкой сетки M , как неявном, так и явном. Тогда, если $x_{j}=j\,\Delta x$ и $t^{n}=n\,\Delta t$, такую ​​схему можно описать формулой

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

Другими словами, решение $\varphi _{j}^{n+1}$ во время $n+1$ и расположение $j$ является линейной функцией решения на предыдущем временном шаге $n$. Мы предполагаем, что $\beta _{m}$ определяет $\varphi _{j}^{n+1}$ однозначно. Теперь, поскольку приведенное выше уравнение представляет собой линейную зависимость между $\varphi _{j}^{n}$ и $\varphi _{j}^{n+1}$ мы можем выполнить линейное преобразование, чтобы получить следующую эквивалентную форму:

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

Теорема 1: Сохранение монотонности

Приведенная выше схема уравнения (2) сохраняет монотонность тогда и только тогда, когда

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

Proof - Godunov (1959)

Случай 1: (достаточное условие)

Предположим, что (3) применимо и что $\varphi _{j}^{n}$ монотонно возрастает с $j$.

Тогда, потому что $\varphi _{j}^{n}\leq \varphi _{j+1}^{n}\leq \cdots \leq \varphi _{j+m}^{n}$ следовательно, следует, что $\varphi _{j}^{n+1}\leq \varphi _{j+1}^{n+1}\leq \cdots \leq \varphi _{j+m}^{n+1}$ потому что

$$\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.$$ ( 4 )

Это означает, что монотонность в этом случае сохраняется.

Случай 2: (необходимое условие)

Необходимое условие докажем от противного. Предположим, что $\gamma _{p}^{}<0$ для некоторых $p$ и выберем следующие монотонно возрастающие $\varphi _{j}^{n}\,$,

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

Тогда из уравнения (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)={\begin{cases}0,&j+m\neq k\\\gamma _{m},&j+m=k\\\end{cases}}$$ ( 6 )

Теперь выберите $j=k-p$, дать

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

что подразумевает, что $\varphi _{j}^{n+1}$ НЕ увеличивается , и мы имеем противоречие. Таким образом, монотонность НЕ сохраняется для $\gamma _{p}<0$, что завершает доказательство.

Теорема 2: Теорема Годунова о барьере порядка

Линейные одношаговые численные схемы второго порядка точности для уравнения конвекции

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

не может сохранять монотонность, если

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

где $\sigma$ – это число условия Куранта – Фридрихса – Леви (CFL) со знаком.

Proof - Godunov (1959)

Предположим, что имеется численная схема вида, описываемого уравнением (2), и выберите

$$\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}.$$ ( 12 )

Точное решение

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

Если предположить, что схема имеет точность не менее второго порядка, она должна дать точно следующее решение:

$$\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}.$$ ( 14 )

Подстановка в уравнение (2) дает:

$$\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\}}.$$ ( 15 )

Предположим, что схема сохраняет монотонность, тогда согласно теореме 1, приведенной выше, $\gamma _{m}\geq 0$.

Теперь из уравнения (15) ясно, что

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

Предполагать $\sigma >0,\quad \sigma \notin \mathbb {N}$ и выбери $j$ такой, что $j>\sigma >\left(j-1\right)$. Это подразумевает, что $\left({j-\sigma }\right)>0$ и $\left({j-\sigma -1}\right)<0$.

Отсюда следует, что

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

что противоречит уравнению (16) и завершает доказательство.

Исключительная ситуация, когда $\sigma =\left|c\right|{{\Delta t} \over {\Delta x}}\in \mathbb {N}$ представляет лишь теоретический интерес, поскольку это невозможно реализовать с переменными коэффициентами. Кроме того, целые числа КЛЛ, большие единицы, не подходят для практических задач.

См. также

• Метод конечного объема
• Предел потока
• Общая вариация уменьшается

Ссылки

• Годунов Сергей Константинович (1954), к.т.н. Диссертация: Различные методы исследования ударных волн , Московский государственный университет.
• Годунов, Сергей К. (1959), Разностная схема для численного решения разрывного решения гидродинамических уравнений, Матем. Sbornik, 47, 271-306 , перевод US Joint Publ. Рез. Служба, JPRS 7226, 1969 г.
• Весселинг, Питер (2001). Принципы вычислительной гидродинамики . Берлин: Springer Verlag. ISBN  9783540678533 . ОСЛК   44972030 .

Дальнейшее чтение

• Хирш, Ч. (1990). Численный расчет внутренних и внешних потоков . Том. 2. Чичестер [Англия]: Уайли. ISBN  0-471-91762-1 . OCLC   16523972 .
• Лэйни, Калберт Б. (1998). Вычислительная газодинамика . Кембридж: Издательство Кембриджского университета. ISBN  978-0-511-77720-2 . OCLC   664017316 .
• Торо, Эльютерио Ф. (2009). Решатели Римана и численные методы гидродинамики: практическое введение (3-е изд.). Берлин. ISBN  978-3-540-25202-3 . OCLC   391057413 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
• Андерсон, Дейл А.; Таннехилл, Джон К.; Плетчер, Ричард Х.; Мунипалли, Рамакант; Шанкар, Виджая (2020). Вычислительная механика жидкости и теплопередача (Четвертое изд.). Бока-Ратон, Флорида: Тейлор и Фрэнсис. ISBN  978-1-351-12400-3 . OCLC   1237821271 .