Просмотр кода страницы Умножение матриц

[[Файл:Matrix multiplication diagram.svg|right]]
'''Умноже́ние ма́триц''' — одна из основных операций над [[матрица (математика)|матрица]]ми. Матрица, получаемая в результате операции умножения, называется '''произведе́нием ма́триц'''. Элементы новой матрицы получаются из элементов старых матриц в соответствии с правилами, проиллюстрированными ниже{{переход|Иллюстрация|1}}.

Матрицы <math>A</math> и <math>B</math> могут быть перемножены, если они '''совместимы''' в том смысле, что число столбцов матрицы <math>A</math> равно числу строк <math>B</math>.

Матрицы обладают многими алгебраическими [[Умножение#Свойства|свойствами умножения]], присущими обычным числам, за исключением [[Коммутативная операция|коммутативности]]{{переход|Свойства|1}}.

Для квадратных матриц, помимо умножения, может быть введена операция возведения матрицы в степень{{переход|Степени матриц|1}} и [[обратная матрица]]{{переход|Обратная матрица|1}}.

Тогда как матрицы используются для описания, в частности, преобразований [[Пространство (математика)|математических пространств]] ([[поворот]], [[отражение (геометрия)|отражение]], [[растяжение (математика)|растяжение]] и другие), произведение матриц будет описывать [[композиция преобразований|композицию преобразований]]{{переход|Обсуждение|1}}.

== Определение ==
Пусть даны две прямоугольные матрицы <math>A</math> и <math>B</math> размерности <math>l \times m</math> и <math>m \times n</math> соответственно:
: <math>
A = 
  \begin{bmatrix} 
    a_{11} & a_{12} & \cdots & a_{1m} \\
    a_{21} & a_{22} & \cdots & a_{2m} \\ 
    \vdots & \vdots & \ddots & \vdots \\ 
    a_{l1} & a_{l2} & \cdots & a_{lm}
  \end{bmatrix},\;\;\;
B =   
  \begin{bmatrix} 
    b_{11} & b_{12} & \cdots & b_{1n} \\
    b_{21} & b_{22} & \cdots & b_{2n} \\ 
    \vdots & \vdots & \ddots & \vdots \\ 
    b_{m1} & b_{m2} & \cdots & b_{mn}
  \end{bmatrix}.
</math>
Тогда матрица <math>C</math> размерностью <math>l \times n</math>:
: <math>
C = 
  \begin{bmatrix} 
    c_{11} & c_{12} & \cdots & c_{1n} \\
    c_{21} & c_{22} & \cdots & c_{2n} \\ 
    \vdots & \vdots & \ddots & \vdots \\ 
    c_{l1} & c_{l2} & \cdots & c_{ln}
  \end{bmatrix},
</math>
в которой:
: <math> c_{ij} = \sum_{r=1}^m a_{ir}b_{rj} \;\;\; \left(i=1, 2, \ldots l;\; j=1, 2, \ldots n \right).</math>
называется их ''произведением''.

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

Таким образом, из существования произведения <math>AB</math> вовсе не следует существование произведения <math>BA.</math>

== Иллюстрация ==
[[Файл:Matrix multiplication diagram 2.svg|right]]
'''Произведение матриц''' ''AB'' '''состоит из всех возможных комбинаций [[скалярное произведение|скалярных произведений]] вектор-строк матрицы''' ''A'' '''и вектор-столбцов матрицы''' ''B''. Элемент матрицы ''AB'' с индексами ''i, j'' есть скалярное произведение ''i''-ой вектор-строки матрицы ''A'' и ''j''-го вектор-столбца матрицы ''B''.

Иллюстрация справа демонстрирует вычисление произведения двух матриц ''A'' и ''B'', она показывает как каждые пересечения в произведении матриц соответствуют строкам матрицы ''A'' и столбцам матрицы ''B''. Размер результирующей матрицы всегда максимально возможный, то есть для каждой строки матрицы ''A'' и столбца матрицы ''B'' есть всегда соответствующее пересечение в произведении матрицы.

Значения на пересечениях, отмеченных кружочками, будут:

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

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

: <math>
  \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}}
