Shpesh duhet të përdorni matrica të ndara në pjesë drejtkëndore - "qeliza" ose "blloqe". Ne ia kushtojmë këtë pjesë shqyrtimit të matricave të tilla "blloqe".

1. Le të jepet një matricë drejtkëndëshe

Duke përdorur horizontale dhe vijat vertikale Le ta presim matricën në blloqe drejtkëndëshe:

. (58)

Për matricën (58) do të themi se ajo ndahet në blloqe të madhësisë ose se paraqitet në formën e një matrice blloku. Në vend të (58) do të shkruajmë shkurtimisht:

Në këtë rast ne do të përdorim shënimin e mëposhtëm:

Veprimet në matricat e bllokut kryhen sipas të njëjtave rregulla formale si në rastin kur në vend të blloqeve kemi elemente numerike. Le të jepen, për shembull, dy matrica drejtkëndëshe të së njëjtës madhësi dhe me të njëjtën ndarje në blloqe:

Është e lehtë ta shohësh këtë

. (62)

Le të hedhim një vështrim më të afërt në shumëzimin matricat e bllokut. Dihet (shih Kapitullin I, f. 17) se kur shumëzohen dy matrica drejtkëndëshe, gjatësia e rreshtave në faktorin e parë duhet të përkojë me lartësinë e kolonave në faktorin e dytë. Për të mundësuar shumëzimin e bllokut të këtyre matricave, ne do të kërkojmë gjithashtu që, kur të ndajmë në blloqe, të gjitha dimensionet horizontale në faktorin e parë përkoi me dimensionet përkatëse vertikale në të dytin:

, . (63)

Atëherë është e lehtë ta kontrollosh atë

, Ku . (64)

Le të shënojmë veçmas rastin e veçantë kur një nga faktorët është një matricë pothuajse diagonale. Le të jetë një matricë pothuajse diagonale, d.m.th., dhe për . Në këtë rast, formula (64) na jep:

Kur një matricë blloku lihet e shumëzuar me një matricë pothuajse diagonale, rreshtat e matricës së bllokut shumëzohen në të majtë me qelizat diagonale përkatëse të matricës pothuajse diagonale.

Le të jetë tani një matricë pothuajse diagonale, d.m.th., dhe për . Pastaj nga (64) marrim:

Kur një matricë blloku shumëzohet në të djathtë me një matricë thuajse diagonale, të gjitha kolonat e matricës së bllokut shumëzohen në të djathtë me qelizat diagonale përkatëse të matricës pothuajse diagonale.

Vini re se shumëzimi i matricave të bllokut katror të të njëjtit rend është gjithmonë i realizueshëm kur faktorët ndahen në modele identike të bllokut katror dhe në secilin prej faktorëve ka matrica katrore në vende diagonale.

Një matricë blloku (58) quhet thuajse trekëndore e sipërme (e poshtme) nëse dhe të gjitha për (përkatësisht, të gjitha për ). Një rast i veçantë i një matrice thuajse trekëndore është një matricë pothuajse diagonale.

Nga formula (64) është e lehtë të shihet se prodhimi i dy matricave thuajse trekëndore të sipërme (të poshtme) është përsëri një matricë thuajse trekëndore e sipërme (e poshtme); në këtë rast, blloqet diagonale të produktit fitohen duke shumëzuar blloqet diagonale përkatëse të faktorëve.

Në të vërtetë, duke supozuar në (64) dhe

.

Në mënyrë të ngjashme analizohet rasti i matricave thuajse trekëndore më të ulëta.

Le të vërejmë rregullin për llogaritjen e përcaktorit të një matrice thuajse trekëndore. Ky rregull mund të merret bazuar në zgjerimin e Laplace.

Nëse është një matricë pothuajse trekëndore (në veçanti, pothuajse diagonale) me blloqe diagonale katrore, atëherë përcaktori i kësaj matrice e barabartë me produktin Përcaktuesit e bllokut diagonal:

(67)

2. Le të jepet një matricë blloku

(68)

Le t'i shtojmë rreshtit të bllokut të th rreshtin e th, të shumëzuar më parë në të majtë me një matricë drejtkëndore me madhësi . Le të marrim matricën e bllokut

. (69)

Le të prezantojmë një matricë katrore ndihmëse, të paraqitur në formën e diagramit të mëposhtëm të bllokut katror:

. (70)

Qelizat diagonale të matricës përmbajnë matrica njësi, rendet e të cilave janë përkatësisht të barabarta; të gjithë blloqet jo diagonale të matricës janë të barabarta me zero, me përjashtim të bllokut që ndodhet në kryqëzimin e rreshtit të bllokut të th me kolonën e bllokut të th.

Nuk është e vështirë ta shohësh këtë

Prandaj, pasi që është një matricë jo njëjës, për radhët e matricave që kemi

Në rastin e veçantë kur është një matricë katrore, nga (71) kemi:

Por përcaktori i një matrice thuajse trekëndore është 1:

Prandaj,

Të njëjtat përfundime mund të arrihen nëse një kolonë tjetër i shtohet çdo kolone të matricës (67), e shumëzuar më parë në të djathtë me një matricë drejtkëndore të dimensioneve të duhura.

Rezultatet e marra mund të formulohen si teorema e mëposhtme.

