Otevřít hlavní menu

Násobení matic nebo též maticové násobení je v matematice zobecnění násobení čísel na matice. Formálně se dá definovat jako binární operace nad množinou matic. Využívá se v matematice, fyzice a jejich aplikacích pro popis skládání lineárních zobrazení.

Formální definiceEditovat

Pokud A je matice o rozměrech m × n a B je matice n × p, jejich součin   je matice s rozměry m × p definována vztahem

 

pro všechny prvky (i , j) výsledné matice.

Prvek v i-tém řádku a j-tém sloupci výsledné matice lze také chápat jako skalární součin vektoru i-tého řádku první matice s vektorem j-tého sloupce druhé matice.

Tečka   se obvykle vynechává a píše se pouze  .

Příklad výpočtuEditovat

 
Ilustrační obrázek

Definujme matice:   Jejich součin je

 
(Tj. prvky matice A zůstávají v řádcích tak, jak jsou, a prvky v matici B se rozmístí opět do levého a pravého sloupce.)

VlastnostiEditovat

  • Maticové násobení odpovídá skládání lineárních zobrazení, které matice reprezentují.
  • Maticové násobení je distributivní vůči sčítání, tj.   pro všechny matice, pro které má rovnice smysl.
  • Násobení reálných resp. komplexních matic je lineární vůči násobení reálným resp. komplexním číslem, tj.  , pokud má rovnice smysl.
  • Matice vzhledem k součinu můžou být dělitelé nuly, tj. součin dvou nenulových matic může být nulová matice.
  • Maticové násobení není komutativní, tedy obecně  .
  • Násobení matice   jednotkovou maticí   zprava i zleva je identické zobrazení, tj.  , pokud má rovnice smysl.
  • Maticové násobení je asociativní, tedy  , pokud prvky matice jsou z asociativního okruhu (např. reálná nebo komplexní čísla).
  • Pro čtvercové matice platí  , tj. determinant součinu je součin determinantů.
  • Transpozice součinu matic je součin transponovaných matic v opačném pořadí, tj.  
  • Inverzní matice součinu regulárních matic je součin inverzních matic v opačném pořadí, tj.  
  • Hermitovské sdružení součinu matic je součin hermitovsky sdružených matic v opačném pořadí, tj.  

Výpočetní náročnostEditovat

Výpočetní náročnost výše popsaného algoritmu je   (počítáme n2 čísel; pro každé potřebujeme n násobení). Existují však algoritmy s nižší složitostí vhodné pro matice vyšších řádů. Nejpoužívanější z nich je Strassenův algoritmus se složitostí  . Nižší složitost u tohoto algoritmu však získáváme za cenu snížené numerické stability. Asymptoticky nejrychlejší ze známých algoritmů je Coppersmithův-Winogradův algoritmus ( ), který je však použitelný až pro matice tak velkých řádů, že je nelze zpracovávat pomocí současných počítačů[1].

Teoreticky by se dala složitost ještě zmenšit, ale nikdy nemůže být menší než  , neboť počítáme n2 čísel.

Hledání nejkratší cesty v grafuEditovat

Násobení matic s malou výpočetní složitostí lze využít i pro hledání nejkratší cesty v grafu z každého do každého vrcholu. To má v nejjednodušší podobě složitost  .

Graf lze popsat maticí vzdáleností A. Pokud je pro výpočty operace sčítání dvou čísel definována jako jejich minimum, a místo násobení se použije sčítání, je možno matici nejkratších cest B získat jako ( ) kde n je řád matice vzdáleností. Při reálném výpočtu není třeba cyklicky násobit původní maticí, ale vždy se vynásobí vzniklé výsledky - nejkratší cesty jsou získány po log2(n) násobeních. Je-li použit pro násobení algoritmus se složitostí menší než  , složitost hledání cest se tímto postupem sníží.

ReferenceEditovat

Související článkyEditovat

Externí odkazyEditovat