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.

L'algoritmo

Sia V uno spazio vettoriale reale con un prodotto scalare definito positivo. Siano

$\mathbf{v}_1,\ldots, \mathbf{v}_n$

dei vettori 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)\ \quad \forall i \qquad \langle \mathbf{e}_i,\mathbf{e}_j \rangle = 0 \ \mbox{se}\ i\neq j,\ 1\ \mbox{se}\ i=j$

In altre parole, i vettori restituiti sono ortonormali, ed i primi i generano lo stesso sottospazio di prima.

Procedimento

Per approfondire, vedi Proiezione (geometria).

Definiamo la proiezione ortogonale come la funzione che proietta il vettore v in modo ortogonale su 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$. Normalizzando quindi la base ortogonale si ottiene una base ortonormale dello spazio.

Il procedimento è il seguente:

I primi due passi dell'algoritmo.

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

Dimostrazione

Per verificare che queste formule producono una sequenza di vettori mutuamente ortogonali, per prima cosa calcoliamo il prodotto scalare fra e₁ e e₂ sostituendo la precedente espressione per u₂: troveremo zero. Successivamente teniamo conto di questo fatto per calcolare il prodotto scalare fra e₁ ed e₃, ora sostituendo u₃ con la relativa espressione: troveremo ancora zero. La dimostrazione generale procede per induzione.

Geometricamente, questo metodo viene descritto come segue. Per calcolare u_i, si proietta v_i ortogonalmente sul sottospazio U_i-1 generato da u₁,...,u_i-1, che è lo stesso del sottospazio generato da v₁,...,v_i-1. si definisce allora u_i come differenza tra v_i e questa proiezione, in modo che risulta garantito che esso sia ortogonale a tutti i vettori nel sottospazio U_i-1.

Poiché però vogliamo dei vettori di norma uno, ad ogni passo normalizziamo il vettore u_i.

Generalizzazioni

Il processo di Gram-Schmidt si applica anche ad una successione infinita {v_i}_i di vettori linearmente indipendenti. Il risultato è sempre una successione {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)\ \forall i.$

Uso del determinante

Il risultato del procedimento di Gram–Schmidt può essere espresso in modo non ricorsivo utilizzando la seguente formula:

$\mathbf{u}_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}$

dove D ₀=1, e per j ≥ 1 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}.$

L'espressione per u_k è un determinante "formale", ovvero la matrice contiene sia scalari che vettori.

Esempio

Consideriamo i vettori seguenti nel piano euclideo R², con il prodotto scalare standard.

$\mathbf{v}_1=(3,1), \ \mathbf{v}_2=(2,2).$

Applichiamo il procedimento di Gram-Schmidt per ottenere vettori ortogonali:

$\mathbf{u}_1=\mathbf{v}_1,\qquad\mathbf{e}_1=1/\sqrt{10}(3, 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)$

Verifichiamo che i vettori u₁ e u₂ sono effettivamente ortogonali:

$\langle\mathbf{u}_1,\mathbf{u}_2\rangle = \left\langle (3,1), (-2/5,6/5) \right\rangle = -\frac65 + \frac65 = 0.$

Cenni storici

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.

Bibliografia

• Serge Lang, Algebra lineare, Torino, Bollati Boringhieri, 1992. ISBN 88-339-5035-2
• Kenneth Hoffman; Ray Kunze, Linear Algebra, 2^a ed., Englewood Cliffs, New Jersey, Prentice - Hall, inc., 1971. ISBN 01-353-6821-9

Voci correlate

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica