Распараллеливание решения уравнения Пуассона с краевыми условиями Дирихле

 

СОДЕРЖАНИЕ

Введение 3

1. Простейшая  разностная схема «крест». Устойчивость  схемы «крест» 6

2. Методы  решения сеточных уравнений 11

2.1. Метод  простых итераций 11

2.2. Метод  простых итераций с оптимальным  параметром 12

2.3. Чебышёвское  ускорение метода простых итераций 14

2.4. Метод  Якоби 15

2.5. Метод  Зейделя 16

2.6. Метод  верхней релаксации 17

2.7. Попеременно  - треугольный итерационный метод 18

3. Сводка  результатов по итерационным  методам решения сеточных   уравнений 21

4. Распараллеливание решения уравнения Пуассона с краевыми условиями Дирихле 22

Заключение 25

Список использованных источников 26

Приложения 27

 

 

 

 

 

 

 

ВВЕДЕНИЕ

Уравнение Пуассона — эллиптическое дифференциальное уравнение в частных производных, которое описывает:

• электростатическое поле,
• стационарное поле температуры,
• поле давления,
• поле потенциала скорости в гидродинамике.

Оно названо в честь  знаменитого французского физика и  математика Симеона Дени Пуассона.

Это уравнение имеет вид:

,

где — оператор Лапласа или лапласиан, — действительная или комплексная функция на некотором многообразии, а — неизвестная функция.

В трёхмерной декартовой системе  координат уравнение принимает  форму:

.

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

Если область  представляет собой некоторый объем в трехмерном пространстве, то граница будет представлять  собой  замкнутую поверхность в этом пространстве,  ограничивающую  заданный  объем. Если  область представляет собой некоторую поверхность в двухмерном пространстве, то граница будет представлять собой замкнутый контур в этом пространстве, ограничивающий заданную поверхность. И, наконец, если область представляет собой некоторый отрезок в одномерном пространстве, то граница будет представлять собой две точки на границах заданного отрезка.

Граничные условия бывают трех видов:

1. Дирихле:  при , ,

где – граница рассматриваемой области; – искомая функция; – некоторая заданная на границе функция; – координаты граничной точки в пространстве (например, для трехмерного пространства = ()), – время.

2. Неймана:  при , ,

где – внутренняя нормаль к границе

3. Смешанные: при , ,

где ,   – некоторые функции координат и времени.

Существует два вида методов  решения данного типа уравнений:

• аналитический, при котором результат выводится различными математическими преобразованиями (например, с использованием функции Грина);
• численный, при котором полученный результат соответствует действительному с заданной точностью, но который требует много рутинных вычислений и, поэтому, выполним только при помощи вычислительной техники (ЭВМ).

В последнее время уравнение  Пуассона находит все большее применение в области обработки изображений (бесшовное клонирование, матирование изображений, редактирование изображений.). Например, бесшовное клонирование  позволяет вставить часть одного изображения в другое так, чтобы не было заметно швов. На самом деле для получения результата используется только градиентное поле вставляемой части и значения пикселей исходного изображения на границе обрабатываемой области. Таким образом получается уравнение Пуассона с краевыми условиями Дирихле: 
, при , , где – известное изображение, вставляемое в область , а – изображение, в которое вставляем.

Находя из уравнения искомое  изображение, можно решать сразу несколько задач:

• Бесшовная вставка новых элементов в изображение.
• Подавление нежелательных артефактов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Простейшая разностная схема «крест». Устойчивость схемы «крест»

Будем рассматривать двухмерное уравнение Пуассона

 

в единичном квадрате с краевыми условиями первого рода на границе расчетной области:

,

где – некоторая заданная на границе функция.

В случае прямоугольной области  граничные условия удобно записать в следующем виде:

,

,

,

.

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

Рис. 1.

Выбираем простейший пятиточечный шаблон разностной схемы «крест» (рис 1.). На этом шаблоне аппроксимирующее разностное уравнение легко выписать. Для этого производные заменим вторыми разностями:

,

где — шаг по координатам, или в операторной форме

,

здесь , , , , , .

Эту же разностную схему  можно записать в каноническом виде для разностных схем для эллиптических  уравнений:

.

Такую каноническую запись не следует путать с канонической формой записи итерационного метода, которая встретится ниже.

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

.

Здесь учтено разложение проекции точного решения в ряд Тейлора

 

и аналогичное разложение для .

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

.

