Il procedimento di Gram-Schmidt è un algoritmo che trasforma una qualsiasi base di uno spazio con prodotto scalare in una base ortogonale (o ortonormale), preservando lo span di ogni prefisso della sequenza.
Vedi anche: Prodotto Scalare, Proiezione Ortogonale, Fattorizzazione QR.
Algoritmo
Data una base \{\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_n\} di V, si costruisce la base ortogonale \{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\} con:
\vec{u}_1 = \vec{v}_1
\vec{u}_k = \vec{v}_k - \sum_{j=1}^{k-1} \frac{\langle \vec{v}_k, \vec{u}_j \rangle}{\langle \vec{u}_j, \vec{u}_j \rangle}\, \vec{u}_j \quad (k = 2, \ldots, n)
Ogni \vec{u}_k è la componente di \vec{v}_k ortogonale a tutti i precedenti \vec{u}_1, \ldots, \vec{u}_{k-1}.
Per ottenere una base ortonormale si normalizza: \vec{e}_k = \vec{u}_k / \|\vec{u}_k\|.
Proiezione Ortogonale
Il termine \text{proj}_{\vec{u}_j}(\vec{v}_k) = \dfrac{\langle \vec{v}_k, \vec{u}_j \rangle}{\langle \vec{u}_j, \vec{u}_j \rangle}\, \vec{u}_j è la proiezione ortogonale di \vec{v}_k su \vec{u}_j.
L’algoritmo sottrae iterativamente le proiezioni, «togliendo» da \vec{v}_k tutto ciò che è già rappresentato dai vettori precedenti.
Proprietà
- \operatorname{span}(\vec{e}_1, \ldots, \vec{e}_k) = \operatorname{span}(\vec{v}_1, \ldots, \vec{v}_k) per ogni k.
- Se \vec{v}_k \in \operatorname{span}(\vec{v}_1, \ldots, \vec{v}_{k-1}), allora \vec{u}_k = \vec{0}: segnala dipendenza lineare.
- L’algoritmo è stabile ma può accumulare errori di arrotondamento; la versione modificata di Gram-Schmidt (che proietta su \vec{u}_k aggiornato) è numericamente più robusta.
Relazione con la Fattorizzazione QR
Il procedimento di Gram-Schmidt applicato alle colonne di una matrice A \in M_{m \times n}(\mathbb{R}) (con m \geq n, colonne linearmente indipendenti) produce la fattorizzazione:
A = QR
dove Q \in M_{m \times n} ha colonne ortonormali e R \in M_{n \times n} è triangolare superiore con elementi diagonali positivi. Vedi: Fattorizzazione QR.
Applicazioni ingegneristiche
- Minimi quadrati: la fattorizzazione QR ottenuta con Gram-Schmidt è il metodo numericamente più stabile per risolvere sistemi sovradeterminati Ax \approx b.
- Analisi modale: la base di modi propri di una struttura, una volta calcolata, viene ortonormalizzata con Gram-Schmidt rispetto alla matrice di massa per disaccoppiare le equazioni del moto.
- Elaborazione del segnale: la costruzione di filtri di Kalman e di basi wavelet usa schemi di ortogonalizzazione analoghi a Gram-Schmidt.