Algoritm Gram-Schmidt

În algebra liniară , într - un spațiu prehilbertian (adică un spațiu vectorial pe câmpul de numere reale sau al complexelor , prevăzut cu un produs scalar ), procesul sau algoritmul de Gram-Schmidt este un algoritm de construire, dintr - un gratuit familie peste o bază ortonormală subspaiul pe care îl generează . Putem folosi, de asemenea, metoda Gram-Schmidt pe o familie infinită de vectori numărați . Acest lucru face posibilă demonstrareaexistența unei baze hilbertiene dacă spațiul este separabil .

State

Tocmai, notând $N = {0, ..., p }$ cu $p$ în $ℕ$ sau $N = ℕ$ :

Teorema - Dacă este o familie liberă a unui spațiu preilbertian, există una și o singură familie ortonormală astfel încât: $(x_ {n}) _ {{n \ în N}} \,$ $(e_ {n}) _ {{n \ în N}} \,$

${{\ rm {Vect}}} (e_ {0}, \ ldots, e_ {n}) = {{\ rm {Vect}}} (x_ {0}, \ ldots, x_ {n}) \,$ pentru toate $n$
produsele dot sunt strict pozitive pentru toate $n$ $(e_ {n} | x_ {n}) \,$

Uităm adesea a doua condiție, care asigură unicitatea. Acesta permite să vorbească despre familia orthonormalized de bacterii Gram-Schmidt , asociat . $(x_ {n}) _ {{n \ în N}} \,$

Pasul general al algoritmului constă în scăderea din vectorul $v j +1$ a proiecției sale ortogonale pe subspațiul generat de $v 0 , ..., v j$ . Unul se bazează pe familia ortonormală deja construită pentru calculul acestui proiect.

Această metodă a fost publicată de Jørgen Pedersen Gram în 1883 și reformulată de Erhard Schmidt în 1907, dar se găsește deja în 1816 lucrări de Laplace .

Aplicații

Procesul de ortonormalizare Gram-Schmidt oferă în mod constructiv existența bazelor ortonormale pentru orice spațiu euclidian sau hermitian .
De asemenea, putem ortonormaliza baza canonică (1, X , ...) a lui ℝ [ X ] și astfel putem obține o familie de polinoame ortogonale .
Metoda Schmidt poate fi utilizată în descompunerea QR a unei matrice.

Procesul Gram-Schmidt

Definim operatorul de proiecție ortogonală pe o linie vectorială direcționată de vectorul $u$ prin:

{\ mathrm {proj}} _ {{{\ mathbf {u}}}} \, ({\ mathbf {v}}) = {\ langle {\ mathbf {u}}, {\ mathbf {v}} \ rangle \ over \ langle {\ mathbf {u}}, {\ mathbf {u}} \ rangle} {\ mathbf {u}}.

Procesul Gram-Schmidt este apoi:

	${\ mathbf {u}} _ {1} = {\ mathbf {v}} _ {1},$		${\ displaystyle \ mathbf {e} _ {1} = {\ mathbf {u} _ {1} \ over \ \| \ mathbf {u} _ {1} \ \|}}$
	${\ mathbf {u}} _ {2} = {\ mathbf {v}} _ {2} - {\ mathrm {proj}} _ {{{\ mathbf {u}} _ {1}}} \, ( {\ mathbf {vb}} _ {2}),$		${\ displaystyle \ 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} ),$		${\ displaystyle \ 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}),$		${\ displaystyle \ mathbf {e} _ {k} = {\ mathbf {u} _ {k} \ over \ \| \ mathbf {u} _ {k} \ \|}}$

Cu:

$<,>$ , produsul scalar din spațiul considerat
$v 1 , ..., v k$ , un set de vectori fără legătură
$u 1 , ..., u k$ , un set de vectori ortogonali doi-la-doi
$e 1 , ..., e k$ , un set de vectori ortonormali doi-la-doi

Note și referințe

(fr) Acest articol este preluat parțial sau în întregime din articolul din Wikipedia engleză intitulat „ Procesul Gram - Schmidt ” (a se vedea lista autorilor ) .

Matematică All-in-One. MP al 2- lea an , Paris, Dunod,2004, A 2 -a ed. , 1279 p. ( ISBN 978-2-10-007576-8 , aviz BnF n o FRBNF39237416 ) , p. 569
(în) ortogonalizare Gram-Schmidt în cele mai vechi utilizări cunoscute ale unora dintre cuvintele matematicii (G)
A. Quarteroni, R. Sacco, F. Saleri, Metode numerice pentru calcul științific, Programe în Matlab , ed. Springer, 2000, p. 83 și următoarele. Citeste online
convenția aleasă pentru produsul scalar Hermitian fiind aici: liniaritatea pe partea dreaptă și semi-liniaritatea pe stânga.