Система линейных уравнений метод выбора главного элемента

Метод Жордана-Гаусса для решения СЛАУ

В данной статье мы рассмотрим метод Жордана-Гаусса для решения систем линейных уравнений, отличие метода Гаусса от метода Жордана-Гаусса, алгоритм действий, а также приведем примеры решений СЛАУ.

Основные понятия

Метод Жордана-Гаусса — один из методов, предназначенный для решения систем линейных алгебраических уравнений.

Этот метод является модификацией метода Гаусса — в отличие от исходного (метода Гаусса) метод Жордана-Гаусса позволяет решить СЛАУ в один этап (без использования прямого и обратного ходов).

Матричная запись СЛАУ: вместо обозначения А в методе Жордана-Гаусса для записи используют обозначение Ã — обозначение расширенной матрицы системы.

Решить СЛАУ методом Жордана-Гаусса:

4 x 1 — 7 x 2 + 8 x 3 = — 23 2 x 1 — 4 x 2 + 5 x 3 = — 13 — 3 x 1 + 11 x 2 + x 3 = 16

Записываем расширенную матрицу системы:

Ã = 4 — 7 8 | — 23 2 — 4 5 | — 13 — 3 11 1 | 16

Напоминаем, что слева от черты записывается матрица системы А :

A = 4 — 7 8 2 — 4 5 — 3 11 1

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

В этой статье мы покажем оба способа решения.

Произвольный способ выбора разрешающих элементов

Первый этап:

Следует обратиться к 1-му столбцу матрицы Ã — необходимо выбрать ненулевой (разрешающий) элемент.

В 1-ом столбце есть 3 ненулевых элемента: 4, 2, -3. Можно выбрать любой, но, по правилам, выбирается тот, чей модуль ближе всего к единице. В нашем примере таким числом является 2.

Цель: обнулить все элементы, кроме разрешающего, т.е. необходимо обнулить 4 и -3:

4 — 7 8 2 — 4 5 — 3 11 1

Произведем преобразование: необходимо сделать разрешающий элемент равным единице. Для этого делим все элементы 2-ой строки на 2. Такое преобразование имеет обозначение: I I : 2 :

4 — 7 8 | — 23 2 — 4 5 | — 13 — 3 11 1 | 16 I I ÷ 2 → 4 — 7 8 | — 23 2 — 4 5 / 2 | — 13 / 2 — 3 11 1 | 16

Теперь обнуляем остальные элементы: 4 и -3:

4 — 7 8 | — 23 2 — 4 5 / 2 | — 13 / 2 — 3 11 1 | 16 I — 4 × I I I I I — ( — 3 ) × I I

Необходимо выполнить преобразования:

I — 4 × I I и I I I — ( — 3 ) × I I = I I I + 3 × I I

Запись I — 4 × I I означает, что от элементов 1-ой строки вычитаются соответствующие элементы 2-ой строки, умноженные на 4.

Запись I I I + 3 × I I означает, что к элементам 3-ей строки прибавляются соответствующие элементы 2-ой строки, умноженные на 3.

I — 4 × I I = 4 — 7 8 — 23 — 4 1 — 2 5 / 2 — 13 / 2 = = 4 — 7 8 — 23 — 4 — 8 10 — 26 = 0 1 — 2 3

Записываются такие изменения следующим образом:

4 — 7 8 | — 23 2 — 4 5 / 2 | — 13 / 2 — 3 11 1 | 16 I — 4 × I I I I I — ( — 3 ) × I I → 0 1 — 2 | 3 1 — 2 5 / 2 | — 13 / 2 0 5 17 / 2 | — 7 / 2

Необходимо обнулить 2-ой столбец, следовательно, нужно выбрать разрешающий элемент: 1, -2, 5. Однако 2-ую строку матрицы мы использовали в первом этапе, так что элемент -2 не может быть использован.

Поскольку необходимо выбирать число, чей модуль ближе всего к единице, то выбор очевиден — это 1. Обнуляем остальные элементы 2-го столбца:

