Množenje kvadratne matrike z vektorjem. Množenje kompleksnega vektorja z matriko

12.09.202227.05.2017

Sistem MatLab preprosto izvaja matematične operacije na matricah in vektorjih. Najprej razmislite o preprostih operacijah seštevanja in množenja matrik in vektorjev. Naj sta dana dva vektorja

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

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

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

V skladu z operacijami na vektorjih množenje vektorja vrstice z vektorjem stolpca da š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 je zapisano kot

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 izdal sporočilo o napaki, ker vektorjev različnih tipov ni mogoče dodati. Tako je pri vseh nedovoljenih aritmetičnih operacijah: če jih ni mogoče izračunati, bo sistem MatLab javil napako in program se bo končal v ustrezni vrstici.

Podobno se izvajajo operacije množenja in seštevanja med matricami:

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
% transponirati vrstični vektor a.
A = ; % matrika 3x3 elementi
B = a*A; %b= - vrstični vektor
C=A*b; % C = - stolpčni vektor
D = a*A*a'; % D = 45 – število, vsota matrike A
E = A'; % E je transponirana matrika A
F = inv(A); % F - inverzna matrika A
G = A^-1; % G - inverzna matrika A

Iz zgornjega primera je razvidno, da operacijo transponiranja matrik in vektorjev označujemo s simbolom ‘ (apostrof), ki se postavi za imenom vektorja ali matrike. Izračun inverzne matrike lahko izvedete 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 narejeni dve metodi izračuna.

Če je med izračuni potrebno pomnožiti, deliti ali povečati elemente vektorja ali matričnega elementa za elementom, se za to uporabljajo naslednji operaterji:

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

Razmislite o delovanju teh operaterjev v naslednjem primeru.

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

Za zaključek tega razdelka razmislite o nekaj funkcijah, ki so uporabne pri delu z vektorji in matricami.

Za iskanje največje vrednosti vektorskega elementa se uporablja standardna funkcija 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 tako največja vrednost elementa kot njegov indeks v vektorju, v drugem pa samo največja vrednost elementa.

V primeru matrik ta funkcija določa 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 vektorskega ali matričnega elementa 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 po stolpcih, nato pa po 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 = sort(A); %B1=
B2 = sort(A, 'descend'); %B2=

V številnih praktičnih problemih je pogosto potrebno 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 zgornjem primeru simbol '==' pomeni preverjanje enakosti, simbol '~=' pa preverja neenakost vrednosti elementov vektorja a. Več podrobnosti o teh operatorjih bo opisanih v razdelku o pogojnih operatorjih.

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

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

Definicija 1

Zmnožek matrik (C=AB) je operacija samo za konsistentni matriki A in B, v katerih je število stolpcev matrike A enako številu vrstic matrike B:

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

Primer 1

Matrični podatki:

A = a (i j) dimenzij m × n;
B = b (i j) 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 matrik:

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 B A sta najdena, vendar sta matriki različnih velikosti: A B ni enako B A.

Lastnosti množenja matrik

Lastnosti množenja matrik:

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

Primer 1

Preverite lastnost #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) \u003d 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 \u003d 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 \u003d 19 22 43 50 + 1 4 3 8 \u003d 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 poiščite najprej 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.

ena). A B \u003d 4 3 7 5 × - 28 93 38 - 126 \u003d 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 .

Uporabljamo formulo A B C \u003d (A B) C:

ena). 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 \u003d (A B) C \u003d 7 3 2 1 - 10 9 14 - 12 \u003d 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 \u003d A k enake velikosti, ki jo dobimo iz izvirnika z množenjem z danim številom vseh njenih elementov:

b i , j = k × a i , j

Lastnosti množenja matrike s številom:

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

Primer 4

Poiščite produkt matrike A \u003d 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 po pravilu 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 c 2 ⋯ c 1 m

če matriko pomnožite z vrstičnim vektorjem, mora biti matrika, ki jo želite pomnožiti, 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ščite produkt matrike A in vektorja stolpca B:

A B \u003d 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 \u003d 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ščite produkt matrike A in vrstičnega vektorja B:

A \u003d 3 2 0 - 1, B \u003d - 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 \u003d - 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

Torej, v prejšnji lekciji smo analizirali 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 morate s predhodnimi definicijami.

Konsistentne matrike

Ena najpomembnejših značilnosti matrice je njena velikost. O tem smo že stokrat govorili: $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 je število stolpcev v prvi matriki enako število vrstic v drugem, se imenujejo dosledni.

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

