Matriisin kertolasku

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. elokuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Matriisin kertolasku on yksi matriisien perusoperaatioista . Kertolaskuoperaation tuloksena olevaa matriisia kutsutaan matriisituloksi . Uuden matriisin alkiot saadaan vanhojen matriisien alkioista alla kuvattujen sääntöjen mukaisesti .

Matriisit ja voidaan kertoa, jos ne ovat yhteensopivia siinä mielessä, että matriisin sarakkeiden lukumäärä on yhtä suuri kuin rivien lukumäärä . $A$ $B$ $A$ $B$

Matriiseilla on monia niitä algebrallisia kertolaskuominaisuuksia , jotka tavallisilla luvuilla on, lukuun ottamatta kommutatiivisuutta .

Neliömatriisien kohdalla kertomisen lisäksi voidaan ottaa käyttöön matriisin nostaminen potenssiin ja käänteismatriisi .

Kun matriiseja käytetään kuvaamaan erityisesti matemaattisten avaruuksien muunnoksia ( kierto , heijastus , venytys ja muut), matriisien tulo kuvaa muunnosten koostumusta .

Määritelmä

Olkoon kaksi suorakaiteen muotoista matriisia ja mittoja ja annettu vastaavasti: $A$ $B$ $l\times m$ $m\ kertaa n$

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

Sitten matriisi mitoineen : $C$ $l\times n$

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

jossa:

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

kutsutaan heidän tuotteekseen .

Kahden matriisin kertominen on mahdollista vain, jos sarakkeiden lukumäärä ensimmäisessä kertoimessa on yhtä suuri kuin toisen kertoimen rivien lukumäärä; tässä tapauksessa matriisien sanotaan olevan johdonmukaisia . Erityisesti kertominen on aina mahdollista, jos molemmat tekijät ovat samaa kertaluokkaa olevia neliömatriiseja .

Teoksen olemassaolo ei siis seuraa ollenkaan teoksen olemassaoloa. $AB$ $B.A.$

Kuva

Matriisitulo AB koostuu matriisin A rivivektorien ja matriisin B sarakevektorien sisätulojen kaikista mahdollisista yhdistelmistä . Matriisin AB alkio indekseillä i, j on matriisin A i :nnen rivivektorin ja matriisin B j :nnen sarakevektorin skalaaritulo .

Oikeanpuoleinen kuva esittää kahden matriisin A ja B tulon laskentaa , se näyttää kuinka kukin matriisitulon leikkauspiste vastaa matriisin A rivejä ja matriisin B sarakkeita . Tuloksena olevan matriisin koko on aina suurin mahdollinen, eli jokaiselle matriisin A riville ja matriisin B sarakkeelle on aina vastaava leikkauspiste matriisin tulossa.

Ympyröillä merkittyjen risteysten arvot ovat:

