Householder变换

Householder变换 https://www.cnblogs.com/reasno/p/9606224.html Householder transformation https://en.wikipedia.org/wiki/Householder_transformation [矩阵的QR分解系列三] 豪斯霍尔德(Householder)变换 https://blog.csdn.net/honyniu/article/details/110351391 北化 矩阵论

Householder矩阵： H = I − 2 w w H H = I - 2ww^H H=I−2wwH， w w w为单位列向量 Householder矩阵性质：厄米特矩阵、正交矩阵、对合矩阵、反射矩阵 注：如果一个对合矩阵也是厄米特矩阵，那么它也是正交矩阵

Householder变换(初等反射阵或镜象变换阵)：将向量 x x x通过Householder矩阵 H H H变换为 H x Hx Hx x x x与 H x Hx Hx关于一个超平面对称，该超平面与 w w w垂直。 H x Hx Hx是 x x x关于与 w w w垂直的超平面的镜面反射。 H x = x − 2 w w H x = x − 2 < x , w > w Hx = x - 2ww^H x = x - 2w Hx=x−2wwHx=x−2w x x x减去 x x x在 w w w上的投影分量，便是位于超平面内的 u u u u u u减去 x x x在 w w w上的投影分量，便是 x x x的反射向量 H x Hx Hx

x x x和其反射向量 H x Hx Hx可以分解为 u u u与 w w w x = u + α w x = u + \alpha w x=u+αw H x = u − α w Hx = u - \alpha w Hx=u−αw α \alpha α为一个常数

H x = x − 2 w w H x Hx = x - 2ww^H x Hx=x−2wwHx 可写作： H x = y Hx = y Hx=y

定理：H为householder矩阵，则 [ I r 0 0 H ] \begin{bmatrix} I_r & 0 \\ 0 & H\end{bmatrix} [Ir​0​0H​]也是为householder矩阵

证明： [ I r 0 0 H ] = [ I r 0 0 I n − 2 w w H ] = I n + r − [ 0 0 0 2 w w H ] = I n + r − 2 [ 0 u ] [ 0 H u H ] = I n + r − 2 u 1 u 1 H \begin{bmatrix} I_r & 0 \\ 0 & H\end{bmatrix} = \begin{bmatrix} I_r & 0 \\ 0 & I_n - 2ww^H \end{bmatrix} = I_{n+r} - \begin{bmatrix} 0 & 0 \\ 0 & 2ww^H \end{bmatrix} = I_{n+r} - 2\begin{bmatrix} 0 \\ u \end{bmatrix} \begin{bmatrix} 0^H & u^H \end{bmatrix} = I_{n+r} - 2u_1 u_1^H [Ir​0​0H​]=[Ir​0​0In​−2wwH​]=In+r​−[00​02wwH​]=In+r​−2[0u​][0H​uH​]=In+r​−2u1​u1H​

H = I − 2 w w H H = I - 2ww^H H=I−2wwH 定理：必存在 H x = ± ∣ ∣ x ∣ ∣ z , ∣ ∣ z ∣ ∣ = 1 Hx = \pm ||x|| z, ||z||=1 Hx=±∣∣x∣∣z,∣∣z∣∣=1

证明： x = 0 x=0 x=0，任取 w w w，则 H x = ± ∣ ∣ x ∣ ∣ z Hx=\pm ||x|| z Hx=±∣∣x∣∣z，定理在这种情况下成立 x = ± ∣ ∣ x ∣ ∣ z x = \pm ||x|| z x=±∣∣x∣∣z，取与 x x x正交的 w w w，则 H x = x = ± ∣ ∣ x ∣ ∣ z Hx=x=\pm ||x|| z Hx=x=±∣∣x∣∣z，定理在这种情况下成立 x ≠ ± ∣ ∣ x ∣ ∣ z x \neq \pm ||x|| z x​=±∣∣x∣∣z，取 w = x − α z ∣ ∣ x − α z ∣ ∣ w = \frac{x- \alpha z}{||x - \alpha z||} w=∣∣x−αz∣∣x−αz​，则 H x = x − 2 ( x − α z ) ( x − α z ) H ∣ ∣ x − α z ∣ ∣ 2 x = α z = ± ∣ ∣ x ∣ ∣ z Hx = x - 2\frac{(x- \alpha z)(x- \alpha z)^H}{||x - \alpha z||^2}x = \alpha z = \pm ||x|| z Hx=x−2∣∣x−αz∣∣2(x−αz)(x−αz)H​x=αz=±∣∣x∣∣z，定理在这种情况下成立

推论： x x x与 e 1 e_1 e1​不共线，取 w = x − α e 1 ∣ ∣ x − α e 1 ∣ ∣ w = \frac{x- \alpha e_1}{||x - \alpha e_1||} w=∣∣x−αe1​∣∣x−αe1​​，则 H x = ± ∣ ∣ x ∣ ∣ e 1 Hx = \pm ||x|| e_1 Hx=±∣∣x∣∣e1​

