Домой

Софт

Мастерская

Лирика

ЧаВО

Юмор

E-Mail

197-577-902

Алгоритм построения обратной матрицы

Описание алгоритма

Пусть А - исходная матрица, обратную к которой мы хотим найти.

n и k - кол-во строк и столбцов в ней соотвественно.

1. Сначала проверим является ли А квадратной, т.е. совпадают ли n и k.
2. Затем проверим равен ли определитель мартицы А нулю. Если он равен нулю, то обратной матрицы не существует.
3. Создаем матрицу Inv равную единичной размерности nxn.
4. А затем при помощи элементарных преобразований: сложения строк матрицы, умножения строки на число, перестановки столбцов и строк приведем матрицу A к единичной. Причем, параллельно, те же самые преобразования будем производить и с матрицей Inv (переставлять и складывать те же строки/столбцы, и умножать на это же число).
5. В результате, матрица Inv - будет являться обратной матрицей к исходной матрице A.

Рассмотрим четвертый шаг алгоритма более подробно.

Это цикл по количеству строк матрицы А. Каждая итерация цикла устроена следующим образом:

1. На каждой итерации мы смотрим на элемент A(i,i). Если он равен нулю, то мы ищем в матрице А ненулевой элемент. Причем ищем его только в прямоугольнике (i, i, n, n) матрицы A. Если он найден, и его координаты (i2, j2), то меняем местами i-ую строку с i2-ой, и j-ый столбец с j2-ым. Те же перестановки делаем в матрице Inv.
2. Делим i-ую строку матриц А и Inv на элемент A(i, i) (делить можно, т.к. мы на шаге 1 позаботились о том, чтобы этот элемент не был равен 0).
   Таким образом элемент A(i, i) теперь равен 1.
3. При помощи вычитания i-й строки матрицы А, с определенным коэффициентом, из остальных ее строк зануляем все элементы стоящие выше и ниже элемента с индексом (i, i). С тем же коэфициентом вычитаем i-ую строку матрицы Inv из ее остальных строк.

Пример

Припишем справа через черту матрицу Inv:

Вычтем из второй строки первую с коэффициентом 3:

Поделим вторую строку на -2:

Вычтем вторую строку из первой с коэффициентом 2:

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

Реализация

Скачать уже реализованный класс "Матрица" с методом нахождения обратной матрицы вы можете отсюда.

Слава Антонов © 2002 — August 13, 2008