${\begin{align}{\color {Punainen}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{aligned}}$

Yleensä matriisitulo ei ole kommutoiva operaatio. Esimerkiksi:

{\overset {3\times 4{\text{ matrix))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot \\\väri {Sininen}1&\väri {Sininen}2&\väri {Sininen}3&\väri {Sininen}4\\\end{bmatrix}}}{\overset {4\times 5{\text{ matrix}}}{\begin {bmatrix}\cdot &\cdot &\cdot &\color {Punainen}a&\cdot \\\cdot &\cdot &\cdot &\color {Punainen}b&\cdot \\\cdot &\cdot &\cdot & \color {Punainen}c&\cdot \\\cdot &\cdot &\cdot &\color {Red}d&\cdot \\\end{bmatrix}}}={\overset {3\times 5{\text{ matriisi ))}{\begin{bmatrix}\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &\cdot &\cdot \\\cdot &\cdot &\cdot &x_ {3,4}&\cdot \\\end{bmatrix}}}

Yllä olevien matriisien tulon elementti lasketaan seuraavasti $x_{{3,4}}$

x_{3,4}=({\väri {sininen}1},{\väri {sininen}2},{\väri {sininen}3},{\väri {sininen}4})\cdot ({\väri {Punainen}a},{\väri {Punainen}b},{\väri {Punainen}c},{\väri {Punainen}d})={\väri {Sininen}1}\cpiste {\väri {Punainen} a}+{\väri {sininen}2}\cpiste {\väri {punainen}b}+{\väri {sininen}3}\cpiste {\väri {punainen}c}+{\väri {sininen}4}\ cdot {\väri {punainen}d}

Ensimmäinen koordinaatti matriisimerkinnässä tarkoittaa riviä, toinen koordinaatti tarkoittaa saraketta; tätä järjestystä käytetään sekä indeksoinnissa että koon määrittämisessä. Tuloksena olevan matriisin rivin ja sarakkeen leikkauskohdassa oleva elementti on ensimmäisen matriisin i:nnen rivin ja toisen matriisin i:nnen sarakkeen skalaaritulo . Tämä selittää, miksi kerrottujen matriisien leveyden ja korkeuden on vastattava: muuten pistetulo on määrittelemätön. $x_{{\väri {sininen}i}{\väri {punainen}j))$ $i$ $j$ $i$ $j$

Keskustelu

Kuvatun matriisin kertolaskusäännön syyt on helpoin nähdä ottamalla huomioon vektorin kertominen matriisilla.

Jälkimmäinen on luonnollisesti otettu käyttöön perustuen siihen, että kun vektoreita hajotetaan kannassa, minkä tahansa lineaarisen operaattorin A toiminta antaa lausekkeen vektorin v' = A v komponenteille :

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

Toisin sanoen lineaarista operaattoria edustaa matriisi, vektorit sarakevektoreilla ja operaattorin toimintaa vektorilla matriisikertomalla vasemmalla olevan sarakevektorin operaattorimatriisilla (tämä on matriisin kertolasku erityinen tapaus, kun yhden matriisin, sarakevektorin, koko on ). ${\näyttötyyli n\kertaa 1}$

(Samoin siirtyminen mihin tahansa uuteen kantaan koordinaatteja vaihdettaessa esitetään täysin samankaltaisella lausekkeella, vain tässä tapauksessa se ei ole enää vanhan kannan uuden vektorin komponentit, vaan vanhan vektorin komponentit uudessa kannassa ; tässä tapauksessa uuteen kantaan siirtymämatriisin elementit ). $v'_{i}$ $A_{{ij}}$

Otettuaan huomioon peräkkäisen toiminnan kahden operaattorin vektorilla: ensin A ja sitten B (tai kannan A muunnos ja sitten kannan B muunnos ) soveltamalla kaavaamme kahdesti, saamme:

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

josta voidaan nähdä, että lineaaristen operaattorien A ja B toiminnan koostumus BA (tai vastaava kantamuunnosten koostumus) vastaa matriisia, joka on laskettu vastaavien matriisien tulosäännöllä :

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

Tällä tavalla määriteltyjen matriisien tulo osoittautuu melko luonnolliseksi ja ilmeisen hyödylliseksi (tarjoaa yksinkertaisen ja universaalin tavan laskea mielivaltaisen määrän lineaarisia muunnoksia).

Ominaisuudet

Assosiatiivisuus , assosiatiivisuus :

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

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

Jakeluominaisuus , distributiivisuus lisäyksen suhteen :

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

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

Matriisin ja sopivan kertaluvun identiteettimatriisin tulo on yhtä suuri kuin itse matriisi: $\mathbf {E}$

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

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

Matriisin ja sopivan mittaisen nollamatriisin tulo on yhtä suuri kuin nollamatriisi: $\mathbf {0}$

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

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

Jos ja ovat samaa kertaluokkaa olevia neliömatriiseja , niin matriisitulolla on useita muita ominaisuuksia. $\mathbf {A}$ $\mathbf {B}$

Matriisikertominen on yleensä ei- kommutatiivista :

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

Jos , Sitten matriisien ja sanotaan liikkuvan toistensa kanssa. $\mathbf {AB} =\mathbf {BA}$ $\mathbf {A}$ $\mathbf {B}$

Yksinkertaisimmat esimerkit työmatkamatriiseista:

mikä tahansa neliömatriisi - itsensä kanssa: (matriisin neliöinti); $\mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}}$
mikä tahansa neliömatriisi — jonka identiteettimatriisi on samaa järjestystä: ; $\mathbf {AE} =\mathbf {EA} =\mathbf {A}$
mikä tahansa neliömatriisi — jossa on samaa kertaluokkaa oleva nollamatriisi: ; $\mathbf {A0} =\mathbf {0A} =\mathbf {0}$
mikä tahansa ei-singulaarinen neliömatriisi — sen käänteismatriisi: . $\mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E}$

