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

Рассмотрим один из самых распространенных методов решения систем линейных алгебраических уравнений - метод Гаусса. Этот метод (который называют также методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

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

1. Схема единственного деления.

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

Прямой ход состоит из шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного из уравнений с номерами Предположим, что коэффициент Будем называть его главным (или ведущим) элементом 1-го шага.

Найдем величины

называемые множителями 1-ю шага. Вычтем последовательно из второго, третьего, уравнений системы (5.1) первое уравнение, умноженное соответственно на Это позволит обратить в

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

в которой вычисляются по формулам

2-й шаг. Целью этого шага является исключение неизвестного из уравнений с номерами Пусть где - коэффициент, называемый главным (или ведущим) элементом шага. Вычислим множители 2-го шага

и вычтем последовательно из третьего, четвертого, уравнений системы (5.30) второе уравнение, умноженное соответственно на . В результате получим систему

Здесь коэффициенты вычисляются по формулам

Аналогично проводятся остальные шаги. Опишем очередной шаг.

k-й шаг. В предположении, что главный (ведущий) элемент шага отличен от нуля, вычислим множители шага

и вычтем последовательно из уравнений полученной на предыдущем шаге системы уравнение, умноженное соответственно на

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

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

Обратный ход. Из последнего уравнения системы (5.33) находим Подставляя найденное значение в предпоследнее уравнение, получим Осуществляя обратную подстановку, далее последовательно находим Вычисления неизвестных здесь проводятся по формулам

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

Вычисления 1-го шага исключения по формулам (5.29), (5.31) требуют выполнения деления, умножений и вычитаний, т. е. общее число арифметических операций составляет Аналогично, на шаге требуется операций, а на шаге - операций.

Подсчитаем теперь приближенно общее число арифметических операций прямого хода, считая размерность системы достаточно большой:

Как нетрудно видеть, для реализации обратного хода по формулам (5.34) нужно всего операций, что при больших пренебрежимо мало по сравнению с числом операций прямого хода.

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

Пример 5.7. Методом Гаусса решим систему

Прямой ход. 1-й шаг. Вычислим множители Вычитая из второго, третьего и четвертого уравнений системы (5.35) первое уравнение, умноженное на соответственно получим

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

3-й шаг. Вычисляя множитель и вычитая из четвертого уравнения системы (5.37) третье уравнение, умноженное на приводим систему к треугольному виду:

Обратный ход. Из последнего уравнения системы находим Подставляя значение в третье уравнение, находим

Результаты вычислений можно свести в следующую таблицу.

Таблица 5.2 (см. скан)

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

Пример 5.8. Используя метод Гаусса, решим систему уравнений

на -разрядной десятичной ЭВМ.

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

Все вычисления на этом шаге выполняются без округлений.

2-й шаг. После вычисления множителя последнее уравнение системы должно быть преобразовано к виду где Однако на используемой ЭВМ будет получено уравнение

Действительно, коэффициент определяется точно, так как при его вычислении не возникает чисел, мантиссы которых имеют более 6 разрядов. В то же время при вычислении умножение коэффициента 3.0001 на дает 7-разрядное число 105003.5, после округления которого до 6 разрядов получится 105004. Вычисление 62) завершается выполнением операции вычитания: . После округления последнего числа до 6 разрядов мантиссы приходим к уравнению (5.41).

Обратный ход. Из уравнения (5.41) находим и 1.00001. Сравнение с истинным значением показывает, что эта величина получена с очень высокой для используемой ЭВМ точностью. Дальнейшие вычисления дают

После округления имеем .

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

В чем же причина появления такой значительной погрешности? Говорить о накоплении ошибок округления не приходится, так как всего было выполнено 28 арифметических операций и лишь в 4 случаях потребовалось округление. Предположение о плохой обусловленности системы не подтверждается; вычисление дает значение и 100.

В действительности причина состоит в использовании на шаге малого ведущего элемента Следствием этого стало появление большого

множителя и существенное возрастание коэффициента в последнем уравнении системы.

