Transformarea gospodarilor

În matematică , o transformare Householder într-un spațiu tridimensional este reflectarea vectorilor față de un plan care trece prin origine. În general, într-un spațiu euclidian este o transformare liniară care descrie o reflecție față de un hiperplan care conține originea.

Transformarea Householder a fost introdusă în 1958 de matematicianul american Alston Scott Householder ( 1905 - 1993 ). Aceasta poate fi utilizată pentru a obține o factorizare QR a unei matrice .

Definiție și proprietăți

Reflectarea unui punct $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf x$ cu privire la un hiperplan, definit ca ortogonal la o unitate vectorială $\mathbf {u}$ ${\ displaystyle \ mathbf {u}}$ ${\ mathbf u}$ , este dat de:

\mathbf {x} -2\langle \mathbf {x} ,\mathbf {u} \rangle \mathbf {u} =\mathbf {x} -2\mathbf {u} (\mathbf {u} ^{\text{T}}\mathbf {x} )

{\ displaystyle \ mathbf {x} -2 \ langle \ mathbf {x}, \ mathbf {u} \ rangle \ mathbf {u} = \ mathbf {x} -2 \ mathbf {u} (\ mathbf {u} ^ {\ text {T}} \ mathbf {x})}

{\ displaystyle \ mathbf {x} -2 \ langle \ mathbf {x}, \ mathbf {u} \ rangle \ mathbf {u} = \ mathbf {x} -2 \ mathbf {u} (\ mathbf {u} ^ {\ text {T}} \ mathbf {x})}

unde este $\langle ,\rangle$ ${\ displaystyle \ langle, \ rangle}$ $\ langle, \ rangle$ denotă produsul scalar euclidian, analog cu produsul dintre matrice , care definește distanța de $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf x$ din hiperplan, în timp ce $\mathbf {u} ^{T}$ ${\ displaystyle \ mathbf {u} ^ {T}}$ ${\ displaystyle \ mathbf {u} ^ {T}}$ denotă transpunerea ( transpunerea conjugată în cazul complex) a vectorului $\mathbf {u}$ ${\ displaystyle \ mathbf {u}}$ ${\ mathbf u}$ (destinat ca o matrice cu o singură coloană). Este o transformare liniară care este reprezentată de matricea Householder :

U=I-2\mathbf {u} \mathbf {u} ^{T}

{\ displaystyle U = I-2 \ mathbf {u} \ mathbf {u} ^ {T}}

{\ displaystyle U = I-2 \ mathbf {u} \ mathbf {u} ^ {T}}

unde este $THE$ ${\ displaystyle I}$ $THE$ Este matricea identitate .

Matricea Householder are următoarele proprietăți:

este o matrice hermitiană ( simetrică ), adică $U=U^{T}$ ${\ displaystyle U = U ^ {T}}$ ${\ displaystyle U = U ^ {T}}$ . Intr-adevar:

U^{T}=(I-2\mathbf {u} \mathbf {u} ^{T})^{T}=I-2(\mathbf {u} \mathbf {u} ^{T})^{T}=I-2((\mathbf {u} ^{T})^{T}\mathbf {u} ^{T})=I-2\mathbf {u} \mathbf {u} ^{T}=U

{\ displaystyle U ^ {T} = (I-2 \ mathbf {u} \ mathbf {u} ^ {T}) ^ {T} = I-2 (\ mathbf {u} \ mathbf {u} ^ {T }) ^ {T} = I-2 ((\ mathbf {u} ^ {T}) ^ {T} \ mathbf {u} ^ {T}) = I-2 \ mathbf {u} \ mathbf {u} ^ {T} = U}

{\ displaystyle U ^ {T} = (I-2 \ mathbf {u} \ mathbf {u} ^ {T}) ^ {T} = I-2 (\ mathbf {u} \ mathbf {u} ^ {T }) ^ {T} = I-2 ((\ mathbf {u} ^ {T}) ^ {T} \ mathbf {u} ^ {T}) = I-2 \ mathbf {u} \ mathbf {u} ^ {T} = U}