</math>
Элемент <math>x_{3,4}</math> произведения матриц, приведённых выше, вычисляется следующим образом
: <math>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}</math>

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

== Обсуждение ==
Увидеть причины описанного правила матричного умножения легче всего, рассмотрев умножение [[Вектор (математика)|вектора]] на матрицу.

Последнее естественно вводится исходя из того, что при разложении векторов по [[базис]]у действие (любого) линейного оператора ''A'' даёт выражение компонент вектора '''v'''' = ''A'''''v''':
: <math>v'_i = \sum\limits_j A_{ij} v_j</math>

То есть [[Линейное отображение|линейный оператор]] оказывается представлен матрицей, векторы — векторами-столбцами, а действие оператора на вектор — матричным умножением вектора-столбца слева на матрицу оператора (это частный случай матричного умножения, когда одна из матриц — вектор-столбец — имеет размер <math>n\times 1</math>).

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

Рассмотрев последовательное действие на вектор двух операторов: сначала ''A'', а потом ''B'' (или преобразование базиса ''A'', а затем преобразование базиса ''B''), дважды применив нашу формулу, получим:
: <math>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, </math>

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

: <math> (BA)_{ik} = \sum\limits_j B_{ij} A_{jk}.</math>

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

== Свойства ==
''Сочетательное свойство'', [[Ассоциативность (математика)|ассоциативность]]:
: <math>\mathbf{A} ( \mathbf{B C} ) = ( \mathbf{A B} ) \mathbf{C};</math>
: <math>\alpha (\mathbf{AB}) = (\alpha\mathbf{A}) \mathbf{B} = \mathbf{A}(\alpha\mathbf{B}).</math>

''Распределительное свойство'', [[Дистрибутивность|дистрибутивность относительно сложения]]:
: <math>\mathbf{A} ( \mathbf{B} + \mathbf{C} ) = \mathbf{A B} + \mathbf{AC};</math>
: <math>( \mathbf{A} + \mathbf{B} ) \mathbf{C} = \mathbf{A C} + \mathbf{B C}.</math>.

Произведение матрицы на [[Единичная матрица|единичную матрицу]] <math>\mathbf{E}</math> подходящего порядка равно самой матрице:
: <math>\mathbf{EA} = \mathbf{A};</math>
: <math>\mathbf{AE} = \mathbf{A}.</math>

Произведение матрицы на [[Нулевая матрица|нулевую матрицу]] <math>\mathbf{0}</math> подходящей размерности равно нулевой матрице:
: <math>\mathbf{0A} = \mathbf{0};</math>
: <math>\mathbf{A0} = \mathbf{0}.</math>

