Ortogonalizacja Grama-Schmidta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Ortogonalizacja Grama-Schmidta – przekształcenie układu liniowo niezależnych wektorów przestrzeni unitarnej w układ wektorów ortogonalnych. Przestrzenie liniowe rozpinane przez układy przed i po ortogonalizacji są tożsame, tak więc proces może służyć do ortogonalizowania bazy.

Opisana w tym artykule metoda nazwana została na cześć Jørgena Grama, matematyka duńskiego oraz Erharda Schmidta, matematyka niemieckiego.

Proces ortogonalizacji[edytuj]

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}. 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 przestrzeni unitarnej (niekoniecznie skończenie wymiarowej).

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]

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

Niech \mathbf{u}_{1},\dots, \mathbf{u}_{k} jest układem wektorów uzyskanym 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ą wzajemnie prostopadłe, czyli spełniają \langle \mathbf{u}_{s}, \mathbf{u}_{t} \rangle = 0 dla wszystkich t,s\in \{1\dots k-1\},~t\neq s oraz  \mathbf{u}_{s} \neq 0 dla s\in \{1\dots k-1\} .

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}_k =
\mathbf{v}_k - 
\sum\limits_{j=1}^{k-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_j \rangle}{\langle \mathbf{u}_j, \mathbf{u}_j \rangle}\mathbf{u}_j

Mnożąc skalarnie \mathbf{u}_l i \mathbf{u}_k i korzystając z własności iloczynu skalarnego (rozdzielności iloczynu względem sumy, przemienności i zgodności z mnożeniem przez skalar) otrzymujemy:

\langle \mathbf{u}_l, \mathbf{u}_k \rangle =
\left\langle \mathbf{u}_l,\  \mathbf{v}_k - 
\sum\limits_{j=1}^{k-1} \frac{\langle \mathbf{v}_k, \mathbf{u}_j \rangle}{\langle \mathbf{u}_j, \mathbf{u}_j \rangle}\mathbf{u}_j 
\right\rangle =
\langle \mathbf{v}_k, \mathbf{u}_l \rangle -
\sum\limits_{j=1}^{k-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

Na mocy założenia indukcyjnego w ostatniej sumie wszystkie składniki o indeksie j\neq l są zerowe, więc:

\langle \mathbf{u}_l, \mathbf{u}_k \rangle =
\langle \mathbf{v}_k, \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 =0

co oznacza, że wektor \mathbf{u}_k jest prostopadły z każdym innym wektorem \mathbf{u}_{1},\dots, \mathbf{u}_{k-1}

Wektor \mathbf{u}_k jest kombinacją liniową wektorów \mathbf{u}_{1},\dots, \mathbf{u}_{k-1}, \mathbf{v}_{k}. Z kolei \mathbf{u}_{k-1} jest kombinacją liniową wektorów \mathbf{u}_{1},\dots, \mathbf{u}_{k-2}, \mathbf{v}_{k-1}. Analogicznie dla wektora \mathbf{u}_{k-2} i tak dalej. Ostatecznie wektor \mathbf{u}_k jest kombinacją liniową wektorów \mathbf{v}_{1},\dots, \mathbf{v}_{k-1}, \mathbf{v}_{k} a dokładniej

\mathbf{u}_{k}=\alpha_1\mathbf{v}_{1}+\dots + \alpha_{k-1}\mathbf{v}_{k-1}+ 1\cdot\mathbf{v}_{k}.

Gdyby \mathbf{u}_k=0, to układ \mathbf{v}_{1},\dots, \mathbf{v}_{k-1}, \mathbf{v}_{k} wbrew założeniom byłby liniowo zależny, bo nie wszystkie współczynniki liczbowe kombinacji są zerowe.


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łady[edytuj]

Przestrzeń R²[edytuj]

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}.

Przestrzeń wielomianów[edytuj]

W przestrzeni wielomianów R[x] wielomiany postaci x^k stanowią bazę. Iloczyn skalarny w tej przestrzeni można wprowadzić np. w ten sposób:

\langle f,g\rangle _w = \int\limits_{-1}^1  f(x) g(x) dx\ \ \ f,g\in R[x]

Przeprowadzając proces ortogonalizacji układu 1,x,x^2, x^3, \dots dostaniemy układ ortogonalny 1,\ x,\ x^2-\tfrac{1}{3},\  x^3-\tfrac{1}{3}x, \dots Są to z dokładnością do czynnika wielomiany Legendre'a:

 P_n(x)= \frac{d^n}{dx^n}(x^2-1)^n\quad (n=0,1,\ldots)

Po znormalizowaniu powstanie układ

 \tilde{P_n}(x)= \sqrt{n+\tfrac{1}{2}}\cdot\frac{1}{(2n)!!}P_n(x)


Bibliografia[edytuj]

  • 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]