Решение системы линейных уравнений методом жордана гаусса. Метод Гаусса-Жордана. Как найти обратную матрицу с помощью элементарных преобразований

Уравнение имеет решение: если хотя бы один из коэффициентов при неизвестных отличен от нуля. В этом случае любой -мерный вектор называется решением уравнения, если при подстановке его координат уравнение обращается в тождество.

Общая характеристика разрешенной системы уравнений

Дать характеристику системе уравнений .

Решение :

1. Входит ли в состав противоречивое уравнение? (Если коэффициенты, в этом случае уравнение имеет вид: и называется противоречивым .)

• Если система содержит противоречивое, то такая система несовместна и не имеет решения

2. Найти все разрешенные переменные . (Неизвестная называется разрешенной для системы уравнений, если она входит в одно из уравнений системы с коэффициентом +1, а в остальные уравнения не входит (т.е. входит с коэффициентом, равным нулю).

3. Является ли система уравнений разрешенной? (Система уравнений называется разрешенной , если каждое уравнение системы содержит разрешенную неизвестную, среди которых нет совпадающих)

Разрешенные неизвестные, взятые по одному из каждого уравнения системы, образуют полный набор разрешенных неизвестных системы. (в нашем примере это )

Разрешенные неизвестные, входящие в полный набор, называют также базисными (), а не входящие в набор — свободными ().

На данном этапе главное понять что такое разрешенная неизвестная (входящая в базис и свободная).

Общее Частное Базисное решения

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

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

Базисным решением называется частное решение, получающееся из общего при нулевых значениях свободных переменных.

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

Теорема (1)

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

Решение :

1. Проверяем является ли система разрешенной?

• Система является разрешенной (т.к. каждое из уравнений содержит в себе разрешенную неизвестную)

2. Включаем в набор разрешенные неизвестные — по одному из каждого уравнения .

3. Записываем общее решение в зависимости от того какие разрешенные неизвестные мы включили в набор .

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

Ответ: частное решение (один из вариантов)

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

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

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

Теорема (2)

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

Теорема (3)

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

Следствие из Теорем (2 и 3)

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

Формулы пересчета коэффициентов системы

Если у нас есть система уравнений и мы хотим преобразовать ее в разрешенную систему уравнений в этом нам поможет метод Жордана-Гаусса.

Преобразование Жордана с разрешающим элементом позволяет получить для системы уравнений разрешенную неизвестную в уравнении с номером . (пример 2).

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

При делении уравнения с номером на , его коэффициенты пересчитываются по формулам:

Чтобы исключить из уравнения с номером , нужно уравнение с номером умножить на и прибавить к этому уравнению.

Теорема (4) О сокращении числа уравнений системы.

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

Теорема (5) О несовместимости системы уравнений.

Если система уравнений содержит противоречивое уравнение, то она несовместна.

Алгоритм метода Жордана-Гаусса

Алгоритм решения систем уравнений методом Жордана-Гаусса состоит из ряда однотипных шагов, на каждом из которых производятся действия в следующем порядке:

1. Проверяется, не является ли система несовместной. Если система содержит противоречивое уравнение, то она несовместна.
2. Проверяется возможность сокращения числа уравнений. Если в системе содержится тривиальное уравнение, его вычеркивают.
3. Если система уравнений является разрешенной, то записывают общее решение системы и если необходимо — частные решения.
4. Если система не является разрешенной, то в уравнении, не содержащем разрешенной неизвестной, выбирают разрешающий элемент и производят преобразование Жордана с этим элементом.
5. Далее заново переходят к пункту 1

Найти : два общих и два соответствующих базисных решения

Решение :

Вычисления приведены в нижеследующей таблице:

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

В первых трех строках таблицы помещены коэффициенты при неизвестных и правые части исходной системы. Результаты первого преобразования Жордана с разрешающим элементом равным единице приведены в строках 4, 5, 6. Результаты второго преобразования Жордана с разрешающим элементом равным (-1) приведены в строках 7, 8, 9. Так как третье уравнение является тривиальным, то его можно не учитывать.

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

Yandex.RTB R-A-339285-1

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

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

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

Примечание

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

Пример 1

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-му столбцу матрицы Ã - необходимо выбрать ненулевой (разрешающий) элемент.

В 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

Пример 2

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

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

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

Каждой системе линейных уравнений поставим в соответствие расширенную матрицу , полученную присоединением к матрице А столбца свободных членов:

Метод Жордана–Гаусса применяется для решения системы m линейных уравнений с n неизвестными вида:

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

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

1. перестановка двух строк ;

2. умножение строки на любое число, отличное от нуля ;

3. прибавление к одной строке другой строки, умноженной на некоторое число ;

4. отбрасывание нулевой строки (столбца) .

Пример 2.11. Решить методом Жордана–Гаусса системы линейных уравнений:

а ) Х 1 + Х 2 + 2Х 3 = -1