este ortogonală , adică $U^{T}=U^{-1}$ ${\ displaystyle U ^ {T} = U ^ {- 1}}$ ${\ displaystyle U ^ {T} = U ^ {- 1}}$ , acesta este $U^{T}U=I$ ${\ displaystyle U ^ {T} U = I}$ ${\ displaystyle U ^ {T} U = I}$ . Intr-adevar:

{\begin{aligned}U^{T}U&=UU\\&=(I-2\mathbf {u} \mathbf {u} ^{T})(I-2\mathbf {u} \mathbf {u} ^{T})\\&=I-4\mathbf {u} \mathbf {u} ^{T}+4\mathbf {u} \underbrace {\mathbf {u} ^{T}\mathbf {u} } _{\lVert \mathbf {u} \rVert =1}\mathbf {u} ^{T}\\&=I-4\mathbf {u} \mathbf {u} ^{T}+4\mathbf {u} \mathbf {u} ^{T}\\&=I\end{aligned}}

{\ displaystyle {\ begin {align} U ^ {T} U & = UU \\ & = (I-2 \ mathbf {u} \ mathbf {u} ^ {T}) (I-2 \ mathbf {u} \ mathbf {u} ^ {T}) \\ & = I-4 \ mathbf {u} \ mathbf {u} ^ {T} +4 \ mathbf {u} \ underbrace {\ mathbf {u} ^ {T} \ mathbf {u}} _ {\ lVert \ mathbf {u} \ rVert = 1} \ mathbf {u} ^ {T} \\ & = I-4 \ mathbf {u} \ mathbf {u} ^ {T} + 4 \ mathbf {u} \ mathbf {u} ^ {T} \\ & = I \ end {align}}}

{\ displaystyle {\ begin {align} U ^ {T} U & = UU \\ & = (I-2 \ mathbf {u} \ mathbf {u} ^ {T}) (I-2 \ mathbf {u} \ mathbf {u} ^ {T}) \\ & = I-4 \ mathbf {u} \ mathbf {u} ^ {T} +4 \ mathbf {u} \ underbrace {\ mathbf {u} ^ {T} \ mathbf {u}} _ {\ lVert \ mathbf {u} \ rVert = 1} \ mathbf {u} ^ {T} \\ & = I-4 \ mathbf {u} \ mathbf {u} ^ {T} + 4 \ mathbf {u} \ mathbf {u} ^ {T} \\ & = I \ end {align}}}

S-a demonstrat astfel că $U$ ${\ displaystyle U}$ $U$ este o involuție , adică $U^{2}=I$ ${\ displaystyle U ^ {2} = I}$ ${\ displaystyle U ^ {2} = I}$ .
Are doar valori proprii egale cu $\pm 1$ ${\ displaystyle \ pm 1}$ $\ pm 1$ .
Determinantul (produsul valorilor proprii) este $-1$ ${\ displaystyle -1}$ ${\ displaystyle -1}$ .

Matricile gospodăriei sunt un caz special al matricilor elementare .

Aplicarea matricei de transformare

Matricea Gospodarului $U$ ${\ displaystyle U}$ $U$ poate fi folosit pentru a anula toate, cu excepția primei componente a unui vector, după cum urmează. Sunt:

\mathbf {x} ={\begin{pmatrix}x_{1}\\\vdots \\x_{n}\end{pmatrix}}\qquad \mathbf {e} _{1}={\begin{pmatrix}1\\0\\\vdots \\0\end{pmatrix}}

{\ displaystyle \ mathbf {x} = {\ begin {pmatrix} x_ {1} \\\ vdots \\ x_ {n} \ end {pmatrix}} \ qquad \ mathbf {e} _ {1} = {\ begin {pmatrix} 1 \\ 0 \\\ vdots \\ 0 \ end {pmatrix}}}

{\ displaystyle \ mathbf {x} = {\ begin {pmatrix} x_ {1} \\\ vdots \\ x_ {n} \ end {pmatrix}} \ qquad \ mathbf {e} _ {1} = {\ begin {pmatrix} 1 \\ 0 \\\ vdots \\ 0 \ end {pmatrix}}}

și este definit:

