Метод Гаусса для решения систем линейных уравнений
1.
Система линейных алгебраических
уравнений
1.1
Понятие системы линейных алгебраических
уравнений
Система
уравнений – это условие, состоящее в одновременном выполнении нескольких
уравнений относительно нескольких переменных. Системой линейных алгебраических
уравнений (далее – СЛАУ), содержащей m уравнений и n неизвестных, называется
система вида:
где числа aij
называются коэффициентами системы, числа bi – свободными членами, aij
и bi (i=1,…, m; b=1,…, n) представляют собой некоторые
известные числа, а x1,…, xn – неизвестные. В
обозначении коэффициентов aij первый индекс i обозначает
номер уравнения, а второй j – номер неизвестного, при котором стоит этот
коэффициент. Подлежат нахождению числа xn. Такую систему удобно
записывать в компактной матричной форме: AX=B. Здесь А – матрица
коэффициентов системы, называемая основной матрицей;
– вектор-столбец из неизвестных xj.
– вектор-столбец из свободных членов bi.
Произведение
матриц А*Х определено, так как в матрице А столбцов столько же, сколько строк в
матрице Х (n штук).
Расширенной
матрицей системы называется матрица A системы, дополненная столбцом
свободных членов
1.2
Решение системы линейных алгебраических
уравнений
Решением
системы уравнений называется упорядоченный набор чисел (значений переменных),
при подстановке которых вместо переменных каждое из уравнений системы
обращается в верное равенство.
Решением
системы называется n значений неизвестных х1=c1, x2=c2,…, xn=cn, при
подстановке которых все уравнения системы обращаются в верные равенства. Всякое
решение системы можно записать в виде матрицы-столбца
Система
уравнений называется совместной, если она имеет хотя бы одно решение, и
несовместной, если она не имеет ни одного решения.
Совместная
система называется определенной, если она имеет единственное решение, и
неопределенной, если она имеет более одного решения. В последнем случае каждое
ее решение называется частным решением системы. Совокупность всех частных
решений называется общим решением.
Решить
систему – это значит выяснить, совместна она или несовместна. Если система
совместна, найти ее общее решение.
Две системы
называются эквивалентными (равносильными), если они имеют одно и то же общее
решение. Другими словами, системы эквивалентны, если каждое решение одной из
них является решением другой, и наоборот.
Преобразование,
применение которого превращает систему в новую систему, эквивалентную исходной,
называется эквивалентным или равносильным преобразованием. Примерами
эквивалентных преобразований могут служить следующие преобразования:
перестановка местами двух уравнений системы, перестановка местами двух
неизвестных вместе с коэффициентами у всех уравнений, умножение обеих частей
какого-либо уравнения системы на отличное от нуля число.
Система
линейных уравнений называется однородной, если все свободные члены равны нулю:
Однородная
система всегда совместна, так как x1=x2=x3=…=xn=0 является решением системы.
Это решение называется нулевым или тривиальным.
2.
Метод исключения Гаусса
2.1 Сущность метода исключения Гаусса
Классическим
методом решения систем линейных алгебраических уравнений является метод
последовательного исключения неизвестных – метод Гаусса (его еще
называют методом гауссовых исключений). Это метод последовательного исключения
переменных, когда с помощью элементарных преобразований система уравнений
приводится к равносильной системе ступенчатого (или треугольного) вида, из
которого последовательно, начиная с последних (по номеру) переменных, находятся
все остальные переменные.
Процесс
решения по методу Гаусса состоит из двух этапов: прямой и обратный ходы.
1.
Прямой ход.
На первом
этапе осуществляется так называемый прямой ход, когда путём элементарных
преобразований над строками систему приводят к ступенчатой или треугольной
форме, либо устанавливают, что система несовместна. А именно, среди элементов
первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее
положение перестановкой строк и вычитают получившуюся после перестановки первую
строку из остальных строк, домножив её на величину, равную отношению первого
элемента каждой из этих строк к первому элементу первой строки, обнуляя тем
самым столбец под ним.
После того,
как указанные преобразования были совершены, первую строку и первый столбец
мысленно вычёркивают и продолжают пока не останется матрица нулевого размера.
Если на какой-то из итераций среди элементов первого столбца не нашёлся
ненулевой, то переходят к следующему столбцу и проделывают аналогичную
операцию.
На первом
этапе (прямой ход) система приводится к ступенчатому (в частности,
треугольному) виду.
Приведенная
ниже система имеет ступенчатый вид:
,
где
Коэффициенты
aii называются главными (ведущими) элементами системы.
1-й шаг.
Будем
считать, что элемент (если a11=0, переставим строки матрицы так, чтобы a11
не был равен 0. Это всегда возможно, т. к. в противном случае
матрица содержит нулевой столбец, ее определитель равен нулю и система
несовместна).
Преобразуем
систему, исключив неизвестное х1 во всех уравнениях, кроме первого (используя
элементарные преобразования системы). Для этого умножим обе части первого
уравнения на и
сложим почленно со вторым уравнением системы (или из второго уравнения почленно
вычтем первое, умноженное на ). Затем умножим обе части первого уравнения на и
сложим с третьим уравнением системы (или из третьего почленно вычтем первое,
помноженное на ). Таким
образом, последовательно умножаем первую строку на число и
прибавляем к i-й строке, для i=2, 3, …, n.
Продолжая
этот процесс, получим эквивалентную систему:
Здесь
– новые значения коэффициентов при неизвестных и свободные
члены в последних m-1 уравнениях системы, которые определяются формулами:
Таким
образом, на первом шаге уничтожаются все коэффициенты, лежащие под первым
ведущим элементом a110, на втором шаге уничтожаются элементы,
лежащие под вторым ведущим элементом а22(1) (если a22(1)0) и
т.д. Продолжая этот процесс и дальше, мы, наконец, на (m-1) шаге приведем
исходную систему к треугольной системе.
Если в
процессе приведения системы к ступенчатому виду появятся нулевые уравнения, т.е.
равенства вида 0=0, их отбрасывают. Если же появится уравнение вида то
это свидетельствует о несовместности системы.
На этом прямой ход метода Гаусса заканчивается.
2.
Обратный ход.
На втором
этапе осуществляется так называемый обратный ход, суть которого заключается в
том, чтобы выразить все получившиеся базисные переменные через небазисные и
построить фундаментальную систему решений, либо, если все переменные являются
базисными, то выразить в численном виде единственное решение системы линейных
уравнений.
Эта
процедура начинается с последнего уравнения, из которого выражают
соответствующую базисную переменную (она в нем всего одна) и подставляют в
предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх.
Каждой
строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге,
кроме последнего (самого верхнего), ситуация в точности повторяет случай
последней строки.
Примечание:
на практике удобнее работать не с системой, а с расширенной ее матрицей,
выполняя все элементарные преобразования над ее строками. Удобно, чтобы
коэффициент a11 был равен 1 (уравнения переставить местами, либо разделить обе
части уравнения на a11).
2.2
Примеры решения СЛАУ методом Гаусса
В
данном разделе на трех различных примерах покажем, как методом Гаусса можно
решить СЛАУ.
Пример
1. Решить СЛАУ 3-го порядка.
Обнулим
коэффициенты при во второй и третьей строчках. Для
этого домножим их на 2/3 и 1 соответственно и сложим с первой строкой:
Теперь
обнулим коэффициент при в третьей строке, домножив вторую
строку на 6 и вычитая из неё третью:
В
результате мы привели исходную систему к треугольному виду, тем самым закончив
первый этап алгоритма.
На
втором этапе разрешим полученные уравнения в обратном порядке. Имеем:
из третьего;
из второго, подставив
полученное ;
из первого, подставив
полученные и .
В
случае, если число уравнений в совместной системе получилось меньше числа
неизвестных, то тогда ответ будет записываться в виде фундаментальной системы
решений.
Пример 2.
Решить неопределенную СЛАУ 4-го порядка:
В
результате элементарных преобразований над расширенной матрицей системы
исходная
система свелась к ступенчатой, где количество уравнений меньше, чем количество
неизвестных:
Поэтому
общее решение системы: x2=5x4–13x3–3; x1=5x4–8x3–1. Если положить, например, что x3=0, x4=0, то найдем одно из частных решений этой системы x1=-1, x2=-3, x3=0, x4=0.
Условие:
х1 – 2х2 – х3 + х4 = 1
х1 – 8х2 – 2х3 – 3х4 = -2
2х1 + 2х2 – х3 + 7х4 = 7
х1 + х2 + 2х3 + х4 = 1
Перепишем систему линейных алгебраических уравнений в матричную
форму. Получится матрица 4х5,
слева от разделительной линии стоят коэффициенты при переменных, а справа стоят
свободные члены.
1 -2 -1 1 | 1
1 -8 -2 -3 | -2
2 2 -1 7 | 7
1 1 2 1 | 1
Проведём следующие действия:
a)
из второй строки вычтем первую строку (cтрока 2 – строка 1);
b)
из третьей строки вычтем первую строку, умноженную на 2 (cтрока 3–2 х строка 1)
c)
из четвертой строки вычтем первую строку (cтрока 4 – строка 1). Получим:
1 -2 -1 1 | 1
0 -6 -1 -4 | -3
0 6 1 5 | 5
0 3 3 0 | 0
Проведём следующие действия:
a)
к третьей строке прибавим вторую строку (строка 3 + строка 2);
b)
четвертую строку поделим на 3 (строка 4 = строка 4 / 3). Получим:
1 -2 -1 1 | 1
0 -6 -1 -4 | -3
0 0 0 1 | 2
0 1 1 0 | 0
Проведём следующие действия:
a)
четвертую строку поставим на место второй строки;
b)
третью строку поставим на место четвертой строки;
c)
вторую строку поставим на место третьей строки. Получим:
1 -2 -1 1 | 1
0 1 1 0 | 0
0 -6 -1 -4 | -3
0 0 0 1 | 2
К третьей строке прибавим вторую строку, умноженную на 6 (строка 3 + 6 × строка 2).
Получим:
1 -2 -1 1 | 1
0 1 1 0 | 0
0 0 5 -4 | -3
0 0 0 1 | 2
Проведём следующие действия:
a)
к третьей строке прибавим четвертую, умноженную на 4 (строка3 + 4×строка4);
b)
из первой строки вычтем четвертую строку (строка 1 – строка 4);
c)
третью строку поделим на 5 (строка
3 = строка 3 / 5). Получим:
1 -2 -1 1 | 1
0 1 1 0 | 0
0 0 1 0 | 1
0 0 0 1 | 2
Проведём следующие действия:
a)
из второй строки вычтем третью строку (строка 2 – строка 3);
b)
к первой строке прибавим третью строку (строка 1 + строка 3). Получим:
1 -2 0 0 | 0
0 1 0 0 | -1
0 0 1 0 | 1
0 0 0 1 | 2
c)
К первой строке прибавим вторую строку, умноженную на 2 (строка 1 + 2 × строка 2). Получим:
1 0 0 0 | -2
0 1 0 0 | -1
0 0 1 0 | 1
0 0 0 1 | 2
В левой части матрицы по главной диагонали остались одни единицы.
В правом столбце получаем решение:
х1 = -2
х2 = -1
х3 = 1
х4 = 2
3.
Преимущества и недостатки метода Гаусса
Итак,
метод Гаусса применим
к любой системе линейных уравнений, он идеально подходит для решения систем,
содержащих больше трех линейных уравнений. Метод Гаусса решения СЛАУ с числовыми коэффициентами в
силу простоты и однотипности выполняемых операций пригоден для счета на
электронно-вычислительных машинах.
Достоинства метода:
a)
менее трудоёмкий по сравнению с другими методами;
b)
позволяет однозначно установить, совместна система или нет, и если
совместна, найти её решение;
c)
позволяет найти максимальное число линейно независимых
уравнений – ранг матрицы системы.
Существенным
недостатком этого метода является невозможность сформулировать условия
совместности и определенности системы в зависимости от значений коэффициентов и
свободных членов. С другой стороны, даже в случае определенной системы этот
метод не позволяет найти общие формулы, выражающие решение системы через ее
коэффициенты и свободные члены, которые необходимо иметь при теоретических
исследованиях.
a) нахождения матрицы, обратной к данной (к матрице справа
приписывается единичная такого же размера, что и исходная: ,
после чего приводится
к виду единичной матрицы методом Гаусса–Жордана; в результате на месте
изначальной единичной матрицы справа оказывается обратная к исходной матрица: );
b) определения ранга матрицы (согласно следствию из теоремы Кронекера–Капелли
ранг матрицы равен числу её главных переменных);
c)
численного решения СЛАУ в вычислительной технике (ввиду
погрешности вычислений используется Метод Гаусса с выделением главного
элемента, суть которого заключена в том, чтобы на каждом шаге в качестве
главной переменной выбирать ту, при которой среди оставшихся после вычёркивания
очередных строк и столбцов стоит максимальный по модулю коэффициент).
Существуют
и другие методы решения и исследования систем линейных уравнений, которые
лишены отмеченных недостатков. Эти методы основаны на теории матриц и
определителей.
Список
источников
1.
Кремер Н.Ш., Путко Б.А. Высшая математика для
экономистов. - М.: Учеб. пособие, 1998.
2.
Курош А.Г. Курс высшей алгебры. - М.: Учеб. пособие, 1968.
3.
Справочник по математике для экономистов. Под ред. В.И. Ермакова //
Инфра-М, Москва – 2009.