Bloková matice

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. dubna 2019; kontroly vyžadují 3 úpravy .

Bloková (buňková) matice - znázornění matice , ve které je rozřezána svislými a vodorovnými čarami na obdélníkové části - bloky ( buňky ):

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

kde blok má velikost pro a ${\displaystyle \mathbf {A} _{\alpha \beta ))$ $m_\alpha\krát n_\beta$ $\alpha = 1, 2,\tečky, s$ $\beta = 1, 2,\tečky, t$

Příklad

Velikost matrice 4×4

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

může být reprezentován jako bloková matice se čtyřmi bloky 2x2 každý.

Při další definici bloku

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

Blokovou matici lze zapsat následovně:

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

Operace

Formálně se operace s blokovými maticemi provádějí podle stejných pravidel, jako kdyby byly místo bloků číselné prvky. Pro proveditelnost operací je nutné vhodné sladění velikostí bloků. Například při násobení blokových matic je požadováno, aby se horizontální rozměry bloků prvního faktoru shodovaly s odpovídajícími vertikálními rozměry druhého faktoru [1] .

Přímý součet

Přímý součet dvou čtvercových matic a velikostí a je definován jako bloková matice následujícího tvaru: $\mathbf {A}$ $\mathbf {B}$ $m \krát m$ $n\krát n$

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

kde označuje nulový blok (matice nulového typu nahoře a dole). Tato operace je nekomutativní , ale asociativní [2] . $\mathbf {0}$ $m\krát n$ $n \krát m$

Typy blokových matic

Mnoho typů matic může být reprezentováno v blokové formě. V tomto případě se k názvu přidá blok nebo blok předpony a operace s prvky se transformují na operace s bloky.

Blokově-diagonální (kvazi-diagonální) matice

U blokově diagonální matice jsou všechny bloky, kromě těch, které se nacházejí na hlavní diagonále, nulové matice.

Matrix vypadá

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

kde každý prvek je nenulová matice. $\mathbf{A}_k$

Determinant čtvercové kvazidiagonální matice se rovná součinu determinantů diagonálních buněk.

Kvazitrojúhelníková matice

Kvazitrojúhelníková je bloková čtvercová matice, jejíž bloky jsou na (nebo ): $\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}

Determinant kvazitrojúhelníkové matice se rovná součinu determinantů diagonálních bloků. Je snadné vidět, že blokově diagonální matice je speciálním případem kvazitrojúhelníkové [3] .

Bloková tridiagonální matice

Viz také tridiagonální matice .

Bloková matice Toeplitz

Viz také Toeplitzova matice .

Blokové násobení matic

Aby se zvýšila efektivita používání vyrovnávací paměti CPU , existuje algoritmus pro násobení matice bloků

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]

ve kterém je výsledná matice

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

se tvoří blok po bloku pomocí známého vzorce

C_{{ij}}=\součet _{{k=1}}^{{n}}A_{{ik}}\krát B_{{kj}}

nebo jeho rychlejší analogy a velikost zpracovávaných dat při každé iteraci nepřesahuje kapacitu vyrovnávací paměti. Velikost bloku přímo závisí na architektuře výpočetního systému a určuje dobu provádění násobení [4] . Podobný přístup se používá při násobení matic na GPU s optimalizací omezeného využití sdílené paměti [5] [6] .

Vzorce

Frobeniův vzorec

K invertování nedegenerované blokové matice lze použít Frobeniusův vzorec :

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

kde je nesingulární čtvercová matice velikosti , je čtvercová matice velikosti a . $A$ $m_1\krát m_1$ $D$ $m_2\krát m_2$ $H=D-CA^{-1} B$

Tento vzorec nám umožňuje redukovat inverzi matice velikostí na inverzi dvou menších matic a operace násobení a sčítání matic velikostí , , , [7] . $(m_1+m_2)\krát (m_1+m_2)$ $m_1\krát m_1$ $m_2\krát m_2$ $m_1\krát m_1$ $m_2\krát m_2$ $m_1\krát m_2$ $m_2\krát m_1$

Poznámky

↑ Gantmakher, 2004 , str. 53-54.
↑ Ilyin, Poznyak, 2007 , str. osmnáct.
↑ Gantmakher, 2004 , str. 55.
↑ Vatutin E.I., Martynov I.A., Titov V.S. Hodnocení skutečného výkonu moderních procesorů v problému násobení matic pro implementaci jednovláknového softwaru Archivováno 11. ledna 2015 na Wayback Machine // Proceedings of the Southwestern State University . Řada: Management, výpočetní technika, informatika. Lékařské přístroje. 2013. č. 4. - S. 11-20.
↑ Vatutin E. I., Martynov I. A., Titov V. S. Odhad skutečného výkonu moderních grafických karet s podporou technologie CUDA v problému násobení matic Archivováno 11. ledna 2015 na Wayback Machine // Proceedings of the Southwestern State University . Řada: Management, výpočetní technika, informatika. Lékařské přístroje. 2014. č. 2. - S. 8-17.
↑ Paralelní výpočet na GPU. Architektura a softwarový model CUDA / Boreskov A. V., Kharlamov A. A. Markovsky N. D. et al. - M . : Izd-vo Mosk. un-ta, 2012. - 336 s.
↑ Gantmakher, 2004 , str. 57-58.

Literatura

Gantmakher F. R. Teorie matic. - 5. vyd. — M .: Fizmatlit , 2004. — 560 s. — ISBN 5-9221-0524-8 .
Ilyin V.A. , Poznyak E.G. Lineární algebra. - 6. vyd., stereotypní. — M .: Fizmatlit , 2007. — 278 s. — (Kurz vyšší matematiky a matematické fyziky, číslo 4). - ISBN 978-5-9221-0481-4 .
Rublev A. N. Lineární algebra. - M . : Vyšší škola , 1968. - 387 s.