Algoritm för matris-vektor multiplikation. Matrismultiplikation: exempel, handlingsalgoritm, produktens egenskaper

I MatLab-systemet är det ganska enkelt att utföra matematiska operationer på matriser och vektorer. Låt oss först betrakta enkla operationer för addition och multiplikation av matriser och vektorer. Låt två vektorer ges

a = ; % radvektor
b = ; % kolumnvektor

då kan multiplikationen av dessa två vektorer skrivas på följande sätt

c = a*b; % c=1+2+3+4+5=16
d = b*a; % d – matris av 5x5 element

Enligt operationer på vektorer ger multiplicering av en radvektor med en kolumnvektor ett tal, och multiplicering av en kolumnvektor med en radvektor ger en tvådimensionell matris, vilket är resultatet av beräkningarna i exemplet ovan, d.v.s.

Addition och subtraktion av två vektorer skrivs så här:

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

Observera att addition och subtraktion kan utföras mellan två kolumnvektorer eller två radvektorer. Annars kommer MatLab att visa ett felmeddelande, eftersom Vektorer av olika typer kan inte läggas till. Detta är fallet med alla olagliga aritmetiska operationer: om de inte kan beräknas kommer MatLab att rapportera ett fel och programmet avslutas på motsvarande rad.

Multiplikations- och additionsoperationer mellan matriser utförs på liknande sätt:

A = ;
B = ettor(3);
C = A+B; % tillägg av två matriser av samma storlek
D = A+5; % tillägg av matris och antal
E = A*B; % multiplikation av matris A med B
F = B*A; % multiplikation av matris B med A
G = 5*A; % multiplicera en matris med ett tal

Operationerna för att beräkna den inversa matrisen, såväl som att transponera matriser och vektorer, skrivs enligt följande:

a = ; % radvektor
b = a’; % kolumnvektor bildad av
% genom att transponera radvektorn a.
A = ; % 3x3 elementmatris
B = a*A; %B = – radvektor
C = A*b; %C = – kolumnvektor
D = a*A*a’; % D = 45 – tal, summan av elementen i matris A
E = A'; % E – transponerad matris A
F = inv(A); % F – invers matris A
G = A^-1; % G – invers matris A

Från exemplet ovan är det tydligt att operationen för att transponera matriser och vektorer indikeras av symbolen ' (apostrof), som är placerad efter namnet på vektorn eller matrisen. Att beräkna inversen av en matris kan göras genom att anropa funktionen inv() eller genom att höja matrisen till -1. Resultatet i båda fallen blir detsamma, och två beräkningsmetoder är gjorda för att underlätta användningen vid implementering av olika algoritmer.

Om det i beräkningsprocessen är nödvändigt att multiplicera, dividera eller höja element i en vektor eller matris element för element, används följande operatorer för detta:

.* - elementvis multiplikation;
./ och.\ - element-för-element divisioner;
.^ - elementvis exponentiering.

Låt oss titta på hur dessa operatörer fungerar med följande exempel.

a = ; % radvektor
b = ; % radvektor
c = a.*b; %c=
A = ettor(3); % 3x3 matris som består av ettor
B = ; % 3x3 matris
C = A.*B; % 3x3 matris bestående av
D = A./B; % 3x3 matris bestående av
E = A.\B; % 3x3 matris bestående av
F = A.^2; % kvadrerar elementen i matris A

För att avsluta detta avsnitt kommer vi att överväga flera funktioner som är användbara när du arbetar med vektorer och matriser.

För att hitta maxvärdet för ett vektorelement, använd standardfunktionen max() som returnerar det hittade maxvärdet för elementet och dess position (index):

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

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

Ovanstående exempel visar två olika sätt att anropa max()-funktionen. I det första fallet bestäms både det maximala värdet för elementet och dess index i vektorn, och i det andra - endast det maximala värdet för elementet.

När det gäller matriser bestämmer denna funktion de maximala värdena som står i kolumnerna, som visas i exemplet nedan:

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

Den fullständiga syntaxen för max()-funktionen kan hittas genom att skriva kommandot i MatLab-kommandofönstret

hjälp<название функции>

Min()-funktionen fungerar på ett liknande sätt, som bestämmer minimivärdet för ett element i en vektor eller matris och dess index.

En annan användbar funktion för att arbeta med matriser och vektorer är funktionen sum() som beräknar summan av värdena för elementen i en vektor eller matriskolumner:

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

Vid beräkning av summan S2 beräknas summan av värdena för elementen i matris A först i kolumner och sedan i rader. Som ett resultat innehåller variabel S2 summan av värdena för alla element i matris A.

För att sortera elementvärdena för en vektor eller matris i stigande eller fallande ordning, använd sort()-funktionen enligt följande:

a = ;

b1 = sort(a); %b1=
b2 = sort(a, 'sjunka'); %b2=
b3 = sort(a, 'stiga upp'); %b3=

för matriser

A = ;
B1 = sort(A); %B1=
B2 = sort(A, 'sänka'); %B2=

I många praktiska problem behöver man ofta hitta ett specifikt element i en vektor eller matris. Detta kan göras med hjälp av standardfunktionen find() som tar som argument ett villkor enligt vilket de nödvändiga elementen hittas, till exempel:

a = ;
b1 = hitta(a == 2); % b1 = 4 – index för element 2
b2 = hitta(a ~= 2); % b2 = – index utan 2
b3 = hitta(a > 3); % b3 =

I det givna exemplet betyder symbolen '==' kontroll av likhet, och symbolen '~=' kontrollerar olikhet mellan värdena för elementen i vektor a. Dessa operatörer kommer att beskrivas mer i detalj i avsnittet Villkorliga operatörer.

En annan användbar funktion för att arbeta med vektorer och matriser är funktionen mean() för att beräkna det aritmetiska medelvärdet, som fungerar enligt följande:

a = ;
m = medelvärde(a); % m = 3
A = ;
Ml = medelvärde(A); % Ml =
M2 = medelvärde(medelvärde(A)); % M2 = 4,333

Matrisprodukt (C = AB) är en operation endast för matchade matriser A och B, där antalet kolumner i matris A är lika med antalet rader i matris B:

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

Exempel 1

Angivna matriser:

• A = a (i j) av dimensionerna m × n;
• B = b (i j) av dimensionerna p × n

Matris C, vars element c i j beräknas med följande formel:

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

Exempel 2

Låt oss beräkna produkterna AB=BA:

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

Lösning med matrismultiplikationsregeln:

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

