|
== Algoritmus ==
Na vstupu mějme ''n'' lineárně nezávislých vektorů <math>v_1, ..., v_n</math>, které generují prostor ''V''. Našim úkolem je najít vektory <math>u_1, ..., u_n</math>, které rovněž generují ''V'', avšak jsou si navzájem kolmé. Případně <math>e_1, ..., e_n</math>, které navíc mají jednotkovou délku.
Uvažujme pro jednoduchost <math>\mathbb{R}^m</math> reálný linerá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
Zajímavým pozorováním je, že za první vektor <math>u_1</math> můžeme zvolit jakýkoli vektor z ''V''. Druhý vektor <math>u_2</math> může být rovněž jakýkoli, avšak musí být kolmý k <math>u_1</math>. Každý další vektor musí být kolmý ke všem předchozím.
:<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>
Definujme si '''operátor projekce''' takto:
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>\mathrm{proj}_{\mathbf{u}}\,(\mathbf{v}) = {\langle \mathbf{u}, \mathbf{v}\rangle\over\langle \mathbf{u}, \mathbf{u}\rangle}\mathbf{u} , </math>
kdee <math>\langle \mathbf{u}, \mathbf{v}\rangle</math> znamená [[skalární součin]] '''u''' a '''v'''. Tento operátor promítá vektor '''v''' kolmo k přímce určené vektorem '''u'''.
Gramova–Schmidtova ortogonalizace pak vypadá takto:
:<math>a_1 = q_1r_{1,1},\qquad \text{kde}\quad r_{1,1}=\|a_1\|_2,</math>
: <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
\begin{align}
\mathbf{u}_1 & = \mathbf{v}_1, & \mathbf{e}_1 & = {\mathbf{u}_1 \over \|\mathbf{u}_1\|} \\
:<math>a_2 = q_1r_{1,2} + q_2r_{2,2},</math>
\mathbf{u}_2 & = \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_2),
& \mathbf{e}_2 & = {\mathbf{u}_2 \over \|\mathbf{u}_2\|} \\
kde <math>q_2</math> je nějaký nový vektor takový, že <math>q_1^Tq_2=0,\;\|q_2\|_2=1</math>. Po pronásobení předchozího vztahu <math>q_1^T</math> zleva,
\mathbf{u}_3 & = \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_3)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_3), & \mathbf{e}_3 & = {\mathbf{u}_3 \over \|\mathbf{u}_3\|} \\
\mathbf{u}_4 & = \mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_3}\,(\mathbf{v}_4), & \mathbf{e}_4 & = {\mathbf{u}_4 \over \|\mathbf{u}_4\|} \\
:<math>q_1^Ta_2 = q_1^Tq_1r_{1,2} + q_1^Tq_2r_{2,2}=r_{1,2}</math>
& {}\ \ \vdots & & {}\ \ \vdots \\
\mathbf{u}_k & = \mathbf{v}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{u}_j}\,(\mathbf{v}_k), & \mathbf{e}_k & = {\mathbf{u}_k\over \|\mathbf{u}_k \|}.
(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
\end{align}
</math>
:<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>
není nic jiného, než [[ortogonální projektor]] do [[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:
:00: '''vstup''' <math>a_1,\ldots,a_n</math>
:01: <math>r_{1,1} := \|a_1\|_2</math>
:02: <math>q_1 := a_1/r_{1,1}</math>
:03: '''for''' <math>k := 2,\ldots,n</math>
:04: <math>p := a_k</math>
:05: '''for''' <math>j := 1,\ldots,k-1</math>
:06: <math>r_{j,k} := q_j^Tp = \langle p,q_j\rangle</math>
:07: '''end'''
:08: '''for''' <math>j := 1,\ldots,k-1</math>
:09: <math>p := p - q_jr_{j,k}</math>
:10: '''end'''
:11: <math>r_{k,k} := \|p\|_2</math>
:12: <math>q_k := p/r_{k,k}</math>
: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í ==
| 