Ortogonalizacja Grama-Schmidta

Ortogonalizacja Grama-Schmidta to metoda za pomocą której można przekształcić zbiór liniowo niezależnych wektorów przestrzeni unitarnej w zbiór wektorów ortogonalnych. Przestrzenie liniowe rozpinane przez zbiory przed i po ortogonalizacji są tożsame, tak więc proces może służyć do ortogonalizowania bazy.

Proces został nazwany na cześć Jørgena Grama, matematyka duńskiego, oraz Erharda Schmidta, matematyka niemieckiego.

Proces ortogonalizacji

Operator rzutowania ortogonalnego wektora $\mathbf{v}$ na wektor $\mathbf{u}$ definiujemy jako:

$\mathrm{proj}_{\mathbf{u}}\,\mathbf{v} = {\langle \mathbf{v}, \mathbf{u}\rangle\over\langle \mathbf{u}, \mathbf{u}\rangle}\mathbf{u}.$

Wówczas dla układu k wektorów $\{\mathbf{v}_1, \ldots,\mathbf{v}_k\}$ proces przebiega następująco:

Dwa pierwsze kroki procesu ortogonalizacji

$\mathbf{u}_1 = \mathbf{v}_1,$

$\mathbf{u}_2 = \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_2,$

$\mathbf{u}_3 = \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_3,$

$\vdots$

$\mathbf{u}_k = \mathbf{v}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{u}_j}\,\mathbf{v}_k,$

Otrzymany zbiór $\{\mathbf{u}_1,\ldots,\mathbf{u}_k\}$ jest zbiorem wektorów ortogonalnych.

Aby zbudować w ten sposób zbiór ortonormalny, każdy wektor należy podzielić przez jego normę:

$\mathbf{e}_n = {\mathbf{u}_n\over||\mathbf{u}_n||}, n=1, 2, ..., k$

Proces ortogonalizacji pozwala na wskazanie bazy ortogonalnej w dowolnej n-wymiarowej przestrzeni unitarnej.

Własności numeryczne tego algorytmu nie są zbyt dobre i uzyskane wektory nadal nie są ortogonalne (za sprawą błędów zaokrągleń), toteż w praktyce powtarza się proces dokonując reortogonalizacji.

Dowód ortogonalności otrzymanej bazy

Dowód ortogonalności tak otrzymanego układu opiera się na indukcji:

Załóżmy, że $\mathbf{u}_{1},\dots, \mathbf{u}_{k}$ jest bazą ortogonalną uzyskaną w procesie ortogonalizacji Grama-Schmidta z bazy $\mathbf{v}_{1}\dots \mathbf{v}_{k}$. Załóżmy, że wektory $\mathbf{u}_{1},\dots, \mathbf{u}_{k-1}$ są wzajmenie prostopadłe, co oznacza, że $\langle \mathbf{u}_{s}, \mathbf{u}_{t} \rangle = 0$ dla wszystkich $t,s\in \{1\dots k-1\},~t\neq s$.

Pokażemy, że wektor $\mathbf{u}_k$ otrzymany z algorytmu ortogonalizacji Grama-Schmidta jest prostopadły z dowolnym wektorem $\mathbf{u}_l$, gdzie $l \in \{1,\dots, k-1\}$.

$\mathbf{u}_l = \mathbf{v}_l - \frac{\langle \mathbf{v}_{l}, \mathbf{u}_{1} \rangle}{\langle \mathbf{u}_{1}, \mathbf{u}_{1} \rangle} \mathbf{u}_1 - \dots - \frac{\langle \mathbf{v}_{l}, \mathbf{u}_{l-1} \rangle}{\langle \mathbf{u}_{l-1}, \mathbf{u}_{l-1} \rangle}\mathbf{u}_{l-1}$

$\mathbf{u}_k = \mathbf{v}_k - \frac{\langle \mathbf{v}_{k}, \mathbf{u}_{1} \rangle}{\langle \mathbf{u}_{1}, \mathbf{u}_{1} \rangle} \mathbf{u}_1 - \dots - \frac{\langle \mathbf{v}_{k}, \mathbf{u}_{l-1} \rangle}{\langle \mathbf{u}_{l-1}, \mathbf{u}_{l-1} \rangle}\mathbf{u}_{l-1}- \frac{\langle \mathbf{v}_{k}, \mathbf{u}_{l} \rangle}{\langle \mathbf{u}_{l}, \mathbf{u}_{l} \rangle}\mathbf{u}_{l} - \dots - \frac{\langle \mathbf{v}_{k}, \mathbf{u}_{k-1} \rangle}{\langle \mathbf{u}_{k-1}, \mathbf{u}_{k-1} \rangle}\mathbf{u}_{k-1}$

