4. Метод Жордана - Гаусса.

Схема с выбором главного элемента состоит в том, что требование неравенства нулю диагональных элементов akk, на которые происходит деление в процессе исключения, заменятся более жестким: из всех элементов К-го столба выбрать наибольший по модулю и переставить уравнения так, чтобы этот элемент оказался на месте элемента акк. Выбор главного элемента и связанная с ним перестановка строк необходимы в тех случаях, когда на каком-либо i-ом шаге акк=0 либо же акк очень мало по остальными элементами i- го столбца: при делении на такое «малое» акк будут получаться большие числа с большими абсолютными погрешностями, в результате чего решение может сильно исказиться.

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

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

1. В процессе исключений левая часть I –го уравнения системы обращается в нуль, а правая часть равна некоторому числу, отличному от нуля. т.е. 02+=bc0.

Это означает, что система не имеет решений, так как I – му уравнению не могут удовлетворять никакие значения неизвестных;

2. Левая и правая части I – го уравнения обращаются в нуль. Это означает, что I – ое уравнение является линейной комбинацией остальных, ему удовлетворяет любое найденное решение системы, поэтому оно может быть отброшено. В системе количество неизвестных больше количества уравнений и, следовательно, такая система имеет множество решений;

3. После того как все уравнения использованы для исключения неизвестных получено решение системы.

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

a11x1 + a12x2 + … + a1nxn = b1,n+1

a21x1 + a22x2 + … + a2nxn = b2,n+1

am1x1 + am2x2 + … + amnxn = bm.n+1

Здесь x1, x2, …, xn - неизвестные, которые надо определить. a11, a12, …, amn - коэффициенты системы - и b1, b2, … bm - свободные члены - предполагаются известными. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

Система (1) называется однородной, если все её свободные члены равны нулю (b1 = b2 = … = bm = 0), иначе - неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (1) - совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все ее уравнения в тождества.

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

Совместная система вида (1) может иметь одно или более решений.

Решения c1(1), c2(1), …, cn(1) и c1(2), c2(2), …, cn(2) совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).

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

Решим следующую систему уравнений:

Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:

Проведём следующие действия:

· К строке 2 добавим: -4 * Строку 1.

· К строке 3 добавим: -9 * Строку 1.

· К строке 3 добавим: -3 * Строку 2.

· Строку 2 делим на -2

· К строке 1 добавим: -1 * Строку 3.

· К строке 2 добавим: -3/2 * Строку 3.

· К строке 1 добавим: -1 * Строку 2.

В правом столбце получаем решение:

.

В методе Ньютона наблюдается ускорение сходимости процесса приближений. 5. Метод касательных (метод Ньютона) Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку x0 и запишем в ней уравнение касательной к графику функции f(x): y=f(x0)+ f ¢(x) (x-x0) (1.5) Графики...

Решения от численных методов расчёта. Для определения корней уравнения не требуется знания теорий групп Абеля, Галуа, Ли и пр. и применения специальной математической терминологии: колец, полей, идеалов, изоморфизмов и т.д. Для решения алгебраического уравнения n - ой степени нужно только умение решать квадратные уравнения и извлекать корни из комплексного числа. Корни могут быть определены с...

Математики тригонометрической подстановки и проверка эффективности разработанной методики преподавания. Этапы работы: 1. Разработка факультативного курса на тему: «Применение тригонометрической подстановки для решения алгебраических задач» с учащимися классов с углубленным изучением математики. 2. Проведение разработанного факультативного курса. 3. Проведение диагностирующей контрольной...

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

В общем случае линейное уравнение имеет вид:

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

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

Пример 20.1

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

Решение :

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

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

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

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

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

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

В общем случае разрешенная система уравнений имеет вид:

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

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

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

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

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

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

Теорема (1)

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

Пример 1. Найти общее, базисное и какое-либо частное решение системы уравнений:

Решение :

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

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

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

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

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

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

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

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

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

Теорема (2)

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

Теорема (3)

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

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

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

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

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

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

Преобразование Жордана состоит из элементарных преобразований двух типов:

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