Produkten A B och BA A finns, men de är matriser av olika storlek: A B är inte lika med BA A.

Egenskaper för matrismultiplikation

Egenskaper för matrismultiplikation:

• (A B) C = A (B C) - associativitet för matrismultiplikation;
• A (B + C) = A B + A C - multiplikationsfördelning;
• (A + B) C = A C + B C - multiplikationsfördelning;
• λ (A B) = (λ A) B

Låt oss kontrollera egenskap nr 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.

Exempel 2

Låt oss kontrollera egenskap nr 2: A (B + C) = A B + A C:

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

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

Produkt av tre matriser

Produkten av tre matriser A B C beräknas på två sätt:

• hitta A B och multiplicera med C: (A B) C;
• eller hitta först B C och multiplicera sedan A (B C).

Multiplicera matriser på två sätt:

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

Algoritm för åtgärder:

• hitta produkten av 2 matriser;
• hitta sedan produkten av 2 matriser igen.

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

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

Vi använder formeln A B C = (A B) C:

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

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

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

Multiplicera en matris med ett tal

Produkten av matris A med nummer k är matris B = A k av samma storlek, som erhålls från den ursprungliga genom att multiplicera alla dess element med ett givet tal:

bi, j = k × ai, j

Egenskaper för att multiplicera en matris med ett tal:

• 1 × A = A
• 0 × A = nollmatris
• k (A + B) = k A + k B
• (k + n) A = k A + n A
• (k × n) × A = k (n × A)

Låt oss hitta produkten av matrisen A = 4 2 9 0 gånger 5.

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

Multiplicera en matris med en vektor

För att hitta produkten av en matris och en vektor måste du multiplicera med "rad för kolumn"-regeln:

• om du multiplicerar en matris med en kolumnvektor måste antalet kolumner i matrisen matcha antalet rader i kolumnvektorn;
• Resultatet av att multiplicera en kolumnvektor är bara en kolumnvektor:

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 2 + a 2 1 n × b n a 21 × b 1 + a 22 × b 2 + ⋯ + a 2 n × b n ⋯ ⋯ ⋯ ⋯ a m 1 × b 1 + a m 2 × b 2 + ⋯ + a m n × b n = c 1 s 2 1 m

• om du multiplicerar en matris med en radvektor, måste matrisen som multipliceras uteslutande vara en kolumnvektor, och antalet kolumner måste matcha antalet kolumner i radvektorn:

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

Exempel 5

Låt oss hitta produkten av matris A och kolumnvektor B:

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

Exempel 6

Låt oss hitta produkten av matris A och radvektor B:

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

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

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

Om du märker ett fel i texten, markera det och tryck på Ctrl+Enter

Varje vektor kan ses som en matris med en kolumn eller en rad. Vi kommer att kalla en enkolumnsmatris för en kolumnvektor och en enradsmatris för en radvektor.

Om A är en matris med storleken m*n, så har kolumnvektorn b storleken n, och radvektorn b har storleken m.

För att multiplicera en matris med en vektor måste vi alltså betrakta vektorn som en kolumnvektor. När en vektor multipliceras med en matris måste den behandlas som en radvektor.

Multiplicera matris

till en komplex vektor

Vi får resultatet

Som du kan se, med vektordimensionen oförändrad, kan vi ha två lösningar.

Jag skulle vilja fästa din uppmärksamhet på det faktum att matrisen i den första och andra versionen, trots samma värden, är helt olika (har olika dimensioner)

I det första fallet betraktas vektorn som en kolumn och då är den nödvändig multiplicera matris med vektor, och i det andra fallet har vi en radvektor och sedan har vi produkten av en vektor och en matris.

Denna bot multiplicerar också vektorer och matriser som har komplexa värden. Baserat på en mer komplett kalkylator: Matrismultiplikation med komplexa värden online

Egenskaper för matris-vektor multiplikation

Matris

Vektor kolumn

Rad vektor

Godtyckligt nummer

1. Produkten av en matris med summan av kolumnvektorer är lika med summan av matrisens produkter av var och en av vektorerna

2. Produkten av summan av radvektorer och matrisen är lika med summan av produkterna av vektorer och matrisen

3. Den gemensamma faktorn för en vektor kan tas utanför produkten av en matris av en vektor/vektor av en matris

4. Produkten av en radvektor och produkten av en matris och en kolumnvektor är ekvivalent med produkten av produkten av en radvektor och en matris och en kolumnvektor.

Föreläsning 6. Parallella numeriska algoritmer för att lösa typiska problem inom beräkningsmatematik: matrismultiplikation.

Multiplicera en matris med en vektor. Att uppnå högsta möjliga prestanda. Utnyttja parallellism på mellannivå. Organisation av parallell beräkning vid p = n. Användning av en begränsad uppsättning processorer. Matrismultiplikation. Makrooperativ analys av problemlösningsalgoritmer. Organisation av parallellism baserad på datadelning.

Multiplicera en matris med en vektor

Problemet med att multiplicera en matris med en vektor definieras av relationerna

Att erhålla den resulterande vektorn innebär således att man upprepar liknande operationer för att multiplicera raderna i matrisen och vektorn. Att erhålla varje sådan operation involverar elementvis multiplikation av elementen i en rad av en matris och en vektor och den efterföljande summeringen av de resulterande produkterna. Det totala antalet erforderliga skalära operationer uppskattas av kvantiteten

Som följer av de åtgärder som utförs när en matris och en vektor multipliceras, kan parallella metoder för att lösa problemet erhållas baserat på parallella summeringsalgoritmer (se avsnitt 4.1). I detta avsnitt kommer analysen av parallelliseringsmetoder att kompletteras med övervägande av frågor om att organisera parallell beräkning beroende på antalet processorer som är tillgängliga för användning. Dessutom, med hjälp av exemplet med problemet med att multiplicera en matris med en vektor, kommer uppmärksamheten att uppmärksammas på behovet av att välja den mest lämpliga topologin för datorsystemet (befintliga kommunikationskanaler mellan processorer) för att minska kostnaderna för att organisera interprocessorinteraktion.

Att uppnå högsta möjliga prestanda ()

Låt oss analysera informationsberoende i matris-vektor multiplikationsalgoritmen för att välja möjliga parallelliseringsmetoder. Som du kan se är operationerna för att multiplicera individuella rader i en matris med en vektor som utförs under beräkningar oberoende och kan utföras parallellt;

Att multiplicera varje rad med en vektor involverar oberoende elementvisa multiplikationsoperationer och kan också utföras parallellt;

