2015-05-05
482
[убрать]
- 1 История
- 2 Описание метода
- 2.1 Условие совместности
- 2.2 Алгоритм
- 2.2.1 Описание
- 2.2.2 Простейший случай
- 2.3 Пример
- 3 Применение и модификации
- 4 Достоинства метода
- 5 Неоптимальность метода Гаусса
- 6 См. также
- 7 Примечания
- 8 Литература
История[править | править исходный текст]
Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах», составленном между I в. до н.э. и II в. н. э.
Описание метода[править | править исходный текст]
Пусть исходная система выглядит следующим образом
Матрица 
называется основной матрицей системы, 
— столбцом свободных членов.
Тогда, согласно свойству элементарных преобразований над строками, основную матрицу этой системы можно привести к ступенчатому виду (эти же преобразования нужно применять к столбцу свободных членов):
При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных 
[3].
|
|
|
Тогда переменные называются главными переменными. Все остальные называются свободными.
Если хотя бы одно число 
, где 
, то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.
Пусть 
для любых .
Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом 
(
, где 
— номер строки):
,
где 
Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.
| Следствия: 1: Если в совместной системе все переменные главные, то такая система является определённой. 2: Если количество переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной. |
Условие совместности[править | править исходный текст]
Упомянутое выше условие для всех 
может быть сформулировано в качестве необходимого и достаточного условия совместности:
Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).
|
| Теорема Кронекера — Капелли. Система совместна тогда и только тогда, когда ранг её основной матрицы равен рангу её расширенной матрицы.
Следствия:
|
Алгоритм[править | править исходный текст]
|
|
|
Блок схема представлена на рисунке. Данный рисунок адаптированный для написания программы на языке С++, где a[0] столбец свободных членов.
Алгоритм Гаусса для решения САУ
Описание[править | править исходный текст]
Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.
- На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.
- На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.
Метод Гаусса требует 
арифметических операций.
Этот метод опирается на:
|
| Теорема (о приведении матриц к ступенчатому виду). Любую матрицу путём элементарных преобразований только над строками можно привести к ступенчатому виду. |
Простейший случай[править | править исходный текст]
В простейшем случае алгоритм выглядит так:
- Прямой ход:
- Обратный ход. Из последнего ненулевого уравнения выражаем базисную переменную через небазисные и подставляем в предыдущие уравнения. Повторяя эту процедуру для всех базисных переменных, получаем фундаментальное решение.
Пример
Покажем, как методом Гаусса можно решить следующую систему:
Обнулим коэффициенты при во второй и третьей строчках. Для этого вычтем из них первую строчку, умноженную на 
и 
, соответственно:
Теперь обнулим коэффициент при 
в третьей строке, вычтя из неё вторую строку, умноженную на 
:
В результате мы привели исходную систему к треугольному виду, тем самым закончим первый этап алгоритма.
На втором этапе разрешим полученные уравнения в обратном порядке. Имеем:
из третьего;
из второго, подставив полученное 
из первого, подставив полученные и .
Таким образом исходная система решена.
В случае, если число уравнений в совместной системе получилось меньше числа неизвестных, то тогда ответ будет записываться в виде фундаментальной системы решений.
