Frå Wikipedia – det frie oppslagsverket
Gram–Schmidts ortogonaliseringsprossess er ein algoritme for å generera ein ortonormalisert basis (ortogonal basis med norm 1) frå ei gjeven mengde vektorar knytte til eit indreproduktrom med eit gjeve skalarprodukt
⟨
⋅
,
⋅
⟩
{\displaystyle {\displaystyle \langle \cdot ,\cdot \rangle }}
Metoden vart oppkalla etter Erhard Schmidt og Jørgen Pedersen Gram , sjølv om han tidlegare vart teken i bruk i verka til Laplace og Cauchy .
Han vert nytta i dei høva ein ønskjer ein ortonormal/ortogonal basis. Å finna QR-faktoriseringa av ei matrise er i røynda Gram-Schmidts ortogonaliseringsprossess.
Algoritmen er basert på definisjonen av projeksjonar . Ein projeksjon er definert som;
p
r
o
j
v
x
=
⟨
x
,
v
⟩
⟨
v
,
v
⟩
v
.
{\displaystyle \mathrm {proj} _{\mathbf {v} }\,\mathbf {x} ={\langle \mathbf {x} ,\mathbf {v} \rangle \over \langle \mathbf {v} ,\mathbf {v} \rangle }\mathbf {v} .}
La
v
1
,
.
.
v
n
{\displaystyle v_{1},..v_{n}}
x
1
,
.
.
,
x
n
{\displaystyle x_{1},..,x_{n}}
v
1
=
x
1
{\displaystyle v_{1}=x_{1}}
x
2
{\displaystyle x_{2}}
v
1
{\displaystyle v_{1}}
v
2
{\displaystyle v_{2}}
v
2
=
x
2
−
p
r
o
j
v
1
x
2
=
x
2
−
x
2
⋅
v
1
v
1
⋅
v
1
v
1
{\displaystyle v_{2}=x_{2}-proj_{v_{1}}x_{2}=x_{2}-{\frac {x_{2}\cdot v_{1}}{v_{1}\cdot v_{1}}}v_{1}}
x
3
{\displaystyle x_{3}}
v
1
{\displaystyle v_{1}}
v
2
{\displaystyle v_{2}}
v
3
{\displaystyle v_{3}}
v
3
=
x
3
−
p
r
o
j
v
1
x
3
+
p
r
o
j
v
2
x
3
{\displaystyle v_{3}=x_{3}-proj_{v_{1}}x_{3}+proj_{v_{2}}x_{3}}
Heile algoritmen kan oppsummerast stegvis som
v
1
=
x
1
,
{\displaystyle \mathbf {v} _{1}=\mathbf {x} _{1},}
e
1
=
v
1
|
|
v
1
|
|
{\displaystyle \mathbf {e} _{1}={\mathbf {v} _{1} \over ||\mathbf {v} _{1}||}}
v
2
=
x
2
−
p
r
o
j
v
1
x
2
,
{\displaystyle \mathbf {v} _{2}=\mathbf {x} _{2}-\mathrm {proj} _{\mathbf {v} _{1}}\,\mathbf {x} _{2},}
e
2
=
v
2
|
|
v
2
|
|
{\displaystyle \mathbf {e} _{2}={\mathbf {v} _{2} \over ||\mathbf {v} _{2}||}}
v
3
=
x
3
−
p
r
o
j
v
1
x
3
−
p
r
o
j
v
2
x
3
,
{\displaystyle \mathbf {v} _{3}=\mathbf {x} _{3}-\mathrm {proj} _{\mathbf {v} _{1}}\,\mathbf {x} _{3}-\mathrm {proj} _{\mathbf {v} _{2}}\,\mathbf {x} _{3},}
e
3
=
v
3
|
|
v
3
|
|
{\displaystyle \mathbf {e} _{3}={\mathbf {v} _{3} \over ||\mathbf {v} _{3}||}}
⋮
{\displaystyle \vdots }
⋮
{\displaystyle \vdots }
v
k
=
x
k
−
∑
j
=
1
k
−
1
p
r
o
j
v
j
x
k
,
{\displaystyle \mathbf {v} _{k}=\mathbf {x} _{k}-\sum _{j=1}^{k-1}\mathrm {proj} _{\mathbf {v} _{j}}\,\mathbf {x} _{k},}
e
k
=
v
k
|
|
v
k
|
|
{\displaystyle \mathbf {e} _{k}={\mathbf {v} _{k} \over ||\mathbf {v} _{k}||}}
For kvart steg vert vektoren
v
k
{\displaystyle v_{k}}
