Matricea blocurilor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 25 aprilie 2019; verificările necesită 3 modificări .

Matricea bloc (celulă) - reprezentare a matricei , în care este tăiată prin linii verticale și orizontale în părți dreptunghiulare - blocuri ( celule ):

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} și \mathbf{A}_{12} și \cdots &\mathbf{A}_{1t}\\ \mathbf{A} _{21} & \mathbf{A}_{22} & \cdots &\mathbf{A}_{2t}\\ \vdots & \vdots & \ddots &\vdots \\ \mathbf{A}_{s1 } & \mathbf{A}_{s2} & \cdots &\mathbf{A}_{st}\end{bmatrix}

unde blocul are dimensiunea pentru și $\mathbf {A} _{\alpha \beta )$ $m_\alpha\times n_\beta$ $\alpha = 1, 2,\dots, s$ $\beta = 1, 2,\dots, t$

Exemplu

Dimensiunea matricei 4×4

\mathbf{P} = \begin{bmatrix} 1 & 1 & 2 & 2\\ 1 & 1 & 2 & 2\\ 3 & 3 & 4 & 4\\ 3 & 3 & 4 & 4\end{bmatrix}

poate fi reprezentat ca o matrice de blocuri de patru blocuri 2x2 fiecare.

La următoarea definiție a blocului

\mathbf{P}_{11} = \begin{bmatrix} 1 și 1 \\ 1 și 1 \end{bmatrix}, \mathbf{P}_{12} = \begin{bmatrix} 2 și 2\\ 2 & 2\end{bmatrix}, \mathbf{P}_{21} = \begin{bmatrix} 3 și 3 \\ 3 și 3 \end{bmatrix}, \mathbf{P}_{22} = \begin{ bmatrix} 4 și 4\\ 4 și 4\end{bmatrix}

Matricea blocurilor poate fi scrisă după cum urmează:

\mathbf{P} = \begin{bmatrix} \mathbf{P}_{11} și \mathbf{P}_{12}\\ \mathbf{P}_{21} și \mathbf{P}_{22 }\end{bmatrix}.

Operațiuni

Formal, operațiunile cu matrice bloc se efectuează după aceleași reguli ca și cum ar fi elemente numerice în loc de blocuri. Pentru fezabilitatea operațiunilor, este necesară o potrivire adecvată a dimensiunilor blocurilor. De exemplu, la înmulțirea matricelor de bloc, este necesar ca dimensiunile orizontale ale blocurilor primului factor să coincidă cu dimensiunile verticale corespunzătoare ale celui de-al doilea factor [1] .

Sumă directă

Suma directă a două matrici pătrate și dimensiuni și este definită ca o matrice bloc de următoarea formă: $\mathbf {A}$ $\mathbf {B}$ $m \ori m$ $n\ ori n$

\mathbf{A} \oplus \mathbf{B} = \begin{bmatrix} \mathbf{A} și \mathbf{0}\\ \mathbf{0} și \mathbf{B}\end{bmatrix}

unde denotă blocul zero (matricea de tip zero deasupra și dedesubt). Această operație este necomutativă , dar asociativă [2] . $\mathbf {0}$ $m\ori n$ $n \ori m$

Tipuri de matrici de bloc

Multe tipuri de matrice pot fi reprezentate sub formă de bloc. În acest caz, la nume se adaugă blocul sau blocul de prefix, iar operațiile pe elemente sunt transformate în operațiuni pe blocuri.

Matrice bloc-diagonală (cvasi-diagonală)

Pentru o matrice bloc-diagonală , toate blocurile, cu excepția celor situate pe diagonala principală, sunt matrice zero.

Matricea arată ca

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{1} & 0 & \cdots & 0 \\ 0 & \mathbf{A}_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{A}_{n} \end{bmatrix},

unde fiecare element este o matrice diferită de zero. $\mathbf{A}_k$

Determinantul unei matrice cvasidiagonale pătrate este egal cu produsul determinanților celulelor diagonale.

Matrice cvasi-triunghiulară

Cvasi-triunghiulară este o matrice pătrată de bloc ale cărei blocuri sunt la (sau ): $\mathbf {A}$ $\mathbf{A}_{ij} = 0$ $i>j$ $i<j$

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \cdots & \mathbf{A}_{1n} \\ 0 & \mathbf{ A}_{22} & \cdots & \mathbf{A}_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{A}_{nn} \end{bmatrix}

Determinantul unei matrici cvasi-triunghiulare este egal cu produsul determinanților blocurilor diagonale. Este ușor de observat că o matrice bloc-diagonală este un caz special al unei matrice cvasi-triunghiulare [3] .

Bloc matrice tridiagonală

Vezi și matrice triagonală .

Blocați matricea Toeplitz

