Умножение матриц

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц.

Определение[править | править вики-текст]

Пусть даны две прямоугольные матрицы A и B размерности m \times n и n \times q соответственно:


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}.

Тогда матрица C размерностью m \times q называется их произведением:


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},

где:

 c_{ij} = \sum_{r=1}^n a_{ir}b_{rj} \;\;\; \left(i=1, 2, \ldots m;\; j=1, 2, \ldots q \right).

Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована. В частности, умножение всегда выполнимо, если оба сомножителя — квадратные матрицы одного и того же порядка.

Следует заметить, что из существования произведения AB вовсе не следует существование произведения BA.

Иллюстрация[править | править вики-текст]

Matrix multiplication diagram 2.svg

Произведение матриц AB состоит из всех возможных комбинаций скалярных произведений вектор-строк матрицы A и вектор-столбцов матрицы B. Элемент матрицы AB с индексами i, j есть скалярное произведение i-ой вектор-строки матрицы A и j-го вектор-столбца матрицы B.

Иллюстрация справа демонстрирует вычисление произведения двух матриц A и B, она показывает как каждые пересечения в произведении матриц соответствуют строкам матрицы A и столбцам матрицы B. Размер результирующей матрицы всегда максимально возможный, то есть для каждой строки матрицы 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}

В общем случае, произведение матриц не является коммутативной операцией. К примеру:


  \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}}

Элемент x_{3,4} произведения матриц, приведённых выше, вычисляется следующим образом

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}\cdot{\color{Red} a}
+{\color{Blue} 2}\cdot{\color{Red} b}
+{\color{Blue} 3}\cdot{\color{Red} c}
+{\color{Blue} 4}\cdot{\color{Red} d}

Первая координата в обозначении матрицы обозначает строку, вторая координата — столбец; этот порядок используют как при индексации, так и при обозначении размера. Элемент x_{{\color{Blue}i}{\color{Red}j}} на пересечении строки i и столбца j результирующей матрицы является скалярным произведением i-й строки первой матрицы и j-го столбца второй матрицы. Это объясняет почему ширина и высота умножаемых матриц должны совпадать: в противном случае скалярное произведение не определено.

Мотивация[править | править вики-текст]

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

Последнее естественно вводится исходя из того, что при разложении векторов по базису действие (любого) линейного оператора A дает выражение компонент вектора v' = Av:

v'_i = \sum\limits_j A_{ij} v_j

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

