Метод конечных разностей - Википедия - Finite difference method

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья ведущий раздел может быть слишком коротким и неадекватно подвести итог ключевые моменты его содержания. Пожалуйста, подумайте о расширении интереса до предоставить доступный обзор обо всех важных аспектах статьи. (Апрель 2015 г.) Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Апрель 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья тон или стиль могут не отражать энциклопедический тон используется в Википедии. См. Википедию руководство по написанию лучших статей для предложений. (Июнь 2020 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

Дифференциальные уравнения
Дифференциальные уравнения Навье – Стокса. используется для имитации воздушного потока вокруг препятствия.
Объем Естественные науки Инженерное дело Астрономия Физика Химия Биология Геология Прикладная математика Механика сплошной среды Теория хаоса Динамические системы Социальные науки Экономика Динамика населения
Классификация
Типы Обычный Частичное Дифференциально-алгебраический Интегро-дифференциал Дробное Линейный Нелинейный По типу переменной Зависимые и независимые переменные Автономный Сложный Связанный / развязанный Точный Однородный  / Неоднородный Функции Заказ Оператор Обозначение
Отношение к процессам Разница (дискретный аналог) Стохастик Стохастический частичный Задерживать
Решение
Существование и уникальность Теорема Пикара – Линделёфа Теорема существования Пеано Теорема существования Каратеодори Теорема Коши – Ковалевского
Общие темы Вронскиан Фазовый портрет Фазовое пространство Ляпунов  / Асимптотический  / Экспоненциальная стабильность Скорость сходимости Серии / Комплексные решения Численное интегрирование Дельта-функция Дирака
Методы решения Осмотр Метод характеристик Эйлер Формула экспоненциального отклика Конечная разница  (Крэнк – Николсон ) Заключительный элемент Бесконечный элемент Конечный объем Галеркин Петров – Галеркин Интегрирующий фактор Интегральные преобразования Теория возмущений Рунге-Кутта Разделение переменных Неопределенные коэффициенты Вариация параметров
Люди Исаак Ньютон Готфрид Лейбниц Леонард Эйлер Эмиль Пикар Юзеф Мария Хене-Вроньски Эрнст Линделёф Рудольф Липшиц Огюстен-Луи Коши Джон Крэнк Филлис Николсон Карл Давид Толме Рунге Мартин Кутта

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

Конвертация методов конечных разностей обыкновенные дифференциальные уравнения (ODE) или уравнения в частных производных (PDE), который может быть нелинейный, в система линейных уравнений это может быть решено методами матричной алгебры. Современные компьютеры могут выполнять эти линейная алгебра вычислений, которые, наряду с их относительной простотой реализации, привели к широкому использованию FDM в современном численном анализе.^[1]Сегодня FDM являются одним из наиболее распространенных подходов к численному решению PDE, наряду с методы конечных элементов.^[1]

Вывод из полинома Тейлора

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

${ displaystyle f (x_ {0} + h) = f (x_ {0}) + { frac {f '(x_ {0})} {1!}} h + { frac {f ^ {(2) } (x_ {0})} {2!}} h ^ {2} + cdots + { frac {f ^ {(n)} (x_ {0})} {n!}} h ^ {n} + R_ {n} (x),}$

куда п! обозначает факториал из п, и р_п(Икс) - остаточный член, обозначающий разницу между полиномом Тейлора степени п и исходная функция. Мы получим приближение для первой производной функции "f", сначала усекая многочлен Тейлора:

${ displaystyle f (x_ {0} + h) = f (x_ {0}) + f '(x_ {0}) h + R_ {1} (x),}$

Настройка, x₀= a имеем,

${ Displaystyle f (a + h) = f (a) + f '(a) h + R_ {1} (x),}$

Разделение на час дает:

${ Displaystyle {е (а + ч) над ч} = {е (а) над ч} + е '(а) + {R_ {1} (х) над ч}}$

Решение для f '(a):

${ displaystyle f '(a) = {f (a + h) -f (a) over h} - {R_ {1} (x) over h}}$

При условии, что ${ Displaystyle R_ {1} (х)}$ достаточно мало, аппроксимация первой производной от "f" равна:

${ displaystyle f '(a) приблизительно {f (a + h) -f (a) over h}.}$

Это не случайно похоже на определение производной, которое дается как:

${ displaystyle f '(a) = lim _ {h to 0} { frac {f (a + h) -f (a)} {h}}.}$

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

Точность и порядок

Погрешность решения метода определяется как разница между приближением и точным аналитическим решением. Двумя источниками ошибок в методах конечных разностей являются: ошибка округления, потеря точности из-за компьютерного округления десятичных величин, и ошибка усечения или же ошибка дискретизации, разница между точным решением исходного дифференциального уравнения и точной величиной при условии точной арифметики (то есть без округления).

Метод конечных разностей основан на дискретизации функции на сетке.

Чтобы использовать метод конечных разностей для аппроксимации решения проблемы, необходимо сначала дискретизировать область проблемы. Обычно это делается путем разделения домена на однородную сетку (см. Изображение справа). Это означает, что конечно-разностные методы производят наборы дискретных численных приближений производной, часто «ступенчато по времени».

Выражением всеобщего интереса является локальная ошибка усечения метода. Обычно выражается с помощью Обозначение Big-O, локальная ошибка усечения относится к ошибке из-за одного применения метода. То есть это количество ${ displaystyle f '(x_ {i}) - f' _ {i}}$ если ${ displaystyle f '(x_ {i})}$ относится к точному значению и ${ displaystyle f '_ {i}}$ в численном приближении. Остаточный член полинома Тейлора удобен для анализа локальной ошибки усечения. Используя форму Лагранжа остатка от полинома Тейлора для ${ displaystyle f (x_ {0} + h)}$, который

${ Displaystyle R_ {n} (x_ {0} + h) = { frac {f ^ {(n + 1)} ( xi)} {(n + 1)!}} (h) ^ {n + 1}}$, куда ${ displaystyle x_ {0} < xi$,

может быть обнаружен доминирующий член локальной ошибки усечения. Например, снова используя формулу прямой разности для первой производной, зная, что ${ Displaystyle f (x_ {i}) = f (x_ {0} + ih)}$,

${ Displaystyle f (x_ {0} + ih) = f (x_ {0}) + f '(x_ {0}) ih + { frac {f' '( xi)} {2!}} (ih) ^ {2},}$

и с некоторыми алгебраическими манипуляциями это приводит к

${ displaystyle { frac {f (x_ {0} + ih) -f (x_ {0})} {ih}} = f '(x_ {0}) + { frac {f' '( xi) } {2!}} Ай,}$

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

${ displaystyle { frac {f (x_ {0} + ih) -f (x_ {0})} {ih}} = f '(x_ {0}) + O (h).}$

Это означает, что в этом случае локальная ошибка усечения пропорциональна размерам шага. Качество и продолжительность моделируемого решения FDM зависит от выбора уравнения дискретизации и размеров шага (временные и пространственные шаги). Качество данных и продолжительность моделирования значительно увеличиваются при меньшем размере шага.^[2] Следовательно, для практического использования необходим разумный баланс между качеством данных и продолжительностью моделирования. Большие временные шаги полезны для увеличения скорости моделирования на практике. Однако слишком большие временные шаги могут создать нестабильность и повлиять на качество данных.^[3][4]

В фон Нейман и Курант-Фридрихс-Леви критерии часто оцениваются для определения устойчивости численной модели.^[3][4][5][6]

Пример: обыкновенное дифференциальное уравнение

Например, рассмотрим обыкновенное дифференциальное уравнение

${ Displaystyle и '(х) = 3u (х) +2. ,}$

В Метод Эйлера для решения этого уравнения используется коэффициент конечных разностей

${ Displaystyle { гидроразрыва {и (х + ч) -у (х)} {ч}} приблизительно и '(х)}$

чтобы аппроксимировать дифференциальное уравнение, сначала подставив его вместо u '(x), затем применив небольшую алгебру (умножив обе части на h, а затем добавив u (x) к обеим сторонам), чтобы получить

${ Displaystyle и (х + ч) = и (х) + час (3u (х) +2). ,}$

Последнее уравнение является конечно-разностным уравнением, и решение этого уравнения дает приближенное решение дифференциального уравнения.

Пример: уравнение теплопроводности

Рассмотрим нормализованный уравнение теплопроводности в одном измерении, с однородным Граничные условия Дирихле

${ Displaystyle U_ {t} = U_ {xx} ,}$

${ Displaystyle U (0, t) = U (1, t) = 0 ,}$ (граничное условие)

${ Displaystyle U (х, 0) = U_ {0} (х) ,}$ (начальное состояние)

Один из способов численного решения этого уравнения - аппроксимировать все производные конечными разностями. Разделим область в пространстве сеткой ${ displaystyle x_ {0}, ..., x_ {J}}$ и вовремя используя сетку ${ displaystyle t_ {0}, ...., t_ {N}}$. Мы предполагаем однородное разделение как в пространстве, так и во времени, поэтому разница между двумя последовательными точками пространства будет час и между двумя последовательными моментами времени будет k. Точки

${ displaystyle u (x_ {j}, t_ {n}) = u_ {j} ^ {n}}$

будет представлять собой численное приближение ${ displaystyle u (x_ {j}, t_ {n}).}$

Явный метод

В трафарет для наиболее распространенного явного метода для уравнения теплопроводности.

Используя форвардная разница вовремя ${ displaystyle t_ {n}}$ и второго порядка центральная разница для пространственной производной в позиции ${ displaystyle x_ {j}}$ (FTCS ) получаем рекуррентное уравнение:

${ displaystyle { frac {u_ {j} ^ {n + 1} -u_ {j} ^ {n}} {k}} = { frac {u_ {j + 1} ^ {n} -2u_ {j } ^ {n} + u_ {j-1} ^ {n}} {h ^ {2}}}. ,}$

Это явный метод для решения одномерной уравнение теплопроводности.

Мы можем получить ${ displaystyle u_ {j} ^ {n + 1}}$ от других значений таким образом:

${ displaystyle u_ {j} ^ {n + 1} = (1-2r) u_ {j} ^ {n} + ru_ {j-1} ^ {n} + ru_ {j + 1} ^ {n}}$

куда ${ displaystyle r = k / h ^ {2}.}$

Итак, с этим рекуррентным соотношением и зная значения во время п, можно получить соответствующие значения в момент времени п+1. ${ displaystyle u_ {0} ^ {n}}$ и ${ displaystyle u_ {J} ^ {n}}$ необходимо заменить граничными условиями, в этом примере они оба равны 0.

Этот явный метод известен как численно стабильный и сходящийся в любое время ${ displaystyle r leq 1/2}$.^[7] Численные ошибки пропорциональны шагу по времени и квадрату шага по пространству:

${ Displaystyle Delta и = О (К) + О (час ^ {2}) ,}$

Неявный метод

Шаблон неявного метода.

Если мы используем обратная разница вовремя ${ displaystyle t_ {n + 1}}$ и центральная разность второго порядка для пространственной производной в позиции ${ displaystyle x_ {j}}$ (Обратное время, метод центрированного пространства "BTCS") мы получаем рекуррентное уравнение:

${ displaystyle { frac {u_ {j} ^ {n + 1} -u_ {j} ^ {n}} {k}} = { frac {u_ {j + 1} ^ {n + 1} -2u_ {j} ^ {n + 1} + u_ {j-1} ^ {n + 1}} {h ^ {2}}}. ,}$

Это неявный метод для решения одномерного уравнение теплопроводности.

Мы можем получить ${ displaystyle u_ {j} ^ {n + 1}}$ от решения системы линейных уравнений:

${ displaystyle (1 + 2r) u_ {j} ^ {n + 1} -ru_ {j-1} ^ {n + 1} -ru_ {j + 1} ^ {n + 1} = u_ {j} ^ {n}}$

Схема всегда численно стабильный и сходящийся, но обычно более интенсивный в числовом отношении, чем явный метод, поскольку он требует решения системы численных уравнений на каждом временном шаге. Ошибки линейны по временному шагу и квадратичны по пространственному шагу:

${ Displaystyle Delta и = О (К) + О (час ^ {2}). ,}$

Метод Кранка – Николсона

Наконец, если мы используем центральную разницу во времени ${ displaystyle t_ {n + 1/2}}$ и центральная разность второго порядка для пространственной производной в позиции ${ displaystyle x_ {j}}$ («CTCS») получаем рекуррентное уравнение:

${ displaystyle { frac {u_ {j} ^ {n + 1} -u_ {j} ^ {n}} {k}} = { frac {1} {2}} left ({ frac {u_ {j + 1} ^ {n + 1} -2u_ {j} ^ {n + 1} + u_ {j-1} ^ {n + 1}} {h ^ {2}}} + { frac {u_ {j + 1} ^ {n} -2u_ {j} ^ {n} + u_ {j-1} ^ {n}} {h ^ {2}}} right). ,}$

Эта формула известна как Метод Кранка – Николсона.

Трафарет Крэнка – Николсона.

Мы можем получить ${ displaystyle u_ {j} ^ {n + 1}}$ от решения системы линейных уравнений:

${ displaystyle (2 + 2r) u_ {j} ^ {n + 1} -ru_ {j-1} ^ {n + 1} -ru_ {j + 1} ^ {n + 1} = (2-2r) u_ {j} ^ {n} + ru_ {j-1} ^ {n} + ru_ {j + 1} ^ {n}}$

Схема всегда численно стабильный и сходящийся, но обычно более интенсивный в числовом отношении, поскольку требует решения системы числовых уравнений на каждом временном шаге. Ошибки квадратичны как по временному, так и по пространственному шагу:

${ Displaystyle Delta и = О (к ^ {2}) + О (час ^ {2}). ,}$

Сравнение

Подводя итог, обычно схема Кранка – Николсона является наиболее точной схемой для малых шагов по времени. Для больших временных шагов неявная схема работает лучше, поскольку она менее требовательна к вычислениям. Явная схема наименее точна и может быть нестабильной, но также является наиболее простой в реализации и наименее трудоемкой.

Вот пример. На рисунках ниже представлены решения, полученные с помощью вышеуказанных методов для аппроксимации уравнения теплопроводности.

${ displaystyle U_ {t} = alpha U_ {xx}, quad alpha = { frac {1} { pi ^ {2}}},}$

с граничным условием

${ Displaystyle U (0, t) = U (1, t) = 0.}$

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

${ Displaystyle U (x, t) = { frac {1} { pi ^ {2}}} e ^ {- t} sin ( pi x).}$

Сравнение методов конечных разностей

Явный метод (нет стабильный)

Неявный метод (стабильный)

Метод Кранка-Николсона (стабильный)

Пример: оператор Лапласа

(Непрерывный) Оператор Лапласа в ${ displaystyle n}$-размеры задаются ${ displaystyle Delta u (x) = sum _ {i = 1} ^ {n} partial _ {i} ^ {2} u (x)}$Дискретный оператор Лапласа ${ displaystyle Delta _ {h} u}$ зависит от размера ${ displaystyle n}$.

В 1D оператор Лапласа аппроксимируется как

${ Displaystyle Delta u (x) = u '' (x) приблизительно { frac {u (xh) -2u (x) + u (x + h)} {h ^ {2}}} =: Дельта _ {h} u (x) ,.}$

Это приближение обычно выражается следующим образом: трафарет

${ displaystyle { frac {1} {h ^ {2}}} { begin {bmatrix} 1 & -2 & 1 end {bmatrix}}}$

и который представляет собой симметричную трехдиагональную матрицу. Для равноудаленной сетки получается Матрица Теплица.

2D-случай показывает все характеристики более общего nD-случая. Каждую вторую частную производную необходимо аппроксимировать аналогично одномерному случаю.

${ displaystyle { begin {align} Delta u (x, y) & = u_ {xx} (x, y) + u_ {yy} (x, y) & приблизительно { frac {u (xh , y) -2u (x, y) + u (x + h, y)} {h ^ {2}}} + { frac {u (x, yh) -2u (x, y) + u (x , y + h)} {h ^ {2}}} & = { frac {u (xh, y) + u (x + h, y) -4u (x, y) + u (x, yh) ) + u (x, y + h)} {h ^ {2}}} & =: Delta _ {h} u (x, y) ,, end {выровнено}}}$

который обычно дается следующим трафарет

${ displaystyle Delta _ {h} = { frac {1} {h ^ {2}}} { begin {bmatrix} & 1 1 & -4 & 1 & 1 end {bmatrix}} ,.}$

Последовательность

Согласованность вышеупомянутого приближения может быть продемонстрирована для очень регулярных функций, таких как ${ Displaystyle и в С ^ {4} ( Omega)}$Заявление

${ displaystyle Delta u- Delta _ {h} u = { mathcal {O}} (h ^ {2}) ,.}$

Чтобы доказать это, нужно заменить Серия Тейлор разложения до порядка 3 в дискретный оператор Лапласа.

Характеристики

Субгармоника

Похожий на непрерывные субгармонические функции можно определить субгармонические функции для конечно-разностных приближений ${ displaystyle u_ {h}}$

${ displaystyle - Delta _ {h} u_ {h} leq 0 ,.}$

Среднее значение

Можно определить общий трафарет из положительный тип через

${ displaystyle { begin {bmatrix} & alpha _ {N} alpha _ {W} & - alpha _ {C} & alpha _ {E} & alpha _ {S} end {bmatrix}} ,, quad alpha _ {i}> 0 ,, quad alpha _ {C} = sum _ {i in {N, E, S, W }} alpha _{я},.}$

Если ${ displaystyle u_ {h}}$ является (дискретной) субгармонической, то следующая свойство среднего значения держит

${ displaystyle u_ {h} (x_ {C}) leq { frac { sum _ {i in {N, E, S, W }} alpha _ {i} u_ {h} (x_ {i})} { sum _ {i in {N, E, S, W }} alpha _ {i}}} ,,}$

где аппроксимация оценивается по точкам сетки, а шаблон считается положительным.

Похожий свойство среднего значения верно и для непрерывного случая.

Принцип максимума

Для (дискретной) субгармонической функции ${ displaystyle u_ {h}}$ следующее имеет место

${ displaystyle max _ { Omega _ {h}} u_ {h} leq max _ { partial Omega _ {h}} u_ {h} ,,}$

куда ${ displaystyle Omega _ {h}, partial Omega _ {h}}$ являются дискретизацией непрерывной области ${ displaystyle Omega}$, соответственно граница ${ displaystyle partial Omega}$.

Похожий принцип максимума справедливо и для непрерывного случая.

Метод SBP-SAT

Метод SBP-SAT - это стабильный и точный метод дискретизации и наложения граничных условий корректного уравнения в частных производных с использованием конечных разностей высокого порядка.^[8][9] Метод основан на конечных разностях, где операторы дифференцирования проявляют свойства суммирования по частям. Обычно эти операторы состоят из матриц дифференцирования с центральными разностными шаблонами внутри с тщательно подобранными односторонними граничными шаблонами, предназначенными для имитации интеграции по частям в дискретной настройке. Используя метод SAT, граничные условия PDE накладываются слабо, когда граничные значения «подтягиваются» к желаемым условиям, а не точно выполняются. Если параметры настройки (присущие методике SAT) выбраны правильно, результирующая система ODE будет демонстрировать такое же энергетическое поведение, что и непрерывное PDE, то есть система не имеет роста нефизической энергии. Это гарантирует стабильность, если используется схема интегрирования с областью устойчивости, которая включает части мнимой оси, например метод Рунге-Кутта четвертого порядка. Это делает метод SAT привлекательным методом наложения граничных условий для методов конечных разностей более высокого порядка, в отличие, например, от метода впрыска, который обычно не будет устойчивым, если используются операторы дифференцирования высокого порядка.

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

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

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

• К.В. Мортон и Д.Ф. Майерс, Численное решение дифференциальных уравнений с частными производными, введение. Издательство Кембриджского университета, 2005.
• Autar Kaw и E. Eric Kalu, Численные методы с приложениями, (2008) [1]. Содержит краткое инженерное введение в FDM (для ODE) в Глава 08.07.
• Джон Стрикверда (2004). Конечно-разностные схемы и уравнения с частными производными (2-е изд.). СИАМ. ISBN  978-0-89871-639-9.
• Смит, Г. Д. (1985), Численное решение дифференциальных уравнений с частными производными: конечно-разностные методы, 3-е изд., Oxford University Press
• Питер Олвер (2013). Введение в уравнения с частными производными. Springer. Глава 5: Конечные различия. ISBN  978-3-319-02099-0..
• Рэндалл Дж. Левек, Конечно-разностные методы для обыкновенных и дифференциальных уравнений с частными производными, СИАМ, 2007.

Различные лекции и конспекты лекций

• Метод конечных разностей в электромагнетизме (см. И прослушайте лекцию 9)
• Конспект лекций Ши-Хунг Чен, Национальный центральный университет
• Численные методы для нестационарных дифференциальных уравнений в частных производных