Wikipedie

Gramova–Schmidtova ortogonalizace: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
m DvorapaBot přesunul stránku Gramova-Schmidtova ortogonalizace na Gramova–Schmidtova ortogonalizace: Robot: změna konsensu dle WP:Název článku
m Robot: oprava ISBN; kosmetické úpravy
Řádek 7:
| datum přístupu = 2011-10-31
| vydavatel = Ústav pro jazyk český Akademie věd ČR
}}</ref> ''Gram-Schmidtova ortogonalizace'') je metoda, která v daném [[unitární prostor|unitárním prostoru]] (neboli [[vektorový prostor|vektorovém prostoru]] se [[skalární součin|skalárním součinem]]) umožňuje pro zadanou [[konečná množina|konečnou množinu]] [[vektor]]ů nalézt [[Ortonormální báze|ortonormální bázi]] [[podprostor]]u jimi generovaného.
 
== Algoritmus ==
Uvažujme pro jednoduchost <math>\mathbb{R}^m</math> reálný lineární vektorový prostor sloupcových vektorů o <math>m</math> složkách (se standardním skalární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 q_k,q_j\rangle=q_j^Tq_k = \delta_{k,j}</math>
Řádek 32:
:<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 zbytku 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 62:
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 výpočet pomocí MGS je numericky výrazně 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>q_1,\ldots,q_n</math>.
Řádek 72:
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).
 
=== Ztráta ortogonality ===
Řádek 141:
 
== Literatura ==
* [[Gene H. Golub|Gene Howard Golub]], Charles F. Van Loan: ''Matrix Computations'', Johns Hopkins University Press, 1996 (3rd Ed.). (Zejména kapitoly 5.2.7 CGS, 5.2.8 MGS a 5.2.9 Work and Accuracy.)
* 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]]
Citováno z „https://cs.wikipedia.org/wiki/Gramova–Schmidtova_ortogonalizace“