Множанне матрыц

right
Мно́жанне ма́трыц — адна з асноўных аперацый над матрыцамі. Матрыца, атрыманая ў выніку аперацыі множання, называецца здабы́ткам ма́трыц. Элементы новай матрыцы атрымліваюцца з элементаў старых матрыц у адпаведнасці з правіламі, праілюстраванымі ніжэй.

Матрыцы  і  могуць быць памножаны, калі яны сумяшчальныя ў тым сэнсе, што колькасць слупкоў матрыцы  роўная колькасці радкоў .

Матрыцы маюць шматлікія алгебраічныя ўласцівасці множання, уласцівыя звычайным лікам, за выключэннем камутатыўнасці.

Для квадратных матрыц, акрамя множання, можа быць уведзена аперацыя ўзвядзення матрыцы ў ступень і адваротная матрыца.

Паколькі матрыцы выкарыстоўваюцца для апісання, у прыватнасці, пераўтварэнняў матэматычных прастораў (паварот, адлюстраванне, расцяжэнне і іншыя), здабытак матрыц будзе апісваць кампазіцыю пераўтварэнняў.

 Азначэнне 
Няхай дадзены дзве прамавугольныя матрыцы  і  памеру  і  адпаведна:

Тады матрыца  памеру :

у якой:

называецца іх здабыткам.

Аперацыя множання двух матрыц магчымая толькі ў тым выпадку, калі колькасць слупкоў у першым множніку роўная колькасці радкоў у другім; у гэтым выпадку кажуць, што матрыцы ўзгодненыя. У прыватнасці, множанне заўсёды магчыма, калі абодва множнікі — квадратныя матрыцы аднаго і таго ж парадку.

Такім чынам, з існавання здабытку  зусім не вынікае існаванне здабытку .

 Ілюстрацыя 
right
Здабытак матрыц AB складаецца з усіх магчымых камбінацый скалярных здабыткаў вектар-радкоў матрыцы A і вектар-слупкоў матрыцы B. Элемент матрыцы AB з індэксамі i, j ёсць скалярным здабыткам i-га вектар-радка матрыцы A і j-га вектар-слупка матрыцы B.

Ілюстрацыя справа дэманструе вылічэнне здабытку дзвюх матрыц A і B, яна паказвае, як кожнае перасячэнне ў здабытку матрыц адпавядае радкам матрыцы A і слупкам матрыцы B. Памер выніковай матрыцы заўсёды максімальна магчымы, гэта значыць для кожнага радка матрыцы A і слупка матрыцы B заўсёды ёсць адпаведнае перасячэнне ў здабытку матрыцы.

Значэнні на перасячэннях, пазначаных кружочкамі, будуць:

У агульным выпадку, здабытак матрыц не з’яўляецца камутатыўнай аперацыяй. Напрыклад:


Элемент  здабытку матрыц, прыведзеных вышэй, вылічваецца наступным чынам


Першая каардыната ў абазначэнні матрыцы абазначае радок, другая каардыната — слупок; гэты парадак выкарыстоўваецца як пры індэксацыі, так і пры абазначэнні памеру. Элемент  на перасячэнні радка  і слупка  выніковай матрыцы з’яўляецца скалярным здабыткам -га радка першай матрыцы і -га слупка другой матрыцы.
Гэта тлумачыць чаму шырыня і вышыня множаных матрыц павінны супадаць: у адваротным выпадку скалярны здабытак не вызначаны.

 Абмеркаванне 
Убачыць прычыны апісанага правіла матрычнага множання прасцей за ўсё, разгледзеўшы множанне вектара на матрыцу.

Апошняе натуральна ўводзіцца зыходзячы з таго, што пры раскладзе вектараў па базісе дзеяння (любога) лінейнага аператара A дае выражэнне кампанентаў вектара v' = Av:


То бок лінейны аператар аказваецца прадстаўлены матрыцай, вектары — вектарамі-слупкамі, а дзеянне аператара на вектар — матрычным множаннем вектара-слупка злева на матрыцу аператара (гэта прыватны выпадак матрычнага множання, калі адна з матрыц — вектар-слупок — мае памер ).

(Пераход да любога новага базіса пры змене каардынат прадстаўляецца цалкам аналагічным выразам, толькі  у гэтым выпадку ўжо не кампаненты новага вектара ў старым базісе, а кампаненты старога вектара ў новым базісе; пры гэтым  — элементы матрыцы пераходу да новага базіса).

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


адкуль відаць, што кампазіцыі BA дзеяння лінейных аператараў A і B (або аналагічнай кампазіцыі пераўтварэнняў базіса) адпавядае матрыца, вылічаная па правілу здабытку адпаведных матрыц:



