Dažnai tenka naudoti matricas, suskirstytas į stačiakampes dalis – „ląsteles“ arba „blokus“. Šią dalį skiriame tokių „blokinių“ matricų svarstymui.

1. Tegu duota stačiakampė matrica

Naudojant horizontalias ir vertikalios linijos Supjaustykime matricą į stačiakampius blokus:

. (58)

Apie matricą (58) pasakysime, kad ji suskirstyta į dydžio blokus arba pateikiama blokinės matricos pavidalu. Vietoj (58) rašysime santrumpa:

Šiuo atveju naudosime šį žymėjimą:

Veiksmai blokų matricose atliekami pagal tas pačias formalias taisykles, kaip ir tuo atveju, kai vietoj blokų turime skaitinius elementus. Pavyzdžiui, duokime dvi tokio paties dydžio stačiakampes matricas su ta pačia pertvara į blokus:

Tai nesunku pastebėti

. (62)

Pažvelkime į daugybą atidžiau blokų matricos. Yra žinoma (žr. I skyrių, p. 17), kad dauginant dvi stačiakampes matricas, pirmojo koeficiento eilučių ilgis turi sutapti su antrojo koeficiento stulpelių aukščiu. Norėdami įgalinti šių matricų blokų dauginimą, mes papildomai reikalausime, kad skaidydami į blokus visi horizontalūs matmenys pirmas veiksnys sutapo su atitinkamais vertikaliais matmenimis antrajame:

, . (63)

Tada nesunku tai patikrinti

, Kur . (64)

Atskirai atkreipkime dėmesį į ypatingą atvejį, kai vienas iš veiksnių yra kvazi-įstrižainė matrica. Leisti būti kvazi-įstrižainės matrica, ty ir už . Šiuo atveju formulė (64) mums suteikia:

Kai bloko matrica paliekama padauginta iš beveik įstrižainės matricos, bloko matricos eilutės kairėje padauginamos iš atitinkamų įstrižainės matricos langelių.

Leiskite dabar būti beveik įstrižainės matrica, ty ir už . Tada iš (64) gauname:

Kai bloko matrica dešinėje padauginama iš beveik įstrižainės matricos, visi bloko matricos stulpeliai padauginami dešinėje iš atitinkamų įstrižainės matricos langelių.

Atkreipkite dėmesį, kad tos pačios eilės kvadratinių blokų matricų dauginimas yra įmanomas visada, kai faktoriai yra suskirstyti į vienodus kvadratinius blokų šablonus ir kiekviename veiksnyse yra kvadratinės matricos įstrižinėse vietose.

Bloko matrica (58) vadinama viršutine (apatinė) kvazitrikampe if ir all for (atitinkamai, all for ). Ypatingas kvazitrikampės matricos atvejis yra beveik įstrižainė.

Iš (64) formulės nesunku pastebėti, kad dviejų viršutinių (apatinių) kvazitrikampių matricų sandauga vėl yra viršutinė (apatinė) kvazitrikampė matrica; šiuo atveju sandaugos įstrižainės blokai gaunami padauginus atitinkamus faktorių įstrižainės blokus.

Iš tiesų, darant prielaidą, kad (64) ir

.

Panašiai analizuojamas ir žemesnių kvazitrikampių matricų atvejis.

Atkreipkite dėmesį į kvazitrikampės matricos determinanto skaičiavimo taisyklę. Šią taisyklę galima gauti remiantis Laplaso išplėtimu.

Jei yra kvazitrikampė (ypač beveik įstrižainė) matrica su kvadratiniais įstrižainiais blokais, tada šios matricos determinantas lygus produktuiįstrižainės bloko determinantai:

(67)

2. Tegu pateikta bloko matrica

(68)

Prie tosios bloko eilutės pridėkime eilutę, anksčiau kairėje padaugintą iš stačiakampės dydžio matricos. Gaukime bloko matricą

. (69)

Pateikiame pagalbinę kvadratinę matricą, pateiktą šios kvadratinės blokinės diagramos pavidalu:

. (70)

Įstrižinėse matricos langeliuose yra vienetinės matricos, kurių eilės atitinkamai yra lygios; visi neįstrižainės matricos blokai yra lygūs nuliui, išskyrus bloką, esantį tosios bloko eilutės sankirtoje su bloko stulpeliu.

Nesunku tai pamatyti

Vadinasi, kadangi yra ne vienaskaita matrica, turimoms matricų eilėms

Ypatingu atveju, kai yra kvadratinė matrica, iš (71) turime:

Tačiau kvazitrikampės matricos determinantas yra 1:

Vadinasi,

Tokias pačias išvadas galima padaryti, jei prie bet kurios matricos (67) stulpelio pridedamas kitas stulpelis, anksčiau dešinėje padaugintas iš atitinkamų matmenų stačiakampės matricos.

Gauti rezultatai gali būti formuluojami kaip tokia teorema.

3 teorema. Jei bloko matricoje prie tosios bloko eilutės (stulpelio) pridedame bloko eilutę (stulpelį), anksčiau kairėje (dešinėje) padaugintą iš atitinkamų matmenų stačiakampės matricos, tai ši transformacija nepakeis matricos rangas, taip pat tuo atveju, kai yra kvadratinė matrica, o matricos determinantas yra.

