QR分解是将矩阵分解成一个正规正交矩阵Q与上三角形矩阵R，所以称为QR分解法。该算法对对称矩阵和非对称矩阵都适用。
定义：
一个矩阵 A ∈ R m × n , m ≥ n A \in \mathbb{R}^{m \times n}, m \geq n A∈Rm×n,m≥n 可以被分解成 A = Q R A=Q R A=QR, 其中
- Q ∈ R m × m Q \in \mathbb{R}^{m \times m} Q∈Rm×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]∈Rm×n
- R ^ ∈ R n × n \hat{R} \in \mathbb{R}^{n \times n} R^∈Rn×n 是上三角矩阵
下面给出一个直观的QR分解的例子
讯享网
从QR分解角度看线性最小二乘
对于一个over-determined线性最小二乘问题 A x ≃ b A x \simeq b Ax≃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)∥22=∥b−Ax∥22=∥∥∥∥b−Q[R^0]x∥∥∥∥22=∥∥∥∥QT(b−Q[R^0]x)∥∥∥∥22=∥∥∥∥QTb−[R^0]x∥∥∥∥22
这里 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∈Rm×m,Qb∈Rm×1,[R^0]∈Rm×n,[R^0]x∈Rm×1
如果把 Q T b Q^{T} b QTb 拆分成上下两部分，形式 [ 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] QTb=[c1c2], where c 1 ∈ R n , c 2 ∈ R m − n c_{1} \in \mathbb{R}^{n}, c_{2} \in \mathbb{R}^{m-n} c1∈Rn,c2∈Rm−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)∥22=∥∥∥c1−R^x∥∥∥22+∥c2∥22
可以看到，我们只能最小化前一部分 ∥ c 1 − R ^ x ∥ 2 2 \left\|c_{1}-\hat{R} x\right\|_{2}^{2} ∥∥∥c1−R^x∥∥∥22 到0，即 R ^ x = c 1 \hat{R} x=c_{1} R^x=c1， ∥ r ( x ) ∥ 2 2 \|r(x)\|_{2}^{2} ∥r(x)∥22 的最小值为 ∥ c 2 ∥ 2 2 \left\|c_{2}\right\|_{2}^{2} ∥c2∥22 。这样处理之后就避免了求正规方程组中的 ( A T A ) − 1 \left(A^{T} A\right)^{-1} (ATA)−1 ，避免了条件数变成 cond ( A T A ) = cond ( A ) 2 \operatorname{cond}\left(A^{T} A\right)=\operatorname{cond}(A)^{2} cond(ATA)=cond(A)2，所以QR分解法更加数值稳定。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/56240.html