H H H为正交矩阵，则其有 n n n个特征对 如果 x x x与 w w w垂直，则 H x = x Hx = x Hx=x 如果 x = w x=w x=w垂直，则 H w = − w Hw = -w Hw=−w n n n维空间存在 n − 1 n-1 n−1个向量与 w w w垂直 因此可以看出 H H H的n个特征对： n − 1 n-1 n−1个 ( 1 , x i ) (1,x_i) (1,xi​)和1个 ( − 1 , w ) (-1,w) (−1,w) 因此 H H H的行列式为-1

矩阵 A = [ a 1 , . . . , a n ] A = [a_1, ..., a_n] A=[a1​,...,an​]，实现 A = Q R A = QR A=QR 利用 n − 1 n-1 n−1个Householder矩阵 H i H_i Hi​对 A A A进行变换，使得 H n − 1 . . . H 2 H 1 A = R H_{n-1}...H_2 H_1 A = R Hn−1​...H2​H1​A=R， Q = H 1 H 2 . . . H n − 1 Q=H_1H_2...H_{n-1} Q=H1​H2​...Hn−1​

如果 a 1 ≠ 0 a_1 \neq 0 a1​​=0，有 H 1 a 1 = α 1 e 1 H_1 a_1 = \alpha_1 e_1 H1​a1​=α1​e1​ H 1 A n = [ α 1 ∗ 0 B n − 1 ] H_1 A_n = \begin{bmatrix} \alpha_1 & * \\ 0 & B_{n-1} \end{bmatrix} H1​An​=[α1​0​∗Bn−1​​] 如果 a 1 = 0 a_1 = 0 a1​=0，则不需要进行householder变换，也可以说 H 1 = I H_1=I H1​=I

B n − 1 = [ b 1 , . . . , b n − 1 ] B_{n-1} = [b_1, ..., b_{n-1}] Bn−1​=[b1​,...,bn−1​] 如果 b 1 ≠ 0 b_1 \neq 0 b1​​=0，有 H 2 ~ b 1 = α 2 e 1 ~ \tilde{H_2} b_1 = \alpha_2 \tilde{e_1} H2​~​b1​=α2​e1​~​ H 2 ~ B n − 1 = [ α 2 ∗ 0 C n − 2 ] \tilde{H_2} B_{n-1} = \begin{bmatrix} \alpha_2 & * \\ 0 & C_{n-2} \end{bmatrix} H2​~​Bn−1​=[α2​0​∗Cn−2​​] 如果 b 1 = 0 b_1 = 0 b1​=0，则 H 2 ~ = I \tilde{H_2}=I H2​~​=I H 2 = [ 1 0 T 0 H 2 ~ ] H_2 = \begin{bmatrix} 1 & 0^T \\ 0 & \tilde{H_2} \end{bmatrix} H2​=[10​0TH2​~​​]

也就是说对于n维矩阵，如果其列向量都不为0，用 n − 1 n-1 n−1个Householder矩阵就能实现正交分解

Householder变换的另一个作用便是实现 A A A的正交化，将 A A A变为 Q Q Q

例1：通过Householder变换，使得 x = [ − 3 , 0 , 0 , 4 ] T x = [-3,0,0,4]^T x=[−3,0,0,4]T与 e 1 e_1 e1​同向

解1： α = ∣ ∣ x ∣ ∣ = 5 \alpha = ||x|| = 5 α=∣∣x∣∣=5 w = x − 5 e 1 ∣ ∣ x − 5 e 1 ∣ ∣ = 1 80 [ − 8 , 0 , 0 , 4 ] T w = \frac{x- 5e_1}{||x - 5 e_1||} = \frac{1}{\sqrt{80}}[-8,0,0,4]^T w=∣∣x−5e1​∣∣x−5e1​​=80 ​1​[−8,0,0,4]T H x = x − 2 w w T x = 5 e 1 Hx = x - 2ww^Tx = 5e_1 Hx=x−2wwTx=5e1​

解2： α = ∣ ∣ x ∣ ∣ = − 5 \alpha = ||x|| = -5 α=∣∣x∣∣=−5 w = x + 5 e 1 ∣ ∣ x + 5 e 1 ∣ ∣ = 1 20 [ 2 , 0 , 0 , 4 ] T w = \frac{x + 5e_1}{||x + 5 e_1||} = \frac{1}{\sqrt{20}}[2,0,0,4]^T w=∣∣x+5e1​∣∣x+5e1​​=20 ​1​[2,0,0,4]T H x = x − 2 w w T x = − 5 e 1 Hx = x - 2ww^Tx = -5e_1 Hx=x−2wwTx=−5e1​

例2：通过Householder变换，使得 A = [ 0 3 1 0 4 − 2 2 1 2 ] A = \begin{bmatrix} 0 & 3 & 1 \\ 0 & 4 & -2 \\ 2 & 1 & 2 \end{bmatrix} A=⎣⎡​002​341​1−22​⎦⎤​实现正交分解