3. Dabar apsvarstykite tai ypatingas atvejis, kai įstrižainės blokas matricoje yra kvadratas ir, be to, ne vienaskaita matrica ().

Prie tosios matricos eilutės pridedame pirmąją eilutę, padaugintą kairėje iš . Tada gauname matricą

, (76)

. (77)

Jei yra kvadratinė ne vienaskaitos matrica, šį procesą galima tęsti. Taip pasiekiame apibendrintą Gauso algoritmą.

Leisti būti kvadratine matrica. Tada

. (78)

Formulė (78) sumažina determinanto, susidedančio iš blokų, skaičiavimą iki žemesnės eilės determinanto, susidedančio iš blokų, skaičiavimo.

Apsvarstykite determinantą, suskirstytą į keturis blokus:

kur ir yra kvadratinės matricos.

Tegul . Tada iš antrosios eilutės atimkite pirmąją, anksčiau padaugintą kairėje iš . Mes gauname:

. (aš)

Tuo pačiu būdu, jei , tada iš pirmosios eilutės atimame antrąją, anksčiau padaugintą kairėje iš . Mes gauname:

. (II)

Ypatingu atveju, kai visos keturios matricos , , , yra kvadratinės (tos pačios eilės), Schur formulės išplaukia iš (I) ir (II), sumažindamos eilės determinanto skaičiavimą iki determinanto skaičiavimo. užsakymas:

(), (Ia)

(). (IIa)

Jei matricos keičiasi viena su kita, tada iš (Ia) seka:

(atsižvelgiant į tai). (Ib)

Lygiai taip pat, jei jie važinėja vienas su kitu, tada

(atsižvelgiant į tai). (IIb)

Formulė (Ib) buvo gauta pagal prielaidą, o formulė (IIb) pagal sąlygą. Tačiau, remiantis tęstinumu, šių apribojimų galima atmesti.

Iš (Ia) - (IIb) formulių galime gauti dar šešias formules sukeisdami vietomis dešiniosiose pusėse ir ir tuo pačiu metu ir .

.

Pagal (Ib) formulę

.

4. Sukurkime Frobenijaus formulę blokinei matricai apversti. Tegul nevienetinė kvadratinė matrica () yra padalinta į blokus

, (80)

ir tegul taip pat yra ne vienaskaita kvadratinė matrica (). Reikia nustatyti.

Matricai pritaikykime apibendrintą Gauso algoritmą. Iš antrosios bloko eilutės atimame pirmąją, anksčiau kairėje padaugintą iš . Ši operacija yra lygiavertė kairėje esančios matricos padauginimui iš matricos, kur . Štai kodėl

. (81)

Supažindinkime su užrašu

ir atkreipkite dėmesį, kad iš lygybės (81) išplaukia:

Todėl nuo tada ir . Pereinant į atvirkštines matricas lygybėje (81), gauname

. (83)

Atvirkštinės matricos matricai ieškosime formoje . Tada iš lygybės

mes tai randame . Taigi,

. (84)

Bet tada iš lygybės (83) randame

Atlikdami blokinės matricos daugybą dešinėje lygybės (85) pusėje, gauname Frobenijaus formulę

, (86)

. (87)

Frobenijaus formulė (86) sumažina eilės matricos inversiją iki dviejų eilės matricų inversijos ir iki matricų, kurių matmenys , , ir , sudėties ir daugybos operacijos.

Jei darysime prielaidą, kad (vietoj ) ir sukeisime matricų vaidmenis ir , tada galime gauti kitą Frobenijaus formulės formą:

, (88)

. (89)

Pavyzdys. Reikalingas norint rasti elementus atvirkštinė matrica matricai

.

Mes tikime

Mes randame nuosekliai

, ,

, ,

,

,

,

.

Todėl naudodamiesi (86) formule randame:

.

5. 3 teorema taip pat reiškia

4 teorema. Jeigu stačiakampė matrica pateikta bloko forma

kur yra kvadratinė ne vienaskaitos matrica, kurios eilės (), tada matricos rangas yra lygus tik tada, jei

Įrodymas. Iš antros matricos bloko eilutės atimkime pirmąją, anksčiau kairėje padaugintą iš . Tada gauname matricą

. (92)

Matricos ir pagal 3 teoremą turi tą patį rangą. Matricos rangas sutampa su matricos rangu (t.y. c) tada ir tik tada, kai galioja, t.y. (91). Teorema įrodyta.

Iliustruojame šį radimo būdą tokiu pavyzdžiu.

Pavyzdys. Leiskite

Būtina apskaičiuoti.

Matricai taikome šiek tiek pakeistą eliminavimo metodą

.

