Numerika pro teoretické fyziky ← →

Kapitola 10

Numerická lineární algebra. Úvod. LU rozklad

Numerická lineární algebra

Mnoho úloh ve fyzice (zvláště pokud je systém popsán parciálními diferenciálními rovnicemi) vede nakonec k numerickému řešení jedné ze tří základních úloh lineární algebry:

  1. řešení soustavy lineárních rovnic \(Ax = b\);
  2. problém hledání vlastních čísel a vektorů \begin{equation}\label{eq:09:vlastni_cisla} Ax = \lambda x , \quad \text{neboli hledáme rozklad } A = V \Lambda V^{-1} ; \end{equation}
  3. řešení přeurčené soustavy \(Ax = b\) vedoucí na metodu nejmenších čtverců.

Při řešení těchto úloh se s výhodou používají různé faktorizace (rozklady, dekompozice) příslušné matice \(A\) na součin dvou až tří speciálních matic, pomocí kterých už pak může být určitá úloha snadno (a rychle) řešitelná.

Základní rozklady

Základní rozklady, kterými se budeme podrobněji zabývat, jsou následující tři.

a) LU rozklad (dekompozice), používaný k řešení úlohy 1):

\begin{equation}\label{eq:09:lu} A = L \cdot U , \end{equation}

kde \(L\) je dolní trojúhelníková a \(U\) je horní trojúhelníková matice.

Interaktivní ukázka · Schéma LU rozkladu

Schéma tvarů matic: plný šrafovaný čtverec \(A\) je roven dolnímu trojúhelníku \(L\) krát hornímu trojúhelníku \(U\), bloky jsou přitom naplněné konkrétními čísly. Provádí se Gaussova eliminace náhodné celočíselné matice a posuvník „krok k“ vás jí provede sloupec po sloupci. Kroužek značí přesnou nulu, sytost políčka velikost prvku, teplá barva zápornou hodnotu. Po každém kroku platí \(L\cdot U = P\cdot A\) — reziduum je vypsáno pod plátnem. Vypněte pivotizaci a sledujte, jak multiplikátory \(\ell_{jk}\) i růstový faktor vyletí nahoru.

b) QR rozklad, používaný pro úlohy 2) a 3), ale lze jej použít i pro 1), jen je dvakrát pomalejší než LU rozklad:

\begin{equation}\label{eq:09:qr} A = Q \cdot R , \end{equation}

kde \(Q\) je ortogonální (obecně \(m \times n\)) matice a \(R\) je horní trojúhelníková matice.

Interaktivní ukázka · Schéma QR rozkladu

Šrafovaný obdélník \(A\) je roven vyššímu úzkému obdélníku \(Q\) krát malému čtverci s vyšrafovanou horní trojúhelníkovou částí \(R\). Poměry stran bloků se řídí posuvníky \(m\) a \(n\), obsah počítá Gram–Schmidtova ortogonalizace. Zapněte „téměř závislé sloupce“ a přepněte na klasický G–S: ortogonalita \(Q\) se rozpadne o sedm řádů, zatímco modifikovaná varianta si ji udrží — součin \(Q\cdot R\) přitom zůstává rovný \(A\) v obou případech.

c) SVD — singulární rozklad matice (singular value decomposition):

\begin{equation}\label{eq:09:svd} A = U \cdot \Sigma \cdot V^t , \end{equation}

kde \(\Sigma\) je diagonální matice obsahující tzv. singulární hodnoty a \(U\) a \(V\) jsou ortogonální (unitární) matice. Tento rozklad lze použít téměř na cokoli, jen je pro praktické výpočty mnohem pomalejší než předchozí rozklady, ovšem je nejstabilnější.

Interaktivní ukázka · Schéma SVD

Úzký šrafovaný obdélník \(A\) je roven širšímu obdélníku \(U\) krát obdélníku \(\Sigma\) s vyznačenou diagonálou a nulami-kroužky mimo ni krát malému šrafovanému čtverci \(V^t\). Rozklad počítá jednostranná Jacobiho metoda. Posuvníkem „hodnost \(k\)“ škrtáte nejmenší singulární hodnoty a porovnává se chyba nejlepší aproximace hodnosti \(k\) s hodnotou \(\sqrt{\sigma_{k+1}^2 + \dots}\), kterou předpovídá Eckartova–Youngova věta.

