Численные методы решения систем линейных уравнений, страница 3

Решение

Рассмотрим матрицу из примера 2:

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

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

Правило. Если ведущие элементы в методе Гаусса по модулю больше, либо равны 1, то ошибки округления в процессе вычисления подавляются, в противном случае ошибки округления увеличиваются.

Условие устойчивости: .

Сложность метода Гаусса без выбора ведущего элемента

Число арифметических действий, необходимых для реализации метода Гаусса без выбора ведущего элемента пропорционально n³, где n – число линейных уравнений. Записывается это так: , где NA – число арифметических действий. Объем памяти, необходимый для реализации алгоритма, пропорционален  – .

Введем понятие невязки или вектора невязки

Определение. Невязкой или вектором невязки называется вектор: , где  – вычисленное решение системы линейных уравнений .

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

1. На первом шаге прямого хода метода Гаусса выбирается максимальный по модулю элемент в первом столбце. Этот элемент является ведущим. Если он равен нулю, то detA = 0. Если ведущий элемент не является элементом , то перестановкой строк помещаем его в  . При этом соответственно переставляются элементы вектора b. Затем применяются формулы метода Гаусса.

2. На -м шаге прямого хода метода Гаусса непреобразованный столбец – это часть столбца i, начиная с элемента , то есть . Находим максимальный по модулю элемент  в непреобразованном столбце. Этот элемент является ведущим. Если он равен нулю, то detA = 0. Если ведущий элемент не является элементом , то перестановкой строк помещаем его в  . При этом соответственно переставляются элементы вектора b. Затем применяются формулы метода Гаусса.

3. После (n-1)-го шага получаем верхнюю треугольную матрицу U и преобразованный вектор правой части.  Выполняем обратную подстановку.

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

Пример

Решить систему линейных уравнений методом Гаусса с частичным выбором ведущего элемента.

Решение

Рассмотрим ту же систему линейных уравнений, что и в предыдущих примерах.

Прямой ход метода Гаусса

Прежде всего, выбираем максимальный по модулю элемент в первом непреобразованном столбце:

,    , следовательно,  ведущим элементом является 10.

Ведущим  элементом является элемент , поэтому перестановка строк не нужна. Умножим первое уравнение на 0.3 и прибавим ко второму. Умножим первое уравнение на -0.5 и прибавим к третьему. Получим:

 

Рассмотрим следующий непреобразованный столбец:

,   , следовательно, ведущим элементом является 2.5, а не  -0.1, как в методе Гаусса без выбора ведущего элемента. Но ведущий элемент не является элементом    (при ) , поэтому  необходимо переставить строки матрицы А, чтобы элемент 2.5 стал элементом . При перестановке строк необходимо одновременно поменять местами элементы вектора правой части . Получим:

.

Умножим второе уравнение на 0.4 и прибавим к третьему. Получим:

.

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

Обратная подстановка

,        следовательно, ;

,                        ;

,               

Ведущими элементами являются числа: 10, 2.5, 6.2,  все они по модулю больше 1, следовательно,  алгоритм является вычислительно устойчивым.

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