Procedimento di Gram-Schmidt

Voci di Glossario Algebra Lineare
Indice dei contenuti

    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 {v⃗1,v⃗2,…,v⃗n}\{\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_n\} di VV, si costruisce la base ortogonale {u⃗1,u⃗2,…,u⃗n}\{\vec{u}_1, \vec{u}_2, \ldots, \vec{u}_n\} con:

    u⃗1=v⃗1\vec{u}_1 = \vec{v}_1

    u⃗k=v⃗k−∑j=1k−1⟨v⃗k,u⃗j⟩⟨u⃗j,u⃗j⟩ u⃗j(k=2,…,n)\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 u⃗k\vec{u}_k è la componente di v⃗k\vec{v}_k ortogonale a tutti i precedenti u⃗1,…,u⃗k−1\vec{u}_1, \ldots, \vec{u}_{k-1}.

    Per ottenere una base ortonormale si normalizza: e⃗k=u⃗k/∥u⃗k∥\vec{e}_k = \vec{u}_k / \|\vec{u}_k\|.

    Proiezione Ortogonale

    Il termine proju⃗j(v⃗k)=⟨v⃗k,u⃗j⟩⟨u⃗j,u⃗j⟩ u⃗j\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 v⃗k\vec{v}_k su u⃗j\vec{u}_j.

    L’algoritmo sottrae iterativamente le proiezioni, «togliendo» da v⃗k\vec{v}_k tutto ciò che è già rappresentato dai vettori precedenti.

    Proprietà

    • span⁡(e⃗1,…,e⃗k)=span⁡(v⃗1,…,v⃗k)\operatorname{span}(\vec{e}_1, \ldots, \vec{e}_k) = \operatorname{span}(\vec{v}_1, \ldots, \vec{v}_k) per ogni kk.
    • Se v⃗k∈span⁡(v⃗1,…,v⃗k−1)\vec{v}_k \in \operatorname{span}(\vec{v}_1, \ldots, \vec{v}_{k-1}), allora u⃗k=0⃗\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 u⃗k\vec{u}_k aggiornato) è numericamente più robusta.

    Relazione con la Fattorizzazione QR

    Il procedimento di Gram-Schmidt applicato alle colonne di una matrice A∈Mm×n(R)A \in M_{m \times n}(\mathbb{R}) (con m≥nm \geq n, colonne linearmente indipendenti) produce la fattorizzazione:

    A=QRA = QR

    dove Q∈Mm×nQ \in M_{m \times n} ha colonne ortonormali e R∈Mn×nR \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≈bAx \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.

    Ultimo aggiornamento: