Gramova–Schmidtova ortogonalizace: Porovnání verzí
Smazaný obsah Přidaný obsah
m clean up, replaced: John Hopkins University → Johns Hopkins University za použití AWB |
|||
Řádek 17:
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, a protože požadujeme aby <math>\|q_1\|=1</math>, musí platit
:<math>a_1 = q_1r_{1,1},\qquad \text{kde}\quad r_{1,1}=\|a_1\|_2,</math>
a dostáváme 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
Řádek 27:
:<math>q_1^Ta_2 = q_1^Tq_1r_{1,2} + q_1^Tq_2r_{2,2}=r_{1,2}</math>
(připomeňme, že <math>q_1^Tq_1=\|q_1\|_2^2=1</math>), dostaneme vztah pro výpočet <math>r_{1,2}</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_{1,2} = q_2r_{2,2}, \qquad\text{kde}\quad r_{2,2}=\|a_2-q_1r_{1,2}\|_2</math>
je norma zbytu vektoru <math>a_2</math> po ortogonalizaci proti <math>q_1</math>. Všimněme si, že po dosazení za <math>r_{1,2}</math> dostáváme
:<math>a_2-q_1q_1^Ta_2 = (I_m-q_1q_1^T)a_2 = q_2r_{2,2},\qquad\text{kde matice}\quad (I_m-q_1q_1^T)</math>
Řádek 37:
není nic jiného, než [[ortogonální projektor]] do [[ortogonální doplněk|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_k</math>.
Algoritmicky zapsáno:
Řádek 60:
== Varianty algoritmu a jejich chování ==
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í.
Řádek 70:
:<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ů najednou, 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ů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ší než u MGS).
Řádek 80:
:<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'''<ref>{{Citace elektronické monografie
Řádek 134:
:<math>\langle p(x),q(x)\rangle_w = \int_a^b p(x)q(x)w(x)dx</math>,
kde <math>w(x)</math> je nějaká váhová funkce. Aplikací Gramova-Schmidtova algoritmu na sadu vektorů (polynomů) <math>1,x,x^2,\ldots,x^{n-1}</math> (v tomto pořadí) dostáváme, pro vhodně volené <math>a,\,b</math> a váhovou funkci <math>w(x)</math> libovolnou sadu [[Ortogonální polynomy|ortogonálních polynomů]] (normalizovanou vzhledem k normě indukované daným skalárním součinem).
Pro <math>a=-1,\,b=1,\,w(x)=1</math> Gramův-Schmidtův algoritmus generuje [[Legenderovy polynomy]],
Řádek 144:
== Literatura ==
* [[Gene H. Golub|Gene Howard Golub]], Charles F. Van Loan: ''Matrix Computations'',
* J. Duintjer Tebbens, I. Hnětynková, M. Plešinger, [[Zdeněk Strakoš|Z. Strakoš]], P. Tichý: ''Analýza metod pro maticové výpočty, základní metody.'' Matfyzpress 2012. ISBN 978-80-7378-201-6. (Kapitola 3, Ortogonální transformace a QR rozklady, str. 53-88.)
[[Kategorie:Lineární algebra]]
| |||