Teorema 3. Nëse në një matricë blloku në rreshtin e bllokut (kolona) i shtojmë rreshtin e bllokut (kolona), të shumëzuar më parë në të majtë (djathtas) me një matricë drejtkëndore të dimensioneve të duhura, atëherë ky transformim nuk do të ndryshojë rangu i matricës, dhe gjithashtu në rastin kur është një matricë katrore, dhe përcaktori i matricës është.

3. Tani merrni parasysh këtë rast i veçantë, kur blloku diagonal në matricë është një matricë katrore dhe, për më tepër, jo njëjës ().

Në rreshtin e th të matricës shtojmë rreshtin e parë, të shumëzuar në të majtë me . Pastaj marrim matricën

, (76)

. (77)

Nëse është një matricë katrore jo njëjës, atëherë ky proces mund të vazhdohet. Arrijmë kështu në algoritmin e përgjithësuar Gaussian.

Le të jetë një matricë katrore. Pastaj

. (78)

Formula (78) zvogëlon llogaritjen e një përcaktori të përbërë nga blloqe në llogaritjen e një përcaktori të rendit më të ulët, i përbërë nga blloqe.

Merrni parasysh përcaktorin, të ndarë në katër blloqe:

ku dhe janë matrica katrore.

Le . Pastaj zbritni nga rreshti i dytë të parën, të shumëzuar më parë në të majtë me . Ne marrim:

. (Unë)

Në të njëjtën mënyrë, nëse , atëherë ne zbresim nga rreshti i parë të dytën, të shumëzuar më parë në të majtë me . Ne marrim:

. (II)

Në rastin e veçantë kur të katër matricat , , , janë katrore (të të njëjtit rend), formulat e Schur-it vijojnë nga (I) dhe (II), duke reduktuar llogaritjen e përcaktorit të rendit të th në llogaritjen e përcaktorit të rendi i th:

(), (Ia)

(). (IIa)

Nëse matricat ndërrojnë njëra-tjetrën, atëherë nga (Ia) vijon:

(duke pasur parasysh atë). (Ib)

Në të njëjtën mënyrë, nëse ata udhëtojnë me njëri-tjetrin, atëherë

(duke pasur parasysh atë). (IIb)

Formula (Ib) është marrë sipas supozimit, dhe formula (IIb) sipas kushtit. Megjithatë, bazuar në konsideratat e vazhdimësisë, këto kufizime mund të hidhen poshtë.

Nga formulat (Ia) - (IIb) mund të marrim gjashtë formula të tjera duke ndërruar vendet në anët e djathta dhe dhe në të njëjtën kohë dhe .

.

Sipas formulës (Ib)

.

4. Le të vendosim formulën Frobenius për përmbysjen e një matrice blloku. Le të ndahet matrica katrore josingulare () në blloqe

, (80)

dhe le të jetë gjithashtu një matricë katrore jo njëjës (). Duhet të përcaktohet.

Le të zbatojmë algoritmin e përgjithësuar Gaussian në matricë. Nga rreshti i dytë i bllokut ne zbresim të parën, të shumëzuar më parë në të majtë me . Ky veprim është ekuivalent me shumëzimin e matricës në të majtë me matricën, ku . Kjo është arsyeja pse

. (81)

Le të prezantojmë shënimin

dhe vini re se nga barazia (81) vijon:

Prandaj, që nga , atëherë dhe . Duke kaluar te matricat e anasjellta në barazi (81), marrim

. (83)

Ne do të kërkojmë matricën e kundërt për matricën në formën . Pastaj nga barazia

ne e gjejmë atë . Kështu,

. (84)

Por pastaj nga barazia (83) gjejmë

Duke kryer shumëzimin e matricës së bllokut në anën e djathtë të barazisë (85), arrijmë në formulën Frobenius

, (86)

. (87)

Formula Frobenius (86) redukton përmbysjen e një matrice të rendit në përmbysjen e matricave të dy rendit dhe dhe në operacionet e mbledhjes dhe shumëzimit të matricave me dimensione , , dhe .

Nëse supozojmë se (në vend të ) dhe shkëmbejmë rolet e matricave dhe , atëherë mund të marrim një formë tjetër të formulës Frobenius:

, (88)

. (89)

Shembull. Kërkohet për të gjetur elementë matricë e anasjelltë për matricën

.

Ne besojmë

Ne gjejmë në mënyrë sekuenciale

, ,

, ,

,

,

,

.

Prandaj, duke përdorur formulën (86) gjejmë:

.

5. Teorema 3 gjithashtu nënkupton

Teorema 4. Nëse matricë drejtkëndëshe paraqitur në formë blloku

ku është një matricë katrore jo njëjës e rendit (), atëherë rangu i matricës është i barabartë vetëm nëse

Dëshmi. Le të zbresim nga rreshti i dytë i bllokut të matricës të parën, të shumëzuar më parë në të majtë me . Pastaj marrim matricën

. (92)

Matricat dhe sipas Teoremës 3 kanë të njëjtën rang. Rangu i matricës përkon me rangun e matricës (d.m.th. c) nëse dhe vetëm nëse vlen, d.m.th. (91). Teorema është e vërtetuar.

Le ta ilustrojmë këtë metodë të gjetjes me shembullin e mëposhtëm.

Shembull. Le

Kërkohet për të llogaritur.

Ne aplikojmë një metodë eliminimi pak të modifikuar në matricë

