Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 130 стр.

UptoLike

ВУЗ: 

ИвГУ | Иваново

Составители: 

Рубрика: 

130 Арифметические линейные пространства Гл. 2
14.6. Алгоритм Жордана — Гаусса вычисления обратной
матрицы. Пусть A — квадратная матрица размера n × n. Ниже
будет описан алгоритм, выясняющий, является ли данная матрица
A обратимой, и, если является, вычисляющий обратную матрицу
B = A
−1
.
Описание алгоритма:
— образуем составную матрицу (A|E) размера n × 2n;
— приведем эту матрицу к ступенчатому виду с помощью элемен-
тарных преобразований над строками (это равносильно умножению
матрицы (A|E) слева на некоторые элементарные матрицы);
— определим число ступенек r, приходящихся на зону матрицы A
(т. е. на первые n столбцов); это число будет равняться рангу данной
матрицы;
— если r < n, то констатируем, что данная матрица не является
обратимой и останавливаем работу алгоритма;
— если r = n, то констатируем, что матрица A обратима (ступень-
ки в ступенчатом виде этой матрицы будут располагаться подряд и
заполнять всю главную диагональ);
— продолжим преобразования и доведем ступенчатый вид до вида
Ж.—Г.; в данном случае левая половина полученной матрицы будет
совпадать с единичной матрицей E;
— считываем из преобразованной составной матрицы ее правую
половину B, образовавшуюся на месте единичной матрицы E;
— записываем ответ: A
−1
= B.
Схематически работу алгоритма можно представить следующим
образом:
(A|E)
Элементарные преобразования
− − − − − − − − − − − − − →
типoв I − III над строками
(E|A
−1
).
Обоснование алгоритма: вывод об обратимости (необратимости)
исходной матрицы обосновывается теоремой 14.1; в случае невырож-
денности для матрицы A можно найти такие элементарные матрицы
P
1
, P
2
, ..., P
k
, что для их произведения P = P
k
· . . . · P
2
· P
1
справедли-
во равенство A = P
−1
и, следовательно, равенство P = A
−1
; значит,
при умножении на P слева составной матрицы (A|E) мы получим:
P · (A| E) = (P · A | P · E) = (E| P ) = (E|A
−1
).
130          Арифметические линейные пространства                       Гл. 2

   14.6. Алгоритм Жордана — Гаусса вычисления обратной
матрицы. Пусть A — квадратная матрица размера n × n. Ниже
будет описан алгоритм, выясняющий, является ли данная матрица
A обратимой, и, если является, вычисляющий обратную матрицу
B = A−1 .
   Описание алгоритма:
   — образуем составную матрицу (A|E) размера n × 2n;
   — приведем эту матрицу к ступенчатому виду с помощью элемен-
тарных преобразований над строками (это равносильно умножению
матрицы (A|E) слева на некоторые элементарные матрицы);
   — определим число ступенек r, приходящихся на зону матрицы A
(т. е. на первые n столбцов); это число будет равняться рангу данной
матрицы;
   — если r < n, то констатируем, что данная матрица не является
обратимой и останавливаем работу алгоритма;
   — если r = n, то констатируем, что матрица A обратима (ступень-
ки в ступенчатом виде этой матрицы будут располагаться подряд и
заполнять всю главную диагональ);
   — продолжим преобразования и доведем ступенчатый вид до вида
Ж.—Г.; в данном случае левая половина полученной матрицы будет
совпадать с единичной матрицей E;
   — считываем из преобразованной составной матрицы ее правую
половину B, образовавшуюся на месте единичной матрицы E;
   — записываем ответ: A−1 = B.
   Схематически работу алгоритма можно представить следующим
образом:

                       Элементарные преобразования
            (A|E) − − − − − − − − − − − − − → (E|A−1 ).
                        типoв I − III над строками


   Обоснование алгоритма: вывод об обратимости (необратимости)
исходной матрицы обосновывается теоремой 14.1; в случае невырож-
денности для матрицы A можно найти такие элементарные матрицы
P1 , P2 , ..., Pk , что для их произведения P = Pk · . . . · P2 · P1 справедли-
во равенство A = P −1 и, следовательно, равенство P = A−1 ; значит,
при умножении на P слева составной матрицы (A|E) мы получим:

             P · (A| E) = (P · A | P · E) = (E| P ) = (E|A−1 ).

Страницы