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]
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.
Sia V {\displaystyle V} uno spazio vettoriale reale con un prodotto scalare definito positivo . Siano v 1 , … , v n {\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}} vettori linearmente indipendenti in V {\displaystyle V} . L'algoritmo di Gram-Schmidt restituisce n {\displaystyle n} vettori linearmente indipendenti e 1 , … , e n {\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{n}} tali che:
Span ( v 1 , … , v i ) = Span ( e 1 , … , e i ) , ∀ i {\displaystyle {\mbox{Span}}(\mathbf {v} _{1},\ldots ,\mathbf {v} _{i})={\mbox{Span}}(\mathbf {e} _{1},\ldots ,\mathbf {e} _{i}),\qquad \forall i} e
⟨ e i , e j ⟩ = { 1 i = j , 0 i ≠ j , ‖ e i ‖ = 1 , ∀ i {\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 i {\displaystyle i} generano lo stesso sottospazio dei primi i {\displaystyle i} vettori iniziali.[1]
La proiezione ortogonale è la funzione che "proietta" il vettore v {\displaystyle \mathbf {v} } in modo ortogonale su u {\displaystyle \mathbf {u} } :[2]
p r o j u ( v ) = ⟨ v , u ⟩ ⟨ u , u ⟩ u . {\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 u 1 , … , u n {\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{n}} a partire da una base generica v 1 , … , v n {\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}} . Per calcolare u i {\displaystyle \mathbf {u} _{i}} si proietta v i {\displaystyle \mathbf {v} _{i}} ortogonalmente sul sottospazio U i − 1 {\displaystyle U_{i-1}} generato da { u 1 , u 2 , … , u i − 1 } {\displaystyle \{\mathbf {u} _{1},\mathbf {u} _{2},\dots ,\mathbf {u} _{i-1}\}} . Si definisce allora u i {\displaystyle \mathbf {u} _{i}} come differenza tra v i {\displaystyle \mathbf {v} _{i}} e questa proiezione, in modo che risulta garantito che esso sia ortogonale a tutti i vettori nel sottospazio U i − 1 {\displaystyle U_{i-1}} . Normalizzando poi la base ortogonale (cioè dividendo ogni vettore u i {\displaystyle \mathbf {u} _{i}} che la compone per la propria norma ‖ u i ‖ {\displaystyle \|\mathbf {u} _{i}\|} ) si ottiene una base ortonormale dello spazio.[3]
Nello specifico:
I primi due passi dell'algoritmo. u 1 = v 1 , e 1 = u 1 ‖ u 1 ‖ u 2 = v 2 − p r o j u 1 ( v 2 ) , e 2 = u 2 ‖ u 2 ‖ u 3 = v 3 − p r o j u 1 ( v 3 ) − p r o j u 2 ( v 3 ) , e 3 = u 3 ‖ u 3 ‖ u 4 = v 4 − p r o j u 1 ( v 4 ) − p r o j u 2 ( v 4 ) − p r o j u 3 ( v 4 ) , e 4 = u 4 ‖ u 4 ‖ ⋮ ⋮ u k = v k − ∑ j = 1 k − 1 p r o j u j ( v k ) , e k = u k ‖ u k ‖ . {\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 { e i } {\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 u i {\displaystyle \mathbf {u} _{i}} e e j {\displaystyle \mathbf {e} _{j}} .
Il processo di Gram-Schmidt si applica anche ad una successione infinita { v i } i {\displaystyle \{\mathbf {v} _{i}\}_{i}} di vettori linearmente indipendenti. Il risultato è sempre una successione { e i } i {\displaystyle \{\mathbf {e} _{i}\}_{i}} di vettori ortogonali e con norma unitaria, tale che:
Span ( v 1 , … , v i ) = Span ( e 1 , … , e i ) , ∀ i . {\displaystyle {\mbox{Span}}(\mathbf {v} _{1},\ldots ,\mathbf {v} _{i})={\mbox{Span}}(\mathbf {e} _{1},\ldots ,\mathbf {e} _{i}),\qquad \forall i.} Il risultato del procedimento di Gram-Schmidt può essere espresso in modo non ricorsivo utilizzando il determinante :
e j = 1 D j − 1 D j | ⟨ v 1 , v 1 ⟩ ⟨ v 2 , v 1 ⟩ … ⟨ v j , v 1 ⟩ ⟨ v 1 , v 2 ⟩ ⟨ v 2 , v 2 ⟩ … ⟨ v j , v 2 ⟩ ⋮ ⋮ ⋱ ⋮ ⟨ v 1 , v j − 1 ⟩ ⟨ v 2 , v j − 1 ⟩ … ⟨ v j , v j − 1 ⟩ v 1 v 2 … v j | , {\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}},} u j = 1 D j − 1 | ⟨ v 1 , v 1 ⟩ ⟨ v 2 , v 1 ⟩ ⋯ ⟨ v j , v 1 ⟩ ⟨ v 1 , v 2 ⟩ ⟨ v 2 , v 2 ⟩ ⋯ ⟨ v j , v 2 ⟩ ⋮ ⋮ ⋱ ⋮ ⟨ v 1 , v j − 1 ⟩ ⟨ v 2 , v j − 1 ⟩ ⋯ ⟨ v j , v j − 1 ⟩ v 1 v 2 ⋯ v j | , {\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 D 0 = 1 {\displaystyle D_{0}=1} , e per j ≥ 1 {\displaystyle j\geq 1} si indica con D j {\displaystyle D_{j}} il determinante della matrice di Gram :
D j = | ⟨ v 1 , v 1 ⟩ ⟨ v 2 , v 1 ⟩ … ⟨ v j , v 1 ⟩ ⟨ v 1 , v 2 ⟩ ⟨ v 2 , v 2 ⟩ … ⟨ v j , v 2 ⟩ ⋮ ⋮ ⋱ ⋮ ⟨ v 1 , v j ⟩ ⟨ v 2 , v j ⟩ … ⟨ v j , v j ⟩ | . {\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}}.} Dati i vettori v 1 = ( 3 , 1 ) {\displaystyle \mathbf {v} _{1}=(3,1)} e v 2 = ( 2 , 2 ) {\displaystyle \mathbf {v} _{2}=(2,2)} nel piano euclideo R 2 {\displaystyle \mathbb {R} ^{2}} munito del prodotto scalare standard, applicando il procedimento di Gram-Schmidt si ha:
u 1 = v 1 , {\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},} u 2 = v 2 − p r o j u 1 ( v 2 ) = ( 2 , 2 ) − p r o j ( 3 , 1 ) ( 2 , 2 ) = ( − 2 / 5 , 6 / 5 ) , {\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 u 1 {\displaystyle \mathbf {u} _{1}} e u 2 {\displaystyle \mathbf {u} _{2}} che sono ortogonali fra loro, come mostra il loro prodotto scalare:
⟨ u 1 , u 2 ⟩ = ⟨ ( 3 , 1 ) , ( − 2 / 5 , 6 / 5 ) ⟩ = − 6 5 + 6 5 = 0. {\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.} 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) (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) .