Transformace domácnosti - Householder transformation

v lineární algebra, a Transformace domácnosti (také známý jako Reflexe domácnosti nebo základní reflektor) je lineární transformace který popisuje a odraz o a letadlo nebo nadrovina obsahující původ. Transformace Householder byla použita v dokumentu z roku 1958 od Alston Scott Householder.^[1]

Je to analogické přes obecné vnitřní produktové prostory je Provozovatel domácnosti.

Definice

Proměna

Odrazovou nadrovinu lze definovat a jednotkový vektor ${ textstyle v}$ (vektor s délkou ${ textový styl 1}$) to je ortogonální do nadroviny. Odraz a směřovat ${ textstyle x}$ o této nadrovině je lineární transformace:

${ displaystyle x-2 langle x, v rangle v = x-2v vlevo (v ^ { textyf {H}} x vpravo),}$

kde ${ textstyle v}$ je uveden jako vektor jednotky sloupce s Hermitian transponovat ${ textstyle v ^ { textyf {H}}}$.

Matice pro domácnosti

Matici vytvořenou z této transformace lze vyjádřit pomocí vnější produkt tak jako:

${ displaystyle P = I-2 (v otimes v) = I-2vv ^ { textyf {H}}}$

je známý jako Matice pro domácnosti, kde ${ textstyle I}$ je matice identity

Vlastnosti

Matice Householder má následující vlastnosti:

• to je Hermitian: ${ textstyle P = P ^ { textyf {H}}}$,
• to je unitární: ${ textstyle P ^ {- 1} = P ^ { textyf {H}}}$,
• proto je nedobrovolný: ${ textstyle P ^ {2} = I}$.
• Matice majitelů domů má vlastní čísla ${ textstyle pm 1}$. Chcete-li to vidět, všimněte si, že pokud ${ textový styl}$ je kolmý k vektoru ${ textstyle v}$ který byl použit k vytvoření reflektoru ${ textstyle Pu = u}$, tj., ${ textový styl 1}$ je vlastní číslo multiplicity ${ textstyle n-1}$, protože tam jsou ${ textstyle n-1}$ nezávislé vektory kolmé na ${ textstyle v}$. Všimněte si také ${ textstyle Pv = -v}$a tak ${ textstyle -1}$ je vlastní číslo s multiplicitou ${ textový styl 1}$.
• The určující reflektoru pro majitele domu je ${ textstyle -1}$, protože determinant matice je produktem vlastních čísel, v tomto případě je jedním z nich ${ textstyle -1}$ se zbytkem bytí ${ textový styl 1}$ (jako v předchozím bodě).

Aplikace

Geometrická optika

V geometrické optice zrcadlový odraz lze vyjádřit pomocí matice Householder (viz Zrcadlová reflexe § Vektorová formulace ).

Numerická lineární algebra

Transformace domácností jsou široce používány v numerická lineární algebra, vystupovat QR rozklady a je prvním krokem Algoritmus QR. Jsou také široce používány pro transformaci na a Hessenberg formulář. Pro symetrické nebo Hermitian matice, symetrie může být zachována, což má za následek tridiagonalizace.^[2]

QR rozklad

K výpočtu lze použít odrazy majitelů domů QR rozklady odrazem prvního jednoho sloupce matice na násobek vektoru standardní báze, výpočtem transformační matice, vynásobením původní maticí a následným opakováním dolů ${ textstyle (i, i)}$ nezletilí tohoto produktu.

Tridiagonalizace

Tento postup je uveden v Numerické analýze Burden and Faires.^[3]V prvním kroku, abychom vytvořili matici Householder v každém kroku, musíme určit ${ textstyle alpha}$ a ${ textstyle r}$, což jsou:

${ displaystyle { begin {aligned} alpha & = - operatorname {sgn} left (a_ {21} right) { sqrt { sum _ {j = 2} ^ {n} a_ {j1} ^ {2}}}; r & = { sqrt {{ frac {1} {2}} left ( alpha ^ {2} -a_ {21} alpha right)}}; end {zarovnáno }}}$

Z ${ textstyle alpha}$ a ${ textstyle r}$, postavit vektor ${ textstyle v}$:

${ displaystyle v ^ {(1)} = { begin {bmatrix} v_ {1} v_ {2} vdots v_ {n} end {bmatrix}},}$

kde ${ textstyle v_ {1} = 0}$, ${ textstyle v_ {2} = { frac {a_ {21} - alpha} {2r}}}$, a

${ displaystyle v_ {k} = { frac {a_ {k1}} {2r}}}$ pro každého ${ displaystyle k = 3,4 ldots n}$

Poté vypočítat:

${ displaystyle { begin {aligned} P ^ {1} & = I-2v ^ {(1)} left (v ^ {(1)} right) ^ { textyf {T}} A ^ {(2)} & = P ^ {1} AP ^ {1} end {aligned}}}$

Po nalezení ${ textový styl P ^ {1}}$ a vypočítané ${ textstyle A ^ {(2)}}$ proces se opakuje pro ${ textstyle k = 2,3, ldots, n-2}$ jak následuje:

${ displaystyle { begin {aligned} alpha & = - operatorname {sgn} left (a_ {k + 1, k} ^ {k} right) { sqrt { sum _ {j = k + 1 } ^ {n} left (a_ {jk} ^ {k} right) ^ {2}}} r & = { sqrt {{ frac {1} {2}} left ( alpha ^ { 2} -a_ {k + 1, k} ^ {k} alpha right)}} v_ {1} ^ {k} & = v_ {2} ^ {k} = cdots = v_ {k} ^ {k} = 0 v_ {k + 1} ^ {k} & = { frac {a_ {k + 1, k} ^ {k} - alpha} {2r}} v_ {j} ^ {k} & = { frac {a_ {jk} ^ {k}} {2r}} { text {pro}} j = k + 2, k + 3, ldots, n P ^ {k} & = I-2v ^ {(k)} left (v ^ {(k)} right) ^ { Textyf {T}} A ^ {(k + 1)} & = P ^ {k} A ^ {(k)} P ^ {k} end {zarovnáno}}}$

Pokračováním tímto způsobem se vytvoří tridiagonální a symetrická matice.

Příklady

V tomto příkladu také z Burdern and Faires,^[3] daná matice je transformována na podobnou trojlodní matici A₃ pomocí metody Householder.

${ displaystyle mathbf {A} = { begin {bmatrix} 4 & 1 & -2 & 2 1 & 2 & 0 & 1 - 2 & 0 & 3 & -2 2 & 1 & -2 & -1 end {bmatrix}},}$

Po těchto krocích v metodě Householder máme:

První matice majitelů domů:

${ displaystyle { begin {aligned} Q_ {1} & = { begin {bmatrix} 1 & 0 & 0 & 0 0 & -1 / 3 & 2/3 & -2 / 3 0 & 2/3 & 2/3 & 1/3 0 & -2 / 3 & 1/3 & 2/3 end {bmatrix}}, A_ {2} = Q_ {1} AQ_ {1} & = { begin {bmatrix} 4 & -3 a 0 & 0 - 3 & 10/3 & 1 & 4/3 0 & 1 & 5 / 3 a -4 / 3 0 a 4/3 a -4 / 3 a -1 end {bmatrix}}, end {zarovnáno}}}$

Použitý ${ textstyle A_ {2}}$ tvořit

${ displaystyle { begin {aligned} Q_ {2} & = { begin {bmatrix} 1 & 0 & 0 & 0 0 & 1 & 0 & 0 0 & 0 & -3 / 5 & -4 / 5 0 & 0 & -4 / 5 & 3/5 end {bmatrix} }, A_ {3} = Q_ {2} A_ {2} Q_ {2} & = { begin {bmatrix} 4 & -3 a 0 & 0 - 3 & 10/3 & -5 / 3 & 0 0 & -5 / 3 & - 33/25 a 68/75 0 a 0 a 68/75 a 149/75 end {bmatrix}}, end {zarovnáno}}}$

Jak vidíme, konečným výsledkem je tridiagonální symetrická matice, která je podobná té původní. Proces je dokončen po dvou krocích.

Výpočtový a teoretický vztah k dalším unitárním transformacím

Transformace Householder je odrazem nad hyperplánem s jednotkovým normálním vektorem ${ textstyle v}$, jak již bylo uvedeno výše. An ${ textstyle N}$-podle-${ textstyle N}$ unitární transformace ${ textový styl}$ splňuje ${ textstyle UU ^ { textyf {H}} = I}$. Vezmeme-li determinant (${ textstyle N}$-tá síla geometrického průměru) a stopa (úměrná aritmetickému průměru) unitární matice odhalí, že její vlastní hodnoty ${ textstyle lambda _ {i}}$ mít jednotkový modul. To lze vidět přímo a rychle:

${ displaystyle { frac { operatorname {Trace} left (UU ^ { textyf {H}} right)} {N}} = { frac { sum _ {j = 1} ^ {N} left | lambda _ {j} right | ^ {2}} {N}} = 1, quad operatorname {det} left (UU ^ { textyf {H}} right) = prod _ { j = 1} ^ {N} vlevo | lambda _ {j} vpravo | ^ {2} = 1.}$

Protože aritmetické a geometrické průměry jsou stejné, pokud jsou proměnné konstantní (viz nerovnost aritmetických a geometrických prostředků ), stanovíme nárok na jednotkový modul.

Pro případ jednotných matic se skutečnou hodnotou získáme ortogonální matice, ${ textstyle UU ^ { textyf {T}} = I}$. Z toho vyplývá poměrně snadno (viz ortogonální matice ), kterou může být libovolná ortogonální matice rozložený do produktu o rotaci 2 o 2, tzv Dává rotace a úvahy majitelů domů. To je intuitivně přitažlivé, protože násobení vektoru ortogonální maticí zachovává délku tohoto vektoru a rotace a odrazy vyčerpávají množinu geometrických operací (se skutečnou hodnotou), které činí invariantní délku vektoru.

Ukázalo se, že transformace Householder má vztah one-to-one s kanonickým cosetovým rozkladem unitárních matic definovaných v teorii grup, které lze použít k velmi účinnému parametrizaci unitárních operátorů.^[4]

Nakonec si všimneme, že jediná transformace Householder může na rozdíl od solitární Givensovy transformace působit na všechny sloupce matice a jako taková vykazuje nejnižší výpočetní náklady na QR rozklad a tridiagonalizaci. Trestem za tuto „výpočetní optimalitu“ je samozřejmě to, že operace majitelů domů nemohou být tak hluboce a efektivně paralelizovány. Jako takový je Householder preferován pro husté matice na sekvenčních strojích, zatímco Givens je preferován pro řídké matice a / nebo paralelní stroje.

Reference

• LaBudde, C.D. (1963). Msgstr "Redukce libovolné reálné čtvercové matice na tridiagonální formu pomocí transformací podobnosti". Matematika výpočtu. Americká matematická společnost. 17 (84): 433–437. doi:10.2307/2004005. JSTOR  2004005. PAN  0156455.
• Morrison, D.D. (1960). „Poznámky k jednotné triangularizaci nesymetrické matice“. Deník ACM. 7 (2): 185–186. doi:10.1145/321021.321030. PAN  0114291.
• Cipra, Barry A. (2000). „To nejlepší 20. století: Redaktoři jmenují top 10 algoritmů“. 33 (4): 1. Citovat deník vyžaduje | deník = (Pomoc) (Zde je Transformace pro majitele domů uváděna jako top 10 algoritmus tohoto století)
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Oddíl 11.3.2. Metoda domácnosti“. Numerické recepty: Umění vědecké práce na počítači (3. vyd.). New York: Cambridge University Press. ISBN  978-0-521-88068-8.