Gram-Schmidt-proces
door Marco Taboga, PhD
Het Gram-Schmidt-proces (of de Gram-Schmidt-procedure) is een reeks bewerkingen die het mogelijk maakt een verzameling lineair onafhankelijke vectoren om te zetten in een verzameling orthonormale vectoren die dezelfde ruimte beslaan als de oorspronkelijke verzameling.
Peliminaria
Laat ons enkele begrippen overlopen die essentieel zijn om het Gram-Schmidt-proces te begrijpen.
Bedenk dat twee vectoren en
orthogonaal zijn als en slechts als hun inwendig product gelijk is aan nul, dat wil zeggen,
Gegeven een inwendig product, kunnen we de norm (lengte) van een vector als volgt definiëren:
Een verzameling vectoren heet orthonormaal als en slechts als de elementen ervan eenheidsnorm hebben en orthogonaal ten opzichte van elkaar zijn. Met andere woorden, een verzameling van vectoren
is orthonormaal als en slechts als
We hebben bewezen dat de vectoren van een orthonormale verzameling lineair onafhankelijk zijn.
Wanneer een basis voor een vectorruimte ook een orthonormale verzameling is, wordt deze een orthonormale basis genoemd.
Projecties op orthonormale verzamelingen
In het Gram-Schmidt-proces gebruiken we herhaaldelijk de volgende stelling, waaruit blijkt dat elke vector in twee delen kan worden ontleed: 1) zijn projectie op een orthonormale verzameling en 2) een rest die orthogonaal is aan de gegeven orthonormale verzameling.
Stelling Laat een vectorruimte zijn, voorzien van een inwendig product
. Zij
een orthonormale verzameling. Voor elke
hebben we
waar
orthogonaal is aan
voor elke
DefinieerDan hebben we voor elke
dat
waar: in de stappen
en
hebben we gebruik gemaakt van het feit dat het binnenproduct lineair is in zijn eerste argument; in stap
hebben we gebruik gemaakt van het feit dat
als
aangezien we te maken hebben met een orthonormale verzameling; in stap
hebben we gebruik gemaakt van het feit dat de norm van
gelijk is aan 1. Daarom is
, zoals hierboven gedefinieerd, orthogonaal voor alle elementen van de orthonormale verzameling, hetgeen de stelling bewijst.
De term heet de lineaire projectie van
op de orthonormale verzameling
, terwijl de term
de rest van de lineaire projectie wordt genoemd.
Normalisatie
Een ander wellicht voor de hand liggend feit dat we herhaaldelijk zullen gebruiken in het Gram-Schmidt proces is dat, als we een willekeurige vector nemen die niet nul is en we delen hem door zijn norm, het resultaat van de deling een nieuwe vector is die eenheidsnorm heeft.
Met andere woorden, als dan hebben we, door de definitiviteitseigenschap van de norm, dat
Als gevolg daarvan kunnen we definiëren en, door de positiviteit en absolute homogeniteit van de norm, hebben we
Overzicht van de procedure
Nu we weten hoe we een vector kunnen normaliseren en hoe we hem kunnen ontbinden in een projectie op een orthonormale verzameling en een residu, zijn we klaar om de Gram-Schmidt-procedure uit te leggen.
We gaan een overzicht geven van het proces, waarna we het formeel zullen uitdrukken als een stelling en we alle technische details zullen bespreken in het bewijs van de stelling.
Hier volgt het overzicht.
We krijgen een verzameling lineair onafhankelijke vectoren .
Om het proces te beginnen normaliseren we de eerste vector, dat wil zeggen we definiëren
In de tweede stap projecteren we op
:
waarbij
de rest van de projectie is.
Vervolgens normaliseren we het residu:
We zullen later bewijzen dat (zodat de normalisatie kan worden uitgevoerd) omdat de startvectoren lineair onafhankelijk zijn.
De twee aldus verkregen vectoren en
zijn orthonormaal.
In de derde stap projecteren we op
en
:
en berekenen we het residu van de projectie
.
Daarna normaliseren we het:
Zo gaan we door tot we het laatste genormaliseerde residu hebben.
Aan het eind van het proces vormen de vectoren een orthonormale verzameling omdat:
-
zij het resultaat zijn van een normalisatie, en bijgevolg eenheidsnorm hebben;
-
elk
wordt verkregen uit een residu dat de eigenschap heeft orthogonaal te zijn aan
.
Ter vervollediging van dit overzicht herinneren wij eraan dat de lineaire spanwijdte van de verzameling is van alle vectoren die kunnen worden geschreven als lineaire combinaties van
; zij wordt aangeduid met
en is een lineaire ruimte.
Daar de vectoren lineair onafhankelijke combinaties zijn van
, kan elke vector die kan worden geschreven als een lineaire combinatie van
, ook worden geschreven als een lineaire combinatie van
. Daarom vallen de spanwijdtes van de twee verzamelingen vectoren samen:
Formele verklaring
We formaliseren hier het Gram-Schmidt proces als een stelling, waarvan het bewijs alle technische details van de procedure bevat.
Stelling Laat een vectorruimte zijn, voorzien van een inwendig product
. Zij
lineair onafhankelijke vectoren. Dan bestaat er een verzameling orthonormale vectoren
zodanig dat
voor elke
.
Het bewijs gaat via inductie: eerst bewijzen we dat de stelling waar is voor , en dan bewijzen we dat ze waar is voor een generieke
als ze geldt voor
. Als
, heeft de vector
eenheidsnorm en vormt hij op zichzelf een orthonormale verzameling: er zijn geen andere vectoren, dus aan de orthogonaliteitsvoorwaarde wordt triviaal voldaan. De verzameling
is de verzameling van alle scalaire veelvouden van
, die ook scalaire veelvouden zijn van
(en vice versa). Daarom
Nu, stel dat de stelling waar is voor
. Dan kunnen we
projecteren op
:
waarbij het residu
orthogonaal is aan
. Stel dat
. Dan geldt,
Omdat
voor elke
,
voor elke
, waarbij
scalaren zijn. Daarom,
Met andere woorden, de aanname dat
leidt tot de conclusie dat
een lineaire combinatie is van
. Maar dit is onmogelijk omdat een van de aannames van de stelling is dat
lineair onafhankelijk zijn. Bijgevolg moet het zo zijn dat
. We kunnen dus het residu normaliseren en de vector
definiëren die eenheidsnorm heeft. We weten al dat
orthogonaal is aan
. Dit impliceert dat ook
orthogonaal is aan
.
is dus een orthonormale verzameling. Neem nu een willekeurige vector
die geschreven kan worden als
waarbij
scalaren zijn. Aangezien, door aanname,
hebben we dat vergelijking (2) ook geschreven kan worden als
waar
scalaren zijn, en: in stap
hebben we vergelijking (1) gebruikt; in stap
hebben we de definitie van
gebruikt. Aldus hebben we bewezen dat elke vector die kan worden geschreven als een lineaire combinatie van
ook kan worden geschreven als een lineaire combinatie van
. Veronderstelling (3) laat toe om het omgekeerde op een volledig analoge manier te bewijzen:
Met andere woorden, elke lineaire combinatie van
is ook een lineaire combinatie van
. Dit bewijst dat
en sluit het bewijs af.
Elke binnenproductruimte heeft een orthonormale basis
De volgende stelling geeft een belangrijk gevolg van het Gram-Schmidtproces.
Stelling Stel is een vectorruimte voorzien van een binnenproduct
. Als
een eindige dimensie
heeft, dan bestaat er een orthonormale basis
voor
.
Omdat eindig-dimensionaal is, bestaat er minstens één basis voor
, bestaande uit
vectoren
. We kunnen de Gram-Schmidt procedure toepassen op de basis en zo een orthonormale verzameling
verkrijgen. Omdat
een basis is, overspant deze
.
Dus
is een orthonormale basis van
.
Oplossingen
Hieronder vindt u enkele oefeningen met toegelichte oplossingen.
Oefening 1
Beschouw de ruimte van alle
vectoren met reele ingangen en het inwendig product
waar
en
de getransponeerde is van
. Definieer de vector
Normaliseer .
De norm van is
Daarom, is de normalisatie van
Oefening 2
Beschouw de ruimte van alle
vectoren met reële ingangen en het inwendig product
waar
. Beschouw de twee lineair onafhankelijke vectoren
Verander ze in een orthonormale verzameling met behulp van het Gram-Schmidt-proces.
De norm van is
Daarom, is de eerste orthonormale vector
Het binnenproduct van
en
is
De projectie van
op
is
Het residu van de projectie is
De norm van het residu is
en het genormaliseerde residu is
Dus, de orthonormale verzameling die we zochten is
Hoe citeren
Aan te halen als:
Taboga, Marco (2017). “Gram-Schmidt proces”, Lezingen over matrixalgebra. https://www.statlect.com/matrix-algebra/Gram-Schmidt-process.
Leave a Reply