Теорема Годунова - Godunovs theorem - Wikipedia

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

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

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

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

Теорема

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

В стороне

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

${\displaystyle \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)}$

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

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

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

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

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

Доказательство - Годунов (1959)

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

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

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

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

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

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

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

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

Тогда из уравнения (2) получаем

${\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)=\left\{{\begin{array}{*{20}c}{0,}&{\left[{j+m\neq k}\right]}\\{\gamma _{m},}&{\left[{j+m=k}\right]}\\\end{array}}\right.\quad \quad (6)}$

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

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

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

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

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

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

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

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

куда ${\displaystyle \sigma }$ подписанный Условие Куранта – Фридрихса – Леви. (CFL) номер.

Доказательство - Годунов (1959)

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

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

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

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

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

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

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

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

Предположим, что схема ЯВЛЯЕТСЯ с сохранением монотонности, то по теореме 1 выше ${\displaystyle \gamma _{m}\geq 0}$.

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

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

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

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

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

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

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

Смотрите также

• Метод конечных объемов
• Ограничитель потока
• Уменьшение общей вариации

Рекомендации

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

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

• Хирш, К. (1990), Численный расчет внутренних и внешних потоков, том 2, Wiley.
• Лэйни, Калберт Б. (1998), Вычислительная газовая динамика, Издательство Кембриджского университета.
• Торо, Э.Ф. (1999), Решатели Римана и численные методы гидродинамики, Springer-Verlag.
• Таннехилл, Джон К. и др., (1997), Вычислительная механика жидкости и теплопередача, 2-е изд., Тейлор и Фрэнсис.