Таким образом, изложенный выше вариант метода Гаусса (схема единственного деления) оказался некорректным и, следовательно, непригодным для вычислений на ЭВМ. Этот метод может привести к аварийному останову (если при некотором и вычисления по нему могут оказаться неустойчивыми.

2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора).

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

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

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

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

Пример 5.9. Решим систему уравнений (5.39) методом Гаусса с выбором главного элемента по столбцу на -разрядной десятичной ЭВМ.

Прямой ход. 1-й шаг. Максимальный в первом столбце элемент матрицы находится в первой строке, поэтому перестановка уравнений не нужна. Здесь 1-й шаг проводится точно так же, как и в примере 5.8.

2-й шаг. Среди элементов матрицы системы (5.40) максимальный принадлежит третьему уравнению. Меняя местами второе и третье уравнения, получим систему

После вычисления последнее уравнение системы преобразуется к виду

Обратный ход. Из последнего уравнения находим Далее, имеем В данном случае ответ получился точным.

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

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

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

Здесь вычисленное на ЭВМ решение системы; его относительная погрешность; число обусловленности матрицы ем - машинное эпсилон; наконец, причем некоторая медленно растущая функция, зависящая от порядка системы (типа степенной функции с небольшим показателем), коэффициент роста.

Наличие в оценке (5.43) множителя указывает на то, что при большом схема частичного выбора может оказаться плохо обусловленной и возможна существенная потеря точности. Однако практика матричных вычислений показывает, что существенный рост элементов матрицы происходит крайне редко. В подавляющем большинстве случаев действительное значение коэффициента роста не превышает 8-10. Если система хорошо обусловлена, то погрешность вычисленного решения оказывается, как правило, малой.

Иногда для проверки качества приближенного решения х

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

где то же, что и в оценке (5.43). Заметим, что в неравенство (5.44) не входит число обусловленности.

3. Метод Гаусса с выборок главного элемента по всей матрице (схема полного выбора).

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

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

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

4. Случаи, когда выбор главных элементов не нужен.

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

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

5. Масштабирование.

Перед началом решения целесообразно масштабировать систему так, чтобы ее коэффициенты были величинами порядка единицы.

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

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

Пусть требуется решить линейную систему уравнений вида:

или в другой форме

В курсе линейной алгебры решения системы уравнений (5.2) представляются по правилу Крамера в виде отношений соответствующих определителей. Если использовать наиболее оптимальный способ расчета определителя, то по правилу Крамера требуется примерно -|п! арифметических операций. Однако существует более оптимальный способ решения системы уравнений (5.2) - метод исключения Гаусса, в рамках которого требуется -|п 3 арифметических действий.

Начнем исследование системы уравнений (5.2) с частного случая, когда матрица системы является верхней треугольной, т. е. все ее элементы ниже главной диагонали равны нулю. Выполняя в командном окне MATLAB oneрацию spy(triu(randn(25))) сгенерируем верхнюю треугольную матрицу и ее графический образ. На рис. 5.1 приведен соответствующий пример верхней треугольной матрицы.

Из последнего уравнения системы с верхней треугольной матрицей находим Х л, подставляя его в предпоследнее уравнение, находим Х„ _i и т. д. - находим все решение. Общая формула для определения Xj-ro имеет вид:

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

Рис. 5.1.

Пусть проведено исключение элементов из k- 1 столбца. Остальные уравнения с не обнуленными столбцами можно записать в виде:

Умножим к-к) строку на число С тк = / оIf 1 , т > к, и вычтем из ш-й

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

Проведение алгоритма (5.4), (5.5) обнуления каждого столбца матрицы ниже главной диагонали заканчивается (п - 1)-м столбцом, при этом вся процедура называется прямым ходом исключения.

Собрав (5.4), (5.5) вместе, будем иметь

или в развернутой форме

Система уравнений (5.6) легко решается обратным ходом по формулам (5.3).

Возможное нарушение в работе алгоритма (5.4), (5.5) может быть связано с тем, что на главной диагонали оказался нулевой элемент а кк " = 0. В этом случае необходимо среди строк матрицы ниже к -й найти такую, у которой на к- м месте находится отличный от нуля элемент. Такая строка обязательно должна найтись, если она не находится, то это значит, что в к- м столбце, начиная с к-го номера все элементы нулевые, а значит, и детерминант матрицы А равен нулю. Перестановкой строк можно переместить подходящую строку в нужное положение.

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

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

