Метод исключения гаусса. Элементарные преобразования системы линейных уравнений

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

Метод Гаусса

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

1. Система имеет единственное решение (определитель главной матрицы системы не равен нулю);
2. Система имеет бесконечное множество решений;
3. Решений нет, система несовместна.

Итак, у нас есть система (пусть у нее будет одно решение), и мы собираемся решать ее методом Гаусса. Как это работает?

Метод Гаусса состоит из двух этапов – прямого и обратного.

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

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

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

Что можно делать:

1. Можно переставлять строки матрицы местами;
2. Если в матрице есть одинаковые (или пропорциональные) строки, можно удалить их все, кроме одной;
3. Можно умножать или делить строку на любое число (кроме нуля);
4. Нулевые строки удаляются;
5. Можно прибавлять к строке строку, умноженную на число, отличное от нуля.

Обратный ход метода Гаусса

После того как мы преобразуем систему таким образом, одна неизвестная Xn становится известна, и можно в обратном порядке найти все оставшиеся неизвестные, подставляя уже известные иксы в уравнения системы, вплоть до первого.

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

Пример решения системы уравнений методом Гаусс

А теперь - пример, чтобы все стало наглядно и понятно. Пусть дана система линейных уравнений, и нужно решить ее методом Гаусса:

Сначала запишем расширенную матрицу:

Теперь займемся преобразованиями. Помним, что нам нужно добиться треугольного вида матрицы. Умножим 1-ую строку на (3). Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой и получим:

Затем умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Умножим 1-ую строку на (6). Умножим 2-ую строку на (13). Добавим 2-ую строку к 1-ой:

Вуаля - система приведена к соответствующему виду. Осталось найти неизвестные:

Система в данном примере имеет единственное решение. Решение систем с бесконечным множеством решений мы рассмотрим в отдельной статье. Возможно, сначала Вы не будете знать, с чего начать преобразования матрицы, но после соответствующей практики набъете руку и будете щелкать СЛАУ методом Гаусса как орешки. А если Вы вдруг столкнетесь со СЛАУ, которая окажется слишком крепким орешком, обращайтесь к нашим авторам! вы можете, оставив заявку в Заочнике. Вместе мы решим любую задачу!

Суть метода Гаусса состоит в преобразовании (1) к системе с треугольной матрицей , из которой затем последовательно (обратным ходом) получаются значения всех неизвестных. Рассмотрим одну из вычислительных схем. Эта схема называется схемой единственного деления. Итак, рассмотрим эту схему. Пусть a 11 ≠0 (ведущий элемент) разделим на a 11 первое уравнение. Получим
(2)
Пользуясь уравнением (2), легко исключить неизвестные x 1 из остальных уравнений системы (для этого достаточно из каждого уравнения вычесть уравнение (2) предварительно умноженное на соответствующий коэффициент при x 1), то есть на первом шаге получим
.
Иными словами, на 1 шаге каждый элемент последующих строк, начиная со второй, равен разности между исходным элементом и произведением его «проекции» на первый столбец и первую (преобразованную) строку.
Вслед за этим оставив первое уравнение в покое, над остальными уравнениями системы, полученной на первом шаге, совершим аналогичное преобразование: выберем из их числа уравнение с ведущим элементом и исключим с его помощью из остальных уравнений x 2 (шаг 2).
После n шагов вместо (1) получим равносильную систему
(3)
Таким образом, на первом этапе мы получим треугольную систему (3). Этот этап называется прямым ходом.
На втором этапе (обратный ход) мы находим последовательно из (3) значения x n , x n -1 , …, x 1 .
Обозначим полученное решение за x 0 . Тогда разность ε=b-A·x 0 называется невязкой .
Если ε=0, то найденное решение x 0 является верным.

Вычисления по методу Гаусса выполняются в два этапа:

1. Первый этап называется прямым ходом метода. На первом этапе исходную систему преобразуют к треугольному виду.
2. Второй этап называется обратным ходом. На втором этапе решают треугольную систему, эквивалентную исходной.

Назначение метода Гаусса

Виды метода Гаусса

