Householdertransformatie

In de lineaire algebra is een householdertransformatie 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 een voorbeeld van een lineaire afbeelding. De transformatie is genoemd naar de Amerikaanse wiskundige Alston Scott Householder, die ze in 1958 invoerde.

In matrixvorm kan ze uitgedrukt worden als:

$H=I-2u{u}^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

Een householdertransformatie 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 eindig aantal householdertransformaties kan dienen om de QR-decompositie van een matrix te berekenen. Elk creëert nullen onder de diagonaal van een van de kolommen van de matrix; en transformeert haar zo tot een bovendriehoeksmatrix (analoog aan wat bij Gauss-eliminatie gebeurt).

Om de vector $x$ met een spiegeling $H$ zo te spiegelen dat de gespiegelde $Hx$ op de x-as ligt, moet gespiegeld worden aan een hypervlak dat de hoek tussen $x$ en $e_1=(1,0,\dots ,0)$ in twee gelijke delen verdeelt. De genormeerde normaalvector van dat hypervlak is:

$u=\frac{x-\Vert x\Vert e_1}{\Vert x-\Vert x\Vert e_1\Vert }$.

De gespiegelde vector is dan

$Hx=(\Vert x\Vert ,0,\dots ,0)$.

Het beeld van een vector onder een householdertransformatie kan men snel berekenen: men moet $2u{u}^{T}x$ 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 householdertransformaties $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^{T}A$; dat wil zeggen:

$Q^T=H_p\cdots H_1$

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