Рассмотрим процедуру решения линейной системы уравнений в среде MATLAB. Покажем экспериментально, что в среднем количество операций, осуществляемое центральным процессором при решении линейной системы уравнений, пропорционально кубу порядка матрицы. Покажем, что асимптотически отношение time(n)/n 3 стремится к некоторой предстепенной константе при п -> оо, где time(n) - время работы центрального процессора при данном порядке матрицы п.

В листинге 5.1 приведен код соответствующей программы.

Листинг 5.1

“/«Программа изучения затрат времени “/«центрального процессора при решении %систем линейных уравнений %очищаем рабочее пространство clear all

“/«определяем максимальный порядок “/«обращаемых матриц

птах =1 0 0 0; к =0;

“/«организуем цикл решений систем “/«уравнений вида А X = Ь for п = 1: 10: птах k =к +1; order) к) =п;

“/оформируем случайну матрицу А %и правую часть Ь A=r andn(n); b=randn(n, 1) ;

“/«запоминаем начальный момент времени “/оработы центрального процессора 10 =с рut i me;

“/орешаем линейную систему уравнений %А X = Ь по формуле: X =А Ь А Ь;

“/онаходим последующий момент времени,

“/овычитаем из него предыдущий и “/оделим на куб порядка матрицы

t (к) =(с put i me-10) / n л3; end

“/«строим график зависимости предстепенной “/оконстанты от порядка матрицы А semilogy(order,t);

Рис. 5.2.

На рис. 5.2 приведен график зависимости предстепенной константы отношения времени работы центрального процессора к кубу порядка матрицы от порядка матрицы. Видно, что при П -> оо действительно отношение time(n)/n 3 стремится к некоторой константе, что и подтверждает кубическую зависимость числа операций в методе Гаусса от порядка матрицы.

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

где выбор "+" или зависит от того, четной или нечетной была суммарная перестановка строк.

Процедуру поиска детерминанта матрицы (5.7) изучим на примере стандартной функции MATLAB - det(A), где А - произвольная матрица пхп. Изучим зависимость величины детерминанта матрицы со случайными элементами, распределенными по нормальному закону со средним 0 и стандартным отклонением 1, в зависимости от порядка матрицы.

В листинге 5.2 приведен код соответствующей программы.

Листинг 52

%Программа изучения процедуры поиска детерминанта %матрицы, элементы которой случайные величины,

“/«распределенные по нормальному закону со средним О %и стандартным отклонением 1 %очищаем рабочее пространство clear all

“/«определяем максимальный порядок %анализируемых матриц

птах =3 0 0;

%организуем цикл поиска детерминанта %матрицы А - det(A) for n=l: 5: nmax k =k +1; order) k) =n;

%формируем случайную матрицу A A=r a n d n (n) ;

%вычисляем детерминант матрицы A

%переходим в логарифмическую шкалу %при фиксации значений детерминанта d(k) =si gn(d(к)) *1 оg 10(d(к)); end

%строим график зависимости значений %детерминанта матрицы от порядка матрицы

plot (order, d);

На рис. 5.3 приведен график зависимости логарифма детерминанта случайной матрицы от порядка матрицы. Видно, что детерминант случайной матрицы экспоненциально растет с ростом порядка матрицы.

Рис. 5.3.

Для вычисления обратной матрицы обозначим ее элементы через а 1т, 1,т = 1 , и будем исходить из соотношения АА 1 = Е, тогда верна следующая запись:

Согласно (5.8) /-й столбец обратной матрицы можно рассматривать в качестве неизвестного вектора линейной системы уравнений с матрицей А со специальной правой частью. Таким образом, обращение матрицы сводится к решению линейной системы уравнений п раз с одной и той же матрицей, но с разными правыми частями. Приведение системы к треугольному виду осуществляется только 1 раз, поэтому количество арифметических операций при обращении матрицы лишь в три раза больше, чем при решении системы линейных уравнений, т. е. порядка * 2П 3 .

Рассмотрим теперь функцию inv(A) в среде MATLAB, которая возвращает обратную к А матрицу. В листинге 5.3 приведен код соответствующей программы.

Листинг 53

%Программа изучения процедуры поиска обратной матрицы, Роэлементы которой - случайные величины, распределенные %по нормальному закону со средним 0 и стандартным %отклонением 1

Роочищаем рабочее пространство

%определяем максимальный порядок %анализируемых матриц

пшах=1 0 00; к =0;

Реорганизуем цикл поиска обратной Роматрицы к А - i ПV(А) for п=1: 5: птах k =к +1; о г d е г (к) =п;

Реформируем случайну матрицу А

Ровычисляем обратную к А матрицу Ai nv=i nv(А);

Ренаходим ошибку обращения Е =еуе(п);

е г (к) =п о г ш(A* Ai nv- Е) ; end

Состроим график зависимости значений ошибок

%обращения матриц от порядка матриц

semilogy(order.er);

На рис. 5.4 приведена зависимость ошибки обращения матрицы от ее порядка. Видно, что по мере роста порядка матрицы от 1 до 800 ошибка обращения, выраженная в определенной норме, выросла на пять порядков.

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

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

Метод Гаусса (метод последовательного исключения неизвестных ) заключается в том, что с помощью элементарных преобразований система приводится к эквивалентной системе ступенчатого вида. Сначала с помощью 1-го уравнения исключается x 1 из всех последующих уравнений системы. Затем с помощью2-го уравнения исключается x 2 из 3-го и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса , продолжается до тех пор, пока в левой части последнего уравнения останется только одно неизвестное x n . После этого производится обратный ход метода Гаусса – решая последнее уравнение, находим x n ; после этого, используя это значение, из предпоследнего уравнения вычисляем x n –1 и т.д. Последним находим x 1 из первого уравнения.

Преобразования Гаусса удобно проводить, осуществляя преобразования не с самими уравнениями, а с матрицами их коэффициентов. Рассмотрим матрицу:

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

Пример 5.1. Решить систему методом Гаусса:

Решение . Выпишем расширенную матрицу системы и, используя первую строку, после этого будем обнулять остальные элементы:

получим нули во 2-й, 3-й и 4-й строках первого столбца:

Теперь нужно чтобы все элементы во втором столбце ниже 2-й строки были равны нулю. Для этого можно умножить вторую строку на –4/7 и прибавить к 3-й строке. Однако чтобы не иметь дело с дробями, создадим единицу во 2-й строке второго столбца и только

Теперь, чтобы получить треугольную матрицу, нужно обнулить элемент четвертой строки 3-го столбца, для этого можно умножить третью строку на 8/54 и прибавить ее к четвертой. Однако чтобы не иметь дело с дробями поменяем местами 3-ю и 4-ю строки и 3-й и 4-й столбец и только после этого произведем обнуление указанного элемента. Заметим, что при перестановке столбцов меняются местами, соответствующие переменные и об этом нужно помнить; другие элементарные преобразования со столбцами (сложение и умножение на число) производить нельзя!

Последняя упрощенная матрица соответствует системе уравнений, эквивалентной исходной:

Отсюда, используя обратный ход метода Гаусса, найдем из четвертого уравнения x 3 = –1; из третьего x 4 = –2, из второго x 2 = 2 и из первого уравнения x 1 = 1. В матричном виде ответ записывается в виде

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

Пример 5.2. Исследовать систему методом Гаусса:

Решение . Выписываем и преобразуем расширенную матрицу системы

Записываем упрощенную систему уравнений:

Здесь, в последнем уравнении получилось, что 0=4, т.е. противоречие. Следовательно, система не имеет решения, т.е. она несовместна . à

Пример 5.3. Исследовать и решить систему методом Гаусса:

Решение . Выписываем и преобразуем расширенную матрицу системы:

В результате преобразований, в последней строке получились одни нули. Это означает, что число уравнений уменьшилось на единицу:

Таким образом, после упрощений осталось два уравнения, а неизвестных четыре, т.е. два неизвестных "лишних". Пусть "лишними", или, как говорят, свободными переменными , будут x 3 и x 4 . Тогда