Zanima nas 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 je, kot je bilo, ne 3 vrstice v drugi).
Doslednost je enostavno preveriti, če eno za drugo izpišete vse dimenzije. Na primeru iz prejšnjega odstavka: "3 2 2 5" - enaka števila so na sredini, zato sta matriki skladni. Toda "2 5 3 2" se ne strinja, ker so na sredini različne številke.

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

V matematiki, ko je pomemben vrstni red oštevilčevanja objektov (npr. v zgoraj obravnavani definiciji je pomemben vrstni red matrik), pogosto govorimo o urejenih parih. Spoznali smo jih 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: tudi koordinate so urejeni pari, ki so sestavljeni iz števil. Toda nič vam ne preprečuje, da bi naredili tak par matric. Potem bo mogoče reči: "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 definiramo jim operacijo množenja.

Opredelitev. Produkt dveh konsistentnih 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$.

Za tiste, ki to definicijo vidijo prvič, se takoj pojavita dve vprašanji:

Kakšna divjad 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))$ (posebej postavite podpičje med indekse, da se ne zamenjate, vendar vam jih ni treba vstaviti splošno - sam sem se naveličal vnašati formulo v definicijo) se v resnici skrči na preprosto pravilo:

Vzemite $i$-to vrstico v prvi matriki;
Vzemite $j$-ti 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 za vse $1\le i\le m$ in $1\le j\le k$. Tisti. skupaj bo $m\krat k$ takih "perverzij".

Pravzaprav smo se z matričnim množenjem že srečali v šolskem kurikulumu, le da 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). \\ \end(align)\]

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))\]

Pravzaprav smo v tistih daljnih letih, ko so bila drevesa bolj zelena in nebo svetlejše, preprosto pomnožili vrstični vektor $\overrightarrow(a)$ s stolpčnim vektorjem $\overrightarrow(b)$.

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

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

Množenje kvadratnih matrik

Naloga 1. Izvedite 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). Torej 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 \\\konec(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) \desno]= \\ & =\levo[ \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. Izvedite 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 zgornjih 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 naslikali, katera števila so vključena v določeno celico. Prav to je treba storiti pri reševanju resničnih problemov.

Osnovne lastnosti produkta matrike

Na kratko. Matrično množenje:

Nekomutativno: $A\cdot B\ne B\cdot A$ na splošno. 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)$. Tu 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 $

In zdaj - vse enako, vendar bolj podrobno.

