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.
Dwa pierwsze kroki procesu ortogonalizacji Operator rzutowania ortogonalnego wektora
v
{\displaystyle \mathbf {v} }
u
{\displaystyle \mathbf {u} }
p
r
o
j
u
v
=
⟨
v
,
u
⟩
⟨
u
,
u
⟩
u
.
{\displaystyle \mathrm {proj} _{\mathbf {u} }\,\mathbf {v} ={\frac {\langle \mathbf {v} ,\mathbf {u} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\mathbf {u} .}
Wówczas dla układu k wektorów
{
v
1
,
…
,
v
k
}
{\displaystyle \{\mathbf {v} _{1},\dots ,\mathbf {v} _{k}\}}
u
1
=
v
1
,
{\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},}
u
2
=
v
2
−
p
r
o
j
u
1
v
2
,
{\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {v} _{2},}
u
3
=
v
3
−
p
r
o
j
u
1
v
3
−
p
r
o
j
u
2
v
3
,
{\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 }
u
k
=
v
k
−
∑
j
=
1
k
−
1
p
r
o
j
u
j
v
k
,
{\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {u} _{j}}\,\mathbf {v} _{k},}
czyli wektor
u
k
{\displaystyle u_{k}}
v
k
{\displaystyle v_{k}}
v
k
{\displaystyle v_{k}}
u
1
,
.
.
.
,
u
k
−
1
.
{\displaystyle u_{1},...,u_{k-1}.}
{
u
1
,
…
,
u
k
}
{\displaystyle \{\mathbf {u} _{1},\dots ,\mathbf {u} _{k}\}}
Aby zbudować w ten sposób zbiór ortonormalny , każdy wektor należy podzielić przez jego normę :
e
n
=
u
n
|
|
u
n
|
|
,
n
=
1
,
2
,
.
.
.
,
k
{\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 [ edytuj | edytuj kod ] Dowód ortogonalności tak otrzymanego układu opiera się na indukcji .
Niech
u
1
,
…
,
u
k
{\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k}}
układem wektorów uzyskanym w procesie ortogonalizacji Grama-Schmidta z bazy
v
1
…
v
k
.
{\displaystyle \mathbf {v} _{1}\dots \mathbf {v} _{k}.}
u
1
,
…
,
u
k
−
1
{\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k-1}}
⟨
u
s
,
u
t
⟩
=
0
{\displaystyle \langle \mathbf {u} _{s},\mathbf {u} _{t}\rangle =0}
t
,
s
∈
{
1
…
k
−
1
}
,
t
≠
s
{\displaystyle t,s\in \{1\dots k-1\},~t\neq s}
u
s
≠
0
{\displaystyle \mathbf {u} _{s}\neq 0}
s
∈
{
1
…
k
−
1
}
.
{\displaystyle s\in \{1\dots k-1\}.}
Pokażemy, że wektor
u
k
{\displaystyle \mathbf {u} _{k}}
u
l
,
{\displaystyle \mathbf {u} _{l},}
l
∈
{
1
,
…
,
k
−
1
}
.
{\displaystyle l\in \{1,\dots ,k-1\}.}
u
k
=
v
k
−
∑
j
=
1
k
−
1
⟨
v
k
,
u
j
⟩
⟨
u
j
,
u
j
⟩
u
j
{\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
u
k
{\displaystyle \mathbf {u} _{k}}
u
l
{\displaystyle \mathbf {u} _{l}}
własności iloczynu skalarnego (rozdzielności iloczynu względem sumy, przemienności i zgodności z mnożeniem przez skalar ) otrzymujemy:
⟨
u
k
,
u
l
⟩
=
⟨
v
k
−
∑
j
=
1
k
−
1
⟨
v
k
,
u
j
⟩
⟨
u
j
,
u
j
⟩
u
j
,
u
l
⟩
=
⟨
v
k
,
u
l
⟩
−
∑
j
=
1
k
−
1
⟨
v
k
,
u
j
⟩
⟨
u
j
,
u
j
⟩
⟨
u
j
,
u
l
⟩
{\displaystyle \langle \mathbf {u} _{k},\mathbf {u} _{l}\rangle =\left\langle \ \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},\mathbf {u} _{l}\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
≠
l
{\displaystyle j\neq l}
⟨
u
k
,
u
l
⟩
=
⟨
v
k
,
u
l
⟩
−
⟨
v
k
,
u
l
⟩
⟨
u
l
,
u
l
⟩
⟨
u
l
,
u
l
⟩
=
0
{\displaystyle \langle \mathbf {u} _{k},\mathbf {u} _{l}\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
u
k
{\displaystyle \mathbf {u} _{k}}
u
1
,
…
,
u
k
−
1
{\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k-1}}
Wektor
u
k
{\displaystyle \mathbf {u} _{k}}
kombinacją liniową wektorów
u
1
,
…
,
u
k
−
1
,
v
k
.
{\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k-1},\mathbf {v} _{k}.}
u
k
−
1
{\displaystyle \mathbf {u} _{k-1}}
u
1
,
…
,
u
k
−
2
,
v
k
−
1
.
{\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k-2},\mathbf {v} _{k-1}.}
u
k
−
2
{\displaystyle \mathbf {u} _{k-2}}
u
k
{\displaystyle \mathbf {u} _{k}}
v
1
,
…
,
v
k
−
1
,
v
k
{\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k-1},\mathbf {v} _{k}}
u
k
=
α
1
v
1
+
…
+
α
k
−
1
v
k
−
1
+
1
⋅
v
k
.
{\displaystyle \mathbf {u} _{k}=\alpha _{1}\mathbf {v} _{1}+\ldots +\alpha _{k-1}\mathbf {v} _{k-1}+1\cdot \mathbf {v} _{k}.}
Gdyby
u
k
=
0
,
{\displaystyle \mathbf {u} _{k}=0,}
v
1
,
…
,
v
k
−
1
,
v
k
{\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k-1},\mathbf {v} _{k}}
Ponieważ ortogonalny układ wektorów jest liniowo niezależny, a każdy z wektorów
u
i
{\displaystyle \mathbf {u} _{i}}
v
1
,
…
,
v
k
,
{\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k},}
u
1
,
…
,
u
k
{\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{k}}
Rozważmy zbiór wektorów w
R
2
{\displaystyle \mathbf {R} ^{2}}
S
=
{
v
1
=
[
3
1
]
,
v
2
=
[
2
2
]
}
.
{\displaystyle S=\left\{\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2\\2\end{bmatrix}}\right\}.}
Teraz przeprowadzamy ortogonalizację, aby otrzymać wektory parami prostopadłe:
u
1
=
v
1
=
[
3
1
]
{\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}}}
u
2
=
v
2
−
p
r
o
j
u
1
(
v
2
)
=
[
2
2
]
−
p
r
o
j
[
3
1
]
(
[
2
2
]
)
=
[
−
2
/
5
6
/
5
]
.
{\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 1 i u 2 rzeczywiście są prostopadłe:
⟨
u
1
,
u
2
⟩
=
⟨
[
3
1
]
,
[
−
2
/
5
6
/
5
]
⟩
=
−
6
5
+
6
5
=
0
,
{\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:
e
1
=
1
10
[
3
1
]
{\displaystyle \mathbf {e} _{1}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3\\1\end{bmatrix}}}
e
2
=
1
40
25
[
−
2
/
5
6
/
5
]
=
1
10
[
−
1
3
]
.
{\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}}.}
W przestrzeni wielomianów
R
[
x
]
{\displaystyle R[x]}
x
k
{\displaystyle x^{k}}
⟨
f
,
g
⟩
w
=
∫
−
1
1
f
(
x
)
g
(
x
)
d
x
f
,
g
∈
R
[
x
]
{\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
1
,
x
,
x
2
,
x
3
,
…
,
{\displaystyle 1,\,x,\,x^{2},\,x^{3},\dots ,}
1
,
x
,
x
2
−
1
3
,
x
3
−
3
5
x
,
…
{\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 :
P
n
(
x
)
=
d
n
d
x
n
(
x
2
−
1
)
n
(
n
=
0
,
1
,
…
)
.
{\displaystyle P_{n}(x)={\frac {d^{n}}{dx^{n}}}(x^{2}-1)^{n}\quad (n=0,1,\dots ).}
Po znormalizowaniu powstanie układ
P
n
~
(
x
)
=
n
+
1
2
⋅
1
(
2
n
)
!
!
P
n
(
x
)
.
{\displaystyle {\tilde {P_{n}}}(x)={\sqrt {n+{\tfrac {1}{2}}}}\cdot {\frac {1}{(2n)!!}}P_{n}(x).}
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.
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a86a735318515e862a6bf4a8fadb42ccce383408)
![{\displaystyle R[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ce54622cb380383ab3a42441b056626ea0d2440)
![{\displaystyle \langle f,g\rangle _{w}=\int \limits _{-1}^{1}f(x)g(x)dx\ \ \ f,g\in R[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ef6fd96672bb37ac4b8d881a4ab2ee9f8534d4c)