\sigma =\|\mathbf {x} \|\qquad \mathbf {v} =\mathbf {x} +\sigma \mathbf {e} _{1}={\begin{pmatrix}x_{1}+\sigma \\x_{2}\\\vdots \\x_{n}\end{pmatrix}}

{\ displaystyle \ sigma = \ | \ mathbf {x} \ | \ qquad \ mathbf {v} = \ mathbf {x} + \ sigma \ mathbf {e} _ {1} = {\ begin {pmatrix} x_ {1 } + \ sigma \\ x_ {2} \\\ vdots \\ x_ {n} \ end {pmatrix}}}

{\ displaystyle \ sigma = \ | \ mathbf {x} \ | \ qquad \ mathbf {v} = \ mathbf {x} + \ sigma \ mathbf {e} _ {1} = {\ begin {pmatrix} x_ {1 } + \ sigma \\ x_ {2} \\\ vdots \\ x_ {n} \ end {pmatrix}}}

Da, pentru unul $U=I-\lambda \mathbf {v} \mathbf {v} ^{T}$ ${\ displaystyle U = I- \ lambda \ mathbf {v} \ mathbf {v} ^ {T}}$ ${\ displaystyle U = I- \ lambda \ mathbf {v} \ mathbf {v} ^ {T}}$ cu $\lambda$ ${\ displaystyle \ lambda}$ $\ lambda$ adecvat, că:

U\mathbf {x} ={\begin{pmatrix}-\sigma \\0\\\vdots \\0\end{pmatrix}}

{\ displaystyle U \ mathbf {x} = {\ begin {pmatrix} - \ sigma \\ 0 \\\ vdots \\ 0 \ end {pmatrix}}}

{\ displaystyle U \ mathbf {x} = {\ begin {pmatrix} - \ sigma \\ 0 \\\ vdots \\ 0 \ end {pmatrix}}}

Într-adevăr, definitorie ${\frac {1}{\lambda }}=\alpha$ ${\ displaystyle {\ frac {1} {\ lambda}} = \ alpha}$ ${\ displaystyle {\ frac {1} {\ lambda}} = \ alpha}$ unde este

\alpha ={\frac {\|\mathbf {v} \|^{2}}{2}}={\frac {\mathbf {v} ^{T}\mathbf {v} }{2}}={\frac {(\mathbf {x} +\sigma \mathbf {e} _{1})^{T}(\mathbf {x} +\sigma \mathbf {e} _{1})}{2}}={\frac {\overbrace {\mathbf {x} ^{T}\mathbf {x} } ^{\|\mathbf {x} \|^{2}=\sigma ^{2}}+2\sigma x_{1}+\sigma ^{2}}{2}}=\sigma ^{2}+\sigma x_{1}

{\ displaystyle \ alpha = {\ frac {\ | \ mathbf {v} \ | ^ {2}} {2}} = {\ frac {\ mathbf {v} ^ {T} \ mathbf {v}} {2 }} = {\ frac {(\ mathbf {x} + \ sigma \ mathbf {e} _ {1}) ^ {T} (\ mathbf {x} + \ sigma \ mathbf {e} _ {1})} {2}} = {\ frac {\ overbrace {\ mathbf {x} ^ {T} \ mathbf {x}} ^ {\ | \ mathbf {x} \ | ^ {2} = \ sigma ^ {2}} +2 \ sigma x_ {1} + \ sigma ^ {2}} {2}} = \ sigma ^ {2} + \ sigma x_ {1}}

{\ displaystyle \ alpha = {\ frac {\ | \ mathbf {v} \ | ^ {2}} {2}} = {\ frac {\ mathbf {v} ^ {T} \ mathbf {v}} {2 }} = {\ frac {(\ mathbf {x} + \ sigma \ mathbf {e} _ {1}) ^ {T} (\ mathbf {x} + \ sigma \ mathbf {e} _ {1})} {2}} = {\ frac {\ overbrace {\ mathbf {x} ^ {T} \ mathbf {x}} ^ {\ | \ mathbf {x} \ | ^ {2} = \ sigma ^ {2}} +2 \ sigma x_ {1} + \ sigma ^ {2}} {2}} = \ sigma ^ {2} + \ sigma x_ {1}}

avem:

