Gramova–Schmidtova ortogonalizace: Porovnání verzí
Smazaný obsah Přidaný obsah
→Algoritmus: ... |
→Algoritmus: opravy, zpresneni, atd |
||
Řádek 7:
Uvažujme pro jednoduchost <math>\mathbb{R}^m</math> reálný linerární vektorový prostor sloupcových vektorů o <math>m</math> složkách (se standardním skalarním součinem). Nechť <math>a_1,\ldots,a_n\in\mathbb{R}^m</math> jsou, opět pro jednoduchost, lineárně nezávislé, tedy <math>n\leq m</math>. Úkolem je nalézt ortonormální bázi <math>q_1,\ldots,q_n</math> <math>n</math>-rozměrného podprostoru <math>\mathbb{R}^m</math>, který vektory <math>a_i</math> generují; má tedy platit
:<math>\mathrm{span}\{a_1,\ldots,a_n\}=\mathrm{span}\{q_1,\ldots,q_n\},\qquad \langle
Algoritmus danou sadu vektorů prochází postupně přičemž v každém kroku vygeneruje nový vektor hledané báze. Omezíme-li se pouze na první vektor, zřejmě musí platit
Řádek 13:
:<math>a_1 = q_1r_{11},\qquad \text{kde}\quad r_{11}=\|a_1\|_2</math>,
což ihned dává vztah pro výpočet prvního vektoru ortonormální báze <math>q_1=a_1/\|a_1\|_2</math>. Protože <math>a_2</math> je lineárně nezávislý na <math>a_1</math> a tedy i na <math>q_1</math>, můžeme ho vyjádřit jako
:<math>a_2 = q_1r_{12} + q_2r_{22
:<math>q_1^Ta_2 = q_1^Tq_1r_{12} + q_1^Tq_2r_{22}=r_{12}</math>,
vztah pro výpočet <math>r_{12}</math> (ortogonalizační koeficient; tj. velikost projekce <math>a_2</math> do směru <math>q_1</math>). Protože známe <math>a_2,\,q_1\,r_{1,2}<math> dostáváme
:<math>a_2-q_1r_{12} = q_2r_{22}, \qquad\text{kde}\quad r_{22}=\|a_2-q_1r_{12}\|_2</math>
je norma zbytu vektoru <math>a_2</math> po ortogonaliazci proti <math>q_1</math>.
:<math>a_2-q_1q_1^Ta_2 = (I_m-q_1q_1^T)a_2 = q_2r_{22},\qquad\text{kde matice}\quad (I_m-q_1q_1^T)</math>
není nic jiného, než [[ortogonální projektor]] do [[ortogonálního doplňku]] <math>\mathrm{span}\{q_1\}^\perp</math> lineárního obalu vektoru <math>q_1</math> v <math>\mathbb{R}^m</math>.
Tento postup lze zřejmě opakovat do vyčerpání všech vektorů <math>a_i</math>.
Algoritmicky zapsáno:
Řádek 31 ⟶ 41:
:04 <math>p := a_k</math>
:05 '''for''' <math>j := 1,\ldots,i-1</math>
:06 <math>r_{j,k} := q_j^Tp = \langle p,q_j\rangle</math>
:07 '''end'''
:08 '''for''' <math>j := 1,\ldots,i-1</math>
:09 <math>p := p -
:10 '''end'''
:11 <math>r_{k,k} := \|p\|_2</math>
Řádek 46 ⟶ 56:
Oba algoritmy CGS i MGS jsou matematicky ekvivalentní, jejich reálné implementace mají výrazně odlišné chování. CGS algoritmus je výrazně paralelní. Výpočet první vnitřní smyčky (tj. výpočet koeficientů <math>r_{j,k}</math>) lze provádět nezávisle pro jednotlivá <math>j</math>; tedy, jednotlivá <math>r_{j,k}</math> mohu počítat na různých procesorech, jejich výpočet se neovlivňuje, nezávisí na sobe a může probíhat paralelně. Zatímco MGS je z tohoto pohledu sekvenční.
Na druhou stranu je výpočet pomocí MGS výrazně numericky stabilnější než výpočet pomocí CGS, kde může, vlivem zaokrouhlovacích chyb, dojít k úplné ztrátě ortogonality mezi vektory <math>
Označíme-li <math>Q_{k}=[q_1,\ldots,q_{k}]\in\mathbb{R}^{m\times (k)},\;Q_{k}^TQ_{k]=I_{k}</math>, lze vztah pro ortogonalizaci vektoru <math>a_{k+1}</math> psát pomocí projektorů dvěma matematicky ekvivalentními způsoby
:<math>p := (I_m-Q_{k}Q_{k}^T)a_{k+1}=(I_m-q_kq_k^T)\ldots(I_m-q_2q_2^T)(I_m-q_1q_1^T)a_{k+1}</math>.
První projekce odpovídá výpočtu pomocí CGS, druhá postupná výpočtu pomocí MGS. Je zřejmé že CGS ortogonalizace (projekce) se počítá paralelně do všech směrů, kdežto sekvenční ortogonalizace (projekce) MGS umožňuje v <math>j</math>-tém kroku částečně eliminovat chyby vzniklé zaokrouhlováním v předchozích krocích <math>j-1,\ldots,2,1</math>.
Řešením v praxi používaným bývá tzv. '''klasický Gram-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 provede 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).
| |||