0 1 — 2 | 3 1 — 2 5 / 2 | — 13 / 2 0 5 17 / 2 | — 7 / 2 I I — ( — 2 ) × I I I I — 5 × I

0 1 — 2 | 3 1 — 2 5 / 2 | — 13 / 2 0 5 17 / 2 | — 7 / 2 I I + 2 × I I I I — 5 × I → 0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 37 / 2 | — 37 / 2

Теперь требуется обнулить элементы 3-го столбца. Поскольку первая и вторая строки уже использованы, поэтому остается только один вариант: 37 / 2 . Обнуляем с его помощью элементы третьего столбца:

0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 37 / 2 | — 37 / 2

I — ( — 2 ) × I I I = I + 2 × I I I и I I — ( — 3 2 ) × I I I = I I + 3 2 × I I

получим следующий результат:

0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 1 | — 1 I + 2 × I I I I I + 3 / 2 × I I I → 0 1 0 | 1 1 0 0 | — 2 0 0 1 | — 1

Ответ: x 1 = — 2 ; x 2 = 1 ; x 3 = — 1 .

4 — 7 8 | — 23 2 — 4 5 | — 13 — 3 11 1 | 16 I I ÷ 2 → 4 — 7 8 | — 23 2 — 4 5 / 2 | — 13 / 2 — 3 11 1 | 16 I — 4 × I I I I I — ( — 3 ) × I I →

→ 0 1 — 2 | 3 1 — 2 5 / 2 | — 13 / 2 0 5 17 / 2 | — 7 / 2 I I — ( — 2 ) × I I I I — 5 × I → 0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 37 / 2 | — 37 / 2 I I I ÷ 37 2 →

→ 0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 1 | — 1 I + 2 × I I I I I + 3 / 2 × I I I → 0 1 0 | 1 1 0 0 | — 2 0 0 1 | — 1 .

Выбор разрешающих элементов на главной диагонали матрицы системы

Принцип выбора разрешающих элементов строится на простом отборе соответствующих элементов: в 1-ом столбце выбирается элемент 1-го столбца, во 2-ом — второй, в 3-ем — третий и т.д.

Первый этап

В первом столбце необходимо выбрать элемент первой строки, т.е. 4. Но поскольку в первом столбце есть число 2, чей модуль ближе к единице, чем 4, то можно поменять местами первую и вторую строку:

4 — 7 8 | — 23 2 — 4 5 | — 13 — 3 11 1 | 16 → 2 — 4 5 | — 13 4 — 7 8 | — 23 — 3 11 1 | 16

Теперь разрешающий элемент — 2. Как показано в первом способе, делим первую строку на 2, а затем обнуляем все элементы:

4 — 7 8 | — 23 2 — 4 5 | — 13 — 3 11 1 | 16 I ÷ 2 → 2 — 4 5 / 2 | — 13 / 2 4 — 7 8 | — 23 — 3 11 1 | 16 I I — 4 × I I I I + 3 × I → 1 — 2 5 / 2 | — 13 / 2 0 1 — 2 | 3 0 5 17 / 2 | — 7 / 2

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

0 1 — 2 | 3 1 — 2 5 / 2 | — 13 / 2 0 5 17 / 2 | — 7 / 2 I + 2 × I I I I I — 5 × I I → 0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 37 / 2 | — 37 / 2

На третьем этапе необходимо обнулить элементы третьего столбца. Разрешающий элемент — 37/2. Делим все элементы на 37/2 (чтобы сделать равными 1), а затем обнуляем:

0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 37 / 2 | — 37 / 2 I I I ÷ 37 2 → 1 0 — 3 / 2 | — 1 / 2 0 1 — 2 | 3 0 0 1 | — 1 I + 2 × I I I I I + 3 / 2 × I I I → 1 0 0 | — 2 0 1 0 | 1 0 0 1 | — 1

Ответ: x 1 = — 2 ; x 2 = 1 ; x 3 = — 1 .

