Produkt matrike in vektorja c. Množenje matrike z vektorjem

12.09.202227.05.2017

V sistemu MatLab je izvajanje matematičnih operacij na matrikah in vektorjih povsem preprosto. Najprej si oglejmo preproste operacije seštevanja in množenja matrik in vektorjev. Naj sta dana dva vektorja

a = ; % vrstični vektor
b = ; %stolpčni vektor

potem lahko množenje teh dveh vektorjev zapišemo takole

c = a*b; % c=1+2+3+4+5=16
d = b*a; % d – matrika 5x5 elementov

V skladu z operacijami na vektorjih dobimo z množenjem vektorja vrstice z vektorjem stolpca število, množenje vektorja stolpca z vektorjem vrstice pa dvodimenzionalno matriko, ki je rezultat izračunov v zgornjem primeru, tj.

Seštevanje in odštevanje dveh vektorjev zapišemo takole:

a1 = ;
a2 = ;
c = a1+a2; % c = ;
c = a2-a1; % c = ;

Upoštevajte, da se operacije seštevanja in odštevanja lahko izvajajo med dvema vektorjema stolpcev ali dvema vektorjema vrstic. V nasprotnem primeru bo MatLab prikazal sporočilo o napaki, ker Vektorjev različnih vrst ni mogoče dodati. To velja za vse nedovoljene aritmetične operacije: če jih ni mogoče izračunati, bo MatLab javil napako in program se bo končal v ustrezni vrstici.

Operacije množenja in seštevanja med matricami se izvajajo na podoben način:

A = ;
B = enice (3);
C = A+B; % seštevek dveh matric enake velikosti
D = A+5; % seštevek matrike in števila
E = A*B; % množenja matrike A z B
F = B*A; % množenja matrike B z A
G = 5*A; % množenje matrike s številom

Operacije izračuna inverzne matrike ter transponiranja matrik in vektorjev so zapisane takole:

a = ; % vrstični vektor
b = a’; % vektor stolpca, ki ga tvori
% s transponiranjem vrstičnega vektorja a.
A = ; % 3x3 elementna matrika
B = a*A; %B = – vrstični vektor
C = A*b; %C = – stolpčni vektor
D = a*A*a’; % D = 45 – število, vsota elementov matrike A
E = A'; % E – transponirana matrika A
F = inv(A); % F – inverzna matrika A
G = A^-1; % G – inverzna matrika A

Iz zgornjega primera je razvidno, da je operacija transpozicije matrik in vektorjev označena s simbolom ' (apostrof), ki je postavljen za imenom vektorja ali matrike. Izračun inverzne matrike je mogoče izvesti s klicem funkcije inv() ali z dvigom matrike na potenco -1. Rezultat bo v obeh primerih enak, za lažjo uporabo pri izvajanju različnih algoritmov pa sta narejena dva načina izračuna.

Če je v procesu izračunov potrebno pomnožiti, deliti ali dvigniti elemente vektorja ali matrike po elementih, se za to uporabljajo naslednji operaterji:

.* - elementno množenje;
./ in.\ - delitve po elementih;
.^ - elementno potenciranje.

Oglejmo si, kako ti operaterji delujejo na naslednjem primeru.

a = ; % vrstični vektor
b = ; % vrstični vektor
c = a.*b; %c=
A = enice (3); % 3x3 matrika, sestavljena iz enic
B = ; % 3x3 matrika
C = A.*B; % 3x3 matrika, sestavljena iz
D = A./B; % 3x3 matrika, sestavljena iz
E = A.\B; % 3x3 matrika, sestavljena iz
F = A.^2; % kvadriranja elementov matrike A

Za zaključek tega razdelka bomo razmislili o več funkcijah, uporabnih pri delu z vektorji in matricami.

Za iskanje največje vrednosti vektorskega elementa uporabite standardno funkcijo max(), ki vrne najdeno največjo vrednost elementa in njegov položaj (indeks):

a = ;
= max(a); % v = 6, i = 2;

v = max(a); % v = 6;

Zgornji primer prikazuje dva različna načina za klic funkcije max(). V prvem primeru sta določena največja vrednost elementa in njegov indeks v vektorju, v drugem pa samo največja vrednost elementa.

V primeru matrik ta funkcija določi največje vrednosti v stolpcih, kot je prikazano v spodnjem primeru:

A = ;
= max (A); %V=,I=
V = max (A); %V=

Celotno sintakso funkcije max() najdete tako, da vnesete ukaz v ukazno okno MatLab

pomoč<название функции>

Na podoben način deluje funkcija min(), ki določi minimalno vrednost elementa vektorja ali matrike in njegov indeks.

Druga uporabna funkcija za delo z matricami in vektorji je funkcija sum(), ki izračuna vsoto vrednosti elementov vektorja ali stolpcev matrike:

a = ;
s = vsota (a); % s = 3+5+4+2+1=15
A = ;
S1 = vsota (A); %S1=
S2 = vsota (vsota (A)); % S2=39

Pri izračunu vsote S2 se vsota vrednosti elementov matrike A najprej izračuna v stolpcih, nato pa v vrsticah. Kot rezultat, spremenljivka S2 vsebuje vsoto vrednosti vseh elementov matrike A.

Če želite razvrstiti vrednosti elementov vektorja ali matrike v naraščajočem ali padajočem vrstnem redu, uporabite funkcijo sort() na naslednji način:

a = ;

b1 = sort(a); %b1=
b2 = sort(a, 'descend'); %b2=
b3 = sort(a, 'navzgor'); %b3=

za matrice

A = ;
B1 = razvrsti(A); %B1=
B2 = sort(A, 'descend'); %B2=

V številnih praktičnih problemih morate pogosto najti določen element v vektorju ali matriki. To je mogoče storiti s standardno funkcijo find(), ki kot argument vzame pogoj, po katerem so najdeni zahtevani elementi, na primer:

a = ;
b1 = najdi (a == 2); % b1 = 4 – indeks elementa 2
b2 = najdi (a ~= 2); % b2 = – indeksi brez 2
b3 = najdi (a > 3); % b3 =

V navedenem primeru simbol '==' pomeni preverjanje enakosti, simbol '~=' pa preverjanje neenakosti vrednosti elementov vektorja a. Ti operatorji bodo podrobneje opisani v razdelku Pogojni operatorji.

Druga uporabna funkcija za delo z vektorji in matrikami je funkcija mean() za izračun aritmetične sredine, ki deluje na naslednji način:

a = ;
m = povprečje (a); % m = 3
A = ;
M1 = povprečje (A); % M1 =
M2 = povprečje (povprečje (A)); % M2 = 4,333

Torej, v prejšnji lekciji smo si ogledali pravila za seštevanje in odštevanje matrik. To so tako preproste operacije, da jih večina študentov razume dobesedno takoj.

Vendar se zgodaj veselite. Brezplačne ponudbe je konec - preidimo na množenje. Takoj vas opozorim: množenje dveh matrik sploh ni množenje števil v celicah z enakimi koordinatami, kot si morda mislite. Tukaj je vse veliko bolj zabavno. In začeti bomo morali s predhodnimi opredelitvami.

Ujemajoče se matrike

Ena najpomembnejših značilnosti matrice je njena velikost. O tem smo že stokrat govorili: zapis $A=\left[ m\times n \right]$ pomeni, da ima matrika točno $m$ vrstic in $n$ stolpcev. Razpravljali smo že o tem, kako ne zamenjati vrstic s stolpci. Zdaj je pomembno nekaj drugega.

Opredelitev. Matrike v obliki $A=\left[ m\times n \right]$ in $B=\left[ n\times k \right]$, v katerih število stolpcev v prvi matriki sovpada s številom vrstic v drugem pa se imenujejo dosledni.

Še enkrat: število stolpcev v prvi matriki je enako številu vrstic v drugi! Od tu dobimo dva sklepa hkrati:

Za nas je pomemben vrstni red matrik. Na primer, matriki $A=\left[ 3\times 2 \right]$ in $B=\left[ 2\times 5 \right]$ sta skladni (2 stolpca v prvi matriki in 2 vrstici v drugi) , ampak obratno — matriki $B=\left[ 2\times 5 \right]$ in $A=\left[ 3\times 2 \right]$ nista več skladni (5 stolpcev v prvi matriki niso 3 vrstice v drugem).
Doslednost lahko enostavno preverimo tako, da eno za drugo zapišemo vse dimenzije. Na primeru iz prejšnjega odstavka: “3 2 2 5” - na sredini so enake številke, zato sta matriki konsistentni. Toda "2 5 3 2" nista dosledna, ker so na sredini različne številke.

Poleg tega se zdi, da Captain Obviousness namiguje, da so kvadratne matrike enake velikosti $\left[ n\times n \right]$ vedno skladne.

V matematiki, ko je pomemben vrstni red naštevanja objektov (npr. v zgoraj obravnavani definiciji je pomemben vrstni red matrik), pogosto govorimo o urejenih parih. Spoznali smo jih že v šoli: mislim, da ni pametno, da koordinate $\left(1;0 \right)$ in $\left(0;1 \right)$ določata različni točki na ravnini.

Torej: koordinate so tudi urejeni pari, ki so sestavljeni iz števil. Toda nič vam ne preprečuje, da bi naredili tak par iz matric. Potem lahko rečemo: "Urejen par matrik $\left(A;B \right)$ je skladen, če je število stolpcev v prvi matriki enako številu vrstic v drugi."

No, kaj pa?

Opredelitev množenja

Razmislite o dveh konsistentnih matrikah: $A=\left[ m\times n \right]$ in $B=\left[ n\times k \right]$. In jim definiramo operacijo množenja.

Opredelitev. Zmnožek dveh ujemajočih se matrik $A=\left[ m\times n \right]$ in $B=\left[ n\times k \right]$ je nova matrika $C=\left[ m\times k \ desno] $, katerega elementi se izračunajo po formuli:

\[\begin(align) & ((c)_(i;j))=((a)_(i;1))\cdot ((b)_(1;j))+((a)_ (i;2))\cdot ((b)_(2;j))+\ldots +((a)_(i;n))\cdot ((b)_(n;j))= \\ & =\sum\limits_(t=1)^(n)(((a)_(i;t))\cdot ((b)_(t;j))) \end(align)\]

Tak izdelek je označen na standarden način: $C=A\cdot B$.

Tisti, ki to definicijo vidijo prvič, imajo takoj dve vprašanji:

Kakšna ostra igra je to?
Zakaj je tako težko?

No, najprej najprej. Začnimo s prvim vprašanjem. Kaj pomenijo vsi ti indeksi? In kako ne delati napak pri delu z resničnimi matricami?

Najprej ugotavljamo, da je dolga vrstica za izračun $((c)_(i;j))$ (med indekse sem posebej postavil podpičje, da ne bi prišlo do zmede, vendar jih ni treba vstavljati splošno - tudi sam sem se naveličal vnašati formulo v definicijo) se pravzaprav skrči na preprosto pravilo:

Vzemite $i$to vrstico v prvi matriki;
Vzemite $j$th stolpec v drugi matriki;
Dobimo dve zaporedji števil. Elemente teh zaporedij pomnožimo z enakimi števili, nato pa nastale produkte seštejemo.

Ta postopek je enostavno razumeti s slike:

Shema za množenje dveh matrik

Še enkrat: popravimo vrstico $i$ v prvi matriki, stolpec $j$ v drugi matriki, pomnožimo elemente z istimi številkami in nato seštejemo nastale produkte - dobimo $((c)_(ij))$ . In tako naprej za vse $1\le i\le m$ in $1\le j\le k$. Tisti. Takšnih “perverzij” bo skupaj $m\krat k$.

Pravzaprav smo matrično množenje že srečali v šolskem kurikulumu, le v močno okrnjeni obliki. Naj bodo podani vektorji:

\[\begin(align) & \vec(a)=\left(((x)_(a));((y)_(a));((z)_(a)) \right); \\ & \overrightarrow(b)=\left(((x)_(b));((y)_(b));((z)_(b)) \desno). \\ \konec(poravnaj)\]

Potem bo njihov skalarni produkt natanko vsota produktov parov:

\[\overrightarrow(a)\times \overrightarrow(b)=((x)_(a))\cdot ((x)_(b))+((y)_(a))\cdot ((y )_(b))+((z)_(a))\cdot ((z)_(b))\]

V bistvu, ko so bila drevesa bolj zelena in je bilo nebo svetlejše, smo preprosto pomnožili vektor vrstice $\overrightarrow(a)$ z vektorjem stolpca $\overrightarrow(b)$.

Danes se ni nič spremenilo. Samo zdaj je več teh vektorjev vrstic in stolpcev.

Ampak dovolj teorije! Poglejmo resnične primere. In začnimo z najpreprostejšim primerom - kvadratnimi matricami.

Množenje kvadratne matrike

Naloga 1. Naredite množenje:

\[\left[ \begin(matrika)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(matrika) \desno]\cdot \left[ \begin(matrika)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\end(matrika) \desno]\]

rešitev. Torej imamo dve matriki: $A=\left[ 2\times 2 \right]$ in $B=\left[ 2\times 2 \right]$. Jasno je, da so konsistentne (kvadratne matrike enake velikosti so vedno konsistentne). Zato izvajamo množenje:

\[\begin(align) & \left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \ začetek(matrika)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(matrika) \desno]=\levo[ \začetek(matrika)(*(35)(r)) 1\cdot \left(-2 \desno)+2\cdot 3 & 1\cdot 4+2\cdot 1 \\ -3\cdot \left(-2 \desno)+4\cdot 3 & -3\cdot 4+4\cdot 1 \\\end(matrika) \right]= \\ & =\left[ \begin(matrika)(*(35)(r)) 4 & 6 \\ 18 & -8 \\\ konec (matrika)\desno]. \end(align)\]

To je vse!

Odgovor: $\left[ \begin(matrika)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(matrika) \desno]$.

Naloga 2. Naredite množenje:

\[\left[ \begin(matrix) 1 & 3 \\ 2 & 6 \\\end(matrix) \right]\cdot \left[ \begin(array)(*(35)(r))9 & 6 \\ -3 & -2 \\\end(matrika) \desno]\]

rešitev. Spet dosledne matrike, zato izvedemo naslednja dejanja:\[\]

\[\begin(align) & \left[ \begin(matrix) 1 & 3 \\ 2 & 6 \\\end(matrix) \right]\cdot \left[ \begin(matrika)(*(35)( ) r)) 9 & 6 \\ -3 & -2 \\\end(matrika) \right]=\levo[ \begin(matrika)(*(35)(r)) 1\cdot 9+3\cdot \ levo(-3 \desno) & 1\cdot 6+3\cdot \left(-2 \desno) \\ 2\cdot 9+6\cdot \levo(-3 \desno) & 2\cdot 6+6 \ cdot \left(-2 \desno) \\\end(matrika) \right]= \\ & =\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrix) \right ] . \end(align)\]

Kot lahko vidite, je rezultat matrika, napolnjena z ničlami

Odgovor: $\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrix) \right]$.

Iz navedenih primerov je očitno, da množenje matrik ni tako zapletena operacija. Vsaj za kvadratne matrice 2 krat 2.

V procesu izračunov smo sestavili vmesno matriko, kjer smo neposredno opisali, katera števila so vključena v posamezno celico. Točno to morate storiti, ko rešujete resnične probleme.