Summeringen av de resulterande produkterna i varje operation att multiplicera en matrisrad med en vektor kan utföras med användning av en av de tidigare övervägda varianterna av summeringsalgoritmen (sekventiell algoritm, konventionella och modifierade kaskadscheman).

Således bestäms det maximala erforderliga antalet processorer av värdet

Användningen av ett sådant antal processorer kan representeras enligt följande. Många processorer är indelade i grupper

,

som var och en representerar en uppsättning processorer för att utföra operationen att multiplicera en individuell rad i en matris med en vektor. I början av beräkningarna skickas ett matrisradelement och ett motsvarande vektorelement till varje processor i gruppen. Därefter utför varje processor en multiplikationsoperation. Efterföljande beräkningar utförs sedan med användning av ett kaskadsummeringsschema. För illustration i fig. 6.1 visar beräkningsschemat för processorerna i en grupp med en matrisdimension på .

Ris. 6.1. Beräkningsschema för operationen att multiplicera en matrisrad med en vektor

Exekveringstiden för en parallellalgoritm vid användning av processorer bestäms av exekveringstiden för paroch exekveringstiden för kaskadkretsen

Som ett resultat bestäms effektivitetsindikatorerna för algoritmen av följande relationer:

, ,

För problemet med matris-vektormultiplikation under övervägande är de mest lämpliga topologierna strukturer som tillhandahåller snabb dataöverföring (vägar av enhetslängd) i en kaskadsummeringskrets (se fig. 4.5). Sådana topologier är en struktur med ett komplett system av anslutningar ( komplett graf) Och hyperkub. Andra topologier leder till ökad kommunikationstid på grund av längre dataöverföringsvägar. Således, med en linjär ordning av processorer med ett system av anslutningar endast med de närmaste grannarna till vänster och höger ( linjal eller ringa) för ett kaskadschema är längden på överföringsvägen för varje mottagen delsumma vid iteration , , lika med . Om vi ​​antar att dataöverföring längs en väglängd i topologier med en linjär struktur kräver dataöverföringsoperationer, bestäms det totala antalet parallella operationer (den totala varaktigheten av vägarna) av dataöverföringen av värdet

(exklusive dataöverföringar för initial laddning av processorer).

Tillämpning av ett datorsystem med rektangulär topologi tvådimensionellt gitter storlek leder till en enkel och tydlig tolkning av de beräkningar som utförs (nätverkets struktur motsvarar strukturen hos de bearbetade data). För en sådan topologi är det mest tillrådligt att placera matrisraderna längs de horisontella rutnäten; i detta fall måste elementen i vektorn vara fördelade längs vertikalerna i beräkningssystemet. Beräkningar med detta arrangemang av data kan utföras parallellt längs rutnätslinjerna; som ett resultat matchar det totala antalet dataöverföringar resultaten för linjal().

Kommunikationsåtgärder som utförs vid lösning av en given uppgift består av att överföra data mellan par av MCS-processorer. En detaljerad analys av varaktigheten av genomförandet av sådana operationer görs i punkt 3.3.

4. Rekommendationer för implementering av en parallell algoritm. När du implementerar en parallell algoritm är det tillrådligt att markera det inledande skedet av att ladda de använda processorerna med initiala data. Enklast är sådan initiering försedd med en topologi för ett datorsystem med en topologi i formen komplett graf(nedladdningen tillhandahålls med en parallell dataöverföringsoperation). När du organiserar flera processorer i formuläret hyperkub Det kan vara användbart att ha tvånivåstyrning av bootstrap-processen, där den centrala styrprocessorn ser till att matris- och vektorraderna skickas till styrprocessorerna i processorgrupperna, som i sin tur skickar matrisens element. och vektorrader till de verkställande processorerna. För topologier i formuläret linjaler eller ringar kräver sekventiella dataöverföringsoperationer med en successivt minskande mängd data som överförs från till element.

Använder parallellism på mellannivå()

1. Välja en parallell beräkningsmetod. När det tillgängliga antalet använda processorer () minskar, blir det vanliga kaskadsummeringsschemat vid utförande av operationer för att multiplicera matrisrader med vektor otillämpligt. För att förenkla presentationen av materialet, låt oss anta och använda ett modifierat kaskadschema. Den initiala belastningen för varje processor i detta fall ökar och processorn laddas () av ​​delar av raderna i matrisen och vektorn. Utförandetiden för operationen att multiplicera en matris med en vektor kan uppskattas som

När man använder det antal processorer som krävs för att implementera det modifierade kaskadschemat, dvs. vid , ger detta uttryck en uppskattning av exekveringstiden (vid ).

När antalet processorer är , när exekveringstiden för algoritmen uppskattas till , kan ett nytt schema för parallell exekvering av beräkningar föreslås, där för varje iteration av kaskadsummering, icke-överlappande uppsättningar av processorer. Med detta tillvägagångssätt visar sig det tillgängliga antalet processorer vara tillräckligt för att implementera endast en operation för att multiplicera en matrisrad och en vektor. Dessutom, när nästa iteration av kaskadsummering utförs, är de processorer som är ansvariga för att utföra alla tidigare iterationer fria. Emellertid kan denna nackdel med det föreslagna tillvägagångssättet omvandlas till en fördel genom att använda lediga processorer för att bearbeta nästa rader i matrisen. Som ett resultat kan följande schema bildas transportband utföra matris- och vektormultiplikation:

En uppsättning processorer är uppdelad i osammanhängande processorgrupper

,

i detta fall består gruppen , , av processorer och används för att utföra iterationer av kaskadalgoritmen (gruppen används för att implementera elementvis multiplikation); totalt antal processorer;

Initiering av beräkningar består av element-för-element-laddning av processorerna i gruppen med värdena på 1 rad i matrisen och vektorn; efter den initiala laddningen utförs en parallell operation av elementvis multiplikation och efterföljande implementering av den vanliga kaskadsummeringskretsen;

När beräkningar utförs, varje gång efter fullbordandet av en elementvis multiplikationsoperation, laddas processorerna i gruppen med element från nästa rad i matrisen och beräkningsprocessen initieras för nyladdade data.

Som ett resultat av att tillämpa den beskrivna algoritmen implementerar många processorer en pipeline för att utföra operationen att multiplicera en matrisrad med en vektor. På en sådan transportör kan det samtidigt finnas flera separata rader av matrisen vid olika bearbetningsstadier. Så, till exempel, efter elementvis multiplikation av elementen i den första raden och vektorn, kommer processorerna i gruppen att utföra den första iterationen av kaskadalgoritmen för den första raden i matrisen, och processorerna i gruppen kommer att utför elementvis multiplikation av värdena på den andra raden i matrisen, etc. För illustration i fig. 6.2 visar situationen för beräkningsprocessen efter 2 iterationer av pipelinen vid .

