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:

Span (𝐯_{1}, \dots, 𝐯_{i}) = Span (𝐞_{1}, \dots, 𝐞_{i}), \forall i

e

⟨ 𝐞_{i}, 𝐞_{j} ⟩ = {\begin{matrix} 1 & i = j, \\ 0 & i \neq j, \end{matrix} ‖ e_{i} ‖ = 1, \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 $𝐮$ :

{p r o 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 $‖ 𝐮_{i} ‖$ ) si ottiene una base ortonormale dello spazio.

Nello specifico:

\begin{matrix} 𝐮_{1} & = 𝐯_{1}, & 𝐞_{1} & = \frac{𝐮_{1}}{‖ 𝐮_{1} ‖} \\ 𝐮_{2} & = 𝐯_{2} - {p r o j}_{𝐮_{1}} (𝐯_{2}), & 𝐞_{2} & = \frac{𝐮_{2}}{‖ 𝐮_{2} ‖} \\ 𝐮_{3} & = 𝐯_{3} - {p r o j}_{𝐮_{1}} (𝐯_{3}) - {p r o j}_{𝐮_{2}} (𝐯_{3}), & 𝐞_{3} & = \frac{𝐮_{3}}{‖ 𝐮_{3} ‖} \\ 𝐮_{4} & = 𝐯_{4} - {p r o j}_{𝐮_{1}} (𝐯_{4}) - {p r o j}_{𝐮_{2}} (𝐯_{4}) - {p r o j}_{𝐮_{3}} (𝐯_{4}), & 𝐞_{4} & = \frac{𝐮_{4}}{‖ 𝐮_{4} ‖} \\ ⋮ & ⋮ \\ 𝐮_{k} & = 𝐯_{k} - \sum_{j = 1}^{k - 1} {p r o j}_{𝐮_{j}} (𝐯_{k}), & 𝐞_{k} & = \frac{𝐮_{k}}{‖ 𝐮_{k} ‖} . \end{matrix}

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:

Span (𝐯_{1}, \dots, 𝐯_{i}) = Span (𝐞_{1}, \dots, 𝐞_{i}), \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}}} | \begin{matrix} ⟨ 𝐯_{1}, 𝐯_{1} ⟩ & ⟨ 𝐯_{2}, 𝐯_{1} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{1} ⟩ \\ ⟨ 𝐯_{1}, 𝐯_{2} ⟩ & ⟨ 𝐯_{2}, 𝐯_{2} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{2} ⟩ \\ ⋮ & ⋮ & ⋱ & ⋮ \\ ⟨ 𝐯_{1}, 𝐯_{j - 1} ⟩ & ⟨ 𝐯_{2}, 𝐯_{j - 1} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{j - 1} ⟩ \\ 𝐯_{1} & 𝐯_{2} & \dots & 𝐯_{j} \end{matrix} |,

𝐮_{j} = \frac{1}{D_{j - 1}} | \begin{matrix} ⟨ 𝐯_{1}, 𝐯_{1} ⟩ & ⟨ 𝐯_{2}, 𝐯_{1} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{1} ⟩ \\ ⟨ 𝐯_{1}, 𝐯_{2} ⟩ & ⟨ 𝐯_{2}, 𝐯_{2} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{2} ⟩ \\ ⋮ & ⋮ & ⋱ & ⋮ \\ ⟨ 𝐯_{1}, 𝐯_{j - 1} ⟩ & ⟨ 𝐯_{2}, 𝐯_{j - 1} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{j - 1} ⟩ \\ 𝐯_{1} & 𝐯_{2} & \dots & 𝐯_{j} \end{matrix} |,

dove $D_{0} = 1$ , e per $j \geq 1$ si indica con $D_{j}$ il determinante della matrice di Gram:

D_{j} = | \begin{matrix} ⟨ 𝐯_{1}, 𝐯_{1} ⟩ & ⟨ 𝐯_{2}, 𝐯_{1} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{1} ⟩ \\ ⟨ 𝐯_{1}, 𝐯_{2} ⟩ & ⟨ 𝐯_{2}, 𝐯_{2} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{2} ⟩ \\ ⋮ & ⋮ & ⋱ & ⋮ \\ ⟨ 𝐯_{1}, 𝐯_{j} ⟩ & ⟨ 𝐯_{2}, 𝐯_{j} ⟩ & \dots & ⟨ 𝐯_{j}, 𝐯_{j} ⟩ \end{matrix} | .

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} - {p r o j}_{𝐮_{1}} (𝐯_{2}) = (2, 2) - {p r o 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.

V · D · M Algebra lineare
Spazio vettoriale	Vettore · Sottospazio vettoriale (Sottospazio generato) · Applicazione lineare (Nucleo · Immagine) · Base · Dimensione · Teorema della dimensione · Formula di Grassmann · Sistema lineare · Algoritmo di Gauss · Teorema di Rouché-Capelli · Regola di Cramer · Spazio duale · Spazio proiettivo · Spazio affine · Teorema della dimensione per spazi vettoriali
Matrici	Identità · Nulla · Quadrata · Invertibile · Simmetrica · Antisimmetrica · Trasposta · Diagonale · Triangolare · Di cambiamento di base · Ortogonale · Normale · Rotazione · Simplettica · Moltiplicazione di matrici · Rango · Teorema di Kronecker · Minore · Matrice dei cofattori · Determinante · Teorema di Binet · Teorema di Laplace · Radice quadrata di una matrice
Diagonalizzabilità	Autovettore e autovalore · Spettro · Polinomio caratteristico · Polinomio minimo · Teorema di Hamilton-Cayley · Matrice a blocchi · Forma canonica di Jordan · Teorema di diagonalizzabilità
Prodotto scalare	Forma bilineare · Sottospazio ortogonale · Spazio euclideo · Base ortonormale · Algoritmo di Lagrange · Segnatura · Teorema di Sylvester · Gram-Schmidt · Forma sesquilineare · Forma hermitiana · Teorema spettrale