U\mathbf {x} =\left(I-{\frac {1}{\alpha }}\mathbf {v} \mathbf {v} ^{T}\right)\mathbf {x} =\mathbf {x} -{\frac {1}{\alpha }}\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)^{T}\mathbf {x} =\mathbf {x} -{\frac {1}{\alpha }}\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)\left(\sigma ^{2}+\sigma x_{1}\right)=\mathbf {x} -{\frac {1}{\alpha }}\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)\alpha =\mathbf {x} -\mathbf {x} -\sigma \mathbf {e} _{1}=-\sigma \mathbf {e} _{1}

{\ displaystyle U \ mathbf {x} = \ left (I - {\ frac {1} {\ alpha}} \ mathbf {v} \ mathbf {v} ^ {T} \ right) \ mathbf {x} = \ mathbf {x} - {\ frac {1} {\ alpha}} \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) ^ {T} \ mathbf {x} = \ mathbf {x} - {\ frac {1} {\ alpha}} \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) \ left (\ sigma ^ {2} + \ sigma x_ {1} \ right) = \ mathbf {x} - {\ frac {1} {\ alpha}} \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) \ alpha = \ mathbf {x} - \ mathbf {x} - \ sigma \ mathbf {e} _ {1} = - \ sigma \ mathbf {e} _ {1}}

{\ displaystyle U \ mathbf {x} = \ left (I - {\ frac {1} {\ alpha}} \ mathbf {v} \ mathbf {v} ^ {T} \ right) \ mathbf {x} = \ mathbf {x} - {\ frac {1} {\ alpha}} \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) ^ {T} \ mathbf {x} = \ mathbf {x} - {\ frac {1} {\ alpha}} \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) \ left (\ sigma ^ {2} + \ sigma x_ {1} \ right) = \ mathbf {x} - {\ frac {1} {\ alpha}} \ left (\ mathbf {x} + \ sigma \ mathbf {e} _ {1} \ right) \ alpha = \ mathbf {x} - \ mathbf {x} - \ sigma \ mathbf {e} _ {1} = - \ sigma \ mathbf {e} _ {1}}

Factorizarea QR

Același subiect în detaliu: Descompunerea QR .

Este $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf x$ un vector arbitrar de coloană m- dimensională în lungime $|\alpha |$ ${\ displaystyle | \ alpha |}$ ${\ displaystyle | \ alpha |}$ (pentru stabilitatea numerică a metodei se presupune că $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ are același semn ca prima coordonată a $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf x$ ). De sine $\mathbf {e} _{1}$ ${\ displaystyle \ mathbf {e} _ {1}}$ ${\ mathbf e} _ {1}$ este vectorul $(1,0,\dots ,0)^{T}$ ${\ displaystyle (1,0, \ dots, 0) ^ {T}}$ ${\ displaystyle (1,0, \ dots, 0) ^ {T}}$ , considera:

\mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1}\qquad \mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}\qquad Q=I-2\mathbf {v} \mathbf {v} ^{t}

{\ displaystyle \ mathbf {u} = \ mathbf {x} - \ alpha \ mathbf {e} _ {1} \ qquad \ mathbf {v} = {\ frac {\ mathbf {u}} {\ | \ mathbf { u} \ |}} \ qquad Q = I-2 \ mathbf {v} \ mathbf {v} ^ {t}}

{\ displaystyle \ mathbf {u} = \ mathbf {x} - \ alpha \ mathbf {e} _ {1} \ qquad \ mathbf {v} = {\ frac {\ mathbf {u}} {\ | \ mathbf { u} \ |}} \ qquad Q = I-2 \ mathbf {v} \ mathbf {v} ^ {t}}

Având în vedere matricea Gospodarului $Î$ ${\ displaystyle Q}$ $Î$ , datorită celor de mai sus, avem:

Q\mathbf {x} =(\alpha ,0,\dots ,0)^{T}

{\ displaystyle Q \ mathbf {x} = (\ alpha, 0, \ dots, 0) ^ {T}}

{\ displaystyle Q \ mathbf {x} = (\ alpha, 0, \ dots, 0) ^ {T}}

