Алгоритм Гауса или исключение неизвестных

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

1 шаг: просматриваем 1 столбец, находим в нем ненулевой элемент, если он не а₁₁, то мы переставляем строки и будем считать, что а₁₁ не равен 0, умножаем эту строку на обратный элемент а₁₁ –го.

2 шаг: умножаем 1 строку на (-1).

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

Предупреждение: после первого шага 1-ую строку уже нельзя использовать, иначе у нас испортится столбец, теперь используем матрицу, на 1 столбец и на 1 строку и возвращаемся к первому шагу.

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

Если в последней ненулевой строчке получится запись 0а_m, где а_m – элемент столбца, свободный член, то тогда получится, что система несовместная.

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

Если итоговая матрица имеет n столбцов, не считая столбца свободных членов и m строк (m<n), то у нас будет (m-n) свободных переменных.

Если же у нас получится, что m=n, то матрица примет нормальный треугольный вид, система имеет 1 решение.

СЛУ может иметь 0 решений, 1 решение (Крамерная система) и, если есть свободные переменные, то ∞решений.

Замечание: Введенные элементарные преобразования (1и2) переводят систему в эквивалентную, т.е. не изменяют множество решений.

Запишем систему по строкам:

Через обозначим СЛУ, получившуюся из первоначальной применением 1-го ЭП.

Пусть и мы умножим i-ую строку. Все общее с системой х (не пишем)

aa₁x=ab_i ……..

нужно доказать, что , т.е. если , - являются решениями первой системы, то они являются решениями и второй.

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

Пусть , … - это решения системы , нужно проверить, что оно является и решением х, т.к. переход от это опять 1-ое ЭП, только (x) единица на .