矩阵理论 |
您所在的位置：网站首页 › householder变换 › 矩阵理论 |
矩阵理论
|
Householder矩阵 / 镜射矩阵
由来：镜射变换
给定镜射超平面，其法向量为
v
\bold v
v（
∥
v
∥
=
1
\|\bold v\|=1
∥v∥=1） 对于任意向量
x
\bold x
x，其镜射变换后的向量为
x
−
2
v
(
v
T
x
)
=
(
I
−
2
v
v
T
)
x
\mathbf{x}-2\mathbf{v}(\mathbf{v}^T\mathbf{x})=(I-2\mathbf{v}\mathbf{v}^T)\mathbf{x}
x−2v(vTx)=(I−2vvT)x （因为
v
T
x
\mathbf{v}^T\mathbf{x}
vTx是向量
x
\bold x
x在法向量
v
\bold v
v上的投影长度，如图） 也可以从另一个角度来看：镜射变换与正交投影是“互补”的变换 矩阵 P \mathbf P P可将向量 x \mathbf{x} x 正交投影至（镜射超平面的）法向量 v \mathbf{v} v 因此，向量 x \mathbf{x} x 到镜射超平面 的正交投影点就是 x − P x = ( I − P ) x \mathbf{x}-P\mathbf{x}=(I-P)\mathbf{x} x−Px=(I−P)x 进而向量 x \mathbf{x} x 关于镜射超平面的 镜射点是 ( I − P ) x − P x = ( I − 2 P ) x = ( I − 2 v v T ) x (I-P)\mathbf{x}-P\mathbf{x}=(I-2P)\mathbf{x}=(I-2\mathbf{v}\mathbf{v}^T)\mathbf{x} (I−P)x−Px=(I−2P)x=(I−2vvT)x 也可得到镜射矩阵为 H = I − 2 v v T \bold H=\bold I-2\bold v\bold v^T H=I−2vvT Householder矩阵的特征向量Householder矩阵 H = I − 2 v v T \bold H=\bold I-2\bold v\bold v^T H=I−2vvT，相当于初等矩阵中 u = − 2 v \bold u=-2\bold v u=−2v 根据初等矩阵的特征向量知识，在 s p a n { v } ⊥ span\{\bold v\}^{\bot } span{v}⊥（即镜射超平面）中必有 n − 1 n-1 n−1个无关特征向量 { x 1 , x 2 , . . . , x n − 1 } \{\bold x_1,\bold x_2,...,\bold x_{n-1}\} {x1,x2,...,xn−1}（超平面的一组基），特征值全为1余下的特征向量有两种寻找方法 ①根据初等矩阵的特征向量知识，由于 u ∈ s p a n { v } \bold u\in span\{\bold v\} u∈span{v}， u = − 2 v \bold u=-2\bold v u=−2v也是一个特征向量，特征值 1 − 2 v T v = − 1 1-2\bold v^T\bold v=-1 1−2vTv=−1 ②也可直接由镜射的几何意义知，镜射超平面的法向量 v \bold v v是特征向量，特征值 − 1 -1 −1根据特征值 { 1 , 1 , 1 , . . . , 1 , − 1 } \{1,1,1,...,1,-1\} {1,1,1,...,1,−1}可知，行列式 d e t ( H ) = − 1 det(\bold H)=-1 det(H)=−1，因而Householder矩阵是可逆的 Householder矩阵的性质 Householder矩阵 H = I − 2 v v T \bold H=\bold I-2\bold v\bold v^T H=I−2vvT是对称矩阵+正交矩阵： H = H T = H − 1 H=H^T=H^{-1} H=HT=H−1①从形式上，显然是对称矩阵 ②可以验证，矩阵为正交阵： H T H = ( I − 2 v v T ) ( I − 2 v v T ) = I − 4 v v T + 4 v v T v v T = I H^TH=(I-2\mathbf{v}\mathbf{v}^T)(I-2\mathbf{v}\mathbf{v}^T)=I-4\mathbf{v}\mathbf{v}^T+4\mathbf{v}\mathbf{v}^T\mathbf{v}\mathbf{v}^T=I HTH=(I−2vvT)(I−2vvT)=I−4vvT+4vvTvvT=I 由上，Householder矩阵满足 H 2 = H H − 1 = I H^2=HH^{-1}=I H2=HH−1=I，称为对合 （involutory） 矩阵 这个概念类比对合 函数理解：“一个函数的反函数是他自身”，即 f ( f ( x ) ) = x f(f(x))=x f(f(x))=x 这就是说，镜射后再次镜射，相当于没变Householder矩阵最有实用价值的性质在于，总存在一个Householder矩阵，将任意单位长度向量 x \bold x x镜射至标准单位向量： H x = e 1 = ( 1 , 0 , … , 0 ) T H\mathbf{x}= \mathbf{e}_1=(1,0,\ldots,0)^T Hx=e1=(1,0,…,0)T 理解：这相当于寻找合适的镜射超平面，将向量 x \bold x x镜射至 e \mathbf{e} e更一般的，若两个向量满足 ∥ x ∥ 2 = ∥ y ∥ 2 \|\mathbf x\|_2=\|\mathbf y\|_2 ∥x∥2=∥y∥2，且 x H y = y H x \mathbf x^H\mathbf y=\mathbf y^H\mathbf x xHy=yHx，必然存在Householder矩阵使得 H x = y \mathbf H\mathbf x=\mathbf y Hx=y注意， H T = H − 1 H^T=H^{-1} HT=H−1表明Householder矩阵也是一个酉矩阵，但几何意义是镜射 这也表明了：酉矩阵的几何意义不仅仅包括旋转，还包括镜射 Householder矩阵的应用：矩阵的三对角化基于上面给出的最后一个性质， Householder 变换可以将对称矩阵 A \bold A A 三对角化 （tridiagonalization），得到形如 [ ∗ ∗ 0 0 0 ∗ ∗ ∗ 0 0 0 ∗ ∗ ∗ 0 0 0 ∗ ∗ ∗ 0 0 0 ∗ ∗ ] \begin{bmatrix} \ast&\ast&0&0&0\\ \ast&\ast&\ast&0&0\\ 0&\ast&\ast&\ast&0\\ 0&0&\ast&\ast&\ast\\ 0&0 &0&\ast&\ast \end{bmatrix} ∗∗000∗∗∗000∗∗∗000∗∗∗000∗∗ 的矩阵，从而尽可能产生零元 基本思路： 从第一列开始，依次将每一列变为三对角阵的形式，具体方法是设计一个可逆矩阵 P \bold P P，使得相似变换 P − 1 A P P^{-1}AP P−1AP满足需求（额外限制 P P P为正交矩阵，从而当 A A A 是对称矩阵时， P − 1 A P P^{-1}AP P−1AP 也是对称矩阵： ( P − 1 A P ) T = P T A T P = P − 1 A P (P^{-1}AP)^T=P^TA^TP=P^{-1}AP (P−1AP)T=PTATP=P−1AP） 以 A = [ 4 1 − 2 2 1 2 0 1 − 2 0 3 − 2 2 1 − 2 − 1 ] A=\left[\!\!\begin{array}{rcrr} 4&1&-2&2\\ 1&2&0&1\\ -2&0&3&-2\\ 2&1&-2&-1 \end{array}\!\!\right] A= 41−221201−203−221−2−1 为例，每一步的具体做法如下： 对 A A A和 P P P矩阵分块，其中正交矩阵 P 1 = [ 1 0 0 0 0 0 H 1 0 ] P_{1}=\left[\begin{array}{l|lll} 1 & 0 & 0 & 0 \\ \hline 0 & & & \\ 0 & & H_{1} & \\ 0 & & & \end{array}\right] P1= 100000H10 ， H 1 H_{1} H1为3阶Householder矩阵，则分块矩阵乘法： P 1 A P 1 = [ 1 0 0 H 1 ] [ a 11 a T a A ~ ] [ 1 0 0 H 1 ] = [ a 11 a T H 1 H 1 a H 1 A ~ H 1 ] P_1AP_1=\begin{bmatrix} 1&0\\ 0&H_1 \end{bmatrix}\begin{bmatrix} a_{11}&\mathbf{a}^T\\ \mathbf{a}&\tilde{A} \end{bmatrix}\begin{bmatrix} 1&0\\ 0&H_1 \end{bmatrix}=\begin{bmatrix} a_{11}&\mathbf{a}^TH_1\\ H_1\mathbf{a}&H_1\tilde{A}H_1\end{bmatrix} P1AP1=[100H1][a11aaTA~][100H1]=[a11H1aaTH1H1A~H1]其中 a = [ a 21 a 31 a 41 ] = [ 1 − 2 2 ] \mathbf{a}=\begin{bmatrix} a_{21}\\ a_{31}\\ a_{41} \end{bmatrix}=\begin{bmatrix} 1\\ -2\\ 2 \end{bmatrix} a= a21a31a41 = 1−22 ，而 A ˉ \bar A Aˉ为 A A A的余下部分 根据上述性质，一定能找到 H 1 H_1 H1，使得 H 1 a H_1\mathbf{a} H1a 平行于 e 1 = [ 1 0 0 ] \mathbf{e}_1=\begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} e1= 100 这里省略中间步骤，直接给出 H 1 = [ − 1 3 2 3 − 2 3 2 3 2 3 1 3 − 2 3 1 3 2 3 ] H_1=\left[\!\!\begin{array}{rcr} -\frac{1}{3}&\frac{2}{3}&-\frac{2}{3}\\ \frac{2}{3}&\frac{2}{3}&\frac{1}{3}\\ -\frac{2}{3}&\frac{1}{3} &\frac{2}{3} \end{array}\!\!\right] H1= −3132−32323231−323132 ， 从而 A 1 = P 1 A P 1 = [ 4 − 3 0 0 − 3 10 3 1 4 3 0 1 5 3 − 4 3 0 4 3 − 4 3 − 1 ] A_1=P_1AP_1=\left[\!\!\begin{array}{rrrr} 4&-3&0&0\\ -3&\frac{10}{3}&1&\frac{4}{3}\\0&1&\frac{5}{3}&-\frac{4}{3}\\ 0&\frac{4}{3}&-\frac{4}{3}&-1 \end{array}\!\!\right] A1=P1AP1= 4−300−33101340135−34034−34−1 ，这便完成第一列的“三对角化”同理，将矩阵分块，设计正交矩阵 P 2 P_2 P2，完成第二列的“三对角化” 直接给出 P 2 = [ 1 0 0 0 0 1 0 0 0 0 − 3 5 − 4 5 0 0 − 4 5 3 5 ] P_2=\left[\!\!\begin{array}{ccrr} 1&0&0&0\\ 0&1&0&0\\0&0&-\frac{3}{5}&-\frac{4}{5}\\ 0&0&-\frac{4}{5}&\frac {3} {5} \end{array}\!\!\right] P2= 1000010000−53−5400−5453 ， 从而得到 A 2 = P 2 A 1 P 2 = [ 4 − 3 0 0 − 3 10 3 − 5 3 0 0 − 5 3 − 33 25 68 75 0 0 68 75 149 75 ] A_2=P_2A_1P_2=\left[\!\!\begin{array}{rrrr} 4&-3&0&0\\ -3&\frac{10}{3}&-\frac{5}{3}&0\\ 0&-\frac{5}{3}&-\frac{33}{25}&\frac{68}{75}\\ 0&0&\frac{68}{75}& \frac{149}{75} \end{array}\!\!\right] A2=P2A1P2= 4−300−3310−3500−35−2533756800756875149 最终的三对角阵就是 A 2 = ( P 1 P 2 ) − 1 A ( P 1 P 2 ) = P − 1 A P A_2=(P_1P_2)^{-1}A(P_1P_2)=P^{-1}AP A2=(P1P2)−1A(P1P2)=P−1AP，其中 P = P 1 P 2 P=P_1P_2 P=P1P2为正交矩阵以上面的三对角化为基础，Householder 变换的两个主要应用都是在数值线性代数的内容：①执行 QR 分解；②计算特征值的 QR 迭代法的第一步。 reference: 特殊矩阵 （4）：Householder 矩阵 Householder 矩阵乘积的特征值 Householder 变换于 QR 分解的应用 |
由此可得Householder矩阵 / 镜射矩阵
H
=
I
−
2
v
v
T
\bold H=\bold I-2\bold v\bold v^T
H=I−2vvT，其中
∥
v
∥
=
1
\|\bold v\|=1
∥v∥=1【本文地址】
今日新闻 |
推荐新闻 |