解： a 1 = [ 0 0 2 ] a_1 = \begin{bmatrix} 0 \\ 0 \\2 \end{bmatrix} a1​=⎣⎡​002​⎦⎤​， α 1 = ∣ ∣ a 1 ∣ ∣ = 2 \alpha_1 = ||a_1|| = 2 α1​=∣∣a1​∣∣=2， w = a 1 − 2 e 1 ∣ ∣ a 1 − 2 e 1 ∣ ∣ = 1 2 [ − 1 0 1 ] w = \frac{a_1 - 2e_1}{||a_1 - 2 e_1||} = \frac{1}{\sqrt{2}}\begin{bmatrix} -1 \\ 0 \\1 \end{bmatrix} w=∣∣a1​−2e1​∣∣a1​−2e1​​=2 ​1​⎣⎡​−101​⎦⎤​ H 1 A = [ 2 1 2 0 4 − 2 0 3 1 ] H_1 A = \begin{bmatrix} 2 & 1 & 2 \\ 0 & 4 & -2 \\ 0 & 3 & 1 \end{bmatrix} H1​A=⎣⎡​200​143​2−21​⎦⎤​

b 1 = [ 4 3 ] b_1 = \begin{bmatrix} 4 \\ 3 \end{bmatrix} b1​=[43​]， α 2 = ∣ ∣ b 1 ∣ ∣ = 5 \alpha_2 = ||b_1|| = 5 α2​=∣∣b1​∣∣=5， w = b 1 − 5 e ~ 1 ∣ ∣ b 1 − 5 e ~ 1 ∣ ∣ = 1 10 [ − 1 3 ] w = \frac{b_1 - 5 \tilde e_1}{||b_1 - 5 \tilde e_1||} = \frac{1}{\sqrt{10}}\begin{bmatrix} -1 \\ 3 \end{bmatrix} w=∣∣b1​−5e~1​∣∣b1​−5e~1​​=10 ​1​[−13​] H 2 H 1 A = [ 2 1 2 0 5 − 1 0 0 − 2 ] H_2H_1 A = \begin{bmatrix} 2 & 1 & 2 \\ 0 & 5 & -1 \\ 0 & 0 & -2 \end{bmatrix} H2​H1​A=⎣⎡​200​150​2−1−2​⎦⎤​

A = Q [ 2 1 2 0 5 − 1 0 0 − 2 ] , Q = H 1 H 2 A = Q \begin{bmatrix} 2 & 1 & 2 \\ 0 & 5 & -1 \\ 0 & 0 & -2 \end{bmatrix}, Q = H_1H_2 A=Q⎣⎡​200​150​2−1−2​⎦⎤​,Q=H1​H2​

https://zh.wikipedia.org/wiki/正交补

W W W为内积空间 V V V的子空间，则 W W W的正交补 W ⊥ W^{\perp} W⊥定义为： W ⊥ = { x ∈ V : ∀ y ∈ W , < x , y > = 0 } W^{\perp} = \{ x \in V: \forall y \in W, =0 \} W⊥={x∈V:∀y∈W,=0} 注： W ⊥ W^{\perp} W⊥也是 V V V的子空间

W ⊥ ⊥ = W ˉ W^{\perp \perp} = \bar{W} W⊥⊥=Wˉ 疑问：线性空间 W W W与线性空间的闭包 W ˉ \bar{W} Wˉ有什么区别

A A A为一个矩阵， R o w A , C o l A , N u l A RowA, ColA, NulA RowA,ColA,NulA分别为其行空间，列空间，零空间 ( R o w A ) ⊥ = N u l A (RowA)^{\perp} = NulA (RowA)⊥=NulA ( C o l A ) ⊥ = N u l A T (ColA)^{\perp} = NulA^T (ColA)⊥=NulAT 注： A A A的右零空间是由 A x = 0 Ax=0 Ax=0的解张成的空间 A A A的左零空间是由 A T x = 0 A^Tx=0 ATx=0的解张成的空间

W W W为巴拿赫空间 V V V的子空间，则 W W W的正交补 W ⊥ W^{\perp} W⊥定义为： W ⊥ = { x ∈ V ∗ : ∀ y ∈ W , x ( y ) = 0 } W^{\perp} = \{ x \in V^*: \forall y \in W, x(y)=0 \} W⊥={x∈V∗:∀y∈W,x(y)=0} 注： W ⊥ W^{\perp} W⊥是 V V V的对偶空间的子空间 对偶空间是行向量与列向量关系的抽象化 疑问： V ∗ ∗ V^{**} V∗∗与 V V V的关系？

设 V V V为 在域 F F F上的向量空间，定义其对偶空间 V ∗ V^∗ V∗ 为由 V → F V \rightarrow F V→F 的所有线性函数的集合

V V V的元素称为反变或逆变contravariant向量； V ∗ V^* V∗的元素称为共变或协变covariant向量，也称余向量或同向量co-vectors，一形或线性型one-form