Osnovne lastnosti produkta matrike

Na kratko. Matrično množenje:

Nekomutativno: $A\cdot B\ne B\cdot A$ v splošnem primeru. Seveda obstajajo posebne matrike, za katere velja enakost $A\cdot B=B\cdot A$ (na primer, če je $B=E$ identitetna matrika), vendar v veliki večini primerov to ne deluje ;
Asociativno: $\levo(A\cdot B \desno)\cdot C=A\cdot \left(B\cdot C \desno)$. Tukaj ni nobenih možnosti: sosednje matrike je mogoče pomnožiti, ne da bi vas skrbelo, kaj je levo in desno od teh dveh matrik.
Distributivno: $A\cdot \left(B+C \desno)=A\cdot B+A\cdot C$ in $\left(A+B \desno)\cdot C=A\cdot C+B\cdot C $ (zaradi nekomutativnosti zmnožka je potrebno ločeno podati desno in levo distribucijo.

In zdaj - vse je enako, vendar bolj podrobno.

Matrično množenje je v marsičem podobno klasičnemu množenju števil. Vendar obstajajo razlike, med katerimi je najpomembnejša ta Matrično množenje je na splošno nekomutativno.

Ponovno poglejmo matrike iz 1. problema. Njihov neposredni produkt že poznamo:

\[\left[ \begin(matrika)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(matrika) \desno]\cdot \left[ \begin(matrika)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\end(matrika) \right]=\levo[ \begin(matrika)(*(35)(r))4 & 6 \\ 18 & -8 \\\konec(matrika) \desno]\]

Če pa matriki zamenjamo, dobimo popolnoma drugačen rezultat:

\[\left[ \begin(matrika)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(matrika) \desno]\cdot \left[ \begin(matrika)(* (35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]=\left[ \begin(matrix) -14 & 4 \\ 0 & 10 \\\end(matrix) )\prav]\]

Izkazalo se je, da $A\cdot B\ne B\cdot A$. Poleg tega je operacija množenja definirana le za konsistentni matriki $A=\left[ m\times n \right]$ in $B=\left[ n\times k \right]$, vendar nihče ni zagotovil, da sta ostanejo dosledni, če jih zamenjamo. Na primer, matriki $\left[ 2\times 3 \right]$ in $\left[ 3\times 5 \right]$ sta precej skladni v podanem vrstnem redu, vendar enaki matriki $\left[ 3\times 5 \right] $ in $\left[ 2\times 3 \right]$, zapisana v obratnem vrstnem redu, nista več skladna. Žalostno. :(

Med kvadratnimi matrikami dane velikosti $n$ bodo vedno tiste, ki dajejo enak rezultat tako pri množenju v neposrednem kot v obratnem vrstnem redu. Kako opisati vse takšne matrice (in koliko jih je na splošno) je tema za ločeno lekcijo. Danes ne bomo o tem :)

Vendar je matrično množenje asociativno:

\[\levo(A\cdot B \desno)\cdot C=A\cdot \left(B\cdot C \desno)\]

Zato, ko morate pomnožiti več matrik zaporedoma, sploh ni potrebno, da to storite takoj: povsem možno je, da nekatere sosednje matrike, ko jih pomnožite, dajo zanimiv rezultat. Na primer ničelna matrika, kot je opisana v problemu 2 zgoraj.

V realnih problemih moramo največkrat množiti kvadratne matrike velikosti $\left[ n\times n \right]$. Množica vseh takih matrik je označena z $((M)^(n))$ (tj. vnosa $A=\left[ n\times n \right]$ in \ pomenita isto) in bo nujno vsebujejo matriko $E$, ki jo imenujemo identitetna matrika.

Opredelitev. Identitetna matrika velikosti $n$ je matrika $E$, tako da za katero koli kvadratno matriko $A=\left[ n\times n \right]$ velja enakost:

Takšna matrika je vedno videti enako: na glavni diagonali so enice, v vseh ostalih celicah pa ničle.

\[\begin(align) & A\cdot \left(B+C \desno)=A\cdot B+A\cdot C; \\ & \levo(A+B \desno)\cdot C=A\cdot C+B\cdot C. \\ \end(align)\]

Z drugimi besedami, če morate eno matriko pomnožiti z vsoto dveh drugih, jo lahko pomnožite z vsako od teh »drugih dveh« in nato seštejete rezultate. V praksi moramo običajno izvesti obratno operacijo: opazimo isto matriko, jo vzamemo iz oklepaja, izvedemo seštevanje in si s tem poenostavimo življenje :).

Opomba: za opis distributivnosti smo morali napisati dve formuli: kjer je vsota v drugem faktorju in kjer je vsota v prvem. To se zgodi prav zato, ker je matrično množenje nekomutativno (in na splošno je v nekomutativni algebri veliko zabavnih stvari, ki sploh ne pridejo na misel pri delu z navadnimi števili). In če morate na primer to lastnost zapisati na izpitu, potem obvezno napišite obe formuli, sicer se lahko učitelj malo razjezi.

Ok, vse to so bile pravljice o kvadratnih matricah. Kaj pa pravokotne?

Primer pravokotnih matrik

A nič – vse je tako kot pri kvadratnih.

Naloga 3. Naredite množenje:

\[\levo[ \begin(matrika) \begin(matrika) 5 \\ 2 \\ 3 \\\end(matrika) & \begin(matrika) 4 \\ 5 \\ 1 \\\end(matrika) \ \\end(matrika) \desno]\cdot \left[ \begin(matrika)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(matrika) \desno]\]

rešitev. Imamo dve matriki: $A=\left[ 3\times 2 \right]$ in $B=\left[ 2\times 2 \right]$. Zapišimo številke, ki označujejo velikosti v vrsti:

Kot lahko vidite, osrednji dve številki sovpadata. To pomeni, da so matrike konsistentne in jih je mogoče množiti. Poleg tega na izhodu dobimo matriko $C=\levo[ 3\krat 2 \desno]$:

\[\begin(align) & \left[ \begin(matrix) \begin(matrix) 5 \\ 2 \\ 3 \\\end(matrix) & \begin(matrix) 4 \\ 5 \\ 1 \\ \end(matrika) \\\end(matrika) \right]\cdot \left[ \begin(matrika)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(matrika) \desno]=\levo[ \begin(matrika)(*(35)(r)) 5\cdot \left(-2 \desno)+4\cdot 3 & 5\cdot 5+4\cdot 4 \\ 2 \cdot \left(-2 \desno)+5\cdot 3 & 2\cdot 5+5\cdot 4 \\ 3\cdot \left(-2 \desno)+1\cdot 3 & 3\cdot 5+1 \cdot 4 \\\end(matrika) \right]= \\ & =\levo[ \begin(matrika)(*(35)(r)) 2 & 41 \\ 11 & 30 \\ -3 & 19 \ \\konec(matrika) \desno]. \end(align)\]

Vse je jasno: končna matrika ima 3 vrstice in 2 stolpca. Precej $=\levo[ 3\krat 2 \desno]$.

Odgovor: $\left[ \begin(matrika)(*(35)(r)) \begin(matrika)(*(35)(r)) 2 \\ 11 \\ -3 \\\end(matrika) & \begin(matrika) 41 \\ 30 \\ 19 \\\end(matrika) \\\end(matrika) \right]$.

Zdaj pa si oglejmo eno najboljših nalog za usposabljanje za tiste, ki šele začenjajo delati z matricami. V njej vam ni treba samo pomnožiti nekaj dveh tablic, ampak najprej ugotoviti: ali je takšno množenje dovoljeno?

Problem 4. Poišči vse možne parne produkte matrik:

\\]; $B=\levo[ \begin(matrika) \begin(matrika) 0 \\ 2 \\ 0 \\ 4 \\\end(matrika) & \begin(matrika) 1 \\ 0 \\ 3 \\ 0 \ \\konec(matrika) \\\konec(matrika) \desno]$; $C=\levo[ \begin(matrix)0 & 1 \\ 1 & 0 \\\end(matrix) \right]$.

rešitev. Najprej zapišimo velikosti matrik:

\;\ B=\levo[ 4\krat 2 \desno];\ C=\levo[ 2\krat 2 \desno]\]

Ugotovimo, da lahko matriko $A$ uskladimo le z matriko $B$, saj je število stolpcev $A$ 4 in samo $B$ ima toliko vrstic. Zato lahko najdemo izdelek:

\\cdot \left[ \begin(matrika)(*(35)(r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end(matrika) \desno]=\ levo[ \začetek(matrika)(*(35)(r))-10 & 7 \\ 10 & 7 \\\konec(matrika) \desno]\]

Bralcu predlagam, da vmesne korake opravi samostojno. Opozoril bom le, da je bolje določiti velikost nastale matrike vnaprej, še pred kakršnimi koli izračuni:

\\cdot \left[ 4\krat 2 \desno]=\levo[ 2\krat 2 \desno]\]

Z drugimi besedami, preprosto odstranimo »tranzitne« koeficiente, ki so zagotavljali konsistentnost matrik.

Katere druge možnosti so možne? Seveda lahko najdemo $B\cdot A$, saj je $B=\left[ 4\times 2 \right]$, $A=\left[ 2\times 4 \right]$, torej urejen par $\ left(B ;A \right)$ je skladen in dimenzija izdelka bo:

\\cdot \left[ 2\krat 4 \desno]=\levo[ 4\krat 4 \desno]\]

Skratka, rezultat bo matrika $\left[ 4\times 4 \right]$, katere koeficiente je mogoče enostavno izračunati:

\\cdot \left[ \begin(matrika)(*(35)(r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\end(matrika) \desno]=\ levo[ \begin(array)(*(35)(r))1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(matrika) \desno]\]

Očitno se lahko dogovorite tudi za $C\cdot A$ in $B\cdot C$ - in to je to. Zato preprosto zapišemo nastale izdelke:

Bilo je lahko. :)

Odgovor: $AB=\levo[ \begin(matrika)(*(35)(r)) -10 & 7 \\ 10 & 7 \\\end(matrika) \desno]$; $BA=\left[ \begin(array)(*(35)(r)) 1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(matrika) \desno]$; $CA=\levo[ \begin(matrika)(*(35)(r)) 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\end(matrika) \desno]$; $BC=\levo[ \begin(matrika)(*(35)(r))1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\end(matrika) \desno]$.

Na splošno toplo priporočam, da to nalogo opravite sami. In še ena podobna naloga, ki je v domači nalogi. Te na videz preproste misli vam bodo pomagale pri vadbi vseh ključnih stopenj množenja matrik.

A zgodba se tu ne konča. Preidimo na posebne primere množenja :)

Vektorji vrstic in vektorji stolpcev

Ena najpogostejših matričnih operacij je množenje z matriko, ki ima eno vrstico ali en stolpec.

Opredelitev. Vektor stolpec je matrika velikosti $\left[ m\times 1 \right]$, tj. sestavljen iz več vrstic in samo enega stolpca.

Vrstni vektor je matrika velikosti $\left[ 1\times n \right]$, tj. sestavljen iz ene vrstice in več stolpcev.

Pravzaprav smo te predmete že srečali. Na primer, navaden tridimenzionalni vektor iz stereometrije $\overrightarrow(a)=\left(x;y;z \right)$ ni nič drugega kot vektor vrstice. S teoretičnega vidika skorajda ni razlike med vrsticami in stolpci. Previdni morate biti le pri usklajevanju z okoliškimi matrikami množiteljev.

Naloga 5. Naredite množenje:

\[\levo[ \begin(matrika)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(matrika) \desno] \cdot \left[ \begin(matrika)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(matrika) \desno]\]

rešitev. Tukaj imamo produkt ujemajočih se matrik: $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Poiščimo ta kos:

\[\levo[ \begin(matrika)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(matrika) \desno] \cdot \left[ \begin(matrika)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(matrika) \desno]=\levo[ \begin(matrika)(*(35 )(r)) 2\cdot 1+\levo(-1 \desno)\cdot 2+3\cdot \levo(-1 \desno) \\ 4\cdot 1+2\cdot 2+0\cdot 2 \ \ -1\cdot 1+1\cdot 2+1\cdot \left(-1 \desno) \\\end(matrika) \desno]=\levo[ \begin(matrika)(*(35)(r) ) -3 \\ 8 \\ 0 \\\konec(matrika) \desno]\]

Odgovor: $\left[ \begin(array)(*(35)(r))-3 \\ 8 \\ 0 \\\end(array) \right]$.

Naloga 6. Naredite množenje:

\[\left[ \begin(matrika)(*(35)(r)) 1 & 2 & -3 \\\end(matrika) \desno]\cdot \left[ \begin(matrika)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(matrika) \right]\]

rešitev. Spet je vse dogovorjeno: $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. Izdelek štejemo:

\[\left[ \begin(matrika)(*(35)(r)) 1 & 2 & -3 \\\end(matrika) \desno]\cdot \left[ \begin(matrika)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(matrika) \desno]=\levo[ \begin(matrika)(*(35)( ) r))5 & -19 & 5 \\\end(matrika) \desno]\]

Odgovor: $\left[ \begin(matrix) 5 & -19 & 5 \\\end(matrix) \right]$.

Kot lahko vidite, ko pomnožimo vektor vrstice in vektor stolpca s kvadratno matriko, je rezultat vedno vrstica ali stolpec enake velikosti. To dejstvo ima veliko uporab - od reševanja linearnih enačb do vseh vrst transformacij koordinat (ki na koncu pridejo tudi do sistemov enačb, a da o žalostnih stvareh ne govorimo).

Mislim, da je bilo tukaj vse očitno. Preidimo na zadnji del današnje lekcije.

Matrično potenciranje

Med vsemi operacijami množenja si posebno pozornost zasluži potenciranje - to je takrat, ko isti predmet večkrat pomnožimo samega s seboj. Matrike niso nobena izjema; prav tako jih je mogoče dvigniti na različne potence.

Takšna dela so vedno dogovorjena:

\\cdot \left[ n\krat n \desno]=\levo[ n\krat n \desno]\]

In označeni so na popolnoma enak način kot običajne stopnje:

\[\begin(align) & A\cdot A=((A)^(2)); \\ & A\cdot A\cdot A=((A)^(3)); \\ & \podoklepaj(A\cdot A\cdot \ldots \cdot A)_(n)=((A)^(n)). \\ \konec(poravnaj)\]

Na prvi pogled je vse preprosto. Poglejmo, kako to izgleda v praksi:

Naloga 7. Dvignite matriko na navedeno moč:

$((\levo[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \desno])^(3))$

rešitev. No OK, gradimo. Najprej ga kvadriramo:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(2))=\left[ \begin(matrix ) 1 & 1 \\ 0 & 1 \\\end(matrika) \desno]\cdot \left[ \begin(matrika) 1 & 1 \\ 0 & 1 \\\end(matrika) \desno]= \\ & =\levo[ \begin(array)(*(35)(r)) 1\cdot 1+1\cdot 0 & 1\cdot 1+1\cdot 1 \\ 0\cdot 1+1\cdot 0 & 0\cdot 1+1\cdot 1 \\\end(matrika) \right]= \\ & =\left[ \begin(matrika)(*(35)(r)) 1 & 2 \\ 0 & 1 \ \\end(matrika) \right] \end(align)\]

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))=((\left[ \begin (matrika) 1 & 1 \\ 0 & 1 \\\end(matrika) \right])^(3))\cdot \left[ \begin(matrika) 1 & 1 \\ 0 & 1 \\\end( matrika) \desno]= \\ & =\levo[ \begin(matrika)(*(35)(r)) 1 & 2 \\ 0 & 1 \\\end(matrika) \desno]\cdot \levo[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 3 \\ 0 & 1 \\\end(matrika) \desno] \end(align)\]

To je vse.:)

Odgovor: $\left[ \begin(matrix)1 & 3 \\ 0 & 1 \\\end(matrix) \right]$.

Problem 8. Dvignite matriko na navedeno moč:

\[((\levo[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \desno])^(10))\]

rešitev. Samo ne jokajte zdaj zaradi dejstva, da je "diploma prevelika", "svet ni pravičen" in "učitelji so popolnoma izgubili svoje obale." Pravzaprav je preprosto:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(10))=((\left[ \begin (matrika) 1 & 1 \\ 0 & 1 \\\end(matrika) \right])^(3))\cdot ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\ konec(matrika) \desno])^(3))\cdot ((\levo[ \začetek(matrika) 1 & 1 \\ 0 & 1 \\\konec(matrika) \desno])^(3))\ cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left(\left[ \begin(matrix) 1 & 3 \\ 0 & 1 \\\end(matrika) \desno]\cdot \left[ \begin(matrika) 1 & 3 \\ 0 & 1 \\\end(matrika) \desno] \desno)\cdot \left(\left[ \begin(matrix) 1 & 3 \\ 0 & 1 \\\end(matrix) \right]\cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right ] \desno)= \\ & =\levo[ \begin(matrika) 1 & 6 \\ 0 & 1 \\\end(matrika) \desno]\cdot \left[ \begin(matrika) 1 & 4 \\ 0 & 1 \\\end(matrika) \right]= \\ & =\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right] \end(align)\ ]

Upoštevajte, da smo v drugi vrstici uporabili asociativnost množenja. Pravzaprav smo ga uporabili v prejšnji nalogi, vendar je bil tam impliciten.

Odgovor: $\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right]$.

Kot lahko vidite, ni nič zapletenega pri dvigovanju matrike na potenco. Zadnji primer lahko povzamemo:

\[((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(n))=\left[ \begin(array)(*(35) (r)) 1 & n \\ 0 & 1 \\\end(matrika) \desno]\]

To dejstvo je enostavno dokazati z matematično indukcijo ali neposrednim množenjem. Vendar ni vedno mogoče ujeti takšnih vzorcev pri dvigu na stopnjo. Zato bodite previdni: pogosto se "naključno" množenje več matrik izkaže za lažje in hitrejše kot iskanje nekakšnih vzorcev.

Na splošno ne iščite višjega smisla tam, kjer ga ni. Za zaključek razmislimo o potenciranju večje matrike - toliko kot $\left[ 3\times 3 \right]$.

Problem 9. Dvignite matriko na navedeno moč:

\[((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(3))\]

rešitev. Ne iščimo vzorcev. Delamo naprej:

\[((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(3))=(( \left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(2))\cdot \left[ \begin (matrika)0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrika) \desno]\]

Najprej kvadriramo to matriko:

\[\begin(align) & ((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^( 2))=\levo[ \begin(matrika) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrika) \desno]\cdot \left[ \begin(matrika ) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right]= \\ & =\left[ \begin(array)(*(35)(r )) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(matrika) \right] \end(align)\]

Zdaj pa ga narežemo na kocke:

\[\begin(align) & ((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^( 3))=\levo[ \begin(matrika)(*(35)(r)) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(matrika) \desno] \cdot \left[ \begin(matrika) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrika) \desno]= \\ & =\left[ \begin( array)(*(35)(r)) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(array) \right] \end(align)\]

To je vse. Problem je rešen.

Odgovor: $\levo[ \begin(matrika) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(matrika) \desno]$.

Kot lahko vidite, se je obseg izračunov povečal, pomen pa se ni nič spremenil :).

S tem se lekcija zaključi. Naslednjič bomo upoštevali inverzno operacijo: z obstoječim produktom bomo iskali originalne faktorje.

Kot ste verjetno že uganili, bomo govorili o inverzni matriki in metodah za njeno iskanje.

Definicija 1

Matrični produkt (C = AB) je operacija samo za ujemajoči se matriki A in B, pri kateri je število stolpcev matrike A enako številu vrstic matrike B:

C ⏟ m × n = A ⏟ m × p × B ⏟ p × n

Primer 1

Dane matrike:

A = a (i j) dimenzij m × n;
B = b (i j) velikosti p × n

Matrika C, katere elementi c i j so izračunani po naslednji formuli:

c i j = a i 1 × b 1 j + a i 2 × b 2 j + . . . + a i p × b p j , i = 1 , . . . m, j = 1, . . . m

Primer 2

Izračunajmo produkte AB=BA:

A = 1 2 1 0 1 2 , B = 1 0 0 1 1 1

Rešitev z uporabo pravila množenja matrike:

A ⏟ 2 × 3 × B ⏟ 3 × 2 = 1 2 1 0 1 2 × 1 0 0 1 1 1 = 1 × 1 + 2 × 0 + 1 × 1 1 × 0 + 2 × 1 + 1 × 1 0 × 1 + 1 × 0 + 2 × 1 0 × 0 + 1 × 1 + 2 × 1 = = 2 3 2 3 ⏟ 2 × 2

B ⏟ 3 × 2 × A ⏟ 2 × 3 = 1 0 0 1 1 1 × 1 2 1 0 1 2 = 1 × 1 + 0 × 0 1 × 2 + 0 × 1 1 × 1 + 0 × 2 0 × 1 + 1 × 0 0 × 2 + 1 × 1 0 × 1 + 1 × 2 1 × 1 + 1 × 0 1 × 2 + 1 × 1 1 × 1 + 1 × 2 = 1 2 1 0 1 2 1 3 3 ⏟ 3×3

Produkt A B in BA A sta najdena, vendar sta matriki različnih velikosti: A B ni enako BA A.

Lastnosti množenja matrik

Lastnosti množenja matrik:

(A B) C = A (B C) - asociativnost matričnega množenja;
A (B + C) = A B + A C - distributivnost množenja;
(A + B) C = A C + B C - distributivnost množenja;
λ (A B) = (λ A) B

Primer 1

Preverimo lastnost št. 1: (A B) C = A (B C) :

(A × B) × A = 1 2 3 4 × 5 6 7 8 × 1 0 0 2 = 19 22 43 50 × 1 0 0 2 = 19 44 43 100,

A (B × C) = 1 2 3 4 × 5 6 7 8 1 0 0 2 = 1 2 3 4 × 5 12 7 16 = 19 44 43 100.

Primer 2

Preverimo lastnost št. 2: A (B + C) = A B + A C:

A × (B + C) = 1 2 3 4 × 5 6 7 8 + 1 0 0 2 = 1 2 3 4 × 6 6 7 10 = 20 26 46 58,

A B + A C = 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 = 19 22 43 50 + 1 4 3 8 = 20 26 46 58.

Produkt treh matrik

Produkt treh matrik A B C se izračuna na 2 načina:

poišči A B in pomnoži s C: (A B) C;
ali najprej poiščite B C in nato pomnožite A (B C).

Primer 3

Pomnožite matrike na dva načina:

4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1

Algoritem dejanj:

poiščite produkt 2 matrik;
nato spet poiščite produkt 2 matrik.

1). A B = 4 3 7 5 × - 28 93 38 - 126 = 4 (- 28) + 3 × 38 4 × 93 + 3 (- 126) 7 (- 28) + 5 × 38 7 × 93 + 5 (- 126 ) = 2 - 6 - 6 21

2). A B C = (A B) C = 2 - 6 - 6 21 7 3 2 1 = 2 × 7 - 6 × 2 2 × 3 - 6 × 1 - 6 × 7 + 21 × 2 - 6 × 3 + 21 × 1 = 2 0 0 3 .

Uporabimo formulo A B C = (A B) C:

1). B C = - 28 93 38 - 126 7 3 2 1 = - 28 × 7 + 93 × 2 - 28 × 3 + 93 × 1 38 × 7 - 126 × 2 38 × 3 - 126 × 1 = - 10 9 14 - 12

2). A B C = (A B) C = 7 3 2 1 - 10 9 14 - 12 = 4 (- 10) + 3 × 14 4 × 9 + 3 (- 12) 7 (- 10) + 5 × 14 7 × 9 + 5 (- 12) = 2 0 0 3

Odgovor: 4 3 7 5 - 28 93 38 - 126 7 3 2 1 = 2 0 0 3

Množenje matrike s številom

Definicija 2

Produkt matrike A s številom k je matrika B = A k enake velikosti, ki jo dobimo iz prvotne z množenjem vseh njenih elementov z danim številom:

b i, j = k × a i, j

Lastnosti množenja matrike s številom:

1 × A = A
0 × A = ničelna matrika
k (A + B) = k A + k B
(k + n) A = k A + n A
(k × n) × A = k (n × A)

Primer 4

Poiščemo produkt matrike A = 4 2 9 0 s 5.

5 A = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0

Množenje matrike z vektorjem

Definicija 3

Če želite najti produkt matrike in vektorja, morate pomnožiti s pravilom "vrstica za stolpcem":

če matriko pomnožite z vektorjem stolpca, se mora število stolpcev v matriki ujemati s številom vrstic v vektorju stolpca;
Rezultat množenja vektorja stolpca je samo vektor stolpca:

A B = a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋯ ⋯ ⋯ ⋯ a m 1 a m 2 ⋯ a m n b 1 b 2 ⋯ b 1 n = a 11 × b 1 + a 12 × b 2 + ⋯ + a 1 n × b n a 21 × b 1 + a 22 × b 2 + ⋯ + a 2 n × b n ⋯ ⋯ ⋯ ⋯ a m 1 × b 1 + a m 2 × b 2 + ⋯ + a m n × b n = c 1 s 2 ⋯ s 1 m

če matriko pomnožite z vrstičnim vektorjem, mora biti matrika, ki jo množite, izključno stolpčni vektor, število stolpcev pa se mora ujemati s številom stolpcev v vrstičnem vektorju:

A B = a a ⋯ a b b ⋯ b = a 1 × b 1 a 1 × b 2 ⋯ a 1 × b n a 2 × b 1 a 2 × b 2 ⋯ a 2 × b n ⋯ ⋯ ⋯ ⋯ a n × b 1 a n × b 2 ⋯ a n × b n = c 11 c 12 ⋯ c 1 n c 21 c 22 ⋯ c 2 n ⋯ ⋯ ⋯ ⋯ c n 1 c n 2 ⋯ c n n

Primer 5

Poiščimo produkt matrike A in vektorja stolpca B:

A B = 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 = 2 × 1 + 4 × 2 + 0 × (- 1) - 2 × 1 + 1 × 2 + 3 × (- 1) - 1 × 1 + 0 × 2 + 1 × (- 1) = 2 + 8 + 0 - 2 + 2 - 3 - 1 + 0 - 1 = 10 - 3 - 2

Primer 6

Poiščimo produkt matrike A in vrstičnega vektorja B:

A = 3 2 0 - 1 , B = - 1 1 0 2

A B = 3 2 0 1 × - 1 1 0 2 = 3 × (- 1) 3 × 1 3 × 0 3 × 2 2 × (- 1) 2 × 1 2 × 0 2 × 2 0 × (- 1) 0 × 1 0 × 0 0 × 2 1 × (- 1) 1 × 1 1 × 0 1 × 2 = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

Odgovor: A B = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

Če v besedilu opazite napako, jo označite in pritisnite Ctrl+Enter

Vsak vektor si lahko predstavljamo kot matriko z enim stolpcem ali eno vrstico. Matriko z enim stolpcem bomo imenovali vektor stolpec, matriko z eno vrstico pa vektor vrstic.

Če je A matrika velikosti m*n, potem ima stolpčni vektor b velikost n, vrstični vektor b pa velikost m.

Če torej želimo matriko pomnožiti z vektorjem, moramo vektor obravnavati kot stolpčni vektor. Pri množenju vektorja z matriko ga je treba obravnavati kot vektor vrstice.

Množilna matrika

na kompleksen vektor

Dobimo rezultat

Kot lahko vidite, imamo lahko z nespremenjeno vektorsko dimenzijo dve rešitvi.

Rad bi vas opozoril na dejstvo, da sta matriki v prvi in drugi različici kljub enakim vrednostim popolnoma različni (imata različne dimenzije)

V prvem primeru se vektor obravnava kot stolpec in takrat je potreben pomnoži matriko z vektorjem, v drugem primeru pa imamo vrstični vektor in potem imamo produkt vektorja in matrike.

Ta bot tudi množi vektorje in matrike, ki imajo kompleksne vrednosti. Na podlagi popolnejšega kalkulatorja: matrično množenje s kompleksnimi vrednostmi na spletu

Lastnosti množenja matričnih vektorjev

Matrix

Vektorski stolpec

Vrstni vektor

Poljubno število

1. Zmnožek matrike z vsoto vektorjev stolpcev je enak vsoti zmnožkov matrike z vsakim od vektorjev

2. Produkt vsote vektorjev vrstic in matrike je enak vsoti produktov vektorjev in matrike

3. Skupni faktor vektorja je mogoče vzeti zunaj produkta matrike z vektorjem/vektorjem z matriko

4. Zmnožek vrstičnega vektorja in produkta matrike in stolpčnega vektorja je enakovreden produktu vrstičnega vektorja ter matrike in stolpčnega vektorja.

Predavanje 6. Vzporedni numerični algoritmi za reševanje tipičnih problemov računalniške matematike: matrično množenje.

Množenje matrike z vektorjem. Doseganje najvišje možne zmogljivosti. Izkoriščanje paralelizma na srednji ravni. Organizacija vzporednega računalništva pri p = n. Uporaba omejenega nabora procesorjev. Matrično množenje. Makrooperacijska analiza algoritmov za reševanje problemov. Organizacija paralelizma na podlagi izmenjave podatkov.

Množenje matrike z vektorjem

Problem množenja matrike z vektorjem definirajo relacije

Tako pridobitev nastalega vektorja vključuje ponavljanje podobnih operacij množenja vrstic matrike in vektorja. Pridobivanje vsake takšne operacije vključuje elementno množenje elementov vrstice matrike in vektorja ter kasnejše seštevanje dobljenih produktov. Skupno število zahtevanih skalarnih operacij je ocenjeno s količino

Kot izhaja iz dejanj, izvedenih pri množenju matrike in vektorja, je mogoče dobiti vzporedne metode za reševanje problema na podlagi algoritmov vzporednega seštevanja (glej odstavek 4.1). V tem razdelku bo analiza metod paralelizacije dopolnjena z obravnavo vprašanj organizacije vzporednega računalništva glede na število procesorjev, ki so na voljo za uporabo. Poleg tega bo na primeru problema množenja matrike z vektorjem opozorjena na potrebo po izbiri najprimernejše topologije računalniškega sistema (obstoječi komunikacijski kanali med procesorji), da se zmanjšajo stroški za organizacijo medprocesorske interakcije.