Prie visų eilučių pridedame antrą eilutę su tam tikru koeficientu ir užtikriname, kad visi pirmojo stulpelio elementai, išskyrus antrąjį, būtų lygūs nuliui. Po to prie visų eilučių, išskyrus antrąją, pridedame trečią eilutę su tam tikru koeficientu ir užtikriname, kad antrajame stulpelyje visi elementai, išskyrus antrąjį ir trečiąjį, būtų lygūs nuliui. Po to prie paskutinių trijų eilučių pridedame pirmąją eilutę su kokiu nors koeficientu ir gauname formos matricą

.

,

,

.

9. Matricos transpozicijos operacija ir jos savybės.

Apibrėžimas: Matrica A', gauta iš matricos A pakeitus eilutes stulpeliais, vadinama transponuota matricos A atžvilgiu.

Galioja šios matricų perkėlimo taisyklės:

(αA+αB)’=αA’ + αB’

(AB)'=B'A'

Įrodinėjimo idėja yra parodyti, kad matricos (AB)' ir B'A' turi tą patį matmenį ir jas atitinkantys elementai yra lygūs.

Apibrėžimas: Jei A yra savavališka kvadratinė matrica ir A=A’ (-A=A’), tada matrica A vadinama simetriška
arba pasviręs-simetriškas

10. Atvirkštinės matricos apibrėžimas. Įrodykite, kad kiekviena apverčiama matrica turi tik vieną inversiją.

Apibrėžimas:

A A -1= A -1 A=E Iš to išplaukia, kad matricai A -1 atvirkštinė vertė bus (A -1) -1 =A

Teorema: Kiekviena apverčiama matrica turi unikalią inversiją.

Įrodymas: Tarkime, kad matrica A kartu su X turi dar vieną atvirkštinę matricą Y, t.y. AU=E. Tada

(HA)U=EU=U ┐

X(AU)=XE=X ┘ Vadinasi, X=Y. Tie. matrica A turi unikalią inversiją (ir kt.)

11. Atvirkštinės matricos apibrėžimas. Įrodyk, kad (ABC) -1 =C -1 IN -1 A -1 .

Apibrėžimas: Sakoma, kad kvadratinė matrica A yra apverčiama, jei egzistuoja kvadratinė matrica X, kurioje AX=XA=E. (1)

Kiekviena matrica X, tenkinanti lygybę (1), vadinama atvirkštine matricos A arba matricos A inversija. Matricos A atvirkštinė matrica žymima A -1

A A -1= A -1 A=E Iš to išplaukia, kad matricai A -1 atvirkštinė vertė bus (A -1) -1 =A (3)

Teorema: Jei tos pačios eilės kvadratinės matricos A, B, C yra apverčiamos, tai jų sandauga taip pat yra apverčiama ir (ABC) -1 =C -1 B -1 A -1 .

Įrodymas: A(B(CC -1)B -1)A -1 =E ir C -1 (B -1 (A -1 A)B)C = E (h.t.d.)

Bet kuriam natūraliam m pagal apibrėžimą A m = A*A*…*A – m kartų.

Pagal apibrėžimą A 0 = E.

Apibrėžimas: Kiekvienai apverčiamai matricai A A -2 =A -1 *A -1 ; A -3 = A -1 *A -1 *A -1 (4)

Iš (3) ir (4) išplaukia, kad kiekviena apverčiama matrica A ir bet kokie sveikieji skaičiai p ir q turime normalios taisyklės veiksmai su laipsniais:

A r A q =A r+ q

(AB) p =A p B p, jei AB=BA

(A p) q =A p* q

12. Įrodykite, kad perkeldami invertuojamąją matricą vėl gauname apverčiamąją matricą ir ( A ’) -1 =( A -1 )’.

Teorema: Perkėlus invertuojamąją matricą A, vėl gaunama apverčiama matrica ir (A’) -1 = (A -1)’.

Įrodymas: Taikykime transponavimo taisykles ryšiui AX=XA=E:

(AH)'=(HA)'=E'

A'X'=X'A'=E

Iš atvirkštinės matricos apibrėžimo matyti, kad (A') -1 = X'=(A -1)'(h.t.c.)

13. Blokų matricos. Blokų matricų sudėjimas ir daugyba. Kvazitrikampės matricos determinanto teorema.

Stačiakampė matrica A gali būti padalinta į stačiakampius langelius (blokus) vertikaliomis ir horizontaliomis linijomis. Visų pirma, matricą galima padalyti tik horizontaliomis arba tik vertikaliomis linijomis. (A α,β) s , t – blokinė matrica. Apsvarstykite dvi to paties matmens matricas A ir B su tuo pačiu skaidiniu į blokus. Atitinkami blokai A α,β ir B α,β turi tą patį matmenį m α x n β , α=1..s, β=1..t. Tada, vadovaujantis matricos sudėjimo taisykle, tokio paties dydžio blokų matricų su tuo pačiu skaidiniu sudėjimo į blokus operacija atliekama lygiai taip pat, lyg vietoj blokų būtų skaitiniai elementai.

Norint išplėsti matricos daugybos taisyklę į blokų matricas, būtina, kad visi horizontalūs pirmosios matricos blokų dydžiai sutaptų su atitinkamais antrojo koeficiento dydžiais. Bloko A stulpelių skaičius α,β lygus bloko B eilučių skaičiui β,c.

Β keičiasi iš 1 į t, c keičiasi iš 1 į u. Taigi matricas A ir B galima padauginti formaliai taip, lyg vietoj blokų būtų skaitiniai elementai.

Apibrėžimas: Kvadratinė matrica, kurioje visi elementai, esantys po (aukščiau) pagrindine įstriža, yra lygūs 0, vadinama viršutine (apatine) trikampe matrica. Panašios sąvokos įvedamos ir blokinėms matricoms.

Apibrėžimas: Bloko matrica A vadinama viršutine (apatine) kvazitrikampe matrica, jei visi įstrižainės blokai ir pati matrica A yra kvadratinės matricos, o visi neįstrižainiai blokai, esantys po (virš) įstrižainių blokų, yra nulinės matricos.

Apibrėžimas: Bloko matrica A vadinama kvazistrižaline, jei visi įstrižainiai blokai ir pati matrica A yra kvadratinės matricos, o visi neįstrižainiai blokai yra nulinės matricos.

Teorema: Kvazitrikampės matricos determinantas yra susietas su įstrižainės matricos determinantu tokiu ryšiu:

(♀), kur P yra produktas.

Įrodymas: Pirmiausia panagrinėkime kvazitrikampę matricą
kur A 12 = 0,
,
,

Pagal apibrėžimą

Nes Ir 12 =0 tada iš visų produktų gali būti ≠0 tik tie, kuriuose indeksai
. Dėl to likę indeksai gali gauti tik rinkinio vertes
. Esant šioms sąlygoms, permutacijos inversijų skaičius
lygu:

Atsižvelgdami į tai, mes tai nustatome

Iš to išplaukia

Atsižvelgiant į bendras atvejis kvazitrikampė matrica

Kaip matrica
Kur

pagal (*) turėsime
. Matrica
vėl kvazitrikampis. Jame atlikę tą pačią operaciją, gauname
. Po (p-1) tokių žingsnių pasiekiame (♀).

Lygybė (♀) įrodoma panašiai ir viršutinės kvazitrikampės matricos atžvilgiu (tt).

1 skyrius
MATRIKOS IR DETERMINANTAI

Šiame skyriuje nagrinėjame skaičių lenteles, vadinamas matricomis, kurios ateityje vaidins labai svarbų vaidmenį. Čia pristatomos pagrindinės operacijos su matricomis ir vadinamųjų determinantų savybės, kurios yra pagrindinės skaitinė charakteristika kvadratinės matricos.

§ 1. Matricos

1. Matricos samprata. Matrica yra stačiakampė skaičių lentelė, kurioje yra tam tikras skaičius m eilučių ir tam tikras skaičius n stulpelių. Tipo skaičiai vadinami matricos tvarka. Jei m = n, matrica vadinama kvadratu, o skaičius m = n yra jos tvarka. Ateityje matricai rašyti bus naudojami dvigubi brūkšniai arba skliaustai:

Tačiau už trumpas pavadinimas matricose dažnai naudojama viena didžioji lotyniška raidė (pavyzdžiui, A) arba simbolis ║ a ij ║, o kartais su paaiškinimu:
Į šią matricą įtraukti skaičiai a ij vadinami jos elementais. Įraše a ij - pirmasis indeksas i reiškia eilutės numerį, o antrasis indeksas j reiškia stulpelio numerį.
Kvadratinės matricos atveju

supažindinama su pagrindinių ir antrinių įstrižainių sąvokomis. Pagrindinė įstrižainė matrica (1.1) vadinama įstrižaine a 11 a 22 ...a nn iš kairės viršutinis kampasšios matricos į apatinį dešinįjį kampą. Šoninė įstrižainė tos pačios matricos įstrižainė a n1 a (n-1)2 ...a 1n , einanti iš apatinio kairiojo kampo į viršutinį dešinįjį kampą.

2. Pagrindinės operacijos su matricomis ir jų savybės. Pirmiausia susitarkime apskaičiuoti dvi matricas lygus, jei šios matricos turi tokias pačias eiles ir visi jas atitinkantys elementai yra vienodi.
Pereikime prie pagrindinių operacijų su matricomis apibrėžimo.
A) Matricos papildymas.Suma dvi matricos A = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n) ir B = (i = 1, 2,..., m; j = 1, 2,... , n) tos pačios eilės m ir n vadinama matrica C= (i = 1, 2,..., m; j = 1, 2,..., n) tos pačios eilės m ir n, elementai c ij – kurios yra lygios

C ij = a ij + b ij (i = 1, 2,..., m; j = 1, 2,... , n) (1,2

Dviejų matricų sumai žymėti naudojamas užrašas C = A + B Matricų sumos sudarymo operacija vadinama jų papildymas. Taigi, pagal apibrėžimą

Iš matricų sumos apibrėžimo, tiksliau, iš (1.2) formulės, iš karto matyti, kad matricos sudėjimo operacija turi tokias pačias savybes kaip ir sudėjimo operacija. realūs skaičiai, būtent:
1) komutacinė savybė: A + B = B + A;
2) asociatyvinė savybė: (A + B) + C = A + (B + C).
Šios savybės leidžia nesijaudinti dėl matricų terminų eilės pridedant du arba daugiau matricos

