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.
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
![{\displaystyle \mathrm {span} \{a_{1},\ldots ,a_{n}\}=\mathrm {span} \{q_{1},\ldots ,q_{n}\},\qquad \langle q_{k},q_{j}\rangle =q_{j}^{T}q_{k}=\delta _{k,j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c09348594c575b095f4278cfd353dcb89faa1158)
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
![{\displaystyle a_{1}=q_{1}r_{1,1},\qquad {\text{kde}}\quad r_{1,1}=\|a_{1}\|_{2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3005a1b8ff86ff428f48c1e4e7087e5abc0be562)
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
![{\displaystyle a_{2}=q_{1}r_{1,2}+q_{2}r_{2,2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9430acdb653eca91f080941c50a356469bac591a)
kde
je nějaký nový vektor takový, že
. Po pronásobení předchozího vztahu
zleva,
![{\displaystyle q_{1}^{T}a_{2}=q_{1}^{T}q_{1}r_{1,2}+q_{1}^{T}q_{2}r_{2,2}=r_{1,2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e16722930e74631b38153eb1e1b026f3aff3a1c)
(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
![{\displaystyle a_{2}-q_{1}r_{1,2}=q_{2}r_{2,2},\qquad {\text{kde}}\quad r_{2,2}=\|a_{2}-q_{1}r_{1,2}\|_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/987dc5bb96e01d1fc5d1528743a04e858c20245e)
je norma zbytku vektoru
po ortogonalizaci proti
. Všimněme si, že po dosazení za
dostáváme
![{\displaystyle a_{2}-q_{1}q_{1}^{T}a_{2}=(I_{m}-q_{1}q_{1}^{T})a_{2}=q_{2}r_{2,2},\qquad {\text{kde matice}}\quad (I_{m}-q_{1}q_{1}^{T})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8317002eab37d85081e052384b56d8f984fe093)
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
![{\displaystyle a_{1},\ldots ,a_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/451345cc97e2ed923dd4656fcc400c3f37119cca)
- 01:
![{\displaystyle r_{1,1}:=\|a_{1}\|_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9e624ad6a781b775255ed177b6606b5e52de953)
- 02:
![{\displaystyle q_{1}:=a_{1}/r_{1,1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84f1137653d61995e744c239d3d85648d036434f)
- 03: for
![{\displaystyle k:=2,\ldots ,n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5431620dbb6726c433d24f6fe08846cd27fbc34)
- 04:
![{\displaystyle p:=a_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87318feb9cbea21dc6f206c197a82d9e1a2677a5)
- 05: for
![{\displaystyle j:=1,\ldots ,k-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d8650ce22ff4fe1d278b74647804cf3c09276b0)
- 06:
![{\displaystyle r_{j,k}:=q_{j}^{T}p=\langle p,q_{j}\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/003e480835e00b9804f896930a37d35dcb180f73)
- 07: end
- 08: for
![{\displaystyle j:=1,\ldots ,k-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d8650ce22ff4fe1d278b74647804cf3c09276b0)
- 09:
![{\displaystyle p:=p-q_{j}r_{j,k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36a14278d6e72341fab6e025f7527a403c396592)
- 10: end
- 11:
![{\displaystyle r_{k,k}:=\|p\|_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2daad010af5f378a6d4308065de1cb416dd1270)
- 12:
![{\displaystyle q_{k}:=p/r_{k,k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1db516912d3b01950ff61b75895cc78ab08cd61)
- 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ů.
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
![{\displaystyle p:=(I_{m}-Q_{k}Q_{k}^{T})a_{k+1}=(I_{m}-q_{k}q_{k}^{T})\ldots (I_{m}-q_{2}q_{2}^{T})(I_{m}-q_{1}q_{1}^{T})a_{k+1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0044805bdd0cf8a044221f378bb0286bf30e837a)
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).
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
![{\displaystyle \|{\hat {Q}}_{n}^{T}{\hat {Q}}_{n}-I_{n}\|_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdb7213607cd2502712c01101c635219bd8439cf)
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]
![{\displaystyle A=\left[{\begin{array}{ccc}1&\ldots &1\\\rho &&0\\&\ddots &\\0&&\rho \end{array}}\right]\in \mathbb {R} ^{(n+1)\times n},\qquad n=20,\;\rho =10^{-7},\;\kappa _{2}(A)\approx 4.47\times 10^{7},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44d1d7e53435697a9163312ceaf3269c1a9b884f)
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
|
|
|
Srovnáním sloupcových vektorů
a koeficientů
do matic,
![{\displaystyle A=[a_{1},\ldots ,a_{n}],\quad Q=[q_{1},\ldots ,q_{n}]\in \mathbb {R} ^{m\times n},\quad R=\left[{\begin{array}{cccc}r_{1,1}&r_{1,2}&\ldots &r_{1,n}\\0&r_{2,2}&\ldots &r_{2,n}\\\vdots &\ddots &\ddots &\vdots \\0&\ldots &0&r_{n,n}\end{array}}\right]\in \mathbb {R} ^{n\times n},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caf9cfe7ad5eecb14c0609a609f3da58ab93530c)
kde
a
je čtvercová regulární matice dostáváme
![{\displaystyle A=QR}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7d3eb7a53055abd0e9112408dbb2423035dfc72)
tedy QR rozklad matice
(pro ověření stačí porovnat
-tý sloupec rovnosti, tedy
s
-tým sloupcem součinu
).
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.
- ↑ Internetová jazyková příručka [online]. Ústav pro jazyk český Akademie věd ČR [cit. 2011-10-31]. Dostupné online.
- ↑ Lauchli matrix [online]. Matrix Market [cit. 2011-11-03]. Dostupné online.
- 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.)