Ortogonalizzazione di Gram-Schmidt
# 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.

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

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

e:

    $\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$ generano lo stesso sottospazio dei primi $i$ vettori iniziali.

### Procedimento

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

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

Nello specifico:

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

### Generalizzazioni

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

    ${\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:

    $\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 \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$, e per $j\geq 1$ la matrice $D_{j}$ è la matrice di Gram:

    $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 $\mathbf {v} _{1}=(3,1)$ e $\mathbf {v} _{2}=(2,2)$ nel piano euclideo $\mathbb {R} ^{2}$ munito del prodotto scalare standard, applicando il procedimento di Gram-Schmidt si ha:

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

    $\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$
