Лекция 8. Метод Гаусса решения систем линейных уравнений

1. Матричное представление метода Гаусса
2. Метод Гаусса с частичным выбором главного элемента
3. Метод Гаусса с полным выбором главного элемента

1. Матричное представление метода Гаусса

Для получения матричного представления метода Гаусса рассмотрим пример. Пусть необходимо решить СЛАУ вида :

,

где . На первом шаге метода Гаусса производятся исключения в первом столбце матрицы СЛАУ при помощи первого уравнения, т.е. путем элементарных эквивалентных преобразований системы в первом столбце матрицы ниже элемента главной диагонали (ниже 10) делаются нули, а это означает, что переменная исключается из всех уравнений системы, кроме первого. Это достигается следующим образом: для получения 0 на месте (2,1) нужно первое уравнение (первую строку матрицы и элемент ) умножить на 0.3 и сложить со вторым уравнением; для получения 0 на месте (3,1) нужно первое уравнение умножить на -0.5 и сложить с третьим уравнением. В итоге получена эквивалентная СЛАУ . Величины 0.3 и -0.5 называются множителями. Запишем их рядом с уравнениями СЛАУ , для которых они использовались:

,

где . Элемент, стоящий на месте (2,2) в полученной матрице , имеет значение, малое по сравнению с другими элементами второго столбца матрицы . Ниже мы остановимся подробно на отрицательных последствиях такого явления для решения СЛАУ, а сейчас просто поменяем местами второе и третье уравнения последней системы, что выведет на место (2,2) элемент 2.5. Получим СЛАУ :

.

Здесь .

На втором шаге метода Гаусса исключим при помощи второго уравнения из третьего, обнулив элемент (3,2) второго столбца. Это достигается путем умножения второго уравнения на 0.04 и сложения с третьим. В итоге получаем эквивалентную СЛАУ :

,

где . Заметим, что проводить исключение во втором столбце (обнуление элемента (3,2)) при помощи первого уравнения было нецелесообразно, т.к. это могло сделать ненулевым элемент (3,1) и «испортить» результат, полученный на предыдущем шаге метода Гаусса (обнуление элементов первого столбца матрицы СЛАУ).

Система - это результат прямого хода метода Гаусса, результат проведенных исключений. В итоге прямого хода получается СЛАУ с верхней треугольной матрицей. Теперь решение треугольной системы осуществляется путем обратной подстановки (снизу вверх). Так последнее уравнение СЛАУ имеет вид: , откуда . Это полученное значение может быть подставлено в предпоследнее уравнение:

.

Подставляя полученные и в первое уравнение , получим .

Решение рассмотренного примера может быть записано в матричном виде. Обозначим

.

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

Непосредственно проверяем, что

.

Обозначим

, тогда .

Матрица отличается от единичной только вторым столбцом, куда записан множитель, использованный при проведении исключения во втором столбце в прямом ходе метода Гаусса. С использованием получаем:

.

Таким образом, из исходной СЛАУ мы пришли к эквивалентной СЛАУ:

,

матрица которой является верхней треугольной, а вектор правой части .

Аналогичные соотношения справедливы и в общем случае для СЛАУ с матрицей размера . Обозначим , матрицу, полученную из единичной матрицы той же перестановкой строк, какая применялась к строкам матрицы СЛАУ на ом шаге исключения (исключения в ом столбце). Таким образом, , - это матрицы перестановок (матрица называется матрицей перестановок, если в каждом ее столбце и в каждой ее строке в точности один элемент равен 1, а все остальные равны 0). Умножение произвольной матрицы на матрицу перестановок слева поменяет местами в матрице строки с соответствующими номерами, а умножение на матрицу перестановок справа поменяет в столбцы с теми же номерами.

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

,

где - соответствующие элементы матрицы СЛАУ после 1 шага метода Гаусса (после исключения, проведенного в 1 столбце).

В принятых обозначениях матричный вид прямого хода метода Гаусса следующий:

.

Матрица итоговой СЛАУ - верхняя треугольная. Полученная СЛАУ легко решается путем обратной подстановки. Если предположить, что перестановки в ходе исключений не делались, то

.

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

Здесь - элементы матрицы СЛАУ после 1 го шага исключения, - элементы матрицы СЛАУ после го шага исключения. В матричном виде эти действия просто эквивалентны умножению на матрицу исключения. Поскольку , при этом матрица невырожденная, а значит, обратимая, обратная к ней – нижняя треугольная, то , а это есть ничто иное, как треугольное разложение матрицы .

Диагональные элементы матрицы называются ведущими, или главными; ый ведущий элемент – это коэффициент при ом неизвестном в ом уравнении на ом шаге исключения Гаусса (исключений в ом столбце матрицы). В предыдущем примере ведущими элементами были 10, 2.5 и 6.2.

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

Пример. Решить СЛАУ :

