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 ${𝐯}_1,\dots ,{𝐯}_n$ vettori linearmente indipendenti in $V$. L'algoritmo di Gram-Schmidt restituisce $n$ vettori linearmente indipendenti ${𝐞}_1,\dots ,{𝐞}_n$ tali che:

$\text{Span}({𝐯}_1,\dots ,{𝐯}_i)=\text{Span}({𝐞}_1,\dots ,{𝐞}_i),\mathrm{\forall }i$

e

$⟨{𝐞}_i,{𝐞}_j⟩=\{\begin{array}{cc}1& i=j,\\ 0& i\ne j,\end{array}\Vert e_i\Vert =1,\mathrm{\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 $𝐯$ in modo ortogonale su $𝐮$:

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐮}(𝐯)=\frac{⟨𝐯,𝐮⟩}{⟨𝐮,𝐮⟩}𝐮.$

Il procedimento di Gram–Schmidt permette di costruire una base ortogonale ${𝐮}_1,\dots ,{𝐮}_n$ a partire da una base generica ${𝐯}_1,\dots ,{𝐯}_n$. Per calcolare ${𝐮}_i$ si proietta ${𝐯}_i$ ortogonalmente sul sottospazio $U_{i-1}$ generato da $\{{𝐮}_1,{𝐮}_2,\dots ,{𝐮}_{i-1}\}$. Si definisce allora ${𝐮}_i$ come differenza tra ${𝐯}_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 ${𝐮}_i$ che la compone per la propria norma $\Vert {𝐮}_i\Vert$) si ottiene una base ortonormale dello spazio.

Nello specifico:

I primi due passi dell'algoritmo.

$\begin{array}{cccc}{𝐮}_1& ={𝐯}_1,& {𝐞}_1& =\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }\\ {𝐮}_2& ={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_2),& {𝐞}_2& =\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }\\ {𝐮}_3& ={𝐯}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_3)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_3),& {𝐞}_3& =\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\\ {𝐮}_4& ={𝐯}_4-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_4)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_4)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_3}({𝐯}_4),& {𝐞}_4& =\frac{{𝐮}_4}{\Vert {𝐮}_4\Vert }\\ & ⋮& & ⋮\\ {𝐮}_k& ={𝐯}_k-\sum _{j=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_j}({𝐯}_k),& {𝐞}_k& =\frac{{𝐮}_k}{\Vert {𝐮}_k\Vert }.\end{array}$

dove $\{{𝐞}_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 ${𝐮}_i$ e ${𝐞}_j$.

Generalizzazioni

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

$\text{Span}({𝐯}_1,\dots ,{𝐯}_i)=\text{Span}({𝐞}_1,\dots ,{𝐞}_i),\mathrm{\forall }i.$

Scrittura per mezzo del determinante

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

${𝐞}_j=\frac{1}{\sqrt{D_{j-1}{D}_j}}\left|\begin{array}{cccc}⟨{𝐯}_1,{𝐯}_1⟩& ⟨{𝐯}_2,{𝐯}_1⟩& \dots & ⟨{𝐯}_j,{𝐯}_1⟩\\ ⟨{𝐯}_1,{𝐯}_2⟩& ⟨{𝐯}_2,{𝐯}_2⟩& \dots & ⟨{𝐯}_j,{𝐯}_2⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{𝐯}_1,{𝐯}_{j-1}⟩& ⟨{𝐯}_2,{𝐯}_{j-1}⟩& \dots & ⟨{𝐯}_j,{𝐯}_{j-1}⟩\\ {𝐯}_1& {𝐯}_2& \dots & {𝐯}_j\end{array}\right|,$

${𝐮}_j=\frac{1}{D_{j-1}}\left|\begin{array}{cccc}⟨{𝐯}_1,{𝐯}_1⟩& ⟨{𝐯}_2,{𝐯}_1⟩& \cdots & ⟨{𝐯}_j,{𝐯}_1⟩\\ ⟨{𝐯}_1,{𝐯}_2⟩& ⟨{𝐯}_2,{𝐯}_2⟩& \cdots & ⟨{𝐯}_j,{𝐯}_2⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{𝐯}_1,{𝐯}_{j-1}⟩& ⟨{𝐯}_2,{𝐯}_{j-1}⟩& \cdots & ⟨{𝐯}_j,{𝐯}_{j-1}⟩\\ {𝐯}_1& {𝐯}_2& \cdots & {𝐯}_j\end{array}\right|,$

dove $D_0=1$, e per $j\ge 1$ si indica con $D_j$ il determinante della matrice di Gram:

$D_j=\left|\begin{array}{cccc}⟨{𝐯}_1,{𝐯}_1⟩& ⟨{𝐯}_2,{𝐯}_1⟩& \dots & ⟨{𝐯}_j,{𝐯}_1⟩\\ ⟨{𝐯}_1,{𝐯}_2⟩& ⟨{𝐯}_2,{𝐯}_2⟩& \dots & ⟨{𝐯}_j,{𝐯}_2⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{𝐯}_1,{𝐯}_j⟩& ⟨{𝐯}_2,{𝐯}_j⟩& \dots & ⟨{𝐯}_j,{𝐯}_j⟩\end{array}\right|.$

Esempio

Dati i vettori ${𝐯}_1=(3,1)$ e ${𝐯}_2=(2,2)$ nel piano euclideo ${ℝ}^2$ munito del prodotto scalare standard, applicando il procedimento di Gram-Schmidt si ha:

${𝐮}_1={𝐯}_1,$

${𝐮}_2={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_2)=(2,2)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{(3,1)}(2,2)=(-2/5,6/5),$

ottenendo i vettori ${𝐮}_1$ e ${𝐮}_2$ che sono ortogonali fra loro, come mostra il loro prodotto scalare:

$⟨{𝐮}_1,{𝐮}_2⟩=⟨(3,1),(-2/5,6/5)⟩=-\frac{6}{5}+\frac{6}{5}=0.$

Bibliografia

• Template:Cita libro
• Template:EnTemplate:Cita libro
• Template:En F.R. Gantmacher, The theory of matrices , 1 , Chelsea, reprint (1977)
• Template:En A.G. Kurosh, Higher algebra , MIR (1972)

Voci correlate

• Algoritmo di Lagrange
• Prodotto scalare
• Teorema di Sylvester
• Teorema spettrale

Collegamenti esterni

• Template:Collegamenti esterni
• Template:Cita web
• Template:Cita web
• Template:Cita web
• Template:Cita web
• Template:En Proof: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.
• Template:Cita web
• Template:Cita web