БИБЛИОТЕКА

Программное обеспечение автоматизированных систем

БИБЛИОТЕКА

Кожухов А.Е., Фельдман Л.П.
Донецкий национальный технический университет

В этом докладе рассматривается метод Гаусса решения систем линейных алгебраических уравнений. Этот метод относится к классу прямых и находит точное решение СЛАУ за конечное число шагов, пропорциональное количеству неизвестных системы. Основная цель – рассмотрение различных модификаций метода исключения Гаусса и вариантов распараллеливания алгоритма в вычислительной системе с заданной топологией.

1. Задачи, приводящие к решению систем линейных алгебраических уравнений

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

2. Классы методов решения СЛАУ

Все методы решения СЛАУ относятся к двум типам: прямым и итерационным. Прямые методы при поиске решения совершают наперёд известное фиксированное количество действий. Итерационные методы находят решение как последовательность приближений и заканчивают выполнение, когда текущее решение будет удовлетворять заданной точности. Число итераций метода заранее неизвестно [1].

3. Метод исключения переменных Гаусса

Метод Гаусса принадлежит к классу прямых методов решения СЛАУ.

Пусть система уравнений задана матрицей коэффициентов A и вектором свободных членов b. Неизвестными являются элементы вектора x. Размерность матрицы A равна n*n. Вектора свободных членов и неизвестных имеют размерность n.

Решение СЛАУ методом Гаусса состоит в последовательном исключении неизвестных элементов вектора x из системы. Пусть для определённости исходная система уравнений имеет решение, отличное от тривиального.

На первом шаге первое уравнение системы делится на коэффициент при первой неизвестной. Далее для всех оставшихся уравнений выполняются действия:

• умножение коэффициентов первого уравнения на коэффициент при исключаемой переменной текущего уравнения;
• вычитание результата от текущего уравнения системы.

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

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

Вычислительная сложность последовательного варианта метода Гаусса составляет O(n³).

4. Модификации метода Гаусса

Каждый шаг прямого хода метода Гаусса может быть записан в матричной форме. Так элементарная матрица специального вида L_i определяет преобразования, выполняемые на i-ом шаге метода. Тогда прямой ход метода Гаусса осуществляется последовательным умножением слева матрицы A на последовательность матриц L₁, …, L_n. Аналогичные операции выполняются и с вектором b [2].

Матрица A может быть выражена в виде произведения диагональных матриц L и U. Матрица L – произведение элементарных матриц L_i, а U - произведение элементарных матриц, обратных L_i. Операция вычисления элементов матриц L и U – LU-разложение матрицы коэффициентов A.

LU-разложение может быть вычислено по рекуррентным формулам без выполнения операций матричного умножения. Это можно осуществить с помощью методов Дуллитла и Краута, которые отличаются только порядком вычисления элементов матриц L и U. Нахождение L и U – прямой ход метода Гаусса.

Обратный ход метода Гаусса реализуется в 2 этапа. На первом - решается система уравнений Ly=b, где y - вспомогательный вектор неизвестных. На втором - решается система уравнений Ux=y.

Существуют модификации метода Гаусса, основанные на специальных свойствах матрицы коэффициентов A. В конечном счёте, они отличаются только формулами осуществления LU-разложения и количеством выполняемых алгебраических операций.

5. Варианты распараллеливания метода Гаусса и его модификаций

Шаги выполнения прямого и обратного ходов метода Гаусса не могут быть распараллелены простым способом, поскольку результат выполнения одного шага является исходными данными для другого.

Но метод Гаусса допускает распараллеливание на уровне выполняемых алгебраических операций. Это позволяет при определённых коммуникационных расходах [3] одновременно выполнять операции сложения соответствующих элементов начального уравнения и всех оставшихся на каждом шаге. Результатом такой организации работы будет ускорение за счёт одновременного выполнения алгебраических операций. Коммуникационная сложность по сравнению с последовательным вариантом метода возрастёт.

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

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

Литература

• [1] Фельдман Л.П., Петренко А.І., Дмитрієва О.А. Чисельні методи в інформатиці. – К.: Видавнича група BHV, 2006. – 480 с.: іл.
• [2] Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. Пер. с англ. – М.: МИР, 2001. – 430 с.: ил.
• [3] Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем.