Gramova–Schmidtova ortogonalizace: Porovnání verzí
Smazaný obsah Přidaný obsah
literatura golub van loan |
pridani prikladu s lauchliho matici |
||
Řádek 58:
Tato varianta algoritmu se nazývá '''klasický Gramův-Schmidtův algoritmus (CGS)''' a je novější než varianta původní, dnes zvaná '''modifikovaný Gramův-Schmidtův algoritmus (MGS)'''. MGS získáme z výše popsaného CGS prostým vypuštěním řádků 07 a 08, tedy, spojením obou vnitřních cyklů.
Oba algoritmy CGS i MGS jsou matematicky ekvivalentní, jejich reálné implementace mají výrazně odlišné chování.
Řádek 74:
Řešením v praxi používaným bývá tzv. '''klasický Gramův-Schmidtův algoritmus s iteračním zpřesněním (ICGS)''', který obsahuje dvě vnitřní smyčky jako CGS (je tedy paralelizovatelný), ale obě smyčky se provedou dvakrát (čímž se výrazně zlepší numerické vlastnosti, ztráta ortogonality mezi vektory <math>q_i</math> je pak dokonce menšní než u MGS).
=== Ztráta ortogonality ===
=== Vztah Gramova-Schmidtova algoritmu a QR rozkladu ===▼
Nechť <math>\hat{Q}_n</math> (<math>\hat{Q}_n=Q_n+E_n</math>) je matice vektorů spočtených pomocí některé varianty Gramova-Schmidtova algoritmu v počítači se standardní konečnou aritmetikou s plovoucí řádovou čárkou. Veličina
:<math>\|\hat{Q}_n^T\hat{Q}_n-I_n\|_2</math>
se nazývá '''ztráta ortogonality''' a je jednou z klíčových veličin sloužících k posouzení kvality spočtené ortonormální báze.
Uvažujme tzv. '''Lauchliho matici'''
:<math>A=\left[\begin{array}{ccc}1&\ldots&1\\\rho&&0\\&\ddots&\\0&&\rho\end{array}\right]\in\mathbb{R}^{(n+1)\times n}, \qquad n=20,\; \rho=10^{-7},\; \kappa_2(A)\approx 4.47\times10^7,</math>
kde <math>\kappa_2(A)</math> je [[Podmíněnost matice|podmíněnost]] matice <math>A</math>.
Uvažujeme-li standardní aritmetiku se [[Strojová přesnost|strojovou přesností]] <math>\epsilon_M\approx2.22\times10^{-16}</math> (double), pak ztráta ortogonality odpovídající jednotlivým výše zmíněným algoritmům je v následující tabulce:
{| class="wikitable"
|+
! Algoritmus
! Ztráta ortogonality
|-
|CGS
|<math>2.2\times10^{-2}</math>
|-
|MGS
|<math>2.2\times10^{-9}</math>
|-
|ICGS
|<math>2.4\times10^{-16}</math>
|-
|}
Srovnáním sloupcových vektorů <math>a_k,\;q_j</math> a koeficientů <math>r_{j,k}</math> do matic,
| |||