Метод конечных разностей - Finite difference method - Wikipedia

В числовой анализ, конечно-разностные методы (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 {f(a+h) \over h}={f(a) \over h}+f'(a)+{R_{1}(x) \over h}}$

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

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

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

${\displaystyle f'(a)\approx {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 <x_{0}+h}$,

может быть обнаружен доминирующий член локальной ошибки усечения. Например, снова используя формулу прямой разности для первой производной, зная, что ${\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!}}ih,}$

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

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

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

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

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

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

${\displaystyle u'(x)=3u(x)+2.\,}$

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

${\displaystyle {\frac {u(x+h)-u(x)}{h}}\approx u'(x)}$

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

${\displaystyle u(x+h)=u(x)+h(3u(x)+2).\,}$

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

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

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

${\displaystyle U_{t}=U_{xx}\,}$

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

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

Один из способов численного решения этого уравнения - аппроксимировать все производные конечными разностями. Разделим область в пространстве сеткой ${\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 u=O(k)+O(h^{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 u=O(k)+O(h^{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 u=O(k^{2})+O(h^{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)\approx {\frac {u(x-h)-2u(x)+u(x+h)}{h^{2}}}=:\Delta _{h}u(x)\,.}$

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

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

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

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

${\displaystyle {\begin{aligned}\Delta u(x,y)&=u_{xx}(x,y)+u_{yy}(x,y)\\&\approx {\frac {u(x-h,y)-2u(x,y)+u(x+h,y)}{h^{2}}}+{\frac {u(x,y-h)-2u(x,y)+u(x,y+h)}{h^{2}}}\\&={\frac {u(x-h,y)+u(x+h,y)-4u(x,y)+u(x,y-h)+u(x,y+h)}{h^{2}}}\\&=:\Delta _{h}u(x,y)\,,\end{aligned}}}$

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

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

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

Согласованность вышеупомянутого приближения может быть продемонстрирована для очень регулярных функций, таких как ${\displaystyle u\in C^{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 _{i}\,.}$

Если ${\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 привлекательным методом наложения граничных условий для методов конечных разностей более высокого порядка, в отличие, например, от метода впрыска, который обычно не будет устойчивым, если используются операторы дифференцирования высокого порядка.

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

• Метод конечных элементов
• Конечная разница
• Конечная разница во временной области
• Метод бесконечных разностей
• Трафарет (численный анализ)
• Конечно-разностные коэффициенты
• Пятиточечный трафарет
• Теорема Лакса – Рихтмайера
• Конечно-разностные методы ценообразования опционов
• Схема дифференцирования против ветра для конвекции
• Центральная разностная схема
• Дискретное уравнение Пуассона
• Дискретный оператор Лапласа

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

1. Кристиан Гроссманн; Hans-G. Roos; Мартин Стайнс (2007). Численное рассмотрение дифференциальных уравнений в частных производных. Springer Science & Business Media. п.23. ISBN  978-3-540-71584-9.
2. Арье Изерлес (2008). Первый курс численного анализа дифференциальных уравнений. Издательство Кембриджского университета. п.23. ISBN  9780521734905.
3. Hoffman JD; Франкель С (2001). Численные методы для инженеров и ученых. CRC Press, Бока-Ратон.
4. Jaluria Y; Атлури С (1994). «Расчетная теплопередача». Вычислительная механика. 14: 385–386. Дои:10.1007 / BF00377593.
5. Маджумдар П. (2005). Расчетные методы тепломассопереноса (1-е изд.). Тейлор и Фрэнсис, Нью-Йорк.
6. Смит Г.Д. (1985). Численное решение уравнений в частных производных: методы конечных разностей (3-е изд.). Издательство Оксфордского университета.
7. Крэнк, Дж. Математика диффузии. 2-е издание, Оксфорд, 1975, с. 143.
8. Бо Стрэнд (1994). Суммирование по частям для конечно-разностных приближений для d / dx. Журнал вычислительной физики. Дои:10.1006 / jcph.1994.1005.
9. Марк Х. Карпентер; Дэвид И. Готтлиб; Саул С. Абарбанель (1994). Устойчивые во времени граничные условия для разностных схем, решающих гиперболические системы: методология и приложение к компактным схемам высокого порядка. Журнал вычислительной физики. Дои:10.1006 / jcph.1994.1057.

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

• К.В. Мортон и Д.Ф. Майерс, Численное решение дифференциальных уравнений с частными производными, введение. Издательство Кембриджского университета, 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)
• Конспект лекций Ши-Хунг Чен, Национальный центральный университет
• Численные методы для нестационарных дифференциальных уравнений в частных производных