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

.

Отсюда видно, что значение q вычисляется, как , а условие сходимости выполняется при . Границы спектра разностного оператора уже оценены в предыдущем пункте.

Для определения параметра  τ, обеспечивающего максимальную скорость сходимости, необходимо решать следующую оптимизационную задачу:

.

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

Как показано на рис. 2, достигается при . Справа от точки B при любых максимальна функция, слева — функция , и тогда минимум от искомого максимума достигается в точке B. Отсюда получим . Следовательно, значение оптимального итерационного параметра равно:

.

Рис. 2

Количество итераций, соответствующее  этому методу, легко оценивается:

.

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

Рассмотрим итерационный метод с выбором параметра  τ на каждой итерации:

.

Соответствующие соотношения  для эволюции невязки имеют вид:

,

.

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

.

Для коэффициентов разложения и компонентов невязки справедливы  следующие равенства:

,

,

.

Оценим погрешности на шаге итераций:

.

Вновь приходим к минимаксной  задаче: найти такую последовательность итерационных параметров , чтобы выполнялось . Заметим, что есть полином (относительно ) степени . Задача — сделать его наименее уклоняющимся от нуля на отрезке . Эта задача, как известно, решена Чебышевым, а корни этого полинома являются нулями полинома Чебышева:

, .

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

.

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

Для системы сеточных уравнений, полученных при использовании схемы "крест":

,

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

,

, с условиями на сеточной  границе .

Если в явном виде выразить , получим каноническую форму записи сеточного метода, правую часть берем на предыдущей итерации, левую — на текущей:

.

Количество итераций, требуемое  для вычисления решения с точностью  ε, оценивается по формуле:

.

2.5. Метод зейделя

Для системы сеточных уравнений, полученных при использовании схемы "крест":

,

запишем итерационный метод  Зейделя. Метод Зейделя, учитывающий результаты вычислений на итерации, записывается для рассматриваемого уравнения Пуассона в следующем виде:

,

, с условиями на сеточной  границе .

Напомним, что хотя метод  Зейделя неявный, но его реализация оказывается простой, если правильно  установить последовательность вычислений. В каноническом виде формулы для  метода Зейделя есть:

.

Оценка количества итераций, необходимых для достижения точности ε, есть:

.

Метод Зейделя сходится быстрее  метода Якоби, однако число итераций также оценивается как  .

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

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

 

представляется в виде:

,

где  и   — нижняя и верхняя треугольные матрицы с нулевыми диагоналями,  - диагональная матрица. Вводится параметр и итерационные формулы записываются в виде:

.

При получаем метод Зейделя.

Рассмотрим реализацию метода верхней релаксации для разностной аппроксимации уравнения Пуассона. Переписав разностную схему в  виде:

,

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

.

Последовательность вычислений в методе релаксаций такая же, как  и в методе Зейделя. Уравнения представляются в виде:

,

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

Необходимое количество итераций для достижения точности ε равно:

.

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

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

При аппроксимации уравнений  Пуассона или Лапласа получается система сеточных уравнений:

,

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

Зададим матрицу :

 

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

Попеременно - треугольный  итерационный метод (ПТИМ) может быть представлен в каноническом виде:

.

Здесь — самосопряженный положительный оператор. Его часто называют оператором предобуславливания. Для рассматриваемого метода оператор предобуславливания представляется в виде:

,

где  — единичный оператор, — параметр (действительное число).

При известных  и значение находится в два этапа. Сначала вычисляется невязка на итерации , а затем решается система матричных уравнений:

,

.

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

Оценка количества итераций для этого метода дает:

.

Алгоритм вычисления, в соответствии с ранее приведенными формулами двух этапов ПТИМ будет таков.

Первый этап:

,

.

Второй этап:

,

, .

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

Использование в ПТИМ набора чебышевских итерационных параметров приводит к следующему результату. Расчетные формулы для метода таковы:

,

, ,

, ,

,

,  .

Оценка количества итераций будет:

.

 

 

 

 

 

 

 

 

 

 

 

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

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

 – методы  Якоби и простых итераций с  оптимальным выбором параметра,

 – метод Зейделя,

 – метод верхней релаксации,

 – метод  простых итераций с чебышевским  набором параметров,

 – попеременно - треугольный итерационный метод,

 – попеременно  - треугольный итерационный метод с чебышевским набором параметров.

 

 

 

 

 

 

 

 

 

4. распараллеливание  решения уравнения пуассона с  краевыми условиями дирихле

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

.

в прямоугольнике с краевыми условиями первого рода:

,

,

,

,

где , , , , .

Решим эту задачу методом  Зейделя и распараллелим решение при помощи библиотеки «Gala».

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

Реализация библиотеки «Gala» опирается на низкоуровневые возможности параллельного программирования, предоставляемые платформой Win32 (операционные системы Windows 95, 98, NT, 2000) - потоки, сигналы, мьютексы, семафоры, критические секции, сообщения. Библиотека позволяет выполнять декомпозицию задачи с использованием асинхронных взаимодействующих параллельных процессов и разделяемых ресурсов, существующих в рамках одной Windows-программы.

В результате решения уравнения Пуассона с краевыми условиями Дирихле получилось следующее:

• Без распараллеливания

 

• С распараллеливанием

 

 

 

 

 

 

 

 

Заключение

Бакалаврская работа состоит из четырех глав – первая глава посвящена простейшей постановки задачи. Во второй главе рассмотрены итерационные методы решения уравнения Пуассона. В третьей главе приведена сводка результатов по итерационным методам решения сеточных уравнений. В четвертой главе решено уравнение Пуассона с краевыми условиями Дирихле методом Зейделя с применением распараллеливания.

Из изученного материала  можно сделать следующие выводы:

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

 

 

 

 

 

 

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

1. Самарский А.А. Введение в численные методы.
2. Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. – Т.2. – М.: Наука, 1977.
3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.: БИНОМ, 2004.
4. Марчук Г.И. Методы вычислительной математики. – 3-е изд. – М.: Наука, 1989.
5. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. – М.: Наука, 1967.
6. Самарский А.А. Теория разностных схем. М.:«Наука». 1983.
7. Самарский А.А., Гулин А.В. Численные методы. М.: «Наука». 1989.
8. Владимир Кононов, Вадим Конушин. Применение уравнения Пуассона в задачах обработки изображений. Компьютерная графика и мультимедиа. Выпуск №7(1)/2009.