Произведение матриц разбитых на блоки. Масштабирование и распределение подзадач по процессорам

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

7.4.1. Определение подзадач

Блочная схема разбиения матриц подробно изложена в первом разделе "Параллельные методы умножения матрицы на вектор" . При таком способе разделения данных исходные матрицы А , В и результирующая матрица С представляются в виде наборов блоков. Для более простого изложения следующего материала будем предполагать далее, что все матрицы являются квадратными размера nxn , количество блоков по горизонтали и вертикали одинаково и равно q (т.е. размер всех блоков равен kxk, k=n/q ). При таком представлении данных операция матричного умножения матриц А и B в блочном виде может быть представлена так:

Где каждый блок C ij матрицы C определяется в соответствии с выражением

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

Для выполнения всех необходимых вычислений базовым подзадачам должны быть доступны соответствующие наборы строк матрицы A и столбцов матрицы B . Размещение всех требуемых данных в каждой подзадаче неизбежно приведет к дублированию и к значительному росту объема используемой памяти. Как результат, вычисления должны быть организованы таким образом, чтобы в каждый текущий момент времени подзадачи содержали лишь часть необходимых для проведения расчетов данных, а доступ к остальной части данных обеспечивался бы при помощи передачи данных между процессорами. Один из возможных подходов – алгоритм Фокса (Fox ) – рассмотрен далее в данном подразделе. Второй способ – алгоритм Кэннона (Cannon ) – приводится в подразделе 7.5.

7.4.2. Выделение информационных зависимостей

Итак, за основу параллельных вычислений для матричного умножения при блочном разделении данных принят подход, при котором базовые подзадачи отвечают за вычисления отдельных блоков матрицы C и при этом в подзадачах на каждой итерации расчетов располагается только по одному блоку исходных матриц A и B . Для нумерации подзадач будем использовать индексы размещаемых в подзадачах блоков матрицы C , т.е. подзадача (i,j) отвечает за вычисление блока C ij – тем самым, набор подзадач образует квадратную решетку, соответствующую структуре блочного представления матрицы C .

Возможный способ организации вычислений при таких условиях состоит в применении широко известного алгоритма Фокса (Fox ) - см., например, [ [ 34 ] , [ 51 ] ].

В соответствии с алгоритмом Фокса в ходе вычислений на каждой базовой подзадаче (i,j) располагается четыре матричных блока:

• блок C ij матрицы C , вычисляемый подзадачей;
• блок A ij матрицы A , размещаемый в подзадаче перед началом вычислений;
• блоки A" ij , B" ij матриц A и B , получаемые подзадачей в ходе выполнения вычислений.

Выполнение параллельного метода включает:

• этап инициализации, на котором каждой подзадаче (i,j) передаются блоки A ij , B ij и обнуляются блоки C ij на всех подзадачах;
• этап вычислений, в рамках которого на каждой итерации l, 0<=l

Для пояснения этих правил параллельного метода на рис. 7.6 приведено состояние блоков в каждой подзадаче в ходе выполнения итераций этапа вычислений (для решетки подзадач 2x2 ).

7.4.3. Масштабирование и распределение подзадач по процессорам

В рассмотренной схеме параллельных вычислений количество блоков может варьироваться в зависимости от выбора размера блоков – эти размеры могут быть подобраны таким образом, чтобы общее количество базовых подзадач совпадало с числом процессоров p . Так, например, в наиболее простом случае, когда число процессоров представимо в виде (т.е. является полным квадратом), можно выбрать количество блоков в матрицах по вертикали и горизонтали равным (т.е. ). Такой способ определения количества блоков приводит к тому, что объем вычислений в каждой подзадаче является одинаковым и тем самым достигается полная балансировка вычислительной нагрузки между процессорами. В более общем случае при произвольных количестве процессоров и размерах матриц балансировка вычислений может отличаться от абсолютно одинаковой, но, тем не менее, при надлежащем выборе параметров может быть распределена между процессорами равномерно в рамках требуемой точности.

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

7.4.4. Анализ эффективности

Определим вычислительную сложность данного алгоритма Фокса. Построение оценок будет происходить при условии выполнения всех ранее выдвинутых предположений: все матрицы являются квадратными размера nxn , количество блоков по горизонтали и вертикали являются одинаковым и равным q (т.е. размер всех блоков равен kxk, k=n/q ), процессоры образуют квадратную решетку и их количество равно p=q 2 .