Vezi și matricea Toeplitz .

Înmulțirea în bloc a matricelor

Pentru a crește eficiența utilizării memoriei cache a CPU , există un algoritm pentru multiplicarea matricei de bloc

C=AB=\left[{\begin{array}{ccccc}A_{{11}}&A_{{12}}&...&A_{{1n}}\\A_{{21}}&A_{{22 }}&...&A_{{2n}}\...&...&...&...\\A_{{n1}}&A_{{n2}}&...&A_{{ nn}}\\\end{array}}\right]\times \left[{\begin{array}{ccccc}B_{{11}}&B_{{12}}&...&B_{{1n}} \\B_{{21}}&B_{{22}}&...&B_{{2n}}\\...&...&...&...\\B_{{n1}}&B_ {{n2}}&...&B_{{nn}}\\\end{array}}\right]

în care matricea rezultată

C=\left[{\begin{array}{ccccc}C_{{11}}&C_{{12}}&...&C_{{1n}}\\C_{{21}}&C_{{22}} &...&C_{{2n}}\\...&...&...&...\\C_{{n1}}&C_{{n2}}&...&C_{{nn} }\\\end{matrice}}\right]

se formează bloc cu bloc folosind formula binecunoscută

C_{{ij}}=\sum _{{k=1}}^{{n}}A_{{ik}}\times B_{{kj}}

sau analogii săi mai rapidi, iar dimensiunea datelor procesate la fiecare iterație nu depășește capacitatea memoriei cache. Mărimea blocului depinde direct de arhitectura sistemului de calcul și determină timpul de execuție al înmulțirii [4] . O abordare similară este utilizată în multiplicarea matricei bazată pe GPU cu optimizarea utilizării limitate a memoriei partajate [5] [6] .

Formule

Formula Frobenius

Pentru a inversa o matrice bloc nedegenerată, se poate folosi formula Frobenius :

\left[\begin{array}{ccccc} A & B \\ C & D \\ \end{array}\right]^{-1} = \left[\begin{array}{ccccc} A^{- 1} +A^{-1} BH^{-1} CA^{-1} și -A^{-1} BH^{-1} \\ -H^{-1} CA^{-1} & H^{-1} \\ \end{matrice}\right],

unde este o matrice pătrată nesingulară de dimensiune , este o matrice pătrată de dimensiune și . $A$ $m_1\ori m_1$ $D$ $m_2\ori m_2$ $H=D-CA^{-1} B$

Această formulă ne permite să reducem inversarea matricei de mărime la inversarea a două matrici mai mici și și operațiile de înmulțire și adunare a matricelor de dimensiuni , , , [7] . $(m_1+m_2)\ori (m_1+m_2)$ $m_1\ori m_1$ $m_2\ori m_2$ $m_1\ori m_1$ $m_2\ori m_2$ $m_1\ori m_2$ $m_2\ori m_1$

Note

↑ Gantmakher, 2004 , p. 53-54.
↑ Ilyin, Poznyak, 2007 , p. optsprezece.
↑ Gantmakher, 2004 , p. 55.
↑ Vatutin E.I., Martynov I.A., Titov V.S. Evaluarea performanței reale a procesoarelor moderne în problema înmulțirii matricei pentru o implementare software cu un singur thread Arhivat 11 ianuarie 2015 la Wayback Machine // Proceedings of the Southwestern State University . Seria: Management, tehnologie informatică, informatică. Instrumente medicale. 2013. Nr 4. - S. 11-20.
↑ Vatutin E. I., Martynov I. A., Titov V. S. Estimarea performanței reale a plăcilor video moderne cu suport de tehnologie CUDA în problema înmulțirii matricelor Arhivat 11 ianuarie 2015 la Wayback Machine // Proceedings of the Southwestern State University . Seria: Management, tehnologie informatică, informatică. Instrumente medicale. 2014. Nr 2. - S. 8-17.
↑ Calcul paralel pe GPU. Arhitectura și modelul software al CUDA / Boreskov A. V., Kharlamov A. A. Markovsky N. D. și colab. - M. : Izd-vo Mosk. un-ta, 2012. - 336 p.
↑ Gantmakher, 2004 , p. 57-58.

Literatură

Gantmakher F. R. . Teoria matricelor. - a 5-a ed. — M .: Fizmatlit , 2004. — 560 p. — ISBN 5-9221-0524-8 .
Ilyin V. A. , Poznyak E. G. . Algebră liniară. - Ed. a VI-a, stereotip. — M .: Fizmatlit , 2007. — 278 p. — (Curs de Matematică Superioară și Fizică Matematică, numărul 4). - ISBN 978-5-9221-0481-4 .
Rublev A. N. Algebră liniară. - M . : Şcoala superioară , 1968. - 387 p.