Перемноження матриць

Множе́ння ма́триць — це бінарна операція, яка використовуючи дві матриці, утворює нову матрицю, яка називається доб́утком ма́триць. Дійсні або комплексні числа множаться відповідно до правил (елементарної арифметики).

Схема праворуч демонструє обчислення добутку двох матриць A і B. Вона показує як перетини в добутку матриць відповідають рядкам матриці A і стовпцям матриці B. Значення на перетинах відмічених кружеяками будуть:

${\displaystyle {\begin{aligned}{\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{aligned}}}$

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

Визначення

Сумісність матриць для множення
${\displaystyle R^{m\times n}\times R^{n\times p}\to R^{m\times p}}$

Нехай дано дві прямокутні матриці ${\displaystyle \mathbf {A} }$ розміру ${\displaystyle m\times n}$ та ${\displaystyle \mathbf {B} }$ розміру ${\displaystyle n\times p}$:

${\displaystyle \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}}.}$

Множення ${\displaystyle i}$-го рядка на ${\displaystyle k}$-тий стовпець для обчислення елемента ${\displaystyle c_{ik}}$

Тоді матриця ${\displaystyle \mathbf {C} }$ розмірністю ${\displaystyle m\times p}$ називається їх добутком:

${\displaystyle \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}},}$

де:

${\displaystyle c_{ik}=\sum _{j=1}^{n}a_{ij}b_{jk}\;\;\;\left(i=1,2,\ldots m;\;k=1,2,\ldots p\right).}$

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

Слід зауважити, що з існування добутку ${\displaystyle AB}$ зовсім не випливає існування добутку ${\displaystyle BA.}$

Приклад

Множення рядка на стовпець

Множення стовпця на рядок

Добуток матриць AB складається з усіх можливих комбінацій скалярних добутків вектор-рядків матриці A і вектор-стовпців матриці B. Елемент матриці AB з індексами i, j є скалярним добутком i-го вектор-рядка матриці A і j-го вектор-стовпця матриці B.

У загальному випадку, добуток матриць не є комутативною операцією. Приміром:

${\displaystyle {\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}}}}$

Елемент ${\displaystyle x_{3,4}}$ добутку матриць приведених вище, обчислюється таким чином

${\displaystyle 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}}$

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

Мотивація

Множення матриці на стовпець

Множення рядка на матрицю

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

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

