Теорема Годунова - Википедия - Godunovs theorem

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

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

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

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

Теорема

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

В стороне

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

${ 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$

Тогда из уравнения (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 _ {kp} ^ {n + 1} - varphi _ {kp-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}} + с {{ 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 более 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 более 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> влево (J-1 вправо)}$ . Отсюда следует, что ${ 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- сигма -1 справа) <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-е изд., Тейлор и Фрэнсис.