Ortogonalizacja Grama-Schmidta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

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,


czyli wektor u_k to wektor v_k po odjęciu od niego rzutu wektora v_k na podprzestrzeń rozpiętą przez wektory u_1,...,u_{k-1}. Zatem 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[edytuj | edytuj kod]

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

Rozważmy zbiór wektorów w R2 (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 u1 i u2 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[edytuj | edytuj kod]

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

  • 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ż[edytuj | edytuj kod]