QR分解是将矩阵分解成一个正规正交矩阵Q与上三角形矩阵R，所以称为QR分解法。该算法对对称矩阵和非对称矩阵都适用。
定义：
一个矩阵
A
∈
R
m
×
n
,
m
≥
n
A \in \mathbb{R}^{m \times n}, m \geq n
A
∈
R
m
×
n
,
m
≥
n
可以被分解成
A
=
Q
R
A=Q R
A
=
Q
R
, 其中
-
Q∈
R
m
×
m
Q \in \mathbb{R}^{m \times m}
Q
∈
R
m
×
m
是正交矩阵 -
R≡
[
R
^
0
]
∈
R
m
×
n
R \equiv\left[\begin{array}{l}\hat{R} \\ 0\end{array}\right] \in \mathbb{R}^{m \times n}
R
≡
[
R
^
0
]
∈
R
m
×
n
-
R^
∈
R
n
×
n
\hat{R} \in \mathbb{R}^{n \times n}
R
^
∈
R
n
×
n
是上三角矩阵
下面给出一个直观的QR分解的例子
从QR分解角度看线性最小二乘
对于一个over-determined线性最小二乘问题
A
x
≃
b
A x \simeq b
A
x
≃
b
，，其目标函数是
ϕ
(
x
)
=
∥
r
(
x
)
∥
2
2
=
∥
b
−
A
x
∥
2
2
=
∥
b
−
Q
[
R
^
0
]
x
∥
2
2
=
∥
Q
T
(
b
−
Q
[
R
^
0
]
x
)
∥
2
2
=
∥
Q
T
b
−
[
R
^
0
]
x
∥
2
2
\begin{aligned} \phi(x)=\|r(x)\|_{2}^{2} &=\|b-A x\|_{2}^{2}=\left\|b-Q\left[\begin{array}{l}\hat{R} \\ 0\end{array}\right] x\right\|_{2}^{2} \\ &=\left\|Q^{T}\left(b-Q\left[\begin{array}{c}\hat{R} \\ 0\end{array}\right] x\right)\right\|_{2}^{2} \\ &=\left\|Q^{T} b-\left[\begin{array}{c}\hat{R} \\ 0\end{array}\right] x\right\|_{2}^{2} \end{aligned}
ϕ
(
x
)
=
∥
r
(
x
)
∥
2
2
=
∥
b
−
A
x
∥
2
2
=
∥
∥
∥
∥
b
−
Q
[
R
^
0
]
x
∥
∥
∥
∥
2
2
=
∥
∥
∥
∥
Q
T
(
b
−
Q
[
R
^
0
]
x
)
∥
∥
∥
∥
2
2
=
∥
∥
∥
∥
Q
T
b
−
[
R
^
0
]
x
∥
∥
∥
∥
2
2
这里
Q
∈
R
m
×
m
,
Q
b
∈
R
m
×
1
,
[
R
^
0
]
∈
R
m
×
n
,
[
R
^
0
]
x
∈
R
m
×
1
Q \in \mathbb{R}^{m \times m}, \quad Q b \in \mathbb{R}^{m \times 1},\left[\begin{array}{c}\hat{R} \\ 0\end{array}\right] \in \mathbb{R}^{m \times n},\left[\begin{array}{c}\hat{R} \\ 0\end{array}\right] x \in \mathbb{R}^{m \times 1}
Q
∈
R
m
×
m
,
Q
b
∈
R
m
×
1
,
[
R
^
0
]
∈
R
m
×
n
,
[
R
^
0
]
x
∈
R
m
×
1
如果把
Q
T
b
Q^{T} b
Q
T
b
拆分成上下两部分，形式
[
R
^
0
]
\left[\begin{array}{c}\hat{R} \\ 0\end{array}\right]
[
R
^
0
]
类似，
Q
T
b
=
[
c
1
c
2
]
Q^{T} b=\left[\begin{array}{l}c_{1} \\ c_{2}\end{array}\right]
Q
T
b
=
[
c
1
c
2
]
, where
c
1
∈
R
n
,
c
2
∈
R
m
−
n
c_{1} \in \mathbb{R}^{n}, c_{2} \in \mathbb{R}^{m-n}
c
1
∈
R
n
,
c
2
∈
R
m
−
n
。那么目标函数可以写成下面的形式：
∥
r
(
x
)
∥
2
2
=
∥
c
1
−
R
^
x
∥
2
2
+
∥
c
2
∥
2
2
\|r(x)\|_{2}^{2}=\left\|c_{1}-\hat{R} x\right\|_{2}^{2}+\left\|c_{2}\right\|_{2}^{2}
∥
r
(
x
)
∥
2
2
=
∥
∥
∥
c
1
−
R
^
x
∥
∥
∥
2
2
+
∥
c
2
∥
2
2
可以看到，我们只能最小化前一部分
∥
c
1
−
R
^
x
∥
2
2
\left\|c_{1}-\hat{R} x\right\|_{2}^{2}
∥
∥
∥
c
1
−
R
^
x
∥
∥
∥
2
2
到0，即
R
^
x
=
c
1
\hat{R} x=c_{1}
R
^
x
=
c
1
，
∥
r
(
x
)
∥
2
2
\|r(x)\|_{2}^{2}
∥
r
(
x
)
∥
2
2
的最小值为
∥
c
2
∥
2
2
\left\|c_{2}\right\|_{2}^{2}
∥
c
2
∥
2
2
。这样处理之后就避免了求正规方程组中的
(
A
T
A
)
−
1
\left(A^{T} A\right)^{-1}
(
A
T
A
)
−
1
，避免了条件数变成
cond
(
A
T
A
)
=
cond
(
A
)
2
\operatorname{cond}\left(A^{T} A\right)=\operatorname{cond}(A)^{2}
c
o
n
d
(
A
T
A
)
=
c
o
n
d
(
A
)
2
，所以QR分解法更加数值稳定。