Mnożąc skalarnie $\mathbf{u}_l$ i $\mathbf{u}_k$ otrzymujemy:

$\langle \mathbf{u}_l, \mathbf{u}_k \rangle = \left\langle \mathbf{u}_l, \left(\mathbf{v}_k - \sum\limits_{j=1}^{l-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_j \rangle}{\langle \mathbf{u}_j, \mathbf{u}_j \rangle}\mathbf{u}_j - \frac{\langle \mathbf{v}_k, \mathbf{u}_l \rangle}{\langle \mathbf{u}_l, \mathbf{u}_l \rangle}\mathbf{u}_l - \sum\limits_{i=l+1}^{k-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_i \rangle}{\langle \mathbf{u}_i, \mathbf{u}_i \rangle}\mathbf{u}_i\right)\right\rangle=$

Korzystając z własności iloczynu skalarnego (rozdzielności iloczynu względem sumy, przemienności i zgodności z mnożeniem przez skalar):

$= \langle \mathbf{v}_k, \mathbf{u}_l \rangle - \left\langle \mathbf{u}_l,\sum\limits_{j=1}^{l-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_j \rangle}{\langle \mathbf{u}_j, \mathbf{u}_j \rangle}\mathbf{u}_j \right \rangle - \frac{\langle \mathbf{v}_k, \mathbf{u}_l \rangle}{\langle \mathbf{u}_l, \mathbf{u}_l \rangle} \langle\mathbf{u}_l, \mathbf{u}_l \rangle - \left\langle \mathbf{u}_l, \sum\limits_{i=l+1}^{k-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_i \rangle}{\langle \mathbf{u}_i, \mathbf{u}_i \rangle}\mathbf{u}_i \right\rangle$

$= \langle \mathbf{v}_k, \mathbf{u}_l \rangle - \sum\limits_{j=1}^{l-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_j \rangle}{\langle \mathbf{u}_j, \mathbf{u}_j \rangle}\langle \mathbf{u}_j, \mathbf{u}_l \rangle - \frac{\langle \mathbf{v}_k, \mathbf{u}_l \rangle}{\langle \mathbf{u}_l, \mathbf{u}_l \rangle} \langle\mathbf{u}_l, \mathbf{u}_l \rangle - \sum\limits_{i=l+1}^{k-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_i \rangle}{\langle \mathbf{u}_i, \mathbf{u}_i \rangle}\langle \mathbf{u}_i, \mathbf{u}_l\rangle =$

Na mocy założenia indukcyjnego:

$= \langle \mathbf{v}_k, \mathbf{u}_l \rangle - 0 - \langle \mathbf{v}_k, \mathbf{u}_l \rangle - 0 = 0$, co oznacza, że wektor $\mathbf{u}_k$ jest prostopadły z każdym innym wektorem $\mathbf{u}_{1},\dots, \mathbf{u}_{k-1}$

Ponieważ ortogonalny układ wektorów jest liniowo niezależny, a każdy z wektorów $\mathbf{u}_i$ jest kombinacją liniową elementów z bazy $\mathbf{v}_1,\dots,\mathbf{v}_k$, więc tak wyznaczone wektory $\mathbf{u}_1,\dots ,\mathbf{u}_k$ istotnie są bazą.

Przykład

Rozważmy zbiór wektorów w R² (ze standardowym iloczynem skalarnym):

$S = \left\lbrace\mathbf{v}_1=\begin{bmatrix} 3 \\ 1\end{bmatrix}, \mathbf{v}_2=\begin{bmatrix}2 \\2\end{bmatrix}\right\rbrace.$

Teraz przeprowadzamy ortogonalizację, aby otrzymać wektory parami prostopadłe:

$\mathbf{u}_1=\mathbf{v}_1=\begin{bmatrix}3\\1\end{bmatrix}$

