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.

\begin{align}
\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\|} \\
\mathbf{u}_4 & = \mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_3}\,(\mathbf{v}_4), & \mathbf{e}_4 & = {\mathbf{u}_4 \over \|\mathbf{u}_4\|} \\
& {}\ \  \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 \|}.
\end{align}

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}(\mathbf{v}_2) =(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