Ris. 6.2. Tillstånd för pipelinen för operationen att multiplicera en matrisrad med en vektor efter att ha genomfört 2 iterationer

2. Utvärdering av algoritmens prestandaindikatorer. Multiplikationen av den första raden med vektor enligt kaskadschemat kommer att slutföras som vanligt efter exekvering av () parallella operationer. För andra rader - i enlighet med pipelineschemat för att organisera beräkningar - kommer multiplikationsresultaten för varje nästa rad att visas efter att varje efterföljande iteration av pipelinen har slutförts. Som ett resultat kan den totala exekveringstiden för matris-uttryckas som

Denna uppskattning är något längre än exekveringstiden för den parallella algoritmen som beskrivs i föregående stycke (), dock kräver den nyligen föreslagna metoden mindre sänd data (vektorn skickas endast en gång). Dessutom leder användningen av ett pipeline-schema till att vissa av beräkningsresultaten visas tidigare (vilket kan vara användbart i ett antal databehandlingssituationer).

Som ett resultat bestäms effektivitetsindikatorerna för algoritmen av följande relationer:

3. Välja topologi för datorsystemet. Den lämpliga topologin för ett datorsystem bestäms helt av datorkretsen - detta är en komplett binärt träd höjd Antalet dataöverföringar med en sådan nätverkstopologi bestäms av det totala antalet iterationer som utförs av pipelinen, dvs.

.

Initiering av beräkningar börjar med trädets löv, summeringsresultaten ackumuleras i rotprocessorn.

Analysen av komplexiteten hos utförda kommunikationsåtgärder för datorsystem med andra interpär tänkt att utföras som en oberoende uppgift (se även avsnitt 3.4).

Organisation av parallell beräkning i

1. Välja en parallell beräkningsmetod. När man använder processorer för att multiplicera en matris med en vektor, kan den parallella rad-för-rad multiplikationsalgoritmen som tidigare diskuterats i manualen användas, där matrisens rader är fördelade mellan processorerna rad för rad och varje processor implementerar operationen att multiplicera en enskild rad i matrisen med en vektor. Ett annat möjligt sätt att organisera parallell beräkning kan vara att bygga rörledningskrets för operationen att multiplicera en matrisrad med en vektor(skalär produkt av vektorer) genom att arrangera alla tillgängliga processorer i en linjär sekvens ( linjaler).

Ett sådant beräkningsschema kan definieras enligt följande. Låt oss föreställa oss uppsättningen processorer som en linjär sekvens (se fig. 4.7):

Varje processor, , används för att multiplicera elementen i en matriskolumn och ett vektorelement. Beräkningarna som utförs på varje processor , , är följande:

Nästa element i matriskolumnen begärs;

Elementen och multipliceras;

Resultatet av den tidigare processorns beräkningar begärs;

Värdena läggs till;

Det resulterande resultatet skickas till nästa processor.

Ris. 6.3. Tillstånd för den linjära pipelinen för operationen att multiplicera en matrisrad med en vektor efter att ha utfört två iterationer

När du initierar det beskrivna schemat måste du utföra ett antal ytterligare åtgärder:

När den första iterationen utförs begär varje processor dessutom ett element av vektorn;

För att synkronisera beräkningar (när nästa iteration av kretsen utförs, begärs beräkningsresultatet för den föregående processorn) vid initialiseringssteget, utför processorn () en vänteslinga.

Dessutom, för homogeniteten hos den beskrivna kretsen för den första processorn, som inte har en tidigare processor, är det tillrådligt att införa en tom additionsoperation ( ).

För illustration i fig. Figur 6.3 visar tillståndet för beräkningsprocessen efter den andra iterationen av pipelinen vid .

2. Utvärdering av algoritmens prestandaindikatorer. Multiplikationen av den första raden med vektorn enligt det beskrivna pipelineschemat kommer att slutföras efter exekvering av () parallella operationer. Resultatet av att multiplicera följande rader kommer att inträffa efter att varje nästa iteration av pipelinen har slutförts (kom ihåg att iterationen av varje processor inkluderar exekveringen av multiplikations- och additionsoperationer). Som ett resultat kan den totala exekveringstiden för en matris-vektor multiplikationsoperation uttryckas som:

Denna uppskattning är också större än den minsta möjliga exekveringstiden för den parallella algoritmen vid . Användbarheten av att använda ett pipelineberäkningsschema är, som noterats i föregående stycke, att minska mängden överförd data och att vissa av beräkningsresultaten visas tidigare.

Effektivitetsindikatorerna för detta beräkningsschema bestäms av relationerna:

, ,

3. Välja topologi för datorsystemet. Den nödvändiga topologin för beräkningssystemet för att exekvera den beskrivna algoritmen bestäms unikt av det föreslagna beräkningsschemat - detta är en linjärt ordnad uppsättning processorer ( linjal).

Använda en begränsad uppsättning processorer ()

1. Välja en parallell beräkningsmetod. Genom att reducera antalet processorer till ett värde kan ett parallellt beräkningsschema för matris-vektormultiplikation erhållas genom att anpassa rad-för-rad-multiplikationsalgoritmen. I detta fall degenereras kaskadkretsen för att summera resultaten av elementvis multiplikation och operationen att multiplicera en matrisrad med en vektor utförs fullständigt på en enda processor. Det beräkningsschema som erhålls med detta tillvägagångssätt kan specificeras enligt följande:

En vektor och matrisrader skickas till var och en av de tillgängliga processorerna;

Att utföra en matris-vektor radmultiplikationsoperation utförs med användning av en konventionell sekventiell algoritm.

Det bör noteras att matrisstorleken kanske inte är en multipel av antalet processorer och då kan matrisraderna inte delas lika mellan processorer. I dessa situationer kan du avvika från kravet på enhetlig laddning av processorer och, för att få ett enklare beräkningsschema, acceptera regeln att data endast placeras på processorer rad för rad (dvs. element i en rad i matrisen kan inte placeras på processorer. delas upp på flera processorer). Ett ojämnt antal rader leder till olika beräkningsbelastning på processorer; Sålunda kommer slutförandet av beräkningar (den totala varaktigheten för att lösa problemet) att bestämmas av driftstiden för den mest laddade processorn (i det här fallet, en del av denna totala tid, kan enskilda processorer vara inaktiva på grund av att deras andel är slut av beräkningar). Den ojämna belastningen av processorer minskar effektiviteten av att använda MCS och, som ett resultat av att betrakta detta exempel, kan vi dra slutsatsen att balanseringsproblem