Matrično množenje je zelo 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 razmislimo o matricah 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(matrika) \\\end(matrika) \right]=\left[ \begin(matrika) -14 & 4 \\ 0 & 10 \\\end(matrika )\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 bosta ostali skladni, če se zamenjajo. Na primer, matriki $\left[ 2\times 3 \right]$ in $\left[ 3\times 5 \right]$ sta precej dosledni v tem vrstnem redu, vendar enaki matriki $\left[ 3\times 5 \ desno] $ in $\left[ 2\krat 3 \desno]$, zapisana v obratnem vrstnem redu, se ne ujemata več. žalost :(

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 pred časom: povsem možno je, da nekatere sosednje matrike, ko se pomnožijo, dajo zanimiv rezultat. Na primer ničelna matrika, kot je opisana v problemu 2 zgoraj.

V realnih problemih je treba 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 vsekakor 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 enote, v vseh ostalih celicah pa ničle.

\[\begin(align) & A\cdot \left(B+C \desno)=A\cdot B+A\cdot C; \\ & \left(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 je običajno treba izvesti inverzno operacijo: opazimo isto matriko, jo vzamemo iz oklepaja, izvedemo seštevanje in si s tem poenostavimo življenje. :)

Upoštevajte, da smo morali za opis distributivnosti napisati dve formuli: kjer je vsota v drugem faktorju in kjer je vsota v prvem. To je ravno zaradi dejstva, da je matrično množenje nekomutativno (in na splošno je v nekomutativni algebri veliko najrazličnejših šal, ki sploh ne pridejo na misel pri delu z navadnimi številkami). In če morate na primer med izpitom zapisati to lastnost, potem obvezno napišite obe formuli, sicer se lahko učitelj nekoliko razjezi.

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

Primer pravokotnih matrik

A nič – vse je tako kot pri kvadratnih.

Naloga 3. Izvedite 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]$. V vrsto zapišimo številke, ki označujejo velikosti:

Kot lahko vidite, sta osrednji dve številki enaki. To pomeni, da so matrike konsistentne in jih je mogoče množiti. In 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 razmislite o eni najboljših nalog za usposabljanje za tiste, ki šele začenjajo delati z matricami. V njej vam ni treba samo pomnožiti nekaj dveh tablet, ampak najprej ugotoviti: ali je takšno množenje dovoljeno?

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

\\]; $B=\levo[ \začetek(matrika) \začetek(matrika) 0 \\ 2 \\ 0 \\ 4 \\\konec(matrika) & \začetek(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 dimenzije matrik:

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

Dobimo, da se matrika $A$ lahko ujema le z matriko $B$, saj je število stolpcev v $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 izvede sam. 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 »prehodne« koeficiente, ki so zagotavljali konsistentnost matrik.

Katere druge možnosti so možne? Zagotovo je mogoče najti $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 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 lahko ujemate tudi $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 razviti vse ključne korake pri matričnem množenju.

A zgodba se tu ne konča. Pojdimo k posebnim primerom 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 $\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 se s temi predmeti ž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. Pomnoži:

\[\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. Imamo produkt konsistentnih matrik: $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Poiščite ta del:

\[\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. Izvedite 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 skladno: $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. Upoštevamo delo:

\[\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, je pri množenju vektorja vrstice in vektorja stolpca s kvadratno matriko rezultat vedno vrstica ali stolpec enake velikosti. To dejstvo ima veliko aplikacij - od reševanja linearnih enačb do najrazličnejših transformacij koordinat (ki na koncu pridejo tudi do sistemov enačb, a da ne govorimo o žalostnih stvareh).

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, tudi te je mogoče dvigniti na različne stopnje.

Takšna dela so vedno usklajena:

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

In so označeni na 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)). \\ \end(align)\]

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

Naloga 7. Dvignite matriko na določeno moč:

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

rešitev. V redu, gradimo. Najprej 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 določeno moč:

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

rešitev. Samo ne jokajte zdaj o tem, da je "diploma previsoka", "svet ni pravičen" in "učitelji so popolnoma izgubili brege". Pravzaprav je vse enostavno:

\[\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 še zdaleč ni vedno mogoče ujeti takšnih vzorcev pri dvigu na potenco. Zato bodite previdni: pogosto je lažje in hitreje pomnožiti več matrik "na prazno", kot pa tam iskati neke vzorce.

Na splošno ne iščite višjega smisla tam, kjer ga ni. Nazadnje si oglejmo še potenciranje večje matrike - toliko kot $\left[ 3\times 3 \right]$.

Problem 9. Dvignite matriko na določeno moč:

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

rešitev. Ne iščimo vzorcev. Delamo "skozi":

\[((\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]\]

Začnimo s kvadriranjem te matrike:

\[\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 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 rešen.

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

Kot lahko vidite, se je število izračunov povečalo, vendar se pomen ni nič spremenil. :)

Ta lekcija se lahko konča. Naslednjič bomo razmislili o inverzni operaciji: prvotne množitelje bomo iskali z obstoječim produktom.

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

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

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

Torej, da bi pomnožili matriko z vektorjem, moramo vektor obravnavati kot vektor stolpca. Pri množenju vektorja z matriko ga je treba obravnavati kot vektor vrstice.

množna matrika

na kompleksni vektor

Dobimo rezultat

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

Rad bi vas opozoril na dejstvo, da je matrika v prvi in drugi različici kljub enakim vrednostim popolnoma drugačna (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 zmnožek vektorja in matrike.

Ta bot tudi množi vektorje in matrike, ki imajo kompleksne vrednosti. Na podlagi popolnejšega kalkulatorja Množenje matrik 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 z matriko je enak vsoti produktov vektorjev z matriko

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

4. Zmnožek vrstičnega vektorja z zmnožkom matrike in stolpčnega vektorja je enakovreden zmnožku vrstičnega vektorja z matriko in stolpčnim vektorjem.

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. Dosežite najvišjo možno hitrost. Uporaba paralelizma na srednji ravni. Organizacija vzporednega računanja za 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 iste vrste operacij za množenje vrstic matrike in vektorja. Pridobivanje vsake take operacije vključuje poelementno množenje elementov vrstice matrike in vektorja ter naknadno seštevanje dobljenih produktov. Skupno število zahtevanih skalarnih operacij je ocenjeno z vrednostjo

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 poglavju bo analiza paralelizacijskih metod dopolnjena z obravnavo 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 najhitrejšega možnega delovanja ()

Opravimo analizo informacijskih odvisnosti v algoritmu množenja matrike in vektorja, da izberemo možne načine 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 neodvisna elementna množenja in se lahko izvede tudi vzporedno;

Seštevanje produktov, dobljenih pri vsaki operaciji množenja vrstice matrike z vektorjem, se lahko izvede z uporabo ene od predhodno obravnavanih različic algoritma seštevanja (serijski 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. Nabor procesorjev je razdeljen na skupine

od katerih vsaka predstavlja nabor procesorjev za izvajanje operacije množenja ene same vrstice matrike z vektorjem. Na začetku izračunov vsak procesor skupine prejme element vrstice matrike in ustrezen element vektorja. Nato vsak procesor izvede operacijo množenja. Naknadni izračuni se izvajajo po shemi kaskadnega seštevanja. Za ponazoritev na sl. 6.1 prikazuje računsko shemo za procesorje skupine z dimenzijo matrike .

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 kaskadne sheme.

Posledično so kazalniki uspešnosti algoritma določeni z naslednjimi razmerji:

Za obravnavani problem množenja matrike z vektorjem so najprimernejše topologije strukture, ki zagotavljajo hiter prenos podatkov (poti enotne dolžine) v shemi kaskadnega seštevanja (glej sliko 4.5). Takšne topologije so strukture s popolnim sistemom povezav ( celoten graf) in hiperkocka. Druge topologije povzročijo daljši komunikacijski čas zaradi daljših podatkovnih poti. Torej, z linearnim vrstnim redom procesorjev s sistemom povezav samo z najbližjimi sosedi na levi in na desni ( vladar oz prstan) za kaskadno shemo je dolžina prenosne poti vsake prejete delne vsote pri iteraciji , , enaka . Če sprejmemo, da prenos podatkov po dolžini poti v topologijah z linearno strukturo zahteva izvedbo operacij prenosa podatkov, je skupno število vzporednih operacij (skupna dolžina poti) prenosa podatkov določeno z vrednostjo

(brez prenosov podatkov za zagonske procesorje).

Uporaba računalniškega sistema s pravokotno topologijo dvodimenzionalna mreža velikost vodi do preproste in vizualne interpretacije izvedenih izračunov (struktura omrežja ustreza strukturi obdelanih podatkov). Za takšno topologijo je najbolj smotrno, da vrstice matrike postavimo vzdolž vodoravnih linij mreže; v tem primeru je treba elemente vektorja poslati po vertikalah računalniškega sistema. Izvedba izračunov s to razporeditvijo podatkov se lahko izvede vzporedno vzdolž črt mreže; posledično je skupno število prenosov podatkov enako rezultatom za ravnilo().

Komunikacijska dejanja, ki se izvajajo pri reševanju problema, so prenos 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 izpostaviti začetno stopnjo nalaganja uporabljenih procesorjev z začetnimi podatki. Takšno inicializacijo najpreprosteje zagotovimo za topologijo računalniškega sistema s topologijo v obliki celoten graf(nalaganje je zagotovljeno z eno samo operacijo vzporednega prenosa podatkov). Pri organizaciji nabora procesorjev v obliki hiperkocka Morda bi bilo koristno imeti dvonivojsko kontrolo zagonskega procesa, pri katerem osrednji krmilni procesor distribuira matrične in vektorske vrstice krmilnim procesorjem procesorskih skupin , , ki nato distribuirajo elemente matrike in vektorja vrstic do izvršnih procesorjev. Za topologije v obliki vladarji oz prstani potrebne so zaporedne operacije prenosa podatkov z zaporedno padajočo količino podatkov, prenesenih iz elementov v.

Uporaba paralelizma srednje ravni ()

1. Izbira metode vzporednega računanja. Z zmanjšanjem razpoložljivega števila uporabljenih procesorjev () postane običajna shema kaskadnega seštevanja pri izvajanju operacij množenja matričnih vrstic z vektorjem neuporabna. Za enostavno predstavitev gradiva predpostavljamo in uporabljamo 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 vrednost

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

S številom procesorjev , ko je čas izvajanja algoritma ocenjen na , je mogoče predlagati novo shemo za vzporedno izvajanje izračunov, v kateri se za vsako ponovitev uporabi kaskadno seštevanje nabori procesorjev, ki se ne prekrivajo. S tem pristopom je razpoložljivo število procesorjev dovolj za izvedbo samo ene operacije množenja vrstice matrike in vektorja. Poleg tega so pri naslednji ponovitvi kaskadnega seštevanja procesorji, odgovorni za izvedbo vseh predhodnih 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 izvedite matrično in vektorsko množenje:

Nabor procesorjev je razdeljen na skupine procesorjev, ki se ne prekrivajo

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

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

Pri izvajanju izračunov se vsakič po zaključku operacije poelementnega 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 množica procesorjev implementira cevovod za izvajanje operacije množenja matrične vrstice z vektorjem. Na takem cevovodu je lahko več posameznih vrstic matrike hkrati na različnih stopnjah obdelave. Tako bodo na primer po elementnem množenju elementov prve vrstice in vektorja skupinski procesorji izvedli prvo iteracijo kaskadnega algoritma za prvo vrstico matrike, skupinski procesorji pa element -modro množenje vrednosti druge vrstice matrike itd. Za ponazoritev na sl. 6.2 prikazuje stanje računskega procesa po 2 ponovitvah cevovoda pri .

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

2. Vrednotenje indikatorjev uspešnosti algoritma. Množenje prve vrstice z vektorjem po kaskadni shemi bo končano, kot običajno, po izvedbi () vzporednih operacij. Za druge vrstice se bodo v skladu s cevovodno shemo organizacije izračunov 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 na novo predlagana metoda zahteva manj podatkov za prenos (vektor je poslan samo enkrat). Poleg tega uporaba sheme cevovoda povzroči zgodnejši prikaz nekaterih rezultatov izračuna (kar je lahko uporabno v številnih situacijah obdelave podatkov).

Posledično so kazalniki uspešnosti 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ška shema - to je popolna 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 od listov drevesa, rezultati seštevanja se kopičijo v korenskem procesorju.

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

Organizacija vzporednega računalništva z

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 že obravnavan v priročniku, pri katerem so vrstice matrike porazdeljene vrstico za vrstico med procesorji in vsak procesor izvaja operacijo množenja katere koli posamezne vrstice matrike z vektorjem . Drug možen način organiziranja vzporednega računalništva je lahko gradnja cevovodna shema za operacijo množenja vrstice matrike z vektorjem(pikčasti produkt vektorjev) z razporeditvijo vseh razpoložljivih procesorjev v linearno zaporedje ( vladarji).

Takšno shemo izračuna lahko definiramo na naslednji način. Predstavimo nabor procesorjev kot linearno zaporedje (glej sliko 4.7):

vsak procesor se uporablja za množenje elementov stolpca matrike in vektorskega elementa. Izvedba izračunov na vsakem procesorju , , je sestavljena iz naslednjega:

Zahtevan je naslednji element stolpca matrike;

Elementi in se pomnožijo;

Zahteva se rezultat izračunov prejšnjega procesorja;

Vrednosti so dodane;

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 je potrebno izvesti številna dodatna dejanja:

Med prvo iteracijo vsak procesor dodatno zahteva element vektorja;

Za sinhronizacijo izračunov (med izvajanjem naslednje ponovitve vezja se zahteva rezultat izračuna predhodnega procesorja) na stopnji inicializacije procesor , , izvede () čakalno zanko.

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

Za ponazoritev na sl. 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, ponovitev vsakega procesorja vključuje izvajanje operacij množenja in seštevanja). Posledično lahko skupni čas izvajanja operacije množenja matričnega vektorja izrazimo kot:

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

Kazalnike uspešnosti te računske sheme določajo razmerja:

, ,

3. Izbira topologije računalniškega sistema. Zahtevano topologijo računalniškega sistema za izvedbo opisanega algoritma enolično določa predlagana računska shema - to je linearno urejen niz procesorjev ( vladar).

Uporaba omejenega nabora procesorjev ()

1. Izbira metode vzporednega računanja. Ko se število procesorjev zmanjša na vrednost, je mogoče dobiti vzporedno računsko shemo za množenje matričnih vektorjev kot rezultat prilagajanja algoritma množenja vrstica za vrstico. V tem primeru se kaskadna shema 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;

Operacija množenja vrstic matrike z vektorjem se izvede z uporabo običajnega zaporednega algoritma.

Upoštevati je treba, da velikost matrike ne sme biti večkratnik števila procesorjev in potem vrstic matrike ni mogoče enakomerno razdeliti med procesorje. V teh situacijah je možno odstopati od zahteve po enotnosti obremenitve procesorja in za enostavnejšo računsko shemo sprejeti pravilo, da se podatki na procesorje postavljajo samo vrstico za vrstico (tj. elementi ene vrstice matrike). ni mogoče deliti med več procesorji). Različno število vrstic povzroči različno računsko obremenitev procesorjev; tako bo dokončanje izračunov (skupno trajanje rešitve naloge) odvisno od časa delovanja najbolj obremenjenega procesorja (hkrati lahko nekateri procesorji del tega skupnega časa mirujejo zaradi izčrpanosti svojega deleža izračuni). 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, izvedenih 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 za sprejemanje rezultatov izvedenih izračunov.

Matrično množenje

Problem množenja matrike z matriko je opredeljen z razmerji

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

Analizo možnih načinov vzporedne izvedbe 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 pokazali uporabo več splošnih pristopov, ki nam omogočajo oblikovanje vzporednih metod za reševanje kompleksnih problemov.