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]

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.

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 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) \qquad \forall i

e:

 \langle \mathbf{e}_i,\mathbf{e}_j \rangle = \begin{cases}1 & i=j\\
0 & i \neq j\end{cases} \qquad \|{e_i}\|=1 \qquad \forall i

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

Procedimento[modifica | modifica wikitesto]

La proiezione ortogonale è la funzione che "proietta" il vettore \mathbf v in modo ortogonale su \mathbf 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. Per calcolare \mathbf u_i si proietta \mathbf v_i ortogonalmente sul sottospazio U_{i-1} generato da \{ \mathbf u_1,\mathbf u_2,\dots,\mathbf u_{i-1} \}. Si definisce allora \mathbf u_i come differenza tra \mathbf v_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 \mathbf u_i che la compone per la propria norma \| \mathbf u_i \|) si ottiene una base ortonormale dello spazio.[3]

Nello specifico:

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

dove \{ \mathbf e_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 \mathbf u_i e \mathbf e_j.

Generalizzazioni[modifica | modifica wikitesto]

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

Scrittura per mezzo del determinante[modifica | modifica wikitesto]

Il risultato del procedimento di Gram-Schmidt può essere espresso in modo non ricorsivo utilizzando il determinante:

 \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 \ge 1 la matrice 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}

Esempio[modifica | modifica wikitesto]

Dati i vettori \mathbf{v}_1=(3,1) e \mathbf{v}_2=(2,2) nel piano euclideo \R^2 munito del prodotto scalare standard, applicando il procedimento di Gram-Schmidt si ha:

\mathbf{u}_1=\mathbf{v}_1
\mathbf{u}_2=\mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1} =(2,2)-\mathrm{proj}_{(3, 1)}\,{(2,2)}=(-2/5,6/5)

ottenendo i vettori \mathbf{u}_1 e \mathbf{u}_2 che sono ortogonali fra loro, come mostra il loro prodotto scalare:

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

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.
  • (EN) Kenneth Hoffman, Ray Kunze, Linear Algebra, 2ª ed., Englewood Cliffs, New Jersey, Prentice - Hall, inc., 1971, ISBN 0-13-536821-9.
  • (EN) F.R. Gantmacher, The theory of matrices , 1 , Chelsea, reprint (1977)
  • (EN) A.G. Kurosh, Higher algebra , MIR (1972)

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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