Метод Гаусса — Йордана (метод полного исключения неизвестных) — метод, который используется для решения
квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы,
нахождения координат вектора в заданном базисе или отыскания ранга
матрицы. Метод является модификацией метода Гаусса. Назван в
честь Карла Фридриха Гаусса и немецкого геодезиста и математика Вильгельма
Йордана.
Алгоритм
Выбирают первый слева столбец матрицы, в
котором есть хоть одно отличное от нуля значение.
Если самое верхнее число в этом столбце ноль, то меняют всю первую строку
матрицы с другой строкой матрицы, где в этой колонке нет нуля.
Все элементы первой строки делят на верхний элемент выбранного столбца.
Из оставшихся строк вычитают первую строку, умноженную на первый элемент
соответствующей строки, с целью получить первым элементом каждой строки (кроме
первой) ноль.
Далее проводят такую же процедуру с матрицей, получающейся из исходной
матрицы после вычёркивания первой строки и первого столбца.
После повторения этой процедуры раз получают верхнюю
треугольную матрицу
Вычитают из предпоследней строки последнюю строку, умноженную на
соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась
только 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.
Знаете ли Вы, что устойчивость оптимального плана - это свойство математических моделей, имеющих форму задачи линейного программирования, состоящее в неизменности двойственных оценок ограничений при изменениях свободных членов ограничений в определённых пределах и в неизменности значений переменных при изменениях параметров целевой функции в определённых пределах.