Gramova–Schmidtova ortogonalizace

Gramův-Schmidtův proces neboli Gramova-Schmidtova ortogonalizace (nesprávně[1] Gram-Schmidtova ortogonalizace) je metoda, která v daném unitárním prostoru (neboli vektorovém prostoru se skalárním součinem) umožňuje pro zadanou konečnou množinu vektorů nalézt ortonormální bázi podprostoru jimi generovaného.

Algoritmus

editovat

Uvažujme pro jednoduchost   reálný lineární vektorový prostor sloupcových vektorů o   složkách (se standardním skalárním součinem). Nechť   jsou, opět pro jednoduchost, lineárně nezávislé, tedy  . Úkolem je nalézt ortonormální bázi    -rozměrného podprostoru  , který vektory   generují; má tedy platit

 

kde   značí lineární obal množiny v závorce.

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  , musí platit

 

a dostáváme vztah pro výpočet prvního vektoru ortonormální báze  . Protože   je lineárně nezávislý na   a tedy i na  , můžeme ho vyjádřit jako

 

kde   je nějaký nový vektor takový, že  . Po pronásobení předchozího vztahu   zleva,

 

(připomeňme, že  ), dostaneme vztah pro výpočet   (ortogonalizační koeficient; tj. velikost projekce   do směru  ). Protože známe   dostáváme

 

je norma zbytku vektoru   po ortogonalizaci proti  . Všimněme si, že po dosazení za   dostáváme

 

není nic jiného, než ortogonální projektor do ortogonálního doplňku   lineárního obalu vektoru   v  .

Tento postup lze zřejmě opakovat do vyčerpání všech vektorů  .

Algoritmicky zapsáno:

00: vstup  
01:  
02:  
03: for  
04:      
05:     for  
06:         
07:     end
08:     for  
09:         
10:     end
11:      
12:      
13: end

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ů.

Varianty algoritmu a jejich chování

editovat

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ů  ) lze provádět nezávisle pro jednotlivá  ; tedy, jednotlivá   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  .

Označíme-li  , lze vztah pro ortogonalizaci vektoru   psát pomocí projektorů dvěma matematicky ekvivalentními způsoby

 

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  -tém kroku částečně eliminovat chyby vzniklé zaokrouhlováním v předchozích krocích  .

Ř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   je pak dokonce menší než u MGS).

Ztráta ortogonality

editovat

Nechť   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, tj.   a  . Veličina

 

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[2]

 

kde   je podmíněnost matice  . Uvažujeme-li standardní aritmetiku se strojovou přesností   (double), pak ztráta ortogonality odpovídající jednotlivým výše zmíněným algoritmům aplikovaným na danou Lauchliho matici, je ve druhém sloupci následující tabulky. Ve třetím sloupci je obecný vztah platný pro libovolnou matici  

Algoritmus Ztráta ortogonality (Lauchliho matice) Ztráta ortogonality (obecně)
CGS    
MGS    
ICGS    

Vztah Gramova-Schmidtova algoritmu a QR rozkladu

editovat

Srovnáním sloupcových vektorů   a koeficientů   do matic,

 

kde   a   je čtvercová regulární matice dostáváme

 

tedy QR rozklad matice   (pro ověření stačí porovnat  -tý sloupec rovnosti, tedy   s  -tým sloupcem součinu  ).

Ortogonální polynomy

editovat

Gramův-Schmidtův algoritmus lze aplikovat na prvky libovolného prostoru se skalárním součinem. Uvažujeme například prostor polynomů   se skalárním součinem

 ,

kde   je nějaká váhová funkce. Aplikací Gramova-Schmidtova algoritmu na sadu vektorů (polynomů)   (v tomto pořadí) dostáváme, pro vhodně volené   a váhovou funkci   libovolnou sadu ortogonálních polynomů (normalizovanou vzhledem k normě indukované daným skalárním součinem).

Pro   Gramův-Schmidtův algoritmus generuje Legenderovy polynomy, pro   dostaneme Čebyševovy polynomy prvního druhu, atd.

Reference

editovat
  1. Internetová jazyková příručka [online]. Ústav pro jazyk český Akademie věd ČR [cit. 2011-10-31]. Dostupné online. 
  2. Lauchli matrix [online]. Matrix Market [cit. 2011-11-03]. Dostupné online. 

Literatura

editovat
  • 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, 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.)