Numerika pro teoretické fyziky ← →

Dodatek

Dodatek: Normy vektorů a matic

Normy na vektorových prostorech

Definice (Norma)

Norma \(\|\cdot\|\) je zobrazení (funkce) obecně z \(\mathbb{C}^m\) do \(\mathbb{R}\), které pro \(\forall x, y \in \mathbb{C}^m\) a \(\forall \alpha \in \mathbb{C}\) splňuje:

  1. \(\|x\| \geq 0\), přičemž \(\|x\| = 0\) právě tehdy, když \(x = 0\);
  2. \(\|x+y\| \leq \|x\| + \|y\|\) (trojúhelníková nerovnost);
  3. \(\|\alpha x\| = |\alpha|\,\|x\|\).

Na prostoru \(\mathbb{C}^m\) se obvykle používají tzv. \(p\)-normy. Ty mají následující jednotkové „koule“, tedy množiny \(\{x \in \mathbb{C}^m : \|x\| \leq 1\}\).

Pro \(p = 1\) je

\begin{equation}\label{eq:normy:norma_1} \|x\|_1 = \sum_{i=1}^{m} |x_i| . \end{equation}
Interaktivní ukázka · Jednotková koule 1-normy

Jednotková koule 1-normy v rovině je kosočtverec (otočený čtverec) se středem v počátku, protínající obě osy v jednotkové vzdálenosti; vyšrafovaná je celá množina \(\{x : |x_1| + |x_2| \leq 1\}\). Táhněte bodem \(x\): tučné úsečky ukazují oba sčítance \(|x_1|\) a \(|x_2|\) a čárkovaný kosočtverec je vrstevnice \(\|\cdot\|_1 = \|x\|_1\). Zkuste bod posunout tak, aby zůstala \(\|x\|_1\) stejná — uvidíte, že se pohybujete po přímé hraně, a proto má koule 1-normy ostré vrcholy právě na osách.

Pro \(p = \infty\) je

\begin{equation}\label{eq:normy:norma_inf} \|x\|_\infty = \max_{1 \leq i \leq m} |x_i| . \end{equation}
Interaktivní ukázka · Jednotková koule \(\infty\)-normy

Jednotková koule \(\infty\)-normy je čtverec se středem v počátku, protínající obě osy v jednotkové vzdálenosti. Táhněte bodem \(x\) a sledujte, která ze složek je právě ta největší: zvýrazní se tučnou úsečkou, protože jen ona rozhoduje o hodnotě normy. Zaškrtnutím porovnání se do obrázku dokreslí koule 1-normy — je do čtverce vepsaná, což je právě obsah nerovnosti \(\|x\|_\infty \leq \|x\|_1\).

Pro \(p = 2\) je

\begin{equation}\label{eq:normy:norma_2} \|x\|_2 = \left( \sum_{i=1}^{m} |x_i|^2 \right)^{1/2} . \end{equation}
Interaktivní ukázka · Jednotková koule 2-normy

Jednotková koule 2-normy je kruh se středem v počátku, protínající obě osy v jednotkové vzdálenosti. Kruh je vykreslen izotropně (i na úzkém displeji zůstane kruhem), takže je vidět, že jde o jedinou \(p\)-normu, jejíž koule se nezmění při otočení. Táhněte bodem \(x\) a čtěte pod plátnem řetězec \(\|x\|_\infty \leq \|x\|_2 \leq \|x\|_1 \leq \sqrt{2}\,\|x\|_2\) — platí pro každou polohu bodu a odpovídá vnoření nakreslených koulí.

Pro obecné \(p\) pak

\begin{equation}\label{eq:normy:norma_p} \|x\|_p = \left( \sum_{i=1}^{m} |x_i|^p \right)^{1/p} . \end{equation}
Interaktivní ukázka · Koule obecné \(p\)-normy

Jednotková koule obecné \(p\)-normy je pro \(1 < p < \infty\) zaoblený čtverec „mezi kruhem a čtvercem“ se středem v počátku. Posuvníkem \(p\) si tvary projděte plynule: od kosočtverce (\(p = 1\)) přes kruh (\(p = 2\)) až ke čtverci (\(p = \infty\)). Body \(x\) a \(y\) jsou tažitelné a počítají se u nich obě strany trojúhelníkové nerovnosti \(\|x + y\|_p \leq \|x\|_p + \|y\|_p\). Stáhněte \(p\) pod jedničku a uvidíte, proč se \(p\)-normy uvažují až od \(p \geq 1\) — nerovnost přestane platit a koule přestane být konvexní.

Používají se případně i vážené \(p\)-normy

\begin{equation}\label{eq:normy:norma_vazena} \|x\|_{w,p} = \|Wx\|_p = \left( \sum_{i=1}^{m} |w_i x_i|^p \right)^{1/p} , \end{equation}

kde \(W\) je diagonální matice.

Interaktivní ukázka · Jednotková koule vážené normy

Koule vážené normy je elipsa se středem v počátku; svislý směr určuje váha \(w_2\), vodorovný \(w_1\). Posuvníky \(w_1\) a \(w_2\) mění diagonální matici \(W\): koule protíná osy v bodech \(\pm 1/w_1\) a \(\pm 1/w_2\), takže menší váha znamená delší poloosu — pro \(w_1 < w_2\) dostanete vodorovně protáhlou elipsu. Čárkovaně je pro srovnání nevážená koule. Přepínačem \(p\) si ověřte, že totéž přeškálování os funguje i pro kosočtverec a čtverec.

Lze uvažovat i obecnější, libovolnou nesingulární matici \(W\), kdy je však nutno definici upravit.

Maticová norma indukovaná vektorovými normami

Uvažujme matici \(A \in \mathbb{C}^{m \times n}\) jako zobrazení z vektorového prostoru s normou \(\|\cdot\|_{(n)}\) do prostoru s normou \(\|\cdot\|_{(m)}\); obvykle jde o stejnou normu, jen v různě dimenzionálních prostorech.

Definice (Indukovaná maticová norma)

Indukovaná maticová norma \(\|A\|_{(m,n)}\) je nejmenší \(C \in \mathbb{R}\) takové, že platí

\[ \|Ax\|_{(m)} \leq C \,\|x\|_{(n)} , \]

neboli

\begin{equation}\label{eq:normy:indukovana} \|A\|_{(m,n)} = \sup_{\substack{x \in \mathbb{C}^n \\ x \neq 0}} \frac{\|Ax\|_{(m)}}{\|x\|_{(n)}} = \sup_{\substack{x \in \mathbb{C}^n \\ \|x\|_{(n)} = 1}} \|Ax\|_{(m)} . \end{equation}

Indukovaná norma tedy vyjadřuje, jak moc se při působení matice \(A\) „prodlouží“ jednotkové vektory — přičemž se obecně změní i jejich směr, ba i počet složek.

Příklad

Příklad

Určeme normy matice

\[ A = \begin{pmatrix} 1 & 2 \\ 0 & 2 \end{pmatrix} . \]

Pro 1-normu dostaneme \(\|A\|_1 = 4\).

Interaktivní ukázka · Obraz koule 1-normy při zobrazení \(A\)

Vlevo jednotková koule 1-normy — kosočtverec s vrcholy \((0,1)\) a \((1,0)\) a vyznačeným vektorem uvnitř; šipka s popiskem \(A\) vede vpravo k jeho obrazu, kosodélníku s vrcholy \((2,2)\) a \((-2,-2)\), s bodem \((1,0)\) na vodorovné ose a čárkovanou úhlopříčkou. Táhněte bodem po levém kosočtverci a vpravo sledujte \(Ax\) i čtenou hodnotu \(\|Ax\|_1\). Tučný vektor je maximalizující směr — vždy některé \(e_j\), takže jeho obrazem je \(j\)-tý sloupec matice, a proto je \(\|A\|_1\) největší sloupcový součet. Posuvníky přepište prvky \(A\) a porovnejte hodnotu ze vzorce s maximem \(\|Ax\|_1\) spočteným numericky po celé hranici koule.

Pro 2-normu je

\[ \|A\|_2 = \sqrt{\frac{9+\sqrt{65}}{2}} \approx 2{,}9208 , \]

a to pro bod

\[ \left( \sqrt{\frac{1}{2} - \frac{7}{2\sqrt{65}}},\ \sqrt{\frac{1}{2} + \frac{7}{2\sqrt{65}}} \right) . \]
Interaktivní ukázka · Obraz koule 2-normy při zobrazení \(A\)