$\mathbf{u}_2 = \mathbf{v}_2 - \mathrm{proj}_{\mathbf{u}_1} \, (\mathbf{v}_2) = \begin{bmatrix}2\\2\end{bmatrix} - \mathrm{proj}_{\left[{3 \atop 1}\right]} \, \left({\begin{bmatrix}2\\2\end{bmatrix}}\right) = \begin{bmatrix} -2/5 \\6/5 \end{bmatrix}.$

Sprawdzamy, że wektory u₁ i u₂ rzeczywiście są prostopadłe:

$\langle\mathbf{u}_1,\mathbf{u}_2\rangle = \left\langle \begin{bmatrix}3\\1\end{bmatrix}, \begin{bmatrix}-2/5\\6/5\end{bmatrix} \right\rangle = -\frac{6}{5} + \frac{6}{5} = 0,$

ponieważ jeśli dwa wektory są prostopadłe, to ich iloczyn skalarny wynosi 0.

Następnie normalizujemy wektory, dzieląc każdy przez ich normy:

$\mathbf{e}_1 = {1 \over \sqrt {10}}\begin{bmatrix}3\\1\end{bmatrix}$

$\mathbf{e}_2 = {1 \over \sqrt{40 \over 25}} \begin{bmatrix}-2/5\\6/5\end{bmatrix} = {1\over\sqrt{10}} \begin{bmatrix}-1\\3\end{bmatrix}.$

Funkcje ciągłe

Jeżeli iloczyn skalarny funkcji ciągłych jest określony wzorem:

$\langle f,g\rangle _w = \int\limits_a^b w(x) f(x) g(x) dx.$

gdzie $w(x)$ jest funkcją wagową, to dla zbioru funkcji liniowo niezależnych przekształcenie w zbiór funkcji ortogonalnych przebiega następująco:

$g_0(x) = f_0(x)$

$g_i(x) = f_i(x) - \sum_{j=0}^{i-1} g_j(t)\frac{\int\limits_a^b w(t) f_i(t)g_j(t) dt}{\int\limits_a^b w(t) g_j^2(t) dt}$

Iloczyn skalarny funkcji $g_i(x)$ i $g_j(x)$ dla różnych $i$,$j$ wynosi (bez straty ogólności przyjmijmy, że $i>j$):

$\int\limits_a^b w(t) g_j(t) g_i(t) dt = \int\limits_a^b w(t) g_j(t) f_i(t) dt - \int\limits_a^b w(s) g_j(s) g_j(s)\frac{\int\limits_a^b w(t) f_i(t)g_j(t) dt}{\int\limits_a^b w(t) g_j^2(t) dt} ds +$

$- \sum_{k=0 \and k\ne j}^{i-1} \frac{\int\limits_a^b w(t) f_i(t)g_k(t) dt}{\int\limits_a^b w(t) g_k^2(t) dt} \int\limits_a^b w(s) g_j(s) g_k(s) ds$

Jeśli dla wszystkich różnych par $j,k$ mniejszych od $i$ iloczyn skalarny wynosi 0, to:

$\int\limits_a^b w(t) g_j(t) g_i(t) dt = \int\limits_a^b w(t) g_j(t) f_i(t) dt - \int\limits_a^b w(s) g_j(s) g_j(s)\frac{\int\limits_a^b w(t) f_i(t)g_k(t) dt}{\int\limits_a^b w(t) g_k^2(t) dt} ds$

$\int\limits_a^b w(t) g_j(t) g_i(t) dt = \int\limits_a^b w(t) f_i(t) g_j(t) dt - \frac{\int\limits_a^b w(t) f_i(t)g_j(t) dt}{\int\limits_a^b w(t) g_j^2(t) dt} \int\limits_a^b w(s) g_j^2(s) ds$

$\int\limits_a^b w(t) g_j(t) g_i(t) dt = \int\limits_a^b w(t) f_i(t) g_j(t) dt - \int\limits_a^b w(t) f_i(t)g_j(t) dt = 0$

Bibliografia

• Mostowski A., Stark, M., Algebra liniowa, PWN, Warszawa 1958, wydanie czwarte, ss. 140-142
• Gleichgewicht B., Algebra. Podręcznik dla kierunków nauczycielskich studiów matematycznych, PWN, Warszawa 1976, ss. 184-186

Zobacz też

• Wielomiany ortogonalne