Метод Гаусса

Рассмотрим неоднородную систему линейных уравнений с прямоугольной матрицей :

, (4.5.1)

где матрица , столбцы , .

Теорема 4.5.1.Любая совместная система линейных уравнений посредством элементарных преобразований и, возможно, изменения нумерации неизвестных приводится к системе с трапециевидной матрицей.

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

,

, .

Умножая каждое i-ое уравнение () на число , и, затем вычитая из s-го уравнения (), получаем систему

,

, .

Так как , то для любого числа , ибо в противном случае система окажется несовместной. Тогда, очевидно, что система (4.5.1) равносильна системе

. (4.5.2)

Рассмотрим теперь систему (4.5.2). Пусть коэффициент (если , то перестановкой местами уравнений всегда можно добиться выполнения условия ).

Умножая первое уравнение системы на число , получаем

Вычтем из каждого уравнения, начиная со второго, первое уравнение, предварительно умноженное соответственно на , получаем

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

Умножая второе уравнение на величину , получаем

Вычитая второе уравнение, предварительно умноженное , из i-го уравнения (), а, затем повторяя описанную процедуру, получаем систему

Если , то переменные называются свободными, им можно придавать произвольные значения, а потом через них выразить .

Когда справедливо равенство , то в силу совместности системы (4.5.1) система (4.5.2) имеет единственное решение.

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

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