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.

[edytuj] 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$

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

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.

[edytuj] 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$