∗ ... ∗ ∗ ... ∗ : O : O : = QR = ∗ ... ∗ m×n 0 ∗ n×n
∗ = QR = : ∗ ... O ... ∗ ∗ : 0 ∗ m×m 0 ... O ... ∗ : ∗ 0 m×n
推导：∀x = ( x1 , x2 ,L , xn ) ≠ 0
T
y = ( x1 ,L , xk −1 , −σ k , 0,L , 0)
σ k = sign( xk )( ∑ x ) ,
i=k n 1 2 2 i
T
1 sign( xk ) = −1
xk ≥ 0 xk < 0
U
(k )
= x − y = (0,L , 0, xk + σ k , xk +1 ,L , xn )
n
x− y
π
y
U 证：若设W = ， 则 有 W 2 = 1， 因 此 U 2 UU T H = I − 2W W T = I − 2 2 U 2 ( x − y) = I−2 ( xT − yT ) 2 x− y 2 ( x − y) Hx = x − 2 ( xT − yT ) x 2 T T x− y 2 ( x − y )( x x − y x )
T
1 2 2 k
U = x − y = x + σ i ei = ( x1 ,L, xi + σ i ,L, xn ) ,
构造初等反射阵
H = I − 2WW
T
= I −2
UU T U
2
=I−
1
ρ
UU T
有 H x = y = −σ i e i
其中 1 T 1 2 2 2 ρ = U U = ( x1 + ... + ( xi + σ i ) + L + xn ) 2 2 1 2 = (2 xiσ i + 2σ i ) = σ i ( xi + σ i ) 2
(1) (1) H 1 A(1) = H 1α1(1) , H 1α 2 ,L , H 1α n (2) (2) (2) a11 a12 L a1n (2) (2) ∆ 0 a22 L a2 n = A(2) = α (2) , α (2) ,L , α (2) = 2 n 1 M M O M (2) (2) 0 an 2 L ann
2 1
−2 w1 w2 L −2 w1 wn 2 1 − 2 w2 L −2 w2 wn L L L 2 −2 wn w2 L 1 − 2 wn
（3）镜映射 − 几何意义 平 面 π 方 程 W T x = 0 ∀x ∈ π T T 若 x ∈ π , Hx = ( I − 2WW ) x = x − 2WW x = x
阵， 即 ： ∀x = ( x1 , x 2 ,L , x n )T ∈ R n , x ≠ 0, 可构造 H 阵 ， 使 Hx = y = −σ i ei = (0, ..., 0, −σ i , 0,L , 0)T ∈ R n
n k =1
其中σ i = sign( xi ) x 2 = sign( xi )( ∑ x ) , 1 sign( xi ) = −1 xi ≥ 0 xi < 0
T
H阵的性质： 阵的性质： 阵的性质 det( H ) = −1 （1）非奇异
（2）对称正交 H = HT T 2 T T HH = H = ( I − 2WW )( I − 2WW ) = I − 4WW T + 4WW T WW T = I
1 − 2w −2w2 w1 H= L −2 wn w1
因为 x − y
2 2
x− y 2 T T T T = ( x − y )( x − y ) = 2( x x − y x )
= x−2
2
代入上式后即得到 Hx = y Q x T x = y T y , xT y = yT x
1. Householder变换可以将给定的向量变为一个 同方向的向量。 与任一个ei ∈ Rn ( i = 1, 2,L , n)同方向的向量。
n×n
∗ L 化矩阵A ∈ R n×n为上三角阵,A = M O ∗ L 只 须 依次 将 各 列 对 角 线 下元 素 化 为 零
(1)
∗ ∗ L ∗ M → O M ∗ ∗
(1) (1) α1(1) , α 2 , L , α n 记A = A = 对A(1)的第一列α1(1) 构造H 1使H 1α1(1) = ( −σ 1 , 0, L , 0)T
1 例：W = 2
1 3 0 ∈ R ,|| W ||2 = 1 2 1 2 1 1 T H = I − 2WW = I − 2 0 0 2 1 2 2 0 0 −1 =0 1 0 −1 0 0
−(4 + 2 5) −(2 + 5) −(2 + 5) (4 + 2 5) 0 0
T
H 2 x = ( x1 , −σ 2 , 0 )
= (2, −
5 ,0)
T
2、矩阵的正交分解
1 、正交分解的基本定理 定理 ∀A ∈ R m×n是列满秩矩阵（m > n, r ( A) = n）， 存在分解式A = QR, 其中Q ∈ R m×n列正交矩阵， R∈ R
Am × n
2、QR分解的实际计算 分解的实际计算 变换对A作 分解 用Householder变换对 作QR分解 变换对
∀A ∈ R 非奇异 构造Householder 阵 H k ∈ R n×n ( k = 1, 2,L , n − 1) 则H n −1 H n − 2 L H 2 H 1 A = R 上三角阵） （上三角阵）
故 取 K = −σ 3 = − 3 于 是 y = −σ 3 e 3 = Ke 3 = (0, 0, − 3, 0)T ,
U = x − y = (2, 0, 5,1) , ρ = σ 3 (σ 3 + x3 ) = 3(3 + 2) = 15
T
1 T ρ = UU 2
H = I−
1
ρ
UU T
11 0 1 = 15 − 10 −2
例 ： 已 知 向 量 x = (2, 2,1)T , 试 构 造 初 等 反 射 阵 使 y = Hx 最 后 一 个 元 素 为 零 。
解
k = 2, 构 造 H 2
2 2 2 3
σ 2 = sign ( x 2 )( x + x ) =
U
(2)
1 2
5
5 , 1)
T
= (0, σ 2 + x 2 , x 3 ) = (0, 2 +
− −1 A = H 1−1 H 2 1 L H n −1 R = H 1 H 2 L H n −1 R = QR 其中 n×n Q = H 1 H 2 L H n −1 ∈ R 为正交阵 R = Q −1 A = Q T A = H n −1 H n − 2 L H 2 H 1 A −1 T −1 T H k = H k = H k , Q = Q = H n −1 H n− 2 L H 2 H 1
T U 1U 1
U1
2
=I−
1
ρ
T U 1U 1
有 H 1 x = y = − σ 1e1
1 T 1 2 2 2 其中 ρ1 = U 1 U 1 = (( x1 + σ 1 ) + x2 + ... + xn ) 2 2 1 = (2 x1σ 1 + 2σ 12 ) = σ 1 ( x1 + σ 1 ) 2
n× n
非奇异上三角阵。若限定R阵对角元符号，
则分解式是唯一的。 当m = n时, Q ∈ R n×n正交阵, R ∈ R n×n非奇异上三角阵。
An× n
∗ : = QR = ∗
... O ...
∗ ∗ : ∗ 0
... O
∗ : ∗
Am×n
例 已 知 向 量 x = (2, 0, 2,1)T , 试 构 造 Householder阵 , 使 Hx = Ke 3 , 其 中 e 3 = (0, 0,1, 0)T ∈ R 4 , K ∈ R。
解 : σ 3 = sign ( x 3 ) x
2
=
4 + 0 + 4 + 1 = 3, 因 x 3 = 2 > 0 ,
0 1 0 0
− 10 0 − 10 −5
−2 0 −5 14
2. 构 造 H 阵 , 将 向 量 x = ( x 1 , L , x k , x k + 1 , L , x n ) T 的 后 面 n − k 个 分 量 约 化 为 零 (1 ≤ k < n )。
即：任给定x = ( x1 , x2 ,L , xn )T ≠ 0, 构造H k ∈ Rn×n , 使 H k x = ( x1 , x2 ,L , xk −1 , −σ k ,0,L ,0)T
T
ρ 2 = σ 2 ( x2 + σ 2 ) = 5 + 2 5 T T 于 是 H 2 x = ( x 1 , − σ 2 , 0) = (2, − 5 , 0)
计算 H2, H2 = I − 1
ρ2
U ( 2 ) (U ( 2 ) )T
5 + 2 5 1 H2 = 0 5+2 5 0
σ 1 = sign( x1 ) x 2 = sign( x1 )(∑ x ) ,