Уравнение Пуассона, решение дискретным преобразованием Фурье: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Строка 4: | Строка 4: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
− | Уравнение Пуассона имеет | + | Уравнение Пуассона для многомерного пространства имеет вид: |
\begin{equation} | \begin{equation} | ||
− | \sum_{i=1}^{N}\frac{\partial^2 \phi}{\partial x_i^2}=f | + | \label{eq:poisson} |
+ | \sum_{i=1}^{N}\frac{\partial^2 \phi}{\partial x_i^2}=f,~\mathbf{x}\in D, | ||
\end{equation} | \end{equation} | ||
+ | |||
+ | где <math>N</math> - размерность пространства независимых переменных, <math>\mathbf{x}=(x_1,...,x_N)^T</math> - вектор независимых переменных, <math>\phi(\mathbf{x})</math> - неизвестная функция. Уравнение Пуассона дополняется граничными условиями: | ||
+ | |||
+ | \begin{equation} | ||
+ | B(\phi)=F,~ \text{на}~ \mathbf{x}\in \Gamma(D), | ||
+ | \end{equation} | ||
+ | |||
+ | где <math>\Gamma(D)</math> - граница области <math>D</math>, a <math>B(\phi)</math> - оператор, определяющий граничные условия. <math>B(\phi)=\phi</math> соответствует граничным условиям Дирихле, <math>B(\phi)=\partial\phi/\partial \mathbf{n}</math> (<math>\mathbf{n}</math> - внешняя нормаль к границе <math>\Gamma(D)</math>) - условиям Неймана. Иногда задают также смешанное граничное условие: <math>B(\phi)=\phi+\partial\phi/\partial \mathbf{n}</math>. Встречаются также так называемые "периодические граничные условия", при которых задача ставится для бесконечной области, но предполагается периодичность решения по подмножеству переменных из <math>\mathbf{x}</math>. | ||
+ | |||
+ | Аналитическое решение уравнения Пуассона для произвольной правой части и неоднородных граничных условий неизвестно, поэтому оно в большинстве приложений находится численно. Наиболее распространенная дискретизация уравнения имеет вид | ||
+ | |||
+ | \begin{equation} | ||
+ | \sum_{i=1}^{N}\frac{\phi_{k_1,...,k_i+1,...,k_N}-2\phi_{k_1,...,k_i,...,k_N}+\phi_{k_1,...,k_i-1,...,k_N}}{\Delta x_i^2}=f_{k_1,...,k_N},~(k_1,...,k_N) \in D_N. | ||
+ | \end{equation} | ||
+ | |||
+ | Здесь вторые производные заменены центральными разностями второго порядка точности. | ||
=== Математическое описание === | === Математическое описание === |
Версия 21:21, 1 мая 2015
Основные авторы описания: В.М.Степаненко, Е.В.Мортиков
Содержание
- 1 Описание свойств и структуры алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Описание схемы реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Описание ресурса параллелизма алгоритма
- 1.9 Описание входных и выходных данных
- 1.10 Свойства алгоритма
- 2 Программная реализация
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Описание локальности данных и вычислений
- 2.3 Возможные способы и особенности реализации параллельного алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Описание свойств и структуры алгоритма
1.1 Общее описание алгоритма
Уравнение Пуассона для многомерного пространства имеет вид:
\begin{equation} \label{eq:poisson} \sum_{i=1}^{N}\frac{\partial^2 \phi}{\partial x_i^2}=f,~\mathbf{x}\in D, \end{equation}
где [math]N[/math] - размерность пространства независимых переменных, [math]\mathbf{x}=(x_1,...,x_N)^T[/math] - вектор независимых переменных, [math]\phi(\mathbf{x})[/math] - неизвестная функция. Уравнение Пуассона дополняется граничными условиями:
\begin{equation} B(\phi)=F,~ \text{на}~ \mathbf{x}\in \Gamma(D), \end{equation}
где [math]\Gamma(D)[/math] - граница области [math]D[/math], a [math]B(\phi)[/math] - оператор, определяющий граничные условия. [math]B(\phi)=\phi[/math] соответствует граничным условиям Дирихле, [math]B(\phi)=\partial\phi/\partial \mathbf{n}[/math] ([math]\mathbf{n}[/math] - внешняя нормаль к границе [math]\Gamma(D)[/math]) - условиям Неймана. Иногда задают также смешанное граничное условие: [math]B(\phi)=\phi+\partial\phi/\partial \mathbf{n}[/math]. Встречаются также так называемые "периодические граничные условия", при которых задача ставится для бесконечной области, но предполагается периодичность решения по подмножеству переменных из [math]\mathbf{x}[/math].
Аналитическое решение уравнения Пуассона для произвольной правой части и неоднородных граничных условий неизвестно, поэтому оно в большинстве приложений находится численно. Наиболее распространенная дискретизация уравнения имеет вид
\begin{equation} \sum_{i=1}^{N}\frac{\phi_{k_1,...,k_i+1,...,k_N}-2\phi_{k_1,...,k_i,...,k_N}+\phi_{k_1,...,k_i-1,...,k_N}}{\Delta x_i^2}=f_{k_1,...,k_N},~(k_1,...,k_N) \in D_N. \end{equation}
Здесь вторые производные заменены центральными разностями второго порядка точности.