Doseganje najvišje možne učinkovitosti ()

Analizirajmo informacijske odvisnosti v algoritmu množenja matričnih vektorjev, da izberemo možne metode paralelizacije. Kot lahko vidite, so operacije množenja posameznih vrstic matrike z vektorjem, izvedene med izračuni, neodvisne in jih je mogoče izvajati vzporedno;

Množenje vsake vrstice z vektorjem vključuje neodvisne operacije množenja elementov in se lahko izvaja tudi vzporedno;

Seštevanje dobljenih produktov pri vsaki operaciji množenja vrstice matrike z vektorjem se lahko izvede z uporabo ene od predhodno obravnavanih različic algoritma seštevanja (zaporedni algoritem, običajne in modificirane kaskadne sheme).

Tako je največje potrebno število procesorjev določeno z vrednostjo

Uporabo takšnega števila procesorjev lahko predstavimo na naslednji način. Številni procesorji so razdeljeni v skupine

od katerih vsaka predstavlja nabor procesorjev za izvedbo operacije množenja posamezne vrstice matrike z vektorjem. Na začetku izračunov se vsakemu procesorju v skupini pošlje element matrične vrstice in ustrezen vektorski element. Nato vsak procesor izvede operacijo množenja. Naslednji izračuni se nato izvedejo z uporabo sheme kaskadnega seštevanja. Za ponazoritev na sl. 6.1 prikazuje računsko shemo za procesorje skupine z matrično dimenzijo .

riž. 6.1. Računska shema za množenje matrične vrstice z vektorjem

Čas izvajanja vzporednega algoritma pri uporabi procesorjev je določen s časom izvajanja operacije vzporednega množenja in časom izvajanja kaskadnega vezja

Posledično so kazalniki učinkovitosti algoritma določeni z naslednjimi razmerji:

, ,

Za obravnavani problem množenja matričnih vektorjev so najprimernejše topologije strukture, ki zagotavljajo hiter prenos podatkov (poti enotne dolžine) v kaskadnem seštevalnem vezju (glej sliko 4.5). Takšne topologije so strukture s popolnim sistemom povezav ( celoten graf) In hiperkocka. Druge topologije povzročajo daljši komunikacijski čas zaradi daljših poti prenosa podatkov. Tako z linearnim urejanjem procesorjev s sistemom povezav samo z najbližjimi sosedi na levi in desni ( vladar oz prstan) za kaskadno shemo je dolžina prenosne poti vsake prejete delne vsote pri ponovitvi , , enaka . Če predpostavimo, da prenos podatkov po dolžini poti v topologijah z linearno strukturo zahteva operacije prenosa podatkov, je skupno število vzporednih operacij (skupno trajanje poti) prenosa podatkov določeno z vrednostjo

(razen prenosov podatkov za začetno nalaganje procesorjev).

Uporaba računalniškega sistema s pravokotno topologijo dvodimenzionalna mreža velikost vodi do preproste in jasne interpretacije izvedenih izračunov (struktura omrežja ustreza strukturi obdelanih podatkov). Za takšno topologijo je najbolj priporočljivo postaviti matrične vrstice vzdolž vodoravnih mrež; v tem primeru morajo biti elementi vektorja razporejeni po vertikalah računalniškega sistema. Izračuni s to razporeditvijo podatkov se lahko izvajajo vzporedno vzdolž mrežnih črt; posledično se skupno število prenosov podatkov ujema z rezultati za ravnilo().

Komunikacijska dejanja, ki se izvajajo pri reševanju dane naloge, so sestavljena iz prenosa podatkov med pari procesorjev MCS. Podrobna analiza trajanja izvajanja takih operacij je izvedena v odstavku 3.3.

4. Priporočila za implementacijo vzporednega algoritma. Pri izvajanju vzporednega algoritma je priporočljivo poudariti začetno stopnjo nalaganja uporabljenih procesorjev z začetnimi podatki. Najpreprosteje je taka inicializacija zagotovljena s topologijo računalniškega sistema s topologijo v obliki celoten graf(prenos je zagotovljen z eno operacijo vzporednega prenosa podatkov). Pri organizaciji več procesorjev v obliki hiperkocka Morda bi bilo koristno imeti dvonivojski nadzor procesa zagona, pri katerem osrednji krmilni procesor zagotavlja, da se matrične in vektorske vrstice pošljejo krmilnim procesorjem procesorskih skupin, ti pa pošiljajo elemente matrike in vektorske vrstice v izvršne procesorje. Za topologije v obliki vladarji oz prstani zahteva zaporedne operacije prenosa podatkov z zaporedno padajočo količino podatkov, prenesenih iz na elemente.

Uporaba paralelizma srednje ravni ()

1. Izbira metode vzporednega računanja. Ko se razpoložljivo število uporabljenih procesorjev () zmanjša, običajna shema kaskadnega seštevanja pri izvajanju operacij množenja matričnih vrstic z vektorjem postane neuporabna. Za poenostavitev predstavitve gradiva predpostavimo in uporabimo spremenjeno kaskadno shemo. Začetna obremenitev vsakega procesorja se v tem primeru poveča in procesor je obremenjen () z deli vrstic matrike in vektorja. Čas izvajanja operacije množenja matrike z vektorjem lahko ocenimo kot

Pri uporabi števila procesorjev, potrebnih za implementacijo spremenjene kaskadne sheme, tj. pri , ta izraz daje oceno časa izvajanja (pri ).

Ko je število procesorjev , ko je čas izvajanja algoritma ocenjen na , se lahko predlaga nova shema za vzporedno izvajanje izračunov, v kateri za vsako ponovitev kaskadnega seštevanja, nabori procesorjev, ki se ne prekrivajo. S tem pristopom se izkaže, da je razpoložljivo število procesorjev dovolj za izvedbo samo ene operacije množenja matrične vrstice in vektorja. Poleg tega so pri izvajanju naslednje ponovitve kaskadnega seštevanja procesorji, ki so odgovorni za izvajanje vseh prejšnjih ponovitev, prosti. Vendar pa je to pomanjkljivost predlaganega pristopa mogoče spremeniti v prednost z uporabo nedejavnih procesorjev za obdelavo naslednjih vrstic matrike. Kot rezultat se lahko oblikuje naslednja shema tekoči trak izvajanje matričnega in vektorskega množenja:

Niz procesorjev je razdeljen na ločene skupine procesorjev

v tem primeru je skupina , , sestavljena iz procesorjev in se uporablja za izvajanje iteracij kaskadnega algoritma (skupina se uporablja za izvajanje elementnega množenja); skupno število procesorjev;

Inicializacija izračunov je sestavljena iz nalaganja procesorjev skupine po elementih z vrednostmi 1 vrstice matrike in vektorja; po začetnem nalaganju se izvede vzporedna operacija elementnega množenja in kasnejša izvedba običajnega kaskadnega seštevalnega vezja;

Pri izvajanju izračunov se vsakič po končani operaciji elementnega množenja v procesorje skupine naložijo elementi naslednje vrstice matrike in sproži se računski proces za novo naložene podatke.

Kot rezultat uporabe opisanega algoritma mnogi procesorji implementirajo cevovod za izvajanje operacije množenja vrstice matrike z vektorjem. Na takem transporterju je lahko hkrati več ločenih vrst matrice na različnih stopnjah obdelave. Tako bodo na primer po elementnem množenju elementov prve vrstice in vektorja procesorji skupine izvedli prvo iteracijo kaskadnega algoritma za prvo vrstico matrike, procesorji skupine pa bodo izvedite elementno množenje vrednosti druge vrstice matrike itd. Za ponazoritev na sl. 6.2 prikazuje stanje procesa izračuna po 2 ponovitvah cevovoda pri .