Если <math>\mathbf{A}</math> и <math>\mathbf{B}</math> — [[Матрица (математика)#Квадратная матрица и смежные определения|квадратные матрицы]] одного и того же порядка, то произведение матриц обладает ещё рядом свойств.

Умножение матриц в общем случае [[Коммутативность|некоммутативно]]:
: <math>\mathbf{AB} \ne \mathbf{BA}.</math>

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

Простейшие примеры коммутирующих матриц:
* любая квадратная матрица — с самой собой: <math>\mathbf{AA} = \mathbf{AA} = \mathbf{A^2}</math> (возведение матрицы в квадрат);
* любая квадратная матрица — с единичной матрицей того же порядка: <math>\mathbf{AE} = \mathbf{EA} = \mathbf{A}</math>;
* любая квадратная матрица — с нулевой матрицей того же порядка: <math>\mathbf{A0} = \mathbf{0A} = \mathbf{0}</math>;
* любая невырожденная квадратная матрица — со своей обратной матрицей: <math>\mathbf{AA^{-1}} = \mathbf{A^{-1}A} = \mathbf{E}</math>.

[[Определитель]] и [[След матрицы|след]] произведения не зависят от порядка умножения матриц:
: <math>\det(\mathbf{AB}) = \det(\mathbf{BA}) = \det \mathbf{A} \cdot \det\mathbf{B};</math>
: <math>\mbox{tr}(\mathbf{AB}) = \mbox{tr}(\mathbf{BA}).</math>

== Обратная матрица ==
{{main|Обратная матрица}}

[[Матрица (математика)#Квадратная матрица и смежные определения|Квадратная матрица]] <math>A</math> называется [[Невырожденная матрица|''неособенной'' (''невырожденной'')]], если она имеет единственную [[Обратная матрица|''обратную матрицу'']] <math>A^{-1}</math> такую, что выполняется условие:
: <math>AA^{-1} = A^{-1}A = E.</math>
В противном случае матрица <math>A</math> называется [[Вырожденная матрица|''особенной'' (''вырожденной'')]].

Матрица <math>A = \left [ a_{ik} \right]</math> порядка <math>n</math> является невырожденной в том и только в том случае, если <math>\det A = \det \left [ a_{ik} \right ] \ne 0;</math> в этом случае <math>A^{-1}</math> есть [[Матрица (математика)#Квадратная матрица и смежные определения|квадратная матрица]] того же порядка <math>n:</math>
: <math>A^{-1} = \left [ a_{ik} \right ]^{-1} = \left [ \frac{A_{ki}}{\det A} \right ],</math>
где <math>A_{ik}</math> — [[алгебраическое дополнение]] элемента <math>a_{ik}</math> в определителе <math>\det \left [ a_{ik} \right ].</math>

== Алгоритмы быстрого перемножения матриц ==
Сложность вычисления произведения матриц по определению составляет <math>\ O(n^3)</math>, однако существуют более эффективные алгоритмы<ref>Кибернетический сборник. Новая серия. Вып. 25. Сб. статей 1983 — 1985 гг.: Пер. с англ. — М.: Мир, 1988 — В.Б. Алекссев. Сложность умножения матриц. Обзор.</ref>, применяющиеся для больших матриц. Вопрос о предельной скорости умножения больших матриц, также как и вопрос о построении наиболее быстрых и устойчивых практических алгоритмов умножения больших матриц остаётся одной из [[нерешённые проблемы математики|нерешённых проблем]] [[Линейная алгебра|линейной алгебры]].

* '''[[Алгоритм Штрассена]] (1969)'''
: Первый алгоритм быстрого умножения больших матриц был разработан [[Штрассен, Фолькер|Фолькером Штрассеном]]{{source-ref|Q21694537}} в 1969 году. В основе алгоритма лежит рекурсивное разбиение матриц на блоки '''2×2'''. Штрассен доказал, что матрицы '''2×2''' можно некоммутативно перемножить с помощью семи умножений, поэтому на каждом этапе рекурсии выполняется семь умножений вместо восьми. В результате асимптотическая сложность этого алгоритма составляет <math>O( n^{\log_{2}7}) \approx O(n^{2.81})</math>. Недостатком данного метода является бо́льшая сложность программирования по сравнению со стандартным алгоритмом, слабая численная устойчивость и больший объём используемой памяти. Разработан ряд алгоритмов на основе метода Штрассена, которые улучшают численную устойчивость, скорость по константе и другие его характеристики. Тем не менее, в силу простоты алгоритм Штрассена остаётся одним из практических алгоритмов умножения больших матриц. Штрассен также выдвинул следующую [[Гипотеза Штрассена|гипотезу Штрассена]]: для сколь угодно малого <math>\varepsilon > 0</math> существует алгоритм, при достаточно больших [[натуральное число|натуральных]] ''n'' гарантирующий перемножение двух матриц размера <math>n \times n</math> за <math>O(n^{2+\varepsilon})</math> операций.
* '''Дальнейшие улучшения показателя степени ω для скорости матричного умножения'''
[[Файл:MatrixMultComplexity_svg.svg|thumb|400px|right|Хронология улучшения оценок показателя степени ω для вычислительной сложности матричного умножения <math>O(n^\omega)</math>.]]
: В дальнейшем оценки скорости умножения больших матриц многократно улучшались. Однако эти алгоритмы носили теоретический, в основном приближённый характер. В силу неустойчивости алгоритмов приближённого умножения в настоящее время они не используются на практике.
:* '''Алгоритм Пана (1978)'''
:: В 1978 году Пан<ref>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</ref> предложил свой метод умножения матриц, сложность которого составила '''Θ(n<sup>2.78041</sup>)'''.
:* '''Алгоритм Бини (1979)'''
:: В 1979 году группа итальянских учёных во главе с Бини<ref>Bini D., Capovani M., Lotti G., Romani F. — <math>O( n^{2.7799} )</math> complexity for approximate matrix multiplication. — Inform. Process. Lett., 1979</ref> разработала алгоритм умножения матриц с использованием тензоров. Его сложность составляет '''Θ(n<sup>2.7799</sup>)'''.
:* '''Алгоритмы Шёнхаге (1981)'''
:: В 1981 году Шёнхаге<ref>Schonhage A. Partial and total matrix multiplication. — SIAM J. Comput., 1981</ref> представил метод, работающий со скоростью '''Θ(n<sup>2.695</sup>)'''. Оценка получена с помощью подхода, названного ''частичным матричным умножением''. Позже ему удалось получить оценку '''Θ(n<sup>2.6087</sup>)'''.
:: Затем Шёнхаге на базе ''метода прямых сумм'' получил оценку сложности '''Θ(n<sup>2.548</sup>)'''. Романи сумел понизить оценку до '''Θ(n<sup>2.5166</sup>)''', а Пан — до '''Θ(n<sup>2.5161</sup>)'''.
* '''[[Алгоритм Копперсмита — Винограда]] (1990)'''
: В 1990 году Копперсмит и Виноград<ref>Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. ''Journal of Symbolic Computation'', 9:251-280, 1990.</ref> опубликовали алгоритм, асимптотическая сложность которого составляла '''O(n<sup>2.3755</sup>)'''. Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день модификации алгоритма Копперсмита—Винограда являются наиболее [[Теория сложности вычислений#Асимптотическая сложность|асимптотически]] быстрыми. В последней модификации (2024) сложность алгоритма составляет '''O(n<sup>2.371339</sup>)'''<ref>{{Cite arXiv|author1=Josh Alman|author2= Ran Duan|author3= Virginia Vassilevska Williams|author4= Yinzhan Xu|author5= Zixuan Xu|author6= Renfei Zhou|title=More Asymmetry Yields Faster Matrix Multiplication|eprint=2404.16349 |class=cs.DS |year=2024}}</ref>. Известно, что широкий класс модификаций этого алгоритма в принципе не может достичь сложность лучше, чем '''O(n<sup>2.3078</sup>)'''<ref>{{Cite web |url=https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/ |title=New Breakthrough Brings Matrix Multiplication Closer to Ideal |website=Quanta Magazine |access-date=2024-03-07 |archive-date=2024-03-07 |archive-url=https://web.archive.org/web/20240307163317/https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/ |url-status=live }}</ref>. Алгоритм Копперсмита—Винограда эффективен только на матрицах астрономического размера и на практике применяться не может.
* '''Связь с теорией групп (2003)'''
: В 2003 году Кох и др. рассмотрели в своих работах<ref>{{Cite web |url=http://www.cs.caltech.edu/~umans/papers/CKSU05.pdf |title=Group-theoretic Algorithms for Matrix Multiplication |access-date=2009-09-26 |archive-date=2011-08-06 |archive-url=https://web.archive.org/web/20110806121526/http://www.cs.caltech.edu/~umans/papers/CKSU05.pdf |deadlink=no }}</ref> алгоритмы Штрассена и Копперсмита-Винограда в контексте [[Теория групп|теории групп]]. Они показали, что гипотеза Штрассена справедлива (т.е. минимальная сложность ограничена <math>O(n^{2+\varepsilon})</math> для любого <math>\varepsilon</math>) , если выполняется одна из гипотез теории групп<ref>{{Cite web |url=http://www.siam.org/pdf/news/174.pdf |title=Toward an Optimal Algorithm for Matrix Multiplication |accessdate=2009-09-26 |archiveurl=https://web.archive.org/web/20100331095603/http://www.siam.org/pdf/news/174.pdf |archivedate=2010-03-31 |deadlink=yes }}</ref>.

== Степени матриц ==
Квадратные матрицы можно многократно умножать сами на себя так же, как обычные числа, так как у них одинаковое число строк и столбцов.
Такое последовательное умножение можно назвать '''возведением матрицы в степень''' — это будет частный случай обычного умножения нескольких матриц. У прямоугольных матриц число строк и столбцов разное, поэтому их ''никогда'' нельзя возводить в степень.
Матрица {{math|'''A'''}} размерности {{math|''n'' × ''n''}}, возведённая в степень, определяется формулой
: <math>\mathbf{A}^k = \underbrace{\mathbf{A}\mathbf{A}\cdots\mathbf{A}}_{k}</math>
и обладает следующими свойствами ({{math|''λ''}} — некоторый скаляр):

'''Нулевая степень:'''

: <math>\mathbf{A}^0 = \mathbf{E}</math>

где '''E''' - [[единичная матрица]]. Это аналог того факта, что [[Возведение в степень#Целая степень|нулевая степень]] любого числа равна единице.

'''Умножение на скаляр:'''

: <math> ( \lambda \mathbf{A} )^k = \lambda^k\mathbf{A}^k</math>

'''Определитель:'''

: <math> \det(\mathbf{A}^k) = \det(\mathbf{A})^k </math>

Наиболее простой способ вычисления степени матрицы — это умножать {{math|''k''}} раз матрицу {{math|'''A'''}} на результат предыдущего умножения, начиная с единичной матрицы, как это часто делают для скаляров.
Для [[Диагонализируемая матрица|диагонализируемых матриц]] существует лучший метод, основанный на использовании [[Спектральное разложение|спектрального разложения]] матрицы {{math|'''A'''}}.
Ещё один метод, основанный на [[Теорема Гамильтона — Кэли|теореме Гамильтона — Кэли]], строит более эффективное выражение для {{math|'''A'''<sup>''k''</sup>}}, в котором в требуемую степень возводится ''скаляр'', а не вся ''матрица''.

Особый случай составляют [[Диагональная матрица|диагональные матрицы]].
Так как произведение диагональных матриц сводится к умножению соответствующих диагональных элементов, то {{math|''k''}}-ая степень диагональной матрицы {{math|'''A'''}} состоит из элементов, возведённых в требуемую степень:
: <math>
  \mathbf{A}^k = \begin{pmatrix}
    a_{11} & 0 & \cdots & 0 \\
    0 & a_{22} & \cdots & 0 \\
    \vdots & \vdots & \ddots & \vdots \\
    0 & 0 & \cdots & a_{nn}
  \end{pmatrix}^k =
\begin{pmatrix}
    a_{11}^k & 0 & \cdots & 0 \\
    0 & a_{22}^k &  \cdots & 0 \\
    \vdots & \vdots & \ddots & \vdots \\
    0 & 0 & \cdots & a_{nn}^k
  \end{pmatrix}.
</math>

Таким образом, возвести диагональную матрицу в степень несложно.
При возведении произвольной матрицы (не обязательно диагональной) в степень часто полезным оказывается использовать сначала свойства [[Диагонализируемая матрица|диагонализируемых матриц]].

Используя умножение матриц и возведение матриц в степень, можно определить другие операции над матрицами. Например, [[матричная экспонента]] может быть определена через [[степенной ряд]], [[матричный логарифм]] — как обратная к матричной [[Экспонента|экспоненте]] функция и так далее.

== См. также ==
* [[Произведение Кронекера]]
* [[Произведение Адамара]]

== Литература ==
* {{книга|автор=Корн&nbsp;Г., Корн&nbsp;Т.|заглавие=Справочник по математике|часть=Алгебра матриц и матричное исчисление|издание=4-е издание|место=М|издательство=Наука|год=1978|страницы=392—394}}

== Примечания ==
{{примечания}}

{{Векторы и матрицы}}

[[Категория:Алгоритмы умножения матриц]]
[[Категория:Матрицы]]
[[Категория:Численные методы линейной алгебры]]
[[Категория:Билинейные операторы]]