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.^[1]

In matrixvorm kan ze uitgedrukt worden als:

${\displaystyle H=I-2uu^{T}}$,

waarin ${\displaystyle I}$ de eenheidsmatrix is. De matrix ${\displaystyle H}$ is symmetrisch en orthogonaal. Het product van ${\displaystyle H}$ met een vector ${\displaystyle y}$ komt overeen met de spiegeling van ${\displaystyle y}$ aan het hypervlak door de oorsprong loodrecht op ${\displaystyle u}$.

Matrixdecompositie

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 ${\displaystyle x}$ met een spiegeling ${\displaystyle H}$ zo te spiegelen dat de gespiegelde ${\displaystyle Hx}$ op de x-as ligt, moet gespiegeld worden aan een hypervlak dat de hoek tussen ${\displaystyle x}$ en ${\displaystyle e_{1}=(1,0,\ldots ,0)}$ in twee gelijke delen verdeelt. De genormeerde normaalvector van dat hypervlak is:

${\displaystyle u={\frac {x-\|x\|e_{1}}{\|x-\|x\|e_{1}\|}}}$.

De gespiegelde vector is dan

${\displaystyle Hx=(\|x\|,0,\ldots ,0)}$.

Het beeld van een vector onder een householdertransformatie kan men snel berekenen: men moet ${\displaystyle 2uu^{T}x}$ aftrekken van ${\displaystyle 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 ${\displaystyle A}$ herleid tot een bovendriehoeksmatrix ${\displaystyle R}$ door opeenvolgende householdertransformaties ${\displaystyle H_{1},H_{2},...H_{p}}$, met normaalvectoren ${\displaystyle u_{1},u_{2},...}$ die orthogonaal zijn ten opzichte van elkaar, zodanig dat in de kolommen van ${\displaystyle A}$ de elementen onder de diagonaal nul worden. Dan is

${\displaystyle R=H_{p}\cdots H_{2}H_{1}A}$

De orthogonale matrix ${\displaystyle Q}$ wordt bepaald door ${\displaystyle R=Q^{T}A}$; dat wil zeggen:

${\displaystyle Q^{T}=H_{p}\cdots H_{1}}$

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