4 — 7 8 | — 23 2 — 4 5 | — 13 — 3 11 1 | 16 I ÷ 2 → 2 — 4 5 / 2 | — 13 / 2 4 — 7 8 | — 23 — 3 11 1 | 16 I I — 4 × I I I I + 3 × I → 0 1 — 2 | 3 1 — 2 5 / 2 | — 13 / 2 0 5 17 / 2 | — 7 / 2 I + 2 × I I I I I — 5 × I I →

→ 0 1 — 2 | 3 1 0 — 3 / 2 | — 1 / 2 0 0 37 / 2 | — 37 / 2 I I I ÷ 37 2 → 1 0 — 3 / 2 | — 1 / 2 0 1 — 2 | 3 0 0 1 | — 1 I + 2 × I I I I I + 3 / 2 × I I I → 1 0 0 | — 2 0 1 0 | 1 0 0 1 | — 1

Решить СЛАУ методом Жордана-Гаусса:

3 x 1 + x 2 + 2 x 3 + 5 x 4 = — 6 3 x 1 + x 2 + 2 x 4 = — 10 6 x 1 + 4 x 2 + 11 x 3 + 11 x 4 = — 27 — 3 x 1 — 2 x 2 — 2 x 3 — 10 x 4 = 1

Записать расширенную матрицу данной системы Ã :

3 1 2 5 | — 6 3 1 0 2 | 10 6 4 11 11 | — 27 — 3 — 2 — 2 — 10 | 1

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

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

3 1 2 5 | — 6 3 1 0 2 | — 10 6 4 11 11 | — 27 — 3 — 2 — 2 — 10 | 1 I ÷ 3 → 1 1 / 3 2 / 3 5 / 3 | — 2 3 1 0 2 | — 10 6 4 11 11 | — 27 — 3 — 2 — 2 — 10 | 1 I I — 3 × I I I I — 6 × I I V + 3 × I →

→ 1 1 / 3 2 / 3 5 / 3 | — 2 0 0 — 2 — 3 | — 4 0 2 7 1 | — 15 0 — 1 0 — 5 | — 5

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

Поскольку в четвертой строке есть число -1, то меняем местами вторую и четвертую строки:

1 1 / 3 2 / 3 5 / 3 | — 2 0 0 — 2 — 3 | — 4 0 2 7 1 | — 15 0 — 1 0 — 5 | — 5 → 1 1 / 3 2 / 3 5 / 3 | — 2 0 — 1 0 — 5 | — 5 0 2 7 1 | — 15 0 0 — 2 — 3 | — 4

Теперь разрешающий элемент равен -1. Делим элементы второго столбца на -1, а затем обнуляем:

1 1 / 3 2 / 3 5 / 3 | — 2 0 — 1 0 — 5 | — 5 0 2 7 1 | — 15 0 0 — 2 — 3 | — 4 I I ÷ ( — 1 ) → 1 1 / 3 2 / 3 5 / 3 | — 2 0 1 0 5 | 5 0 2 7 1 | — 15 0 0 — 2 — 3 | — 4 I — 1 / 3 × I I I I I — 2 × I →

→ 1 0 2 / 3 0 | — 11 / 3 0 1 0 5 | 5 0 0 7 — 9 | — 25 0 0 — 2 — 3 | — 4

На третьем этапе необходимо также обнулить элементы третьего столбца. Для этого находим разрешающий элемент в третьей строке — это 7. Но на 7 делить неудобно, поэтому необходимо менять строки местами, чтобы разрешающий элемент стал -2:

1 0 2 / 3 0 | — 11 / 3 0 1 0 5 | 5 0 0 7 — 9 | — 25 0 0 — 2 — 3 | — 4 → 1 0 2 / 3 0 | — 11 / 3 0 1 0 5 | 5 0 0 — 2 — 3 | — 4 0 0 7 — 9 | — 25

Теперь делим все элементы третьего столбца на -2 и обнуляем все элементы:

1 0 2 / 3 0 | — 11 / 3 0 1 0 5 | 5 0 0 — 2 — 3 | — 4 0 0 7 — 9 | — 25 I I I ÷ ( — 2 ) → 1 0 2 / 3 0 | — 11 / 3 0 1 0 5 | 5 0 0 1 3 / 2 | 2 0 0 0 — 9 | — 25 I — 2 / 3 × I I I I V — 7 × I I I →