(Равно переход к любому новому базису при смене координат представляется полностью аналогичным выражением, только v'_i в этом случае уже не компоненты нового вектора в старом базисе, а компоненты старого вектора в новом базисе; при этом A_{ij} - элементы матрицы перехода к новому базису).

Рассмотрев последовательное действие на вектор двух операторов: сначала A, а потом B (или преобразование базиса A, а затем преобразование базиса B), дважды применив нашу формулу, получим:

v''_i = \sum\limits_j B_{ij}\sum\limits_k A_{jk} v_k = \sum\limits_j \sum\limits_k B_{ij} A_{jk} v_k 
= \sum\limits_k \sum\limits_j (B_{ij} A_{jk}) v_k,

откуда видно, что композиции BA действия линейных операторов A и B (или аналогичной композиции преобразований базиса) соответствует матрица, вычисляемая по правилу произведения соответствующих матриц:

 (BA)_{ik} = \sum\limits_j B_{ij} A_{jk}.

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

Свойства[править | править вики-текст]

Сочетательное свойство:

\mathbf{A} ( \mathbf{B C} ) = ( \mathbf{A B} ) \mathbf{C};
\alpha (\mathbf{AB}) = (\alpha\mathbf{A}) \mathbf{B} = \mathbf{A}(\alpha\mathbf{B}).

Распределительное свойство:

\mathbf{A} ( \mathbf{B} + \mathbf{C} ) = \mathbf{A B} + \mathbf{AC};
( \mathbf{A} + \mathbf{B} ) \mathbf{C} = \mathbf{A C} + \mathbf{B C}..

Произведение матрицы на единичную матрицу \mathbf{E} подходящего порядка равно самой матрице:

\mathbf{EA} = \mathbf{A};
\mathbf{AE} = \mathbf{A}.

Произведение матрицы на нулевую матрицу \mathbf{0} подходящей размерности равно нулевой матрице:

\mathbf{0A} = \mathbf{0};
\mathbf{A0} = \mathbf{0}.

Если \mathbf{A} и \mathbf{B}квадратные матрицы одного и того же порядка, то произведение матриц обладает ещё рядом свойств.

Умножение матриц в целом некоммутативно:

\mathbf{AB} \ne \mathbf{BA}.

Если \mathbf{AB} = \mathbf{BA}, то матрицы \mathbf{A} и \mathbf{B} называются перестановочными или коммутирующими между собой.

Определитель и след произведения не зависят от порядка умножения матриц:

\det(\mathbf{AB}) = \det(\mathbf{BA}) = \det \mathbf{A} \cdot \det\mathbf{B};
\mbox{tr}(\mathbf{AB}) = \mbox{tr}(\mathbf{BA}).

Обратная матрица[править | править вики-текст]

Квадратная матрица A называется неособенной (невырожденной), если она имеет единственную обратную матрицу A^{-1} такую, что выполняется условие:

\! AA^{-1} = A^{-1}A = E.

В противном случае матрица A называется особенной (вырожденной).

Матрица A = \left [ a_{ik} \right] порядка n является невырожденной в том и только в том случае, если \det A = \det \left [ a_{ik} \right ] \ne 0; в этом случае A^{-1} есть квадратная матрица того же порядка n:

A^{-1} = \left [ a_{ik} \right ]^{-1} = \left [ \frac{A_{ki}}{\det A} \right ],

где A_{ik}алгебраическое дополнение элемента a_{ik} в определителе \det \left [ a_{ik} \right ].

Алгоритмы быстрого перемножения матриц[править | править вики-текст]

Сложность вычисления произведения матриц по определению составляет \ O(n^3), однако существуют более эффективные алгоритмы[1], применяющиеся для больших матриц. Вопрос о предельной скорости умножения больших матриц, также как и вопрос о построении наиболее быстрых и устойчивых практических алгоритмов умножения больших матриц остается одной из нерешенных проблем линейной алгебры.

Первый алгоритм быстрого умножения больших матриц был разработан Фолькером Штрассеном[2] в 1969. В основе алгоритма лежит рекурсивное разбиение матриц на блоки 2Х2. Штрассен доказал, что матрицы 2Х2 можно некоммутативно перемножить с помощью семи умножений, поэтому на каждом этапе рекурсии выполняется семь умножений вместо восьми. В результате асимптотическая сложность этого алгоритма составляет O( n^{\log_{2}7}) \approx O(n^{2.81}). Недостатком данного метода является бо́льшая сложность программирования по сравнению со стандартным алгоритмом, слабая численная устойчивость и больший объём используемой памяти. Разработан ряд алгоритмов на основе метода Штрассена, которые улучшают численную устойчивость, скорость по константе и другие его характеристики. Тем не менее, в силу простоты алгоритм Штрассена остается одним из практических алгоритмов умножения больших матриц. Штрассен также выдвинул следующую гипотезу Штрассена: для сколь угодно малого \varepsilon > 0 существует алгоритм, при достаточно больших натуральных n гарантирующий перемножение двух матриц размера n \times n за O(n^{2+\varepsilon}) операций.
  • Дальнейшие улучшения показателя степени ω для скорости матричного умножения
Хронология улучшения оценок показателя степени ω для скорости матричного умножения.
В дальнейшем оценки скорости умножения больших матриц многократно улучшались. Однако эти алгоритмы носили теоретический, в основном приближенный характер. В силу неустойчивости алгоритмов приближенного умножения в настоящее время они не используются на практике.
  • Алгоритм Пана (1978)
В 1978 Пан[3] предложил свой метод умножения матриц, сложность которого составила Θ(n2.78041).
  • Алгоритм Бини (1979)
В 1979 группа итальянских учёных во главе с Бини[4] разработала алгоритм умножения матриц с использованием тензоров. Его сложность составляет Θ(n2.7799).
  • Алгоритмы Шёнхаге (1981)
В 1981 Шёнхаге[5] представил метод, работающий со скоростью Θ(n2.695). Оценка получена с помощью подхода,названного частичным матричным умножением. Позже ему удалось получить оценку Θ(n2.6087).
Затем Шёнхаге на базе метода прямых сумм получил оценку сложности Θ(n2.548). Романи сумел понизить оценку до Θ(n2.5166), а Пан — до Θ(n2.5161).
В 1990 Копперсмит и Виноград[6] опубликовали алгоритм, который в модификации Вильямс Василевской [7] 2011 года умножает матрицы со скоростью O(n2.3727). Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день модификации алгоритма Копперсмита-Винограда являются наиболее асимптотически быстрыми. Но тот факт, что полученные улучшения ничтожны, позволяет говорить о существовании "барьера Копперсмита-Винограда" в асимптотических оценках скорости алгоритмов. Алгоритм Копперсмита-Винограда эффективен только на матрицах астрономического размера и на практике применяться не может.
  • Связь с теорией групп (2003)
В 2003 Кох и др. рассмотрели в своих работах[8] алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали, что гипотеза Штрассена справедлива, если выполняется одна из гипотез теории групп[9].

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Корн Г., Корн Т. Алгебра матриц и матричное исчисление // Справочник по математике. — 4-е издание. — М: Наука, 1978. — С. 392—394..

Примечания[править | править вики-текст]

  1. Кибернетический сборник. Новая серия. Вып. 25. Сб. статей 1983 — 1985 гг.: Пер. с англ. — М.: Мир, 1988 — В.Б. Алекссев. Сложность умножения матриц. Обзор.
  2. Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
  3. 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
  4. Bini D., Capovani M., Lotti G., Romani F. — O( n^{2.7799} ) complexity for approximate matrix multiplication. — Inform. Process. Lett., 1979
  5. Schonhage A. Partial and total matrix multiplication. - SIAM J. Comput., 1981
  6. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251–280, 1990.
  7. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier
  8. Group-theoretic Algorithms for Matrix Multiplication
  9. Toward an Optimal Algorithm for Matrix Multiplication