Fra Wikipedia, den frie encyklopædi
Inden for Lineær algebra er Gram-Schmidt-processen en algoritme til at ortonormalisere et endeligt set af lineært uafhængige vektorer inden for et indre produkt-rum , ofte for R n skalarproduktet .
Processen er opkaldt efter den danske matematiker Jørgen Pedersen Gram og tysk-baltiske matematiker Erhard Schmidt , selvom den tidligere har været taget i brug af Laplace .
Gram-Schmidt processen bygger på ortogonale projektioner
p
r
o
j
u
(
v
)
=
⟨
v
,
u
⟩
⟨
u
,
u
⟩
u
,
{\displaystyle \mathrm {proj} _{\mathbf {u} }\,(\mathbf {v} )={\langle \mathbf {v} ,\mathbf {u} \rangle \over \langle \mathbf {u} ,\mathbf {u} \rangle }{\mathbf {u} },}
hvor
⟨
u
,
v
⟩
{\displaystyle \langle \mathbf {u} ,\mathbf {v} \rangle }
Indre produkt af vektorerne u og v . Projektionen projicerer vektoreren v ned på u og skaber da en ny vektor med samme retning sum u, men med den projicerede længde.
Følgende betegner Gram-Schhmidt processen:
u
1
=
v
1
,
e
1
=
u
1
‖
u
1
‖
u
2
=
v
2
−
p
r
o
j
u
1
(
v
2
)
,
e
2
=
u
2
‖
u
2
‖
u
3
=
v
3
−
p
r
o
j
u
1
(
v
3
)
−
p
r
o
j
u
2
(
v
3
)
,
e
3
=
u
3
‖
u
3
‖
u
4
=
v
4
−
p
r
o
j
u
1
(
v
4
)
−
p
r
o
j
u
2
(
v
4
)
−
p
r
o
j
u
3
(
v
4
)
,
e
4
=
u
4
‖
u
4
‖
⋮
⋮
u
k
=
v
k
−
∑
j
=
1
k
−
1
p
r
o
j
u
j
(
v
k
)
,
e
k
=
u
k
‖
u
k
‖
.
{\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {v} _{1},&\mathbf {e} _{1}&={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}\\\mathbf {u} _{2}&=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{2}),&\mathbf {e} _{2}&={\mathbf {u} _{2} \over \|\mathbf {u} _{2}\|}\\\mathbf {u} _{3}&=\mathbf {v} _{3}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{3})-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {v} _{3}),&\mathbf {e} _{3}&={\mathbf {u} _{3} \over \|\mathbf {u} _{3}\|}\\\mathbf {u} _{4}&=\mathbf {v} _{4}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{4})-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {v} _{4})-\mathrm {proj} _{\mathbf {u} _{3}}\,(\mathbf {v} _{4}),&\mathbf {e} _{4}&={\mathbf {u} _{4} \over \|\mathbf {u} _{4}\|}\\&{}\ \ \vdots &&{}\ \ \vdots \\\mathbf {u} _{k}&=\mathbf {v} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {u} _{j}}\,(\mathbf {v} _{k}),&\mathbf {e} _{k}&={\mathbf {u} _{k} \over \|\mathbf {u} _{k}\|}.\end{aligned}}}
hvor vektorerne v 1 ...v k betegner inputtet bestående af lineært uafhængige vektorer og e 1 ...e k de resulterende ortonormaliserede vektorer. Yderligere er vektorerne u 1 ...u k også en ortogonal mængde, men uden garanti for at have længden 1.
Som Eksempel ses på vektorrummet R 4 udstyret med skalarproduktet.
Lad
v
1
=
(
1
1
1
1
)
,
v
2
=
(
1
1
0
0
)
,
v
3
=
(
3
1
1
−
1
)
{\displaystyle \mathbf {v} _{1}={\begin{pmatrix}1\\1\\1\\1\end{pmatrix}},\mathbf {v} _{2}={\begin{pmatrix}1\\1\\0\\0\end{pmatrix}},\mathbf {v} _{3}={\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}}
Det er givet at v 1 , v 2 og v 3 er lineært uafhængige.
Gram-Schmidt udføres:
u
1
=
v
1
=
(
1
1
1
1
)
{\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1}={\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}}
u
2
=
v
2
−
p
r
o
j
u
1
(
v
2
)
=
(
1
1
0
0
)
−
p
r
o
j
(
1
1
1
1
)
(
1
1
0
0
)
=
(
1
1
0
0
)
−
1
2
(
1
1
1
1
)
=
(
1
/
2
1
/
2
−
1
/
2
−
1
/
2
)
{\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{2})={\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}-\mathrm {proj} _{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}\,{\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}={\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}-{1 \over 2}{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix}}}
u
3
=
v
3
−
p
r
o
j
u
1
(
v
3
)
−
p
r
o
j
u
2
(
v
3
)
=
(
3
1
1
−
1
)
−
p
r
o
j
(
1
1
1
1
)
(
3
1
1
−
1
)
−
p
r
o
j
(
1
1
0
0
)
(
3
1
1
−
1
)
=
(
3
1
1
−
1
)
−
(
1
1
1
1
)
−
2
(
1
/
2
1
/
2
−
1
/
2
−
1
/
2
)
=
(
1
−
1
1
−
1
)
{\displaystyle \mathbf {u} _{3}=\mathbf {v} _{3}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{3})-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {v} _{3})={\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}-\mathrm {proj} _{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}\,{\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}-\mathrm {proj} _{\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}\,{\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}={\begin{pmatrix}3\\1\\1\\-1\end{pmatrix}}-{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}-2{\begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix}}={\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}}}
Det kan tjekkes om vektorerne er ortogonale ved at beregne de indbyrdes skalarprodukter. Eksempelvis u 1 og u 3 :
⟨
u
1
,
u
3
⟩
=
⟨
(
1
1
1
1
)
,
(
1
−
1
1
−
1
)
⟩
=
1
−
1
+
1
−
1
=
0
,
{\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle =\left\langle {\begin{pmatrix}1\\1\\1\\1\end{pmatrix}},{\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}}\right\rangle =1-1+1-1=0,}
Vektorerne er ortogonale da deres indre produkt er 0.
For at finde de normaliserede vektorer e 1 , e 2 og e 3 gøres følgende:
e
1
=
u
1
‖
u
1
‖
=
1
2
(
1
1
1
1
)
=
(
1
/
2
1
/
2
1
/
2
1
/
2
)
{\displaystyle \mathbf {e} _{1}={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}={1 \over 2}{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}1/2\\1/2\\1/2\\1/2\end{pmatrix}}}
e
2
=
u
2
‖
u
2
‖
=
(
1
/
2
1
/
2
−
1
/
2
−
1
/
2
)
{\displaystyle \mathbf {e} _{2}={\mathbf {u} _{2} \over \|\mathbf {u} _{2}\|}={\begin{pmatrix}1/2\\1/2\\-1/2\\-1/2\end{pmatrix}}}
e
3
=
u
3
‖
u
3
‖
=
1
2
(
1
−
1
1
−
1
)
{\displaystyle \mathbf {e} _{3}={\mathbf {u} _{3} \over \|\mathbf {u} _{3}\|}={1 \over 2}{\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}}}
