31.2-3

Представим себе, что мы умеем перемножать две (3 X 3)-матрицы, сделав к умножений (при этом не используя коммутативности умножения) и используем этот приём рекурсивно для умножения (га X га)-матриц, как в методе Штрассена. При каких к это позволило бы улучшить оценку Штрассена и умножать (га X га)-матрицы за время o(ralg7). Какая оценка при этом получилась бы?

31.2-4

В.Я. Пан придумал способы умножения двух матриц размера 68 X 68 (132464 умножений чисел), 70 X 70 (143640 умножений) и 72 X 72 (155424 умножений). Какой из них даёт лучшую асимптотическую оценку для умножении (га X га)-матриц при использовании приёма «разделяй и властвуй»? Сравните эту оценку с оценкой для алгоритма Штрассена.

31.2-5

Насколько быстро можно умножить (кп X га)-матрицу на (га X кп)-матрицу, используя алгоритм Штрассена в качестве подпрограммы? А сколько времени уйдёт на умножение тех же матриц в обратном порядке?

31.2-6

Как умножить два комплексных числа а + Ы и с + di, используя лишь 3 операции умножения вещественных чисел? (Алгоритм должен получать на вход значения a, b,c,dn вычислять вещественную и мнимую части произведения, то есть ас - bd и ad + be.)

31.3. Обращение матриц

На практике решение систем линейных уравнений не требует обращения матриц, как мы сидели в преыдущем разделе (LUP-разложение). Но всё-таки может понадобиться вычислить обратную матрицу, и тогда это можно сделать с помощью того же LUP-разложения. Интерес (скорее теоретический, впрочем) представляет также вопрос о том, как ускорить поиск вычисление обратной матрицы с помоью методов Штрассена. (Именно эту цель преследовал Штрассен в своей работе.)

Вычисление обратной матрицы с помощью LUP-разложения.

Пусть нам дано LUP-разложение РА = LU матрицы А размера (га X га). Зная его, можно решить систему вида Ах = b с помощью процедуры LU-Solve за время 0(га2). Чтобы решить другую систему Ах = V (с той же матрицей, но другой правой частью) нам понадобится ещё столько же времени. Таким образом, зная LUP-разложение матрицы А, можно решить к систем с матрицей А за время @(кп2).

Матричное уравнение

АХ = 1п(31.24)

для обратной матрицы X можно рассматривать как совокупность п систем вида Ах = Ь. Обозначим г-й столбец матрицы X через Хг-; тогда

AXi = ег, г = 1,... , п

поскольку г-м столбцом матрицы 1п является единичный вектор ег). Другими словами, нахождение обратной матрицы сводится к решению гг уравнений с одной матрицей и разными правыми частями. После выполнения Lt/P-разложения (время 0(гг3)) на решение каждого из гг уравнений нужно время 0(гг2), так что и эта часть работы требует времени 0(п3). Умножение и обращение матриц

Теперь мы покажем, каким образом можно использовать быстрый алгоритм умножения матриц для быстрого вычисления обратной матрицы. (Подчеркнём, что это улучшение имеет скорее теоретический интерес.) Мы докажем, что (при некоторых естественных предположениях) вычисление обратной матрицы имеет ту же сложность, что и умножение матриц того же размера (с точностью до умножения на константу). Сначала мы докажем более простую часть этого утверждения.

Теорема 31.11 (Умножение матриц не сложнее обращения)

Если можно обратить (гг X гг)-матрицу за время /(гг), причём /(Згг) = 0(1(п)), то можно умножить две (гг X гг)-матрицы за время 0(/(гг)).

Доказательство.

Пусть надо вычислить произведение двух (гг X гг)-матриц А и В. Составим (Згг X Згг)-матрицу

D

Матрица, обратная к D, имеет вид D-1

и мы можем вычислить АВ как (гг X гг)-подматрицу в верхнем правом углу матрицы D~l.

Матрицу D можно построить за время ©(гг2) = 0(1(п)) (заметим, что /(гг) гг2, так как нужно вычислить все гг2 элементов обратной матрицы), а обратить за время 0(/(Згг)) = 0(/(гг)) (согласно условию). Отсюда и следует утверждение теоремы.

Наложенное на /(га) условие /(Зга) = 0(1(п)) означает, что /(га) не делает больших скачков с ростом га. Например, функция /(га) = 0(raclgdra) обладает таким свойством при любых значениях с > 0,d 0.

Сведение обращения матриц к умножению

Нам понядобятся некоторые свойства симметрических положительно определённых матриц, которые мы докажем в разделе 31.6. Теорема 31.11 (Обращение матриц не сложнее умножения) Если можно умножить две (га X га)-матрицы за время М(га), причём М(п) монотонно неубвает и удовлетворяет условию с\М[п) М(2га) С2М(га) при некоторых с\ и с2, причём с\ > 2, то можно обратить невырожденную (га X га)-матрицу за время 0(М(п)).

Доказательство. Обращение матрицы сводится к обращению большей матрицы, так как

(А (Л-1 /А"1 0\ V0 1к) ~ \ 0 1к)

для любого к > 0. Поэтому мы можем доказывать теорему для га, являющихся степенями двойки, поскольку значения М(п) и М(га), где га - ближайшая сверху степень двойки, отличаются не более чем в константу раз.

Пусть сначала матрица А, которую нам надо обратить, является положительно определённой симметрической матрицей. Разобьём её на четыре блока размера га/2 X га/2:

a={ccd)-<3l25>

Рассмотрим матрицу

s = d - св~гст,(31.26) (дополнение Шура) и напишем соотношение

(в~1 + b-lcTs~lcb-1 -b~1cts-

~ V -s~lcb-1s~l

(проверяется умножением на А). Поскольку А является положительно определённой симметрической матрицей, то в и s обладают тем же свойством, и потому обратимы (леммы 31.13, 31.14 и 31.15). Легко проверить, что в~1ст = (св-1)т и b~1cts~1 = (s-1cb-1)t (упр. 31.1-3) Соотношения (31.26) и (31.27) задают рекурсивный алгоритм обращения матрицы, использующий 4 операции умножения (га/2 X га/2)-матриц:

с -в-1, (св-1) -ст,

s1 (св1),

(с в-1)7 (s-cb-1)

(31.27)