1 0 0 — 1 | — 5 0 1 0 5 | 5 0 0 1 3 / 2 | 2 0 0 0 — 39 / 2 | — 39

Обнуляем четвертый столбец. Разрешающий элемент — — 39 2 :

1 0 0 — 1 | — 5 0 1 0 5 | 5 0 0 1 3 / 2 | 2 0 0 0 — 39 / 2 | — 39 I V ÷ ( — 39 2 ) → 1 0 0 — 1 | — 5 0 1 0 5 | 5 0 0 1 3 / 2 | 2 0 0 0 1 | 2 I + I V I I — 5 × I V I I I — 3 / 2 × I V →

→ 1 0 0 0 | — 3 0 1 0 0 | — 5 0 0 1 0 | — 1 0 0 0 1 | 2 .

Ответ: x 1 = — 3 ; x 2 = — 5 ; x 3 = — 1 ; x 4 = 2

Метод Гаусса с выбором главного элемента

Московский Государственный Технически Университет

«МАМИ»

Лабораторная работа №3 по курсу «Вычислительная Математика»

«РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ»

3. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Справочная информация

Численные методы решения систем линейных алгебраических уравнений

записываемых в матричной форме в виде

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

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

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

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

Один из простейших способов исключения состоит в следующем. Первое уравнение системы

которое на этом шаге считается ведущим, нормируется – делится на значение диагонального элемента a₁₁

Если в исходной системе a₁₁= 0, то в качестве первого уравнения следует взять любое другое с ненулевым первым коэффициентом, поменяв их местами. Полученное уравнение умножается на первый коэффициент второго уравнения a₂₁ и вычитается из него. В результате во втором уравнении пропадает слагаемое a₂₁x₁, содержащее первое неизвестное x₁. Такие же операции проводятся со всеми последующими уравнениями. В результате система уравнений принимает вид

Далее процесс повторяется. За ведущее берется второе уравнение и исключается неизвестное x₂ из всех уравнений, начиная с третьего

Таким образом, за n шагов система уравнений последовательно сводится к треугольному виду, при этом для последнего уравнения выполняется только операция нормирования:

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

Выполняя аналогичные подстановки найденных неизвестных в вышестоящие уравнения, удается определить все компоненты решения x_n_–2. x₂, x₁.

Метод Гаусса даёт точное решение, если все исходные данные точны и все вычисления производятся точно. На практике, при выполнении вычислений, неизбежно проводятся округления. Ошибка округлений вносит погрешность в решение метода Гаусса. Таким образом, при операциях с округленными десятичными числами метод Гаусса даёт не точное решение x_т системы линейных алгебраических уравнений, а некоторое приближённое решение , где

, .

Степень отличия приближённого решения от точного определяется длиной разрядной сетки ЭВМ: чем больше разрядов в ней учитывается, тем это отличие меньше.

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

или или

где двойные модульные скобки обозначают норму вектора.

Для определения величины погрешности полученного решения на практике используют следующий алгоритм вычисления её главной части. Сначала по имеющемуся решению пересчитывается вектор правых частей системы

а затем посредством повторного решения системы уравнений

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

или или ,

так и его относительная погрешность

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

Метод Гаусса с выбором главного элемента

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

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

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

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

а. Выбор главного элемента среди элементов первого столбца

б. Нормировка первого уравнения

в. Исключение элементов первого столбца

г. Выбор главного элемента среди элементов второго столбца второго и третьего уравнений

д. Нормировка второго уравнения

е. Исключение элементов второго столбца

ё. Нормировка последнего уравнения

В итоге получено решение системы уравнений

3. Погрешность найденного решения.

а. Пересчёт вектора правых частей системы

б. Формирование системы уравнений, определяющей погрешности решения

в. Решение системы относительно погрешностей оно выполняется аналогично пунктам 1 и 2. Прямой ход (пункт 1) даёт следующую систему с верхней треугольной матрицей

а обратный ход позволяет получить решение

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