b) Matricos padauginimas iš skaičiaus. Darbas matrica A = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,... , n) į tikrąją
skaičius λ vadinamas matrica C = (i = 1, 2,..., m; j = 1, 2,..., n), kurios elementai c ij yra lygūs

c ij = λ a ij (i = 1, 2,..., m; j = 1, 2,... , n) (1,3)

Norint žymėti matricos sandaugą skaičiumi, naudojamas užrašas C = λ A arba C = Aλ. Matricos sandaugos sudarymo iš skaičiaus operacija vadinama matricos padauginimu iš šio skaičiaus. Tiesiogiai iš (1.3) formulės aišku, kad matricos padauginimas iš skaičiaus turi šias savybes:
1) kombinacinė savybė skaitinio koeficiento atžvilgiu: (λ µ )A = λ ( µ A);

2) paskirstymo nuosavybė dėl matricų sumos: λ (A + B) = λ A + λ B;
3) skaičių sumos paskirstymo savybė: (λ + µ )A = λ A + µ A.
komentuoti. Dviejų tos pačios eilės matricų A ir B skirtumą natūralu vadinti tos pačios eilės m ir n matrica C, kurią sumuojant su matrica B gaunama matrica A. Dviejų matricų skirtumui pažymėti natūralųjį žymėjimą naudojamas: C = A - B.
Labai lengva patikrinti, ar dviejų matricų A ir B skirtumą C galima gauti pagal taisyklę C = A + (-1)B.
c) Matricos daugyba. Darbas matrica A = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n), kurių eilės atitinkamai lygios m ir n, matricoje B = (i = 1, 2,.. ., n ; j = 1, 2,..., p), kurios eilės lygios atitinkamai n ir p, vadinama matrica C= (i = 1, 2,..., m; j = 1, 2,... , p), kurių eilės atitinkamai lygios m ir p, o elementai c ij apibrėžti formule

Matricos A ir matricos B sandaugai pažymėti naudokite žymėjimą C = A - B. Matricos A ir matricos B sandaugos sudarymo operacija vadinama daugybašios matricos. Iš aukščiau suformuluoto apibrėžimo matyti, kad Matricos A negalima padauginti iš kiekvienos matricos B: būtina, kad matricos A stulpelių skaičius būtų lygus matricos B eilučių skaičiui.
Konkrečiai, abu sandaugai A B ir B A gali būti nustatomi tik tuo atveju, kai stulpelių A skaičius sutampa su eilučių B skaičiumi, o eilučių A skaičius sutampa su stulpelių B skaičiumi. Šiuo atveju abi matricos A - B ir B - A bus kvadratiniai , tačiau jų eilės paprastai skirsis. Kad abu sandaugai A B ir B A būtų ne tik apibrėžti, bet ir turėti tą pačią tvarką, būtina ir pakanka, kad abi matricos A ir B būtų kvadratinės matricos tos pačios eilės.
Formulė (1.4) yra matricos C elementų sudarymo taisyklė, kuri yra matricos A ir matricos B sandauga. Ši taisyklė gali būti suformuluota ir žodžiu: elementas c ij , stovi prie sankryžosi -eilutės irj- matricos stulpelis

C = A B, lygi sumai Atitinkamų elementų poriniai sandaugai i-oji eilutė matrica A ir matricos B stulpelis.
Kaip šios taisyklės taikymo pavyzdį pateikiame antros eilės kvadratinių matricų daugybos formulę

Iš (1.4) formulės išplaukia šias savybes matricos A ir matricos B sandauga:
1) asociatyvi savybė: (AB)C = A(BC);
2) skirstomoji savybė, susijusi su matricų suma: (A + B)C = AC + BC arba A(B + C) = AB + AC.
Paskirstymo savybė iš karto išplaukia iš (1.4) ir (1.2) formulių ir įrodyti asociatyvinės savybės pakanka pastebėti, kad jei A = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n), B = (i = 1, 2,..., n; j = 1, 2,... , p ), C = (i = 1, 2,..., m ; j = 1, 2,... , p ), tada
matricos (AB)C elementas d il dėl (1.4) lygus o matricos A(BC) elementas d il " yra lygus , bet tada lygybė d il = d il " išplaukia iš galimybės keisti sumavimo tvarką j ir k atžvilgiu.
Klausimą apie matricos A ir matricos B sandaugos permutacijos savybę prasminga kelti tik tos pačios eilės kvadratinėms matricoms A ir B (kaip minėta, tik tokioms matricoms A ir B yra sandaugai AB ir BA A apibrėžtos ir yra tų pačių eilių matricos). Tai rodo elementarūs pavyzdžiai dviejų tos pačios eilės kvadratinių matricų sandauga, paprastai kalbant, neturi komutavimo savybės. Tiesą sakant, jei įdėtume

Tačiau čia nurodysime svarbius specialius atvejus, kai komutavimo savybė yra teisinga (dvi matricos, kurių sandauga yra teisinga, paprastai vadinamos komutavimo savybėmis). Tarp kvadratinių matricų išryškiname vadinamųjų klasę įstrižainės matricos, kurių kiekviena turi elementus, esančius už pagrindinės įstrižainės, lygios nuliui. Kiekviena n eilės įstrižainė turi formą

kur d 1, d 2,..., d n yra bet kokie skaičiai. Nesunku suprasti, kad jei visi šie skaičiai yra lygūs vienas kitam, ty d 1 = d 2= ...= d n = d, tada bet kuriam
N eilės kvadratinei matricai A galioja lygybė AD = DA. Tiesą sakant, simboliais Cij ir cf(j pažymėkime elementus, esančius atitinkamai matricų AD ir DA i-osios eilutės ir j-ro stulpelio sankirtoje. Tada iš lygybės (1.4) ir iš matricos D formą gauname, kad c ij =a ij d j = a ij d , c ij " = d i a ij = da ij (1.6) , t.y. c ij = c ij " .

Tarp visų įstrižainių matricų (1.5), kurių elementai sutampa d 1 = d 2= ...= d n svarbus vaidmuožaidžia dvi matricos. Pirmoji iš šių matricų gaunama esant d = 1 ir vadinama n-osios eilės tapatybės matrica ir žymimas simboliu E. Antroji matrica gaunama esant d = 0 ir vadinama n-osios eilės nulinė matrica ir žymimas simboliu O. Taigi,

Remiantis tuo, kas buvo įrodyta aukščiau, AE = EA ir AO = O A. Be to, iš (1.6) formulių akivaizdu, kad

AE = EA = E, AO = OA = O. (1,7)

Pirmoji iš (1.7) formulių apibūdina ypatingą tapatybės matricos E vaidmenį, panašų į skaičių 1 dauginant realiuosius skaičius. Kalbant apie ypatingą nulinės matricos O vaidmenį, tai atskleidžia ne tik antroji iš (1.7) formulių, bet ir elementari patikrinama lygybė A + O = O + A = A (ši lygybė yra tiesioginė formulės pasekmė (1.2)).
Apibendrinant pažymime, kad nulinės matricos sąvoką taip pat galima įvesti ne kvadratinėms matricoms (nulinė matrica yra bet kokia matrica, kurios visi elementai yra nuliai).
3. Blokų matricos. Tarkime, kad kuri nors matrica A = ║ a ij ║ naudojant horizontalias ir vertikalias linijas, jis padalijamas į atskiras stačiakampes ląsteles, kurių kiekviena yra mažesnio dydžio matrica ir vadinama pradinės matricos blokas. Tokiu atveju pradinę matricą A galima laikyti kokia nors nauja (vadinamoji blokine) matrica A = ║ A αβ ║, elementai A αβ kuriam šie blokai tarnauja.
Šiuos elementus žymime kaip didelius lotyniška raidė, norėdami pabrėžti, kad paprastai tai yra matricos, o ne skaičiai, ir (kaip ir įprasti skaitiniai elementai) pateikiame du indeksus, kurių pirmasis nurodo „bloko“ eilutės numerį, o antrasis – „bloko“ numerį. “ stulpelis. Pavyzdžiui, matrica

gali būti laikoma blokine matrica, kurios elementai yra šie blokai:

Įsidėmėtina tai, kad pagrindinės operacijos su blokų matricomis atliekamos pagal tas pačias taisykles, kaip ir su įprastomis skaitinėmis matricomis, tik blokai veikia kaip elementai.
Tiesą sakant, nesunku patikrinti, ar matrica A = ║ a ij ║ yra bloko lygio ir turi bloko lygio elementus A αβ, tada su tuo pačiu skaidiniu į blokus matrica λ A = ║λ a ij ║ atitinka bloko elementus λ A αβ(Šiuo atveju bloko elementai λ A αβ yra apskaičiuojami naudojant matricos daugybos taisyklę A αβ pagal skaičių λ).
Lygiai taip pat lengva patikrinti, ar jei A ir B matricos yra vienodos eilės ir vienodai suskirstytos į blokus, tai matricų A ir B suma atitinka blokų matricą su elementais. A αβ = A αβ + B αβ(Čia A αβ Ir B αβ- matricų A ir B blokiniai elementai).
Galiausiai tegul A ir B yra dvi blokų matricos, kurių kiekvieno bloko stulpelių skaičius A αβ lygus eilučių skaičiui bloke B β γ (Taigi
bet kokiam α, β o γ apibrėžiamas matricų sandauga A αβ IN β γ ). Tada sandauga C = A B yra matrica su elementais C α γ , apibrėžta formule

Norint įrodyti šią formulę, pakanka parašyti jos kairę ir dešinę dalis įprastiniais (skaitiniais) matricų A ir B elementais (paliekame tai skaitytojui).
Kaip blokinių matricų naudojimo pavyzdį, apsistokime ties vadinamosios tiesioginės kvadratinių matricų sumos sąvoka. Tiesioginė suma dvi kvadratinės matricos A ir B, kurių eilės atitinkamai m ir n, vadinamos kvadratine bloko matrica C, kurios eilės m + n, lygi . Tiesioginei matricų A ir B sumai žymėti naudojamas užrašas C = A

Statant lygiagrečiai metodai Norint atlikti matricos dauginimą, kartu su matricų laikymu eilučių ir stulpelių rinkiniais, plačiai naudojamas blokinis matricų vaizdavimas. Pažiūrėkime atidžiau šis metodas skaičiavimų organizavimas.

7.4.1. Subužduočių apibrėžimas

Matricų skaidymo blokų schema išsamiai aprašyta pirmajame skyriuje „Lygiagretūs matricos dauginimo iš vektoriaus metodai“. Taikant šį duomenų padalijimo metodą, pradinės matricos A, B ir gauta matrica C vaizduojamos kaip blokų rinkiniai. Kad būtų paprastesnis šios medžiagos pateikimas, darysime prielaidą, kad visos matricos yra nxn dydžio kvadratai, blokų skaičius horizontaliai ir vertikaliai yra vienodas ir lygus q (t. y. visų blokų dydis lygus kxk, k =n/q). Su šiuo duomenų vaizdavimu matricos operacija matricos daugyba A ir B bloko pavidalu gali būti pavaizduoti taip:

Kur kiekvienas matricos C blokas C ij yra apibrėžtas pagal išraišką

Kai duomenys skirstomi į blokus, siekiant nustatyti pagrindines antrines užduotis, atrodo natūralu remtis matricos blokų skaičiavimais. Atsižvelgdami į tai, kas išdėstyta aukščiau, pagrindinę dalį apibrėžiame kaip visų vieno iš C matricos blokų elementų apskaičiavimo procedūrą.

Norint atlikti visus būtinus skaičiavimus, pagrindinės papildomos užduotys turi turėti prieigą prie atitinkamų A matricos eilučių ir B matricos stulpelių rinkinių. Į kiekvieną papildomą užduotį patalpinus visus reikiamus duomenis, neišvengiamai dubliuosis ir žymiai padidės naudojamos atminties kiekis. Dėl to skaičiavimai turi būti organizuojami taip, kad kiekvienu einamuoju laiko momentu antrinėse užduotyse būtų tik dalis skaičiavimams būtinų duomenų, o prieiga prie likusių duomenų būtų suteikiama perduodant duomenis tarp procesorių. Vienas iš galimų būdų yra Fox algoritmas ( Lapė) – toliau aptariama šiame poskyryje. Antrasis metodas yra Cannon algoritmas ( Patranka) – pateikta 7.5 poskyryje.

7.4.2. Informacijos priklausomybių nustatymas

Taigi lygiagrečių matricos daugybos su blokų duomenų padalijimu skaičiavimų pagrindas yra metodas, kuriame pagrindinės papildomos užduotys yra atsakingos už atskirų matricos C blokų apskaičiavimą ir tuo pačiu metu kiekvienoje skaičiavimo iteracijos antrinėse užduotyse yra tik vienas pradinių matricų A ir B blokas. Subužduotims sunumeruoti naudosime matricos C blokų indeksus, patalpintus į antrinius uždavinius, t.y. subužduotis (i,j) yra atsakinga už bloko C ij apskaičiavimą - taigi, papildomų užduočių rinkinys sudaro kvadratinę gardelę, atitinkančią matricos C bloko vaizdavimo struktūrą.

Galimas būdas organizuoti skaičiavimus tokiomis sąlygomis yra naudoti gerai žinomą Lapės algoritmas (Lapė) – žr., pavyzdžiui, [ [34] , [51] ].

Pagal Fox algoritmą, atliekant skaičiavimus, kiekvienoje pagrindinėje antrinėje užduotyje (i, j) yra keturi matricos blokai:

• matricos C blokas C ij, apskaičiuotas pagal použduotį;
• A matricos blokas A ij, įdėtas į antrinę užduotį prieš skaičiavimų pradžią;
• A ir B matricų A" ij, B" ij blokai, gauti atliekant skaičiavimus pagal použduotį.

Vykdymas lygiagretus metodas apima:

• inicijavimo stadija, kurios metu blokai A ij , B ij perkeliami į kiekvieną antrinę užduotį (i,j), o blokai C ij atstatomi į nulį visose antrinėse užduotyse;
• skaičiavimo etapas, kurio metu kiekvienoje iteracijoje l, 0<=l

Norėdami paaiškinti šias lygiagrečiojo metodo taisykles Fig. 7.6 paveiksle parodyta blokų būsena kiekvienoje antrinėje užduotyje skaičiavimo etapo iteracijų metu (2x2 antrinių užduočių gardelės).

7.4.3. Papildomų užduočių mastelio keitimas ir paskirstymas tarp procesorių

Nagrinėjamoje lygiagrečiojo skaičiavimo schemoje blokų skaičius gali skirtis priklausomai nuo bloko dydžio pasirinkimo – šie dydžiai gali būti parinkti taip, kad bendras pagrindinių papildomų užduočių skaičius sutaptų su procesorių skaičiumi p. Taigi, pavyzdžiui, paprasčiausiu atveju, kai procesorių skaičius gali būti pavaizduotas formoje (t.y. yra tobulas kvadratas), galima pasirinkti blokų skaičių matricose vertikaliai ir horizontaliai, kad būtų lygus (t.y. ). Šis blokų skaičiaus nustatymo metodas lemia tai, kad kiekvienos papildomos užduoties skaičiavimų kiekis yra vienodas ir taip pasiekiamas visiškas skaičiavimo apkrovos tarp procesorių subalansavimas. Bendresniu atveju, su savavališku procesorių skaičiumi ir matricos dydžiais balansavimo skaičiavimai gali skirtis nuo absoliučiai identiško, tačiau, nepaisant to, tinkamai parinkus parametrus, jį galima tolygiai paskirstyti tarp procesorių reikiamu tikslumu.

Norint efektyviai įgyvendinti Fox algoritmą, kuriame pagrindinės papildomos užduotys pavaizduotos kvadratinės gardelės pavidalu ir atliekant skaičiavimus atliekamos blokų perkėlimo išilgai subužduočių gardelės eilučių ir stulpelių operacijos, tinkamiausias sprendimas yra sutvarkyti aibę. turimų procesorių taip pat kvadratinės gardelės pavidalu. Tokiu atveju galima tiesiogiai susieti antrinių užduočių rinkinį daugeliui procesorių – pagrindinė antrinė užduotis (i,j) turėtų būti procesoriaus Pi,j. Reikiama duomenų perdavimo tinklo struktūra gali būti pateikta fiziniu lygmeniu, jei skaičiavimo sistemos topologija turi gardelės arba pilno grafo formą.

7.4.4. Veiklos analizė

Nustatykime šio Fox algoritmo skaičiavimo sudėtingumą. Sąmata bus sudaryta, jei bus įvykdytos visos anksčiau padarytos prielaidos: visos matricos yra nxn dydžio kvadratai, blokų skaičius horizontaliai ir vertikaliai yra vienodas ir lygus q (t. y. visų blokų dydis lygus kxk , k=n/q), procesoriai sudaro kvadratinę gardelę ir jų skaičius lygus p=q 2.

Kaip jau minėta, Fox algoritmui vykdyti reikia q iteracijų, kurių metu kiekvienas procesorius padaugina savo esamus matricų A ir B blokus ir daugybos rezultatus prideda prie dabartinės matricos C bloko reikšmės. Atsižvelgiant į padarytas prielaidas, bendras atliktų operacijų skaičius šiuo atveju bus n 3 /p. Dėl to algoritmo pagreičio ir efektyvumo rodikliai turi tokią formą:

Bendra sudėtingumo analizė vėl suteikia idealią lygiagrečiojo skaičiavimo efektyvumo metriką. Išaiškinkime gautus ryšius – tam tiksliau nurodysime algoritmo skaičiavimo operacijų skaičių ir atsižvelgsime į vykdymo išlaidas duomenų perdavimo operacijos tarp procesorių.

Nustatykime skaičiavimo operacijų skaičių. Vykdymo sunkumas skaliarinis dauginimas matricos A bloko eilučių viename matricos B bloko stulpelyje galima įvertinti kaip 2(n/q)-1. Eilučių ir stulpelių skaičius blokuose yra lygus n/q ir dėl to blokų daugybos operacijos sudėtingumas lygus (n 2 /p)(2n/q-1) . Norint pridėti blokus, reikia n 2 /p operacijų. Atsižvelgiant į visas aukščiau pateiktas išraiškas, Fox algoritmo skaičiavimo operacijų vykdymo laikas gali būti įvertintas taip:

(prisiminkime, kad yra vienos elementarios skaliarinės operacijos vykdymo laikas).

Apskaičiuokime įgyvendinimo išlaidas duomenų perdavimo operacijos tarp procesorių. Kiekvienoje algoritmo iteracijoje, prieš padaugindamas blokus, vienas iš procesoriaus tinklelio eilės procesorių siunčia savo matricos A bloką kitiems savo eilutės procesoriams. Kaip minėta anksčiau, naudojant tinklo topologiją hiperkubo arba pilno grafiko pavidalu, šią operaciją galima atlikti log 2 q žingsniais, o perduodamų blokų tūris yra lygus n 2 /p. Dėl to matricos A blokų perdavimo operacijos, naudojant Hockney modelį, vykdymo laikas gali būti įvertintas kaip

Kur yra delsa, yra duomenų tinklo pralaidumas, o w yra matricos elemento dydis baitais. Tuo atveju, kai procesoriaus tinklelio eilučių topologija yra žiedas, matricos A blokų perdavimo laiko įvertinimo išraiška yra tokia:

Tada, padauginę matricos blokus, procesoriai perduoda savo matricos B blokus ankstesniems procesoriams išilgai procesoriaus gardelės stulpelių (pirmieji stulpelių procesoriai perduoda savo duomenis paskutiniams gardelės stulpelių procesoriams). Šias operacijas procesoriai gali atlikti lygiagrečiai, todėl tokios ryšio operacijos trukmė yra:

(prisiminkime, kad parametras q lemia procesoriaus tinklelio dydį ir ).