riž. 6.2. Stanje cevovoda za operacijo množenja vrstice matrike z vektorjem po zaključku 2 ponovitev

2. Vrednotenje indikatorjev uspešnosti algoritma. Množenje prve vrstice z vektorjem po kaskadni shemi bo zaključeno kot običajno po izvedbi () vzporednih operacij. Za druge vrstice - v skladu s shemo cevovoda organiziranja izračunov - se bodo rezultati množenja vsake naslednje vrstice pojavili po zaključku vsake naslednje ponovitve cevovoda. Posledično lahko skupni čas izvajanja operacije množenja matrike in vektorja izrazimo kot

Ta ocena je nekoliko daljša od časa izvajanja vzporednega algoritma, opisanega v prejšnjem odstavku (), vendar pa na novo predlagana metoda zahteva manj prenesenih podatkov (vektor je poslan le enkrat). Poleg tega uporaba cevovodne sheme vodi do zgodnejšega pojava nekaterih računskih rezultatov (kar je lahko koristno v številnih situacijah obdelave podatkov).

Posledično so kazalniki učinkovitosti algoritma določeni z naslednjimi razmerji:

3. Izbira topologije računalniškega sistema. Ustrezno topologijo računalniškega sistema v celoti določa računalniško vezje – to je popolno binarno drevo višina Število prenosov podatkov s takšno topologijo omrežja je določeno s skupnim številom iteracij, ki jih izvede cevovod, tj.

Inicializacija izračunov se začne z listi drevesa, rezultati seštevanja se kopičijo v korenskem procesorju.

Analiza kompleksnosti izvedenih komunikacijskih dejanj za računalniške sisteme z drugimi topologijami medprocesorskih komunikacij naj bi bila izvedena kot samostojna naloga (glej tudi klavzulo 3.4).

Organizacija vzporednega računanja ko

1. Izbira metode vzporednega računanja. Pri uporabi procesorjev za množenje matrike z vektorjem je mogoče uporabiti vzporedni algoritem množenja vrstica za vrstico, ki je bil prej obravnavan v priročniku, pri katerem so vrstice matrike porazdeljene med procesorji vrstico za vrstico in vsak procesor izvaja operacija množenja katere koli posamezne vrstice matrike z vektorjem. Drug možen način za organizacijo vzporednega računalništva bi lahko bila gradnja cevovodno vezje za operacijo množenja matrične vrstice z vektorjem(skalarni produkt vektorjev) z razporeditvijo vseh razpoložljivih procesorjev v linearno zaporedje ( vladarji).

Takšno shemo izračuna lahko definiramo na naslednji način. Predstavljajmo si množico procesorjev kot linearno zaporedje (glej sliko 4.7):

Vsak procesor, , se uporablja za množenje elementov stolpca matrike in vektorskega elementa. Izvajanje izračunov na vsakem procesorju , , je naslednje:

Zahtevan je naslednji element stolpca matrike;

Elementi in se pomnožijo;

Zahteva se rezultat izračunov prejšnjega procesorja;

Vrednosti so dodane;

Nastali rezultat se pošlje naslednjemu procesorju.

riž. 6.3. Stanje linearnega cevovoda za operacijo množenja vrstice matrike z vektorjem po izvedbi dveh ponovitev

Pri inicializaciji opisane sheme morate izvesti številna dodatna dejanja:

Pri izvedbi prve iteracije vsak procesor dodatno zahteva element vektorja;

Za sinhronizacijo izračunov (pri izvajanju naslednje ponovitve vezja se zahteva rezultat izračuna prejšnjega procesorja) na stopnji inicializacije procesor izvede () čakalno zanko.

Poleg tega je za homogenost opisane sheme za prvi procesor, ki nima predhodnega procesorja, priporočljivo uvesti prazno operacijo dodajanja ( ).

Za ponazoritev na sl. Slika 6.3 prikazuje stanje računskega procesa po drugi ponovitvi cevovoda pri .

2. Vrednotenje indikatorjev uspešnosti algoritma. Množenje prve vrstice z vektorjem po opisani cevovodni shemi bo končano po izvedbi () vzporednih operacij. Rezultat množenja naslednjih vrstic se bo pojavil po zaključku vsake naslednje ponovitve cevovoda (spomnimo se, da ponovitev vsakega procesorja vključuje izvajanje operacij množenja in seštevanja). Posledično lahko skupni čas izvajanja operacije množenja matričnih vektorjev izrazimo kot:

Ta ocena je tudi večja od minimalnega možnega časa izvajanja vzporednega algoritma pri . Uporabnost uporabe cevovodne računalniške sheme je, kot je navedeno v prejšnjem odstavku, v zmanjšanju količine prenesenih podatkov in v zgodnejšem pojavu nekaterih rezultatov izračuna.

Kazalnike učinkovitosti te računske sheme določajo razmerja:

, ,

3. Izbira topologije računalniškega sistema. Potrebna topologija računalniškega sistema za izvajanje opisanega algoritma je enolično določena s predlagano računalniško shemo - to je linearno urejen niz procesorjev ( vladar).

Uporaba omejenega nabora procesorjev ()

1. Izbira metode vzporednega računanja. Z zmanjšanjem števila procesorjev na vrednost je mogoče dobiti vzporedno računalniško shemo za množenje matričnih vektorjev s prilagajanjem algoritma množenja vrstica za vrstico. V tem primeru se kaskadno vezje za seštevanje rezultatov elementnega množenja degenerira in operacija množenja matrične vrstice z vektorjem se v celoti izvede na enem samem procesorju. Računalniško shemo, pridobljeno s tem pristopom, je mogoče specificirati na naslednji način:

Vektor in matrične vrstice se pošljejo vsakemu od razpoložljivih procesorjev;

Izvajanje operacije množenja vrstice matričnega vektorja se izvede z uporabo običajnega zaporednega algoritma.

Upoštevati je treba, da velikost matrike morda ni večkratnik števila procesorjev in potem vrstic matrike ni mogoče enakomerno razdeliti med procesorje. V teh situacijah lahko odstopate od zahteve po enakomerni obremenitvi procesorjev in za enostavnejšo računsko shemo sprejmete pravilo, da se podatki na procesorje postavljajo le vrstico za vrstico (tj. elementi ene vrstice matrike ne morejo razdeliti med več procesorjev). Neenako število vrstic povzroči različno računsko obremenitev procesorjev; Tako bo dokončanje izračunov (skupno trajanje reševanja problema) odvisno od časa delovanja najbolj obremenjenega procesorja (v tem primeru lahko del tega skupnega časa posamezni procesorji mirujejo zaradi izčrpanosti svojega deleža). izračunov). Neenakomerna obremenitev procesorjev zmanjšuje učinkovitost uporabe MCS in na podlagi tega primera lahko sklepamo, da težava z uravnoteženjem

3. Izbira topologije računalniškega sistema. V skladu z naravo medprocesorskih interakcij, ki se izvajajo v predlagani računalniški shemi, je organizacija procesorjev v obliki zvezde(glej sliko 1.1). Krmilni procesor takšne topologije se lahko uporablja za nalaganje računalniških procesorjev z začetnimi podatki in sprejemanje rezultatov izvedenih izračunov.

Matrično množenje

Problem množenja matrike na matriko definirajo razmerja

(zaradi poenostavitve predstavitve bomo predpostavili, da sta pomnoženi matriki in kvadratni in imata vrstni red ).

Analizo možnih metod za vzporedno izvajanje te naloge lahko izvedemo po analogiji z obravnavo problema množenja matrike z vektorjem. Če pustimo takšno analizo za neodvisno študijo, bomo na primeru problema množenja matrik prikazali uporabo več splošnih pristopov, ki nam omogočajo oblikovanje vzporednih metod za reševanje kompleksnih problemov.