3. Välja topologi för datorsystemet. I enlighet med arten av interprocessorinteraktionerna som utförs i det föreslagna beräkningsschemat, organiseringen av processorer i form av stjärnor(se fig. 1.1). En styrprocessor med en sådan topologi kan användas för att ladda beräkningsprocessorer med initialdata och för att ta emot resultaten av utförda beräkningar.

Matrismultiplikation

Problemet med matris-matris multiplikation definieras av relationerna

.

(för enkelhetens skull kommer vi att anta att de multiplicerade matriserna och är kvadratiska och har ordning ).

En analys av möjliga metoder för parallellt utförande av denna uppgift kan utföras i analogi med övervägandet av problemet med att multiplicera en matris med en vektor. Om vi ​​lämnar en sådan analys för oberoende studie kommer vi att använda exemplet med matrismultiplikationsproblemet för att visa användningen av flera generella tillvägagångssätt som tillåter oss att bilda parallella metoder för att lösa komplexa problem.

Så i den föregående lektionen tittade vi på reglerna för att addera och subtrahera matriser. Dessa är så enkla operationer att de flesta elever förstår dem bokstavligen direkt.

Däremot gläds du tidigt. Gratisbiten är över - låt oss gå vidare till multiplikation. Jag varnar dig genast: att multiplicera två matriser är inte alls att multiplicera tal i celler med samma koordinater, som du kanske tror. Allt är mycket roligare här. Och vi måste börja med preliminära definitioner.

Matchade matriser

En av de viktigaste egenskaperna hos en matris är dess storlek. Vi har redan pratat om detta hundra gånger: notationen $A=\left[ m\times n \right]$ betyder att matrisen har exakt $m$ rader och $n$ kolumner. Vi har också redan diskuterat hur man inte förväxlar rader med kolumner. Något annat är viktigt nu.

Definition. Matriser av formen $A=\vänster[ m\ gånger n \höger]$ och $B=\vänster[ n\ gånger k \höger]$, där antalet kolumner i den första matrisen sammanfaller med antalet rader i den andra kallas konsekventa.

Återigen: antalet kolumner i den första matrisen är lika med antalet rader i den andra! Härifrån får vi två slutsatser på en gång:

1. Ordningen på matriserna är viktig för oss. Till exempel är matriserna $A=\vänster[ 3\ gånger 2 \höger]$ och $B=\vänster[ 2\ gånger 5 \höger]$ konsekventa (2 kolumner i den första matrisen och 2 rader i den andra) , men vice versa — matriserna $B=\left[ 2\times 5 \right]$ och $A=\left[ 3\times 2 \right]$ är inte längre konsekventa (5 kolumner i den första matrisen är inte 3 rader på sekunden ).
2. Konsistensen kan enkelt kontrolleras genom att skriva ner alla dimensioner efter varandra. Med hjälp av exemplet från föregående stycke: "3 2 2 5" - det finns identiska nummer i mitten, så matriserna är konsekventa. Men "2 5 3 2" är inte konsekventa, eftersom det finns olika nummer i mitten.

Dessutom verkar Captain Obviousness antyda att kvadratiska matriser av samma storlek $\left[ n\ gånger n \right]$ alltid är konsekventa.

I matematik, när ordningen på listobjekt är viktig (till exempel i definitionen som diskuterats ovan är ordningen på matriser viktig), talar vi ofta om ordnade par. Vi träffade dem i skolan: jag tror att det är en självklarhet att koordinaterna $\left(1;0 \right)$ och $\left(0;1 \right)$ definierar olika punkter på planet.

Så: koordinater är också ordnade par som är uppbyggda av tal. Men ingenting hindrar dig från att göra ett sådant par från matriser. Sedan kan vi säga: "Ett ordnat par av matriser $\left(A;B \right)$ är konsekvent om antalet kolumner i den första matrisen är detsamma som antalet rader i den andra."

Vadå då?

Definition av multiplikation

Tänk på två konsekventa matriser: $A=\vänster[ m\ gånger n \höger]$ och $B=\vänster[ n\ gånger k \höger]$. Och vi definierar multiplikationsoperationen för dem.

Definition. Produkten av två matchade matriser $A=\vänster[ m\ gånger n \höger]$ och $B=\vänster[ n\ gånger k \höger]$ är den nya matrisen $C=\vänster[ m\ gånger k \ höger] $, vars element beräknas med formeln:

\[\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))= \\ & =\summa\limits_(t=1)^(n)(((a)_(i;t))\cdot ((b)_(t;j))) \end(align)\]

En sådan produkt betecknas på standardsättet: $C=A\cdot B$.

De som ser denna definition för första gången har omedelbart två frågor:

1. Vad är detta för grymt spel?
2. Varför är det så svårt?

Tja, först till kvarn. Låt oss börja med den första frågan. Vad betyder alla dessa index? Och hur gör man inte misstag när man arbetar med riktiga matriser?

Först och främst noterar vi att den långa raden för att beräkna $((c)_(i;j))$ (jag satte speciellt ett semikolon mellan indexen för att inte bli förvirrad, men det finns ingen anledning att sätta in dem i allmänt - jag blev själv trött på att skriva formeln i definitionen) kommer faktiskt ner på en enkel regel:

1. Ta $i$th-raden i den första matrisen;
2. Ta $j$th kolumnen i den andra matrisen;
3. Vi får två talföljder. Vi multiplicerar elementen i dessa sekvenser med samma siffror och lägger sedan till de resulterande produkterna.

Denna process är lätt att förstå från bilden:

Än en gång: vi fixar rad $i$ i den första matrisen, kolumn $j$ i den andra matrisen, multiplicerar element med samma tal och lägger sedan till de resulterande produkterna - vi får $((c)_(ij))$ . Och så vidare för alla $1\le i\le m$ och $1\le j\le k$. De där. Det kommer att finnas $m\xk$ av sådana "perversioner" totalt.

Faktum är att vi redan har stött på matrismultiplikation i skolans läroplan, bara i en kraftigt reducerad form. Låt vektorerna ges:

\[\begin(align) & \vec(a)=\left(((x)_(a));((y)_(a));((z)_(a)) \right); \\ & \överhögerpil(b)=\vänster(((x)_(b));((y)_(b));((z)_(b)) \höger). \\ \end(align)\]