iar acest rezultat poate fi folosit pentru a transforma treptat o matrice $LA$ ${\ displaystyle A}$ $LA$ de tip $m\times n$ ${\ displaystyle m \ times n}$ $m \ ori n$ în forma triunghiulară superioară : în primul rând se înmulțește $LA$ ${\ displaystyle A}$ $LA$ pentru matricea Gospodarului $Q_{1}$ ${\ displaystyle Q_ {1}}$ $Q_1$ obținută prin alegere $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf x$ pentru prima sa coloană. Acest lucru are ca rezultat o matrice $Î LA$ ${\ displaystyle QA}$ ${\ displaystyle QA}$ care are zerouri în coloana din stânga, cu excepția numai primul rând:

Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}

{\ displaystyle Q_ {1} A = {\ begin {bmatrix} \ alpha _ {1} & \ star & \ dots & \ star \\ 0 &&& \\\ vdots && A '& \\ 0 &&& \ end {bmatrix }}}

{\ displaystyle Q_ {1} A = {\ begin {bmatrix} \ alpha _ {1} & \ star & \ dots & \ star \\ 0 &&& \\\ vdots && A '& \\ 0 &&& \ end {bmatrix }}}

Această schimbare poate fi repetată pentru ${LA}^{'}$ ${\ displaystyle A '}$ $LA'$ printr-o matrice Housholder $Q_{2}$ ${\ displaystyle Q_ {2}}$ $Q_2$ . Rețineți că $Q_{2}$ ${\ displaystyle Q_ {2}}$ $Q_2$ este mai mic decât $Q_{1}$ ${\ displaystyle Q_ {1}}$ $Q_1$ . Din moment ce doriți să fie real, să operați $Q_{1}A$ ${\ displaystyle Q_ {1} A}$ ${\ displaystyle Q_ {1} A}$ in loc de ${LA}^{'}$ ${\ displaystyle A '}$ $LA'$ trebuie să extindeți acest lucru în stânga sus, completându-l cu 1 intrări sau, în general:

Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}

{\ displaystyle Q_ {k} = {\ begin {bmatrix} I_ {k-1} și 0 \\ 0 & Q_ {k} '\ end {bmatrix}}}

{\ displaystyle Q_ {k} = {\ begin {bmatrix} I_ {k-1} și 0 \\ 0 & Q_ {k} '\ end {bmatrix}}}

După $t$ ${\ displaystyle t}$ $t$ iterații ale acestui proces, cu $t=\min(m-1,n)$ ${\ displaystyle t = \ min (m-1, n)}$ ${\ displaystyle t = \ min (m-1, n)}$ , ajungem la:

R=Q_{t}\dots Q_{2}Q_{1}A

{\ displaystyle R = Q_ {t} \ dots Q_ {2} Q_ {1} A}

{\ displaystyle R = Q_ {t} \ dots Q_ {2} Q_ {1} A}

care este o matrice triunghiulară superioară. Astfel, cu:

Q=Q_{1}Q_{2}\dots Q_{t}

{\ displaystyle Q = Q_ {1} Q_ {2} \ dots Q_ {t}}

{\ displaystyle Q = Q_ {1} Q_ {2} \ dots Q_ {t}}

descompunere $A=QR$ ${\ displaystyle A = QR}$ ${\ displaystyle A = QR}$ este o descompunere QR a $LA$ ${\ displaystyle A}$ $LA$ . Această metodă este stabilă numeric.

Bibliografie

( EN ) WH Press, SA Teukolsky, WT Vetterling și BP Flannery, secțiunea 11.3.2. Metoda Householder , în Rețete Numerice: Arta Computării Științifice , 3rd, New York, Cambridge University Press, 2007, ISBN 978-0-521-88068-8 .
( EN ) Householder, AS Principiile analizei numerice . New York: McGraw-Hill, pp. 135-138, 1953.
( EN ) Lehoucq, RB "Calculul matricilor unitare elementare." ACM Trans. Matematica. Software 22 , 393-400, 1996.
( EN ) Trefethen, LN și Bau, D. III. Algebra liniară numerică . Philadelphia, PA: SIAM, 1997.

Elemente conexe

linkuri externe

(EN) Eric W. Weisstein, Householder Matrix, în MathWorld Wolfram Research.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică