Ortogonalizzazione di Gram-Schmidt

Da Wikipedia, l'enciclopedia libera.

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.[1]

L'algoritmo[modifica | modifica wikitesto]

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.[1]

Procedimento[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Proiezione (geometria).

Definiamo la proiezione ortogonale come la funzione che proietta il vettore v in modo ortogonale su u:[2]

\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:[3]

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[modifica | modifica wikitesto]

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

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

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

Generalizzazioni[modifica | modifica wikitesto]

Il processo di Gram-Schmidt si applica anche ad una successione infinita {vi}i di vettori linearmente indipendenti. Il risultato è sempre una successione {ei}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[modifica | modifica wikitesto]

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 0=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 uk è un determinante "formale", ovvero la matrice contiene sia scalari che vettori.

Esempio[modifica | modifica wikitesto]

Consideriamo i vettori seguenti nel piano euclideo R2, 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 u1 e u2 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[modifica | modifica wikitesto]

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.

Note[modifica | modifica wikitesto]

  1. ^ a b Hoffman, Kunze, Pag. 280
  2. ^ S. Lang, Pag. 152
  3. ^ S. Lang, Pag. 154

Bibliografia[modifica | modifica wikitesto]

  • Serge Lang, Algebra lineare, Torino, Bollati Boringhieri, 1992, ISBN 88-339-5035-2.
  • Kenneth Hoffman, Ray Kunze, Linear Algebra, 2ª ed., Englewood Cliffs, New Jersey, Prentice - Hall, inc., 1971, ISBN 0-13-536821-9.

Voci correlate[modifica | modifica wikitesto]

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