Vlevo jednotková kružnice 2-normy s popisky \((0,1)\) a \((1,0)\) a čárkovaným poloměrem; šipka s popiskem \(A\) vede vpravo k obrazu, elipse protažené v šikmém směru, s vyznačeným krajním bodem vpravo nahoře a čárkovanou hlavní poloosou. Maximalizující směr se počítá jako vlastní vektor matice \(A^\dagger A\) k největšímu vlastnímu číslu; pro matici z příkladu vyjde \(\|A\|_2 = 2{,}9208\) a bod \((0{,}2567;\ 0{,}9665)\) — tedy přesně hodnoty uvedené výše. Táhněte bodem po kružnici a sledujte, jak se \(\|Ax\|_2\) mění a maxima dosahuje právě na hlavní poloose. Snížením \(a_{22}\) k nule matici přiblížíte singulární — elipsa zkolabuje do úsečky a \(\sigma_{\min}\) jde k nule.

Pro \(\infty\)-normu je \(\|A\|_\infty = 3\).

Interaktivní ukázka · Obraz koule \(\infty\)-normy při zobrazení \(A\)

Vlevo jednotková koule \(\infty\)-normy — čtverec s popisky \((0,1)\) a \((1,0)\) a čárkovanou úhlopříčkou; šipka s popiskem \(A\) vede vpravo k obrazu, kosodélníku s vrcholy \((3,2)\) a \((-3,-2)\), s osami popsanými hodnotami \(-3\), \(1\), \(3\) vodorovně a \(2\), \(-2\) svisle a s čárkovanou úhlopříčkou. Maximum se nabývá ve vrcholu čtverce, tedy ve vektoru se složkami \(\pm 1\) podle znamének „nejtěžšího“ řádku — proto je \(\|A\|_\infty\) největší řádkový součet. Táhněte bodem po obvodu čtverce a sledujte, jak \(\|Ax\|_\infty\) roste k maximu právě ve vrcholech.

Obecné vztahy pro maticové normy

Obecně platí následující tvrzení.

1) 1-norma. Hodnota \(\|A\|_1\) je maximum ze součtů absolutních hodnot prvků ve sloupcích, tedy

\begin{equation}\label{eq:normy:norma_matice_1} \|A\|_1 = \max_{1 \leq j \leq n} \|a_j\|_1 , \end{equation}

kde \(a_j\) je \(j\)-tý sloupec matice \(A\). Platí totiž

\begin{equation}\label{eq:normy:odhad_sloupce} \|Ax\|_1 = \Big\| \sum_{j=1}^{n} x_j a_j \Big\|_1 \leq \sum_{j=1}^{n} |x_j| \,\|a_j\|_1 \leq \|x\|_1 \cdot \max_{1 \leq j \leq n} \|a_j\|_1 , \end{equation}

a volbou \(x = e_j\) pro to \(j\), pro něž je \(\|a_j\|_1\) maximální, dostaneme rovnost, a tedy

\[ \|A\|_1 = \sup_{\|x\|_1 = 1} \|Ax\|_1 = \max_{1 \leq j \leq n} \|a_j\|_1 . \]

2) \(\infty\)-norma. Podobně lze ukázat, že \(\|A\|_\infty\) je maximum ze součtů absolutních hodnot prvků v řádcích, tedy

\begin{equation}\label{eq:normy:norma_matice_inf} \|A\|_\infty = \max_{1 \leq i \leq m} \|a_i^*\|_1 , \end{equation}

kde \(a_i^*\) je \(i\)-tý řádek matice \(A\).

3) 2-norma. Hodnotu \(\|A\|_2\) lze určit z maximálního tzv. singulárního čísla, tj. jako \(\max\{\sigma_i\}_{i=1}^{m}\), kde singulární čísla se určují pomocí tzv. SVD rozkladu (viz později).

4) Norma součinu. Pro odhad normy součinu dvou matic platí

\begin{equation}\label{eq:normy:submultiplikativita} \|AB\|_{(\ell,n)} \leq \|A\|_{(\ell,m)} \cdot \|B\|_{(m,n)} , \end{equation}

a speciálně

\begin{equation}\label{eq:normy:mocnina} \|A^n\| \leq \|A\|^n , \end{equation}

kde obecně nejde o rovnost.