1. Классический метод Гаусса;
2. Модификации метода Гаусса. Одной из модификаций метода Гаусса является схема с выбором главного элемента. Особенностью метода Гаусса с выбором главного элемента является такая перестановка уравнений, чтобы на k -ом шаге ведущим элементом оказывался наибольший по модулю элемент k -го столбца.
3. Метод Жордано-Гаусса;

Пример решения методом Гаусса
Решим систему:

Для удобства вычислений поменяем строки местами:

Умножим 2-ую строку на (2). Добавим 3-ую строку к 2-ой

Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой

Из 1-ой строки выражаем x 3:
Из 2-ой строки выражаем x 2:
Из 3-ой строки выражаем x 1:

Пример решения методом Жордано-Гаусса
Эту же СЛАУ решим методом Жордано-Гаусса.

Последовательно будем выбирать разрешающий элемент РЭ, который лежит на главной диагонали матрицы.
Разрешающий элемент равен (1).



НЭ = СЭ - (А*В)/РЭ
РЭ - разрешающий элемент (1), А и В - элементы матрицы, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

x 1	x 2	x 3	B
1 / 1 = 1	2 / 1 = 2	-2 / 1 = -2	1 / 1 = 1

x 1	x 2	x 3	B
0 / 3 = 0	3 / 3 = 1	1 / 3 = 0.33	4 / 3 = 1.33

x 1	x 2	x 3	B
0 / -4 = 0	0 / -4 = 0	-4 / -4 = 1	-4 / -4 = 1

Реализация метода Гаусса

Использование метода Гаусса

Применение метода Гаусса в теории игр

Применение метода Гаусса при решении дифференциальных уравнений

Применение метода Жордано-Гаусса в линейном программировании

При решении системы уравнений

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

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

Первая модификация метода Гаусса – поиск по строкам. В алгоритме ведущий элемент надо выбирать из условия .

Недостаток модификации. Предположим х i найден с погрешностью D. Тогда при поиске какого-либо х s надо, согласно формуле обратного хода, умножать . При этом погрешность D также умножится на . Если значение велико, то погрешность возрастет.

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

Вторая модификация метода Гаусса – поиск по столбцам. Указанное требование можно обеспечить, если неизвестные х i исключаются в произвольном порядке, а в ведущей строке ищется , доставляющий . Это и будет очередной ведущий элемент. После определения ведущего элемента меняем местами k-й и r-й столбцы .

Внимание. При такой замене меняется нумерация неизвестных x i . Чтобы обеспечить такую замену, надо при программировании ввести массив p 1 ,…p n с настоящими номерами неизвестных. В начале прямого хода все p i = i – обычная нумерация. После нахождения ведущего элемента меняем местами p k и p r . При обратном ходе по формуле (7) вычисляются перенумерованные x i . После вычисления всех неизвестных надо положить y]:=x[i] , и массив y[i] будет окончательным решением задачи.

Третья модификация метода Гаусса – полный поиск. В качестве ведущего выбирается элемент , доставляющий . При этом меняются местами k-й и r-й столбцы, p k и p r , а также m-я и k-я строки. Эта модификация обеспечивает максимальную точность, но и наиболее сложна.

Применение метода Гаусса для решения различных задач линейной алгебры

1. Обращение матриц. Пусть необходимо вычислить обратную матрицу к квадратной матрице А. Обозначим Х = А –1 . Как известно АХ = I, где I – единичная матрица, в которой по диагонали расположены 1, а остальные элементы – 0. Иными словами, i-й столбец матрицы I равен

(1 стоит на i-м месте). Пусть х (i) – i-й столбец матрицы Х. Тогда, в силу правила умножения матриц (строка умножается на столбец) имеем А х (i) = e (i) . Значит, для обращения матрицы надо решить n систем линейных уравнений с одинаковыми матрицами и разными правыми частями:

Ах = е (1) ; Ах = е (2) ; …; Ах = е ( n ) . (2.1)

Решив эти системы, получим, что найденные решения х (1) , х (2) , …, х (n) являются столбцами матрицы А –1 .

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

1) переставляли строки или столбцы в зависимости от модификации метода;

2) делили ведущую строку на ненулевой ведущий элемент;