2Х 1 - Х 2 + 2Х 3 = -4

4Х 1 + Х 2 + 4Х 3 = -2

Решение: Составим расширенную матрицу:

Итерация 1

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

На этом первая итерация закончена.

Итерация 2

Выбираем направляющий элемент . Так как , то делим вторую строку на -3. Затем умножаем вторую строку соответственно на (-1) и на 3 и складываем соответственно с первой и третьей строками. Получим матрицу

Итерация 3

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

откуда Х 1 = 1, Х 2 = 2, Х 3 = -2.

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

б ) Х 1 – Х 2 + Х 3 – Х 4 = 4

Х 1 + Х 2 + 2Х 3 +3Х 4 = 8

2Х 1 +4Х 2 + 5Х 3 +10Х 4 = 20

2Х 1 – 4Х 2 + Х 3 – 6Х 4 = 4

Решение: Расширенная матрица имеет вид:

Применяя элементарные преобразования, получим:

Исходная система эквивалентна следующей системе уравнений:

Х 1 – 3Х 2 – 5Х 4 = 0

2Х 2 + Х 3 + 4Х 4 = 4

Последние две строки матрицы A (2) являются линейно зависимыми.

Определение. Строки матрицы e 1 , e 2 ,…, e m называются линейно зависимыми , если существуют такие числа , не равные одновременно нулю, что линейная комбинация строк матрицы равна нулевой строке:

где 0 =(0, 0…0). Строки матрицы являются линейно независимыми , когда комбинация этих строк равна нулю тогда и только тогда, когда все коэффициенты равны нулю.

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

Теорема 2.3 (о ранге матрицы). Ранг матрицы равен максимальному числу её линейно независимых строк или столбцов, через которые линейно выражаются все остальные её строки (столбцы).

Ранг матрицы A (2) равен 2, т.к. в ней максимальное число линейно независимых строк равно 2 (это первые две строки матрицы).

Теорема 2.4 (Кронекера–Капели). Система линейных уравнений совместна и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы этой системы.

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

2. Если ранг матрицы системы меньше числа переменных, т.е. r < n, то система неопределённая и имеет бесконечное множество решений.

В данном случае система имеет 4 переменных, а её ранг равен 2, следовательно, она имеет бесконечное множество решений.

Определение. Пусть r < n , r переменных x 1 , x 2 ,…, x r называются базисными , если определитель матрицы из коэффициентов при них (базисный минор ) отличен от нуля. Остальные n – r переменных называются свободными .

Определение. Решение системы, в котором все n – r свободных переменных равны нулю, называется базисным .

Совместная система m линейных уравнений с n переменными (m < n ) имеет бесконечное множество решений, среди которых базисных решений конечное число, не превосходящее , где .

В нашем случае , т.е. система имеет не более 6 базисных решений.

Общее решение имеет вид:

Х 1 = 3Х 2 +5Х 4

Х 3 = 4 – 2Х 2 – 4Х 4

Найдем базисные решения. Для этого полагаем Х 2 = 0, Х 4 = 0, тогда Х 1 =0, Х 3 = 4. Базисное решение имеет вид: (0, 0, 4, 0).

Получим другое базисное решение. Для этого в качестве свободных неизвестных примем Х 3 и Х 4 . Выразим неизвестные Х 1 и Х 2 через неизвестные Х 3 и Х 4:

Х 1 = 6 – 3/2Х 2 – Х 4

Х 2 = 2 – 1/2Х 3 – 2Х 4 .

Тогда базисное решение имеет вид: (6, 2, 0, 0).

Пример 2.12. Решить систему:

X 1 + 2X 2 – X 3 = 7

2X 1 – 3X 2 + X 3 = 3

4X 1 + X 2 – X 3 = 16

Решение.Преобразуем расширенную матрицу системы

Итак, уравнение, соответствующее третьей строке последней матрицы, противоречиво – оно привелось к неверному равенству 0 = –1, следовательно, данная система несовместна. Данный вывод можно также получить, если заметить, что ранг матрицы системы равен 2, тогда как ранг расширенной матрицы системы равен 3.