Реализация описанного метода без нахождения погрешности решения в рамках программы Excel приведена на рис.1.

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

Каждый из рассмотренных методов имеет свои достоинства и недостатки. В частности, метод Гаусса позволяет получить решение за конечное число шагов. Для этого требуется выполнить n(n 2 + 3n – 1)/3 операций умножения и деления и n(n – 1)(2n + 5)/6 операций сложения и вычитания, количество которых при больших порядках системы (n > 100) можно принять равным n 3 /3 в обоих случаях. Однако его методические ошибки, связанные с размером разрядной сетки вычислений, резко нарастают с увеличением порядка системы и не позволяют применять его для систем высоких порядков без использования специальных приёмов.

Итерационные методы позволяют получать решение систем бóльшего порядка. Для выполнения каждой итерации с их помощью необходимо выполнить n(n + 1) операций умножения и деления и столько же операций сложения и вычитания. При больших порядках системы уравнений (n > 100) их количество можно принять равным n 2 . Из сравнения трудоёмкости итерационных методов и метода Гаусса следует оценка, которой можно руководствоваться при окончательном выборе метода решения системы при необходимости его многократного нахождения. Если количество итераций, требуемое для получения решения системы итерационными методами, не превышает n/3, то выгоднее применять их, а не методы типа Гаусса. Однако здесь следует помнить, что итерационные методы требуют, чтобы матрица системы обладала определёнными свойствами, обеспечивающими их сходимость. Необходимо также отметить, что выполнение этих требований часто не гарантирует высокой скорости их сходимости.

Метод Гаусса онлайн

Данный онлайн калькулятор находит решение системы линейных уравнений (СЛУ) методом Гаусса. Дается подробное решение. Для вычисления выбирайте количество переменных и количество уравнений. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить.»

Предупреждение

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Метод Гаусса

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

Эквивалентными преобразованиями системы линейных уравнений являются:

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

Рассмотрим систему линейных уравнений:

(1)

Запишем систему (1) в матричном виде:

Ax=b

(2)

(3)

A-называется матрица коэффициентов системы, b − правая часть ограничений, x− вектор переменных, которую нужно найти. Пусть rang(A)=p.

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

Построим расшренную матрицу системы:

(4)

Предположим a₁₁≠0. Если это не так, то можно поменять местами эту строку со строкой с ненулевым элементом в столбце 1 (если нет таких строк, то переходим к следующему столбцу). Обнуляем все элементы столбца 1 ниже ведущего элемента a₁₁. Для этого сложим строки 2,3, . m со строкой 1, умноженной на −a₂₁/a₁₁, −a₃₁/a₁₁, . −a_m1/a₁₁, соответственно. Тогда (4) примет следующий вид:

(5)

На следующем этапе обнуляем все элементы столбца 2, ниже элемента . Если данный элемент нулевой, то эту строку меняем местами со строкой, лежащий ниже данной строки и имеющий ненулевой элемент во втором столбце. Далее обнуляем все элементы столбца 2 ниже ведущего элемента a₂₂. Для этого сложим строки 3, . m со строкой 2, умноженной на −a₃₂/a₂₂, . −a_m2/a₂₂, соответственно. Продолжая процедуру, получим матрицу диагонального или ступенчатого вида. Пусть полученная расширенная матрица имеет вид:

(6)

Обратим внимание на последние строки. Если . равны нулю, то система линейных уравнений имеет решение, если же хотя бы один из этих чисел отлично от нуля, то система несовместна. Иными словами, система (2) совместна тогда и только тогда, когда ранг матрицы A навен рангу расширенной матрицы (A|b).

Пусть . Тогда

(7)

Так как rangA=rang(A|b), то множество решений (7) есть (n−p)− многообразие. Следовательно n−p неизвестных можно выбрать произвольно. Остальные неизвестные из системы (7) вычисляются так. Из последнего уравнения выражаем x_p через остальные переменные и вставляем в предыдущие выражения. Далее из предпоследнего уравнения выражаем x_p−1 через остальные переменные и вставляем в предыдущие выражения и т.д. Рассмотрим метод Гаусса на конкретных примерах.