Då kommer deras skalära produkt att vara exakt summan av parvisa produkter:

\[\överhögerpil(a)\ gånger \överhögerpil(b)=((x)_(a))\cdot ((x)_(b))+((y)_(a))\cdot ((y) )_(b))+((z)_(a))\cdot ((z)_(b))\]

I grund och botten, när träden var grönare och himlen var ljusare, multiplicerade vi helt enkelt radvektorn $\overrightarrow(a)$ med kolumnvektorn $\overrightarrow(b)$.

Inget har förändrats idag. Det är bara det att nu finns det fler av dessa rad- och kolumnvektorer.

Men nog med teori! Låt oss titta på verkliga exempel. Och låt oss börja med det enklaste fallet - kvadratiska matriser.

Kvadratisk matris multiplikation

Uppgift 1. Gör multiplikationen:

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

Lösning. Så vi har två matriser: $A=\vänster[ 2\ gånger 2 \höger]$ och $B=\vänster[ 2\ gånger 2 \höger]$. Det är tydligt att de är konsekventa (kvadratmatriser av samma storlek är alltid konsekventa). Därför utför vi multiplikationen:

\[\begin(align) & \left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \ begin(array)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]=\left[ \begin(array)(*(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(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 4 & 6 \\ 18 & -8 \\\ end(array)\right]. \end(align)\]

Det är allt!

Svar: $\left[ \begin(array)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(array) \right]$.

Uppgift 2. Gör multiplikationen:

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

Lösning. Återigen, konsekventa matriser, så vi utför följande åtgärder:\[\]

\[\begin(align) & \left[ \begin(matris) 1 & 3 \\ 2 & 6 \\\end(matris) \right]\cdot \left[ \begin(array)(*(35)( ) r)) 9 & 6 \\ -3 & -2 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 1\cdot 9+3\cdot \ left(-3 \right) & 1\cdot 6+3\cdot \left(-2 \right) \\ 2\cdot 9+6\cdot \left(-3 \right) & 2\cdot 6+6 \ cdot \left(-2 \right) \\\end(array) \right]= \\ & =\left[ \begin(matris) 0 & 0 \\ 0 & 0 \\\end(matris) \höger ] . \end(align)\]

Som du kan se är resultatet en matris fylld med nollor

Svar: $\left[ \begin(matris) 0 & 0 \\ 0 & 0 \\\end(matris) \right]$.

Från ovanstående exempel är det uppenbart att matrismultiplikation inte är en så komplicerad operation. Åtminstone för 2 x 2 kvadratiska matriser.

I beräkningsprocessen sammanställde vi en mellanmatris, där vi direkt beskrev vilka tal som ingår i en viss cell. Det är precis vad som bör göras när man löser verkliga problem.

Grundläggande egenskaper hos matrisprodukten

I ett nötskal. Matrismultiplikation:

1. Icke-kommutativ: $A\cdot B\ne B\cdot A$ i det allmänna fallet. Det finns naturligtvis speciella matriser för vilka likheten $A\cdot B=B\cdot A$ (till exempel om $B=E$ är identitetsmatrisen), men i de allra flesta fall fungerar inte detta ;
2. Associativt: $\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)$. Det finns inga alternativ här: intilliggande matriser kan multipliceras utan att oroa dig för vad som är till vänster och till höger om dessa två matriser.
3. Distributivt: $A\cdot \left(B+C \right)=A\cdot B+A\cdot C$ och $\left(A+B \right)\cdot C=A\cdot C+B\cdot C $ (på grund av produktens icke-kommutativitet är det nödvändigt att separat specificera höger och vänster distribution.

Och nu - allt är sig likt, men mer detaljerat.

Matrismultiplikation liknar på många sätt klassisk talmultiplikation. Men det finns skillnader, den viktigaste är det Matrismultiplikation är generellt sett icke-kommutativ.

Låt oss titta igen på matriserna från uppgift 1. Vi känner redan till deras direkta produkt:

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

Men om vi byter matriser får vi ett helt annat resultat:

\[\left[ \begin(array)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]=\left[ \begin(matris) -14 & 4 \\ 0 & 10 \\\end(matris )\höger]\]

Det visar sig att $A\cdot B\ne B\cdot A$. Dessutom är multiplikationsoperationen endast definierad för konsekventa matriser $A=\left[ m\times n \right]$ och $B=\left[ n\times k \right]$, men ingen har garanterat att de kommer att förbli konsekventa om de byts ut. Till exempel är matriserna $\left[ 2\times 3 \right]$ och $\left[ 3\times 5 \right]$ ganska konsekventa i den angivna ordningen, men samma matriser $\left[ 3\times 5 \right] $ och $\left[ 2\x 3 \right]$ skrivna i omvänd ordning är inte längre konsekventa. Ledsen.:(

Bland kvadratiska matriser av en given storlek $n$ kommer det alltid att finnas de som ger samma resultat både när de multipliceras i direkt och i omvänd ordning. Hur man beskriver alla sådana matriser (och hur många det finns i allmänhet) är ett ämne för en separat lektion. Det ska vi inte prata om idag :)

Men matrismultiplikation är associativ:

\[\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)\]

Därför, när du behöver multiplicera flera matriser i rad samtidigt, är det inte alls nödvändigt att göra det direkt: det är mycket möjligt att vissa intilliggande matriser, när de multipliceras, ger ett intressant resultat. Till exempel en nollmatris, som i uppgift 2 diskuterat ovan.

I verkliga problem måste vi oftast multiplicera kvadratiska matriser med storleken $\left[ n\ gånger n \right]$. Mängden av alla sådana matriser betecknas med $((M)^(n))$ (dvs posterna $A=\left[ n\ gånger n \right]$ och \ betyder samma sak), och det kommer att nödvändigtvis innehålla matris $E$, som kallas identitetsmatrisen.

Definition. En identitetsmatris med storleken $n$ är en matris $E$ så att för vilken kvadratisk matris $A=\left[ n\ gånger n \right]$ som helst gäller likheten:

En sådan matris ser alltid likadan ut: det finns ettor på dess huvuddiagonal och nollor i alla andra celler.

\[\begin(align) & A\cdot \left(B+C \right)=A\cdot B+A\cdot C; \\ & \left(A+B \höger)\cdot C=A\cdot C+B\cdot C. \\ \end(align)\]

Med andra ord, om du behöver multiplicera en matris med summan av två andra, kan du multiplicera den med var och en av dessa "andra två" och sedan lägga till resultaten. I praktiken måste vi vanligtvis utföra den motsatta operationen: vi märker samma matris, tar bort den från parentes, utför addition och förenklar därigenom vårt liv. :)

