Перегляд вихідного коду сторінки Множення матриць

[[Файл:Matrix multiplication diagram 2.svg|right]]
'''Множе́ння ма́триць'''&nbsp;— це [[бінарна операція]], яка використовуючи дві матриці, утворює нову матрицю, яка називається '''доб́утком ма́триць'''. [[Дійсне число|Дійсні]] або [[Комплексне число|комплексні]] числа множаться відповідно до правил [[Таблиця множення#Елементарна арифметика|елементарної арифметики]].

Схема праворуч демонструє обчислення добутку двох матриць ''A'' і ''B''. Вона показує як перетини в добутку матриць відповідають рядкам матриці ''A'' і стовпцям матриці ''B''.
Значення на перетинах відмічених кружечками будуть:
:<math>\begin{align}
{\color{Red}x_{1,2}}  &= {\color{Olive}(a_{1,1}, a_{1,2})} \cdot {\color{Green}(b_{1,2}, b_{2,2})} = a_{1,1}b_{1,2} + a_{1,2}b_{2,2} \\
{\color{Blue}x_{3,3}} &= {\color{Olive}(a_{3,1}, a_{3,2})} \cdot {\color{Green}(b_{1,3}, b_{2,3})} = a_{3,1}b_{1,3} + a_{3,2}b_{2,3}
\end{align}</math>

Окрім загально відомого, існують і інші види множення матриць. Ключовими особливостями будь-якого матричного множення є: кількість рядків і стовпців, в початкових матрицях, і правило, як елементи матриць утворюють нову матрицю.

== Визначення ==
[[Файл:Matrix multiplication qtl1_mnp.svg|thumb|Сумісність матриць для множення<br/><math>R^{m \times n} \times R^{n \times p} \to R^{m \times p}</math>]]
Нехай дано дві прямокутні матриці <math>\mathbf{A}</math> розміру <math>m \times n</math> та <math>\mathbf{B}</math> розміру <math>n \times p</math>:
:<math>
\mathbf{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},\;\;\;
\mathbf{B} =   
  \begin{bmatrix} 
    b_{11} & b_{12} & \cdots & b_{1p} \\
    b_{21} & b_{22} & \cdots & b_{2p} \\ 
    \vdots & \vdots & \ddots & \vdots \\ 
    b_{n1} & b_{n2} & \cdots & b_{np}
  \end{bmatrix}.
</math>
[[Файл:Matrix multiplication qtl2.svg|thumb|Множення <math>i</math>-го рядка на <math>k</math>-тий стовпець для обчислення елемента <math>c_{ik}</math>]]
Тоді матриця <math>\mathbf{C}</math> розмірністю <math>m \times p</math> називається їх ''добутком'':
: <math>
\mathbf{C} = 
  \begin{bmatrix} 
    c_{11} & c_{12} & \cdots & c_{1p} \\
    c_{21} & c_{22} & \cdots & c_{2p} \\ 
    \vdots & \vdots & \ddots & \vdots \\ 
    c_{m1} & c_{m2} & \cdots & c_{mp}
  \end{bmatrix},
</math>
де:
: <math> c_{ik} = \sum_{j=1}^n a_{ij}b_{jk} \;\;\; \left(i=1, 2, \ldots m;\; k=1, 2, \ldots p \right).</math>

Операція множення двох матриць здійсненна тільки в тому випадку, якщо число стовпців в першому співмножнику дорівнює числу рядків у другому; в цьому випадку говорять, що форма матриць ''узгоджена''. Зокрема, множення завжди здійснимо, якщо обидва множники&nbsp;— [[Квадратна матриця|квадратні матриці]] одного і того ж порядку.

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

== Приклад ==
[[Файл:Matrix multiplication qtl4.svg|thumb|Множення рядка на стовпець]]
[[Файл:Matrix multiplication qtl3.svg|thumb|Множення стовпця на рядок]]
'''Добуток матриць''' ''AB'' '''складається з усіх можливих комбінацій [[Скалярний добуток|скалярних добутків]] вектор-рядків матриці''' ''A'' і '''вектор-стовпців матриці''' ''B''. Елемент матриці ''AB'' з індексами ''i, j'' є скалярним добутком ''i''-го вектор-рядка матриці ''A'' і ''j''-го вектор-стовпця матриці ''B''.

У загальному випадку, добуток матриць не є комутативною операцією. Приміром:
:<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>

Перша координата в позначенні матриці позначає рядок, друга координата&nbsp;— стовпець; цей порядок використовують як при індексації, так і при позначенні розміру. Елемент <math>x_{{\color{Blue}i}{\color{Red}j}}</math> на перетині рядка <math>i</math> та стовпця <math>j</math> результуючої матриці є скалярним добутком <math>i</math>-го рядка першої матриці і <math>j</math>-го стовпця другої матриці. Це пояснює чому ширина і висота множимих матриць повинні збігатися: інакше скалярний добуток не визначено.

== Мотивація ==
[[Файл:Matrix multiplication qtl5.svg|thumb|Множення матриці на стовпець — це [[лінійна комбінація]] стовпців матриці]]
[[Файл:Matrix multiplication qtl7.svg|thumb|Множення рядка на матрицю — це [[лінійна комбінація]] рядків матриці]]
Описане правило матричного множення прозоріше всього мотивується, виходячи з множення вектора на матрицю.

Останнє звичайно вводиться виходячи з того, що при розкладанні векторів по [[Базис (математика)|базису]] дію (кожного) лінійного оператора ''A'' дає вираз компонент вектора '''v'''' = ''A'''''v''':
: <math>v'_i = \sum\limits_j A_{ij} v_j.</math>
Тобто лінійний оператор виявляється представлений матрицею, вектори&nbsp;— векторами-стовпцями, а дія оператора на вектор&nbsp;— матричним множенням вектора-стовпця зліва на матрицю оператора (це окремий випадок матричного множення, коли одна з матриць&nbsp;— вектор-стовпець&nbsp;— має розмір 1х''n'').

(Так само перехід до будь-якого нового базису при зміні координат представляється повністю аналогічним виразом, тільки <math>v'_i</math> в цьому випадку вже не компоненти нового вектора в старому базисі, а компоненти старого вектора в новому базисі; при цьому <math>A_{ij}</math>&nbsp;— елементи матриці переходу до нового базису).

Розглянувши послідовну дію на вектор двох операторів: спочатку ''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>&nbsp;— [[Квадратна матриця|квадратні матриці]] одного і того ж порядку, то добуток матриць має ще ряд властивостей.

Множення матриць в загальному випадку є [[Комутативність|некомутативним]]:
: <math>\mathbf{AB} \ne \mathbf{BA}.</math>

Якщо <math>\mathbf{AB} = \mathbf{BA}</math>, то матриці <math>\mathbf{A}</math> і <math>\mathbf{B}</math> називаються [[Матриця перестановки|перестановочними]] або комутуючими між собою.

Найпростіші приклади комутуючих матриць:

* будь-яка квадратна матриця&nbsp;— з самою собою: <math>\mathbf{AA} = \mathbf{AA} = \mathbf{A^2}</math> (зведення матриці в квадрат);
* будь-яка квадратна матриця&nbsp;— з одиничною матрицею того ж порядку: <math>\mathbf{AE} = \mathbf{EA} = \mathbf{A}</math>;
* будь-яка квадратна матриця&nbsp;— з нульовою матрицею того ж порядку: <math>\mathbf{A0} = \mathbf{0A} = \mathbf{0}</math>;
* будь-яка невироджена квадратна матриця&nbsp;— зі своєю зворотною матрицею: <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>

Ранг добутку не перевищує рангу кожного з множників
:<math>\operatorname{rank}(\mathbf{AB}) \le\min(\operatorname{rank}\ \mathbf{A}, \operatorname{rank}\ \mathbf{B}).</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>&nbsp;— [[алгебраїчне доповнення]] елементу <math>a_{ik}</math> у визначнику <math>\det \left [ a_{ik} \right ].</math>

== Алгоритми швидкого перемноження матриць ==
{{Докладніше|Алгоритм перемножування матриць}}

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

* '''[[Алгоритм Штрассена]]''' (1969): Перший алгоритм швидкого множення великих матриць був розроблений [[Фолькер Штрассен|Фолькером Штрассеном]]<ref>Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354–356, 1969</ref> в 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> операцій.
* '''Подальші поліпшення показника ступеня ω для швидкості матричного множення'''
[[Файл:Обмеження омеги перемножування матриць за часом.svg|thumb|400px|right|Хронологія поліпшення оцінок показника ступеня ω для швидкості матричного множення.]]
: Надалі оцінки швидкості множення великих матриць багаторазово поліпшувалися. Однак ці алгоритми носили теоретичний, в основному наближений характер. В силу нестійкості алгоритмів наближеного множення в даний час вони не використовуються на практиці.
:* '''Алгоритм Пана (1978)'''
:: У 1978 Пан<ref>Pan V. Ya, Strassen's algorithm is not optimal&nbsp;— trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations.&nbsp;— 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.&nbsp;— <math>O( n^{2.7799} )</math> complexity for approximate matrix multiplication.&nbsp;— Inform. Process. Lett., 1979</ref> розробила алгоритм множення матриць з використанням тензорів. Його складність становить '''Θ(n<sup>2.7799</sup>)'''.
:* '''Алгоритми Шенхаге (1981)'''
:: У 1981 Шенхаге<ref>Schonhage A. Partial and total matrix multiplication.&nbsp;— 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>)''', а Пан&nbsp;— до '''Θ(n<sup>2.5161</sup>)'''.
* '''[[Алгоритм Копперсміта-Вінограда]]''' (1990)
: У 1990 [[Дон Копперсміт|Копперсміт]] і {{Не перекладено|Шмуель Віноград|Віноград||Shmuel Winograd}}<ref>Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. ''Journal of Symbolic Computation'', 9:251-280, 1990.</ref> опублікували алгоритм, який в модифікації Вильямс Василевської<ref>Williams, Virginia (2011), [http://theory.stanford.edu/~virgi/matrixmult-f.pdf Multiplying matices in O(n<sup>2.3727</sup> time] {{Webarchive|url=https://web.archive.org/web/20141026144011/http://theory.stanford.edu/~virgi/matrixmult-f.pdf |date=26 жовтня 2014 }}</ref> 2011 року перемножує матриці зі швидкістю '''O(n<sup>2.3727</sup>)'''. Цей алгоритм використовує ідеї, схожі з алгоритмом Штрассена. На сьогоднішній день модифікації алгоритму Копперсміта-Винограда є найбільш асимптотично швидкими. Але той факт, що отримані поліпшення нікчемні, дозволяє говорити про існування «бар'єру Копперсміта-Винограда» в [[Обчислювальна складність|асимптотичних оцінках]] швидкості алгоритмів. Алгоритм Копперсміта-Винограда ефективний тільки на матрицях астрономічного розміру і на практиці застосовуватися не може.
* '''Зв'язок з теорією груп (2003)'''
: У 2003 Кох та ін. розглянули в своїх роботах<ref>{{Cite web |url=http://www.cs.caltech.edu/~umans/papers/CKSU05.pdf |title=Group-theoretic Algorithms for Matrix Multiplication |accessdate=26 жовтня 2014 |archive-date=6 серпня 2011 |archive-url=https://web.archive.org/web/20110806121526/http://www.cs.caltech.edu/~umans/papers/CKSU05.pdf }}</ref> алгоритми Штрассена і Копперсміта-Винограда в контексті теорії груп. Вони показали, що гіпотеза Штрассена справедлива, якщо виконується одна з гіпотез теорії груп<ref>{{Cite web |url=http://www.siam.org/pdf/news/174.pdf |title=Toward an Optimal Algorithm for Matrix Multiplication |accessdate=26 жовтня 2014 |archiveurl=https://web.archive.org/web/20100331095603/http://www.siam.org/pdf/news/174.pdf |archivedate=31 березня 2010 |deadurl=yes }}</ref>.

== Інші види множення матриць ==
* [[Добуток Адамара]]
* [[Добуток Кронекера]]
* [[Добуток Хатрі-Рао]]
* [[Торцевий добуток]]

== Див. також ==
* [[Скелетний розклад матриці]] — розклад на 2 прямокутні множники мінімального рангу.
* [[Розклад матриці]] — представлення у вигляді добутку 2 чи 3 матриць більш простої структури.

== Джерела ==
* {{Гантмахер.Теорія матриць}}
* {{Ланкастер.Теорія матриць}}
* {{Хорн.Джонсон.Матричний аналіз}}
* {{Golub.Loan.Matrix Computations}}
* {{Корн.Корн.Справочник}}

== Примітки ==
{{reflist|2}}

== Посилання ==
* [https://ua.onlinemschool.com/math/assistance/matrix/ Матричний калькулятор]

{{Числова лінійна алгебра}}

[[Категорія:Теорія матриць]]
[[Категорія:Білінійні оператори]]
[[Категорія:Множення|Матриць]]
[[Категорія:Числова лінійна алгебра]]