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:

H  = I - 2 uu^T,

waarin I de eenheidsmatrix is.

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

Matrixdecompositie[bewerken]

Householder-transformatie in het vlak: de vector x wordt getransformeerd naar Hx door spiegeling aan het hypervlak (hier een lijn) dat de hoek tussen x en Hx 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 x met een spiegeling H zo te spiegelen dat de gespiegelde Hxop de x-as ligt, moet gespiegeld worden aan een hypervlak dat de hoek tussen x en e_1=(1,0,\ldots,0) in twee gelijke delen verdeelt. De genormeerde normaalvector van dat hypervlak is:

 u = \frac{x - \|x\| e_1}{\|x- \|x\| e_1\|}.

De gespiegelde vector is dan

Hx=(\|x\|, 0, \ldots, 0).

Het beeld onder een Householder-transformatie van een vector kan men snel berekenen: men moet 2 uu^Tx aftrekken van x. 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 A herleid tot een bovendriehoeksmatrix R door opeenvolgende Householder-transformaties H_1, H_2, ... H_p, met normaalvectoren u_1, u_2, ... die orthogonaal zijn ten opzichte van elkaar, zodanig dat in de kolommen van A de elementen onder de diagonaal nul worden. Dan is

R = H_p \cdots H_2 H_1 A

De orthogonale matrix Q wordt bepaald door R = Q^TA; dat wil zeggen:

Q^T = H_p \cdots H_1

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

Bronnen, noten en/of referenties
  1. Alston S. Householder. "Unitary Triangularization of a Nonsymmetric Matrix." Journal of the ACM (1958), vol. 5 nr. 4, blz. 339-342. DOI:10.1145/320941.320947