Notera: för att beskriva fördelningsförmågan var vi tvungna att skriva två formler: där summan är i den andra faktorn och där summan är i den första. Detta händer just för att matrismultiplikation är icke-kommutativ (och i allmänhet, i icke-kommutativ algebra finns det många roliga saker som inte ens kommer att tänka på när man arbetar med vanliga tal). Och om du till exempel behöver skriva ner den här egenskapen i ett prov, se till att skriva båda formlerna, annars kan läraren bli lite arg.

Okej, det här var alla sagor om kvadratiska matriser. Hur är det med rektangulära?

Fallet med rektangulära matriser

Men ingenting - allt är detsamma som med fyrkantiga.

Uppgift 3. Gör multiplikationen:

\[\left[ \begin(matris) \begin(matris) 5 \\ 2 \\ 3 \\\end(matris) & \begin(matris) 4 \\ 5 \\ 1 \\\end(matris) \ \\end(matris) \right]\cdot \left[ \begin(array)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(array) \right]\]

Lösning. Vi har två matriser: $A=\vänster[ 3\ gånger 2 \höger]$ och $B=\vänster[ 2\ gånger 2 \höger]$. Låt oss skriva ner siffrorna som anger storlekarna i rad:

Som du kan se sammanfaller de två centrala siffrorna. Detta innebär att matriserna är konsekventa och kan multipliceras. Vid utgången får vi dessutom matrisen $C=\left[ 3\times 2 \right]$:

\[\begin(align) & \left[ \begin(matris) \begin(matris) 5 \\ 2 \\ 3 \\\end(matris) & \begin(matris) 4 \\ 5 \\ 1 \\ \end(matris) \\\end(matris) \right]\cdot \left[ \begin(array)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(array) \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(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 2 & 41 \\ 11 & 30 \\ -3 & 19 \ \\end(array) \right]. \end(align)\]

Allt är klart: den slutliga matrisen har 3 rader och 2 kolumner. Ganska $=\vänster[ 3\ gånger 2 \höger]$.

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

Låt oss nu titta på en av de bästa träningsuppgifterna för den som precis har börjat arbeta med matriser. I den behöver du inte bara multiplicera några två tabletter, utan först bestämma: är sådan multiplikation tillåten?

Uppgift 4. Hitta alla möjliga parvisa produkter av matriser:

\\]; $B=\left[ \begin(matris) \begin(matris) 0 \\ 2 \\ 0 \\ 4 \\\end(matris) & \begin(matris) 1 \\ 0 \\ 3 \\ 0 \ \\end(matris) \\\end(matris) \right]$; $C=\left[ \begin(matrix)0 & 1 \\ 1 & 0 \\\end(matris) \right]$.

Lösning. Låt oss först skriva ner storleken på matriserna:

\;\ B=\vänster[ 4\gånger 2 \höger];\ C=\vänster[ 2\gånger 2 \höger]\]

Vi finner att matrisen $A$ endast kan stämmas av med matrisen $B$, eftersom antalet kolumner i $A$ är 4, och endast $B$ har detta antal rader. Därför kan vi hitta produkten:

\\cdot \left[ \begin(array)(*(35)(r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end(array) \right]=\ vänster[ \begin(array)(*(35)(r))-10 & 7 \\ 10 & 7 \\\end(array) \right]\]

Jag föreslår att läsaren genomför de mellanliggande stegen självständigt. Jag kommer bara att notera att det är bättre att bestämma storleken på den resulterande matrisen i förväg, även innan några beräkningar:

\\cdot \vänster[ 4\gånger 2 \höger]=\vänster[ 2\gånger 2 \höger]\]

Med andra ord tar vi helt enkelt bort "transit"-koefficienterna som säkerställde konsistensen av matriserna.

Vilka andra alternativ är möjliga? Naturligtvis kan man hitta $B\cdot A$, eftersom $B=\left[ 4\times 2 \right]$, $A=\left[ 2\times 4 \right]$, så det ordnade paret $\ left(B ;A \right)$ är konsekvent, och produktens dimension blir:

\\cdot \vänster[ 2\gånger 4 \höger]=\vänster[ 4\gånger 4 \höger]\]

Kort sagt, utdata kommer att vara en matris $\left[ 4\times 4 \right]$, vars koefficienter lätt kan beräknas:

\\cdot \left[ \begin(array)(*(35)(r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\end(array) \right]=\ vänster[ \begin(array)(*(35)(r))1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(array) \right]\]

Självklart kan du också komma överens om $C\cdot A$ och $B\cdot C$ - och det är allt. Därför skriver vi helt enkelt ner de resulterande produkterna:

Det var enkelt.:)

Svar: $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(array) \right]$; $CA=\left[ \begin(array)(*(35)(r)) 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\end(array) \right]$; $BC=\left[ \begin(array)(*(35)(r))1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\end(array) \right]$.

I allmänhet rekommenderar jag starkt att du gör den här uppgiften själv. Och en till liknande uppgift som är i läxor. Dessa till synes enkla tankar kommer att hjälpa dig att öva alla nyckelstadier av matrismultiplikation.

Men historien slutar inte där. Låt oss gå vidare till speciella fall av multiplikation. :)

Radvektorer och kolumnvektorer

En av de vanligaste matrisoperationerna är multiplikation med en matris som har en rad eller en kolumn.

Definition. En kolumnvektor är en matris med storleken $\vänster[ m\ gånger 1 \höger]$, dvs. som består av flera rader och endast en kolumn.

En radvektor är en matris med storleken $\vänster[ 1\ gånger n \höger]$, dvs. som består av en rad och flera kolumner.

Faktum är att vi redan har stött på dessa föremål. Till exempel är en vanlig tredimensionell vektor från stereometri $\overrightarrow(a)=\left(x;y;z \right)$ inget annat än en radvektor. Ur en teoretisk synvinkel är det nästan ingen skillnad mellan rader och kolumner. Du behöver bara vara försiktig när du koordinerar med de omgivande multiplikatormatriserna.

Uppgift 5. Gör multiplikationen:

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

Lösning. Här har vi produkten av matchade matriser: $\vänster[ 3\ gånger 3 \höger]\cdot \vänster[ 3\ gånger 1 \höger]=\vänster[ 3\ gånger 1 \höger]$. Låt oss hitta den här biten:

\[\left[ \begin(array)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(array) \right] \cdot \left[ \begin(array)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(array) \right]=\left[ \begin(array)(*(35) )(r)) 2\cdot 1+\left(-1 \right)\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(array) \right]=\left[ \begin(array)(*(35)(r) ) -3 \\ 8 \\ 0 \\\end(array) \right]\]

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

Uppgift 6. Gör multiplikationen:

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

Lösning. Återigen är allt överens: $\vänster[ 1\ gånger 3 \höger]\cdot \vänster[ 3\ gånger 3 \höger]=\vänster[ 1\ gånger 3 \höger]$. Vi räknar produkten:

\[\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(array) \right]=\left[ \begin(array)(*(35)( ) r))5 & -19 & 5 \\\end(array) \right]\]

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

Som du kan se, när vi multiplicerar en radvektor och en kolumnvektor med en kvadratisk matris, resulterar resultatet alltid i en rad eller kolumn av samma storlek. Detta faktum har många tillämpningar - från att lösa linjära ekvationer till alla typer av koordinattransformationer (som i slutändan också kommer ner till ekvationssystem, men låt oss inte prata om sorgliga saker).

Jag tror att allt var uppenbart här. Låt oss gå vidare till den sista delen av dagens lektion.

Matrisexponentiering

Bland alla multiplikationsoperationer förtjänar exponentiering särskild uppmärksamhet - det är när vi multiplicerar samma objekt med sig själv flera gånger. Matriser är inget undantag, de kan också höjas till olika krafter.

Sådana arbeten är alltid överenskomna:

\\cdot \vänster[ n\ gånger n \höger]=\vänster[ n\ gånger n \höger]\]

Och de betecknas på exakt samma sätt som vanliga grader:

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

Vid första anblicken är allt enkelt. Låt oss se hur det här ser ut i praktiken:

Uppgift 7. Höj matrisen till den angivna styrkan:

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

Lösning. Okej, låt oss bygga. Låt oss först kvadrera det:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matris) \right])^(2))=\left[ \begin(matris ) 1 & 1 \\ 0 & 1 \\\end(matris) \höger]\cdot \left[ \begin(matris) 1 & 1 \\ 0 & 1 \\\end(matris) \höger]= \\ & =\vänster[ \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(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \ \\end(array) \right] \end(align)\]

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matris) \right])^(3))=((\left[ \begin) (matris) 1 & 1 \\ 0 & 1 \\\end(matris) \höger])^(3))\cdot \left[ \begin(matris) 1 & 1 \\ 0 & 1 \\\end( matris) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \\\end(array) \right]\cdot \left[ \begin(matris) 1 & 1 \\ 0 & 1 \\\end(matris) \right]= \\ & =\vänster[ \begin(array)(*(35)(r)) 1 & 3 \\ 0 & 1 \\\end(array) \right] \end(align)\]

Det är allt.:)

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

Problem 8. Höj matrisen till den angivna effekten:

\[((\vänster[ \begin(matris) 1 & 1 \\ 0 & 1 \\\end(matris) \höger])^(10))\]

Lösning. Gråt bara inte nu över det faktum att "examen är för stor", "världen är inte rättvis" och "lärarna har helt tappat sina stränder." Det är faktiskt lätt:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matris) \right])^(10))=((\left[ \begin) (matris) 1 & 1 \\ 0 & 1 \\\end(matris) \höger])^(3))\cdot ((\left[ \begin(matris) 1 & 1 \\ 0 & 1 \\\ end(matris) \höger])^(3))\cdot ((\vänster[ \begin(matris) 1 & 1 \\ 0 & 1 \\\end(matris) \höger])^(3))\ cdot \left[ \begin(matris) 1 & 1 \\ 0 & 1 \\\end(matris) \right]= \\ & =\left(\left[ \begin(matris) 1 & 3 \\ 0 & 1 \\\end(matris) \höger]\cdot \left[ \begin(matris) 1 & 3 \\ 0 & 1 \\\end(matris) \höger] \höger)\cdot \left(\left[ \begin(matris) 1 & 3 \\ 0 & 1 \\\end(matris) \höger]\cdot \left[ \begin(matris) 1 & 1 \\ 0 & 1 \\\end(matris) \höger ] \right)= \\ & =\left[ \begin(matris) 1 & 6 \\ 0 & 1 \\\end(matris) \höger]\cdot \left[ \begin(matris) 1 & 4 \\ 0 & 1 \\\end(matris) \right]= \\ & =\vänster[ \begin(matris) 1 & 10 \\ 0 & 1 \\\end(matris) \right] \end(align)\ ]

Lägg märke till att på andra raden använde vi multiplikationsassociativitet. Egentligen använde vi det i föregående uppgift, men det var underförstått där.

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

Som du kan se är det inget komplicerat med att höja en matris till en makt. Det sista exemplet kan sammanfattas:

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

Detta faktum är lätt att bevisa genom matematisk induktion eller direkt multiplikation. Det är dock inte alltid möjligt att fånga sådana mönster när man höjer till en makt. Var därför försiktig: att multiplicera flera matriser "slumpmässigt" visar sig ofta vara lättare och snabbare än att leta efter någon form av mönster.

Leta i allmänhet inte efter högre mening där det inte finns någon. Sammanfattningsvis, låt oss överväga exponentieringen av en större matris - så mycket som $\left[ 3\times 3 \right]$.

Problem 9. Höj matrisen till den angivna styrkan:

\[((\vänster[ \begin(matris) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matris) \höger])^(3))\]

Lösning. Låt oss inte leta efter mönster. Vi jobbar framåt:

\[((\vänster[ \begin(matris) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matris) \höger])^(3))=(( \left[ \begin(matris) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matris) \right])^(2))\cdot \left[ \begin (matris)0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matris) \höger]\]

Låt oss först kvadrera denna matris:

\[\begin(align) & ((\left[ \begin(matris) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matris) \right])^( 2))=\vänster[ \begin(matris) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matris) \höger]\cdot \left[ \begin(matris ) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matris) \right]= \\ & =\left[ \begin(array)(*(35)(r) )) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(array) \right] \end(align)\]

Låt oss nu kubera det:

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

Det är allt. Problemet är löst.

Svar: $\left[ \begin(matris) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(matris) \right]$.

Som du kan se har volymen av beräkningar blivit större, men innebörden har inte förändrats alls. :)

Detta avslutar lektionen. Nästa gång kommer vi att överväga den omvända operationen: med den befintliga produkten kommer vi att leta efter de ursprungliga faktorerna.

Som du förmodligen redan gissat kommer vi att prata om den inversa matrisen och metoder för att hitta den.