Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц.
Определение
Пусть даны две прямоугольные матрицы и размерности и соответственно:
![A =
\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{bmatrix},\;\;\;
B =
\begin{bmatrix}
b_{11} & b_{12} & \cdots & b_{1q} \\
b_{21} & b_{22} & \cdots & b_{2q} \\
\vdots & \vdots & \ddots & \vdots \\
b_{n1} & b_{n2} & \cdots & b_{nq}
\end{bmatrix}.](//upload.wikimedia.org/math/0/6/d/06ddc9035af760cb6499678349152bbb.png)
Тогда матрица размерностью называется их произведением:
![C =
\begin{bmatrix}
c_{11} & c_{12} & \cdots & c_{1q} \\
c_{21} & c_{22} & \cdots & c_{2q} \\
\vdots & \vdots & \ddots & \vdots \\
c_{m1} & c_{m2} & \cdots & c_{mq}
\end{bmatrix},](//upload.wikimedia.org/math/c/8/3/c8373c77ef1c942fb221e00d5d2aba0a.png)
где:
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована. В частности, умножение всегда выполнимо, если оба сомножителя — квадратные матрицы одного и того же порядка.
Следует заметить, что из существования произведения вовсе не следует существование произведения
Иллюстрация
Иллюстрация справа демонстрирует произведение двух матриц A и B, она показывает как каждые пересечения в произведении матриц соответствуют строкам матрицы A столбцам матрицы B. Размер результирующей матрицы всегда максимально возможный, т.е. для каждой строки матрицы A и столбца матрицы B есть всегда соответствующее пересечение в произведении матрицы. Произведение матриц AB состоит из всевозможных комбинаций скалярных произведений строк матрицы A и столбцов матрицы B.
Значения на пересечениях отмеченных кружочками будут:
![\begin{align}
{\color{Red}x_{1,2}} &= (a_{1,1}, a_{1,2})\cdot(b_{1,2}, b_{2,2}) \\
&= a_{1, 1}b_{1,2} + a_{1,2}b_{2, 2} \\
{\color{Blue}x_{3,3}} &= (a_{3,1}, a_{3, 2})\cdot(b_{1, 3}, b_{2, 3}) \\
&= a_{3, 1}b_{1,3} + a_{3,2}b_{2, 3}.
\end{align}](//upload.wikimedia.org/math/8/d/8/8d882833a9d17808e781f358abc688c0.png)
В общем случае, произведение матриц не является коммутативной операцией. К примеру:
![\overset{3\times 4 \text{ matrix}}{\begin{bmatrix}
\cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \cdot \\
\color{Blue} 1 & \color{Blue} 2 & \color{Blue} 3 & \color{Blue} 4 \\
\end{bmatrix}}
\overset{4\times 5\text{ matrix}}{\begin{bmatrix}
\cdot & \cdot & \cdot & \color{Red}a & \cdot \\
\cdot & \cdot & \cdot & \color{Red}b & \cdot \\
\cdot & \cdot & \cdot & \color{Red}c & \cdot \\
\cdot & \cdot & \cdot & \color{Red}d & \cdot \\
\end{bmatrix}}
=
\overset{3\times 5\text{ matrix}}{
\begin{bmatrix}
\cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & x_{3,4} & \cdot \\
\end{bmatrix}}.](//upload.wikimedia.org/math/a/1/c/a1cb69ea0bb8d73749301f1f1856fb46.png)
Элемент произведения матриц приведённых выше вычисляется следующим образом
![x_{3,4} =
({\color{Blue}1}, {\color{Blue}2}, {\color{Blue}3}, {\color{Blue}4})\cdot
({\color{Red}a}, {\color{Red}b}, {\color{Red}c}, {\color{Red}d})
= {\color{Blue} 1}\times{\color{Red} a}
+{\color{Blue} 2}\times{\color{Red} b}
+{\color{Blue} 3}\times{\color{Red} c}
+{\color{Blue} 4}\times{\color{Red} d}.](//upload.wikimedia.org/math/e/d/9/ed9af7757a0596497c3f19dc7f8f845d.png)
Первая координата в обозначении матрицы обозначает строку, вторая координата столбец; этот порядок используют как при индексации, так и при обозначении размера. Элемент на пересечении строки и столбца результирующей матрицы является скалярным произведением -й строки первой матрицы и -го столбца второй матрицы. Это объясняет почему ширина и высота умножаемых матриц должны совпадать: в противном случае скалярное произведение не определено.
Свойства
Сочетательное свойство:
Распределительное свойство:
- .
Произведение матрицы на единичную матрицу подходящего порядка равно самой матрице:
Произведение матрицы на нулевую матрицу подходящей размерности равно нулевой матрице:
Если и — квадратные одного и того же порядка, то произведение матриц обладает ещё рядом свойств.
Умножение матриц в целом некоммутативно:
Если , то матрицы и называются перестановочными или коммутирующими между собой.
Определитель и след произведения не зависят от порядка умножения матриц:
Обратная матрица
Квадратная матрица называется неособенной (невырожденной), если она имеет единственную обратную матрицу такую, что выполняется условие:
В противном случае матрица называется особенной (вырожденной).
Матрица порядка является невырожденной в том и только в том случае, если в этом случае есть квадратная матрица того же порядка
где — алгебраическое дополнение элемента в определителе
Алгоритмы быстрого перемножения матриц
Сложность вычисления произведения матриц по определению составляет Θ(n3), однако существуют более эффективные алгоритмы[1], применяющиеся для больших матриц.
- Алгоритм Штрассена (1969)
- Первый алгоритм быстрого умножения матриц был разработан В. Штрассеном[2] в 1969. В основе алгоритма лежит рекурсивное разбиение матриц на блоки. На каждом этапе рекурсии выполняется семь умножений вместо восьми. В результате сложность этого алгоритма составляет . Недостатком данного метода является бо́льшая сложность программирования по сравнению со стандартным алгоритмом, численная неустойчивость и большой объём используемой памяти.
- Разработано большое количество алгоритмов на основе метода Штрассена, которые улучшают его численную устойчивость и объём используемой памяти.
- Алгоритм Пана (1978)
- В 1978 Пан[3] предложил свой метод умножения матриц, сложность которого составила Θ(n2.78041).
- Алгоритм Бини (1979)
- В 1979 группа итальянских учёных во главе с Бини[4] разработала алгоритм умножения матриц с использованием тензоров. Его сложность составляет Θ(n2.7799).
- Алгоритмы Шёнхаге (1981)
- В 1981 Шёнхаге[5] представил метод, работающий со сложностью Θ(n2.695), который он назвал частичным матричным умножением. Позже ему удалось получить оценку Θ(n2.6087).
- Затем Шёнхаге создал метод, названный методом прямых сумм, сложность которого составляет Θ(n2.548). Романи сумел понизить оценку до Θ(n2.5166), а Пан — до Θ(n2.5161).
- Алгоритм Копперсмита — Винограда (1990)
- В 1990 Копперсмит и Виноград[6] опубликовали алгоритм, умножающий матрицы со сложностью O(n2.3727).[7] Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день алгоритм Копперсмита-Винограда является наиболее асимптотически быстрым, но он эффективен только на очень больших матрицах и поэтому не применяется.
- Алгоритмы с использованием теории групп (2003)
- В 2003 Кох и др. рассмотрели в своих работах[8] алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали возможность существования алгоритмов умножения матриц со сложностью Θ(n2)[9].
См. также
Литература
- Корн Г., Корн Т. Алгебра матриц и матричное исчисление // Справочник по математике. — 4-е издание. — М: Наука, 1978. — С. 392—394..
Примечания
- ↑ Кибернетический сборник. Новая серия. Вып. 25. Сб. статей 1983 — 1985 гг.: Пер. с англ. — М.: Мир, 1988 — В.Б. Алекссев. Сложность умножения матриц. Обзор.
- ↑ Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
- ↑ Pan V. Ya, Strassen's algorithm is not optimal — trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations. — Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978
- ↑ Bini D., Capovani M., Lotti G., Romani F. — complexity for approximate matrix multiplication. — Inform. Process. Lett., 1979
- ↑ Schonhage A. Partial and total matrix multiplication. - SIAM J. Comput., 1981
- ↑ Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251–280, 1990.
- Breaking the Coppersmith-Winograd barrier.
- Group-theoretic Algorithms for Matrix Multiplication
- Toward an Optimal Algorithm for Matrix Multiplication