Ortogonalizzazione di Gram-Schmidt

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]

Storia

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.

L'algoritmo

Sia ${\displaystyle V}$ uno spazio vettoriale reale con un prodotto scalare definito positivo. Siano ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}$ vettori linearmente indipendenti in ${\displaystyle V}$. L'algoritmo di Gram-Schmidt restituisce ${\displaystyle n}$ vettori linearmente indipendenti ${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{n}}$ tali che:

${\displaystyle {\mbox{Span}}(\mathbf {v} _{1},\ldots ,\mathbf {v} _{i})={\mbox{Span}}(\mathbf {e} _{1},\ldots ,\mathbf {e} _{i}),\qquad \forall i}$

e

${\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 ${\displaystyle i}$ generano lo stesso sottospazio dei primi ${\displaystyle i}$ vettori iniziali.^[1]

Procedimento

La proiezione ortogonale è la funzione che "proietta" il vettore ${\displaystyle \mathbf {v} }$ in modo ortogonale su ${\displaystyle \mathbf {u} }$:^[2]

${\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 ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{n}}$ a partire da una base generica ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}$. Per calcolare ${\displaystyle \mathbf {u} _{i}}$ si proietta ${\displaystyle \mathbf {v} _{i}}$ ortogonalmente sul sottospazio ${\displaystyle U_{i-1}}$ generato da ${\displaystyle \{\mathbf {u} _{1},\mathbf {u} _{2},\dots ,\mathbf {u} _{i-1}\}}$. Si definisce allora ${\displaystyle \mathbf {u} _{i}}$ come differenza tra ${\displaystyle \mathbf {v} _{i}}$ e questa proiezione, in modo che risulta garantito che esso sia ortogonale a tutti i vettori nel sottospazio ${\displaystyle U_{i-1}}$. Normalizzando poi la base ortogonale (cioè dividendo ogni vettore ${\displaystyle \mathbf {u} _{i}}$ che la compone per la propria norma ${\displaystyle \|\mathbf {u} _{i}\|}$) si ottiene una base ortonormale dello spazio.^[3]

Nello specifico:

I primi due passi dell'algoritmo.

${\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 ${\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 ${\displaystyle \mathbf {u} _{i}}$ e ${\displaystyle \mathbf {e} _{j}}$.

Generalizzazioni

Il processo di Gram-Schmidt si applica anche ad una successione infinita ${\displaystyle \{\mathbf {v} _{i}\}_{i}}$ di vettori linearmente indipendenti. Il risultato è sempre una successione ${\displaystyle \{\mathbf {e} _{i}\}_{i}}$ di vettori ortogonali e con norma unitaria, tale che:

${\displaystyle {\mbox{Span}}(\mathbf {v} _{1},\ldots ,\mathbf {v} _{i})={\mbox{Span}}(\mathbf {e} _{1},\ldots ,\mathbf {e} _{i}),\qquad \forall i.}$

Scrittura per mezzo del determinante

Il risultato del procedimento di Gram-Schmidt può essere espresso in modo non ricorsivo utilizzando il determinante:

${\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}},}$

${\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 ${\displaystyle D_{0}=1}$, e per ${\displaystyle j\geq 1}$ si indica con ${\displaystyle D_{j}}$ il determinante della matrice di Gram:

${\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}}.}$

Esempio

Dati i vettori ${\displaystyle \mathbf {v} _{1}=(3,1)}$ e ${\displaystyle \mathbf {v} _{2}=(2,2)}$ nel piano euclideo ${\displaystyle \mathbb {R} ^{2}}$ munito del prodotto scalare standard, applicando il procedimento di Gram-Schmidt si ha:

${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},}$

${\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 ${\displaystyle \mathbf {u} _{1}}$ e ${\displaystyle \mathbf {u} _{2}}$ che sono ortogonali fra loro, come mostra il loro prodotto scalare:

${\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.}$