Вызначаны такім чынам здабытак матрыц аказваецца цалкам натуральным і відавочна карысным (дае просты і універсальны спосаб вылічэння кампазіцый адвольнай колькасці лінейных пераўтварэнняў).

 Уласцівасці 
Злучальная ўласцівасць, асацыятыўнасць:



Размеркавальная ўласцівасць, дыстрыбутыўнасць адносна складання:

 .

Здабытак матрыцы на адзінкавую матрыцу  адпаведнага парадку роўны самой матрыцы:



Здабытак матрыцы на нулявую матрыцу  адпаведнага памеру роўны нулявой матрыцы:



Калі  і  — квадратныя матрыцы аднаго і таго ж парадку, то здабытак матрыц валодае яшчэ шэрагам уласцівасцей.

Множанне матрыц у агульным выпадку некамутатыўна:


Калі , то матрыцы  і  называюцца камутавальнымі паміж сабой.

Прасцейшыя прыклады камутавальных матрыц:
 любая квадратная матрыца — з самой сабой:  (узвядзенне матрыцы ў квадрат);
 любая квадратная матрыца — з адзінкавай матрыцай таго ж парадку: ;
 любая квадратная матрыца — з нулявой матрыцай таго ж парадку: ;
 любая нявыраджаная квадратная матрыца — са сваёй адваротнай матрыцай: .

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



 Адваротная матрыца 

Квадратная матрыца  называецца неасаблівай (нявыраджанай), калі яна мае адзіную адваротную матрыцу  такую, што выконваецца ўмова:

У адваротным выпадку матрыца  называецца асаблівай (выраджанай).

Матрыца  парадку  з’яўляецца нявыраджанай тады і толькі тады, калі  у гэтым выпадку  ёсць квадратная матрыца таго ж парадку 

дзе  — алгебраічнае дапаўненне элемента  у вызначніку 

 Алгарытмы хуткага перамнажэння матрыц 
Складанасць вылічэння здабытку матрыц па азначэнні складае , аднак існуюць больш эфектыўныя алгарытмыКибернетический сборник. Новая серия. Вып. 25. Сб. статей 1983—1985 гг.: Пер. с англ. — М.: Мир, 1988 — В. Б. Алекссев. Сложность умножения матриц. Обзор., якія прымяняюцца для вялікіх матрыц. Пытанне пра мяжу хуткасці множання вялікіх матрыц, гэтак жа як і пытанне пра стварэнне найбольш хуткіх і ўстойлівых практычных алгарытмаў множання вялікіх матрыц застаецца адной з нераскрытых праблем лінейнай алгебры.

 Алгарытм Штрассена (1969)
 Першы алгарытм хуткага множання вялікіх матрыц быў распрацаваны Фолькерам Штрасенам у 1969 годзе. У аснове алгарытму ляжыць рэкурсіўная разбіўка матрыц на блокі 2×2. Штрасен даказаў, што матрыцы 2×2 можна некамутатыўна перамножыць з дапамогай сямі множанняў, таму на кожным этапе рэкурсіі выконваецца сем множанняў замест васьмі. У выніку асімптатычная складанасць гэтага алгарытму складае . Недахопам гэтага метаду з’яўляецца большая складанасць праграмавання ў параўнанні са стандартным алгарытмам, слабая лікавая ўстойлівасць і большы аб’ём выкарыстанай памяці. Распрацаваны шэраг алгарытмаў на аснове метаду Штрасена, якія паляпшаюць лікавую ўстойлівасць, хуткасць па канстанце і іншыя яго характарыстыкі. Тым не менш, з-за прастаты алгарытм Штрасена застаецца адным з практычных алгарытмаў множання вялікіх матрыц. Штрасен таксама вылучыў наступную гіпотэзу Штрасена: для якой заўгодна малой  існуе алгарытм, пры дастаткова вялікіх натуральных n гарантуе перамнажэнне дзвюх матрыц памеру  за  аперацый.
 Далейшыя паляпшэнні паказчыка ступені ω для хуткасці матрычнага множання
 У далейшым ацэнкі хуткасці множання вялікіх матрыц шматразова паляпшаліся. Аднак гэтыя алгарытмы насілі тэарэтычны, галоўным чынам набліжаны характар. З-за неўстойлівасці алгарытмаў набліжанага множання ў цяперашні час яны не выкарыстоўваюцца на практыцы.
 Алгарытм Пана (1978)
 У 1978 годзе Пан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 прапанаваў свой метад множання матрыц, складанасць якога склала Θ(n2.78041).
 Алгарытм Біні (1979)
 У 1979 годзе група італьянскіх навукоўцаў на чале з БініBini D., Capovani M., Lotti G., Romani F. —  complexity for approximate matrix multiplication. — Inform. Process. Lett., 1979 распрацавала алгарытм множання матрыц з выкарыстаннем тэнзараў. Яго складанасць складае Θ(n2.7799).
 Алгарытмы Шонхаге (1981)
 У 1981 годзе ШонхагеSchonhage A. Partial and total matrix multiplication. — SIAM J. Comput., 1981 прадставіў метад, які працуе з хуткасцю Θ(n2.695). Ацэнка атрымана з дапамогай падыходу, названага частковым матрычным множаннем. Пазней яму ўдалося атрымаць ацэнку Θ(n2.6087).
 Затым Шонхаге на базе метаду прамых сум атрымаў ацэнку складанасці Θ(n2.548). Рамані змог панізіць ацэнку да Θ(n2.5166), а Пан — да Θ(n2.5161).
 Алгарытм Каперсміта — Вінаграда (1990)
 У 1990 годзе Копперсміт і ВінаградDon Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990. апублікавалі алгарытм, асімптатычная складанасць якога складала O(n2.3755). Гэты алгарытм выкарыстоўвае ідэі, падобныя з алгарытмам Штрасена. На сённяшні дзень мадыфікацыі алгарытму Каперсміта—Вінаграда з’яўляюцца найбольш асімптатычна хуткімі. У апошняй мадыфікацыі (2024) складанасць алгарытму складае O(n2.371552). Вядома, што шырокі клас мадыфікацый гэтага алгарытму ў прынцыпе не можа дасягнуць складанасці лепшай, чым O(n2.3078). Алгарытм Копперсміта—Вінаграда эфектыўны толькі на матрыцах астранамічнага памеру і на практыцы прымяняцца не можа.
 Сувязь з тэорыяй груп (2003)
 У 2003 годзе Кох і інш. разгледзелі ў сваіх працах алгарытмы Штрасена і Каперсміта-Вінаграда ў кантэксце тэорыі груп. Яны паказалі, што гіпотэза Штрасена справядлівая (г. зн. мінімальная складанасць абмежаваная  для любога ), калі выконваецца адна з гіпотэз тэорыі груп.

 Ступені матрыц 
