Blok matrix

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. april 2019; checks kræver 3 redigeringer .

Blok (celle) matrix - repræsentation af matrixen , hvor den er skåret af lodrette og vandrette linjer i rektangulære dele - blokke ( celler ):

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \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}

hvor blok har størrelse til og ${\displaystyle \mathbf {A} _{\alpha \beta ))$ $m_\alfa\ gange n_\beta$ $\alfa = 1, 2,\prikker, s$ $\beta = 1, 2,\prikker, t$

Eksempel

Matrix størrelse 4×4

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

kan repræsenteres som en blokmatrix af fire 2x2 blokke hver.

Ved næste blokdefinition

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

Blokmatricen kan skrives som følger:

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

Operationer

Formelt udføres operationer med blokmatricer efter de samme regler, som hvis der var numeriske elementer i stedet for blokke. For gennemførligheden af operationer er passende matchning af blokstørrelser nødvendig. Når man for eksempel multiplicerer blokmatricer, kræves det, at de vandrette dimensioner af blokkene af den første faktor falder sammen med de tilsvarende vertikale dimensioner af den anden faktor [1] .

Direkte sum

Den direkte sum af to kvadratiske matricer og størrelser og er defineret som en blokmatrix af følgende form: $\mathbf {A}$ $\mathbf {B}$ $m \ gange m$ $n\ gange n$

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

hvor angiver nulblokken (nultypematrix over og under). Denne operation er ikke -kommutativ , men associativ [2] . $\mathbf {0}$ $m\ gange n$ $n \ gange m$

Typer af blokmatricer

Mange typer af matricer kan repræsenteres i blokform. I dette tilfælde tilføjes præfikset blok eller blok til navnet, og operationer på elementer omdannes til operationer på blokke.

Blok-diagonal (kvasi-diagonal) matrix

For en blokdiagonal matrix er alle blokke, undtagen dem, der er placeret på hoveddiagonalen, nulmatricer.

Matrixen ser ud

\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},

hvor hvert element er en matrix, der ikke er nul. $\mathbf{A}_k$

Determinanten af en kvadratisk kvasidiagonal matrix er lig med produktet af determinanterne af de diagonale celler.

Kvasi-trekant matrix

Kvasi-trekant er en kvadratisk blokmatrix, hvis blokke er ved (eller ): $\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}

Determinanten af en kvasi-trekant matrix er lig med produktet af determinanterne af de diagonale blokke. Det er let at se, at en blokdiagonal matrix er et specialtilfælde af en kvasi-trekantet [3] .

Bloker tridiagonal matrix

Se også tridiagonal matrix .

Bloker Toeplitz matrix

Se også Toeplitz matrix .

Blokmultiplikation af matricer

For at øge effektiviteten ved at bruge CPU- cachehukommelsen er der en algoritme til blokmatrixmultiplikation

C=AB=\venstre[{\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]

hvori den resulterende matrix

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

dannes blok for blok ved hjælp af den velkendte formel

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

eller dets hurtigere analoger, og størrelsen af de behandlede data ved hver iteration overstiger ikke cachehukommelsens kapacitet. Blokstørrelsen afhænger direkte af computersystemets arkitektur og bestemmer multiplikationsudførelsestiden [4] . En lignende tilgang bruges i GPU -baseret matrixmultiplikation med optimering af begrænset brug af delt hukommelse [5] [6] .

Formler

Frobenius formel

For at invertere en ikke-degenereret blokmatrix kan Frobenius -formlen bruges :

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

hvor er en ikke-singular kvadratisk matrix af størrelse , er en kvadratisk matrix af størrelse og . $EN$ $m_1\ gange m_1$ $D$ $m_2\ gange m_2$ $H=D-CA^{-1} B$

Denne formel giver os mulighed for at reducere inversionen af størrelsesmatrixen til inversionen af to mindre matricer og og operationerne med multiplikation og addition af matricer af størrelser , , , [7] . $(m_1+m_2)\ gange (m_1+m_2)$ $m_1\ gange m_1$ $m_2\ gange m_2$ $m_1\ gange m_1$ $m_2\ gange m_2$ $m_1\ gange m_2$ $m_2\ gange m_1$

Noter

↑ Gantmakher, 2004 , s. 53-54.
↑ Ilyin, Poznyak, 2007 , s. atten.
↑ Gantmakher, 2004 , s. 55.
↑ Vatutin E.I., Martynov I.A., Titov V.S. Evaluering af den reelle ydeevne af moderne processorer i problemet med matrixmultiplikation for en enkelt-trådet softwareimplementering Arkiveret 11. januar 2015 på Wayback Machine // Proceedings of the Southwestern State University . Serie: Ledelse, computerteknologi, informatik. Medicinsk instrumentering. 2013. nr. 4. - S. 11-20.
↑ Vatutin E. I., Martynov I. A., Titov V. S. Estimering af den reelle ydeevne af moderne videokort med CUDA-teknologistøtte i problemet med matrixmultiplikation Arkiveret 11. januar 2015 på Wayback Machine // Proceedings of the Southwestern State University . Serie: Ledelse, computerteknologi, informatik. Medicinsk instrumentering. 2014. nr. 2. - S. 8-17.
↑ Parallel databehandling på GPU'en. Arkitektur og softwaremodel af CUDA / Boreskov A. V., Kharlamov A. A. Markovsky N. D. et al. - M . : Izd-vo Mosk. un-ta, 2012. - 336 s.
↑ Gantmakher, 2004 , s. 57-58.

Litteratur

Gantmakher F. R. . Matrix teori. - 5. udg. — M .: Fizmatlit , 2004. — 560 s. — ISBN 5-9221-0524-8 .
Ilyin V. A. , Poznyak E. G. . Lineær algebra. - 6. udg., stereotypisk. — M .: Fizmatlit , 2007. — 278 s. — (Kursus i højere matematik og matematisk fysik, hæfte 4). - ISBN 978-5-9221-0481-4 .
Rublev A. N. Lineær algebra. - M . : Højere skole , 1968. - 387 s.