Записывается в виде расширенной матрицы, т.е. в столбец свободных членов помещается в одну матрицу с коэффициентами неизвестных. Аалгоритм заключается в приведении исходной матрицы, характеризующей систему линейных уравнений, к единичной путем эквивалентных преобразований (домножения строки матрицы на константу и сложения с другой строкой матрицы). В качестве константы используется 1/a[i][i] , т.е. число, обратное по отношению к элементу диагонали. Естественно, в ряде случаев возникают проблемы, связанные с делением на ноль, которые решаются перестановкой строк и столбцов:

Весь алгоритм можно представить 10 пунктами:

В качестве опорной выбираем первую строку матрицы.

Если элемент опорной строки, индекс которого равен номеру опорной строки, равен нулю, то меняем всю опорную строку на первую попавшуюся строку снизу, в столбце которого нет нуля.

Все элементы опорной строки делим на первый слева ненулевой элемент этой строки.

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

В качестве опорной строки выбираем следующую строку.

Повторяем действия 2 – 5 пока номер опорной строки не превысит число строк.

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

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

В качестве опорной строки выбираем строку выше.

Повторяем 8 – 9 пока номер опорной строки не станет меньше номера первой строки.

Пример расчета 1

Пусть имеется система уравнений:

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

и выполним элементарные преобразования ее строк.

Для этого умножим первую строку на 1 и вычитаем из второй строки; затем умножим первую строку на 2 и вычтем из третьей строки.

В результате мы исключим переменную x 1 из всех уравнений, кроме первого. Получим:

Теперь вычтем из строки 3 строку 2, умноженную на 3:

Теперь вычитаем из 1 строки сначала 3 строку, а затем 2 строку:

После преобразований получаем систему уравнений:

Из этого следует, что система уравнений имеет следующее решение:

x1 = 1, x2 = 3 , x3 = -1

Пример расчета 2

В качестве примера решим систему уравнений, представленную в виде матрицы (Таблица 1), методом Гаусса – Жордана.

Делим первую строку на 3 (элемент первой строки, расположенный на главной диагонали), получим:

Умножаем первую строку на 1 и вычитаем из второй строки. Умножаем первую строку на 6 и вычитаем из третьей строки. Получим:

В первом столбце все элементы кроме диагонального равны нулю, займемся вторым столбцом, для этого выберем вторую строку в качестве опорной. Вторая Делим ее на 17/3:

Умножаем строку 2 на -6 и вычитаем из третьей строки:

Теперь третья строка – опорная, делим ее на -33/17:

Умножаем опорную строку на 3/17 и вычитаем ее из второй. Умножаем третью строку на 1 и вычитаем ее из первой

Получена треугольная матрица, начинается обратный ход алгоритма (во время которого получим единичную матрицу). Вторая строка становится опорной. Умножаем третью строку на 4/3 и вычитаем ее из первой:

Последний столбец матрицы – решение системы уравнений.

Березнёва Т. Д.

Тема 7

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

МЕТОД ГАУССА – ЖОРДАНА.»

(Учебная дисциплина “Введение в линейную алгебру и аналитическую геометрию”)

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

МЕТОД ГАУССА – ЖОРДАНА.

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

Уравнение с n переменными называется линейным , если все переменные (x 1 , x 2 , … x n ) входят в него в степени 1. Общий вид такого уравнения формально записывается следующим образом:

a 1 x 1 + a 2 x 2 + … a j x j + … a n x n = b , (*)

= b .

Величины a j , j = 1,…, n , и b являются известными (заданными). Величиныa j называются коэффициентами при переменных (при неизвестных), а b - свободным членом .

