Gramov-Schmidtov ortogonalizačný proces

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Gramov-Schmidtov ortogonalizačný proces (iné názvy: Gramov-Schmidtov proces ortogonalizácie, Gramova-Schmidtova ortogonalizácia) je proces, ktorým z množiny lineárne nezávislých vektorov priestoru vytvárame jeho ortonormálnu bázu. Ortonormálna báza sa vyznačuje vlastnosťou, že jej vektory majú normovanú jednotkovú dĺžku a navzájom sú ortogonálne. Vektorový priestor dimenzie n môže byť všeobecne generovaný ľubovoľnou n-ticou lineárne nezávislých vektorov. Tieto však majú rôznu orientáciu a nejednotnú dĺžku (normu). Na odstránenie respektíve normalizáciu sa využíva práve spomínaný Gram-Schimdtov ortogonalizačný proces.

Postup ortogonalizácie[upraviť | upraviť zdroj]

V prvom kroku Gramovho-Schmidtovho ortogonalizačného procesu sa pokladá za základ prvý vektor z množiny vektorov, ktoré normalizujeme. Podľa tohto vektora sa odvíja orientácia zvyšných. Ďalším krokom je samotná ortogonalizácia vektorov, a nakoniec normalizácia vektorov. Pre zjednodušenie výpočtov sa vektory normalizujú až na koniec procesu. Tento proces možno popísať ako rekurentný proces.

Vlastnosti a vzťahy[upraviť | upraviť zdroj]

Nech \mathcal{M}=\text{span}(\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n) je vektorový priestor, ktorý je generovaný lineárne nezávislými vektormi \mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n. To, že vektory sú lineárne nezávislé znamená, že existuje len triviálna nulová kombinácia koeficientov c_1,c_2,\cdots,c_n, že systém \mathbf{X}\mathbf{c}=0 má riešenie. Hľadáme také vektory \mathbf{y}_1,\mathbf{y}_2,\cdots,\mathbf{y}_n s vlastnosťou