Rychlost a stabilita

V praktických problémech rozhoduje především rychlost (efektivita) určité metody řešení a dále stabilita a přesnost; správnost řešení jde většinou ruku v ruce se stabilitou.

Bohužel velmi často jsou stabilnější metody méně efektivní a je nutný určitý kompromis založený na zkušenosti z praxe. Například pro řešení \(Ax = b\) je pořadí efektivity

\begin{equation}\label{eq:09:poradi_efektivity} LU < QR < SVD , \end{equation}

ale pokud jde o stabilitu, je to naopak. V praxi se ale ukazuje, že pro většinu systémů \(Ax = b\) vzešlých např. z diskretizace PDR je z hlediska přesnosti bezpečné použít LU rozklad.

Doporučení pro praxi

Přestože si ukážeme, jak některé metody fungují a jak je lze využít k řešení problémů 1), 2) a 3), v praxi velmi doporučuji použít některou z dostupných knihoven, případně programy jako Mathematica nebo Matlab, kde jsou všechny výše uvedené metody a problémy vyladěné jak z hlediska efektivity, tak z hlediska přesnosti (viz pár odkazů na mé webové stránce).

Gaussova eliminace a LU dekompozice (rozklad)

Gaussova eliminace převádí systém \(Ax = b\), kde \(A \in \mathbb{C}^{m \times m}\), na systém \(Ux = \bar{b}\), kde \(U\) je horní \(\Delta\) matice a \(\bar{b}\) je modifikované \(b\), pomocí operací eliminujících prvky pod diagonálou.

Postupné řádkové eliminace v jednom sloupci jsou ovšem ekvivalentní násobení matice \(A\) dolní \(\Delta\) maticí:

\begin{equation}\label{eq:09:a1_eq_l1a} A^{(1)} = L_1 A , \end{equation}

neboli

\[ \underset{\textstyle A = A^{(0)}}{\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1m}\\ a_{21} & a_{22} & & \vdots\\ \vdots & & \ddots & \vdots\\ a_{m1} & \cdots & \cdots & a_{mm} \end{pmatrix}} \;\overset{\textstyle L_1}{\longrightarrow}\; \underset{\textstyle A^{(1)}}{\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1m}\\ 0 & \widetilde{a}_{22} & \cdots & \widetilde{a}_{2m}\\ \vdots & \vdots & & \vdots\\ 0 & \widetilde{a}_{m2} & \cdots & \widetilde{a}_{mm} \end{pmatrix}} ,\ \text{kde } L_1 = \begin{pmatrix} 1 & 0 & \cdots & 0\\ -\ell_{21} & 1 & \ddots & \vdots\\ \vdots & 0 & \ddots & \\ \vdots & \vdots & \ddots & 0\\ -\ell_{m1} & 0 & \cdots 0 & 1 \end{pmatrix} \]

a

\begin{equation}\label{eq:09:multiplikatory_prvni} \ell_{j1} = a_{j1}/a_{11},\ j > 1 . \end{equation}

Obdobně pro eliminaci \(k\)-tého sloupce použijeme

\begin{equation}\label{eq:09:lk} L_k = \begin{pmatrix} 1 & 0 & \cdots 0 & \cdots & \cdots & 0\\ 0 & \ddots & & & & \vdots\\ & \ddots & 0 & & & \\ \vdots & & 0 & 1 & \ddots & \\ & & & -\ell_{k+1,k} & \ddots & 0\\ 0 & \cdots 0 & \cdots & -\ell_{mk} & 0 & 1 \end{pmatrix} \qquad \text{kde } \ell_{jk} = \frac{a_{jk}^{(k-1)}}{a_{kk}^{(k-1)}} \quad \text{pro } j > k , \end{equation}

přičemž sloupec obsahující jedničku a prvky \(-\ell_{k+1,k}, \dots, -\ell_{mk}\) je \(k\)-tý sloupec a \(a_{jk}^{(k-1)}\) jsou prvky matice \(A^{(k-1)} = L_{k-1} \cdots L_1 A\).

Dostáváme nakonec \(L_{m-1} L_{m-2} \cdots L_1 A = U\), neboli