.

Të gjitha rreshtave shtojmë një rresht të dytë me disa faktor dhe sigurojmë që të gjithë elementët e kolonës së parë, përveç elementit të dytë, të jenë të barabartë me zero. Pas kësaj, në të gjitha rreshtat përveç të dytës, shtojmë një rresht të tretë me disa faktor dhe sigurojmë që në kolonën e dytë të gjithë elementët, përveç të dytës dhe të tretës, të jenë të barabartë me zero. Pas kësaj, në tre rreshtat e fundit shtojmë rreshtin e parë me disa faktor dhe marrim një matricë të formës

.

,

,

.

9. Operacioni i transpozimit të matricës dhe vetitë e tij.

Përkufizimi: Matrica A' e përftuar nga matrica A duke zëvendësuar rreshtat me kolona quhet e transpozuar në lidhje me matricën A.

Rregullat e mëposhtme për transpozimin e matricave janë të vlefshme:

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

(AB)'=B'A'

Ideja e provës është të tregojë se matricat (AB)' dhe B'A' kanë të njëjtin dimension dhe elementët e tyre përkatës janë të barabartë.

Përkufizimi: Nëse A është një matricë katrore arbitrare dhe A=A’ (-A=A’), atëherë matrica A quhet simetrike
ose anore-simetrike

10. Përkufizimi i një matrice inverse. Vërtetoni se çdo matricë e kthyeshme ka vetëm një përmbysje.

Përkufizimi:

A A -1= A -1 A=E Nga kjo rrjedh se për matricën A -1 anasjellta do të jetë (A -1) -1 =A

Teorema:Çdo matricë e kthyeshme ka një përmbysje unike.

Dëshmi: Le të supozojmë se matrica A ka, së bashku me X, një matricë tjetër të anasjelltë Y, d.m.th. AU=E. Pastaj

(HA)U=EU=U ┐

X(AU)=XE=X ┘Prandaj X=Y. Ato. matrica A ka një përmbysje unike (etj.)

11. Përkufizimi i një matrice inverse. Vërtetoni se (ABC) -1 =C -1 NË -1 A -1 .

Përkufizimi: Një matricë katrore A thuhet se është e kthyeshme nëse ekziston një matricë katrore X e tillë që AX=XA=E. (1)

Çdo matricë X që plotëson barazinë (1) quhet inversi i matricës A ose inversi i matricës A. Matrica e kundërt e matricës A shënohet A -1

A A -1= A -1 A=E Nga kjo rrjedh se për matricën A -1 anasjellta do të jetë (A -1) -1 =A (3)

Teorema: Nëse matricat katrore A, B, C të të njëjtit rend janë të kthyeshme, atëherë produkti i tyre është gjithashtu i kthyeshëm dhe (ABC) -1 =C -1 B -1 A -1 .

Dëshmi: A(B(CC -1)B -1)A -1 =E dhe C -1 (B -1 (A -1 A)B)C=E (h.t.d.)

Për çdo m natyror, sipas përkufizimit, A m = A*A*…*A – m-herë.

Sipas përkufizimit, A 0 = E.

Përkufizimi: Për çdo matricë të kthyeshme A, A -2 =A -1 *A -1 ; A -3 = A -1 *A -1 *A -1 (4)

Nga (3) dhe (4) rrjedh se për secilën matricë të kthyeshme A dhe çdo numër të plotë p dhe q kemi rregulla normale veprimet me gradë:

A r A q =A r+ q

(AB) p =A p B p nëse AB=BA

(A p) q =A p* q

12. Vërtetoni se si rezultat i transpozimit të një matrice të kthyeshme, ne përsëri marrim një matricë të kthyeshme dhe ( A ’) -1 =( A -1 )’.

