MatLab sustav jednostavno izvodi matematičke operacije na matricama i vektorima. Razmotrimo prvo jednostavne operacije zbrajanja i množenja matrica i vektora. Neka su data dva vektora
a = ; % vektor reda
b = ; % vektor stupca
tada se množenje ova dva vektora može zapisati kao
c = a*b; %c=1+2+3+4+5=16
d = b*a; %d - matrica od 5x5 elemenata
Prema operacijama na vektorima, množenjem vektora retka s vektorom stupcem dobiva se broj, a množenjem vektora stupca s vektorom retka dobiva se dvodimenzionalna matrica, koja je rezultat proračuna u gornjem primjeru, t.j.
Zbrajanje i oduzimanje dva vektora zapisuje se kao
a1 = ;
a2 = ;
c = a1+a2; % c = ;
c = a2-a1; % c = ;
Imajte na umu da se operacije zbrajanja i oduzimanja mogu izvesti između dva vektora stupca ili dva vektora retka. Inače će MatLab izdati poruku o pogrešci, jer ne mogu se dodavati vektori različitih tipova. To je slučaj sa svim nevažećim aritmetičkim operacijama: ako se ne mogu izračunati, MatLab sustav će prijaviti grešku i program će završiti u odgovarajućem retku.
Slično se izvode operacije množenja i zbrajanja između matrica:
A = ;
B = jedinice (3);
C=A+B; % zbrajanja dviju matrica iste veličine
D=A+5; % zbrajanja matrice i broja
E=A*B; % množenje matrice A sa B
F=B*A; % množenje matrice B s A
G=5*A; % množenje matrice brojem
Operacije izračunavanja inverzne matrice, kao i transponiranja matrica i vektora, zapisuju se na sljedeći način:
a = ; % vektor reda
b = a'; % vektor stupca formiran od
% transponiranja vektora retka a.
A = ; % matrica 3x3 elemenata
B = a*A; %b= - vektor reda
C=A*b; % C = - vektor stupca
D = a*A*a'; % D = 45 – broj, zbroj matrice A
E = A'; % E je transponirana matrica A
F = inv(A); % F - inverzna matrica A
G = A^-1; % G - inverzna matrica A
Iz gornjeg primjera može se vidjeti da je operacija transponiranja matrica i vektora označena simbolom ‘ (apostrof), koji se stavlja iza naziva vektora ili matrice. Izračun inverzne matrice može se obaviti pozivanjem funkcije inv() ili podizanjem matrice na -1 stepen. Rezultat će u oba slučaja biti isti, a napravljene su dvije metode izračuna radi lakšeg korištenja pri implementaciji različitih algoritama.
Ako je tijekom izračuna potrebno množiti, podijeliti ili podići elemente vektora ili matrice element po element, tada se za to koriste sljedeći operatori:
.* - množenje po elementima;
./ i .\ - podjele po elementima;
.^ - eksponencijacija po elementima.
Razmotrite rad ovih operatora u sljedećem primjeru.
a = ; % vektor reda
b = ; % vektor reda
c = a.*b; %c=
A = jedinice (3); % 3x3 matrica koja se sastoji od jedinica
B = ; % matrica 3x3
C = A.*B; % matrica 3x3, koja se sastoji od 
D = A./B; % matrica 3x3, koja se sastoji od 
E = A.\B; % matrica 3x3, koja se sastoji od 
F = A.^2; % kvadratura elemenata matrice A
Za kraj ovog odjeljka razmotrite nekoliko funkcija koje su korisne pri radu s vektorima i matricama.
Za pronalaženje maksimalne vrijednosti vektorskog elementa koristi se standardna funkcija max() koja vraća pronađeno maksimalna vrijednost element i njegov položaj (indeks):
a = ;
= max(a); % v = 6, i = 2;
v = max(a); %v = 6;
Ovaj primjer pokazuje dva različiti putevi poziva funkciju max(). U prvom slučaju određuju se i maksimalna vrijednost elementa i njegov indeks u vektoru, a u drugom se određuje samo maksimalna vrijednost elementa.
U slučaju matrica, ova funkcija određuje maksimalne vrijednosti u stupcima, kao što je prikazano u primjeru ispod:
A = ;
= max(A); % V=, I=
V = max(A); %V=
Potpuna sintaksa funkcije max() može se pronaći upisivanjem naredbe u naredbeni prozor MatLab-a
Pomozite<название функции>
Na sličan način radi i funkcija min(), koja određuje minimalnu vrijednost vektorskog ili matričnog elementa i njegov indeks.
Još jedna korisna funkcija za rad s matricama i vektorima je funkcija sum() koja izračunava zbroj vrijednosti elemenata vektora ili stupaca matrice:
a = ;
s = zbroj(a); %s = 3+5+4+2+1=15
A = ;
S1 = zbroj (A); %S1=
S2 = zbroj(zbroj(A)); % S2=39
Prilikom izračunavanja zbroja S2, zbroj vrijednosti elemenata matrice A prvo se izračunava po stupcima, a zatim po recima. Kao rezultat toga, varijabla S2 sadrži zbroj vrijednosti svih elemenata matrice A.
Da biste sortirali vrijednosti elemenata vektora ili matrice uzlaznim ili silaznim redoslijedom, koristite funkciju sort() kako slijedi:
a = ;
b1 = sortiranje (a); %b1=
b2 = sortiranje (a, 'spuštanje'); %b2=
b3 = sortiraj(a, 'uzdizanje'); %b3=
za matrice
A = ;
B1 = sortiranje (A); %B1=
B2 = sortiranje (A, 'spuštanje'); %B2=
U mnogim praktičnim problemima često je potrebno pronaći određeni element u vektoru ili matrici. To se može učiniti pomoću standardne funkcije find() koja kao argument uzima uvjet prema kojem se traže potrebni elementi, na primjer:
a = ;
b1 = pronađi (a == 2); %b1 = 4 - indeks elementa 2
b2 = pronađi (a ~= 2); % b2 = - indeksi bez 2
b3 = pronađi (a > 3); %b3=
U gornjem primjeru, simbol ‘==’ znači provjeru jednakosti, a simbol ‘~=’ vrši provjeru nejednakosti vrijednosti elemenata vektora a. Više pojedinosti o ovim operatorima bit će opisano u odjeljku o uvjetnim operatorima.
Još jedna korisna funkcija za rad s vektorima i matricama je funkcija mean() za izračunavanje aritmetičke sredine, koja radi ovako:
a = ;
m = srednja vrijednost (a); %m = 3
A = ;
M1 = srednja vrijednost (A); %M1=
M2 = srednja vrijednost (srednja (A)); % M2 = 4,333
Svaki se vektor može promatrati kao matrica od jednog stupca ili jednog reda. Matrica s jednim stupcem zvati će se vektor stupca, a matrica s jednim redom zvati će se vektor redaka.
Ako je A matrica veličine m*n, tada vektor stupca b ima veličinu n, a vektor reda b ima veličinu m.
Dakle, da bi se matrica pomnožila s vektorom, vektor se mora tretirati kao vektor stupac. Kada se vektor množi matricom, on se mora tretirati kao vektor reda.
matrica množenja
kompleksnom vektoru
Dobivamo rezultat
Kao što vidite, uz nepromijenjenu dimenziju vektora, možemo imati dva rješenja.
Želio bih vam skrenuti pozornost na činjenicu da je matrica u prvoj i drugoj verziji, unatoč iste vrijednosti, potpuno drugačiji (imaju različite dimenzije)
U prvom slučaju vektor se smatra stupcem i tada je neophodan pomnožiti matricu s vektorom, a u drugom slučaju imamo vektor reda i onda imamo umnožak vektora i matrice.
Ovaj bot također množi vektore i matrice koje imaju složene vrijednosti. Na temelju potpunijeg kalkulatora množenje matrica s kompleksnim vrijednostima na mreži
Svojstva množenja matrice-vektora
Matrica
Vektorski stupac
Vektor reda
proizvoljan broj
1. Umnožak matrice na zbroj vektora stupaca jednak je zbroju proizvoda matrice po svakom od vektora
2. Umnožak zbroja vektora reda po matrici jednak je zbroju proizvoda vektora po matrici
3. Zajednički faktor vektora može se izvaditi iz produkta matrice vektorom / vektor matricom
4. Umnožak vektora retka umnoškom matrice i vektora stupca ekvivalentan je umnošku vektora retka po matrici i vektoru stupca.
Definicija 1Umnožak matrica (C=AB) je operacija samo za konzistentne matrice A i B, u kojoj je broj stupaca matrice A jednak broju redaka matrice B:
C ⏟ m × n = A ⏟ m × p × B ⏟ p × n
Primjer 1
Podaci matrice:
- A = a (i j) dimenzija m × n;
- B = b (i j) p × n
Matrica C, čiji se elementi c i j izračunavaju sljedećom formulom:
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
Primjer 2
Izračunajmo proizvode AB=BA:
A = 1 2 1 0 1 2 , B = 1 0 0 1 1 1
Rješenje pomoću pravila množenja matrice:
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
Pronađeni su umnožak A B i B A, ali to su matrice različitih veličina: A B nije jednako B A.
Svojstva množenja matrice
Svojstva množenja matrice:
- (A B) C = A (B C) - asocijativnost množenja matrice;
- A (B + C) \u003d A B + A C - distributivno množenje;
- (A + B) C \u003d A C + B C - distributivnost množenja;
- λ (A B) = (λ A) B
Provjerite svojstvo #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 .
Primjer 2
Provjeravamo svojstvo br. 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 = 19 22 43 50 + 1 4 3 8 \u003d 20 26 46 58.
Umnožak tri matrice
Umnožak tri matrice A B C izračunava se na 2 načina:
- pronađite A B i pomnožite s C: (A B) C;
- ili pronađite prvo B C, a zatim pomnožite A (B C) .
Pomnožite matrice na 2 načina:
4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1
Algoritam akcije:
- pronaći umnožak 2 matrice;
- zatim ponovno pronađite umnožak 2 matrice.
jedan). 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 .
Koristimo formulu A B C \u003d (A B) C:
jedan). 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 matrice brojem
Definicija 2Umnožak matrice A brojem k je matrica B \u003d A k iste veličine, koja se dobiva iz originala množenjem zadanog broja svih njegovih elemenata:
b i , j = k × a i , j
Svojstva množenja matrice brojem:
- 1 × A = A
- 0 × A = nula matrica
- k(A + B) = kA + kB
- (k + n) A = k A + n A
- (k×n)×A = k(n×A)
Pronađite umnožak matrice A \u003d 4 2 9 0 sa 5.
5 A = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0
Množenje matrice vektorom
Definicija 3Da biste pronašli umnožak matrice i vektora, morate pomnožiti prema pravilu red po stupac:
- ako množite matricu vektorom stupca, broj stupaca u matrici mora odgovarati broju redaka u vektoru stupca;
- rezultat množenja vektora stupca je samo vektor stupca:
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 × 1 × 1 + ⋯ 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 1 m
- ako množite matricu vektorom retka, tada matrica koja se množi mora biti isključivo vektor stupca, a broj stupaca mora odgovarati broju stupaca u vektoru retka:
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 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
Primjer 5
Pronađite umnožak matrice A i vektora stupca 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
Primjer 6
Pronađite umnožak matrice A i vektora retka 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
Ako primijetite grešku u tekstu, označite je i pritisnite Ctrl+Enter
Dakle u prethodna lekcija Analizirali smo pravila za zbrajanje i oduzimanje matrica. To su tako jednostavne operacije da ih većina učenika razumije doslovno odmah.
Međutim, rano se raduješ. Freebie je gotov - prijeđimo na množenje. Odmah ću vas upozoriti: množenje dvije matrice uopće nije množenje brojeva u ćelijama s istim koordinatama, kao što mislite. Ovdje je sve puno zabavnije. I morate početi s preliminarnim definicijama.
Dosljedne matrice
Jedna od najvažnijih karakteristika matrice je njena veličina. Već smo sto puta govorili o tome: $A=\left[ m\times n \right]$ znači da matrica ima točno $m$ redaka i $n$ stupaca. Već smo raspravljali o tome kako ne brkati retke sa stupcima. Sada je važno nešto drugo.
Definicija. Matrice oblika $A=\left[ m\times n \right]$ i $B=\left[ n\times k \right]$, u kojima je broj stupaca u prvoj matrici isti kao broj redaka u drugom, nazivaju se dosljednim.
Još jednom: broj stupaca u prvoj matrici jednak je broju redaka u drugoj! Iz ovoga dobivamo dva zaključka odjednom:
- Mi brinemo o redoslijedu matrica. Na primjer, matrice $A=\left[ 3\times 2 \right]$ i $B=\left[ 2\times 5 \right]$ su konzistentne (2 stupca u prvoj matrici i 2 retka u drugoj) , ali obrnuto — matrice $B=\left[ 2\times 5 \right]$ i $A=\left[ 3\times 2 \right]$ više nisu konzistentne (5 stupaca u prvoj matrici je, kao bilo je, a ne 3 reda u drugom).
- Dosljednost je lako provjeriti ako napišete sve dimenzije jednu za drugom. Koristeći primjer iz prethodnog odlomka: "3 2 2 5" - isti brojevi su u sredini, pa su matrice konzistentne. Ali “2 5 3 2” nije dogovoreno, jer su u sredini različiti brojevi.
Osim toga, čini se da kapetan nagovještava da su kvadratne matrice iste veličine $\left[ n\puta n \right]$ uvijek dosljedne.
U matematici, kada je bitan redoslijed nabrajanja objekata (na primjer, u definiciji o kojoj smo gore govorili, redoslijed matrica je važan), često se govori o uređenim parovima. Upoznali smo ih u školi: mislim da je neozbiljno da koordinate $\left(1;0 \right)$ i $\left(0;1 \right)$ definiraju različite točke na ravnini.
Dakle: koordinate su također uređeni parovi, koji se sastoje od brojeva. Ali ništa vas ne sprječava da napravite takav par matrica. Tada će biti moguće reći: "Uređeni par matrica $\left(A;B \right)$ je konzistentan ako je broj stupaca u prvoj matrici isti kao broj redaka u drugoj. "
Pa, što onda?
Definicija množenja
Razmotrimo dvije konzistentne matrice: $A=\left[ m\times n \right]$ i $B=\left[ n\times k \right]$. I za njih definiramo operaciju množenja.
Definicija. Umnožak dviju konzistentnih matrica $A=\left[ m\times n \right]$ i $B=\left[ n\times k \right]$ je nova matrica $C=\left[ m\times k \ desno] $, čiji se elementi izračunavaju prema 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)\]
Takav proizvod se označava na standardni način: $C=A\cdot B$.
Za one koji prvi put vide ovu definiciju, odmah se postavljaju dva pitanja:
- Kakva je ovo divljač?
- Zašto je tako teško?
Pa, prvo o svemu. Počnimo s prvim pitanjem. Što znače svi ovi indeksi? I kako ne pogriješiti pri radu s pravim matricama?
Prije svega, napominjemo da je dugačak red za izračunavanje $((c)_(i;j))$ (posebno stavite točku i zarez između indeksa kako se ne biste zbunili, ali ih ne morate stavljati općenito - i sam sam se umorio od upisivanja formule u definiciju) zapravo se svodi na jednostavno pravilo:
- Uzmite $i$-ti red u prvoj matrici;
- Uzmite $j$-ti stupac u drugoj matrici;
- Dobivamo dva niza brojeva. Pomnožimo elemente tih nizova s istim brojevima, a zatim dodamo rezultirajuće proizvode.
Ovaj proces je lako razumjeti sa slike:
Shema za množenje dvije matrice Još jednom: popravljamo red $i$ u prvoj matrici, stupac $j$ u drugoj matrici, pomnožimo elemente s istim brojevima, a zatim dodamo rezultirajuće proizvode - dobivamo $((c)_(ij ))$. I tako za sve $1\le i\le m$ i $1\le j\le k$. Oni. bit će $m\puta k$ takvih "perverzija" ukupno.
Zapravo, već smo se susreli s množenjem matrice u školski kurikulum, samo u znatno smanjenom obliku. Neka su dati vektori:
\[\begin(align) & \vec(a)=\left(((x)_(a));((y)_(a));((z)_(a)) \desno); \\ & \overrightarrow(b)=\left(((x)_(b));((y)_(b));((z)_(b)) \desno). \\ \end(poravnati)\]
Tada će njihov skalarni proizvod biti točno zbroj proizvoda u paru:
\[\overrightarrow(a)\times \overrightarrow(b)=((x)_(a))\cdot ((x)_(b))+((y)_(a))\cdot ((y )_(b))+((z)_(a))\cdot ((z)_(b))\]
Zapravo, u tim dalekim godinama, kada je drveće bilo zelenije, a nebo svjetlije, jednostavno smo pomnožili vektor retka $\overrightarrow(a)$ s vektorom stupca $\overrightarrow(b)$.
Danas se ništa nije promijenilo. Samo što sada ima više ovih vektora reda i stupaca.
Ali dosta teorije! Pogledajmo stvarni primjeri. I krenimo s najjednostavnijim slučajem - kvadratnim matricama.
Množenje kvadratnih matrica
Zadatak 1. Izvedite množenje:
\[\left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\kraj (niz) \desno]\]
Odluka. Dakle, imamo dvije matrice: $A=\left[ 2\times 2 \right]$ i $B=\left[ 2\times 2 \right]$. Jasno je da su konzistentne (kvadratne matrice iste veličine uvijek su konzistentne). Zato radimo množenje:
\[\begin(align) & \left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \ početak(niz)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(niz) \desno]=\lijevo[ \begin(niz)(*(35)(r)) 1\cdot \left(-2 \right)+2\cdot 3 & 1\cdot 4+2\cdot 1 \\ -3\cdot \left(-2 \right)+4\cdot 3 & -3\cdot 4+4\cdot 1 \\\end(niz) \desno]= \\ & =\left[ \begin(niz)(*(35)(r)) 4 & 6 \\ 18 & -8 \\\ kraj (niz)\desno]. \end(poravnati)\]
To je sve!
Odgovor: $\left[ \begin(array)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(array) \right]$.
Zadatak 2. Izvedite množenje:
\[\left[ \begin(matrica) 1 & 3 \\ 2 & 6 \\\end(matrica) \right]\cdot \left[ \begin(array)(*(35)(r))9 & 6 \\ -3 & -2 \\\kraj (niz) \desno]\]
Odluka. Opet, konzistentne matrice, pa izvodimo sljedeće radnje:\[\]
\[\begin(poravnati) & \left[ \begin(matrica) 1 & 3 \\ 2 & 6 \\\end(matrica) \desno]\cdot \left[ \begin(array)(*(35)( r)) 9 & 6 \\ -3 & -2 \\\kraj(niz) \desno]=\lijevo[ \begin(niz)(*(35)(r)) 1\cdot 9+3\cdot \ lijevo(-3 \desno) & 1\cdot 6+3\cdot \left(-2 \right) \\ 2\cdot 9+6\cdot \left(-3 \desno) & 2\cdot 6+6\ cdot \left(-2 \desno) \\\end(niz) \right]= \\ & =\left[ \begin(matrica) 0 & 0 \\ 0 & 0 \\\end(matrica) \right] . \end(poravnati)\]
Kao što vidite, rezultat je matrica ispunjena nulama
Odgovor: $\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrix) \right]$.
Iz gornjih primjera očito je da množenje matrice nije tako komplicirana operacija. Barem za kvadratne matrice 2x2.
U procesu proračuna sastavili smo srednju matricu, gdje smo izravno slikali koji su brojevi uključeni u određenu ćeliju. Upravo to treba činiti pri rješavanju stvarnih problema.
Osnovna svojstva matričnog proizvoda
U suštini. Množenje matrice:
- Nekomutativno: $A\cdot B\ne B\cdot A$ općenito. Postoje, naravno, posebne matrice za koje je jednakost $A\cdot B=B\cdot A$ (na primjer, ako je $B=E$ matrica identiteta), ali u velikoj većini slučajeva to ne radi ;
- Asocijativno: $\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)$. Ovdje nema opcija: susjedne matrice se mogu množiti bez brige o tome što je lijevo i desno od ove dvije matrice.
- Distributivno: $A\cdot \left(B+C \desno)=A\cdot B+A\cdot C$ i $\left(A+B \right)\cdot C=A\cdot C+B\cdot C $
A sada - sve isto, ali detaljnije.
Množenje matrice uvelike je slično klasičnom množenju brojeva. Ali postoje razlike, od kojih je najvažnija ta množenje matrice je, općenito govoreći, nekomutativno.
Razmotrimo ponovo matrice iz Zadatka 1. Već znamo njihov izravni proizvod:
\[\left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\end(niz) \right]=\left[ \begin(niz)(*(35)(r))4 & 6 \\ 18 & -8 \\\kraj (niz) \desno]\]
Ali ako zamijenimo matrice, dobivamo potpuno drugačiji rezultat:
\[\left[ \begin(niz)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(niz) \desno]\cdot \left[ \begin(array)(* (35)(r)) 1 & 2 \\ -3 & 4 \\\end(niz) \right]=\left[ \begin(matrica) -14 & 4 \\ 0 & 10 \\\end(matrica )\pravo]\]
Ispada da je $A\cdot B\ne B\cdot A$. Također, operacija množenja definirana je samo za konzistentne matrice $A=\left[ m\times n \right]$ i $B=\left[ n\times k \right]$, ali nitko nije jamčio da će one ostati dosljedni, ako su zamijenjeni. Na primjer, matrice $\left[ 2\times 3 \right]$ i $\left[ 3\times 5 \right]$ prilično su konzistentne ovim redoslijedom, ali iste matrice $\left[ 3\times 5 \ desno] $ i $\left[ 2\times 3 \right]$ napisani obrnutim redoslijedom više se ne podudaraju. Tuga :(
Među kvadratnim matricama zadane veličine $n$ uvijek će biti onih koje daju isti rezultat i kada se množe izravnim i obrnutim redoslijedom. Kako opisati sve takve matrice (i koliko ih općenito) tema je za zasebnu lekciju. Danas nećemo o tome. :)
Međutim, množenje matrice je asocijativno:
\[\lijevo(A\cdot B \desno)\cdot C=A\cdot \left(B\cdot C \desno)\]
Stoga, kada trebate pomnožiti nekoliko matrica u nizu odjednom, uopće nije potrebno to učiniti prije vremena: sasvim je moguće da neke susjedne matrice, kada se pomnože, daju zanimljiv rezultat. Na primjer, nulta matrica, kao u problemu 2 o kojem je gore raspravljano.
U stvarnim problemima najčešće se moraju množiti kvadratne matrice veličine $\left[ n\puta n \right]$. Skup svih takvih matrica označen je s $((M)^(n))$ (tj., unosi $A=\left[ n\times n \right]$ i \ znače istu stvar), i to će definitivno sadrže matricu $E$, koja se naziva matrica identiteta.
Definicija. Matrica identiteta veličine $n$ je matrica $E$ takva da za bilo koju kvadratnu matricu $A=\left[ n\times n \right]$ vrijedi jednakost:
Takva matrica uvijek izgleda isto: na njenoj glavnoj dijagonali nalaze se jedinice, a u svim ostalim ćelijama nule.
\[\begin(align) & A\cdot \left(B+C \right)=A\cdot B+A\cdot C; \\ & \left(A+B \desno)\cdot C=A\cdot C+B\cdot C. \\ \end(align)\]
Drugim riječima, ako trebate pomnožiti jednu matricu sa zbrojem dvije druge, onda je možete pomnožiti sa svakim od ove "druge dvije", a zatim zbrojiti rezultate. U praksi obično morate izvesti obrnutu operaciju: primijetimo istu matricu, izvadimo je iz zagrade, izvršimo zbrajanje i time si pojednostavimo život. :)
Imajte na umu da smo za opisivanje distributivnosti morali napisati dvije formule: gdje je zbroj u drugom faktoru i gdje je zbroj u prvom. To je upravo zbog činjenice da je množenje matrice nekomutativno (i općenito, u nekomutativnoj algebri postoji puno raznoraznih šala koje niti ne padaju na pamet kada radite s običnim brojevima). A ako, na primjer, trebate zapisati ovo svojstvo tijekom ispita, onda svakako napišite obje formule, inače bi se učitelj mogao malo naljutiti.
Dobro, sve su to bile bajke o kvadratnim matricama. Što je s pravokutnicima?
Slučaj pravokutnih matrica
Ali ništa - sve je isto kao i kod kockastih.
Zadatak 3. Izvedite množenje:
\[\left[ \begin(matrica) \begin(matrica) 5 \\ 2 \\ 3 \\\end(matrica) & \begin(matrica) 4 \\ 5 \\ 1 \\\end(matrica) \ \\end(matrica) \desno]\cdot \left[ \begin(niz)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(niz) \desno]\]
Odluka. Imamo dvije matrice: $A=\left[ 3\times 2 \right]$ i $B=\left[ 2\times 2 \right]$. Napišimo redom brojeve koji označavaju veličine:
Kao što vidite, dva središnja broja su ista. To znači da su matrice konzistentne i da se mogu množiti. I na izlazu dobivamo matricu $C=\left[ 3\puts 2 \right]$:
\[\begin(poravnati) & \left[ \begin(matrica) \begin(matrica) 5 \\ 2 \\ 3 \\\end(matrica) & \begin(matrica) 4 \\ 5 \\ 1 \\ \end(matrica) \\\end(matrica) \desno]\cdot \left[ \begin(niz)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(niz) \right]=\left[ \begin(array)(*(35)(r)) 5\cdot \left(-2 \right)+4\cdot 3 & 5\cdot 5+4\cdot 4 \\ 2 \cdot \left(-2 \right)+5\cdot 3 & 2\cdot 5+5\cdot 4 \\ 3\cdot \left(-2 \right)+1\cdot 3 & 3\cdot 5+1 \cdot 4 \\\end(niz) \desno]= \\ & =\left[ \begin(niz)(*(35)(r)) 2 & 41 \\ 11 & 30 \\ -3 & 19 \ \\kraj (niz)\desno]. \end(poravnati)\]
Sve je jasno: konačna matrica ima 3 retka i 2 stupca. Sasvim $=\lijevo[ 3\put 2 \desno]$.
Odgovor: $\left[ \begin(niz)(*(35)(r)) \begin(niz)(*(35)(r)) 2 \\ 11 \\ -3 \\\end(niz) & \begin(matrica) 41 \\ 30 \\ 19 \\\end(matrica) \\\end(niz) \right]$.
Sada razmotrite jedan od najboljih zadataka treninga za one koji tek počinju raditi s matricama. U njemu ne trebate samo umnožiti neke dvije tablete, već prvo utvrditi: je li takvo množenje dopušteno?
Zadatak 4. Pronađite sve moguće parove umnožaka matrica:
\\]; $B=\left[ \begin(matrica) \begin(matrica) 0 \\ 2 \\ 0 \\ 4 \\\end(matrica) & \begin(matrica) 1 \\ 0 \\ 3 \\ 0 \ \\end(matrica) \\\end(matrica) \desno]$; $C=\left[ \begin(matrix)0 & 1 \\ 1 & 0 \\\end(matrix) \right]$.
Odluka. Prvo, zapišimo dimenzije matrica:
\;\ B=\lijevo[ 4\put 2 \desno];\ C=\lijevo[ 2\put 2 \desno]\]
Dobivamo da se matrica $A$ može upariti samo s matricom $B$, budući da je broj stupaca u $A$ 4, a samo $B$ ima ovaj broj redaka. Stoga možemo pronaći proizvod:
\\cdot \left[ \begin(niz)(*(35)(r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end(niz) \right]=\ lijevo[ \begin(niz)(*(35)(r))-10 & 7 \\ 10 & 7 \\\end(niz) \desno]\]
Predlažem da čitatelj sam izvede međukorake. Samo ću napomenuti da je bolje unaprijed odrediti veličinu rezultirajuće matrice, čak i prije bilo kakvih izračuna:
\\cdot \lijevo[ 4\puta 2 \desno]=\lijevo[ 2\put 2 \desno]\]
Drugim riječima, jednostavno uklanjamo "prijelazne" koeficijente koji su osiguravali konzistentnost matrica.
Koje su druge opcije moguće? Svakako je moguće pronaći $B\cdot A$, budući da je $B=\left[ 4\times 2 \right]$, $A=\left[ 2\times 4 \right]$, dakle uređeni par $\ left(B ;A \right)$ je konzistentan, a dimenzija proizvoda bit će:
\\cdot \lijevo[ 2\puta 4 \desno]=\lijevo[ 4\put 4 \desno]\]
Ukratko, izlaz će biti matrica $\left[ 4\times 4 \right]$, čije je koeficijente lako izračunati:
\\cdot \left[ \begin(niz)(*(35)(r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\end(niz) \right]=\ lijevo[ \begin(array)(*(35)(r))1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\kraj (niz) \desno]\]
Očito, također možete uskladiti $C\cdot A$ i $B\cdot C$, i to je to. Stoga jednostavno zapisujemo rezultirajuće proizvode:
Bilo je lako.:)
Odgovor: $AB=\left[ \begin(array)(*(35)(r)) -10 & 7 \\ 10 & 7 \\\end(array) \right]$; $BA=\left[ \begin(array)(*(35)(r)) 1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(niz) \desno]$; $CA=\lijevo[ \begin(niz)(*(35)(r)) 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\end(niz) \desno]$; $BC=\lijevo[ \begin(niz)(*(35)(r))1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\end(niz) \desno]$.
Općenito, toplo preporučujem da sami obavite ovaj zadatak. I još jedan sličan zadatak, koji je in domaća zadaća. Ove naizgled jednostavne misli pomoći će vam da razradite sve ključne korake u množenju matrice.
Ali priča tu ne prestaje. Prijeđimo na posebne slučajeve množenja. :)
Vektori reda i vektori stupaca
Jedna od najčešćih matričnih operacija je množenje matricom koja ima jedan redak ili jedan stupac.
Definicija. Vektor stupca je $\left[ m\times 1 \right]$ matrica, tj. koji se sastoji od nekoliko redaka i samo jednog stupca.
Vektor reda je matrica veličine $\left[ 1\puta n \right]$, tj. koji se sastoji od jednog reda i nekoliko stupaca.
Zapravo smo se već susreli s tim objektima. Na primjer, običan trodimenzionalni vektor iz stereometrije $\overrightarrow(a)=\left(x;y;z \right)$ nije ništa drugo nego vektor reda. S teorijske točke gledišta, gotovo da nema razlike između redaka i stupaca. Morate biti oprezni samo pri koordinaciji s okolnim matricama množenja.
Zadatak 5. Pomnožite:
\[\lijevo[ \begin(niz)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(niz) \desno] \cdot \left[ \begin(niz)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(niz) \desno]\]
Odluka. Imamo proizvod dosljednih matrica: $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Pronađite ovaj komad:
\[\lijevo[ \begin(niz)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(niz) \desno] \cdot \left[ \begin(niz)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(niz) \right]=\left[ \begin(niz)(*(35 )(r)) 2\cdot 1+\left(-1 \desno)\cdot 2+3\cdot \left(-1 \right) \\ 4\cdot 1+2\cdot 2+0\cdot 2 \ \ -1\cdot 1+1\cdot 2+1\cdot \left(-1 \right) \\\end(niz) \right]=\left[ \begin(array)(*(35)(r) ) -3 \\ 8 \\ 0 \\\kraj (niz) \desno]\]
Odgovor: $\left[ \begin(array)(*(35)(r))-3 \\ 8 \\ 0 \\\end(array) \right]$.
Zadatak 6. Izvedite množenje:
\[\left[ \begin(array)(*(35)(r)) 1 & 2 & -3 \\\end(array) \right]\cdot \left[ \begin(array)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(niz) \desno]\]
Odluka. Opet je sve dosljedno: $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. Rad smatramo:
\[\left[ \begin(array)(*(35)(r)) 1 & 2 & -3 \\\end(array) \right]\cdot \left[ \begin(array)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(niz) \right]=\left[ \begin(array)(*(35)( r))5 & -19 & 5 \\\kraj (niz) \desno]\]
Odgovor: $\left[ \begin(matrix) 5 & -19 & 5 \\\end(matrix) \right]$.
Kao što možete vidjeti, kada množite vektor retka i vektor stupca kvadratnom matricom, izlaz je uvijek redak ili stupac iste veličine. Ova činjenica ima mnoge primjene, od rješavanja linearne jednadžbe na sve vrste koordinatnih transformacija (koje se na kraju svode i na sustave jednadžbi, ali nemojmo govoriti o tužnim stvarima).
Mislim da je ovdje sve bilo očito. Prijeđimo na završni dio današnje lekcije.
Eksponencijacija matrice
Među svim operacijama množenja, eksponencijalnost zaslužuje posebnu pozornost - to je kada isti objekt množimo sam po sebi nekoliko puta. Matrice nisu iznimka, one se također mogu dizati na različite moći.
Takvi se radovi uvijek usklađuju:
\\cdot \lijevo[ n\puta n \desno]=\lijevo[ n\puta n \desno]\]
I oni su označeni na isti način kao i obični stupnjevi:
\[\begin(align) & A\cdot A=((A)^(2)); \\ & A\cdot A\cdot A=((A)^(3)); \\ & \underbrace(A\cdot A\cdot \ldots \cdot A)_(n)=((A)^(n)). \\ \end(poravnati)\]
Na prvi pogled sve je jednostavno. Pogledajmo kako to izgleda u praksi:
Zadatak 7. Podignite matricu na navedenu snagu:
$((\lijevo[ \početak(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(3))$
Odluka. OK, gradimo. Prvo kvadrirajmo:
\[\begin(poravnaj) & ((\lijevo[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(2))=\lijevo[ \begin(matrica ) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno]\cdot \left[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno]= \\ & =\left[ \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(niz) \desno]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \ \\end(niz) \desno] \end(poravnati)\]
\[\begin(poravnati) & ((\lijevo[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(3))=((\lijevo[ \begin (matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(3))\cdot \left[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end( matrica) \desno]= \\ & =\lijevo[ \begin(niz)(*(35)(r)) 1 & 2 \\ 0 & 1 \\\end(niz) \desno]\cdot \left[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 3 \\ 0 & 1 \\\kraj (niz) \desno] \end(poravnanje)\]
To je sve.:)
Odgovor: $\left[ \begin(matrix)1 & 3 \\ 0 & 1 \\\end(matrix) \right]$.
Problem 8. Podignite matricu na navedenu snagu:
\[((\lijevo[ \početak(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(10))\]
Odluka. Samo nemojte sad plakati zbog činjenice da je “diploma previsoka”, “svijet nije fer” i “učitelji su potpuno izgubili banku”. Zapravo, sve je jednostavno:
\[\begin(poravnati) & ((\lijevo[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(10))=((\lijevo[ \begin (matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(3))\cdot ((\lijevo[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\ kraj(matrica) \desno])^(3))\cdot ((\lijevo[ \početak(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \desno])^(3))\ cdot \left[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \right]= \\ & =\left(\left[ \begin(matrica) 1 & 3 \\ 0 & 1 \\\end(matrica) \desno]\cdot \left[ \begin(matrica) 1 & 3 \\ 0 & 1 \\\end(matrica) \desno] \desno)\cdot \left(\left[ \begin(matrica) 1 & 3 \\ 0 & 1 \\\end(matrica) \desno]\cdot \left[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \right ] \desno)= \\ & =\lijevo[ \begin(matrica) 1 & 6 \\ 0 & 1 \\\end(matrica) \desno]\cdot \left[ \begin(matrica) 1 & 4 \\ 0 & 1 \\\end(matrica) \desno]= \\ & =\left[ \begin(matrica) 1 & 10 \\ 0 & 1 \\\end(matrica) \right] \end(align)\ ]
Imajte na umu da smo u drugom retku koristili asocijativnost množenja. Zapravo, koristili smo ga u prethodnom zadatku, ali tamo je bilo implicitno.
Odgovor: $\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right]$.
Kao što vidite, nema ništa komplicirano u podizanju matrice na stepen. Posljednji primjer se može sažeti:
\[((\left[ \begin(matrica) 1 & 1 \\ 0 & 1 \\\end(matrica) \right])^(n))=\left[ \begin(array)(*(35) (r)) 1 & n \\ 0 & 1 \\\kraj (niz) \desno]\]
Ovu činjenicu je lako dokazati matematičkom indukcijom ili izravnim množenjem. Međutim, daleko od uvijek je moguće uhvatiti takve obrasce prilikom podizanja na stepen. Stoga, budite oprezni: često je lakše i brže pomnožiti nekoliko matrica "praznih" nego tamo tražiti neke uzorke.
Općenito, nemojte gledati više značenje gdje ne postoji. Konačno, razmotrimo eksponencijaciju veće matrice - koliko i $\left[ 3\puts 3 \right]$.
Problem 9. Podignite matricu na navedenu snagu:
\[((\lijevo[ \begin(matrica) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno])^(3))\]
Odluka. Nemojmo tražiti uzorke. Radimo "kroz":
\[((\lijevo[ \begin(matrica) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno])^(3))=(( \left[ \begin(matrica) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno])^(2))\cdot \left[ \begin (matrica)0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno]\]
Počnimo s kvadriranjem ove matrice:
\[\početak(poravnati) & ((\lijevo[ \begin(matrica) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno])^( 2))=\left[ \begin(matrica) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno]\cdot \left[ \begin(matrix ) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno]= \\ & =\left[ \begin(array)(*(35)(r )) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(niz) \desno] \end(align)\]
Sada ga kockicemo:
\[\početak(poravnati) & ((\lijevo[ \begin(matrica) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno])^( 3))=\lijevo[ \begin(niz)(*(35)(r)) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(niz) \desno] \cdot \left[ \begin(matrica) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrica) \desno]= \\ & =\left[ \begin( niz)(*(35)(r)) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(niz) \desno] \end(poravnati)\]
To je sve. Problem riješen.
Odgovor: $\left[ \begin(matrix) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(matrix) \right]$.
Kao što vidite, količina proračuna je postala veća, ali značenje se uopće nije promijenilo. :)
Ova lekcija može završiti. Sljedeći put ćemo razmotriti inverznu operaciju: potražit ćemo izvorne množitelje koristeći postojeći proizvod.
Kao što ste vjerojatno već pretpostavili, govorimo o inverzna matrica i metode za njegovo pronalaženje.
Predavanje 6. Paralelni numerički algoritmi za rješavanje tipični zadaci računalna matematika: množenje matrica.
Množenje matrice vektorom. Postignite najveću moguću brzinu. Korištenje paralelizma srednje razine. Organizacija paralelnog računanja za p = n. Korištenje ograničenog skupa procesora. Množenje matrice. Makrooperativna analiza algoritama rješavanja problema. Organizacija paralelizma na temelju dijeljenja podataka.
Množenje matrice vektorom
Problem množenja matrice vektorom definiran je relacijama
Dakle, dobivanje rezultirajućeg vektora uključuje ponavljanje iste vrste operacija za množenje redaka matrice i vektora. Dobivanje svake takve operacije uključuje množenje elemenata po elementu elemenata retka matrice i vektora i naknadno zbrajanje rezultirajućih proizvoda. Ukupan broj potrebnih skalarnih operacija procjenjuje se vrijednošću
Kao što slijedi iz radnji koje se izvode prilikom množenja matrice i vektora, paralelne metode za rješavanje problema mogu se dobiti na temelju paralelnih algoritama zbrajanja (vidi paragraf 4.1). U ovom dijelu, analiza metoda paralelizacije bit će dopunjena razmatranjem organizacije paralelnog računanja ovisno o broju procesora dostupnih za korištenje. Osim toga, na primjeru problema množenja matrice s vektorom, pozornost će se skrenuti na potrebu odabira najprikladnije topologije računalnog sustava (postojeći komunikacijski kanali između procesora) kako bi se smanjili troškovi organizacije međuprocesorske interakcije. .
Postizanje najbrže moguće izvedbe ()
Izvršimo analizu informacijskih ovisnosti u algoritmu množenja matrice-vektora kako bismo odabrali moguće načine paralelizacije. Kao što vidite, operacije množenja pojedinih redaka matrice vektorom koje se izvode tijekom izračuna su neovisne i mogu se izvoditi paralelno;
Množenje svakog retka vektorom uključuje neovisna množenja po elementima i također se može izvesti paralelno;
Zbrajanje rezultirajućih proizvoda u svakoj operaciji množenja retka matrice vektorom može se izvesti pomoću jedne od prethodno razmatranih varijanti algoritma zbrajanja (serijski algoritam, konvencionalne i modificirane kaskadne sheme).
Dakle, maksimalni potrebni broj procesora određen je vrijednošću
Korištenje takvog broja procesora može se prikazati na sljedeći način. Skup procesora podijeljen je u grupe
,
od kojih svaki predstavlja skup procesora za izvođenje operacije množenja jednog retka matrice vektorom. Na početku izračuna, svaki procesor grupe prima element retka matrice i odgovarajući element vektora. Zatim svaki procesor izvodi operaciju množenja. Zatim se izračuni izvode prema shemi kaskadnog zbrajanja. Za ilustraciju na sl. 6.1 prikazana je računska shema za procesore grupe s dimenzijom matrice.
Riža. 6.1. Računska shema za množenje retka matrice vektorom
Vrijeme izvršenja paralelnog algoritma pri korištenju procesora određeno je vremenom izvršenja operacije paralelnog množenja i vremenom izvršenja kaskadne sheme
Kao rezultat toga, pokazatelji izvedbe algoritma određeni su sljedećim odnosima:
Za razmatrani problem množenja matrice vektorom, najprikladnije topologije su strukture koje omogućuju brz prijenos podataka (putovi jedinične duljine) u shemi kaskadne sumacije (vidi sliku 4.5). Takve topologije su strukture s kompletan sustav kravate ( kompletan graf) i hiperkocka. Druge topologije rezultiraju povećanim vremenom komunikacije zbog dužih putova podataka. Dakle, uz linearni poredak procesora sa sustavom veza samo s najbližim susjedima s lijeve i desne strane ( vladar ili prsten) za kaskadnu shemu, duljina puta prijenosa svake primljene djelomične sume na iteraciji , , jednaka je . Ako prihvatimo da prijenos podataka duž puta duljine u topologijama s linearnom strukturom zahtijeva izvršavanje operacija prijenosa podataka, ukupan broj paralelnih operacija (ukupna duljina putova) prijenosa podataka određuje se vrijednošću
(isključujući prijenos podataka za bootstrapping procesore).
Primjena računalnog sustava s pravokutnom topologijom dvodimenzionalna rešetka veličina dovodi do jednostavne i vizualne interpretacije izvršenih izračuna (struktura mreže odgovara strukturi obrađenih podataka). Za takvu topologiju najpovoljnije je postaviti redove matrice duž vodoravnih linija rešetke; u ovom slučaju elementi vektora moraju biti poslani duž vertikala računskog sustava. Izvođenje izračuna s ovim rasporedom podataka može se provoditi paralelno duž linija rešetke; kao rezultat, ukupan broj prijenosa podataka je isti kao i rezultati za ravnalo().
Komunikacijske radnje koje se izvode u rješavanju problema su prijenos podataka između parova MCS procesora. Detaljna analiza trajanja provedbe takvih operacija provodi se u stavku 3.3.
4. Preporuke za implementaciju paralelnog algoritma. Pri implementaciji paralelnog algoritma preporučljivo je izdvojiti početnu fazu učitavanja korištenih procesora početnim podacima. Takva je inicijalizacija najjednostavnije predviđena za topologiju računalnog sustava s topologijom u obliku kompletan graf(učitavanje je omogućeno jednom operacijom paralelnog prijenosa podataka). Prilikom organiziranja skupa procesora u obrascu hiperkocka Može biti korisno imati dvorazinsku kontrolu procesa pokretanja, u kojoj središnji upravljački procesor distribuira retke matrice i vektora kontrolnim procesorima grupa procesora , koji zauzvrat distribuiraju elemente matrice i vektorske redove do izvršnih procesora. Za topologije u obliku vladari ili prstenje potrebne su sekvencijalne operacije prijenosa podataka sa sekvencijalno opadajućom količinom podataka koji se prenose od do elemenata.
Korištenje paralelizma srednje razine()
1. Izbor metode paralelnog računanja. Sa smanjenjem raspoloživog broja korištenih procesora (), uobičajena shema kaskadnog zbrajanja pri izvođenju operacija množenja redaka matrice s vektorom postaje neprimjenjiva. Radi jednostavnosti prezentacije materijala pretpostavljamo i koristimo modificiranu kaskadnu shemu. Početno opterećenje svakog procesora u ovom slučaju raste i procesor se opterećuje () dijelovima redaka matrice i vektora. Vrijeme izvršenja operacije množenja matrice vektorom može se procijeniti kao vrijednost
Kada se koristi broj procesora potreban za implementaciju modificirane kaskadne sheme, t.j. na 
, ovaj izraz daje procjenu vremena izvršenja 
(na ).
Uz broj procesora , kada se vrijeme izvršenja algoritma procjenjuje kao , može se predložiti nova shema za paralelno izvođenje izračuna u kojoj se za svaku iteraciju kaskadno zbrajanje koristi skupovi procesora koji se ne preklapaju. S ovim pristupom, raspoloživi broj procesora dovoljan je za implementaciju samo jedne operacije množenja retka matrice i vektora. Osim toga, prilikom izvođenja sljedeće iteracije kaskadnog zbrajanja, procesori odgovorni za izvršenje svih prethodnih iteracija su slobodni. Međutim, ovaj nedostatak predloženog pristupa može se pretvoriti u prednost korištenjem neaktivnih procesora za obradu sljedećih redaka matrice. Kao rezultat, može se formirati sljedeća shema transporter izvršiti množenje matrice i vektora:
Skup procesora podijeljen je u skupine procesora koji se ne preklapaju
,
grupa , , sastoji se od procesora i koristi se za ponavljanje kaskadnog algoritma (grupa se koristi za implementaciju množenja po elementima); ukupan broj procesora;
Inicijalizacija proračuna sastoji se od učitavanja element po element procesora grupe vrijednostima 1 retka matrice i vektora; nakon bootstrapa, izvodi se paralelna operacija množenja po elementima i naknadna implementacija konvencionalnog kaskadnog kruga zbrajanja;
Prilikom izvođenja proračuna, svaki put nakon završetka operacije množenja po elementima, procesori grupe se učitavaju elementima sljedećeg retka matrice i pokreće se proces proračuna za novoučitane podatke.
Kao rezultat primjene opisanog algoritma, veći broj procesora implementira cjevovod za izvođenje operacije množenja retka matrice s vektorom. Na takvom cjevovodu nekoliko pojedinačnih redaka matrice može istovremeno biti u različitim fazama obrade. Tako će, na primjer, nakon elementarnog množenja elemenata prvog retka i vektora, procesori grupe izvesti prvu iteraciju kaskadnog algoritma za prvi red matrice, a procesori grupe će izvesti elementarno množenje vrijednosti drugog retka matrice, itd. Za ilustraciju na sl. 6.2 prikazuje situaciju procesa izračunavanja nakon 2 iteracije cjevovoda na .
Riža. 6.2. Stanje cjevovoda za operaciju množenja retka matrice vektorom nakon izvođenja 2 iteracije
2. Evaluacija pokazatelja uspješnosti algoritma. Množenje prvog retka vektorom prema kaskadnoj shemi bit će dovršeno, kao i obično, nakon izvršenja () paralelnih operacija. Za ostale retke, u skladu s cjevovodnom shemom organizacije proračuna, rezultati množenja svakog uzastopnog retka pojavit će se nakon završetka svake sljedeće iteracije cjevovoda. Kao rezultat, ukupno vrijeme izvršenja operacije množenja matrice-vektora može se izraziti kao
Ova procjena je nešto dulje od vremena izvršavanja paralelnog algoritma opisanog u prethodnom stavku (), međutim, novopredložena metoda zahtijeva manje podataka za prijenos (vektor se šalje samo jednom). Osim toga, korištenje cjevovodne sheme dovodi do ranije pojave nekih rezultata izračuna (što može biti korisno u brojnim situacijama obrade podataka).
Kao rezultat toga, pokazatelji performansi algoritma određeni su relacijama sljedeće vrste:
3. Izbor topologije računalnog sustava. Prikladna topologija računalnog sustava u potpunosti je određena računskom shemom - ovo je cjelovito binarno stablo visina . Broj prijenosa podataka s takvom mrežnom topologijom određen je ukupnim brojem iteracija koje izvodi cjevovod, t.j.
Inicijalizacija izračuna počinje od listova stabla, rezultati zbrajanja se akumuliraju u korijenskom procesoru.
Analiza složenosti komunikacijskih radnji koje se izvode za računalne sustave s drugim topologijama međuprocesorskih komunikacija trebala bi se provesti kao samostalna zadaća (vidi također odjeljak 3.4).
Organizacija paralelnog računanja s
1. Izbor metode paralelnog računanja. Kada se koriste procesori za množenje matrice s vektorom, može se koristiti paralelni algoritam množenja red po red koji je već razmotren u priručniku, u kojem su redovi matrice raspoređeni red po red među procesorima i svaki procesor implementira operaciju množenja bilo kojeg pojedinačnog retka matrice vektorom . Drugi mogući način organiziranja paralelnog računanja može biti izgradnja cjevovodna shema za operaciju množenja retka matrice vektorom(točkasti proizvod vektora) raspoređivanjem svih dostupnih procesora u linearni niz ( vladari).
Takva shema izračuna može se definirati na sljedeći način. Predstavimo skup procesora kao linearni niz (vidi sliku 4.7):
svaki procesor , koristi se za množenje elemenata stupca matrice i elementa vektora . Izvršenje izračuna na svakom procesoru, sastoji se od sljedećeg:
Zahtijeva se sljedeći element stupca matrice;
Elementi i se množe;
Zahtijeva se rezultat izračuna prethodnog procesora;
Vrijednosti se dodaju;
Rezultat se šalje sljedećem procesoru.
Riža. 6.3. Stanje linearnog cjevovoda za operaciju množenja retka matrice vektorom nakon izvođenja dvije iteracije
Prilikom inicijalizacije opisane sheme potrebno je izvršiti niz dodatnih radnji:
Tijekom prve iteracije, svaki procesor dodatno zahtijeva element vektora;
Za sinkronizaciju izračuna (tijekom izvođenja sljedeće iteracije kruga, traži se rezultat izračuna prethodnog procesora) u fazi inicijalizacije, procesor , , izvršava () petlju čekanja.
Osim toga, za ujednačenost opisane sheme za prvi procesor, koji nema prethodni procesor, preporučljivo je uvesti praznu operaciju zbrajanja ( 
).
Za ilustraciju na sl. 6.3 prikazuje stanje procesa računanja nakon druge iteracije cjevovoda na .
2. Evaluacija pokazatelja uspješnosti algoritma. Množenje prvog retka vektorom u skladu s opisanom shemom cjevovoda bit će završeno nakon izvođenja () paralelnih operacija. Rezultat množenja sljedećih redaka pojavit će se nakon završetka svake sljedeće iteracije cjevovoda (podsjetimo, iteracija svakog procesora uključuje izvođenje operacija množenja i zbrajanja). Kao rezultat, ukupno vrijeme izvršenja operacije množenja matrice-vektora može se izraziti kao:
Ova procjena je također veća od minimalnog mogućeg vremena izvršenja paralelnog algoritma za . Korisnost korištenja cjevovodne računalne sheme je, kao što je navedeno u prethodnom stavku, u smanjenju količine prenesenih podataka i u ranijem pojavljivanju dijela rezultata proračuna.
Pokazatelji izvedbe ove računske sheme određeni su relacijama:
, 
,
3. Izbor topologije računalnog sustava. Potrebna topologija računskog sustava za implementaciju opisanog algoritma jedinstveno je određena predloženom računskom shemom - to je linearno uređen skup procesora ( vladar).
Korištenje ograničenog skupa procesora ()
1. Izbor metode paralelnog računanja. Kada se broj procesora svede na vrijednost, može se dobiti paralelna računska shema za množenje matrice-vektora kao rezultat prilagodbe algoritma množenja red po red. U ovom slučaju se degenerira kaskadna shema za zbrajanje rezultata množenja po elementima i operacija množenja retka matrice vektorom u potpunosti se izvodi na jednom procesoru. Računska shema dobivena ovim pristupom može se specificirati na sljedeći način:
Vektorski i matrični redovi šalju se svakom od dostupnih procesora;
Operacija množenja redaka matrice vektorom izvodi se uobičajenim sekvencijalnim algoritmom.
Treba napomenuti da veličina matrice ne može biti višekratnik broja procesora, a zatim se retke matrice ne mogu ravnomjerno podijeliti između procesora. U tim je situacijama moguće odstupiti od zahtjeva ujednačenosti opterećenja procesora i, kako bi se dobila jednostavnija računska shema, prihvatiti pravilo da se podaci stavljaju na procesore samo red po red (tj. elementi jednog retka matrice ne može se dijeliti između više procesora). Različiti broj redaka rezultira različitim računalnim opterećenjem na procesorima; tako će završetak proračuna (ukupno trajanje rješavanja problema) biti određen vremenom rada najopterećenijeg procesora (u ovom slučaju neki procesori mogu biti u stanju mirovanja zbog iscrpljivanja svog udjela u proračunima). Neravnomjerno opterećenje procesora smanjuje učinkovitost korištenja MCS-a i, kao rezultat razmatranja ovog primjera, možemo zaključiti da problem balansiranja
3. Izbor topologije računalnog sustava. U skladu s prirodom međuprocesorskih interakcija izvedenih u predloženoj računskoj shemi, organizacija procesora u obliku zvijezde(vidi sliku 1.1). Upravljački procesor takve topologije može se koristiti za učitavanje računalnih procesora početnim podacima i za primanje rezultata izvršenih proračuna.
Množenje matrice
Problem množenja matrice matricom definiran je relacijama
.
(radi jednostavnosti, pretpostavit ćemo da su pomnožene matrice i kvadratne i imaju red ).
Analogno razmatranju problema množenja matrice vektorom može se provesti analiza mogućih načina paralelnog izvršavanja ovog zadatka. Ostavljajući ovu analizu za samostalno istraživanje, pokazat ćemo na primjeru problema množenja matrice korištenje nekoliko općih pristupa koji nam omogućuju formiranje paralelnih metoda za rješavanje složenih problema.