(\mathbf{q}_i,\mathbf{q}_j)=\left\{\begin{array}{ll}1\,;&i=j\\0\,;&i\ne j\end{array}\right.

Odtiaľ vyplýva, že vektory musia byť ortogonálne a musia mať jednotkovú dĺžku. Tieto už budú priamo tvoriť bázu konkrétneho vektorového priestoru.

Proces ortogonalizácie[upraviť | upraviť zdroj]

Ortogonalizácia[upraviť | upraviť zdroj]

Najprv teda položíme \mathbf{x}_1=\mathbf{y}_1. Postupujeme ďalšími vektormi, pričom sú dané rekurentným vzťahom

\mathbf{y}_k=\mathbf{x}_k-\frac{\langle\mathbf{y}_1,\mathbf{x}_k\rangle}{\langle\mathbf{y}_1,\mathbf{y}_1\rangle}\mathbf{y}_1-\frac{\langle\mathbf{y}_2,\mathbf{x}_k\rangle}{\langle\mathbf{y}_2,\mathbf{y}_2\rangle}\mathbf{y}_2-\cdots-\frac{\langle\mathbf{y}_{k-1},\mathbf{x}_k\rangle}{\langle\mathbf{y}_{k-1},\mathbf{y}_{k-1}\rangle}\mathbf{y}_{k-1}

čo možno ekvivalentné prepísať do sumačného zápisu

\mathbf{y}_k=\mathbf{x}_k-\sum_{i=1}^{k-1}\frac{\langle\mathbf{y}_i,\mathbf{x}_k\rangle}{\langle\mathbf{y}_i,\mathbf{y}_i\rangle}\mathbf{y}_i

Treba poznamenať vlastnosť k\leq n, kde n=\dim\mathcal{M}. Samotný ortogonalizačný proces využíva k ortogonalizácií operátor projekcie, ktorý je definovaný

\text{proj}_{\mathbf{y}}(\mathbf{x})=\frac{\langle\mathbf{y},\mathbf{x}\rangle}{\langle\mathbf{y},\mathbf{y}\rangle}\mathbf{y}

Ortogonálnou projekciou vektora \mathbf{x} na priestor generovaný vektorom \mathbf{y} nazývame vektor \mathbf{y}' a platí \mathbf{y}'\in\text{span}(\mathbf{y}). Týmto spôsobom sa nájde ortogonálna projekcia daného vektora. Vektor ortogonálny na priestor generovaný vektorom \mathbf{y} je potom rozdiel \mathbf{x}-\mathbf{y}'. Platí teda, že skalárny súčin \langle \mathbf{x}-\mathbf{y}',\mathbf{y}\rangle je nulový.

Normalizácia[upraviť | upraviť zdroj]

Ortogonalizované vektory sa následne normalizujú na spoločnú jednotkovú dĺžku. Po tomto, dostaneme výsledný ortonormálny vektor \mathbf{q}_i, preto môžeme písať

\mathbf{q}_i=\frac{\mathbf{y}_i}{\Vert\mathbf{y}_i\Vert}

Ide o symbolický zápis súčinu každej zložky vektora \mathbf{y}_i prevrátenou hodnotu normy tohto vektora. Odtiaľ

\mathbf{q}_i=\left(\frac{q_1}{\Vert\mathbf{y}_i\Vert},\frac{q_2}{\Vert\mathbf{y}_i\Vert},\cdots,\frac{q_n}{\Vert\mathbf{y}_i\Vert}\right)

Pod normou vektora \Vert\mathbf{q}_i\Vert sa chápe norma definovaná nasledovne

\Vert\mathbf{y}_i\Vert=\sqrt{\langle\mathbf{y}_i,\mathbf{y}_i\rangle}

Príklad[upraviť | upraviť zdroj]

Majme vektorový priestor \mathbb{R}^2 generovaný dvojicou lineárne nezávislých vektorov \left\{(1,1)^T,(1/2,2)^T\right\}. Postupujeme najprv voľbou \mathbf{y}_1=(1,1)^T. Teraz podľa tohto vektora budú závisieť druhý. Použijeme vzťah pre ortogonalizáciu ďalších vektorov a dostávame rovnosť

\mathbf{y}_2=\begin{pmatrix}1/2\\2\end{pmatrix}-\frac{(1,1)\begin{pmatrix}1/2\\2\end{pmatrix}}{(1,1)\begin{pmatrix}1\\1\end{pmatrix}}\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}1/2\\2\end{pmatrix}-\frac{5}{4}\cdot\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}-3/4\\3/4\end{pmatrix}

Výsledný vektor je ortogonálny vektor k vektoru (1,1)^T. Teraz ho treba znormalizovať. Vektory generujú obyčajný euklidovský dvojrozmerný priestor, stačí preto použiť euklidovskú normu

\left\Vert\begin{pmatrix}-3/4\\3/4\end{pmatrix}\right\Vert=\sqrt{\frac{9}{16}+\frac{9}{16}}=\frac{3}{2\sqrt{2}}

Výsledný ortonormálny vektor bázy bude mať tvar

\mathbf{q}_2=\left(-\frac{\sqrt{2}}{2};\frac{\sqrt{2}}{2}\right)

Podobným spôsobom sa znormalizuje vektor (1,1)^T, ktorého norma je \Vert(1,1)^T\Vert=\sqrt{2} a odtiaľ

\mathbf{q}_1=\left(\frac{\sqrt{2}}{2};\frac{\sqrt{2}}{2}\right)

Ľahko možno skalárnym súčinom overiť, že vektory sú skutočne ortogonálne.

Použitie ortogonalizácie na iné priestory[upraviť | upraviť zdroj]

Gram-Schmidtov proces sa však nemusí používať výlučne pre euklidovské priestory \mathbb{R}^n. Môže sa použiť taktiež na ortogonalizáciu funkcií v priestore funkcií so skalárnym súčinom

\langle f(x),g(x)\rangle=\int_{a}^{b}f(x)g(x)\,\text{d}x

Pomocou ortogonalizačného procesu možno vytvoriť Legendrove polynómy, ktoré sú prvky priestoru funkcií so skalárnym súčinom

\langle P_1(x),P_2(x)\rangle=\int_{-1}^{1}P_1(x)P_2(x)\,\text{d}x