\begin{equation}\label{eq:09:a_eq_lu} A = (L_{m-1} \cdots L_1)^{-1} U = L_1^{-1} \cdots L_{m-1}^{-1} U = LU , \end{equation}

kde \(U\) je horní \(\Delta\) matice a \(L\) je dolní \(\Delta\) matice, neboť

\[ L_k^{-1} = \begin{pmatrix} 1 & 0 & \cdots 0 & \cdots & \cdots & 0\\ 0 & \ddots & & & & \vdots\\ & & 1 & 0 & & \vdots\\ \vdots & & 0 & 1 & \ddots & \\ & & & \ell_{k+1,k} & \ddots & 0\\ 0 & \cdots & 0 & \ell_{mk} & 0 & 1 \end{pmatrix} \quad \text{a navíc} \quad L_1^{-1} L_2^{-1} = \begin{pmatrix} 1 & & & \\ \ell_{21} & 1 & & 0\\ \vdots & \ell_{32} & 1 & \\ & & \ddots & \\ \ell_{m1} & \ell_{m2} & 0 & 1 \end{pmatrix} \quad \text{atd.} \]

Jde tedy pouze o změnu znamének v \(\ell_{jk}\).

Poznámka

Matici \(L_k\) lze zapsat pomocí „vnějšího součinu“

\begin{equation}\label{eq:09:lk_vnejsi_soucin} L_k = I - \ell_k e_k^T , \end{equation}

kde

\[ \ell_k e_k^T = \begin{pmatrix} 0\\ \vdots\\ 0\\ \ell_{k+1,k}\\ \vdots\\ \ell_{m,k} \end{pmatrix} (0 \ldots 0\ 1\ 0 \ldots 0) \]

a jednička v řádkovém vektoru je na \(k\)-tém místě. Protože skalární součin \(e_k^T \ell_k = 0\), bude

\[ (I - \ell_k e_k^T)(I + \ell_k e_k^T) = I , \]

a tedy \(L_k^{-1} = I + \ell_k e_k^T\). Dále platí

\[ L_k^{-1} L_{k+1}^{-1} = (I + \ell_k e_k^T)(I + \ell_{k+1} e_{k+1}^T) = I + \ell_k e_k^T + \ell_{k+1} e_{k+1}^T \]

atd.

Poznámka

Protože má \(L\) na diagonále jedničky, lze \(L\) a \(U\) uložit do jediné matice; většinou se nahrazuje přímo matice \(A\) jejím LU rozkladem.

Poznámka

Takto přímočaře nelze postup použít, neboť je nestabilní; nutná je tzv. pivotizace.

Příklad (Nestabilita Gaussovy eliminace bez pivotizace)

Řešme \(Ax = b\) pro

\[ A = \begin{pmatrix} 10^{-20} & 1 \\ 1 & 1 \end{pmatrix} , \qquad b = \begin{pmatrix} 1 \\ 0 \end{pmatrix} . \]

Přímo:

\[ \begin{aligned} 10^{-20} x_1 + x_2 &= 1 \; , \\ x_1 + x_2 &= 0 \end{aligned} \qquad \Rightarrow \qquad x_1 = \frac{1}{10^{-20} - 1} \doteq -1 \; , \quad x_2 = -x_1 \doteq 1 . \]

LU dekompozice dává

\[ L = \begin{pmatrix} 1 & 0 \\ 10^{20} & 1 \end{pmatrix} , \qquad U = \begin{pmatrix} 10^{-20} & 1 \\ 0 & 1-10^{20} \end{pmatrix} \quad \Rightarrow \quad L \cdot U = A = \begin{pmatrix} 10^{-20} & 1 \\ 1 & 1 \end{pmatrix} . \]

Ovšem v double precision:

\[ \tilde{L} = \begin{pmatrix} 1 & 0 \\ 10^{20} & 1 \end{pmatrix} \qquad \tilde{U} = \begin{pmatrix} 10^{-20} & 1 \\ 0 & -10^{20} \end{pmatrix} \quad \Rightarrow \quad \tilde{L}\tilde{U} = \begin{pmatrix} 10^{-20} & 1 \\ 1 & 0 \end{pmatrix} \neq A . \]

