Выдержка из текста работы
Значительное число задач физики и техники приводят к дифференциальным уравнениям в частных прозводных (уравнения математической физики). Установившиеся процессы различной физической природы описываются уравнениями эллиптического типа. Точные решения краевых задач для эллиптических уравнений удаётся получить лишь в частных случаях. Поэтому эти задачи решают в основном приближённо. Одним из наиболее универсальных и эффективных методов, получивших в настоящее время широкое распространение для приближённого решения уравнений математической физики, является метод конечных разностей или метод сеток.
Суть метода состоит в следующем. Область непрерывного изменения аргументов, заменяется дискретным множеством точек (узлов), которое называется сеткой или решёткой. Вместо функции непрерывного аргумента рассматриваются функции дискретного аргумента, определённые в узлах сетки и называемые сеточными функциями. Производные, входящие в дифференциальное уравнение и граничные условия, заменяются разностными производными, при этом краевая задача для дифференциального уравнения заменяется системой линейных или нелинейных алгебраических уравнений (сеточных или разностных уравнений). Такие системы часто называют разностными схемами. И эти схемы решаются относительно неизвестной сеточной функции.
Параллельное решение систем линейных алгебраических уравнений Методом Зейделя
Задача нахождения решения СЛАУ
где — матрица СЛАУ; — вектор правой части; ( — ранг матрицы ); — матрица, полученная из путем приписывания к ней справа вектора ; — множество, содержащее элементы, над которыми определены операции сложения и умножения, относится к классу задач линейной алгебры и для ее решения разработан целый ряд численных методов. Среди них немаловажное место занимает метод Зейделя, для которого итерационный процесс имеет следующий вид
, (1)
где — вектор приближения, вычисляемый на n-ом шаге итерации (вектор n-го приближения); — матрица итерации; — вектор итерации; — вектор начального приближения; , .
Матрица и вектор итерации определяются соотношениями , , где — параметр итерации.
В качестве оценки близости вектора n-го приближения к вектору-решению может использоваться оценка относительной погрешности вычисления: ,. Нашей целью будет построение параллельного алгоритма данного метода, что продиктовано наличием параллельных вычислительных систем, способных давать выигрыш при вычислениях по сравнению с их последовательными аналогами.
Рекуррентные формулы Зейделя обладают той особенностью, что компоненты вектора приближений не могут вычисляться параллельно. Они определяются последовательно, друг за другом, и каждое новое значение выражается через найденные предыдущие. Несмотря на это, имеется возможность распараллеливания рассматриваемого итерационного процесса. Мы не будем модифицировать метод с целью повышения его степени параллелизма, а рассмотрим непосредственно метод Зейделя, представленный формулами (1). При этом будем предполагать, что каждый шаг итерации алгоритма может быть выполнен параллельно.
Параллелизм метода Зейделя
Характер задачи полностью определяется формулами (1), поэтому процедура построения метода параллельного вычисления должна быть основана на них.
Будем предполагать, что в нашем распоряжении имеются p ветвей алгоритма, способных проводить вычисления независимо друг от друга. Присвоим каждой ветви ее порядковый номер, причем нумерацию начнем с нуля. Будем также считать, что все ветви равноценны в вычислительном отношении. Это означает, что вычисления, проводимые над заданным набором данных выполняются всеми ветвями за одно и то же время (время вычислений не зависит от порядкового номера ветви). Порядок проведения вычислений каждой ветвью, а также процедуры взаимодействия, осуществляемые при этом, будем описывать с помощью параллельного алгоритма (p-алгоритма).
Заметим, что в (1) для фиксированного () все произведения могут выполняться параллельно. После суммирования результатов умножений получается i-ая компонента вектора нового приближения. Указанное параллельное вычисление будет иметь смысл только в случае, когда количество ветвей алгоритма меньше либо равно размерности задачи. При равенстве указанных параметров мы получаем случай, когда каждая ветвь производит одно умножение при вычислении очередной компоненты вектора. При этом было бы правильным каждый столбец матрицы , а также соответствующие компоненты векторов приближений, обрабатывать в отдельной ветви алгоритма. Если столбцы матрицы пронумеровать слева направо, начиная с нуля, то k-ый () столбец используется в ветви с номером k. Компоненты вектора итерации также распределим по ветвям так, что компонента с номером k () достается ()-ой ветви.
Рис. 1. Декомпозиция данных для случая, когда
На рис. 1 в прямоугольники заключены данные, получаемые k-ой ветвью в результате указанной декомпозиции. .
Параллельное вычисление вектора n-го приближения состоит в последовательном нахождении его компонент по формулам (1), причем операции умножения, необходимые для этого, выполняются ветвями параллельно. Результаты произведений должны быть просуммированы, что осуществляется путем взаимодействия ветвей алгоритма. Максимальная эффективность при суммировании достигается в случае, когда ветви организуют двоичное дерево коммуникаций.
На рис. 2, а приведено дерево для семи ветвей алгоритма. Каждому узлу дерева соответствует своя ветвь алгоритма. Обозначим за слагаемое, содержащееся в -ом узле дерева. Стрелками показано направление передачи результатов суммирования (частичных сумм). Процедура получения суммы называется сдваиванием относительно операции суммы. Она производится снизу-вверх путем последовательного выполнения элементарных сдваиваний, осуществляемых тройкой узлов. Указанная тройка представляет собой поддерево исходного дерева (см. рис. 2, б) и является 3-х узловым шаблоном взаимодействия. Получение суммы осуществляется в следующей последовательности. Узел получает от узла величину и увеличивает на принятую величину. Затем выполняется аналогичное взаимодействие с узлом и выполняется пересчет значения :. В итоге узел содержит сумму величин, хранящихся в рассмотренном поддереве. При этом будем говорить, что к узлу применена операция сдваивания на шаблоне . Полученная в результате сумма затем выступает в качестве элементарного слагаемого в поддереве, для которого является дочерним узлом, и т. д. Процедура получения суммы всех элементов дерева завершается после применения операции сдваивания к корневому узлу. Несложно заметить, что при суммировании существуют сдваивания, которые можно выполнять параллельно. Соответствующие тройки узлов лежат на одном уровне дерева, а количество этих уровней равно: , где — целая часть числа .
Возвращаясь к формулам (1), заметим, что -ая компонента вектора нового приближения, получаемая при сдваивании, предназначена для дальнейшего использования в ветви с номером . Поэтому целесообразно именно эту ветвь соотнести с корневым узлом дерева сдваивания. Указанное предложение может быть реализовано с помощью динамического дерева, в котором корню по очереди соответствуют все ветви алгоритма.
Опишем порядок выполнения параллельных вычислений для случая, когда . Пусть- предыдущее значение компоненты вектора приближения, используемое -ой ветвью алгоритма, — значение, используемое ветвью при вычислениях по формулам (1).
Параллельный алгоритм метода Зейделя
(-алгоритм Зейделя; случай, когда ).
Последовательность вычислений, проводимая -той () ветвью алгоритма, представляет собой периодическое выполнение следующих действий.
1) Участие в параллельном нахождении j-ой () компоненты нового вектора. При этом возможны два случая:
a) ; здесь ветвь вычисляет , а затем использует найденную величину в процедуре сдваивания на дереве коммуникаций;
b) , т.е. ветвь участвует в вычислении соответствующей ей компоненты вектора нового приближения; для этого находится величина и далее выполняется сдваивание величин (), и пересчет и : ; (результат сдваивания).
2) Проверка условия завершения процесса вычисления после вычисления всех компонент нового вектора. Взаимодействие при проверке также осуществляется на дереве коммуникаций. Норма вектора, необходимая для оценки близости найденного вектора к точному решению может быть вычислена различными способами, каждый из которых определяет свой порядок взаимодействия ветвей. В любом случае, в качестве исходных данных в узлах дерева выступают величины и . В случае невыполнения условия окончания работы , где — заданная относительная погрешность вычисления принимается решение о продолжении вычислений, начиная с п. 1.
Отметим, что результат проверки должен быть получен во всех ветвях алгоритма. Это означает, что после сдваивания необходимо распределить флаг окончания работы по всем ветвям алгоритма. Указанное распределение может быть выполнено в направлении, обратном направлению сдваивания, т. е. сверху-вниз. При этом осуществляется взаимодействие узлов в противоположном направлении (передача информации от узла-предка к узлу-потомку). Так же как и для сдваивания, для распределения можно выделить тройки узлов, взаимодействующих параллельно. Они лежат на одном уровне дерева коммуникаций, а количество этих уровней равно .
Имея в распоряжении параллельный алгоритм, хотелось бы выяснить целесообразность его использования. Для этого нам необходимо оценить время, которое требуется для проведения вычислений по последовательному и параллельному алгоритмам.
Пусть T1— время выполнения последовательного алгоритма, Tp— время выполнения -алгоритма. Базовые операции, используемые в (1), а также проверка условия окончания вычислений требуют определенных временных затрат. Будем считать, что:
1) время, необходимое для выполнения операции сложения равно ;
2) время, затрачиваемое на выполнение операции умножения равно ;
3) время сравнения двух операндов — ;
4) количество итераций последовательного и параллельного алгоритмов равно ;
5) время передачи элементов от одной ветви другой — ;
6) при проверке условия окончания работы вычисляется кубическая норма .
Можно показать, что тогда время вычислений по последовательному и параллельному алгоритмам будет оцениваться соответственно следующими выражениями:
Оценка ускорения представленного алгоритма имеет вид . На рис. 3 приведен график зависимости ускорения алгоритма от количества параллельных ветвей. Он построен в предположении, что , и . Как видно из рисунка ускорение растет с ростом размерности задачи. Однако оно растет очень медленно, что объясняется наличием частых и продолжительных взаимодействий между ветвями алгоритма. Несмотря на это, существует возможность ускорить процесс вычисления и получить выигрыш во времени.
В настоящей работе рассмотрен общий подход к распараллеливанию итерационного метода Зейделя, предназначенного для решения СЛАУ. Построен алгоритм для случая, когда количество ветвей алгоритма равно размерности задачи. Полученные результаты следует рассматривать как отправную точку при построении алгоритмов для более общего случая. Приведенная оценка ускорения не исключает возможности получения выигрыша при параллельных вычислениях, что говорит о целесообразности использования параллельных вычислительных систем для решения СЛАУ большой размерности.
Пример
Методом Зейделя решить систему уравнений
Приведем эту систему к виду, удобному для итерации:
В качестве нулевых приближений корней возьмем:
Применяя процесс Зейделя, последовательно получим:
Результаты вычислений с точностью до четырех знаков приведены в Таблице 2.
Таблица 2. Нахождение корней линейной системы методом Зейделя
|
i |
||||
|
0 |
1,2000 |
0,0000 |
0,000 |
|
|
1 |
1,2000 |
1,0600 |
0,9480 |
|
|
2 |
0,9992 |
1,0054 |
0,9991 |
|
|
3 |
0,9996 |
1,0001 |
1,0001 |
|
|
4 |
1,000 |
1,000 |
1,000 |
|
|
5 |
1,000 |
1,000 |
1,000 |
Точные значения корней: х1 = 1; х2 = 1; х3 = 1.
Список использованной литературы
http://www.exponenta.ru/default.asp — образовательный математический сайт
«Математические задачи электроэнергетики» — Веников В.А.