Teorema: Si rezultat i transpozimit të matricës së kthyeshme A, fitohet përsëri një matricë e kthyeshme dhe (A') -1 = (A -1)'.

Dëshmi: Le të zbatojmë rregullat e transpozimit në relacionin AX=XA=E:

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

A'X'=X'A'=E

Nga përkufizimi i matricës së kundërt rrjedh se (A’) -1 = X’=(A -1)’(h.t.c.)

13. Matricat e bllokut. Mbledhja dhe shumëzimi i matricave të bllokut. Teorema mbi përcaktorin e një matrice thuajse trekëndore.

Një matricë drejtkëndore A mund të ndahet në qeliza (blloqe) drejtkëndëshe me vija vertikale dhe horizontale. Në veçanti, matrica mund të ndahet vetëm me vija horizontale ose vetëm vertikale. (A α,β) s , t – matrica e bllokut. Konsideroni dy matrica A dhe B të të njëjtit dimension dhe me të njëjtën ndarje në blloqe. Blloqet përkatëse A α,β dhe B α,β kanë të njëjtin dimension m α x n β , α=1..s, β=1..t. Më pas, në përputhje me rregullin e mbledhjes së matricës, operacioni i shtimit të matricave të bllokut të së njëjtës madhësi me të njëjtën ndarje në blloqe kryhet saktësisht në të njëjtën mënyrë sikur të kishte elemente numerike në vend të blloqeve.

Për të zgjeruar rregullin e shumëzimit të matricës në matricat bllok, është e nevojshme që të gjitha madhësitë horizontale të blloqeve të matricës së parë të përkojnë me madhësitë përkatëse të faktorit të dytë. Numri i kolonave të bllokut A,β është i barabartë me numrin e rreshtave të bllokut B β,c.

Β ndryshon nga 1 në t, c ndryshon nga 1 në u. Kështu, është e mundur të shumëzohen zyrtarisht matricat A dhe B në të njëjtën mënyrë sikur në vend të blloqeve të kishte elemente numerike.

Përkufizimi: Një matricë katrore në të cilën të gjithë elementët e vendosur nën (sipër) diagonalen kryesore janë të barabartë me 0 quhet matricë trekëndore e sipërme (e poshtme). Koncepte të ngjashme paraqiten për matricat e bllokut.

Përkufizimi: Një matricë blloku A quhet matricë pothuajse trekëndore e sipërme (e poshtme) nëse të gjithë blloqet diagonale dhe vetë matrica A janë matrica katrore, dhe të gjithë blloqet jo diagonale të vendosura nën (sipër) blloqet diagonale janë matrica zero.

Përkufizimi: Një matricë blloku A quhet thuajse diagonale nëse të gjithë blloqet diagonale dhe vetë matrica A janë matrica katrore, dhe të gjitha blloqet jo diagonale janë matrica zero.

Teorema: Përcaktori i një matrice thuajse trekëndore lidhet me përcaktuesin e matricave diagonale nga relacioni i mëposhtëm:

(♀) ku P është produkti.

Dëshmi: Le të shqyrtojmë së pari matricën thuajse trekëndore
ku A 12 = 0,
,
,

A-parësore

Sepse Dhe 12 =0 atëherë nga të gjitha produktet mund të ketë ≠0 vetëm ato në të cilat janë indekset
. Si rezultat, indekset e mbetura mund të marrin vetëm vlera nga grupi
. Në këto kushte, numri i përmbysjeve në një ndërrim
barazohet me:

Duke marrë parasysh këtë gjejmë se

Nga kjo rrjedh se

Duke marrë parasysh në rast i përgjithshëm matricë thuajse trekëndore

Si një matricë
Ku

sipas (*) do të kemi
. Matricë
përsëri kuazi-trekëndësh. Pasi kemi kryer të njëjtin operacion mbi të, marrim
. Pas (p-1) hapave të tillë arrijmë në (♀).

Barazia (♀) vërtetohet në mënyrë të ngjashme në lidhje me matricën e sipërme kuazi-trekëndore (etj.)

Kapitulli 1
MATRICAT DHE PËRCAKTORËT

Në këtë kapitull, ne studiojmë tabelat e numrave të quajtur matrica, të cilat luajnë një rol jetik në të ardhmen. Këtu prezantohen veprimet bazë mbi matricat dhe vetitë e të ashtuquajturve përcaktorë, të cilët janë kryesore karakteristikë numerike matricat katrore.

§ 1. Matricat

1. Koncepti i një matrice. Një matricë është një tabelë drejtkëndëshe e numrave që përmban një numër të caktuar m rreshtash dhe një numër të caktuar n kolonash. Numrat e tipit quhen urdhra matricë. Nëse m = n, matrica quhet katror, ​​dhe numri m = n është rendi i saj. Në të ardhmen, ose vizat e dyfishta ose kllapat do të përdoren për të shkruar matricën:

Megjithatë, për emërtim i shkurtër matricat shpesh do të përdorin ose një shkronjë të madhe latine (për shembull, A) ose simbolin ║ a ij ║, dhe ndonjëherë me një shpjegim:
Numrat a ij të përfshirë në këtë matricë quhen elementë të saj. Në hyrjen a ij - indeksi i parë i nënkupton numrin e rreshtit, dhe indeksi i dytë j nënkupton numrin e kolonës.
Në rastin e një matrice katrore

Prezantohen konceptet e diagonaleve kryesore dhe dytësore. Diagonalja kryesore matrica (1.1) quhet diagonalja a 11 a 22 ...a nn që vjen nga e majta këndi i sipërm të kësaj matrice në këndin e poshtëm të djathtë të saj. Diagonale anësore e së njëjtës matricë quhet diagonalja a n1 a (n-1)2 ...a 1n, duke shkuar nga këndi i poshtëm i majtë në këndin e sipërm të djathtë.

2. Veprimet bazë mbi matricat dhe vetitë e tyre. Para së gjithash, le të biem dakord të llogarisim dy matrica të barabartë, nëse këto matrica kanë renditje të njëjta dhe të gjithë elementët përkatës të tyre janë të njëjtë.
Le të kalojmë në përcaktimin e operacioneve bazë në matrica.
A) Shtimi i matricës.Shuma dy matrica A = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n) dhe B = (i = 1, 2,..., m; j = 1, 2,... , n) të të njëjtit rend m dhe n quhet matricë C= (i = 1, 2,..., m; j = 1, 2,..., n) me rend të njëjtë m dhe n, elementë c ij - të cilat janë të barabarta

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

Për të treguar shumën e dy matricave, përdoret shënimi C = A + B Operacioni i kompozimit të shumës së matricave quhet i tyre shtesë. Pra, sipas përkufizimit

Nga përkufizimi i shumës së matricave, ose më saktë, nga formula (1.2), rrjedh menjëherë se operacioni i mbledhjes së matricës ka të njëjtat veti si operacioni i mbledhjes. numra realë, domethënë:
1) veti komutative: A + B = B + A;
2) veti asociative: (A + B) + C = A + (B + C).
Këto veti ju lejojnë të mos shqetësoheni për rendin e termave të matricave kur shtoni dy ose më shumë matricat

b) Shumëzimi i një matrice me një numër. Puna matrica A = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,... , n) në real
numri λ quhet matrica C = (i = 1, 2,..., m; j = 1, 2,..., n), elementet c ij te se ciles jane te barabarta

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

Për të treguar prodhimin e një matrice me një numër, përdoret shënimi C = λ A ose C = Aλ. Operacioni i kompozimit të prodhimit të një matrice me një numër quhet shumëzim i matricës me këtë numër. Direkt nga formula (1.3) është e qartë se shumëzimi i një matrice me një numër ka vetitë e mëposhtme:
1) një veti kombinuese në lidhje me një faktor numerik: (λ µ )A = λ ( µ A);

2) pronë distributive në lidhje me shumën e matricave: λ (A + B) = λ A + λ B;
3) vetinë e shpërndarjes në lidhje me shumën e numrave: (λ + µ )A = λ A + µ A.
Komentoni. Është e natyrshme të quajmë diferencën midis dy matricave A dhe B të të njëjtit rend një matricë të tillë C të të njëjtit rend m dhe n, e cila në shumë me matricën B jep matricën A. Për të treguar ndryshimin midis dy matricave, një shënim natyror përdoret: C = A - B.
Është shumë e lehtë të verifikohet se diferenca C e dy matricave A dhe B mund të merret sipas rregullit C = A + (-1)B.
c) Shumëzimi i matricës. Puna matricat A = ║ a ij ║(i = 1, 2,..., m; j = 1, 2,..., n), me rend të barabartë me m dhe n, përkatësisht, në matricën B = (i = 1, 2,.. ., n j = 1, 2,..., p), që ka rend të barabartë me n dhe p, përkatësisht, quhet matricë C= (i = 1, 2,..., m; j = 1, 2,... , p), që kanë rend të barabartë me m dhe p, përkatësisht, dhe elementë c ij të përcaktuar me formulën

Për të treguar prodhimin e matricës A dhe matricës B, përdorni shënimin C = A - B. Operacioni i kompozimit të prodhimit të matricës A dhe matricës B quhet shumëzimi këto matrica. Nga përkufizimi i mësipërm rezulton se Matrica A nuk mund të shumëzohet me çdo matricë B: është e nevojshme që numri i kolonave të matricës A të jetë i barabartë me numrin e rreshtave të matricës B.
Në veçanti, të dy produktet A B dhe B A mund të përcaktohen vetëm në rastin kur numri i kolonave A përkon me numrin e rreshtave B dhe numri i rreshtave A përputhet me numrin e kolonave B. Në këtë rast, të dyja matricat A - B dhe B - A do të jenë katrore, por renditjet e tyre, në përgjithësi, do të jenë të ndryshme. Në mënyrë që të dy produktet A B dhe B A jo vetëm të përcaktohen, por edhe të kenë të njëjtin rend, është e nevojshme dhe e mjaftueshme që të dyja matricat A dhe B të jenë matricat katrore të të njëjtit rend.
Formula (1.4) është një rregull për përbërjen e elementeve të matricës C, e cila është prodhim i matricës A dhe matricës B. Ky rregull mund të formulohet edhe verbalisht: element c ij , duke qëndruar në kryqëzimi -vijat e th dhej- kolona e matricës

C = A B, e barabartë me shumën produkte çifte të elementeve përkatëse rreshti i-të matrica A dhe kolona e th e matricës B.
Si shembull i zbatimit të këtij rregulli, ne paraqesim formulën e shumëzimit të matricave katrore të rendit të dytë

Nga formula (1.4) rrjedh vetitë e mëposhtme produkti i matricës A dhe matricës B:
1) veti asociative: (AB)C = A(BC);
2) vetia shpërndarëse në lidhje me shumën e matricave: (A + B)C = AC + BC ose A(B + C) = AB + AC.
Vetia shpërndarëse rrjedh menjëherë nga formula (1.4) dhe (1.2), dhe për të vërtetuar veti asociative mjafton të theksohet se nëse 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 ), pastaj
elementi d il i matricës (AB)C për shkak të (1.4) është i barabartë me dhe elementi d il " i matricës A(BC) është i barabartë me , por atëherë barazia d il = d il " rrjedh nga mundësia e ndryshimit të rendit të mbledhjes në lidhje me j dhe k.
Pyetja në lidhje me vetinë e ndërrimit të produktit të matricës A dhe matricës B ka kuptim të shtrohet vetëm për matricat katrore A dhe B të të njëjtit rend (pasi, siç u tregua më lart, vetëm për matricat e tilla A dhe B janë të dy produkte AB dhe BA A të përcaktuara dhe janë matrica të të njëjtave renditje). Shembujt elementar tregojnë se prodhimi i dy matricave katrore të të njëjtit rend, në përgjithësi, nuk ka vetinë e komutimit. Në fakt, nëse vendosim

Këtu do të tregojmë, megjithatë, raste të rëndësishme të veçanta në të cilat vetia e komutimit është e vërtetë (Dy matrica për produktin e të cilave vetia e komutimit është e vërtetë quhen zakonisht komutim). Ndër matricat katrore, ne veçojmë klasën e të ashtuquajturave diagonale matricat, secila prej të cilave ka elementë të vendosur jashtë diagonales kryesore të barabartë me zero. Çdo matricë diagonale e rendit n ka formën

