Ortogonalizacja Grama-Schmidta

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

Dwa pierwsze kroki procesu ortogonalizacji

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

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

Wówczas dla układu k wektorów ${\displaystyle \{\mathbf {v} _{1},\dots ,\mathbf {v} _{k}\}}$ proces przebiega następująco:

${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},}$

${\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {v} _{2},}$

${\displaystyle \mathbf {u} _{3}=\mathbf {v} _{3}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {v} _{3}-\mathrm {proj} _{\mathbf {u} _{2}}\,\mathbf {v} _{3},}$

${\displaystyle \vdots }$

${\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {u} _{j}}\,\mathbf {v} _{k},}$

czyli wektor ${\displaystyle u_{k}}$ to wektor ${\displaystyle v_{k}}$ po odjęciu od niego rzutu wektora ${\displaystyle v_{k}}$ na podprzestrzeń rozpiętą przez wektory ${\displaystyle u_{1},...,u_{k-1}.}$ Otrzymany zbiór ${\displaystyle \{\mathbf {u} _{1},\dots ,\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ę:

${\displaystyle \mathbf {e} _{n}={\frac {\mathbf {u} _{n}}{||\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

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

Niech ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k}}$ jest układem wektorów uzyskanym w procesie ortogonalizacji Grama-Schmidta z bazy ${\displaystyle \mathbf {v} _{1}\dots \mathbf {v} _{k}.}$ Załóżmy, że wektory ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k-1}}$ są wzajemnie prostopadłe, czyli spełniają ${\displaystyle \langle \mathbf {u} _{s},\mathbf {u} _{t}\rangle =0}$ dla wszystkich ${\displaystyle t,s\in \{1\dots k-1\},~t\neq s}$ oraz ${\displaystyle \mathbf {u} _{s}\neq 0}$ dla ${\displaystyle s\in \{1\dots k-1\}.}$

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

${\displaystyle \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 ${\displaystyle \mathbf {u} _{l}}$ i ${\displaystyle \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:

${\displaystyle \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 ${\displaystyle j\neq l}$ są zerowe, więc:

${\displaystyle \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 ${\displaystyle \mathbf {u} _{k}}$ jest prostopadły z każdym innym wektorem ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k-1}}$

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

${\displaystyle \mathbf {u} _{k}=\alpha _{1}\mathbf {v} _{1}+\dots +\alpha _{k-1}\mathbf {v} _{k-1}+1\cdot \mathbf {v} _{k}.}$

Gdyby ${\displaystyle \mathbf {u} _{k}=0,}$ to układ ${\displaystyle \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 ${\displaystyle \mathbf {u} _{i}}$ jest kombinacją liniową elementów z bazy ${\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k},}$ więc tak wyznaczone wektory ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k}}$ istotnie są bazą.

Przykłady

Przestrzeń R²

Rozważmy zbiór wektorów w ${\displaystyle \mathbf {R} ^{2}}$ (ze standardowym iloczynem skalarnym):

${\displaystyle 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:

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

${\displaystyle \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:

${\displaystyle \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:

${\displaystyle \mathbf {e} _{1}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3\\1\end{bmatrix}}}$

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

Przestrzeń wielomianów

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

${\displaystyle \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 ${\displaystyle 1,\,x,\,x^{2},\,x^{3},\dots ,}$ dostaniemy układ ortogonalny ${\displaystyle 1,\,x,\,x^{2}-{\tfrac {1}{3}},\,x^{3}-{\tfrac {3}{5}}x,\,\dots }$

Są to z dokładnością do czynnika wielomiany Legendre’a:

${\displaystyle P_{n}(x)={\frac {d^{n}}{dx^{n}}}(x^{2}-1)^{n}\quad (n=0,1,\ldots ).}$

Po znormalizowaniu powstanie układ

${\displaystyle {\tilde {P_{n}}}(x)={\sqrt {n+{\tfrac {1}{2}}}}\cdot {\frac {1}{(2n)!!}}P_{n}(x).}$

Zobacz też

• wielomiany ortogonalne

Bibliografia

• Mostowski A., Stark, M., Algebra liniowa, Państwowe Wydawnictwo Naukowe, Warszawa 1958, wydanie czwarte, s. 140–142.
• Gleichgewicht B., Algebra. Podręcznik dla kierunków nauczycielskich studiów matematycznych, PWN, Warszawa 1976, s. 184–186.