Как уже отмечалось, алгоритм Фокса требует для своего выполнения q итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц А и В и прибавляет результаты умножения к текущему значению блока матрицы C . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок n 3 /p . Как результат, показатели ускорения и эффективности алгоритма имеют вид:

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

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы A на столбец блока матрицы В можно оценить как 2(n/q)-1 . Количество строк и столбцов в блоках равно n/q и, как результат, трудоемкость операции блочного умножения оказывается равной (n 2 /p)(2n/q-1) . Для сложения блоков требуется n 2 /p операций. С учетом всех перечисленных выражений время выполнения вычислительных операций алгоритма Фокса может быть оценено следующим образом:

(напомним, что есть время выполнения одной элементарной скалярной операции).

Оценим затраты на выполнение операций передачи данных между процессорами. На каждой итерации алгоритма перед умножением блоков один из процессоров строки процессорной решетки рассылает свой блок матрицы A остальным процессорам своей строки. Как уже отмечалось ранее, при топологии сети в виде гиперкуба или полного графа выполнение этой операции может быть обеспечено за log 2 q шагов, а объем передаваемых блоков равен n 2 /p . Как результат, время выполнения операции передачи блоков матрицы A при использовании модели Хокни может оцениваться как

Где – латентность, – пропускная способность сети передачи данных, а w есть размер элемента матрицы в байтах. В случае же когда топология строк процессорной решетки представляет собой кольцо, выражение для оценки времени передачи блоков матрицы A принимает вид:

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

(напомним, что параметр q определяет размер процессорной решетки и ).

Глава 1
МАТРИЦЫ И ОПРЕДЕЛИТЕЛИ

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

§ 1. Матрицы

1. Понятие матрицы. Матрицей называется прямоугольная таблица из чисел, содержащая некоторое количество m строк и некоторое количество n столбцов. Числа тип называются порядками матрицы. В случае, если m = n , матрица называется квадратной, а число m = n - ее порядком. В дальнейшем для записи матрицы будут применяться либо сдвоенные черточки, либо круглые скобки:

Впрочем, для краткого обозначения матрицы часто будет использоваться либо одна большая латинская буква (например, А), либо символ ║a ij ║ , а иногда и с разъяснением:
Числа a ij , входящие в состав данной матрицы, называются ее элементами. В записи a ij - первый индекс i означает номер строки, а второй индекс j - номер столбца.
В случае квадратной матрицы

вводятся понятия главной и побочной диагоналей. Главной диагональю матрицы (1.1) называется диагональ a 11 a 22 ...a nn , идущая из левого верхнего угла этой матрицы в правый нижний ее угол. Побочной диагональю той же матрицы называется диагональ a n1 a (n-1)2 ...a 1n , идущая из левого нижнего угла в правый верхний угол.

2. Основные операции над матрицами и их свойства. Прежде всего договоримся считать две матрицы равными , если эти матрицы имеют одинаковые порядки и все их соответствующие элементы совпадают.
Перейдем к определению основных операций над матрицами.
а) Сложение матриц. Суммой двух матриц А = ║a ij ║ (i = 1, 2,..., m ; j = 1, 2,... , n ) и В = (i = 1, 2,..., m ; j = 1, 2,... , n ) одних и тех же порядков m и n называется матрица С= (i = 1, 2,..., m ; j = 1, 2,... , n ) тех же порядков m и n , элементы c ij - которой равны

C ij = a ij + b ij (i = 1, 2,..., m ; j = 1, 2,... , n ) (1.2

Для обозначения суммы двух матриц используется запись С = А + В. Операция составления суммы матриц называется их сложением . Итак, по определению

Из определения суммы матриц, а точнее, из формулы (1.2), непосредственно вытекает, что операция сложения матриц обладает теми же свойствами, что и операция сложения вещественных чисел, а именно:
1) переместительным свойством: А + В = В + А;
2) сочетательным свойством: (А + В) + С = А + (Б + С).
Эти свойства позволяют не заботиться о порядке следования слагаемых матриц при сложении двух или большего числа матриц.

б) Умножение матрицы на число. Произведением матрицы А = ║a ij ║ (i = 1, 2,..., m ; j = 1, 2,... , n ) на вещественное
число λ называется матрица С = (i = 1, 2,..., m ; j = 1, 2,... , n ), элементы c ij которой равны