Tuloksen determinantti ja jälki eivät riipu matriisin kertolaskujärjestyksestä:

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

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

Käänteinen matriisi

Neliömatriisia kutsutaan ei- singulaariseksi ( ei- singulaariseksi ) , jos sillä on ainutlaatuinen käänteimatriisi siten, että seuraava ehto täyttyy: $A$ $A^{{-1}}$

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

Muuten matriisia kutsutaan erityiseksi ( degeneroituneeksi ) . $A$

Järjestysmatriisi ei ole rappeutunut silloin ja vain, jos tässä tapauksessa on samaa kertaluokkaa oleva neliömatriisi $A=\vasen[a_{ik}\oikea]$ $n$ $\det A=\det \left[a_{ik}\right]\neq 0;$ $A^{{-1}}$ $n:$

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

missä on determinantin elementin algebrallinen komplementti $A_{{ik}}$ $a_{{ik}}$ $\det\left[a_{ik}\right].$

Nopeat matriisin kertolaskualgoritmit

Matriisien tulon laskemisen monimutkaisuus määritelmän mukaan on , mutta on olemassa tehokkaampia algoritmeja [1] , joita käytetään suurille matriiseille. Kysymys suurten matriisien kertolaskunopeuden rajoittamisesta sekä kysymys nopeimpien ja vakaimpien käytännön algoritmien rakentamisesta suurten matriisien kertomiseen on edelleen yksi lineaarisen algebran ratkaisemattomista ongelmista . $\O(n^{3})$

Strassenin algoritmi (1969)

Ensimmäisen algoritmin suurten matriisien nopeaan kertomiseen kehitti Volker Strassen [2] vuonna 1969. Algoritmi perustuu matriisien rekursiiviseen osiointiin 2X2 -lohkoihin . Strassen osoitti, että 2X2 -matriisit voidaan kertoa ei-kommutatiivisesti seitsemällä kertolaskulla, joten jokaisessa rekursion vaiheessa suoritetaan seitsemän kertolaskua kahdeksan sijaan. Tämän seurauksena tämän algoritmin asymptoottinen monimutkaisuus on . Tämän menetelmän haittana on ohjelmoinnin monimutkaisuus verrattuna standardialgoritmiin, huono numeerinen vakaus ja suurempi käytetty muistimäärä. On kehitetty useita Strassen-menetelmään perustuvia algoritmeja, jotka parantavat numeerista vakautta, vakionopeutta ja muita ominaisuuksia. Siitä huolimatta Strassen-algoritmi on yksinkertaisuutensa vuoksi edelleen yksi käytännön algoritmeista suurten matriisien kertomiseen. Strassen esitti myös seuraavan Strassen -oletuksen : mielivaltaisen pienille , on olemassa algoritmi, joka riittävän suurille luonnollisille luvuille n takaa kahden koon matriisin kertomisen operaatioissa .

O(n^{\log _{2}7})\noin O(n^{2.81})

\varepsilon > 0

n\ kertaa n

O(n^{2+\varepsilon })

Muita parannuksia matriisin kertolaskunopeuden eksponenttiin ω

Jatkossa suurten matriisien kertolaskunopeuden arvioita parannettiin moninkertaisesti. Nämä algoritmit olivat kuitenkin teoreettisia, enimmäkseen likimääräisiä. Likimääräisten kertolaskualgoritmien epävakauden vuoksi niitä ei tällä hetkellä käytetä käytännössä.

Pan's Algorithm (1978)

Vuonna 1978 Pan [3] ehdotti omaa matriisin kertolaskumenetelmää, jonka monimutkaisuus oli Θ(n 2,78041 ) .

Beanie's Algorithm (1979)

Vuonna 1979 Binin [4] johtama italialaisten tiedemiesten ryhmä kehitti algoritmin matriisin kertomiseen tensoreja käyttäen. Sen monimutkaisuus on Θ(n 2,7799 ) .

Schönhagen algoritmit (1981)

Vuonna 1981 Schönhage [5] esitteli menetelmän, joka toimii nopeudella Θ(n 2,695 ) . Arviointi saadaan käyttämällä lähestymistapaa, jota kutsutaan osittaiseksi matriisikertomiseksi . Myöhemmin hän onnistui saamaan arvion Θ(n 2,6087 ) . Sitten Schönhage sai suorien summien menetelmän perusteella kompleksisuusestimaatin Θ(n 2,548 ) . Romani pystyi laskemaan tason Θ(n 2.5166 ) , kun taas Pan pystyi laskemaan arvoon Θ(n 2.5161 ) .

Coppersmith-Winograd-algoritmi (1990)

Vuonna 1990 Coppersmith ja Winograd [6] julkaisivat algoritmin, joka Williams Wasilewskan [7] vuonna 2011 muokkaamana, kertoo matriisit nopeudella O(n 2,3727 ) . Tämä algoritmi käyttää ideoita, jotka ovat samanlaisia kuin Strassenin algoritmi. Tähän mennessä Coppersmith-Winograd-algoritmin modifikaatiot ovat asymptoottisimmin nopeita. Mutta se tosiasia, että saadut parannukset ovat mitättömiä, antaa meille mahdollisuuden puhua "Coppersmith-Winogradin esteen" olemassaolosta algoritmien nopeuden asymptoottisissa arvioissa. Coppersmith-Winograd-algoritmi on tehokas vain tähtitieteellisen kokoisille matriiseille, eikä sitä voida soveltaa käytännössä.

Yhteys ryhmäteoriaan (2003)

Vuonna 2003 Koch ym. tarkastelivat Strassen- ja Coppersmith-Winograd-algoritmeja kirjoissaan [8] ryhmäteorian yhteydessä . He osoittivat, että Strassenin olettamus on pätevä (eli minimikompleksisuus on rajoitettu mille tahansa ), jos jokin ryhmäteorian hypoteeseista [9] täyttyy .

O(n^{2+\epsilon })

\epsilon

Matriisien potenssit

Neliömatriisit voidaan kertoa itsestään monta kertaa samalla tavalla kuin tavalliset luvut, koska niissä on sama määrä rivejä ja sarakkeita. Tällaista peräkkäistä kertolaskua voidaan kutsua matriisin nostamiseksi potenssiin - tämä on erityinen tapaus useiden matriisien tavanomaisesta kertomisesta. Suorakaidematriiseissa on eri määrä rivejä ja sarakkeita, joten niitä ei voi koskaan nostaa potenssiin. n × n matriisi A , joka on korotettu potenssiin, määritellään kaavalla

{\displaystyle \mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k))

ja sillä on seuraavat ominaisuudet ( λ on jokin skalaari):

Nolla tutkinto:

\mathbf {A} ^{0}=\mathbf {E}

missä E on identiteettimatriisi . Tämä on analogista sen tosiasian kanssa, että minkä tahansa luvun nollapotenssi on yhtä suuri kuin yksi.

Kertominen skalaarilla:

(\lambda \mathbf {A} )^{k}=\lambda ^{k}\mathbf {A} ^{k}

Determinantti:

\det(\mathbf {A} ^{k})=\det(\mathbf {A} )^{k}

Helpoin tapa laskea matriisin aste on kertoa matriisi A k kertaa edellisen kertolaskun tuloksella alkaen identiteettimatriisista, kuten usein tehdään skalaareille. Diagonalisoitaville matriiseille on olemassa parempi menetelmä, joka perustuu matriisin A spektrihajotteluun . Toinen menetelmä, joka perustuu Hamilton-Cayleyn lauseeseen , muodostaa tehokkaamman lausekkeen Ak :lle, jossa skalaari nostetaan vaadittuun tehoon , ei koko matriisia .

