§ 5.7. Метод Гаусса и разложение матрицы на множители. LU-разложение

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

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

1. Схема единственного деления и LU-разложение.

При выполнении вычислений 1-го шага исключения по схеме единственного деления система уравнений приводится к виду

где

а коэффициенты вычисляются по формулам (5.29), (5.31). Введем матрицу

Как нетрудно проверить, справедливы равенства

т. е. преобразование системы (5.51) к виду (5.52) эквивалентно умножению левой и правой частей системы на матрицу

Аналогично можно показать, что вычисления 2-го шага исключения приводят систему (5.52) к виду

где

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

с верхней треугольной матрицей Здесь

Заметим, что матрица получена из матрицы А последовательным умножением на

Аналогично,

Из равенства (5.54) вытекает следующее представление:

Как легко проверить,

Для этого достаточно перемножить матрицы в результате чего получится единичная матрица.

Введем обозначения Вычисляя матрицу убеждаемся в том, что она имеет следующий вид:

Тогда равенство (5.56) в новых обозначениях примет вид

Это и есть LU-разложение матрицы А — представление матрицы А в виде произведения нижней треугольной матрицы и верхней треугольной матрицы

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

Возможность -разложения обосновывается следующей теоремой.

Теорема 5.3. Если все главные миноры матрицы А отличны от нуля, то существуют единственные нижняя треугольная матрица вида (5.57) и верхняя треугольная матрица такие, что

Структура матриц позволяет организовывать компактное размещение элементов этих матриц в памяти ЭВМ по мере их вычисления. На шаге исключения в области памяти, где первоначально располагалась матрица А, размещается матрица

При этом вся необходимая для дальнейших вычислений информация сохраняется.

Пример 5.12. Проиллюстрируем -разложение на примере решения системы (5.35). На основании данных табл. 5.2 можно записать

Следовательно, -разложение матрицы системы имеет вид

2. Использование LU-разложения.

В современных программах, реализующих метод Гаусса на ЭВМ, вычисления разбивают на два основных этапа. Первый этап — это вычисление -разложения матрицы системы. Второй этап — обработка правых частей и вычисление решения.

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

На втором этапе выполняют следующие действия:

1°. Преобразуют правую часть по формулам прямого хода; необходимые для вычисления коэффициенты берут из матрицы . В результате получают вектор связанный с вектором 6 формулой (5.55).

2°. С помощью обратной подстановки решают систему

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

В случае, если необходимо решить систем уравнений с фиксированной матрицей А и различными правыми частями первый этап проводят лишь один раз. Затем последовательно раз проводят вычисления второго этапа для получения решений Для этого, как и в § 5.6, требуется примерно арифметических операций.

Пример 5.13. Решим систему

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

1-й шаг. После 1-го шага получим

2-й шаг. После 2-го шага найдем

3-й шаг. . В результате прямого хода получен вектор и система приведена к виду

Обратный ход дает значения неизвестных

3. Метод Гаусса с выбором главного элемента и разложение матрицы на множители. В отличие от схемы единственного деления схема частичного выбора предполагает на шаге прямого хода перестановку уравнений системы с номерами и к (при выборе в качестве главного элемента шага элемента а). Это преобразование эквивалентно умножению системы на матрицу которая получается из единичной матрицы перестановкой строк (см. пример 5.14). Исключение неизвестного на шаге по-прежнему эквивалентно умножению системы на матрицу

Таким образом, после 1-го шага система преобразуется к виду где После 2-го шага система преобразуется к виду где

После завершающего шага прямого хода система оказывается приведенной к виду где

Как нетрудно видеть,

Равенство (5.59) равносильно следующему разложению матрицы А на множители:

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

Разложение (5.61) не является -разложением матрицы А. Однако прямой ход по-прежнему равносилен -разложению, но уже не самой матрицы А, а матрицы А, полученной из нее в результате соответствующей перестановки строк. Это разложение имеет вид

где нижняя треугольная матрица, отличающаяся от матрицы (5.57) перестановкой множителей в столбцах.

Пример 5.14. Найдем разложение вида (5.62) для матрицы системы (5.39), используя результаты вычислений примера 5.9. Так как 1-й шаг прямого хода не потребовал перестановки, а на шаге были переставлены второе и третье уравнения, то

Для матрицы А прямой ход уже проводится по схеме единственного деления. Отличие от вычислений примера 5.9 состоит в том, что на шаге множители а также второе и третье уравнения системы (5.40) меняются местами. В результате получим разложение вида (5.62), где

После получения разложения вида (5.62) для решения системы выполняют следующие действия.

1°. Правую часть перестановкой элементов приводят к виду

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

3°. Обратной подстановкой решают систему

Заметим, что матрица перестановки полностью определяется заданием номера уравнения, которое переставляется с уравнением. Поэтому для хранения всей информации о перестановках достаточно целочисленного массива длины

Пример 5.15. Решим систему (5.39), используя полученное в примере 5.14 разложение матрицы А

Здесь вектор преобразуется в вектор перестановкой второго и третьего элементов.

Прямой ход. 1-й шаг. В результате 1-го шага имеем

2-й шаг. . В результате прямого хода правая часть оказалась приведенной к виду

Обратный ход проводится точно так же, как в примере 5.9, и дает значения