.

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

. (10)

Для решения полученной СЛАУ с верхней треугольной матрицей применяем обратный ход метода Гаусса. Второе уравнение СЛАУ имеет вид: , откуда . Предположим, что в нашей вычислительной системе количество разрядов в мантиссе равно , тогда . Если полученное значение сравнить с точным значением решения данной СЛАУ, то качественно очевидно, что хорошо приближает . Продолжим обратный ход метода Гаусса подставляя в первое уравнение СЛАУ : , откуда , что «абсольтно не похоже» на точное значение решения данной СЛАУ.

Что произошло, где была допущена катастрофическая ошибка? Здесь не было накопления ошибок округления, вызываемого выполнением большого количества аоифметических операций. Матрица исходной СЛАУ далека от вырожденной: . Полученный результат имеет только одно объяснение: при проводимом исключение ведущий элемент 0.0001 имел значение, малое по сравнению с другими элементами матрицы, что привело в процессе исключения к колосальному росту коэффициентов второго уравнения: . Эти коэффициенты в 10⁴ раз стали превосходить коэффициенты исходной задачи. Ошибка округления, произошедшая при вычислении и равная , является малой и приемлемой по отношению к большим коэффициентам уравнения , но совершенно неприемлемой с точки зрения уровня элементов исходной матрицы (ведь там есть элемент 0.0001, который меньше, чем абсолютная погрешность ). Таким образом необходимо при проведении процесса исключения обеспечивать следующее условие: модули значений ведущих элементов не должны быть малыми по сравнению с модулями других элементов матрицы СЛАУ.

1. Метод Гаусса с частичным выбором главного элемента

Для обеспечения устойчивости процесса исключения Гаусса необходимо позаботиться о том, чтобы ведущие элементы имели значения, сравнимые со значениями остальных элементов матрицы СЛАУ. Это можно обеспечить различными способами. Рассмотрим один из них, который называется частичным выбором главного элемента.

Частичный выбор главного элемента может осуществляться по столбцу или по строке. Начнем с выбора по столбцу.

Рассматривается СЛАУ :

. (20)

Перед проведением исключений в первом столбце выберем в этом столбце максимальный по модулю элемент. Пусть этот элемент . Выведем этот элемент на место ведущего (на место (1,1)) для первого шага метода Гаусса. Для этого в СЛАУ (20) поменяем местами первое и ое уравнения. Получим СЛАУ:

(30)

Теперь проведем исключение в первом столбце матрицы СЛАУ (30). В результате исключения СЛАУ (30) примет вид:

(40)

В (40) выделены те коэффициенты, которые изменяются (подвергаются пересчету в соответствии с формулой (5)) в процессе исключения. Обозначим полученную систему :

.

Перед проведением исключений второго шага метода Гаусса выберем максимальный по модулю элемент второго столбца матрицы СЛАУ (40), исключая при выборе элемент стоящий в первой строке (область выбора обозначена в предыдущей формуле). Пусть этот элемент . Выводим его на место ведущего элемента для второго шага исключений – на место (2,2) путем перестановки второго и го уравнений (элемент не участвовал при выборе максимального по модулю элемента в силу того, что перестановка первой строки на место второй, в том случае, если бы оказался максимальным по модулю, привела бы к порче структуры матрицы, полученной на первом шаге исключения: нулевой элемент первого столбца, стоящий во второй строке, стал бы ненулевым за счет того, что на место (2,1) попал бы элемент ). В результате получим СЛАУ:

(50)

Теперь проведем исключение во втором столбце матрицы СЛАУ (50). В результате исключения СЛАУ (50) примет вид:

Перед проведением третьего шага исключения Гаусса (обнуления элементов третьего столбца матрицы СЛАУ ниже главной диагонали) выберем максимальный по модулю элемент третьего столбца среди элементов, исключающих элементы первой и второй строк. Выведем этот элемент на позицию (3,3) – позицию ведущего элемента для третьего шага. И т.д.

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

Частичный выбор главного элемента обеспечит сравнимость ведущих элементов на всех шагах исключения Гаусса с остальными элементами соответствующих столбцов (строк) матрицы СЛАУ, т.е. обеспечит устойчивость исключений Гаусса.

1. Метод Гаусса с полным выбором главного элемента

Выбор главного элемента, предваряющий исключение на очередном шаге метода Гаусса, можно проводить, учитывая большее количество элементов матрицы СЛАУ. Так перед исключением в первом столбце выберем максимальный по модулю элемент во всей матрице системы . Пусть этот элемент - . Для того, чтобы вывести этот элемент на место (1,1), переставим в первую и ую строки (соответственно в векторе - первый и ый элементы), первый и ый столбец, после чего проведем исключения в первом столбце.

Перед исключением в ом столбце выберем максимальный по модулю элемент в матрице СЛАУ среди ее элементов , где . И т.д.

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