Полагая x 3 = 2a и x 4 = b , получим x 2 = 1–a и x 1 = 2b –a ; или в матричном виде

Записанное подобным образом решение называется общим , поскольку, придавая параметрам a и b различные значения, можно описать все возможные решения системы. à

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

Метод Гаусса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Начинаем осуществлять прямой ход . Считаем, что коэффициент а 11 ≠ 0; если же это не так, меняем местами уравнения.

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

Полученная система равносильна исходной системе.

Вторым шагом исключают неизвестное из всех уравнений, кроме первого и второго. Для этого повторяем все действия первого шага для второго и последующих уравнений, а именно: считаем, что коэффициент
≠ 0 и так далее. Если в результате преобразований получается нулевое уравнение, то его удаляют, если же получается несовместное уравнение, то решение системы закончено – она несовместна. Процесс исключения неизвестных продолжаем до тех пор, пока это возможно. Обозначим количество уравнений, оставшихся после прямого хода, через r . Это число равно рангу основной матрицы системы и может быть меньше или равно n . Рассмотрим оба случая.

1) Если r = n

где с 11 ≠ 0, с 22 ≠ 0, …, с nn ≠ 0.

Обратным ходом , начиная с последнего уравнения, последовательно найдем значения x n , (где x n = ), x n – 1 , ..., x 1 . В этом случае система линейных уравнений имеет единственное решение, то есть является определенной.

2) Если r < n , то система после прямого хода принимает вид:

где с 11 ≠ 0, с 22 ≠ 0, …, с rr ≠ 0. Неизвестные x 1 , x 2 , …, x r , с которых начинаются уравнения, называются главными неизвестными , а остальные x r + 1 , x r + 2 , …, x n – свободными . В этом случае обратным ходом, начиная с последнего уравнения, выражают главные неизвестные через свободные неизвестные. Получают следующие равенства:

x 1 = k 1, r + 1 x r + 1 + … + k 1, n x n + t 1 ,

x 2 = k 2, r + 1 x r + 1 + … + k 2, n x n + t 2 ,

……………………………………..

x r = k r , r + 1 x r + 1 + … + k r , n x n + t r .

Определение 6.10. Общим решением системы называется выражение главных неизвестных через свободные.

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

Пример 6.3. Решить методом Гаусса систему линейных уравнений:

Решение . Преобразования с системой линейных удобнее производить не с самими уравнениями, а с матрицей их коэффициентов. Расширенная матрица этой системы имеет вид: (А |B ) =
.

Осуществляем прямой ход. Первым шагом исключаем неизвестное х 1 из всех уравнений, кроме первого. Так как а 11 = 1 ≠ 0, то переставлять уравнения местами не нужно. Прибавим ко второму уравнению системы первое уравнение, умноженное на (–1), к третьему уравнению – первое, умноженное на (–3). Получим после преобразований следующую матрицу:
, в которой элемент а 22 = 1. Перестановка местами уравнений (первое уравнение трогать не следует) не поможет, поэтому переходим к следующему неизвестному х 3 и исключаем его из всех уравнений, кроме первого и второго. Для этого к третьему уравнению прибавим второе, умноженное на (–2) и вычеркнем получившееся нулевое уравнение. После прямого хода получаем следующую систему:
. Прямой ход завершен. В этом случае n = 4, r = 2, r < n , и, следовательно, система неопределенная. Главные неизвестные – это те неизвестные, с которых начинаются уравнения, в нашем случае это х 1 и х 3 . Неизвестные х 2 и х 4 – свободные.

Обратным ходом надо выразить главные неизвестные через свободные. Для этого в столбцах, содержащих ведущие элементы строк, следует получить нули. Здесь это элемент а 13 . Прибавим к первому уравнению, умноженному на 2, второе и выпишем получившуюся матрицу коэффициентов:
, а затем и сами уравнения:
Из этих уравнений получаем общее решение:

Найдем какое-нибудь частное решение; пусть х 2 = 3, х 4 = 1, тогда из общего решения получим значения х 1 = , и х 1 = –2. Таким образом, частное решение – вектор а = (, 3, –2, 1).