Решением линейного уравнения (*) ,,…,) значений переменных, который при подстановке в уравнение (т.е. при заменеx j на при всехj от 1до n обращает его в тождество. Подчеркнем, что решение уравнения с n переменными всегда есть набор из n чисел и каждый такой набор из n чисел представляет собой одно решение. Очевидно, что если хотя бы один коэффициент при переменных не равен 0, то уравнение (*) имеет решение. В противном случае решение существует только при b = 0, и это все произвольные наборы из n чисел.

Рассмотрим одновременно m уравнений вида (*), т.е. систему m линейных алгебраических уравнений с n переменными . Пусть каждое i - е уравнение, i = 1,2,…,m, задается коэффициентами при переменных a i 1 , a i 2 , …, a in и свободным членом b i , т.е. имеет вид

a i1 x 1 + a i2 x 2 + … + a ij x j + … + a in x n = b i .

Тогда в общем виде система m линейных алгебраических уравнений с n переменными может быть записана в виде:

a 11 x 1 + a 12 x 2 + … + a 1j x j + … + a 1n x n = b 1

a 21 x 1 + a 22 x 2 + … + a 2j x j + … + a 2n x n = b 2

………………………………………………………………………………

a i1 x 1 + a i2 x 2 + … + a ij x j + … + a in x n = b i (1)

…………………………………………………

a m1 x 1 + a m2 x 2 + … + a mj x j + … + a mn x n = b m

или, что то же самое,

= b i , i = 1,…, m .

Если все свободные члены равны нулю, то система (1) называется однородной , т.е. имеет вид

= 0, i = 1,…, m, (1 0 )

в противном случае - неоднородной . Система (1 0 ) является частным случает общей системы (1) .

Решением системы уравнений (1) называется упорядоченный набор (,,…,) значений пере­менных, который при подстановке в урав­нения системы (1) (т.е. при заменеx j на , j = 1,…,n) все эти уравнения обращает в тождества, т.е.
=b i при всех i = 1,…,m.

Система уравнений (1) называется совместной, если у нее существует хотя бы одно решение. В противном случае система называется несовместной .

Совокупность всех решений системы уравнений (1) мы будем называть множеством ее решений и обозначать X b (X 0 , если система однородная). Если система несовместна, то X b = .

Основная задача теории систем линейных алгебраических уравнений состоит в том, чтобы выяснить, совместна ли система (1), и, если совместна, то описать множество всех её решений. Существуют методы анализа таких систем, которые позволяют описывать множество всех решений в случае совместных систем или убеждаться в несовместности в противном случае. Одним из таких универсальных методов является метод последовательного полного исключения неизвестных, или метод Гаусса - Жордана , который мы будем подробно изучать.

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

Две системы уравнений называются эквивалентными , если они имеют одно и то же множество решений. Другими словами, каждое решение одной системы является решением другой, и наоборот. Все несовместные системы считаются эквивалентными между собой.

Из определений эквивалентности и множества решений систем вида (1) сразу же вытекает справедливость следующих утверждений, которые мы сформулируем в виде теоремы.

Теорема 1. Если в системе (1) имеется уравнение с номером k , 1k m , такое, что a kj = 0 j , то

Справедливость утверждений теоремы становится очевидной, если заметить, что k – е уравнение имеет вид

0 x 1 + 0 x 2 + … + 0 x j + … + 0 x n = b k .

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

Доказательство. Умножим, например, второе уравнение системы (1) на некоторое число и прибавим его к первому уравнению. В результате этого преобразования получим систему (1’), в которой все уравнения, начиная со второго, не изменились, а первое имеет следующий вид

= b 1 + b 2 .

Очевидно, если какой-нибудь набор (,,…,) значений переменных обращает в тождества все уравнения системы (1), то он обращает в тождества и все уравнения системы (1’). Наоборот, решение (x’ 1 ,x’ 2 ,…,x’ j , … ,x’ n) системы (1’) является также решением системы (1), так как система (1) получается из системы (1’) с помощью аналогичного преобразования, когда к первому уравнению системы (1’) прибавляется второе уравнение системы (1’), умноженное на число (-).

Точно также доказывается и следующее утверждение.

Теорема 2’ . Умножение произвольного уравнения системы (1) на любое число, отличное от нуля, переводит систему (1) в эквивалентную ей систему уравнений .

Теоремы 2 и 2’ дают два вида преобразований, которым подвергалась система (1), оставаясь эквивалентной:

а) умножение (или деление) произвольного уравнения системы (1) на любое число, отличное от нуля;

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

Такие преобразования а) и б) называются элементарными преобразованиями системы уравнений (1).

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

Систему уравнений (1) можно записать в табличной форме:

Прямоугольная таблица чисел, составленная из коэффициентов a ij при неизвестных системы (1), называется матрицей системы (1) и обозначается A (в ней m строк и n столбцов), столбец свободных членов обозначается b. Прямоугольная таблица, составленная из коэффициентов a ij при неизвестных и из столбца свободных членов b системы (1), называется расширенной матрицей системы (1) и обозначается (в нейm строк и (n+1) столбцов), т.е = (A, b). В i – ой строке матрицы содержатся всеизвестные параметры, характеризующие i - ое уравнение системы (1), i = 1,…, m. В j – м столбце матрицы A содержатся все коэффициенты при неизвестном x j , встречающиеся в системе (1).

Числа a ij называются элементами матрицы А. Элемент a ij находится в i - ой строкеи в j - м столбце матрицы А. Принято говорить, что элементa ij находится на пересечении i - ой строки и j - го столбца матрицы А. Если все элементы строки (столбца) матрицы А (кроме одного) равны нулю, а ненулевой элемент равен единице, то такая строка (столбец) называется единичной (единич­ным).

Элементарным преобразованиям системы (1) соответствуют следующие элементарные преобразования таблицы (2):

а) умножение (или деление) всех элементов произвольной строки таблицы (2) на любое число, отличное от нуля ,

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

В результате любого элементарного преобразования получается новая таблица , в которой вместо той строки, к которой прибавляли (или умножали на любое число, отличное от нуля), пишется новая строка , а осталь­ные строки (в том числе и та, которую прибавляли) пишутся без из­менения . Новая таблица соответствует системе уравнений, эквивалентной исходной системе .

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

Метод последовательного полного исключения неизвестных

(Метод Гаусса - Жордана)

Метод последовательного полного исключения неизвестных, или метод Гаусса – Жордана , является универсальным методом анализа любых (заранее неизвестно, каких - совместных или несовместных) систем линейных алгебраических уравнений. Он позволяет решать совместные системы или убеждаться в несовместности несовместных систем.

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

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

Пусть задана конкретная система линейных алгебраических уравнений (1). Это значит, что известны n , m , a ij , b i , i = 1,…, m ; j = 1,…, n . Опишем предлагаемый метод решения этой системы.

Начальный этап включает в себя построение таблицы I (0) вида (2) и выбор в ней ведущего элемента – любого ненулевого коэффициента при переменных из таблицы (2). Столбец и строка, на пересечении которых стоит ведущий элемент, называются ведущими . (Пусть выбран элемент a i 0 j 0 . Тогда i 0 – ая строка ведущая, j 0 - й столбец ведущий.) Переходим к основному этапу. Заметим, что часто ведущий элемент называют разрешающим .

Основной этап состоит из повторяющихся однотипных итераций с номерами k = 1, 2,…. Опишем подробно итерации метода Гаусса - Жордана.

К началу каждой итерации известна некоторая таблица I вида (2), в ней выбран ведущий (разрешающий) элемент и, соответственно, ведущий столбец и ведущая строка. Кроме того, имеется информация о том, какие строки и столбцы уже были ведущими. (Так, например, после начального этапа, т.е. на итерации 1 известны I (0) , ведущий (разрешающий) элемент a i 0 j 0 и i 0 – ая строка ведущая, j 0 - ой столбец ведущий.)

Итерация(с номером k ) состоит из следующих действий.

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

Выписы­вается новая таблица I (k) , (k - номер итерации), в которой все столбцы, которые были когда-либо ведущими, – единичные .

Проверяется, можно ли в таблице I (k) выбрать новый ведущий (разрешающий) элемент . По определению это любой ненулевой элемент, который стоит на пересечении строки и столбца, которые еще не были ведущими .

Если такой выбор возможен, то столбец и строка, на пересечении которых стоит ведущий (разрешающий) элемент, называются ведущими . Затем итерация повторяется с новой таблицей I (k) , т.е. действия 1 – 3 повторяются с новой таблицей I (k) . При этом строится новая таблица I (k +1) .

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

Заключительный этап. Пусть проделано r итераций, получена таблица I (r) , состоящая из матрицы коэффициентов при переменных A (r) и столбца свободных членов b (r) , и в ней нельзя выбрать новый ведущий элемент, т.е. метод остановился . Заметим, что метод обязательн о остановится за конечное число шагов , т.к. r не может быть больше min{m,n}.

Каковы варианты остановки метода? Что значит «нельзя выбрать новый ведущий элемент»? Это значит, что после r – ой итерации в матрице A (r) новой системы, эквивалентной системе (1), либо

а) все строки A (r) были ведущими, т.е. в каждой строке стоит одна и ровно одна единица, которая не стоит больше не в какой другой строке,

б) остались строки в A (r) , состоящие только из нулей.

Рассмотрим эти варианты.

а) В этом случае r = m, m n. Переставив строки и перенумеровав переменные (т.е. переставив столбцы), можно таблицу I (r) представить в виде