3) к строкам матрицы прибавляли ведущую строку, умноженную на некоторое число.

Как известно, при таких преобразованиях определитель матрицы претерпевает соответствующие изменения:

1) изменяет знак;

2) делится на тот же элемент;

3) не меняется.

После прямого хода матрица А будет приведена к верхнему треугольному виду с единицами на главной диагонали. Определитель такой матрицы равен, очевидно, 1. С учетом тех изменений, которые претерпевал определитель матрицы А в процессе преобразований, имеем следующую формулу:

det A = (–1) s × a 11 × a 22 ×…× a n n ,

где a j j – ведущие элементы, s – число перестановок строк и/или столбцов при поиске ведущих элементов.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Вручную реализовать метод Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) для данной системы уравнений

и выполнить следующие задания

1) Решить эту систему уравнений

2) Вычислить определитель матрицы данной системы (методом Гаусса – см. п 2 ).

3) Обратить матрицу этой системы (методом Гаусса – см. п 1 ).

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

2. Составить программу решения линейной системы методом Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) и выполнить обращение матриц с использованием этой программы.

Систему уравнений (1.1) представим в виде

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

Метод Гаусса можно интерпретировать как метод, в котором первоначально матрица приводится к верхней треугольной форме (прямой ход), а далее - к единичной (обратный ход). Очевидно, что если матрица единичная, то x t = b r

Пусть матрица системы (1.3) - верхняя треугольная, поэтому a tj = 0 при i > j, т. е. все элементы ниже главной диагонали равны нулю. Тогда из последнего уравнения сразу определяем х п. Подставляя х п в предпоследнее уравнение, находим х а _ х и т. д. Общие формулы имеют вид

При k > I коэффициенты а ы = 0.

Приведем матрицу системы (1.3) к верхней треугольной. Вычтем из второго уравнения системы (1.3) первое, умноженное на такое число, при котором коэффициент при х х обратится в нуль. То же проделаем со всеми остальными уравнениями. В результате все коэффициенты первого столбца, лежащие ниже главной диагонали, обратятся в нуль. Затем, используя второе уравнение, обратим в нуль соответствующие коэффициенты второго столбца. Последовательно продолжая этот процесс, приведем матрицу системы к верхней треугольной форме.

Запишем общие формулы метода Гаусса. Пусть проведено исключение коэффициентов из (А - 1)-го столбца. Тогда останутся уравнения с ненулевыми элементами ниже главной диагонали:

Умножим k-ю строку на число с тк = т > k и вычтем

из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-ro столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется ПРЯМЫМ ХОДОМ МЕТОДА ГАУССА. Вычисление неизвестных по формулам (1.4) называют ОБРАТНЫМ ХОДОМ метода.

Обратный ход можно совершить иначе, если обратить в нуль и все коэффициенты, лежащие выше главной диагонали. Например, элементы п -го столбца обращаются в нуль, если ej^| умножить на (-a^V ax t = б| 2л) , где Ь^ п) - коэффициенты правой части i-го уравнения после указанных преобразований.

На некотором шаге прямого хода может оказаться, что коэффициент aj*" * 0, но мал по сравнению с остальными элементами матрицы системы и, в частности, мал по сравнению с элементами первого столбца. Деление коэффициентов системы на малую величину может привести к значительным ошибкам округления.

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

Для реализации метода требуется примерно п 3 /3 операций типа умножения и п 3 /3 операций типа сложения . Полезно помнить, что оценка числа операций определяется в основном операциями, затрачиваемыми при выполнении прямого хода метода Гаусса. Обратный ход метода Гаусса требует примерно п 2 операций. Следовательно, если требуется решить несколько систем линейных алгебраических уравнений вида Ах = b с одной и той же матрицей и различными правыми частями, то общее число операций при решении S систем будет оцениваться величиной (2/3)п 3 + Sn 2 . В этом случае целесообразно реализовать алгоритм метода Гаусса в виде двух подпрограмм: первая подпрограмма должна реализовывать прямой ход алгоритма и получать на выходе верхнюю треугольную матрицу, а вторая подпрограмма должна, используя полученную матрицу, вычислять решение системы для произвольной правой части.