Метод Гаусса

В методе Гаусса линейная система

решается в два этапа. На первом этапе система преобразуется к виду (см. рис. 2.1)

,

прямого хода Гаусса

где – верхняя треугольная матрица с единичной диагональю (это так

называемый прямой ход Гаусса). На втором этапе (обратный ход Гаусса) решается система . Рассмотрим эти этапы подробнее.

Прямой ход. Прямой ход Гаусса состоит из n шагов.

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

Умножим первое уравнение на и вычтем его из i -го уравнения преобразованной системы:

Обозначим . Получим

Второй шаг. На втором шаге из системы

исключается аналогичным образом:

K-й шаг. Запишем общий вид преобразованной системы после k-го шага прямого хода Гаусса:

Здесь

Проиллюстрируем, как меняется матрица системы в процессе прямого хода Гаусса на примере системы четвертого порядка (рис. 2.2; ненулевые элементы матрицы обозначены крестиками).

Рис. 2.2. Преобразование матрицы системы 4-го порядка на прямом ходе Гаусса

Оценим количество длинных операций (умножений и делений) на первом шаге прямого хода Гаусса. Преобразование первого уравнения требует n таких операций. Преобразование остальных n- 1 уравнений – n(n- 1 ) операций умножения и деления. Таким образом, первый шаг выполняется за длинных операций. Рассуждая по аналогии, нетрудно найти затраты на остальных n- 1 шагах. Суммарные затраты прямого хода Гаусса определяются в итоге рядом

.

Последняя оценка имеет место для n>> 1.

Обратный ход. Запишем систему, решаемую на обратном ходе, в координатном виде

Ее решение:

Запись означает, что индекс k изменяется от значения n- 1 до 1 с шагом 1.

Требуемое число длинных операций на обратном ходе

Приближенная оценка справедлива для n>> 1.

Общие затраты метода Гаусса:

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