Процес Грама - Шмідта — найвідоміший алгоритм ортогоналізації , в якому за лінійно-незалежною системою
v
1
,
v
2
,
…
,
v
k
{\displaystyle \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{k}}
ортогональна система
u
1
,
u
2
,
…
,
u
k
{\displaystyle \mathbf {u} _{1},\mathbf {u} _{2},\dots ,\mathbf {u} _{k}}
u
i
{\displaystyle \mathbf {u} _{i}}
v
1
,
v
2
,
…
,
v
i
{\displaystyle \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{i}}
матриця переходу від
{
v
i
}
{\displaystyle \{\mathbf {v} _{i}\}}
{
u
i
}
{\displaystyle \{\mathbf {u} _{i}\}}
верхня трикутна матриця .
Процес ортогоналізації Грама — Шмідта на трьох лінійно незалежних, неортогональних векторах Можна пронормувати систему
{
u
i
}
{\displaystyle \{\mathbf {u} _{i}\}}
{
u
i
}
{\displaystyle \{\mathbf {u} _{i}\}}
Процес Грама — Шмідта застосований до матриці з лінійно-незалежними стовпцями є QR розкладом матриці (розклад на ортогональну і верхню трикутну матрицю з додатніми діагональними елементами).
Алгоритм
ред.
Перші 2 кроки ортогоналізації Визначимо ортогонально-проєкційний оператор
p
r
o
j
u
v
=
⟨
u
,
v
⟩
⟨
u
,
u
⟩
u
=
u
u
⊤
⟨
u
,
u
⟩
⋅
v
=
e
e
⊤
⋅
v
,
e
=
u
‖
u
‖
,
{\displaystyle \mathrm {proj} _{\mathbf {u} }\,\mathbf {v} ={\langle \mathbf {u,v} \rangle \over \langle \mathbf {u,u} \rangle }\mathbf {u} ={\mathbf {uu^{\top }} \over \langle \mathbf {u,u} \rangle }\cdot \mathbf {v} =\mathbf {ee^{\top }} \cdot \mathbf {v} ,\qquad \mathbf {e} ={\mathbf {u} \over \|\mathbf {u} \|},}
де <u , v > означає скалярний добуток векторів u and v . Цей оператор проектує вектор v ортогонально на вектор u .
Приймемо
u
1
=
v
1
{\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1}}
u
i
=
v
i
−
∑
j
=
1
i
−
1
⟨
v
i
,
u
j
⟩
⟨
u
j
,
u
j
⟩
u
j
=
v
i
−
(
∑
j
=
1
i
−
1
e
j
e
j
⊤
)
v
i
.
{\displaystyle \mathbf {u} _{i}=\mathbf {v} _{i}-\sum _{j=1}^{i-1}{\frac {\langle \mathbf {v} _{i},\mathbf {u} _{j}\rangle }{\langle \mathbf {u} _{j},\mathbf {u} _{j}\rangle }}\mathbf {u} _{j}=\mathbf {v} _{i}-{\bigg (}\sum _{j=1}^{i-1}\mathbf {e} _{j}\mathbf {e} _{j}^{\top }{\bigg )}\mathbf {v} _{i}.}
Нормуючи вектори
u
i
{\displaystyle \mathbf {u} _{i}}
{
e
i
}
{\displaystyle \{\mathbf {e} _{i}\}}
Геометричний зміст процесу в тому, що вектор
u
i
{\displaystyle \mathbf {u} _{i}}
v
i
{\displaystyle \mathbf {v} _{i}}
лінійної оболонки векторів
v
1
,
…
,
v
i
−
1
.
{\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{i-1}.}
Властивості
ред.
Для кожного
i
{\displaystyle \ i}
v
1
,
…
,
v
i
{\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{i}}
u
1
,
…
,
u
i
{\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{i}}
Добуток довжин
u
i
{\displaystyle \mathbf {u} _{i}}
паралелепіпеда , побудованого на векторах системи
{
v
i
}
{\displaystyle \{\mathbf {v} _{i}\}}
Числова стійкість
ред.
Коли процес втілено на комп'ютері, вектори
u
k
{\displaystyle \mathbf {u} _{k}}
Процес Грама — Шмідта можна стабілізувати завдяки маленькій зміні; цю версію іноді згадують як модифікований Грам — Шмідт .
Цей підхід дає той самий результат що й оригінальна формула в точній арифметиці і вводить менші похибки в арифметиці скінченної точності.
Замість того, щоб обчислювати вектор u k
u
k
=
v
k
−
p
r
o
j
u
1
(
v
k
)
−
p
r
o
j
u
2
(
v
k
)
−
⋯
−
p
r
o
j
u
k
−
1
(
v
k
)
,
{\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{k})-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {v} _{k})-\cdots -\mathrm {proj} _{\mathbf {u} _{k-1}}\,(\mathbf {v} _{k}),}
його обчислюють як
u
k
(
1
)
=
v
k
−
p
r
o
j
u
1
(
v
k
)
,
u
k
(
2
)
=
u
k
(
1
)
−
p
r
o
j
u
2
(
u
k
(
1
)
)
,
⋮
u
k
(
k
−
2
)
=
u
k
(
k
−
3
)
−
p
r
o
j
u
k
−
2
(
u
k
(
k
−
3
)
)
,
u
k
(
k
−
1
)
=
u
k
(
k
−
2
)
−
p
r
o
j
u
k
−
1
(
u
k
(
k
−
2
)
)
.
{\displaystyle {\begin{aligned}\mathbf {u} _{k}^{(1)}&=\mathbf {v} _{k}-\mathrm {proj} _{\mathbf {u} _{1}}\,(\mathbf {v} _{k}),\\\mathbf {u} _{k}^{(2)}&=\mathbf {u} _{k}^{(1)}-\mathrm {proj} _{\mathbf {u} _{2}}\,(\mathbf {u} _{k}^{(1)}),\\&\,\,\,\vdots \\\mathbf {u} _{k}^{(k-2)}&=\mathbf {u} _{k}^{(k-3)}-\mathrm {proj} _{\mathbf {u} _{k-2}}\,(\mathbf {u} _{k}^{(k-3)}),\\\mathbf {u} _{k}^{(k-1)}&=\mathbf {u} _{k}^{(k-2)}-\mathrm {proj} _{\mathbf {u} _{k-1}}\,(\mathbf {u} _{k}^{(k-2)}).\end{aligned}}}
Кожен крок знаходить вектор
u
k
(
i
)
{\displaystyle \mathbf {u} _{k}^{(i)}}
u
k
(
i
−
1
)
{\displaystyle \mathbf {u} _{k}^{(i-1)}}
u
k
(
i
)
{\displaystyle \mathbf {u} _{k}^{(i)}}
u
k
(
i
−
1
)
{\displaystyle \mathbf {u} _{k}^{(i-1)}}
