Метод Гаусса — Йордана (метод полного исключения неизвестных) — метод, который используется для решения
квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы,
нахождения координат вектора в заданном базисе или отыскания ранга
матрицы. Метод является модификацией метода Гаусса. Назван в
честь Карла Фридриха Гаусса и немецкого геодезиста и математика Вильгельма
Йордана.
Алгоритм
Выбирают первый слева столбец матрицы, в
котором есть хоть одно отличное от нуля значение.
Если самое верхнее число в этом столбце ноль, то меняют всю первую строку
матрицы с другой строкой матрицы, где в этой колонке нет нуля.
Все элементы первой строки делят на верхний элемент выбранного столбца.
Из оставшихся строк вычитают первую строку, умноженную на первый элемент
соответствующей строки, с целью получить первым элементом каждой строки (кроме
первой) ноль.
Далее проводят такую же процедуру с матрицей, получающейся из исходной
матрицы после вычёркивания первой строки и первого столбца.
После повторения этой процедуры раз получают верхнюю
треугольную матрицу
Вычитают из предпоследней строки последнюю строку, умноженную на
соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась
только 1 на главной диагонали.
Повторяют предыдущий шаг для последующих строк. В итоге получают единичную
матрицу и решение на месте свободного вектора (с ним необходимо проводить все
те же преобразования).
Расширенный алгоритм для нахождения обратной матрицы
Пусть дано:
Прямой ход (алгоритм образования нулей под главной диагональю)
Разделим первую строку матрицы А на получим: , j — столбец
матрицы А.
Повторяем действия для матрицы I, по формуле: , s — столбец
матрицы I
Получим:
Будем образовывать 0 в первом столбце :
Повторяем действия для матрицы І, по формулам :
Получим:
продолжаем выполнять аналогичные операции, используя формулы :
при условии, что
Повторяем действия для матрицы І, по формулам :
при условии, что Получим :
Обратный ход (алгоритм образования нулей над главной диагональю)
Используем формулу: , при условии, что
Повторяем действия для матрицы І, по формуле : , при условии, что
Окончательно получаем :
Пример
Для решения следующей системы уравнений:
Запишем её в виде матрицы 3×4, где последний столбец является свободным
членом:
Проведём следующие действия:
К строке 2 добавим: −4 × Строку 1.
К строке 3 добавим: −9 × Строку 1.
Получим:
К строке 3 добавим: −3 × Строку 2.
Строку 2 делим на −2
К строке 1 добавим: −1 × Строку 3.
К строке 2 добавим: −3/2 × Строку 3.
К строке 1 добавим: −1 × Строку 2.
В правом столбце получаем решение:
.
Литература
Lipschutz, Seymour, and Lipson, Mark. «Schaum’s Outlines: Linear Algebra».
Tata McGraw-hill edition. Delhi 2001. pp. 69-80.
Знаете ли Вы, что несовместность системы ограничений - это ситуация, при которой множество допустимых значений переменных задачи математического программирования пусто вследствие наличия взаимоисключающих уравнений или неравенств, определяющих это множество. Вследствие отстутствия допустимых значений при несовместности системы ограничений оптимального решения задачи не существует.