Пример 2 Пересчитаем коэффициенты системы

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

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

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

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

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

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

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

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

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

Пример 3 Решить систему уравнений методом Жордана-Гаусса.

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

Решение :

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

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

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

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

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

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

На некоторое время развевает тоску другой способ приведения матрицы к ступенчатому виду: , причём он совершенно равноценен и может быть неудобен только по причине субъективного восприятия. Но всё рано или поздно приедается…. И подумал тогда Жо рдан – а зачем вообще мучиться с обратным ходом гауссовского алгоритма? Не проще ли сразу получить ответ с помощью дополнительных элементарных преобразований?

…да, такое бывает только по любви =)

Для освоения данного урока «чайникам» придётся пойти путём Жо рдана и прокачать элементарные преобразования хотя бы среднего уровня, прорешав, минимум, 15-20 соответствующих заданий. Поэтому если вы смутно понимаете, о чём идёт разговор и/или у вас возникнет недопонимание чего-либо по ходу занятия, то рекомендую ознакомиться с темой в следующем порядке:

Ну, и совсем замечательно, если отработано понижение порядка определителя .

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

Не мудрствуя лукаво:

Пример 1

Решить систему методом Гаусса-Жордана

Решение : это первое задание урока Метод Гаусса для чайников , где мы 5 раз трансформировали расширенную матрицу системы и привели её к ступенчатому виду:

Теперь вместо обратного хода в игру вступают дополнительные элементарные преобразования. Сначала нам необходимо получить нули на этих местах: ,
а потом ещё один ноль вот здесь: .

Идеальный с точки зрения простоты случай:

(6) Ко второй строке прибавили третью строку. К первой строке прибавили третью строку.

(7) К первой строке прибавили вторую строку, умноженную на –2.

Не могу удержаться от иллюстрации итоговой системы:

Ответ :

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

Не хочу показаться категоричным или придирчивым, но в подавляющем большинстве источников информации, которые я видел, типовые задачи рассмотрены крайне плохо – нужно обладать семью пядями во лбу и потратить массу времени/нервов на тяжёлое неуклюжее решение с дробями. За годы практики мне удалось отшлифовать, не скажу, что самую лучшую, но рациональную и достаточно лёгкую методику, которая доступна всем, кто владеет арифметическими действиями:

Пример 2

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

Решение : первая часть задания хорошо знакома:

(1) Ко второй строке прибавили первую строку, умноженную на –1. К третьей строке прибавили первую строку, умноженную на 3. К четвертой строке прибавили первую строку, умноженную на –5.

(2) Вторую строку разделили на 2, третью строку разделили на 11, четвёртую строку разделили на 3.

(3) Вторая и третья строки пропорциональны, 3-ю строку удалили. К четвёртой строке прибавили вторую строку, умноженную на –7

(4) Третью строку разделили на 2.

Очевидно, что система имеет бесконечно много решений, и наша задача – привести её расширенную матрицу к виду .

Как действовать дальше? Прежде всего, следует отметить, что мы лишились вкусного элементарного преобразования – перестановки строк. Точнее говоря, переставить-то их можно, но в этом нет смысла (просто выполним лишние действия). И далее целесообразно придерживаться следующего шаблона:

Находим наименьшее общее кратное чисел третьего столбца (1, –1 и 3), т.е. – наименьшее число, которое бы делилось без остатка и на 1, и на –1 и на 3. В данном случае, это, конечно же, «тройка». Теперь в третьем столбце нам нужно получить одинаковые по модулю числа , и этими соображениями обусловлено 5-е преобразование матрицы:

(5) Первую строку умножаем на –3, вторую строку умножаем на 3. Вообще говоря, первую строку можно было умножить тоже на 3, но это было бы менее удобно для следующего действия. К хорошему привыкаешь быстро:

(6) Ко второй строке прибавили третью строку. К первой строке прибавили третью строку.

(7) Во втором столбце два ненулевых значения (24 и 6) и нам снова нужно получить одинаковые по модулю числа . В данном случае всё сложилось довольно удачно – наименьшее кратное 24, и эффективнее всего умножить вторую строку на –4.

(8) К первой строке прибавили вторую.

(9) Заключительный штрих: первую строку разделили на –3, вторую строку разделили на –24 и третью строку разделили на 3. Это действие выполняется В ПОСЛЕДНЮЮ ОЧЕРЕДЬ! Никаких преждевременных дробей!

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

Элементарно выражаем базисные переменные через свободную:

и записываем:

Ответ : общее решение:

В подобных примерах применение рассмотренного алгоритма чаще всего оправдано, поскольку обратный ход метода Гаусса обычно требует трудоёмких и неприятных вычислений с дробями.

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

Для самостоятельного решения:

Пример 3

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

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

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

Примечание : термин «базис» имеет алгебраический смысл и понятие геометрического базиса здесь не при чём!

Если в расширенной матрице данных размеров вдруг обнаруживается пара линейно зависимых строк, то её следует попытаться привести к привычному виду с базисными переменными . Образец такого решения есть в Примере №7 статьи об однородных системах линейных уравнений , причём там выбран другой базис .

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

Как найти обратную матрицу методом Гаусса?

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

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

(Понятно, что обратная матрица должна существовать)

Демо-пример 4

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

(1) Ко второй строке прибавили первую строку, умноженную на –3.

(2) К первой строке прибавили вторую строку.

(3) Вторую строку разделили на –2.

Ответ :

Сверьтесь с ответом первого примера урока Как найти обратную матрицу?

Но то была очередная заманивающая задачка – в действительности решение гораздо более длительно и кропотливо. Как правило, вам будет предложена матрица «три на три»:

Пример 5

Решение : присоединяем единичную матрицу и начинаем выполнять преобразования, придерживаясь алгоритма «обычного» метода Гаусса :

(1) Первую и третью строки поменяли местами. На первый взгляд, перестановка строк кажется нелегальной, но на самом деле переставлять их можно – ведь по итогу слева нам нужно получить единичную матрицу, а справа же «принудительно» получится именно матрица (вне зависимости от того будем ли мы переставлять строки в ходе решения или нет) . Обратите внимание, что здесь вместо перестановки можно организовать «шестёрки» в 1-м столбце (наименьшее общее кратное (НОК) чисел 3, 2 и 1) . Решение через НОК особенно удобно, когда в первом столбце отсутствуют «единицы».

(2) Ко 2-й и 3-й строкам прибавили 1-ю строку, умноженную на –2 и –3 соответственно.

(3) К 3-й строке прибавили 2-ю строку, умноженную на –1

Вторая часть решения проводится по уже известной из предыдущего параграфа схеме: перестановки строк становятся бессмысленными, и мы находим наименьшее общее кратное чисел третьего столбца (1, –5, 4): 20. Существует строгий алгоритм нахождения НОК, но здесь обычно хватает подбора. Ничего страшного, если взять бОльшее число, которое делится и на 1, и на –5, и на 4, например, число 40. Отличие будет в более громоздких вычислениях.

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

(4) Третью строку умножаем на 5, вторую строку на 4, первую строку на «минус двадцать»:

(5) К 1-й и 2-й строкам прибавили третью строку.

(6) Первую и третью строки разделили на 5, вторую строку умножили на –1.

(7) Наименьшее общее кратное ненулевых чисел второго столбца (–20 и 44) равно 220. Первую строку умножаем на 11, вторую строку – на 5.

(8) К первой строке прибавили вторую строку.

(9) Первую строку умножили на –1, вторую строку разделили «обратно» на 5.

(10) Теперь на главной диагонали левой матрицы целесообразно получить наименьшее общее кратное чисел диагонали (44, 44 и 4). Совершенно понятно, что это число 44. Третью строку умножаем на 11.

(11) Каждую строку делим на 44. Данное действие выполняется в последнюю очередь!

Таким образом, обратная матрица:

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

Ответ :

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

Продвинутые люди могут несколько сократить решение, но должен предупредить, спешка тут чревата ПОВЫШЕННЫМ риском допустить ошибку.

Аналогичное задание для самостоятельного решения:

Пример 6

Найти обратную матрицу методом Гаусса-Жордана.

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

Иногда бывает удобно более короткое «модернистское» решение, которое заключается в следующем: на первом шаге всё как обычно: .

На втором шаге накатанным приёмом (через НОК чисел 2-го столбца) организуются сразу два нуля во втором столбце: . Перед данным действием особенно трудно устоять, если во 2-м столбце нарисовались одинаковые по модулю числа, например, те же банальные «единицы».

И, наконец, на третьем шаге точно так же получаем нужные нули в третьем столбце: .

Что касается размерности, то в большинстве случаев приходится разруливать матрицу «три на три». Однако время от времени встречается лайт-версия задачи с матрицей «два на два» и хард… – специально для всех читателей сайт:

Пример 7

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

Это задание из моей собственной физматовской контрольной работы по алгебре, …эх, где мой первый курс =) Пятнадцать лет назад (листочек на удивление ещё не пожелтел) , я уложился в 8 шагов, а сейчас – всего лишь в 6! Матрица, кстати, весьма творческая – на первом же шаге просматривается несколько заманчивых путей решения. Моя поздняя версия внизу страницы.

И заключительный совет – после таких примеров очень полезна гимнастика для глаз и какая-нибудь хорошая музыка для релаксации =)

Желаю успехов!

Решения и ответы:

Пример 3: Решение : запишем расширенную матрицу системы и с помощью элементарных преобразований получим базисное решение:


(1) Первую и вторую строки поменяли местами.
(2) Ко второй строке прибавили первую строку, умноженную на –2. К третьей строке прибавили первую строку, умноженную на 5.
(3) Третью строку разделили на 3.
(4) К третьей строке прибавили вторую строку, умноженную на 2.
(5) Третью строку разделили на 7.
(6) Наименьшее кратное чисел 3-го столбца (–3, 5, 1) равно 15. Первую строку умножили на 5, вторую строку умножили на –3, третью строку умножили на 15.
(7) К первой строке прибавили 3-ю строку. Ко второй строке прибавили 3-ю строку.
(8) Первую строку разделили на 5, вторую строку разделили на –3, третью строку разделили на 15.
(9) Наименьшее кратное ненулевых чисел 2-го столбца (–2 и 1) равно: 2. Вторую строку умножили на 2
(10) К первой строке прибавили вторую строку.
(11) Вторую строку разделили на 2.
Выразим базисные переменные через свободные переменные :

Ответ : общее решение:

Пример 6: Решение : обратную матрицу найдём с помощью элементарных преобразований:


(1) Первую строку умножили на –15, вторую строку умножили на 3, третью строку умножили на 5.
(2) Ко 2-й и 3-й строкам прибавили первую строку.
(3) Первую строку разделили на –15, вторую строку разделили на –3, третью строку разделили на –5.
(4) Вторую строку умножили на 7, третью строку умножили на –9.
(5) К третьей строке прибавили вторую строку.


(6) Вторую строку разделили на 7.
(7) Первую строку умножили на 27, вторую строку умножили на 6, третью строку умножили на –4.
(8) К первой и второй строкам прибавили третью строку.
(9) Третью строку разделили на –4. К первой строке прибавили вторую строку, умноженную на –1.
(10) Вторую строку разделили на 2.
(11) Каждую строку разделили на 27.
В результате:
Ответ :

Пример 7: Решение : найдём обратную матрицу методом Гаусса-Жордана:
(1) К 1-й и 4-й строкам прибавили 3-ю строку.
(2) Первую и четвёртую строки поменяли местами.
(3) Ко 2-й строке прибавили 1-ю строку. К 3-й строке прибавили 1-ю строку, умноженную на 2:


(4) К 3-й строке прибавили 2-ю строку, умноженную на –2. К 4-й строке прибавили 2-ю строку.
(5) К 1-й и 3-й строкам прибавили 4-ю строку, умноженную на –1.
(6) Вторую строку умножили на –1, третью строку разделили на –2.
Ответ :

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

Метод Жордана–Гаусса применяется для решения системы 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.

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

Метод базируется на элементарных преобразованиях (переводящих систему в эквивалентную), к которым относятся:

• прибавление к обеим частям уравнения системы другого уравнения той же системы, умноженного на число, отличное от нуля;
• перестановка местами уравнений в системе;
• удаление из системы уравнений вида 0 = 0.

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

Шаг метода состоит в следующем:

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

Алгоритмизировать это можно так:

Для СЛАУ в матричном виде A*x=b (матрица A размерности m*n , совсем необязательно квадратная) составляется следующая таблица:

В таблице выбран разрешающий элемент a r,s ≠0 , тогда r - разрешающая строка, s - разрешающий столбец.

Переход к следующей таблице выполняется по правилам:

1. вычисляются элементы разрешающей строки: a" r,j =a r,j /a r,s - то есть, r-строка таблицы делится на разрешающий элемент;

2. все элементы разрешающего столбца, кроме a r,s , равного единице, становятся равны нулю;

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

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

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

Возможны следующие случаи:

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

2. Получается тождество 0 = 0 - уравнение является линейной комбинацией остальных и строка нулей может быть вычеркнута из системы.

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

Запрограммируем метод в Excel одной формулой, изменять которую должно быть не слишком трудоёмко. Например, для решения СЛАУ

заполним коэффициентами системы ячейки листа от A1 до D4 включительно, выберем разрешающий элемент a 1,1 =1 , а первый шаг метода сделаем в ячейке A6 , куда загоним "универсальную" формулу для преобразования Жордана-Гаусса:

ЕСЛИ(СТРОКА($A$1)=СТРОКА(A1);A1/$A$1;
ЕСЛИ(СТОЛБЕЦ($A$1)=СТОЛБЕЦ(A1);0;(A1*$A$1-
ДВССЫЛ(АДРЕС(СТРОКА(A1);СТОЛБЕЦ($A$1)))*
ДВССЫЛ(АДРЕС(СТРОКА($A$1);СТОЛБЕЦ(A1))))/$A$1))

На следующем шаге разрешающим элементом может быть, например, a 2,2 =1 (ячейка B7). Нам останется скопировать формулу из A6 в A11 (по пустой строке оставляем, чтоб визуально разделить шаги метода), войти в режим редактирования формулы (двойной щелчок по ячейке или выбрать её и нажать клавишу F2) и поправить (аккуратно перетащить мышкой за границу) все закреплённые ссылки с ячейки A1 на B7 .

Конечно, можно заменить везде в формуле закреплённую ссылку $A$1 на конструкцию вида ДВССЫЛ(ЯЧЕЙКА) , образующую динамический адрес ссылки. Скажем, ДВССЫЛ(F8) , а в ячейке F8 будет автоматически формироваться адрес ячейки разрешающего элемента по заданным пользователем номеру строки и столбца. Тогда для этих номеров строки и столбца придётся предусмотреть отдельные ячейки, например, так:

Увы, всё это ничего не даст - вместо $A$1 мы просто вынуждены будем закрепить в формуле ДВССЫЛ($F$8) и всё равно потом перетаскивать столько же ссылок при копировании формулы. Кроме того, "вручную" введённые номера строки и столбца придётся ещё и проверять на допустимость (хотя бы как на рисунке), так что, не будем умножать сущностей.

Посмотреть метод в работе можно на двух первых листах приложенного файла Excel (2 разных примера).

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

Сначала минимум теории.

Если вектор-столбцы СЛАУ линейно независимы, соответствующие им переменные являются базисными , а остальные – свободными . Например, в СЛАУ

переменные x 2 и x 4 - базисные, а x 1 и x 3 - свободные. Базисные переменные между собой независимы, а свободные можно сделать, например, нулями и получить { x 2 =2, x 4 =1 } – базисное решение системы.

Выбирая различные разрешающие элементы, можно получить решения СЛАУ с различными базисами. Любое неотрицательное базисное решение СЛАУ называется опорным .

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

Алгоритм симплекс-метода состоит в следующем:

1. Задача ЛП преобразуется к каноническому виду:

Это всегда можно сделать следующим образом: к задаче, записанной в стандартной постановке

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

2*x 1 +3*x 2 ≤20
3*x 1 +x 2 ≤15
4*x 1 ≤16
3*x 2 ≤12
x 1 ,x 2 ≥0

примет вид

2*x 1 +3*x 2 +x 3 =20
3*x 1 +x 2 +x 4 =15
4*x 1 +x 5 =16
3*x 2 +x 6 =12
x 1 ,x 2 ,...,x 6 ≥0

То есть, "экономический" смысл балансовых переменных очень прост – это "остатки" неиспользованных ресурсов каждого вида.

Если в исходной задаче искался не минимум, а максимум, целевая функция Z заменятся на Z 1 = -Z . Решения задач совпадают, при этом min Z = - max Z 1 . Например, цель

Z(x 1 ,x 2)=2*x 1 +5*x 2 (max)

переписывается в виде

Z 1 (x 1 ,x 2)=-2*x 1 -5*x 2 (min)

Если в исходной задаче были уравнения-неравенства со знаками " ≥ " вместо " ≤ ", обе части каждого такого неравенства умножаются на -1 , а знак неравенства меняется на противоположный, например,

3*x 1 +x 2 +x 4 ≥15

превращается в

3*x 1 -x 2 -x 4 ≤15

Канонический вид модели получен, для него выписывается симплекс-таблица :

В левом столбце записываются базисные переменные (БП), если они ещё не выделены – пусто.

2. С помощью шагов Жордана–Гаусса ищется первоначальный опорный план, т.е. СЛАУ приводится к базисному виду с неотрицательными свободными членами b i >0 . При этом целевая функция Z должна быть выражена только через свободные неизвестные (нулевые коэффициенты в Z-строке стоят только под переменными x i , которые есть в базисе). При выборе разрешающего элемента a r,s в строку r столбца БП выписываем переменную x s , если там уже была переменная – вычеркиваем её (выводим из базиса).

3. Выписываем под столбцами x i опорный план X * : под свободными переменными - нули, под базисными – соответствующие базисной переменной коэффициенты из столбца b .

Ниже выписываем вектор R по правилу: под базисными переменными – нули, под свободными R i =Z i .

Если все R i ≥0 , найдено оптимальное решение X * и значение цели Z min = -q , иначе нужен новый план, а у вас он есть, товарищ Жюков? (п. 4).

4. Для выбора разрешающего столбца s выбираем максимальную по модулю отрицательную компоненту вектора R , разрешающий столбец s выбран. Затем анализируем коэффициенты s-го столбца матрицы системы ограничений. Если все a i,s ≤0 , решения нет и Z min стремится к минус бесконечности, иначе переходим к п.5.

5. Для выбора разрешающей строки r составляем неотрицательные отношения b i /A i,s ≥0 , i=1,2,...,m , и выбираем среди них наименьшее. Если минимум достигается для нескольких строк, за разрешающую можно принять любую из них, при этом, в новом опорном плане значения некоторых базисных переменных станут равными 0, т.е., получаем вырожденный опорный план.

6. Выполняем преобразование Жордана-Гаусса с разрешающим элементом a r,s и переходим к п.3

Геометрически симплекс-методу соответствует кратчайший обход вершин n-мерного выпуклого многогранника, образующего область допустимых решений задачи:

Здесь мы перешли от опорного плана C , представляющего собой одну из вершин многомерного многоугольника, к оптимальному плану E=X * .

Запрограммировать это всё в Excel нелегко, но можно. В прилагаемом документе приведены 3 примера, реализующие решение задач симплекс-методом. Правда, при выполнени шага менять уже придётся 3 формулы, на листе первого примера на симплекс-метод они выделены жёлтым цветом: расчёт отношений для выбора разрешающей строки в ячейке I2 , заполнение столбца БП в ячейке A12 , шаг преобразования Жордана-Гаусса в ячейке B12 . Как и в примере на преобразование Жордана-Гаусса, изменение формул связано только с необходимостью сослаться на новую строку, содержащую адрес ячейки с разрешающим элементом (для первого шага - ячейка C9).