Pro některé pravé strany (např. \(b = \begin{pmatrix} 1 \\ 1 \end{pmatrix}\)) to stále dá správné řešení, ale ne vždy! Právě pro \(b = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\) dostaneme

\begin{align*} &\tilde{L}^{-1} = \begin{pmatrix} 1 & 0 \\ -10^{20} & 1 \end{pmatrix} \qquad \tilde{U}^{-1} = \begin{pmatrix} 10^{20} & 1 \\ 0 & -10^{-20} \end{pmatrix} \quad \Rightarrow \\[2pt] &\qquad \Rightarrow \quad \tilde{x} = \tilde{U}^{-1}\tilde{L}^{-1} b = \tilde{U}^{-1} \begin{pmatrix} 1 \\ -10^{20} \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \neq \begin{pmatrix} -1 \\ 1 \end{pmatrix} , \end{align*}

neboť Gaussova eliminace dělá něco jiného než dosazení za \(x_2 = -x_1\):

\[ \begin{array}{r|l} - \cdot 10^{20} & 10^{-20} x_1 + x_2 = 1 \\ & x_1 + x_2 = 0 \\ \hline & 10^{-20} x_1 + x_2 = 1 \\ & (1-10^{20}) x_2 = -10^{20} \quad \Rightarrow \end{array} \]

Po zaokrouhlení odtud plyne

\[ -10^{20} x_2 = -10^{20} \quad \Rightarrow \quad x_2 = 1 \quad ! \]

a tedy \(10^{-20} x_1 + 1 = 1 \quad \Rightarrow \qquad x_1 = 0 \quad !\)

Ovšem s pivotizací bude

\[ \begin{array}{r|l} \cdot \, 10^{-20} & x_1 + x_2 = 0 \\ & 10^{-20} x_1 + x_2 = 1 \\ \hline & x_1 + x_2 = 0 \\ & 0 \; + (1-10^{-20}) x_2 = 1 \quad \Rightarrow \end{array} \]

a po zaokrouhlení

\[ 1 x_2 = 1 \quad \Rightarrow \quad x_2 = 1 , \]

a tedy nyní \(x_1 = -x_2 = -1\).

Pivotizace

Pivotizace je výběr největšího prvku, kterým dělíme. Nejen tehdy, pokud se na diagonále objeví nula, ale i tehdy, když je tam velmi malé číslo relativně k ostatním, je nutné kvůli stabilitě přehodit řádky (a případně i sloupce) a pak pokračovat v Gaussově eliminaci.

Rozlišujeme dvě varianty:

Plná pivotizace ovšem potřebuje \(O(m^3)\) operací porovnání oproti \(O(m^2)\) operacím v řádkové pivotizaci, a proto se používá pivotizace řádková.

Poznámka

Zde \(O(m^3)\) je celkový počet operací v průběhu celé Gaussovy eliminace.

Řádková pivotizace a LU rozklad

Prohazování řádků lze provést pomocí permutačních matic, např. matice

\[ P = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} \]

přehodí 2. a 4. řádek matice \(4 \times 4\).

Lze tedy psát

\begin{equation}\label{eq:09:eliminace_s_permutacemi} L_{m-1} P_{m-1} L_{m-2} P_{m-2} \dots L_1 P_1 A = U \end{equation}

s příslušnými permutačními maticemi \(P_k\) pro řádkovou pivotizaci v \(k\)-tém kroku. Toto lze ovšem přepsat pomocí

\begin{equation}\label{eq:09:lk_carka} L_k' = P_{m-1} \dots P_{k+1} L_k P_{k+1}^{-1} \dots P_{m-1}^{-1} \quad , \quad L_{m-1}' = L_{m-1} \end{equation}

jako

