П 3.1 Метод Гаусса решения систем линейных алгебраических уравнений

Рассмотрим метод Гаусса. Имеем систему линейных алгебраических уравнений:

(1)

или в матричном виде AX = f, (2)

где А – вещественная квадратная матрица порядка n, f – заданный
и X – искомый векторы. Будем предполагать, что определитель матрицы отличен от нуля.

Метод Гаусса решения системы (1) реализуется в два этапа: прямой и обратный ход. Первый этап состоит в последовательном исключении неизвестных из системы (1). Предположим, что . Разделим первое уравнение на , получаем:

, (3)

где .

Рассмотрим теперь оставшиеся уравнения системы (1):

. (4)

Умножим (3) на и вычтем полученное уравнение из i -ого уравнения системы (4). В результате получим следующую систему уравнений:

(5)

где (6)

Тем самым осуществили первый шаг метода Гаусса и получили систему (5), в которой матрица системы имеет вид:

,

т.е. неизвестное содержится только в первом уравнении.

Если , то из системы (5) можно исключить неизвестное и получить систему, эквивалентную (1) с матрицей следующей структуры:

.

При этом первое уравнение полученной системы остается без изменения.

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

(7)

Матрица системы (7) будет иметь вид верхней треугольной матрицы с единичными элементами на главной диагонали

.

Получение системы (7) составляет прямой ход метода Гаусса, в котором коэффициенты уравнений преобразуются по следующему правилу [18]:

(8)

Вычисление правых частей системы (7) осуществляется по формулам

,

(9)

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

.(10)

Пример 1. Решить систему уравнений методом Гаусса.

Решение:

Прямой ход.

Разделим первое уравнение на 3, получим систему:

Умножим первое уравнение на 2 и сложим со вторым уравнением системы, получим:

Умножим первое уравнение на –2 и сложим с третьим уравнением системы, получим:

Разделим второе уравнение на 1/3, получим:

Умножим второе уравнение на 1/3 и сложим с третьим уравнением системы, получим:

Разделим третье уравнение на 5, получим:

Обратный ход.

Из третьего уравнения находим .

Из второго уравнения находим .

Из первого уравнения получаем .

Установим связь метода Гаусса с LU-разложением. Прямой ход метода Гаусса преобразует исходную систему уравнений (1) в эквивалентную систему

UX = g,(11)

где U – верхняя треугольная матрица с единицами на главной диагонали.

Проанализировав соотношения (9), можно записать:

f = Lg, (12)

где L – нижняя треугольная матрица с ненулевыми элементами , - на главной диагонали. Выразим из последнего уравнения вектор g, получим:

. (13)

Подставляя (13) в (11), получаем

UX =

или

LUX = f. (14)

Сопоставляя (14) и уравнение (2), приходим к выводу, что в результате применения метода Гаусса получено разложение исходной матрицы А в произведение , где L – нижняя треугольная матрица с ненулевыми элементами на главной диагонали, U – верхняя треугольная матрица с единичной главной диагональю [19].

Значения элементов матрицы L и U находятся по рекуррентным соотношениям [19]

,

(15)

Таким образом, метод Гаусса можно трактовать следующим образом. Сначала производится разложение матрицы А в произведение двух треугольных матриц L и U, т.е. , а затем последовательно решаются две системы уравнений [19]:

Lg = f,

UX = g.

Решая первую систему (прямой ход), находим вектор g. Одновременно происходит разложение .

В результате решения второй системы (обратный ход) находим решение задачи – вектор X.

Пример 2. Решить систему методом Гаусса, используя LU-разложение:

Решение:

Выполним операцию факторизации. Представим матрицу системы в виде

При k =1:

При k =2:

При k =3:

В результате получены две треугольные матрицы:

, .

Решим систему линейных уравнений Lg = f. Найдем вектор g:

Решим систему линейных уравнений UX =g. Найдем искомый вектор X:

Пример 3. Реализовать алгоритм LU-разложения для произвольной матрицы.

При описании алгоритма используются объекты класса «SquareMatrix» и методы данного класса: getRowCount (количество строк матрицы), getElement (получение значения элемента) и setElement (установка значения).

Реализация на языке программирования С++ может иметь следующий вид:

void FactorizationAlgorithms:: LU_decomposition (SquareMatrix A, SquareMatrix LU){

int n = A. getRowCount ();

/*Нахождение первого столбца матрицы L и первой строки матрицы U*/

for (int i = 0; i < n; i++){

LU.setElement(i, 0, A.getElement(i, 0));

if ((i+1)<n)

LU.setElement(0,i+1,A.getElement(0,i+1)/LU.getElement(0, 0));

}

/*Вычисление по формулам (15)*/

for (int i = 1; i < n; i++){

for (int j = 1; j < n; j++){

if (i >= j) /*Нижняя треугольная матрица*/

{

double sum = 0;

for (int k = 0; k < j; k++)

sum += LU.getElement(i, k)*LU.getElement(k, j);

LU.setElement(i, j, A.getElement(i, j) - sum);

}

else /*Верхняя треугольная матрица*/

{

sum = 0;

for (int k = 0; k < i; k++)

sum += LU.getElement(i, k)*LU.getElement(k, j);

LU.setElement(i,j,(A.getElement(i,j)-sum)/LU.getElement(i,i));

}

}

}

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

Пример 4. Сформировать на языке программирования С++ алгоритм метода Гаусса на основе факторизации.

При описании алгоритма используются объекты и методы классов «SquareMatrix», «Vector» и «FactorizationAlgorithms».

void DirectMethodsFactorization:: gaussMethod(SquareMatrix A, Vector f){

/*Создание матрицы LU, векторов g и x */

int n = A.getColCount();

SquareMatrix LU = SquareMatrix(n);

Vector x = Vector(n);

Vector g = Vector(n);

/* LU – факторизация. */

FactorizationAlgorithms FA;

FA.LU_decomposition(A, LU);

/* Решение системы Lg = f (прямой ход метода Гаусса), где L – нижняя треугольная матрица с ненулевыми элементами на главной диагонали */

.................................................

/* Решение системы Ux = g (обратный ход метода Гаусса), где U– верхняя треугольная матрица с единичной главной диагональю */

.................................................

/* Вывод вектора - решения */

}

Поиск по сайту: