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

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í

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

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

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

Vztah Gramova-Schmidtova algoritmu a QR rozkladu

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

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

  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

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