${\displaystyle v'_{i}=\sum \limits _{j}A_{ij}v_{j}.}$

Тобто лінійний оператор виявляється представлений матрицею, вектори — векторами-стовпцями, а дія оператора на вектор — матричним множенням вектора-стовпця зліва на матрицю оператора (це окремий випадок матричного множення, коли одна з матриць — вектор-стовпець — має розмір 1хn).

(Так само перехід до будь-якого нового базису при зміні координат представляється повністю аналогічним виразом, тільки ${\displaystyle v'_{i}}$ в цьому випадку вже не компоненти нового вектора в старому базисі, а компоненти старого вектора в новому базисі; при цьому ${\displaystyle A_{ij}}$ — елементи матриці переходу до нового базису).

Розглянувши послідовну дію на вектор двох операторів: спочатку A, а потім B (або перетворення базису A, а потім перетворення базису B), двічі застосувавши формулу, отримуємо:

${\displaystyle 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 (або аналогічної композиції перетворень базису) відповідає матриця, що обчислюється за правилом добутку відповідних матриць:

${\displaystyle (BA)_{ik}=\sum \limits _{j}B_{ij}A_{jk}.}$

Визначений таким чином добуток матриць виявляється абсолютно звичайним і очевидно корисним (дає простий і універсальний спосіб обчислення композицій довільної кількості лінійних перетворень).

Властивості

Сполучна властивість, асоціативність:

${\displaystyle \mathbf {A} (\mathbf {BC} )=(\mathbf {AB} )\mathbf {C} ;}$

${\displaystyle \alpha (\mathbf {AB} )=(\alpha \mathbf {A} )\mathbf {B} =\mathbf {A} (\alpha \mathbf {B} ).}$

Розподільна властивість, дистрибутивність щодо додавання:

${\displaystyle \mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ;}$

${\displaystyle (\mathbf {A} +\mathbf {B} )\mathbf {C} =\mathbf {AC} +\mathbf {BC} .}$.

Добуток матриці на одиничну матрицю ${\displaystyle \mathbf {E} }$ того ж порядку дорівнює самій матриці:

${\displaystyle \mathbf {EA} =\mathbf {A} ;}$

${\displaystyle \mathbf {AE} =\mathbf {A} .}$

Добуток матриці на нульову матрицю ${\displaystyle \mathbf {0} }$ тієї ж розмірності дорівнює нульовий матриці:

${\displaystyle \mathbf {0A} =\mathbf {0} ;}$

${\displaystyle \mathbf {A0} =\mathbf {0} .}$

Якщо ${\displaystyle \mathbf {A} }$ і ${\displaystyle \mathbf {B} }$ — квадратні матриці одного і того ж порядку, то добуток матриць має ще ряд властивостей.

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

${\displaystyle \mathbf {AB} \neq \mathbf {BA} .}$

Якщо ${\displaystyle \mathbf {AB} =\mathbf {BA} }$, то матриці ${\displaystyle \mathbf {A} }$ і ${\displaystyle \mathbf {B} }$ називаються перестановочними або комутуючими між собою.

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

• будь-яка квадратна матриця — з самою собою: ${\displaystyle \mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}} }$ (зведення матриці в квадрат);
• будь-яка квадратна матриця — з одиничною матрицею того ж порядку: ${\displaystyle \mathbf {AE} =\mathbf {EA} =\mathbf {A} }$;
• будь-яка квадратна матриця — з нульовою матрицею того ж порядку: ${\displaystyle \mathbf {A0} =\mathbf {0A} =\mathbf {0} }$;
• будь-яка невироджена квадратна матриця — зі своєю зворотною матрицею: ${\displaystyle \mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E} }$.

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

${\displaystyle \det(\mathbf {AB} )=\det(\mathbf {BA} )=\det \mathbf {A} \cdot \det \mathbf {B} ;}$

${\displaystyle {\mbox{tr}}(\mathbf {AB} )={\mbox{tr}}(\mathbf {BA} ).}$

Обернена матриця

Докладніше: Обернена матриця

Квадратна матриця ${\displaystyle A}$ називається неособливою(невиродженою), якщо вона має єдину обернену матрицю ${\displaystyle A^{-1}}$ таку, що виконується умова:

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

Інакше матриця ${\displaystyle A}$ називається особливою (виродженою).

Матриця ${\displaystyle A=\left[a_{ik}\right]}$ порядку ${\displaystyle n}$ є невиродженою в тому і лише в тому випадку, якщо ${\displaystyle \det A=\det \left[a_{ik}\right]\neq 0;}$ в цьому випадку ${\displaystyle A^{-1}}$ є квадратна матриця того ж порядку ${\displaystyle n:}$

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

де ${\displaystyle A_{ik}}$ — алгебраїчне доповнення елементу ${\displaystyle a_{ik}}$ у визначнику ${\displaystyle \det \left[a_{ik}\right].}$

Алгоритми швидкого перемноження матриць

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

Складність обчислення добутку матриць за визначенням становить ${\displaystyle \ O(n^{3})}$, однак існують більш ефективні алгоритми, що застосовуються для великих матриць. Питання про граничну швидкість множення великих матриць, також як і питання про побудову найбільш швидких і стійких практичних алгоритмів множення великих матриць залишається однією з невирішених проблем лінійної алгебри.

• Алгоритм Штрассена (1969): Перший алгоритм швидкого множення великих матриць був розроблений Фолькером Штрассеном в 1969. В основі алгоритму лежить рекурсивне розбиття матриць на блоки 2Х2. Штрассен довів, що матриці 2Х2 можна некомутативно перемножити за допомогою семи множень, тому на кожному етапі рекурсії виконується сім множень замість восьми. В результаті асимптотична складність цього алгоритму складає ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.81})}$. Недоліком даного методу є велика складність програмування в порівнянні зі стандартним алгоритмом, слабка чисельна стійкість і більший обсяг використовуваної пам'яті. Розроблено ряд алгоритмів на основі методу Штрассена, які покращують чисельну стійкість, швидкість по константі і інші його характеристики. Проте, в силу простоти алгоритм Штрассена залишається одним з практичних алгоритмів множення великих матриць. Штрассен також висунув наступну гіпотезу Штрассена: для як завгодно малого ${\displaystyle \varepsilon >0}$ існує алгоритм, що при досить великих натуральних n гарантує перемножування двох матриць розміру ${\displaystyle n\times n}$ за ${\displaystyle O(n^{2+\varepsilon })}$ операцій.
• Подальші поліпшення показника ступеня ω для швидкості матричного множення