Квадратныя матрыцы можна шмат разоў множыць самі на сябе гэтак жа, як звычайныя лікі, паколькі ў іх аднолькавая колькасць радкоў і слупкоў. Такое паслядоўнае множанне можна назваць узвядзеннем матрыцы ў ступень — гэта будзе прыватным выпадкам звычайнага множання некалькіх матрыц. У прамавугольных матрыц колькасць радкоў і слупкоў розная, таму іх ніколі нельга ўзводзіць у ступень.

Матрыца  памеру , узведзеная ў ступень, вызначаецца формулай

і валодае наступнымі ўласцівасцямі ( — некаторы скаляр):

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



дзе E — адзінкавая матрыца. Гэта аналаг таго факту, што нулявая ступень любога ліку роўная адзінцы.

Множанне на скаляр:



Вызначнік:



Найбольш просты спосаб вылічэння ступені матрыцы — гэта множыць  разоў матрыцу  на вынік папярэдняга множання, пачынаючы з адзінкавай матрыцы, як гэта часта робяць для скаляраў. Для дыяганалізуемых матрыц існуе лепшы метад, заснаваны на выкарыстанні спектральнага раскладанне матрыцы . Яшчэ адзін метад, заснаваны на тэарэме Гамільтана — Кэлі, будуе больш эфектыўнае выражэнне для , у якім у патрабаваную ступень узводзіцца скаляр, а не ўся матрыца.

Асобны выпадак складаюць дыяганальныя матрыцы. Паколькі здабытак дыяганальных матрыц зводзіцца да множання адпаведных дыяганальных элементаў, то -ая ступень дыяганальнай матрыцы  складаецца з элементаў, узведзеных у патрабаваную ступень:


Такім чынам, узвесці дыяганальную матрыцу ў ступень нескладана. Пры ўзвядзенні адвольнай матрыцы (не абавязкова дыяганальнай) у ступень часта аказваецца карысным выкарыстоўваць спачатку ўласцівасці дыяганалізуемых матрыц.

Выкарыстоўваючы множанне матрыц і ўзвядзенне матрыц у ступень, можна вызначыць іншыя аперацыі над матрыцамі. Напрыклад, матрычная экспанента можа быць вызначана праз ступеневы рад, матрычны лагарыфм — як адваротная да матрычнай экспаненты функцыя і гэтак далей.

 Гл. таксама 
 Здабытак Кронекера
 Здабытак Адамара

 Літаратура 


 Крыніцы 

Катэгорыя:Алгарытмы множання матрыц
Катэгорыя:Матрыцы
Катэгорыя:Лічбавыя метады лінейнай алгебры
Катэгорыя:Білінеарныя аператары