Householder-transformatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de lineaire algebra is een Householder-transformatie een lineaire afbeelding, met name een reflectie (spiegeling) in de euclidische ruimte ten opzichte van een hypervlak dat door de oorsprong gaat. Het spiegelvlak wordt bepaald door een normaalvector u van lengte 1 (een eenheidsvector).

De transformatie is genoemd naar de Amerikaanse wiskundige Alston Scott Householder, die ze in 1958 invoerde.[1]

In matrixvorm kan ze uitgedrukt worden als:

,

waarin de eenheidsmatrix is.

De matrix is symmetrisch en orthogonaal. Het product van met een vector komt overeen met de spiegeling van aan het hypervlak door de oorsprong loodrecht op .

Matrixdecompositie[bewerken]

Householder-transformatie in het vlak: de vector wordt getransformeerd naar door spiegeling aan het hypervlak (hier een lijn) dat de hoek tussen en in tweeën deelt

Een van de technieken om de QR-decompositie van een matrix te berekenen gebruikt Householder-transformaties om nullen te verkrijgen in de benedendriehoek van de matrix (analoog aan wat bij Gauss-eliminatie gebeurt).

Om de vector met een spiegeling zo te spiegelen dat de gespiegelde op de x-as ligt, moet gespiegeld worden aan een hypervlak dat de hoek tussen en in twee gelijke delen verdeelt. De genormeerde normaalvector van dat hypervlak is:

.

De gespiegelde vector is dan

.

Het beeld onder een Householder-transformatie van een vector kan men snel berekenen: men moet aftrekken van . Dit vereist de berekening van een inwendig product en het verschil van een vector met een veelvoud van een andere vector.

In de QR-decompositie wordt een matrix herleid tot een bovendriehoeksmatrix door opeenvolgende Householder-transformaties , met normaalvectoren die orthogonaal zijn ten opzichte van elkaar, zodanig dat in de kolommen van de elementen onder de diagonaal nul worden. Dan is

De orthogonale matrix wordt bepaald door ; dat wil zeggen:

De QR-decompositie kan men ook langs andere wegen bekomen, bijvoorbeeld via Givens-rotaties.