Дискретное уравнение Пуассона

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

На двумерной прямоугольной сетке

Использование численного метода конечных разностей для дискретизациидвумерное уравнение Пуассона (при условии равномерной пространственной дискретизации, $\Delta x=\Delta y$ ) на $сетке m \times n$ дает следующую формулу: ^[1] $({\nabla }^{2}u)_{ij}={\frac {1}{\Delta x^{2}}}(u_{i+1,j}+u_{i-1,j}+u_{i,j+1}+u_{i,j-1}-4u_{ij})=g_{ij}$ где $2\leq i\leq m-1$ и $2\leq j\leq n-1$ . Предпочтительным расположением вектора решения является использование естественного порядка , который до удаления граничных элементов будет выглядеть так: $\mathbf {u} ={\begin{bmatrix}u_{11},u_{21},\ldots ,u_{m1},u_{12},u_{22},\ldots ,u_{m2},\ldots ,u_{mn}\end{bmatrix}}^{\mathsf {T}}$

В результате получим $линейную систему mn \times mn$ : $A\mathbf {u} =\mathbf {b}$ где $A={\begin{bmatrix}~D&-I&~0&~0&~0&\cdots &~0\\-I&~D&-I&~0&~0&\cdots &~0\\~0&-I&~D&-I&~0&\cdots &~0\\\vdots &\ddots &\ddots &\ddots &\ddots &\ddots &\vdots \\~0&\cdots &~0&-I&~D&-I&~0\\~0&\cdots &\cdots &~0&-I&~D&-I\\~0&\cdots &\cdots &\cdots &~0&-I&~D\end{bmatrix}},$

$I$ — $m \times m$ единичная матрица размера , а $D$ , а также $m \times m$ , определяется выражением: ^[2] $D={\begin{bmatrix}~4&-1&~0&~0&~0&\cdots &~0\\-1&~4&-1&~0&~0&\cdots &~0\\~0&-1&~4&-1&~0&\cdots &~0\\\vdots &\ddots &\ddots &\ddots &\ddots &\ddots &\vdots \\~0&\cdots &~0&-1&~4&-1&~0\\~0&\cdots &\cdots &~0&-1&~4&-1\\~0&\cdots &\cdots &\cdots &~0&-1&~4\end{bmatrix}},$ и $\mathbf {b}$ определяется $\mathbf {b} =-\Delta x^{2}{\begin{bmatrix}g_{11},g_{21},\ldots ,g_{m1},g_{12},g_{22},\ldots ,g_{m2},\ldots ,g_{mn}\end{bmatrix}}^{\mathsf {T}}.$

Для каждого $u_{ij}$ уравнение, столбцы $D$ соответствуют блоку $m$ компоненты в $u$ : ${\begin{bmatrix}u_{1j},&u_{2j},&\ldots ,&u_{i-1,j},&u_{ij},&u_{i+1,j},&\ldots ,&u_{mj}\end{bmatrix}}^{\mathsf {T}}$ в то время как столбцы $I$ слева и справа от $D$ каждый соответствует другим блокам $m$ компоненты внутри $u$ : ${\begin{bmatrix}u_{1,j-1},&u_{2,j-1},&\ldots ,&u_{i-1,j-1},&u_{i,j-1},&u_{i+1,j-1},&\ldots ,&u_{m,j-1}\end{bmatrix}}^{\mathsf {T}}$ и ${\begin{bmatrix}u_{1,j+1},&u_{2,j+1},&\ldots ,&u_{i-1,j+1},&u_{i,j+1},&u_{i+1,j+1},&\ldots ,&u_{m,j+1}\end{bmatrix}}^{\mathsf {T}}$

соответственно.

Из вышеизложенного можно сделать вывод, что существуют $n$ блокировать столбцы $m$ в $A$ . Важно отметить, что заданные значения $u$ (обычно лежащих на границе) соответствующие элементы будут удалены из $I$ и $D$ . Для общего случая, когда все узлы на границе установлены, мы имеем $2\leq i\leq m-1$ и $2\leq j\leq n-1$ , и система будет иметь размеры $(m - 2)(n - 2) \times (m - 2)(n - 2)$ , где $D$ и $I$ будет иметь размеры $(м - 2) \times (м - 2)$ .

Пример

Для 3×3 ( $m=3$ и $n=3$ ) со всеми заданными граничными узлами, система будет выглядеть так: ${\begin{bmatrix}U\end{bmatrix}}={\begin{bmatrix}u_{22},u_{32},u_{42},u_{23},u_{33},u_{43},u_{24},u_{34},u_{44}\end{bmatrix}}^{\mathsf {T}}$ с $A=\left[{\begin{array}{ccc|ccc|ccc}~4&-1&~0&-1&~0&~0&~0&~0&~0\\-1&~4&-1&~0&-1&~0&~0&~0&~0\\~0&-1&~4&~0&~0&-1&~0&~0&~0\\\hline -1&~0&~0&~4&-1&~0&-1&~0&~0\\~0&-1&~0&-1&~4&-1&~0&-1&~0\\~0&~0&-1&~0&-1&~4&~0&~0&-1\\\hline ~0&~0&~0&-1&~0&~0&~4&-1&~0\\~0&~0&~0&~0&-1&~0&-1&~4&-1\\~0&~0&~0&~0&~0&-1&~0&-1&~4\end{array}}\right]$ и

\mathbf {b} =\left[{\begin{array}{l}-\Delta x^{2}g_{22}+u_{12}+u_{21}\\-\Delta x^{2}g_{32}+u_{31}~~~~~~~~\\-\Delta x^{2}g_{42}+u_{52}+u_{41}\\-\Delta x^{2}g_{23}+u_{13}~~~~~~~~\\-\Delta x^{2}g_{33}~~~~~~~~~~~~~~~~\\-\Delta x^{2}g_{43}+u_{53}~~~~~~~~\\-\Delta x^{2}g_{24}+u_{14}+u_{25}\\-\Delta x^{2}g_{34}+u_{35}~~~~~~~~\\-\Delta x^{2}g_{44}+u_{54}+u_{45}\end{array}}\right].

Как видно, граница $u$ 's перенесены в правую часть уравнения. ^[3] Вся система имеет размер $9 \times 9,$ а $D$ и $I$ имеют $размер 3 \times 3$ и определяются выражением: $D={\begin{bmatrix}~4&-1&~0\\-1&~4&-1\\~0&-1&~4\\\end{bmatrix}}$ и $-I={\begin{bmatrix}-1&~0&~0\\~0&-1&~0\\~0&~0&-1\end{bmatrix}}.$

Методы решения

Потому что ${\begin{bmatrix}A\end{bmatrix}}$ блок трехдиагональный и разреженный, много методов решениябыли разработаны для оптимального решения этой линейной системы для ${\begin{bmatrix}U\end{bmatrix}}$ .Среди методов — обобщенный алгоритм Томаса с результирующей вычислительной сложностью $O(n^{2.5})$ , циклическое сокращение , последовательное чрезмерное расслабление , имеющее сложность $O(n^{1.5})$ и быстрое преобразование Фурье , которое $O(n\log(n))$ . Оптимальный $O(n)$ Решение также может быть вычислено с использованием многосеточных методов . ^[4]

Приложения

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

Для несжимаемого потока это ограничение определяется выражением: ${\frac {\partial v_{x}}{\partial x}}+{\frac {\partial v_{y}}{\partial y}}+{\frac {\partial v_{z}}{\partial z}}=0$ где $v_{x}$ это скорость в $x$ направление, $v_{y}$ скорость в $y$ и $v_{z}$ это скорость в $z$ направление. Учитывая дивергенцию уравнения количества движения и использование ограничения несжимаемости, уравнение Пуассона для давления формируется по формуле: $\nabla ^{2}p=f(\nu ,V)$ где $\nu$ - кинематическая вязкость жидкости и $V$ – вектор скорости. ^[5]

Дискретное уравнение Пуассона возникает в теории цепей Маркова . Она появляется как функция относительного значения для уравнения динамического программирования в марковском процессе принятия решений и как управляющая переменная для применения при уменьшении дисперсии моделирования. ^[6]^[7]^[8]

Сноски

^ Хоффман, Джо (2001), «Глава 9. Эллиптические уравнения в частных производных», Численные методы для инженеров и ученых (2-е изд.), МакГроу – Хилл, ISBN 0-8247-0443-6 .
^ Голуб, Джин Х. и К.Ф. Ван Лоан, Матричные вычисления, 3-е изд. , Издательство Университета Джона Хопкинса, Балтимор, 1996, страницы 177–180.
^ Чени, Уорд и Дэвид Кинкейд, Численная математика и вычисления, 2-е изд. , Brooks/Cole Publishing Company, Пасифик Гроув, 1985, страницы 443–448.
^ CS267: Примечания к лекциям 15 и 16, 5 и 7 марта 1996 г., https://people.eecs.berkeley.edu/~demmel/cs267/lecture24/lecture24.html.
^ Флетчер, Клайв А.Дж., Вычислительные методы для гидродинамики: Том I , 2-е изд., Springer-Verlag, Берлин, 1991, стр. 334–339.
^ С. П. Мейн и Р. Л. Твиди, 2005. Цепи Маркова и стохастическая устойчивость . Появится второе издание, Cambridge University Press, 2009 г.
^ С.П. Мейн, 2007. Методы управления сложными сетями. Архивировано 16 декабря 2014 г., в Wayback Machine , Cambridge University Press, 2007.
^ Асмуссен, Сорен, Глинн, Питер В., 2007. «Стохастическое моделирование: алгоритмы и анализ». Спрингер. Серия: Стохастическое моделирование и прикладная теория вероятности, Vol. 57, 2007.

Ссылки

Хоффман, Джо Д., Численные методы для инженеров и ученых, 4-е изд. , McGraw–Hill Inc., Нью-Йорк, 1992 г.
Свит, Роланд А. , Журнал SIAM по численному анализу, Vol. 11, № 3 , июнь 1974 г., стр. 506–520.
Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 20.4. Методы Фурье и циклической редукции» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8 . Архивировано из оригинала 11 августа 2011 года . Проверено 18 августа 2011 г.

[1] Хоффман, Джо (2001), «Глава 9. Эллиптические уравнения в частных производных», Численные методы для инженеров и ученых (2-е изд.), МакГроу – Хилл, ISBN 0-8247-0443-6 .

[2] Голуб, Джин Х. и К.Ф. Ван Лоан, Матричные вычисления, 3-е изд. , Издательство Университета Джона Хопкинса, Балтимор, 1996, страницы 177–180.

[3] Чени, Уорд и Дэвид Кинкейд, Численная математика и вычисления, 2-е изд. , Brooks/Cole Publishing Company, Пасифик Гроув, 1985, страницы 443–448.

[4] CS267: Примечания к лекциям 15 и 16, 5 и 7 марта 1996 г., https://people.eecs.berkeley.edu/~demmel/cs267/lecture24/lecture24.html.

[5] Флетчер, Клайв А.Дж., Вычислительные методы для гидродинамики: Том I , 2-е изд., Springer-Verlag, Берлин, 1991, стр. 334–339.

[MCSS-6] С. П. Мейн и Р. Л. Твиди, 2005. Цепи Маркова и стохастическая устойчивость . Появится второе издание, Cambridge University Press, 2009 г.

[CTCN-7] С.П. Мейн, 2007. Методы управления сложными сетями. Архивировано 16 декабря 2014 г., в Wayback Machine , Cambridge University Press, 2007.

[AG07-8] Асмуссен, Сорен, Глинн, Питер В., 2007. «Стохастическое моделирование: алгоритмы и анализ». Спрингер. Серия: Стохастическое моделирование и прикладная теория вероятности, Vol. 57, 2007.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]