Diagonaaliset matriisit muodostavat erikoistapauksen . Koska diagonaalimatriisien tulo pelkistetään vastaavien diagonaalialkioiden kertolaskuksi, niin diagonaalimatriisin A k :s potenssi koostuu alkioista, jotka on korotettu vaadittuun potenssiin:

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

Näin ollen diagonaalimatriisin nostaminen potenssiin ei ole vaikeaa. Nostettaessa mielivaltaista matriisia (ei välttämättä diagonaalista) potenssiin, on usein hyödyllistä käyttää ensin diagonalisoitavien matriisien ominaisuuksia .

Matriisien kertolaskua ja eksponentiota käyttämällä voidaan määritellä muita matriisien operaatioita. Esimerkiksi matriisieksponentti voidaan määritellä potenssisarjana , matriisin logaritmi voidaan määritellä matriisieksponentin käänteiseksi ja niin edelleen.

Katso myös

Kirjallisuus

Korn G., Korn T. Matriisialgebra ja matriisilaskenta // Matematiikan käsikirja. - 4. painos. - M .: Nauka, 1978. - S. 392-394.

Muistiinpanot

↑ Kyberneettinen kokoelma. Uusi sarja. Ongelma. 25. la. artikkelit 1983 - 1985: Per. englannista. - M .: Mir, 1988 - V.B. Aleksev. Matriisikertomisen monimutkaisuus. Arvostelu.
↑ Strassen V. Gaussin eliminointi ei ole optimaalinen // Numero . Math / F. Brezzi - Springer Science + Business Media , 1969. - Voi. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
↑ Pan V. Ya, Strassenin algoritmi ei ole optimaalinen - trilineaarinen yhdistämis- ja peruutustekniikka nopeiden algoritmien rakentamiseen matriisioperaatioille. — Pros. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978
↑ Bini D., Capovani M., Lotti G., Romani F. — monimutkaisuus likimääräiselle matriisin kertomiselle. - ilmoittaa. prosessi. Lett., 1979 $O(n^{2,7799})$
↑ Schonhage A. Osittais- ja kokonaismatriisin kertolasku. - SIAM J. Comput., 1981
↑ Don Coppersmith ja Shmuel Winograd. Matriisin kertolasku aritmeettisen progression avulla. Journal of Symbolic Computation , 9:251-280, 1990.
↑ Williams, Virginia (2011), Multiplying matices in O(n 2,3727 aika Arkistoitu 26. lokakuuta 2014 Wayback Machinessa
↑ Ryhmäteoreettiset algoritmit matriisikertolaskulle . Haettu 26. syyskuuta 2009. Arkistoitu alkuperäisestä 6. elokuuta 2011. (määrätön)
↑ Kohti optimaalista matriisin kertolaskualgoritmia (downlink) . Haettu 26. syyskuuta 2009. Arkistoitu alkuperäisestä 31. maaliskuuta 2010. (määrätön)

Vektorit ja matriisit

Vektorit

Peruskonseptit	Vektori geometriassa Perusta Ortogonaalinen perusta Vektorikoordinaatit Kollineaarisuus Ortogonaalisuus Lineaarinen riippuvuus Saraketila
Vektorityypit	Yksikkövektori Aksiaalinen vektori isotrooppinen vektori Normaali Kollineaarisuus Nolla vektori Sädevektori Omavektori
Operaatiot vektoreille	Skalaarituote vektorituote sekoitettu tuote Pseudoskalaarinen tuote Kaksinkertainen ristituote
Tilatyypit	vektoriavaruus affinista tilaa Euklidinen avaruus Pseudoeuklidinen avaruus Normaali tila Minkowskin tila

matriiseja

Peruskonseptit	Matriisin kertolasku Transponoitu matriisi Hermitian konjugaattimatriisi Symmetrinen matriisi käänteinen matriisi Ominaisarvo Matriisin karakteristinen polynomi
Erikoismatriisit	Identiteettimatriisi Nolla matriisi Diagonaalinen matriisi lambda matriisi
Matriisihajotukset	LU:n hajoaminen Cholesky-hajoaminen QR-hajotus LUP-hajoaminen singulaariarvon hajottelu Matriisin spektrihajotus

Muut