ku d 1, d 2,..., d n janë çdo numër. Është e lehtë të shihet se nëse të gjithë këta numra janë të barabartë me njëri-tjetrin, d.m.th. d 1 = d 2= ...= d n = d, atëherë për çdo
Për një matricë katrore A të rendit n, vlen barazia AD = DA. Në fakt, le të shënojmë me simbolet Cij dhe cf(j elementet e vendosura në kryqëzimin e rreshtit të i-të dhe kolonës j-ro të matricave AD dhe DA, përkatësisht. Pastaj nga barazia (1.4) dhe nga formën e matricës D marrim se c ij =a ij d j = a ij d , c ij " = d i a ij = da ij (1.6), d.m.th. c ij = c ij " .

Ndër të gjitha matricat diagonale (1.5) me elemente që përputhen d 1 = d 2= ...= d n rol i rendesishem luajnë dy matrica. E para nga këto matrica fitohet për d = 1 dhe quhet Matrica e identitetit të rendit të n-të dhe shënohet me simbolin E. Matrica e dytë fitohet në d = 0 dhe quhet matrica zero e rendit të n-të dhe shënohet me simbolin O. Kështu,

Në bazë të asaj që u vërtetua më lart, AE = EA dhe AO = O A. Për më tepër, nga formula (1.6) është e qartë se

AE = EA = E, AO = OA = O. (1.7)

E para e formulave (1.7) karakterizon rolin e veçantë të matricës së identitetit E, i ngjashëm me rolin që luan numri 1 gjatë shumëzimit të numrave realë. Sa i përket rolit të veçantë të matricës zero O, ai zbulohet jo vetëm nga e dyta e formulave (1.7), por edhe nga barazia elementare e verifikueshme A + O = O + A = A (kjo barazi është pasojë e drejtpërdrejtë e formulës (1.2)).
Si përfundim, vërejmë se koncepti i një matrice zero mund të prezantohet edhe për matricat jo katrore (një matricë zero është çdo matricë, elementët e së cilës janë të gjithë zero).
3. Blloko matricat. Supozoni se një matricë A = ║ a ij ║ duke përdorur linja horizontale dhe vertikale, ajo ndahet në qeliza të veçanta drejtkëndore, secila prej të cilave është një matricë me madhësi më të vogla dhe quhet blloku i matricës origjinale. Në këtë rast, bëhet e mundur të konsiderohet matrica origjinale A si një matricë e re (e ashtuquajtur bllok) A = ║ A αβ ║, elementet A αβ të cilit i shërbejnë këto blloqe.
Ne i shënojmë këto elemente si të mëdha shkronja latine, për të theksuar se ato janë, në përgjithësi, matrica, jo numra, dhe (si elementët numerikë të zakonshëm) ne ofrojmë dy indekse, i pari prej të cilëve tregon numrin e rreshtit të "bllokut" dhe i dyti numrin e "bllokut". kolona”. Për shembull, një matricë

mund të konsiderohet si një matricë blloku, elementët e së cilës janë blloqet e mëposhtme:

Një fakt i jashtëzakonshëm është se veprimet kryesore me matricat e bllokut kryhen sipas të njëjtave rregulla me të cilat kryhen me matricat e zakonshme numerike, vetëm blloqet veprojnë si elementë.
Në fakt, është e lehtë të kontrollohet nëse matrica A = ║ a ij ║është në nivel blloku dhe ka elemente në nivel blloku A αβ, pastaj me të njëjtën ndarje në blloqe matrica λ A = ║λ a ij ║ korrespondojnë me elementet e bllokut λ A αβ(Në këtë rast, elementët e bllokut λ A αβ janë llogaritur vetë duke përdorur rregullën e shumëzimit të matricës A αβ me numrin λ).
Është po aq e lehtë të kontrollohet se nëse matricat A dhe B kanë të njëjtat rende dhe ndahen në blloqe në të njëjtën mënyrë, atëherë shuma e matricave A dhe B korrespondon me një matricë blloku me elementë A αβ = A αβ + B αβ(Këtu A αβ Dhe B αβ- elementet e bllokut të matricave A dhe B).
Së fundi, le të jenë A dhe B dy matrica blloku të tilla që numri i kolonave të secilit bllok A αβ e barabartë me numrin e rreshtave në bllokun B β γ (Kështu që
për çdo α, β dhe γ është përcaktuar prodhimi i matricave A αβ NË β γ ). Atëherë prodhimi C = A B është një matricë me elementë C α γ , të përcaktuara nga formula

Për të vërtetuar këtë formulë, mjafton të shkruajmë pjesët e majta dhe të djathta të saj sipas elementeve të zakonshme (numerike) të matricave A dhe B (këtë ia lëmë lexuesit).
Si shembull i përdorimit të matricave të bllokut, le të ndalemi në konceptin e të ashtuquajturës shumë direkte të matricave katrore. Shuma direkte dy matrica katrore A dhe B të renditjes m dhe n, përkatësisht, quhet matricë e bllokut katror C e rendit m + n, e barabartë me . Për të treguar shumën e drejtpërdrejtë të matricave A dhe B, përdoret shënimi C = A

Gjatë ndërtimit metodat paralele Për të kryer shumëzimin e matricës, së bashku me marrjen në konsideratë të matricave si grupe rreshtash dhe kolonash, përdoret gjerësisht paraqitja në bllok e matricave. Le të hedhim një vështrim më të afërt këtë metodë organizimi i llogaritjeve.

7.4.1. Përcaktimi i nëndetyrave

Blloku i ndarjes së matricës përshkruhet në detaje në seksionin e parë "Metodat paralele të shumëzimit matricë-vektor". Me këtë metodë të ndarjes së të dhënave, matricat origjinale A, B dhe matrica rezultuese C përfaqësohen si grupe blloqesh. Për një paraqitje më të thjeshtë të materialit të mëposhtëm, më tej do të supozojmë se të gjitha matricat janë katrore me madhësi nxn, numri i blloqeve horizontalisht dhe vertikalisht është i njëjtë dhe i barabartë me q (d.m.th., madhësia e të gjithë blloqeve është e barabartë me kxk, k =n/q). Me këtë paraqitje të të dhënave, operacioni i matricës shumëzimi i matricës A dhe B në formë blloku mund të përfaqësohen si më poshtë:

Ku çdo bllok C ij i matricës C përcaktohet sipas shprehjes

Kur ndahen të dhënat në blloqe për të përcaktuar nëndetyrat bazë, duket e natyrshme të merren si bazë llogaritjet e kryera në blloqet e matricës. Duke marrë parasysh sa më sipër, ne përcaktojmë nëndetyrën bazë si një procedurë për llogaritjen e të gjithë elementëve të njërit prej blloqeve të matricës C.

Për të kryer të gjitha llogaritjet e nevojshme, nëndetyrat themelore duhet të kenë akses në grupet e duhura të rreshtave të matricës A dhe kolonave të matricës B. Vendosja e të gjitha të dhënave të kërkuara në çdo nëndetyrë do të çojë në mënyrë të pashmangshme në dyfishim dhe një rritje të konsiderueshme të sasisë së memories së përdorur. Si rezultat, llogaritjet duhet të organizohen në atë mënyrë që në çdo moment aktual në kohë nën-detyrat të përmbajnë vetëm një pjesë të të dhënave të nevojshme për llogaritjet, dhe qasja në pjesën tjetër të të dhënave sigurohet duke transferuar të dhëna midis përpunuesve. Një qasje e mundshme është algoritmi Fox ( Dhelpra) – diskutohet më tej në këtë nënseksion. Metoda e dytë është algoritmi Cannon ( Top) – dhënë në nënparagrafin 7.5.

7.4.2. Identifikimi i varësive të informacionit

Pra, baza për llogaritjet paralele për shumëzimin e matricës me ndarjen e të dhënave në bllok është një qasje në të cilën nëndetyrat bazë janë përgjegjëse për llogaritjen e blloqeve individuale të matricës C dhe në të njëjtën kohë, në nën-detyrat në çdo përsëritje të llogaritjeve ka vetëm një bllok i matricave origjinale A dhe B. Për të numëruar nëndetyrat, do të përdorim indekset e blloqeve të matricës C të vendosura në nëndetyrat, d.m.th. nëndetyra (i,j) është përgjegjëse për llogaritjen e bllokut C ij - kështu, grupi i nëndetyrave formon një rrjetë katrore që korrespondon me strukturën e paraqitjes së bllokut të matricës C .

Një mënyrë e mundshme për të organizuar llogaritjet në kushte të tilla është përdorimi i të njohurve Algoritmi i dhelprës (Dhelpra) - shih, për shembull, [ [34] , [51] ].

Në përputhje me algoritmin Fox, gjatë llogaritjeve, katër blloqe matricë janë të vendosura në secilën nëndetyrë bazë (i, j):

• blloku C ij i matricës C, i llogaritur nga nëndetyra;
• blloku A ij i matricës A, i vendosur në nëndetyrë përpara fillimit të llogaritjeve;
• blloqet A" ij, B" ij të matricave A dhe B, të marra nga nëndetyra gjatë llogaritjeve.

Performanca metodë paralele përfshin:

• faza e inicializimit, në të cilën blloqet A ij , B ij transferohen në secilën nëndetyrë (i, j) dhe blloqet C ij rivendosen në zero në të gjitha nëndetyrat;
• faza e llogaritjeve, brenda së cilës në çdo përsëritje l, 0<=l

7.6.

Për të shpjeguar këto rregulla të metodës paralele në Fig. Figura 7.6 tregon gjendjen e blloqeve në secilën nëndetyrë gjatë përsëritjeve të fazës së llogaritjes (për një rrjetë nëndetyrash 2x2).

7.4.3. Shkallëzimi dhe shpërndarja e nëndetyrave nëpër procesorë Në skemën e konsideruar të llogaritjes paralele, numri i blloqeve mund të ndryshojë në varësi të zgjedhjes së madhësisë së bllokut - këto madhësi mund të zgjidhen në atë mënyrë që numri i përgjithshëm i nëndetyrave bazë të përputhet me numrin e procesorëve p. Kështu, për shembull, në rastin më të thjeshtë, kur numri i përpunuesve mund të paraqitet në formë (d.m.th. është një katror i përsosur), mund të zgjidhet numri i blloqeve në matricat vertikalisht dhe horizontalisht të jetë i barabartë (d.m.th.). Kjo metodë e përcaktimit të numrit të blloqeve çon në faktin se sasia e llogaritjeve në secilën nëndetyrë është e njëjtë dhe në këtë mënyrë arrihet balancimi i plotë i ngarkesës llogaritëse midis procesorëve. Në një rast më të përgjithshëm, me një numër arbitrar të procesorëve dhe madhësive të matricës llogaritjet balancuese

Për të zbatuar në mënyrë efektive algoritmin Fox, në të cilin nëndetyrat bazë përfaqësohen në formën e një grilë katrore dhe gjatë llogaritjes kryhen operacionet e transferimit të blloqeve përgjatë rreshtave dhe kolonave të rrjetës së nëndetyrave, zgjidhja më adekuate është organizimi i grupit. të përpunuesve të disponueshëm edhe në formën e një rrjete katrore. Në këtë rast, është e mundur që drejtpërdrejt të hartohet një grup nën-detyrash për shumë procesorë - nëndetyra bazë (i,j) duhet të vendoset në procesorin Pi,j. Struktura e nevojshme e rrjetit të transmetimit të të dhënave mund të sigurohet në nivel fizik nëse topologjia e sistemit kompjuterik ka formën e një rrjete ose një grafik të plotë.

7.4.4. Analiza e Performancës

Le të përcaktojmë kompleksitetin llogaritës të këtij algoritmi Fox. Ndërtimi i vlerësimeve do të ndodhë në varësi të përmbushjes së të gjitha supozimeve të bëra më parë: të gjitha matricat janë katrore me madhësi nxn, numri i blloqeve horizontalisht dhe vertikalisht është i njëjtë dhe i barabartë me q (d.m.th., madhësia e të gjithë blloqeve është e barabartë me kxk , k=n/q), procesorët formojnë rrjetë katrore dhe numri i tyre është i barabartë me p=q 2.

Siç është vërejtur tashmë, algoritmi Fox kërkon përsëritje q për ekzekutimin e tij, gjatë të cilave secili procesor shumëzon blloqet e tij aktuale të matricave A dhe B dhe shton rezultatet e shumëzimit në vlerën aktuale të bllokut të matricës C. Duke marrë parasysh supozimet e bëra, numri total i operacioneve të kryera në këtë rast do të jetë i rendit n 3 /p. Si rezultat, treguesit e përshpejtimit dhe efikasitetit të algoritmit kanë formën:

Analiza e përgjithshme e kompleksitetit përsëri ofron metrika ideale të efikasitetit të llogaritjes paralele. Le të sqarojmë marrëdhëniet e marra - për këtë do të tregojmë më saktë numrin e operacioneve llogaritëse të algoritmit dhe do të marrim parasysh kostot e ekzekutimit operacionet e transferimit të të dhënave ndërmjet procesorëve.

Le të përcaktojmë numrin e operacioneve llogaritëse. Vështirësia e ekzekutimit shumëzimi skalar rreshtat e një blloku të matricës A për kolonën e një blloku të matricës B mund të vlerësohen si 2(n/q)-1. Numri i rreshtave dhe kolonave në blloqe është i barabartë me n/q dhe, si rezultat, kompleksiteti i operacionit të shumëzimit të bllokut është i barabartë me (n 2 /p) (2n/q-1) . Shtimi i blloqeve kërkon operacione n 2 /p. Duke marrë parasysh të gjitha shprehjet e mësipërme, koha e ekzekutimit të operacioneve llogaritëse të algoritmit Fox mund të vlerësohet si më poshtë:

(kujtoni se ka kohë ekzekutimi për një operacion skalar elementar).

Le të vlerësojmë kostot e zbatimit operacionet e transferimit të të dhënave ndërmjet procesorëve. Në çdo përsëritje të algoritmit, përpara shumëzimit të blloqeve, një nga procesorët në një rresht të rrjetit të procesorit dërgon bllokun e tij të matricës A tek pjesa tjetër e procesorëve në rreshtin e tij. Siç u përmend më herët, me një topologji rrjeti në formën e një hiperkubi ose një grafik të plotë, ky operacion mund të kryhet në hapat log 2 q, dhe vëllimi i blloqeve të transmetuara është i barabartë me n 2 /p. Si rezultat, koha e ekzekutimit të operacionit të transferimit të blloqeve të matricës A duke përdorur modelin Hockney mund të vlerësohet si

Ku është vonesa, është xhiroja e rrjetit të të dhënave dhe w është madhësia e elementit të matricës në bajt. Në rastin kur topologjia e rreshtave të rrjetit të procesorit është një unazë, shprehja për vlerësimin e kohës së transmetimit të blloqeve të matricës A merr formën:

Pastaj, pas shumëzimit të blloqeve të matricës, procesorët i transmetojnë blloqet e tyre të matricës B tek procesorët e mëparshëm përgjatë kolonave të rrjetës së procesorit (përpunuesit e parë në kolona transmetojnë të dhënat e tyre tek procesorët e fundit në kolonat e rrjetës). Këto operacione mund të kryhen nga procesorët paralelisht, dhe kështu kohëzgjatja e një operacioni të tillë komunikimi është:

(kujtojmë se parametri q përcakton madhësinë e rrjetit të procesorit dhe ).