Метод конечных разностей

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

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

В численном анализе , конечно-разностные методы ( 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),}$

Деление на h дает:

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

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

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

В фон Неймана и Куранта-Фридрихса-Lewy критерии часто оценивается для определения численной устойчивости модели. ^{[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)\,}$ (начальное состояние)

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

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

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

Явный метод [ править ]

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

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

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

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

${\displaystyle \Delta u=O(k)+O(h^{2})\,}$

Неявный метод [ править ]

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

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

Метод Кранка – Николсона [ править ]

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

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• К. В. Мортон, Д. Ф. Майерс, Численное решение уравнений с частными производными, Введение . Издательство Кембриджского университета, 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..
• Рэндалл Дж. Левек , Конечно-разностные методы для обыкновенных и дифференциальных уравнений с частными производными , SIAM, 2007.
• Сергей Лемешевский, Петр Матус, Дмитрий Поляков (ред.): «Точные конечно-разностные схемы», De Gruyter (2016). DOI: https://doi.org/10.1515/9783110491326 .

Различные лекции и конспекты лекций [ править ]

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