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}
uno spazio vettoriale reale con un prodotto scalare definito positivo . Siano
v
1
,
…
,
v
n
{\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}
vettori linearmente indipendenti in
V
{\displaystyle V}
. L'algoritmo di Gram-Schmidt restituisce
n
{\displaystyle n}
vettori linearmente indipendenti
e
1
,
…
,
e
n
{\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{n}}
tali che:
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}
vettori iniziali.[ 1]
La proiezione ortogonale è la funzione che "proietta" il vettore
v
{\displaystyle \mathbf {v} }
in modo ortogonale su
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}}
a partire da una base generica
v
1
,
…
,
v
n
{\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}
. Per calcolare
u
i
{\displaystyle \mathbf {u} _{i}}
si proietta
v
i
{\displaystyle \mathbf {v} _{i}}
ortogonalmente sul sottospazio
U
i
−
1
{\displaystyle U_{i-1}}
generato da
{
u
1
,
u
2
,
…
,
u
i
−
1
}
{\displaystyle \{\mathbf {u} _{1},\mathbf {u} _{2},\dots ,\mathbf {u} _{i-1}\}}
. Si definisce allora
u
i
{\displaystyle \mathbf {u} _{i}}
come differenza tra
v
i
{\displaystyle \mathbf {v} _{i}}
e questa proiezione, in modo che risulta garantito che esso sia ortogonale a tutti i vettori nel sottospazio
U
i
−
1
{\displaystyle U_{i-1}}
. Normalizzando poi la base ortogonale (cioè dividendo ogni vettore
u
i
{\displaystyle \mathbf {u} _{i}}
che la compone per la propria norma
‖
u
i
‖
{\displaystyle \|\mathbf {u} _{i}\|}
) si ottiene una 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}\}}
è la base normalizzata.
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
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}}
di vettori linearmente indipendenti. Il risultato è sempre una successione
{
e
i
}
i
{\displaystyle \{\mathbf {e} _{i}\}_{i}}
di vettori ortogonali e con norma unitaria, tale che:
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}
, e per
j
≥
1
{\displaystyle j\geq 1}
si indica con
D
j
{\displaystyle D_{j}}
il determinante della 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)}
e
v
2
=
(
2
,
2
)
{\displaystyle \mathbf {v} _{2}=(2,2)}
nel piano euclideo
R
2
{\displaystyle \mathbb {R} ^{2}}
munito del 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}}
e
u
2
{\displaystyle \mathbf {u} _{2}}
che sono ortogonali fra loro, come mostra il loro prodotto scalare:
⟨
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 , 2ª ed., Englewood Cliffs, New Jersey, Prentice - Hall, inc., 1971, ISBN 0-13-536821-9 .
(EN ) F.R. Gantmacher, The theory of matrices , 1 , Chelsea, reprint (1977)
(EN ) A.G. Kurosh, Higher algebra , MIR (1972)
(EN ) Eric W. Weisstein, Ortogonalizzazione di Gram-Schmidt , su MathWorld , Wolfram Research.
(EN ) Ortogonalizzazione di Gram-Schmidt , su Encyclopaedia of Mathematics , Springer e European Mathematical Society.
(EN ) Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm (PDF ), su 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 , su jeff560.tripod.com .
(EN ) Gram-Schmidt orthogonalization applet , su math.ucla.edu .
(EN ) NAG Gram–Schmidt orthogonalization of n vectors of order m routine , su nag.co.uk .
(EN ) Proof: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.
(EN ) Gram Schmidt process in plane , su bigsigma.com . URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 7 maggio 2009) .
(EN ) Gram Schmidt process in space , su bigsigma.com . URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 7 maggio 2009) .