Хронологія поліпшення оцінок показника ступеня ω для швидкості матричного множення.

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

• Алгоритм Пана (1978)

У 1978 Пан запропонував свій метод множення матриць, складність якого склала Θ(n^2.78041).

• Алгоритм Біні (1979)

У 1979 група італійських учених на чолі з Біні розробила алгоритм множення матриць з використанням тензорів. Його складність становить Θ(n^2.7799).

• Алгоритми Шенхаге (1981)

У 1981 Шенхаге представив метод, який працює зі швидкістю Θ(n^2.695). Оцінка отримана за допомогою підходу, названого частковим матричним множенням. Пізніше йому вдалося отримати оцінку Θ(n^2.6087).

Потім Шенхаге на базі методу прямих сум отримав оцінку складності Θ(n^2.548). Романі зумів понизити оцінку до Θ(n^2.5166), а Пан — до Θ(n^2.5161).

• Алгоритм Копперсміта-Вінограда (1990)

У 1990 Копперсміт і ^[en] опублікували алгоритм, який в модифікації Вильямс Василевської 2011 року перемножує матриці зі швидкістю O(n^2.3727). Цей алгоритм використовує ідеї, схожі з алгоритмом Штрассена. На сьогоднішній день модифікації алгоритму Копперсміта-Винограда є найбільш асимптотично швидкими. Але той факт, що отримані поліпшення нікчемні, дозволяє говорити про існування «бар'єру Копперсміта-Винограда» в асимптотичних оцінках швидкості алгоритмів. Алгоритм Копперсміта-Винограда ефективний тільки на матрицях астрономічного розміру і на практиці застосовуватися не може.

• Зв'язок з теорією груп (2003)

У 2003 Кох та ін. розглянули в своїх роботах алгоритми Штрассена і Копперсміта-Винограда в контексті теорії груп. Вони показали, що гіпотеза Штрассена справедлива, якщо виконується одна з гіпотез теорії груп.

Інші види множення матриць

• Добуток Адамара
• Добуток Кронекера
• Добуток Хатрі-Рао
• Торцевий добуток

Джерела

• Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — .(рос.)
• Теория матриц. — 2. — Москва : Наука, 1982. — 272 с.(рос.)
• , . Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)
• , Справочник по математике для научных работников и инженеров. — Москва : Наука, 1973. — 832 с.(рос.)

Примітки

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. — ${\displaystyle 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), Multiplying matices in O(n^2.3727 time [ 26 жовтня 2014 у Wayback Machine.]
8. (PDF). Архів оригіналу (PDF) за 6 серпня 2011. Процитовано 26 жовтня 2014.
9. (PDF). Архів оригіналу (PDF) за 31 березня 2010. Процитовано 26 жовтня 2014.

Посилання

• Матричний калькулятор