\begin{equation}\label{eq:09:pa_eq_lu_odvozeni} \underbrace{\left( L_{m-1}' L_{m-2}' \dots L_1' \right)}_{L^{-1}} \underbrace{\left( P_{m-1} P_{m-2} \dots P_1 \right)}_{P} A = U , \end{equation}

neboli \(PA = LU\). Kromě matic \(L\) a \(U\) je tedy nutné ještě uložit celkovou permutační matici \(P\) (lze ji uložit jako vektor).

Matice \(L_k'\) má oproti \(L_k\) pouze přeuspořádané prvky \(\ell_{jk}\), neboť \(P_k^{-1} = P_k\) a \(P_k\) násobící \(A\) zprava přehazuje místo řádků příslušné sloupce; matici \(L_k\) přitom násobíme pouze maticemi \(P_j\) pro \(j > k\), takže se přehodí sloupce jednotkové podmatice a pak to přehození řádků vrátí.

Poznámka

Obdobně lze přepsat i úplnou pivotizaci, a to jako \(PAQ = LU\), kde \(P\) i \(Q\) jsou permutační matice. V praxi se však kvůli efektivitě nepoužívá.

Algoritmus LU rozkladu s řádkovou pivotizací

\[ \begin{aligned} &U = A \, , \, L = I, \, P = I && (\text{inicializace}) \\ &\text{pro } k = 1, m-1 && (\text{eliminujeme } m-1 \text{ sloupců}) \\ &\quad \text{najdi } i \ge k \text{, pro které je } |U_{ik}| \text{ maximální} && (\text{pivotizace}) \\ &\quad U_{k,k:m} \longleftrightarrow U_{i,k:m} \\ &\quad \ell_{k,1:k-1} \longleftrightarrow \ell_{i,1:k-1} \\ &\quad P_{k,:} \longleftrightarrow P_{i,:} \\ &\quad \text{pro } j = k+1, m \\ &\qquad \ell_{jk} = U_{jk} / U_{kk} \\ &\qquad U_{j,k:m} = U_{j,k:m} - \ell_{jk} U_{k,k:m} \end{aligned} \]

Tři řádky s prohozením představují přehození řádků, pokud \(i \ne k\). Poslední dva řádky jsou odečtení dvou řádků, tedy časově nejnáročnější část algoritmu.

Počet operací

Operace \(+, -, *, /\) uvažujeme na stejné úrovni. Když eliminujeme jeden (\(k\)-tý) sloupec, musíme upravit podmatici \((m-k) \times (m-k)\), a sloupců je \(m-1\); obrazově tedy dostáváme situaci v interaktivní ukázce.

Interaktivní ukázka · Pyramida operací

Stupňovitá „pyramida“ složená z vrstev postupně se zmenšujících čtvercových podmatic, s hranami řádu \(m\). Posuvníkem \(m\) měníte rozměr matice, posuvníkem „vrstva \(k\)“ zvýrazníte podmatici \((m-k)\times(m-k)\), kterou upravuje \(k\)-tý krok eliminace, a dopočítá se její příspěvek \((m-k)\,[2(m-k)+1]\) operací. Součet objemů vrstev \(\sum (m-k)^2\) porovnává s \(m^3/3\) a přesný počet operací s asymptotou \(\tfrac{2}{3}m^3\). Přepínač „poměr k 2/3 m³“ pak vykreslí přímo podíl z limity na konci tohoto odstavce — křivka opravdu míří k jedničce.

Objem této pyramidy je \(\sim \frac{1}{3} m^3\), ovšem vždy musíme dělat dvě operace (\(-\), \(*\)), viz poslední řádek algoritmu. Takže celkem je potřeba

\begin{equation}\label{eq:09:pocet_operaci_lu} \sim \tfrac{2}{3} m^3 \end{equation}

operací (tzv. flops, tedy floating point operations). Řádková pivotizace je \(\sim m^2\).

Zápis \(\sim \frac{2}{3} m^3\) znamená, že

\[ \lim\limits_{m \to \infty} \frac{\text{počet operací}}{\frac{2}{3} m^3} = 1 . \]

Řešení soustavy \(Ax = b\) pomocí LU rozkladu

Jakmile máme rozklad \(PA = LU\), můžeme řešit ekvivalentní soustavu \(PAx = Pb\) (tj. přeuspořádáme pravou stranu) a řešíme \(Ly = Pb\) a pak \(Ux = y\) přímo, neboť jde o trojúhelníkové matice (tzv. zpětná substituce).

Obě rovnice mají náročnost \(\sim m^2\), proto se vyplatí udělat LU rozklad zvláště tehdy, pokud se matice \(A\) nemění, ale máme různé pravé strany.

Choleského rozklad

Jde o obdobu LU rozkladu, ale pro hermitovské, pozitivně definitní matice \(A\), tj. \(A = A^\dagger\) a \(x^\dagger A x > 0\) pro libovolné \(x \neq 0\). Z pozitivní definitnosti např. plyne, že všechna vlastní čísla jsou kladná, a též že jsou kladné diagonální prvky.

Díky hermitovosti můžeme při Gaussově eliminaci nejen nulovat první sloupec násobením dolní \(\Delta\) maticí zleva, ale také první řádek násobením hermitovsky sdruženou maticí zprava. Matici \(A\) lze tedy (pro \(a_{11} > 0\)) rozložit takto:

\begin{equation}\label{eq:09:cholesky_krok} A = \begin{pmatrix} a_{11} & w^\dagger \\ w & K \end{pmatrix} = \begin{pmatrix} \alpha & 0 \\ \frac{w}{\alpha} & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & K - \frac{ww^\dagger}{\alpha^2} \end{pmatrix} \begin{pmatrix} \alpha & w^\dagger/\alpha \\ 0 & 1 \end{pmatrix} = R_1^\dagger A_1 R_1, \quad \text{kde } \alpha = \sqrt{a_{11}} , \end{equation}

přičemž \(K - \frac{ww^\dagger}{\alpha^2}\) je opět pozitivně definitní hermitovská matice.

Matice \(A_1 = (R_1^\dagger)^{-1} A R_1^{-1}\) je též pozitivně definitní hermitovská matice. Navíc platí, že libovolná podmatice obsahující levý horní nebo pravý dolní roh takovéto matice je též hermitovská a pozitivně definitní: násobením \(X^\dagger A_1 X\), kde

\[ X = \begin{pmatrix} 0 \\ \mathbf{1}_{n \times n} \end{pmatrix} , \]

takovou podmatici vybereme.

Takto můžeme pokračovat dále rozklady podmatic, až zůstane uprostřed jednotková matice, tj. máme

\begin{equation}\label{eq:09:cholesky} A = R_1^\dagger R_2^\dagger \cdots R_m^\dagger R_m \cdots R_2 R_1 = R^\dagger R, \quad \text{kde } r_{jj} > 0 \end{equation}

a \(R\) je horní \(\Delta\) matice. Tento rozklad je jednoznačný.

Díky hermitovosti matice \(A\) stačí uložit jen její horní trojúhelníkovou část a upravovat ji na \(R\):

\[ \begin{aligned} &R = A \\ &\text{pro } k = 1, m \\ &\quad \text{pro } j = k+1, m \\ &\qquad R_{j,j:m} = R_{j,j:m} - R_{k,j:m}\, R^*_{kj}/R_{kk} \\ &\quad R_{k,k:m} = R_{k,k:m}/\sqrt{R_{kk}} \end{aligned} \]

Výraz \(R^*_{kj}/R_{kk}\) se vyplatí uložit do pomocné proměnné, pak jsou potřeba jen dvě operace; nyní je ovšem „objem“ pouze \(\frac{1}{6}m^3\), takže celkem je potřeba \(\sim \frac{1}{3}m^3\) operací.

Stabilita Gaussovy eliminace a LU rozkladu

Bez pivotizace lze ukázat, že spočtené \(\tilde L\) a \(\tilde U\) splňují

\begin{equation}\label{eq:09:stabilita_bez_pivotizace} \tilde L \tilde U = A + \delta A, \quad \text{kde ovšem } \frac{\|\delta A\|}{\|L\|\,\|U\|} = \mathcal{O}(\varepsilon_M), \end{equation}

pro určité \(\delta A\). Ve jmenovateli tedy není \(\|A\|\), ale záleží na velikosti \(L\) a \(U\). Pokud \(\|A\| \ll \|L\|\) nebo \(\|A\| \ll \|U\|\), pak může být \(\|\delta A\|\) poměrně velké a spočtené \(\tilde L \tilde U\) se může dost lišit od původní matice \(A\).

Říkáme, že LU rozklad není zpětně stabilní; důsledkem je, že řešení \(\tilde L \tilde U x = b\) pak může být velmi nepřesné.

Pro LU rozklad s pivotizací lze ukázat, že je zpětně stabilní, tj.

\begin{equation}\label{eq:09:stabilita_s_pivotizaci} \tilde L \tilde U = \tilde P A + \delta A, \quad \text{kde } \frac{\|\delta A\|}{\|A\|} = \mathcal{O}(\rho\,\varepsilon_M) , \end{equation}

přičemž kvůli zaokrouhlovacím chybám nemusí jít u \(\tilde P\) nutně o matici \(P\).

Nyní již \(\|\delta A\|\) porovnáváme s \(\|A\|\), ale objevuje se tzv. růstový faktor (growth factor)

\begin{equation}\label{eq:09:rustovy_faktor} \rho = \frac{\max_{i,j} |u_{ij}|}{\max_{i,j} |a_{ij}|} , \end{equation}

který může být ve výjimečných případech až \(2^m\) (viz ukázka v Mathematice), ale v praxi se s tímto případem s velkou pravděpodobností nesetkáte; u náhodně generovaných matic je spíše řádu \(\sqrt{m}\).

Poznámka

Algoritmus \(\tilde f\) je pro problém \(f = f(x)\) zpětně stabilní, pokud pro \(\forall x\) platí \(\tilde f(x) = f(\tilde x)\) pro určité \(\tilde x\) splňující

\[ \frac{\|\tilde x - x\|}{\|x\|} = \mathcal{O}(\varepsilon_M) , \]

neboli „Zpětně stabilní algoritmus dá správnou odpověď na skoro správnou otázku.“

Navíc pro přesnost zpětně stabilního algoritmu platí (viz např. Trefethen, Bau III: Numerical linear algebra)

\begin{equation}\label{eq:09:presnost_zpetne_stabilniho} \frac{\|\tilde f(x) - f(x)\|}{\|f(x)\|} = \mathcal{O}(\varkappa(x)\,\varepsilon_M) , \end{equation}

kde \(\varkappa(x)\) je číslo podmíněnosti, pro matice \(\varkappa(A) = \|A\|\,\|A^{-1}\|\).

Poznámka

Následující dva obrázky jsou převzaty ze strany 168 uvedené knihy (část IV, Systems of Equations); jejich popisky jsou ponechány v původním anglickém znění.

Interaktivní ukázka · Růstový faktor a rozměr matice

Růstové faktory Gaussovy eliminace s částečnou pivotizací pro náhodné matice — obdoba grafu Figure 22.1. Growth factors for Gaussian elimination with partial pivoting applied to 496 random matrices (independent, normally distributed entries) of various dimensions. The typical size of \(\rho\) is of order \(m^{1/2}\), much less than the maximal possible value \(2^{m-1}\). Data se generují znovu: každý bod je jedna náhodná matice s nezávislými normálně rozdělenými prvky, pro kterou se spočítá LU rozklad a z něj \(\rho = \max|u_{ij}|/\max|a_{ij}|\). Osy jsou logaritmické a čárkovaná přímka je \(m^{1/2}\). Tlačítkem přidávejte další matice; přepnutím na „bez pivotizace“ uvidíte, o kolik řádů mrak vyskočí, a volba „Wilkinson“ nahradí náhodné matice patologickou maticí, u níž \(\rho\) přesně dosahuje maxima \(2^{m-1}\).

Interaktivní ukázka · Hustota pravděpodobnosti růstového faktoru

Hustota rozdělení růstových faktorů v semilogaritmickém měřítku — obdoba grafu Figure 22.2. Probability density distributions for growth factors of random matrices of dimensions \(m = 8\), 16, 32, based on sample sizes of one million for each dimension. The density appears to decrease exponentially with \(\rho\). The chatter near the end of each curve is an artifact of the finite sample sizes. Milion vzorků na rozměr v prohlížeči nedáme, ale princip ano: generují se náhodné matice, počítá se jejich LU rozklad s částečnou pivotizací a z nasbíraných hodnot \(\rho\) staví histogram hustoty. Tlačítkem „+ 500 vzorků“ statistiku zpřesňujete a rozkmitané konce křivek se posouvají doprava — je to přesně ten „chatter“ z popisku, tedy artefakt konečného počtu vzorků. Ostrý náběh, exponenciální pokles i posun křivek s rostoucím \(m\) odpovídají citovanému grafu.