Подчеркнем, что в таблице (3) каждая переменная с номером i, не превосходящим r, встречается только в одной строке. Таблица (3) соответствует системе линейных уравнений вида

x 1 +
=b (r) 1 ,

x 2 +
=b (r) 2 ,

………………………, (4)

x r +
=b (r) r ,

в которой каждая переменная с номером i, не превосходящим r , однозначно выражается через переменные x r +1 , … ,x n , коэффициенты матрицы a (r) ij , j = r+1,…,n, и свободный член b (r) i , представленные в таблице (3). На переменные x r +1 , … , x n не накладываются никакие ограничения , т.е. они могут принимать любые значения . Отсюда произвольное решение системы, описываемой таблицей (3), или, что то же самое, произвольное решение системы (4), или, что то же самое, произвольное решение системы (1) имеет вид

x i = b (r) i - a (r) ij x j , i = 1,…,r = m; x j – любое при j = (r+1),…,n. (5)

Тогда множество решений системы (1) можно записать как

X b = {x=(x 1 , … ,x n) : x i = b (r) i - a (r) ij x j при i = 1,…, r = m; x j – любое при j =(r+1),…,n.}.

б) В этом случае r < m, и существует хотя бы одна строка k, k > r, (предполагаем, что сделана перестановка строк и столбцов такая же, как в пункте а)) такая, что a (r) kj = 0 при всех j. Тогда, если соответствующий свободный член b (r) k не равен 0, то k - е уравнение не имеет решения, и, следовательно, вся система не имеет решения, т.е. система (1) несовместна .

Если же соответствующий b (r) k равен 0, то k - ое уравнение является лишним и его можно отбросить. Отбросив все такие уравнения, получим, что система (1) эквивалентна системе изr уравнений с n переменными, которая через r шагов записывается с помощью таблицы вида (3), в которой все строки были ведущими. Таким образом, мы пришли к рассмотренному выше случаю а) и можем выписать решение вида (5).

Метод Гаусса – Жордана описан полностью. За конечное число итераций система линейных алгебраических уравнений будет решена (если она совместна) или будет очевидно, что она несовместна (если она действительно несовместна).

Переменные, соответствующие ведущим (разрешающим) элементам , или стоящие в ведущих столбцах, принято называть базисными , а ос­тальные переменные -свобод­ными .

Обратим внимание на следующее.

1) Когдамы начинаем решать систему методом Гаусса - Жордана, мы можем не знать, совместна эта система или нет. Метод Гаусса - Жордана за конечное число итераций r даст ответ на этот вопрос. В случае совместной системы на основании последней таблицы выписывается общее решение исход­ной системы. В этом случае число базисных переменных обязательно равно номеру r последней итерации, т.е. числу выполненных итераций. Число r всегда не превосходит min{m,n},гдеm - число уравнений системы,а n - число переменных системы. Если r < n, то ( n – r) равно числу свободных переменных.

2) При записи общего решения не нужно перенумеровывать переменные, как это делалось для простоты понимания при описании Заключительного этапа. Это сделано для более ясного понимания.

3) При решении системы (1) методом Гаусса - Жордана базисными переменными будут только переменные, соответствующие столбцам, которые на каких-то итерациях выступали в роли ведущих , и наоборот, если на какой-то итерации столбец выступал в качестве ведущего, соответствующая ему переменная обязательно будет в числе базисных.

4) Если общее решение системы (1) содержит хотя бы одну свободную переменную, то эта система имеет бесконечно много част­ных решений, если же свободных переменных нет, то система имеет единственное решение, которое совпадает с общим решением.

5) Ведущие элементы могут быть выбраны на каждой итерации различным способом. Важно только то, что это ненулевые коэффициенты, стоящие на пересечении строки и столбца, которые до этого не были ведущими. Различный выбор ведущих элементов может дать различные записи множества решений. Однако, само множество решений при любой записи одно и то же.

Поясним работу метода на примерах.

Пример I. Решить следующую систему линейных алгебраических уравнений

2 x 1 – 3 x 2 + 3 x 3 + 5 x 4 = -1,

3 x 1 + 4 x 2 - 2 x 3 + 6 x 4 = 2, (6)

5 x 1 – 4 x 2 + 6 x 3 + 10 x 4 = 2

методом последовательного полного исключения неизвестных (методом Гаусса - Жордана).

Начальный этап. Сначала выпишем систему уравнений (6) в более удобной форме - в виде таблицы I (0) .