Рассмотрим устойчивость полученной схемы. Отметим, что методы исследования на устойчивость, применяемые  для эволюционных (зависящих от времени) уравнений, здесь не работают. Действовать  приходится на основе определения устойчивости.

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

Лемма 1.

Пусть сеточная функция  определена на сетке , и во всех внутренних узлах сетки удовлетворяет уравнению

,

причем во всех внутренних узлах сетки правая часть этого уравнения неотрицательная: . Тогда наибольшее значение сеточная функция достигает хотя бы в одной точке границы сеточной области.

Лемма 2.

Пусть сеточная функция  определена на сетке , и во всех внутренних узлах сетки удовлетворяет уравнению

,

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

Лемма 3 (сеточный принцип  максимума).

Каждое решение разностного  уравнения Лапласа

 

достигает своего минимального и максимального значения на границе  сеточной области.

Введем норму сеточной функции как

.

Для доказательства устойчивости теперь надо доказать однозначную разрешимость разностной задачи для уравнения  Пуассона с любой правой частью и  любыми граничными условиями, получить оценку

.

Здесь в правой части стоит  норма правой части задачи, записанной в операторном виде, . Первый максимум в этой сумме берется по всем внутренним точкам, второй — по всем точкам сеточной границы.

Докажем однозначную разрешимость разностной задачи. Рассмотрим сеточное уравнение Лапласа с нулевыми граничными условиями. В силу принципа максимума такая задача имеет  лишь тривиальное решение. Но сеточная система — это система линейных уравнений. Если система с нулевой  правой частью имеет лишь тривиальное  решение, то она однозначно разрешима  при любой правой части.

Заметим, что в точной арифметике действие разностного оператора, приближающего дифференциальный оператор Лапласа, на произвольный полином второй степени совпадает по результату с действием дифференциального  оператора — погрешность аппроксимации, как следует из приведенной выше оценки, будет нулевая. Рассмотрим вспомогательную функцию

,

где — радиус окружности с центром в точке и включающей в себя рассматриваемую область. В данном случае . Эта функция иногда называется мажорантой Гершгорина.

Индекс  означает, что рассматривается сеточная проекция мажоранты. Обратимся к сеточной функции и применим к ней разностный оператор Лапласа. Получим

 

во всех внутренних точках области. Отсюда следует, что свое наибольшее значение рассматриваемая сеточная функция достигает на границе  сеточной области в соответствии с леммой 1. Но, как легко убедиться, на границе области сеточная функция принимает только отрицательные значения. Тогда во всех точках сеточной области, включая граничные. Рассмотрим сеточную функцию . Проведя такие же рассуждения, придем к неравенству во всех точках сеточной области, включая граничные.

Объединяя полученные результаты, находим

,

Откуда следует неравенство . Таким образом, устойчивость самой разностной схемы доказана.

 

 

 

 

 

 

 

 

 

 

 

 

2. Методы решения сеточных уравнений

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

2.1. Метод простых итераций

Наиболее эффективные  алгоритмы для численного решения  полученной СЛАУ — итерационные. Действительно, прямые методы требуют вычисления обратной матрицы, обратная матрица получается заполненной. Пусть  — начальное приближение, выбирать которое желательно как можно ближе к искомому решению, , ,… — последующие приближения. Верхний индекс в данных обозначениях указывает номер итерации.

Если выполняется условие

,

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

,

где — константа, . Итерации продолжаются до тех пор, пока не выполнено условие , где — заданная точность. В таком случае можно оценить количество итераций, необходимое для достижения этой точности +1. Квадратные скобки в этой записи — операция взятия целой части числа.

Метод простых итераций записывается для системы сеточных уравнений  в следующем виде:

,

если точка принадлежит  внутренней части сеточной области, и  если точка с индексами принадлежит границе сеточной области. Здесь , — итерационный параметр. Количество арифметических операций при реализации метода простых итераций .

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

В таком случае для сеточной функции невязки , равной нулю на границе, ее эволюция описывается уравнением

.

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

,

откуда получим

.

2.2. Метод простых итераций с оптимальным параметром

Представим сеточную функцию  невязки , равную нулю на границе, в виде разложения по базису из собственных функций разностного оператора (— собственные функции оператора )

,

при этом выполняется равенство  Парсеваля

.

Далее, используя это разложение, получим

 

 

Здесь используется то, что  являются собственными числами оператора При сложении равенств и получаем Легко получается оценка нормы этой сеточной функции на первой итерации:

 

Для последовательности итераций также легко получается стандартная  оценка нормы