11QR分解
QR分解
1.定义
矩阵A可以化为正交(酉)矩阵Q和上三角矩阵R的乘积,即
A
=
Q
R
A=QR
A=QR,则称上式为矩阵的
Q
R
QR
QR分解
2.定理
若
A
A
A是一个
n
n
n阶非奇异矩阵,则存在正交(酉)矩阵
Q
Q
Q和上三角矩阵
R
R
R使得
A
=
Q
R
A=QR
A=QR,且除去相差一个对角元素绝对值全为1的对角因子外,上述分解唯一。
回顾一下施密特正交化的过程
可以得到施密特正交化的矩阵为
证明:
设
A
=
[
a
1
,
a
2
.
.
.
a
n
]
A=[a_1,a_2...a_n]
A=[a1,a2...an],且
a
1
,
a
2
,
.
.
.
a
n
a_1,a_2,...a_n
a1,a2,...an线性无关。应用施密特正交化的办法可以得到
[
a
1
a
2
⋯
a
n
]
=
[
b
1
b
2
⋯
b
n
]
[
1
b
⋯
k
n
1
1
⋯
k
n
2
⋱
⋮
k
n
n
−
1
]
\left[ \begin{matrix} a_1 & a_2 & \cdots & a_n \end{matrix} \right]=\left[ \begin{matrix} b_1 & b_2 & \cdots & b_n \end{matrix} \right]\left[ \begin{matrix} 1 & b & \cdots & k_{n1} \\ & 1 & \cdots & k_{n2} \\ & & \ddots & \vdots \\ & & & k_{nn-1} \end{matrix} \right]
[a1a2⋯an]=[b1b2⋯bn]⎣⎢⎢⎢⎡1b1⋯⋯⋱kn1kn2⋮knn−1⎦⎥⎥⎥⎤对其单位化可得
[
a
1
a
2
⋯
a
n
]
=
[
q
1
q
2
⋯
q
n
]
[
∣
b
1
∣
∣
b
2
∣
⋱
∣
b
n
∣
]
[
1
b
⋯
k
n
1
1
⋯
k
n
2
⋱
⋮
k
n
n
−
1
]
=
Q
R
\left[ \begin{matrix} a_1 & a_2 & \cdots & a_n \end{matrix} \right]=\left[ \begin{matrix} q_1 & q_2 & \cdots & q_n \end{matrix} \right]\left[ \begin{matrix} |b_1| & & & \\ & |b_2| & & \\ & & \ddots & \\ & & & |b_n| \end{matrix} \right]\left[ \begin{matrix} 1 & b & \cdots & k_{n1} \\ & 1 & \cdots & k_{n2} \\ & & \ddots & \vdots \\ & & & k_{nn-1} \end{matrix} \right]=QR
[a1a2⋯an]=[q1q2⋯qn]⎣⎢⎢⎡∣b1∣∣b2∣⋱∣bn∣⎦⎥⎥⎤⎣⎢⎢⎢⎡1b1⋯⋯⋱kn1kn2⋮knn−1⎦⎥⎥⎥⎤=QR接下来我们证明其唯一性:
假设有两个QR分解
A
=
Q
R
=
Q
1
R
1
A=QR=Q_1R_1
A=QR=Q1R1
Q
=
Q
1
R
1
R
−
1
=
Q
1
D
Q=Q_1R_1R^{-1}=Q_1D
Q=Q1R1R−1=Q1D因为
R
1
,
R
R_1,R
R1,R都为上三角矩阵,而上三角矩阵的逆为上三角矩阵,上三角矩阵成上三角矩阵还是上三角矩阵因此
D
D
D是上三角矩阵。又
I
=
Q
H
Q
=
D
H
Q
1
H
Q
1
D
=
D
H
D
I=Q^HQ=D^HQ_1^HQ_1D=D^HD
I=QHQ=DHQ1HQ1D=DHD所以
D
D
D是酉矩阵。所以,
D
D
D只能是对角元素绝对值全为1的对角阵
3.求QR分解的办法
3.1Gives变换(利用Gives变换的
T
x
=
∣
x
∣
e
1
Tx=|x|e_1
Tx=∣x∣e1)
例题:利用
G
i
v
e
n
s
变
换
Givens变换
Givens变换求
A
=
[
2
2
1
0
2
2
2
1
2
]
A=\left[ \begin{matrix} 2 & 2& 1 \\ 0 & 2& 2\\ 2 & 1 & 2 \end{matrix} \right]
A=⎣⎡202221122⎦⎤的
Q
R
分
解
QR分解
QR分解(正交矩阵的转置就是其逆)
解:首先对第一列进行Givens变换,有
T
13
=
[
c
0
s
0
1
0
−
s
0
c
]
,
c
=
a
11
a
11
2
+
a
31
2
=
2
2
2
=
1
2
,
s
=
a
31
a
11
2
+
a
31
2
=
1
2
T_{13}=\left[ \begin{matrix} c & 0& s \\ 0 & 1& 0\\ -s & 0 & c \end{matrix} \right] ,c=\frac{a_{11}}{\sqrt{a_{11}^2+a_{31}^2}}=\frac{2}{2\sqrt{2}}=\frac{1}{\sqrt{2}},s=\frac{a_{31}}{\sqrt{a_{11}^2+a_{31}^2}}=\frac{1}{\sqrt{2}}
T13=⎣⎡c0−s010s0c⎦⎤,c=a112+a312a11=222=21,s=a112+a312a31=21所以可得
T
1
=
[
1
2
0
1
2
0
1
0
−
1
2
0
1
2
]
,
T
1
A
=
[
2
2
3
2
3
2
0
2
2
0
−
1
2
1
2
]
,
A
(
1
)
=
[
2
2
−
1
2
1
2
]
T_1=\left[ \begin{matrix} \frac{1}{\sqrt{2}} & 0& \frac{1}{\sqrt{2}} \\ 0 & 1& 0\\ -\frac{1}{\sqrt{2}} & 0& \frac{1}{\sqrt{2}} \end{matrix} \right] ,T_1A=\left[ \begin{matrix} 2\sqrt{2} & \frac{3}{\sqrt{2}}&\frac{3}{\sqrt{2}} \\ 0 & 2& 2\\ 0 & -\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}} \end{matrix} \right],A^{(1)}=\left[ \begin{matrix} 2& 2\\ -\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}} \end{matrix} \right]
T1=⎣⎡210−2101021021⎦⎤,T1A=⎣⎢⎡2200232−2123221⎦⎥⎤,A(1)=[2−21221]对
A
(
1
)
A^{(1)}
A(1)再进行Givens变换,可以得到
T
12
=
[
c
s
−
s
c
]
,
c
=
2
2
3
,
s
=
−
1
3
T_{12}=\left[ \begin{matrix} c & s \\ -s & c \end{matrix} \right],c=\frac{2\sqrt{2}}{3},s=-\frac{1}{3}
T12=[c−ssc],c=322,s=−31所以可得
T
2
=
[
2
2
3
−
1
3
1
3
2
2
3
]
,
T
2
A
(
1
)
=
[
2
2
3
7
2
6
0
4
3
]
,
T2=\left[ \begin{matrix} \frac{2\sqrt{2}}{3} & -\frac{1}{3} \\ \frac{1}{3} & \frac{2\sqrt{2}}{3} \end{matrix} \right],T_2A^{(1)}=\left[ \begin{matrix} \frac{2\sqrt{2}}{3} & \frac{7\sqrt{2}}{6} \\ 0 & \frac{4}{3} \end{matrix} \right],
T2=[32231−31322],T2A(1)=[322067234],综上可得,
R
=
[
2
2
3
2
3
2
0
2
2
3
7
2
6
0
0
4
3
]
,
Q
=
[
[
1
0
0
T
2
]
T
1
]
T
=
[
1
2
1
3
2
−
2
3
0
2
2
3
7
2
6
1
2
−
1
3
2
2
3
]
R=\left[ \begin{matrix} 2\sqrt{2} & \frac{3}{\sqrt{2}}&\frac{3}{\sqrt{2}} \\ 0 & \frac{2\sqrt{2}}{3} & \frac{7\sqrt{2}}{6}\\ 0 & 0 & \frac{4}{3} \end{matrix} \right],Q=\left[\left[ \begin{matrix} 1 & 0 \\ 0& T2 \end{matrix} \right]T_1\right]^T=\left[ \begin{matrix} \frac{1}{\sqrt{2}} & \frac{1}{3\sqrt{2}}&-\frac{2}{3} \\ 0 & \frac{2\sqrt{2}}{3} & \frac{7\sqrt{2}}{6}\\ \frac{1}{\sqrt{2}} & -\frac{1}{3\sqrt{2}}& \frac{2}{3} \end{matrix} \right]
R=⎣⎢⎡22002332202367234⎦⎥⎤,Q=[[100T2]T1]T=⎣⎢⎡21021321322−321−3267232⎦⎥⎤
3.2Householder变换(利用
H
x
=
∣
x
∣
z
Hx=|x|z
Hx=∣x∣z)
将
z
z
z矩阵设为e矩阵,u=
x
−
∣
x
∣
z
∣
x
−
∣
x
∣
z
∣
\frac{x-|x|z}{|x-|x|z|}
∣x−∣x∣z∣x−∣x∣z
利用Householder求
A
=
[
0
4
1
1
1
1
0
3
2
]
A=\left[ \begin{matrix} 0 & 4& 1 \\ 1 & 1& 1\\ 0 & 3 & 2 \end{matrix} \right]
A=⎣⎡010413112⎦⎤的
Q
R
QR
QR分解
解:首先对第一列使用Householder变换,可以得到
H
=
I
−
2
u
u
T
,
∣
x
−
∣
x
∣
e
1
∣
=
2
,
x
−
∣
x
∣
e
1
=
[
−
1
1
0
]
,
u
=
1
2
[
−
1
1
0
]
H=I-2uu^T,|x-|x|e_1|=\sqrt{2},x-|x|e_1=\left[ \begin{matrix} -1\\ 1 \\ 0 \end{matrix} \right],u=\frac{1}{\sqrt{2}}\left[ \begin{matrix} -1\\ 1 \\ 0 \end{matrix} \right]
H=I−2uuT,∣x−∣x∣e1∣=2,x−∣x∣e1=⎣⎡−110⎦⎤,u=21⎣⎡−110⎦⎤
2
u
u
T
=
1
2
[
−
1
1
0
]
1
2
[
−
1
1
0
]
=
1
2
[
1
−
1
0
−
1
1
0
0
0
0
]
2uu^T=\frac{1}{\sqrt{2}}\left[ \begin{matrix} -1\\ 1 \\ 0 \end{matrix} \right]\frac{1}{\sqrt{2}}\left[ \begin{matrix} -1 &1 & 0 \end{matrix} \right]=\frac{1}{2}\left[ \begin{matrix} 1&-1&0\\ -1&1&0 \\ 0&0&0 \end{matrix} \right]
2uuT=21⎣⎡−110⎦⎤21[−110]=21⎣⎡1−10−110000⎦⎤
I
−
2
u
u
T
=
[
0
1
0
1
0
0
0
0
1
]
=
H
,
H
A
=
[
1
1
1
0
4
1
0
3
2
]
I-2uu^T=\left[ \begin{matrix} 0&1&0\\ 1&0&0 \\ 0&0&1 \end{matrix} \right]=H,HA=\left[ \begin{matrix} 1&1&1\\ 0&4&1 \\ 0&3&2 \end{matrix} \right]
I−2uuT=⎣⎡010100001⎦⎤=H,HA=⎣⎡100143112⎦⎤继续做下去,可以得到