In matematica , e in particolare in algebra lineare , l'ortogonalizzazione Gram-Schmidt è un algoritmo che permette di ottenere un insieme di vettori ortogonali a partire da un generico insieme di vettori linearmente indipendenti in uno spazio vettoriale dotato di un prodotto scalare definito positivo .[1]
Il procedimento è così chiamato in onore del matematico danese Jørgen Pedersen Gram (1850-1916) e del matematico tedesco Erhard Schmidt (1876-1959); esso però è stato introdotto precedentemente ai loro studi e si trova in lavori di Laplace e Cauchy .
Quando si implementa l'ortogonalizzazione su un computer , al processo di Gram-Schmidt di solito si preferisce la trasformazione di Householder , in quanto questa è numericamente più stabile, cioè gli errori causati dall'arrotondamento sono minori.
Sia
V
{\displaystyle V}
spazio vettoriale reale con un prodotto scalare definito positivo . Siano
v
1
,
…
,
v
n
{\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}
V
{\displaystyle V}
n
{\displaystyle n}
linearmente indipendenti
e
1
,
…
,
e
n
{\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{n}}
Span
(
v
1
,
…
,
v
i
)
=
Span
(
e
1
,
…
,
e
i
)
,
∀
i
{\displaystyle {\mbox{Span}}(\mathbf {v} _{1},\ldots ,\mathbf {v} _{i})={\mbox{Span}}(\mathbf {e} _{1},\ldots ,\mathbf {e} _{i}),\qquad \forall i}
e
⟨
e
i
,
e
j
⟩
=
{
1
i
=
j
,
0
i
≠
j
,
‖
e
i
‖
=
1
,
∀
i
{\displaystyle \langle \mathbf {e} _{i},\mathbf {e} _{j}\rangle ={\begin{cases}1&i=j,\\0&i\neq j,\end{cases}}\qquad \|{e_{i}}\|=1,\qquad \forall i}
In altre parole, i vettori restituiti sono ortonormali , ed i primi
i
{\displaystyle i}
generano lo stesso sottospazio dei primi
i
{\displaystyle i}
[1]
La proiezione ortogonale è la funzione che "proietta" il vettore
v
{\displaystyle \mathbf {v} }
u
{\displaystyle \mathbf {u} }
[2]
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} .}
Il procedimento di Gram–Schmidt permette di costruire una base ortogonale
u
1
,
…
,
u
n
{\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{n}}
v
1
,
…
,
v
n
{\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}
u
i
{\displaystyle \mathbf {u} _{i}}
v
i
{\displaystyle \mathbf {v} _{i}}
U
i
−
1
{\displaystyle U_{i-1}}
{
u
1
,
u
2
,
…
,
u
i
−
1
}
{\displaystyle \{\mathbf {u} _{1},\mathbf {u} _{2},\dots ,\mathbf {u} _{i-1}\}}
u
i
{\displaystyle \mathbf {u} _{i}}
v
i
{\displaystyle \mathbf {v} _{i}}
U
i
−
1
{\displaystyle U_{i-1}}
u
i
{\displaystyle \mathbf {u} _{i}}
norma
‖
u
i
‖
{\displaystyle \|\mathbf {u} _{i}\|}
base ortonormale dello spazio.[3]
Nello specifico:
I primi due passi dell'algoritmo.
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}}}
dove
{
e
i
}
{\displaystyle \{\mathbf {e} _{i}\}}
Una verifica immediata della correttezza del procedimento eseguito, ovvero che si è ottenuto un insieme di vettori mutuamente ortogonali, è il calcolo del prodotto scalare fra
u
i
{\displaystyle \mathbf {u} _{i}}
e
j
{\displaystyle \mathbf {e} _{j}}
Il processo di Gram-Schmidt si applica anche ad una successione infinita
{
v
i
}
i
{\displaystyle \{\mathbf {v} _{i}\}_{i}}
{
e
i
}
i
{\displaystyle \{\mathbf {e} _{i}\}_{i}}
Span
(
v
1
,
…
,
v
i
)
=
Span
(
e
1
,
…
,
e
i
)
,
∀
i
.
{\displaystyle {\mbox{Span}}(\mathbf {v} _{1},\ldots ,\mathbf {v} _{i})={\mbox{Span}}(\mathbf {e} _{1},\ldots ,\mathbf {e} _{i}),\qquad \forall i.}
Il risultato del procedimento di Gram-Schmidt può essere espresso in modo non ricorsivo utilizzando il determinante :
e
j
=
1
D
j
−
1
D
j
|
⟨
v
1
,
v
1
⟩
⟨
v
2
,
v
1
⟩
…
⟨
v
j
,
v
1
⟩
⟨
v
1
,
v
2
⟩
⟨
v
2
,
v
2
⟩
…
⟨
v
j
,
v
2
⟩
⋮
⋮
⋱
⋮
⟨
v
1
,
v
j
−
1
⟩
⟨
v
2
,
v
j
−
1
⟩
…
⟨
v
j
,
v
j
−
1
⟩
v
1
v
2
…
v
j
|
,
{\displaystyle \mathbf {e} _{j}={\frac {1}{\sqrt {D_{j-1}D_{j}}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\dots &\mathbf {v} _{j}\end{vmatrix}},}
u
j
=
1
D
j
−
1
|
⟨
v
1
,
v
1
⟩
⟨
v
2
,
v
1
⟩
⋯
⟨
v
j
,
v
1
⟩
⟨
v
1
,
v
2
⟩
⟨
v
2
,
v
2
⟩
⋯
⟨
v
j
,
v
2
⟩
⋮
⋮
⋱
⋮
⟨
v
1
,
v
j
−
1
⟩
⟨
v
2
,
v
j
−
1
⟩
⋯
⟨
v
j
,
v
j
−
1
⟩
v
1
v
2
⋯
v
j
|
,
{\displaystyle {\displaystyle \mathbf {u} _{j}={\frac {1}{D_{j-1}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j-1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j-1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}},}
dove
D
0
=
1
{\displaystyle D_{0}=1}
j
≥
1
{\displaystyle j\geq 1}
D
j
{\displaystyle D_{j}}
matrice di Gram :
D
j
=
|
⟨
v
1
,
v
1
⟩
⟨
v
2
,
v
1
⟩
…
⟨
v
j
,
v
1
⟩
⟨
v
1
,
v
2
⟩
⟨
v
2
,
v
2
⟩
…
⟨
v
j
,
v
2
⟩
⋮
⋮
⋱
⋮
⟨
v
1
,
v
j
⟩
⟨
v
2
,
v
j
⟩
…
⟨
v
j
,
v
j
⟩
|
.
{\displaystyle D_{j}={\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{2}\rangle \\\vdots &\vdots &\ddots &\vdots \\\langle \mathbf {v} _{1},\mathbf {v} _{j}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{j}\rangle &\dots &\langle \mathbf {v} _{j},\mathbf {v} _{j}\rangle \end{vmatrix}}.}
Dati i vettori
v
1
=
(
3
,
1
)
{\displaystyle \mathbf {v} _{1}=(3,1)}
v
2
=
(
2
,
2
)
{\displaystyle \mathbf {v} _{2}=(2,2)}
piano euclideo
R
2
{\displaystyle \mathbb {R} ^{2}}
prodotto scalare standard, applicando il procedimento di Gram-Schmidt si ha:
u
1
=
v
1
,
{\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},}
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})=(2,2)-\mathrm {proj} _{(3,1)}\,{(2,2)}=(-2/5,6/5),}
ottenendo i vettori
u
1
{\displaystyle \mathbf {u} _{1}}
u
2
{\displaystyle \mathbf {u} _{2}}
⟨
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 (3,1),(-2/5,6/5)\right\rangle =-{\frac {6}{5}}+{\frac {6}{5}}=0.}
Serge Lang, Algebra lineare , Torino, Bollati Boringhieri, 1992, ISBN 88-339-5035-2 . (EN Kenneth Hoffman, Ray Kunze, Linear Algebra ISBN 0-13-536821-9 .
(EN The theory of matrices , 1 , Chelsea, reprint (1977)
(EN Higher algebra , MIR (1972) (EN Ortogonalizzazione di Gram-Schmidt MathWorld (EN Ortogonalizzazione di Gram-Schmidt Encyclopaedia of Mathematics (EN Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm PDF math.hmc.edu . URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 2 aprile 2016) . (EN Earliest known uses of some of the words of mathematics: G jeff560.tripod.com . (EN Gram-Schmidt orthogonalization applet math.ucla.edu . (EN NAG Gram–Schmidt orthogonalization of n vectors of order m routine nag.co.uk . (EN Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.
(EN Gram Schmidt process in plane bigsigma.com . URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 7 maggio 2009) . (EN Gram Schmidt process in space bigsigma.com . URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 7 maggio 2009) . 
