2.2 Вывод расчётных формул для решения слау методом Гаусса.
Прямой ход метода Гаусса.
Как отмечалось выше, процесс решения системы линейных алгебраических уравнений методом Гаусса состоит из двух этапов, называемых прямым и обратным ходом. Первый этап или прямой ход – сводится к приведению исходной системы (1) к треугольному виду.
Первый шаг прямого хода состоит в исключении неизвестного x1 из всех уравнений системы (1), кроме первого уравнения системы.
(1)
Предположим, что a11 0. Это предположение правомерно, так как мы считаем, что система однозначно разрешима и, следовательно, все коэффициенты при x1 одновременно не равны нулю во всех уравнениях системы, поэтому на первое место в системе (1) всегда можно поставить уравнение с отличным от нуля первым коэффициентом.
Тогда разделив коэффициенты первого уравнения системы (1) на a11 получим:
(4)
Пользуясь далее уравнением (4) легко исключить из системы (1) неизвестную x1. Действительно, умножим уравнение (4) на (a21) и сложим полученное уравнение со вторым уравнением системы (1):
-
+
В
результате получим:
.
Аналогично, умножим уравнение (4) на ( a31) и сложим полученное уравнение с третьим уравнением системы (1), получим:
-
+
В результате уравнение 3 заменяется уравнением, не содержащим переменной x1:
Продолжая указанный процесс и исключая неизвестную x1 из последнего n -го уравнения системы (1) получим уравнение:
Таким образом, на первом шаге метода Гаусса, после исключения переменной x1 из всех уравнений системы (1) кроме первого, система (1) перепишется в виде:
или
где коэффициенты (с верхним индексом) при переменных в системе (5) подсчитываются по следующим формулам:
Задаваемые
формулами (6) выражения для коэффициентов
,
системы, полученной после исключения
переменной x1
из всех уравнений исходной системы (1)
кроме первого уравнения, можно записать
компактно в следующем виде (7):
где
i,
j
= 2, 3, …,
n
(7).
Второй шаг прямого хода. На втором шаге прямого хода метода Гаусса проделывается тот же цикл операций, как и на первом шаге, но уже с подсистемой системы (5), не содержащей её первого уравнения (т.е. с подсистемой, коэффициенты которой имеют вид , ). В результате реализации второго шага прямого хода будет получен следующий результат:
где
i,
j
= 3, 4, …, n
.
(n 1) й шаг прямого хода метода Гаусса. Продолжая этот процесс далее, на (n 1)-м шаге прямого хода метода Гаусса исходную систему (1) приведём к треугольному виду, т.е. к системе (9) с верхней треугольной матрицей:
На данном (n 1)-м шаге прямого хода и заканчивается прямой ход метода Гаусса, преобразующий матрицу исходной системы к диагональному виду.
Далее целесообразно проанализировать некоторые выражения, полученные на этапе прямого хода метода Гаусса.
На основе предыдущих рассуждений и формул можно убедиться, что коэффициенты системы (9) могут быть получены из полученных ранее коэффициентов последовательным пересчётом по формулам:
(10)
(11)
В
формуле (10)
верхний индекс k
характеризует номер этапа (по
исключению очередной переменной),
k
должно меняться от 1 до n
1, нижние
индексы i
и j
(в
любой очерёдности)
меняются от k
+ 1 до
n;
по определению при k
=
0 полагаем,
что
В
качестве примера отметим, что если в
формулах (10) считать k
= 0, то в
соответствии с вышесказанным i,
j
= 1, …,
n
и коэффициенты
.
То есть на нулевом шаге метода Гаусса
коэффициенты, определяемые формулами
(10), совпадают с коэффициентами исходной
системы. Действительно, в этом случае,
целая переменная i,
определяющая количество уравнений
системы, меняется от 1 до
n
и поскольку при этом для каждого i
переменная j
также меняется от 1 до
n,
то, значит, для каждого из уравнений мы
имеем n
коэффициентов
,
т.е. это равносильно случаю, когда ещё
не было исключения переменной x1,
и, следовательно, мы имеем дело с исходной
системой (1).
Аналогично,
полагая k
= 1, легко видеть,
что вычисляемые по формуле (10) коэффициенты
совпадают с коэффициентами (6), (7),
полученными для первого шага реализации
прямого
хода метода
Гаусса:
i,
j
= 2, 3, …,
n
и т.д.
Обратный
ход метода Гаусса.
Второй этап,
называемый обратным
ходом метода
Гаусса, сводится к последовательному
вычислению значений неизвестных.
Треугольная структура матрицы системы
(9) позволяет последовательно одно за
другим вычислять значения неизвестных,
начиная с последнего (т.е. с неизвестной
):
…………..
Данное последовательное вычисление неизвестных можно представить компактно в виде одной формулы (11):
. (12)
В
выражении (12) k
полагают равным n,
n
– 1, n
– 2, …, 2, 1
и сумма
по определению считается равной нулю,
если нижний предел суммирования у знака
имеет значение больше верхнего.
ВЫВОД:
Алгоритм решения системы линейных алгебраических уравнений вида (1) методом Гаусса сводится к последовательной реализации вычислений по формулам (10) (12). |
Отметим, что при реализации на ЭВМ прямого хода метода Гаусса нет необходимости действовать непосредственно с переменными x1, x2, …, xn. Достаточно указать алгоритм, согласно которому исходная матрица преобразуется к треугольному виду, и осуществить соответствующее преобразование правых частей системы (1) по формуле (11).
2.3 Численный алгоритм решения СЛАУ методом Гаусса и анализ его свойств
Учитывая цикличность процедур, реализуемых для решения СЛАУ по методу Гаусса на базе формул (10), (12), а также нецелесообразность хранения промежуточных результатов (коэффициентов, пересчитываемых при реализации промежуточных этапов, т.е. всех этапов кроме (n 1)-го) можно записать следующий простой численный алгоритм решения СЛАУ методом Гаусса, пригодный для реализации вычислительной схемы на ЭВМ.
АЛГОРИТМ
ПРЯМОЙ ХОД
1. для k = 1, 2, 3, … , n 1: (цикл 1 по k от1 до n 1)
для i = k + 1, … ,n: (цикл 2 по i от k + 1 до n)
вставка – (алгоритм дополнительной обработки, обсуждаемый ниже);
3.
tik
=
,
4. bi = bi tik bk;
(конец цикла 2);
5. для j = k + 1, … ,n: (цикл 3 по j от k + 1 до n)
6.
=
tik
.
(конец цикла 3);
(конец цикла 1).