Дискретное уравнение Пуассона - Discrete Poisson equation

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

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

С использованием конечная разница численный метод дискретизации 2-мерного уравнения Пуассона (предполагая равномерную пространственную дискретизацию, ${displaystyle Delta x=Delta y}$) на м × п сетка дает следующую формулу:^[1]

${displaystyle ({abla }^{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}}$

куда ${displaystyle 2leq ileq m-1}$ и ${displaystyle 2leq jleq n-1}$. Предпочтительное расположение вектора решения - использовать естественный порядок который до удаления граничных элементов выглядел бы так:

${displaystyle {vec {u}}={egin{bmatrix}u_{11},u_{21},ldots ,u_{m1},u_{12},u_{22},ldots ,u_{m2},ldots ,u_{mn}end{bmatrix}}^{T}}$

Это приведет к мин × мин линейная система:

${displaystyle A{vec {u}}={vec {b}}}$

куда

${displaystyle A={egin{bmatrix}~D&-I&~0&~0&~0&ldots &~0-I&~D&-I&~0&~0&ldots &~0~0&-I&~D&-I&~0&ldots &~0vdots &ddots &ddots &ddots &ddots &ddots &vdots ~0&ldots &~0&-I&~D&-I&~0~0&ldots &ldots &~0&-I&~D&-I~0&ldots &ldots &ldots &~0&-I&~Dend{bmatrix}},}$

${displaystyle I}$ это м × м единичная матрица, и ${displaystyle D}$, также м × м, дан кем-то:

${displaystyle D={egin{bmatrix}~4&-1&~0&~0&~0&ldots &~0-1&~4&-1&~0&~0&ldots &~0~0&-1&~4&-1&~0&ldots &~0vdots &ddots &ddots &ddots &ddots &ddots &vdots ~0&ldots &~0&-1&~4&-1&~0~0&ldots &ldots &~0&-1&~4&-1~0&ldots &ldots &ldots &~0&-1&~4end{bmatrix}},}$

^[2]и ${displaystyle {vec {b}}}$ определяется

${displaystyle {vec {b}}=-Delta x^{2}{egin{bmatrix}g_{11},g_{21},ldots ,g_{m1},g_{12},g_{22},ldots ,g_{m2},ldots ,g_{mn}end{bmatrix}}^{T}.}$

Для каждого ${displaystyle u_{ij}}$ уравнение, столбцы ${displaystyle D}$ соответствуют блоку ${displaystyle m}$ компоненты в ${displaystyle u}$:

${displaystyle {egin{bmatrix}u_{1j},&u_{2j},&ldots ,&u_{i-1,j},&u_{ij},&u_{i+1,j},&ldots ,&u_{mj}end{bmatrix}}^{T}}$

в то время как столбцы ${displaystyle I}$ слева и справа от ${displaystyle D}$ каждый соответствует другим блокам ${displaystyle m}$ компоненты внутри ${displaystyle u}$:

${displaystyle {egin{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}}^{T}}$

и

${displaystyle {egin{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}}^{T}}$

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

Из вышеизложенного можно сделать вывод, что есть ${displaystyle n}$ блочные столбцы ${displaystyle m}$ в ${displaystyle A}$. Важно отметить, что предписанные значения ${displaystyle u}$ (обычно лежащие на границе) их соответствующие элементы были бы удалены из ${displaystyle I}$ и ${displaystyle D}$. Для общего случая, когда все узлы на границе установлены, мы имеем ${displaystyle 2leq ileq m-1}$ и ${displaystyle 2leq jleq n-1}$, а система имела бы размеры (м − 2)(п − 2) × (м − 2)(п - 2), где ${displaystyle D}$ и ${displaystyle I}$ имел бы размеры (м − 2) × (м − 2).

Пример

Для 5 × 5 ( ${displaystyle m=5}$ и ${displaystyle n=5}$ ) сетка со всеми заданными граничными узлами, система будет выглядеть так:

${displaystyle {egin{bmatrix}Uend{bmatrix}}={egin{bmatrix}u_{22},u_{32},u_{42},u_{23},u_{33},u_{43},u_{24},u_{34},u_{44}end{bmatrix}}^{T}}$

с

${displaystyle A=left[{egin{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&~0hline -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&-1hline ~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&~4end{array}}ight]}$

и

${displaystyle {vec {b}}=left[{egin{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}}ight].}$

Как видно, граница ${displaystyle u}$в правую часть уравнения.^[3] Вся система имеет размер 9 × 9, а ${displaystyle D}$ и ${displaystyle I}$ равны 3 × 3 и определяются по формуле:

${displaystyle D={egin{bmatrix}~4&-1&~0-1&~4&-1~0&-1&~4end{bmatrix}}}$

и

${displaystyle -I={egin{bmatrix}-1&~0&~0~0&-1&~0~0&~0&-1end{bmatrix}}.}$

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

Потому что ${displaystyle {egin{bmatrix}Aend{bmatrix}}}$ является блочным трехдиагональным и разреженным, многие методы решения были разработаны для оптимального решения этой линейной системы для ${displaystyle {egin{bmatrix}Uend{bmatrix}}}$.Среди методов есть обобщенные Алгоритм Томаса с результирующей вычислительной сложностью ${displaystyle O(n^{2.5})}$, циклическое сокращение, последовательное чрезмерное расслабление это имеет сложность ${displaystyle O(n^{1.5})}$, и Быстрые преобразования Фурье который ${displaystyle O(nlog(n))}$. Оптимальный ${displaystyle O(n)}$ решение также может быть вычислено с использованием многосеточные методы. ^[4]

Сходимость по Пуассону различных итерационных методов с бесконечными нормами остатков в зависимости от количества итераций и компьютерного времени.

Приложения

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

Для несжимаемого потока это ограничение определяется выражением:

${displaystyle {frac {partial v_{x}}{partial x}}+{frac {partial v_{y}}{partial y}}+{frac {partial v_{z}}{partial z}}=0}$

куда ${displaystyle v_{x}}$ - скорость в ${displaystyle x}$ направление, ${displaystyle v_{y}}$ скорость в ${displaystyle y}$ и ${displaystyle v_{z}}$ - скорость в ${displaystyle z}$ направление. Принимая дивергенцию уравнения импульса и используя ограничение несжимаемости, уравнение Пуассона давления формируется следующим образом:

${displaystyle abla ^{2}p=f(u ,V)}$

куда ${displaystyle u }$ - кинематическая вязкость жидкости и ${displaystyle V}$ - вектор скорости.^[5]

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

Сноски

1. Хоффман, Джо (2001), "Глава 9. Эллиптические уравнения в частных производных", Численные методы для инженеров и ученых (2-е изд.), McGraw – Hill, ISBN  0-8247-0443-6.
2. Голуб, Джин Х. и К. Ф. Ван Лоан, Матричные вычисления, 3-е изд., Издательство Университета Джона Хопкинса, Балтимор, 1996 г., страницы 177–180.
3. Чени, Уорд и Дэвид Кинкейд, Вычислительная математика и вычисления 2-е изд., Brooks / Cole Publishing Company, Pacific Grove, 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.
6. С.П. Мейн и Р.Л. Твиди, 2005. Марковские цепи и стохастическая устойчивость. Выйдет второе издание, Cambridge University Press, 2009.
7. С. П. Мейн, 2007. Методы управления сложными сетями, Издательство Кембриджского университета, 2007.
8. Асмуссен, Сорен, Глинн, Питер В., 2007. «Стохастическое моделирование: алгоритмы и анализ». Springer. Серия: Стохастическое моделирование и прикладная вероятность, Vol. 57, 2007.

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

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