c ij = λ a ij (i = 1, 2,..., m ; j = 1, 2,... , n ) (1.3)

Для обозначения произведения матрицы на число используется запись С = λ А или С = Аλ . Операция составления произведения матрицы на число называется умножением матрицы на это число. Непосредственно из формулы (1.3) ясно, что умножение матрицы на число обладает следующими свойствами:
1) сочетательным свойством относительно числового множителя: (λµ )А = λ (µ А);

2) распределительным свойством относительно суммы матриц: λ (А + В) = λ А + λ В;
3) распределительным свойством относительно суммы чисел: (λ + µ )А = λ А + µ A.
Замечание. Разностью двух матриц А и В одинаковых порядков тип естественно назвать такую матрицу С тех же порядков m и n , которая в сумме с матрицей В дает матрицу А. Для обозначения разности двух матриц используется естественная запись: С = А - В.
Очень легко убедиться в том, что разность С двух матриц А и В может быть получена по правилу С = А + (-1)В.
в) Перемножение матриц. Произведением матрицы А = ║a ij ║ (i = 1, 2,..., m ; j = 1, 2,... , n ), имеющей порядки, соответственно равные m и n , на матрицу В = (i = 1, 2,..., n ; j = 1, 2,... , p ), имеющую порядки, соответственно равные n и p , называется матрица С= (i = 1, 2,..., m ; j = 1, 2,... , p ), имеющая порядки, соответственно равные m и p , и элементы c ij , определяемые формулой

Для обозначения произведения матрицы А на матрицу В используют запись С = А - В. Операция составления произведения матрицы А на матрицу В называется перемножением этих матриц. Из сформулированного выше определения вытекает, что матрицу А можно умножить не на всякую матрицу В : необходимо, чтобы число столбцов матрицы А было равно числу строк матрицы В.
В частности, оба произведения А В и В А можно определить лишь в том случае, когда число столбцов А совпадает с числом строк Б, а число строк А совпадает с числом столбцов В. При этом обе матрицы А - В и В - А будут квадратными, но порядки их будут, вообще говоря, различными. Для того чтобы оба произведения А В и В А не только были определены, но и имели одинаковый порядок, необходимо и достаточно, чтобы обе матрицы А и В были квадратными матрицами одного и того же порядка.
Формула (1.4) представляет собой правило составления элементов матрицы С, являющейся произведением матрицы А на матрицу В. Это правило можно сформулировать и словесно: элемент c ij , стоящий на пересечении i -й строки и j- го столбца матрицы

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

Из формулы (1.4) вытекают следующие свойства произведения матрицы А на матрицу В:
1) сочетательное свойство: (АВ)С = А(ВС);
2) распределительное относительно суммы матриц свойство: (А + В)С = АС + ВС или А(В + С) = АВ + АС.
Распределительное свойство сразу вытекает из формул (1.4) и (1.2), а для доказательства сочетательного свойства достаточно заметить, что если А = ║a ij ║ (i = 1, 2,..., m ; j = 1, 2,... , n ), В = (i = 1, 2,..., n ; j = 1, 2,... , p ), С= (i = 1, 2,..., m ; j = 1, 2,... , p ), то
элемент d il матрицы (АВ)С в силу (1.4) равен а элемент d il " матрицы А(ВС) равен , но тогда равенство d il = d il " вытекает из возможности изменения порядка суммирования относительно j и к.
Вопрос о перестановочном свойстве произведения матрицы А на матрицу В имеет смысл ставить лишь для квадратных матриц А и В одинакового порядка (ибо, как указывалось выше, только для таких матриц А и В оба произведения АВ и В А определены и являются матрицами одинаковых порядков). Элементарные примеры показывают, что произведение двух квадратных матриц одинакового порядка не обладает, вообще говоря, перестановочным свойством . В самом деле, если положить

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

где d 1 , d 2 ,..., d n - какие угодно числа. Легко видеть, что если все эти числа равны между собой, т. е. d 1 = d 2= ...= d n = d, то для любой
квадратной матрицы А порядка n справедливо равенство AD = DA. В самом деле, обозначим символами Cij и cf{j элементы, стоящие на пересечении i -й строки и j-ro столбца матриц AD и DA соответственно. Тогда из равенства (1.4) и из вида матрицы D получим, что c ij =a ij d j = a ij d , c ij " = d i a ij = da ij (1.6) , т.е. c ij = c ij " .

Среди всех диагональных матриц (1.5) с совпадающими элементами d 1 = d 2= ...= d n особо важную роль играют две матрицы. Первая из этих матриц получается при d = 1, называется единичной матрицей п-го порядка и обозначается символом Е. Вторая матрица получается при d = 0, называется нулевой матрицей п-го порядка и обозначается символом О. Таким образом,

В силу доказанного выше АЕ = ЕА и АО = О А. Более того, из формул (1.6) очевидно, что

AE = EA = E, АО = ОА = О. (1.7)

Первая из формул (1.7) характеризует особою роль единичной матрицы Е, аналогичную той роли, которую играет число 1 при перемножении вещественных чисел. Что же касается особой роли нулевой матрицы О, то ее выявляет не только вторая из формул (1.7), но и элементарно проверяемое равенство А + О = О + А = А (это равенство является прямым следствием формулы (1.2)).
В заключение заметим, что понятие нулевой матрицы можно вводить и для неквадратных матриц (нулевой называют любую матрицу, все элементы которой равны нулю).
3. Блочные матрицы. Предположим, что некоторая матрица А = ║a ij ║ при помощи горизонтальных и вертикальных прямых разбита на отдельные прямоугольные клетки, каждая из которых представляет собой матрицу меньших размеров и называется блоком исходной матрицы . В таком случае возникает возможность рассмотрения исходной матрицы А как некоторой новой (так называемой блочной) матрицы А = ║A αβ ║ , элементами A αβ которой служат указанные блоки.
Указанные элементы мы обозначаем большой латинской буквой, чтобы подчеркнуть, что они являются, вообще говоря, матрицами, а не числами и (как обычные числовые элементы) снабжаем двумя индексами, первый из которых указывает номер «блочной» строки, а второй - номер «блочного» столбца. Например, матрицу

можно рассматривать как блочную матрицу , элементами которой служат следующие блоки:

Замечательным является тот факт, что основные операции с блочными матрицами совершаются по тем же правилам, по которым они совершаются с обычными числовыми матрицами, только в роли элементов выступают блоки.
В самом деле, элементарно проверяется, что если матрица А = ║a ij ║ является блочной и имеет блочные элементы A αβ , то при том же разбиении на блоки матрице λ А = ║λa ij ║ отвечают блочные элементы λA αβ (При этом блочные элементы λA αβ сами вычисляются по правилу умножения матрицы A αβ на число λ ).
Столь же элементарно проверяется, что если матрицы A и В имеют одинаковые порядки и одинаковым образом разбиты на блоки, то сумме матриц А и В отвечает блочная матрица с элементами A αβ = A αβ + B αβ (здесь A αβ и B αβ - блочные элементы матриц А и В).
Пусть, наконец, А и В - две блочные матрицы такие, что число столбцов каждого блока A αβ равно числу строк блока В β γ (так что
при любых α, β и γ определено произведение матриц A αβ В β γ ). Тогда произведение С = А В представляет собой матрицу с элементами С α γ , определяемыми формулой

Для доказательства этой формулы достаточно расписать левую и правую ее части в терминах обычных (числовых) элементов матриц A и В (предоставляем это сделать читателю).
В качестве примера применения блочных матриц остановимся на понятии так называемой прямой суммы квадратных матриц. Прямой суммой двух квадратных матриц А и В порядков m и n соответственно называется квадратная блочная матрица С порядка m + n, равная . Для обозначения прямой суммы матриц А и В используется запись С = А

Часто приходится пользоваться матрицами, разбитыми на прямоугольные части - «клетки» или «блоки». Рассмотрению таких «блочных» матриц мы посвящаем настоящий параграф.

1. Пусть дана прямоугольная матрица

При помощи горизонтальных и вертикальных линий рассечем матрицу на прямоугольные блоки:

. (58)

Про матрицу (58) будем говорить, что она разбита на блоков размером или что она представлена в виде блочной матрицы. Вместо (58) будем сокращенно писать:

В случае будем пользоваться и такой записью:

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

Легко усмотреть, что

. (62)

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

, . (63)

Тогда легко проверить, что

, где . (64)

Отдельно отметим тот частный случай, когда одним из сомножителей является квазидиагональная матрица. Пусть - квазидиагональная матрица, т. е. и при . В этом случае формула (64) нам дает:

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

Пусть теперь - квазидиагональная матрица, т. е. и при . Тогда из (64) получаем:

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

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

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

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

Действительно, полагая в (64) и

.

Аналогично разбирается случай нижних квазитреугольных матриц.

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

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

(67)

2. Пусть дана блочная матрица

(68)

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

. (69)

Введем вспомогательную квадратную матрицу , представленную в виде следующей квадратной схемы блоков:

. (70)

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

Нетрудно видеть, что

Отсюда, поскольку - неособенная матрица, для рангов матриц и имеем

В частном случае, когда – квадратная матрица, из (71) имеем:

Но определитель квазитреугольной матрицы равен 1:

Следовательно,

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

Полученные результаты могут быть сформулированы в виде следующей теоремы.

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

3. Рассмотрим теперь тот частный случай, когда в матрице диагональный блок - квадратная и притом неособенная матрица ().

К -й строке матрицы прибавим первую строку, помноженную слева на . Тогда получим матрицу

, (76)

. (77)

Если - квадратная неособенная матрица, то этот процесс можно продолжить. Мы приходим, таким образом, к обобщенному алгоритму Гаусса.

Пусть - квадратная матрица. Тогда

. (78)

Формула (78) сводит вычисление определителя состоящего из блоков, к вычислению определителя меньшего порядка, состоящего из блоков.

Рассмотрим определитель , разбитый на четыре блока:

где и - квадратные матрицы.

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

. (I)

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

. (II)

В частном случае, когда все четыре матрицы , , , - квадратные (одного и того же порядка ), из (I) и (II) следуют формулы Шура, сводящие вычисление определителя -го порядка к вычислению определителя -го порядка:

(), (Iа)

(). (IIа)

Если матрицы и перестановочны между собой, то из (Iа) следует:

(при условии ). (Iб)

Точно так же, если и перестановочны между собой, то

(при условии ). (IIб)

Формула (Iб) была получена в предположении , а формула (IIб) при условии . Однако, исходя из соображений непрерывности, эти ограничения можно отбросить.

Из формул (Iа) - (IIб) можно получить еще шесть формул, поменяв местами в правых частях и и одновременно и .

.

По формуле (Iб)

.

4. Установим формулу Фробениуса для обращения блочной матрицы. Пусть неособенная квадратная матрица () разбита на блоки

, (80)

и пусть - также неособенная квадратная матрица (). Требуется определить .

Применим к матрице обобщенный алгоритм Гаусса. Из второй блочной строки вычтем первую, предварительно помноженную слева на . Эта операция равносильна умножению матрицы слева на матрицу , где . Поэтому

. (81)

Введем обозначение

и заметим, что из равенства (81) следует:

Поэтому, поскольку , то и . Переходя к обратным матрицам в равенстве (81), получим

. (83)

Обратную матрицу для матрицы будем искать в виде . Тогда из равенства

находим, что . Таким образом,

. (84)

Но тогда из равенства (83) находим

Выполняя умножение блочных матриц в правой части равенства (85), приходим к формуле Фробениуса

, (86)

. (87)

Формула Фробениуса (86) сводит обращение матрицы порядка к обращению двух матриц порядка и и к операциям сложения и умножения матриц с размерами , , и .

Если предположить, что (вместо ) и поменять ролями матрицы и , то можно получить другой вид формулы Фробениуса:

, (88)

. (89)

Пример. Требуется найти элементы обратной матрицы для матрицы

.

Полагаем

Находим последовательно

, ,

, ,

,

,

,

.

Поэтому по формуле (86) находим:

.

5. Из теоремы 3 вытекает так же

Теорема 4. Если прямоугольная матрица представлена в блочном виде

где - квадратная неособенная матрица порядка (), то ранг матрицы равен только в том случае, когда

Доказательство. Вычтем из второй блочной строки матрицы первую, предварительно помноженную слева на . Тогда получим матрицу

. (92)

Матрицы и согласно теореме 3 имеют один и тот же ранг. Ранг же матрицы совпадает с рангом матрицы (т. е. с ) тогда и только тогда, когда имеет место , т. е. (91). Теорема доказана.

Проиллюстрируем этот способ нахождения на следующем примере.

Пример. Пусть

Требуется вычислить .

Применяем несколько видоизмененный метод исключения к матрице

.

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

.

,

,

.