Ortogonalizzazione di Gram-Schmidt

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]

Storia

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

Sia ${\displaystyle V}$ uno spazio vettoriale reale con un prodotto scalare definito positivo. Siano ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}$ vettori linearmente indipendenti in ${\displaystyle V}$. L'algoritmo di Gram-Schmidt restituisce ${\displaystyle n}$ vettori linearmente indipendenti ${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{n}}$ tali che:

${\displaystyle {\mbox{Span}}(\mathbf {v} _{1},\ldots ,\mathbf {v} _{i})={\mbox{Span}}(\mathbf {e} _{1},\ldots ,\mathbf {e} _{i}),\qquad \forall i}$

e

${\displaystyle \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 ${\displaystyle i}$ generano lo stesso sottospazio dei primi ${\displaystyle i}$ vettori iniziali.^[1]

Procedimento

La proiezione ortogonale è la funzione che "proietta" il vettore ${\displaystyle \mathbf {v} }$ in modo ortogonale su ${\displaystyle \mathbf {u} }$:^[2]

${\displaystyle \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 ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{n}}$ a partire da una base generica ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}$. Per calcolare ${\displaystyle \mathbf {u} _{i}}$ si proietta ${\displaystyle \mathbf {v} _{i}}$ ortogonalmente sul sottospazio ${\displaystyle U_{i-1}}$ generato da ${\displaystyle \{\mathbf {u} _{1},\mathbf {u} _{2},\dots ,\mathbf {u} _{i-1}\}}$. Si definisce allora ${\displaystyle \mathbf {u} _{i}}$ come differenza tra ${\displaystyle \mathbf {v} _{i}}$ e questa proiezione, in modo che risulta garantito che esso sia ortogonale a tutti i vettori nel sottospazio ${\displaystyle U_{i-1}}$. Normalizzando poi la base ortogonale (cioè dividendo ogni vettore ${\displaystyle \mathbf {u} _{i}}$ che la compone per la propria norma ${\displaystyle \|\mathbf {u} _{i}\|}$) si ottiene una base ortonormale dello spazio.^[3]

Nello specifico:

${\displaystyle {\begin{aligned}\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{aligned}}}$

dove ${\displaystyle \{\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 ${\displaystyle \mathbf {u} _{i}}$ e ${\displaystyle \mathbf {e} _{j}}$.

Generalizzazioni

Il processo di Gram-Schmidt si applica anche ad una successione infinita ${\displaystyle \{\mathbf {v} _{i}\}_{i}}$ di vettori linearmente indipendenti. Il risultato è sempre una successione ${\displaystyle \{\mathbf {e} _{i}\}_{i}}$ di vettori ortogonali e con norma unitaria, tale che:

${\displaystyle {\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

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

${\displaystyle \mathbf {e} _{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}},}$

${\displaystyle {\displaystyle \mathbf {u} _{j}={\frac {1}{D_{j-1}}}{\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}},}$

dove ${\displaystyle D_{0}=1}$, e per ${\displaystyle j\geq 1}$ si indica con ${\displaystyle D_{j}}$ il determinante della matrice di Gram:

${\displaystyle 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

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

${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},}$

${\displaystyle \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 ${\displaystyle \mathbf {u} _{1}}$ e ${\displaystyle \mathbf {u} _{2}}$ che sono ortogonali fra loro, come mostra il loro prodotto scalare:

${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle =\left\langle (3,1),(-2/5,6/5)\right\rangle =-{\frac {6}{5}}+{\frac {6}{5}}=0.}$

Note

Bibliografia

• 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

• Algoritmo di Lagrange
• Prodotto scalare
• Teorema di Sylvester
• Teorema spettrale

Collegamenti esterni

• (EN) Eric W. Weisstein, Ortogonalizzazione di Gram-Schmidt, su MathWorld, Wolfram Research.
• (EN) Ortogonalizzazione di Gram-Schmidt, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm (PDF), su math.hmc.edu. URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 2 aprile 2016).
• (EN) Earliest known uses of some of the words of mathematics: G, su jeff560.tripod.com.
• (EN) Gram-Schmidt orthogonalization applet, su math.ucla.edu.
• (EN) NAG Gram–Schmidt orthogonalization of n vectors of order m routine, su nag.co.uk.
• (EN) Proof: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.
• (EN) Gram Schmidt process in plane, su bigsigma.com. URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 7 maggio 2009).
• (EN) Gram Schmidt process in space, su bigsigma.com. URL consultato il 18 febbraio 2015 (archiviato dall'url originale il 7 maggio 2009).

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