线性代数 A = [ 1 2 3 4 ] {\displaystyle \mathbf {A} ={\begin{bmatrix}1&2\\3&4\end{bmatrix}}} 向量 · 向量空间 · 基底 · 行列式 · 矩阵
QR分解法 是一種将矩阵分解 的方式。這種方式,把矩阵 分解成一个正交矩阵 与一个上三角矩阵 的积。QR分解经常用来解线性最小二乘法 问题。QR分解也是特定特征值算法即QR算法的基础。
類別及定义
方陣 任何方块矩阵 A都可以分解為
A = Q R {\displaystyle A=QR} 其中Q 是正交矩阵 (意味着Q T Q = I )而R 是上三角矩阵 。如果A 是非奇异 的,且限定R 的对角线元素为正,则这个因数分解是唯一的。
更一般的说,我们可以因数分解复数 m {\displaystyle m} × n {\displaystyle n} 矩阵(有着m ≥ n )为 m {\displaystyle m} × n {\displaystyle n} 幺正矩阵 (在Q ∗ Q = I 的意义上,不需要是方阵)和 n {\displaystyle n} × n {\displaystyle n} 上三角矩阵的乘积。对m<n的情况,在Q 是 m {\displaystyle m} × m {\displaystyle m} 方阵,而R则是 m {\displaystyle m} × n {\displaystyle n} 矩阵。
長方形矩陣 更一般地,我們可以將m ×n 的A 矩陣,其中m ≥ n ,分解成m ×m 酉矩阵 Q 和m ×n 三角矩陣R 的成積。由於m ×n 上三角矩陣的底部(m −n )行完全由零組成,因此對R 或R 和Q 進行分解通常很有用:
A = Q R = Q [ R 1 0 ] = [ Q 1 Q 2 ] [ R 1 0 ] = Q 1 R 1 , {\displaystyle A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=Q_{1}R_{1},} 其中R 1 是n ×n 上三角矩陣,0是(m − n )×n 零矩陣,Q 1 是m ×n ,Q 2 是m ×(m − n ) ,且Q 1 和Q 2 都是有正交列。
Golub & Van Loan (1996 ,§5.2) call Q 1 R 1 the thin QR factorization of A ; Trefethen and Bau call this the reduced QR factorization .[ 1] If A is of full rank n and we require that the diagonal elements of R 1 are positive then R 1 and Q 1 are unique, but in general Q 2 is not. R 1 is then equal to the upper triangular factor of the Cholesky decomposition of A * A (= A T A if A is real).
QL、RQ 和 LQ 分解 类似的,我们可以定义A的QL,RQ和LQ分解。其中L是下三角矩陣。
QR分解的求法 QR分解的实际计算有很多方法,例如Givens旋转 、Householder变换 ,以及Gram-Schmidt正交化 等等。每一种方法都有其优点和不足。
使用Householder变换
Householder变换 Householder变换 将一个向量关于某个平面或者超平面 进行反射。我们可以利用这个操作对 m × n ( m ≧ n ) {\displaystyle m\times n(m\geqq n)} 的矩阵 A {\displaystyle A} 进行QR分解。
矩阵 Q {\displaystyle Q} 可以被用于对一个向量以一种特定的方式进行反射变换,使得它除了一个维度以外的其他所有分量都化为0。
令 x {\displaystyle \mathbf {x} } 为矩阵 A {\displaystyle A} 的任一m 维实列向量,且有 ‖ x ‖ = | α | {\displaystyle \|\mathbf {x} \|=|\alpha |} (其中 α {\displaystyle \alpha } 为标量)。若该算法是通过浮点数 实现的,则 α {\displaystyle \alpha } 应当取和 x {\displaystyle \mathbf {x} } 的第 k {\displaystyle k} 维相反的符号(其中 x k {\displaystyle x_{k}} 是要保留不为0的项),这样做可以避免精度缺失。对于复数的情况,令
α = − e i arg x k ‖ x ‖ {\displaystyle \alpha =-\mathrm {e} ^{\mathrm {i} \arg x_{k}}\|\mathbf {x} \|} (Stoer & Bulirsch 2002 ,p.225),并且在接下来矩阵 Q {\displaystyle Q} 的构造中要将矩阵转置替换为共轭转置。
接下来,设 e 1 {\displaystyle \mathbf {e} _{1}} 为单位向量 ( 1 , 0 , ⋯ , 0 ) T {\displaystyle (1,0,\cdots ,0)^{T}} ,||·||为欧几里德范数 , I {\displaystyle I} 为 m × m {\displaystyle m\times m} 单位矩阵,令
u = x − α e 1 {\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1}} , v = u ‖ u ‖ {\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|}} , Q = I − 2 v v T {\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{T}} 。 或者,若 A {\displaystyle A} 为复矩阵,则
Q = I − ( 1 + w ) v v H {\displaystyle Q=I-(1+w)\mathbf {v} \mathbf {v} ^{H}} ,其中 w = x H v / v H x {\displaystyle w=\mathbf {x} ^{H}\mathbf {v} \mathbf {/} \mathbf {v} ^{H}\mathbf {x} } 式中 x H {\displaystyle \mathbf {x} ^{H}} 是 x {\displaystyle x} 的共轭转置 (亦称埃尔米特共轭 或埃尔米特转置 )。 则 Q {\displaystyle Q} 为一个 m × m {\displaystyle m\times m} 的Householder矩阵,它满足
Q x = ( α , 0 , ⋯ , 0 ) T {\displaystyle Q\mathbf {x} =(\alpha ,0,\cdots ,0)^{T}\ } 利用Householder矩阵,可以将一个 m × n {\displaystyle m\times n} 的矩阵 A ′ {\displaystyle A'} 变换为上三角矩阵。 首先,我们将A左乘通过选取矩阵的第一列得到列向量 x {\displaystyle x} 的Householder矩阵 Q 1 {\displaystyle Q_{1}} 。这样,我们得到的矩阵 Q 1 A {\displaystyle Q_{1}A} 的第一列将全部为0(第一行除外):
Q 1 A = [ α 1 ⋆ … ⋆ 0 ⋮ A ′ 0 ] {\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}} 这个过程对于矩阵 A ′ {\displaystyle A'} (即 Q 1 A {\displaystyle Q_{1}A} 排除第一行和第一列之后剩下的方阵)还可以继续做下去,从而得到另一个Householder矩阵 Q 2 {\displaystyle Q_{2}} 。注意到 Q 2 {\displaystyle Q_{2}} 其实比 Q 1 {\displaystyle Q_{1}} 要小,因为它是在 Q 1 A {\displaystyle Q_{1}A} 而非 A {\displaystyle A} 的基础上得到的。因此,我们需要在 Q 2 {\displaystyle Q_{2}} 的左上角补上1,或者,更一般地来说:
Q k = [ I k − 1 0 0 Q k ′ ] {\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}} 将这个迭代过程进行 t {\displaystyle t} 次之后( t = min ( m − 1 , n ) {\displaystyle t=\min(m-1,n)} ),将有
R = Q t ⋯ Q 2 Q 1 A {\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A} 其中R为一个上三角矩阵。因此,令
Q = Q 1 T Q 2 T ⋯ Q t T , {\displaystyle Q=Q_{1}^{T}Q_{2}^{T}\cdots Q_{t}^{T},} 则 A = Q R {\displaystyle A=QR} 为矩阵 A {\displaystyle A} 的一个QR分解。
相比与Gram-Schmidt正交化,使用Householder变换具有更好的数值稳定性 。
例子 现在要用Householder变换求解矩阵 A {\displaystyle A} 的 Q R {\displaystyle QR} 分解。
A = [ 0 3 1 0 4 − 2 2 1 1 ] {\displaystyle A={\begin{bmatrix}0&3&1\\0&4&-2\\2&1&1\\\end{bmatrix}}} 因为 α 1 = [ 0 , 0 , 2 ] T {\displaystyle \alpha _{1}=[0,\ 0,\ 2]^{T}} , 令 a 1 = | | α 1 | | 2 = 2 {\displaystyle a_{1}=||\alpha _{1}||_{2}=2} ,则
ω 1 = α 1 − a 1 e 1 | | α 1 − a 1 e 1 | | 2 = 1 2 [ − 1 , 0 , 1 ] T {\displaystyle \omega _{1}={\frac {\alpha _{1}-a_{1}e_{1}}{||\alpha _{1}-a_{1}e_{1}||_{2}}}={\frac {1}{\sqrt {2}}}[-1,\ 0,\ 1]^{T}} 则有
H 1 = I − 2 ω 1 ω 1 H = [ 0 0 1 0 1 0 1 0 0 ] {\displaystyle H_{1}=I-2\omega _{1}\omega _{1}^{H}={\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\\\end{bmatrix}}} 从而,
H 1 A = [ 2 1 1 0 4 − 2 0 3 1 ] {\displaystyle H_{1}A={\begin{bmatrix}2&1&1\\0&4&-2\\0&3&1\\\end{bmatrix}}} 记 β = [ 4 , 3 ] T {\displaystyle \beta =[4,\ 3]^{T}} , 则 b 1 = | | β 2 | | 2 = 5 {\displaystyle b_{1}=||\beta _{2}||_{2}=5} 。令
ω 2 = β 2 − b 1 e 1 | | β 2 − b 1 e 1 | | 2 = 1 10 [ − 1 , 3 ] T {\displaystyle \omega _{2}={\frac {\beta _{2}-b_{1}e_{1}}{||\beta _{2}-b_{1}e_{1}||_{2}}}={\frac {1}{\sqrt {10}}}[-1,\ 3]^{T}} H 2 ^ = I − 2 ω 2 ω H = 1 5 [ 4 3 3 − 4 ] {\displaystyle {\hat {H_{2}}}=I-2\omega _{2}\omega ^{H}={\frac {1}{5}}{\begin{bmatrix}4&3\\3&-4\\\end{bmatrix}}} 记,
H 2 = [ 1 0 T 0 H 2 ^ ] = [ 1 0 0 0 4 5 3 5 0 3 5 − 4 5 ] {\displaystyle H_{2}={\begin{bmatrix}1&0^{T}\\0&{\hat {H_{2}}}\\\end{bmatrix}}={\begin{bmatrix}1&0&0\\0&{\frac {4}{5}}&{\frac {3}{5}}\\0&{\frac {3}{5}}&-{\frac {4}{5}}\\\end{bmatrix}}} 则,
R = H 2 ( H 1 A ) = [ 2 1 1 0 5 − 1 0 0 − 2 ] {\displaystyle R=H_{2}(H_{1}A)={\begin{bmatrix}2&1&1\\0&5&-1\\0&0&-2\\\end{bmatrix}}} 那么
Q = H 1 H 2 = 1 5 [ 0 3 − 4 0 4 3 5 0 0 ] {\displaystyle Q=H_{1}H_{2}={\frac {1}{5}}{\begin{bmatrix}0&3&-4\\0&4&3\\5&0&0\\\end{bmatrix}}}
使用吉文斯旋转
吉文斯旋转 吉文斯旋转表示为如下形式的矩阵
G ( i , j , θ ) = [ 1 ⋯ 0 ⋯ 0 ⋯ 0 ⋮ ⋱ ⋮ ⋮ ⋮ 0 ⋯ c ⋯ − s ⋯ 0 ⋮ ⋮ ⋱ ⋮ ⋮ 0 ⋯ s ⋯ c ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 ⋯ 0 ⋯ 0 ⋯ 1 ] {\displaystyle G(i,j,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots &-s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}}} 这里的 c = cos(θ ) 和 s = sin(θ ) 出现在第 i 行和第 j 行与第 i 列和第 j 列的交叉点上。就是说,吉文斯旋转矩阵的所有非零元定义如下::
g k k = 1 for k ≠ i , j g i i = c g j j = c g i j = s g j i = − s {\displaystyle {\begin{aligned}g_{k\,k}&{}=1\qquad {\text{for}}\ k\neq i,\,j\\g_{i\,i}&{}=c\\g_{j\,j}&{}=c\\g_{i\,j}&{}=s\\g_{j\,i}&{}=-s\end{aligned}}} 乘积 G (i , j , θ )x 表示向量 x 在 (i ,j )平面中的逆时针旋转 θ 弧度。
吉文斯旋转作用于QR分解 对于一个向量
A = [ a b ] {\displaystyle {\begin{array}{lcl}A&=&{\begin{bmatrix}a\\b\\\end{bmatrix}}\\\end{array}}} 如果, r = a 2 + b 2 {\displaystyle r={\sqrt {a^{2}+b^{2}}}} , c = a r {\displaystyle c={\frac {a}{r}}} , s = − b r {\displaystyle s=-{\frac {b}{r}}} , 那么,就存在旋转矩阵G,使 A {\displaystyle A} 底部转成0。
A 2 _ S u b = [ c − s s c ] [ a b ] = [ r 0 ] {\displaystyle A_{2\_Sub}={\begin{bmatrix}c&-s\\s&c\\\end{bmatrix}}{\begin{bmatrix}a\\b\\\end{bmatrix}}={\begin{bmatrix}r\\0\\\end{bmatrix}}} 每一次的旋转,吉文斯旋转都可以将一个元素化成0,直到将原始矩阵转成一个上三角矩阵,则完成分解。
A = Q R {\displaystyle A=QR} Q = G 1 T G 2 T ⋯ G k T {\displaystyle Q=G_{1}^{T}G_{2}^{T}\cdots G_{k}^{T}}
例子 A 1 = [ 6 5 0 5 1 4 0 4 3 ] {\displaystyle A_{1}={\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}}} r = 6 2 + 5 2 ≈ 7.8102 {\displaystyle r={\sqrt {6^{2}+5^{2}}}\approx 7.8102} c = 6 / r ≈ 0.7682 {\displaystyle c=6/r\approx 0.7682} s = − 5 / r ≈ − 0.6402 {\displaystyle s=-5/r\approx -0.6402} A 2 = G 1 A 1 = [ c − s 0 s c 0 0 0 1 ] [ 6 5 0 5 1 4 0 4 3 ] ≈ [ 7.8102 4.4813 2.5607 0 − 2.4327 3.0729 0 4 3 ] {\displaystyle A_{2}=G_{1}A_{1}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\\\end{bmatrix}}{\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}} 对于: A 2 {\displaystyle A_{2}} 子矩阵 : A 2 _ S u b {\displaystyle A_{2\_Sub}}
A 2 _ S u b = [ − 2.4327 3.0729 4 3 ] {\displaystyle A_{2\_Sub}={\begin{bmatrix}-2.4327&3.0729\\4&3\\\end{bmatrix}}} r = ( − 2.4327 ) 2 + 4 2 ≈ 4.6817 {\displaystyle r={\sqrt {(-2.4327)^{2}+4^{2}}}\approx 4.6817} c = − 2.4327 / r ≈ − 0.5196 {\displaystyle c=-2.4327/r\approx -0.5196} s = − 5 / r ≈ − 0.8544 {\displaystyle s=-5/r\approx -0.8544} G 2 A 2 = [ 1 0 0 0 c − s 0 s c ] [ 7.8102 4.4813 2.5607 0 − 2.4327 3.0729 0 4 3 ] ≈ [ 7.8102 4.4813 2.5607 0 4.6817 0.9664 0 0 − 4.1843 ] {\displaystyle G_{2}A_{2}={\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\\\end{bmatrix}}{\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&4.6817&0.9664\\0&0&-4.1843\\\end{bmatrix}}} R = G 2 A 2 = G 2 G 1 A 1 {\displaystyle R=G_{2}A_{2}=G_{2}G_{1}A_{1}} Q = G 1 T G 2 T = [ 0.7682 0.3327 0.5470 0.6402 − 0.3992 − 0.6564 0 0.8544 − 0.5196 ] {\displaystyle Q=G_{1}^{T}G_{2}^{T}={\begin{bmatrix}0.7682&0.3327&0.5470\\0.6402&-0.3992&-0.6564\\0&0.8544&-0.5196\\\end{bmatrix}}}
使用格拉姆-施密特正交化方法
基本思想 图1 v {\displaystyle {\boldsymbol {v}}} 在 V 2 {\displaystyle {\boldsymbol {V}}^{2}} 上投影,构造 V 3 {\displaystyle {\boldsymbol {V}}^{3}} 上的正交基 β {\displaystyle {\boldsymbol {\beta }}} 格拉姆-施密特正交化的基本想法,是利用投影原理在已有正交基的基础上构造一个新的正交基。
设 v ∈ V n {\displaystyle {\boldsymbol {v}}\in {\boldsymbol {V^{n}}}} 。 V k {\displaystyle {\boldsymbol {V}}^{k}} 是 V n {\displaystyle {\boldsymbol {V}}^{n}} 上的 k {\displaystyle k} 维子空间,其标准正交基为 { η 1 , … , η k } {\displaystyle \{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k}\}} ,且 v {\displaystyle {\boldsymbol {v}}} 不在 V k {\displaystyle {\boldsymbol {V}}^{k}} 上。由投影原理知, v {\displaystyle {\boldsymbol {v}}} 与其在 V k {\displaystyle {\boldsymbol {V}}^{k}} 上的投影 p r o j V k v {\displaystyle \mathrm {proj} _{\boldsymbol {V^{k}}}{\boldsymbol {v}}} 之差
β = v − ∑ i = 1 k p r o j η i v = v − ∑ i = 1 k ⟨ v , η i ⟩ η i {\displaystyle {\boldsymbol {\beta }}={\boldsymbol {v}}-\sum _{i=1}^{k}\mathrm {proj} _{{\boldsymbol {\eta }}_{i}}\,{\boldsymbol {v}}={\boldsymbol {v}}-\sum _{i=1}^{k}\langle {\boldsymbol {v}},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i}} 是正交于子空间 V k {\displaystyle {\boldsymbol {V}}^{k}} 的,亦即 β {\displaystyle {\boldsymbol {\beta }}} 正交于 V k {\displaystyle {\boldsymbol {V}}^{k}} 的正交基 η i {\displaystyle {\boldsymbol {\eta }}_{i}} 。因此只要将 β {\displaystyle {\boldsymbol {\beta }}} 单位化,即
η k + 1 = β ‖ β ‖ = β ⟨ β , β ⟩ {\displaystyle {\boldsymbol {\eta }}_{k+1}={\frac {\boldsymbol {\beta }}{\|{\boldsymbol {\beta }}\|}}={\frac {\boldsymbol {\beta }}{\sqrt {\langle {\boldsymbol {\beta }},{\boldsymbol {\beta }}\rangle }}}} 那么 { η 1 , … , η k , η k + 1 } {\displaystyle \{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{k},{\boldsymbol {\eta }}_{k+1}\}} 就是 V k {\displaystyle {\boldsymbol {V}}^{k}} 在 v {\displaystyle {\boldsymbol {v}}} 上扩展的子空间 s p a n { v , η 1 , . . . , η k } {\displaystyle \mathrm {span} \{{\boldsymbol {v}},{\boldsymbol {\eta }}_{1},...,{\boldsymbol {\eta }}_{k}\}} 的标准正交基。
根据上述分析,对于向量组 { v 1 , … , v m } {\displaystyle \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{m}\}} 张成的空间 V m {\displaystyle {\boldsymbol {V}}^{m}} ( m < n {\displaystyle m<n} ),只要从其中一个向量(不妨设为 v 1 {\displaystyle {\boldsymbol {v}}_{1}} )所张成的一维子空间 s p a n { v 1 } {\displaystyle \mathrm {span} \{{\boldsymbol {v}}_{1}\}} 开始(注意到 v 1 {\displaystyle {\boldsymbol {v}}_{1}} 就是 s p a n { v 1 } {\displaystyle \mathrm {span} \{{\boldsymbol {v}}_{1}\}} 的正交基),重复上述扩展构造正交基的过程,就能够得到 V n {\displaystyle {\boldsymbol {V}}^{n}} 的一组正交基。这就是格拉姆-施密特正交化 。
格拉姆-施密特正交化算法 首先需要确定已有基底向量的顺序,不妨设为 { v 1 , … , v n } {\displaystyle \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}} 。Gram-Schmidt正交化的过程如下:
β 1 = v 1 , {\displaystyle {\boldsymbol {\beta }}_{1}={\boldsymbol {v}}_{1},} η 1 = β 1 ‖ β 1 ‖ {\displaystyle {\boldsymbol {\eta }}_{1}={{\boldsymbol {\beta }}_{1} \over \|{\boldsymbol {\beta }}_{1}\|}} β 2 = v 2 − ⟨ v 2 , η 1 ⟩ η 1 , {\displaystyle {\boldsymbol {\beta }}_{2}={\boldsymbol {v}}_{2}-\langle {\boldsymbol {v}}_{2},{\boldsymbol {\eta }}_{1}\rangle {\boldsymbol {\eta }}_{1},} η 2 = β 2 ‖ β 2 ‖ {\displaystyle {\boldsymbol {\eta }}_{2}={{\boldsymbol {\beta }}_{2} \over \|{\boldsymbol {\beta }}_{2}\|}} β 3 = v 3 − ⟨ v 3 , η 1 ⟩ η 1 − ⟨ v 3 , η 2 ⟩ η 2 , {\displaystyle {\boldsymbol {\beta }}_{3}={\boldsymbol {v}}_{3}-\langle {\boldsymbol {v}}_{3},{\boldsymbol {\eta }}_{1}\rangle {\boldsymbol {\eta }}_{1}-\langle {\boldsymbol {v}}_{3},{\boldsymbol {\eta }}_{2}\rangle {\boldsymbol {\eta }}_{2},} η 3 = β 3 ‖ β 3 ‖ {\displaystyle {\boldsymbol {\eta }}_{3}={{\boldsymbol {\beta }}_{3} \over \|{\boldsymbol {\beta }}_{3}\|}} ⋮ {\displaystyle \vdots } ⋮ {\displaystyle \vdots } β n = v n − ∑ i = 1 n − 1 ⟨ v n , η i ⟩ η i , {\displaystyle {\boldsymbol {\beta }}_{n}={\boldsymbol {v}}_{n}-\sum _{i=1}^{n-1}\langle {\boldsymbol {v}}_{n},{\boldsymbol {\eta }}_{i}\rangle {\boldsymbol {\eta }}_{i},} η n = β n ‖ β n ‖ {\displaystyle {\boldsymbol {\eta }}_{n}={{\boldsymbol {\beta }}_{n} \over \|{\boldsymbol {\beta }}_{n}\|}}
这样就得到 s p a n { v 1 , … , v n } {\displaystyle \mathrm {span} \{{\boldsymbol {v}}_{1},\ldots ,{\boldsymbol {v}}_{n}\}} 上的一组正交基 { β 1 , … , β n } {\displaystyle \{{\boldsymbol {\beta }}_{1},\ldots ,{\boldsymbol {\beta }}_{n}\}} ,以及相应的标准正交基 { η 1 , … , η n } {\displaystyle \{{\boldsymbol {\eta }}_{1},\ldots ,{\boldsymbol {\eta }}_{n}\}} 。
例子 现在要用格拉姆-施密特变换求解矩阵 A {\displaystyle A} 的 Q R {\displaystyle QR} 分解。
A = [ 1 2 4 0 0 5 0 3 6 ] {\displaystyle A={\begin{bmatrix}1&2&4\\0&0&5\\0&3&6\\\end{bmatrix}}} 令, a = [ 1 , 0 , 0 ] {\displaystyle a=[1,0,0]}
q 1 = a | | a | | = [ 1 0 0 ] {\displaystyle q_{1}={\frac {a}{||a||}}={\begin{bmatrix}1\\0\\0\\\end{bmatrix}}} q 2 ^ = b − ( b ∗ q 1 ) q 1 = [ 2 0 3 ] − 2 [ 1 0 0 ] = [ 0 0 3 ] {\displaystyle {\hat {q_{2}}}=b-(b*q_{1})q_{1}={\begin{bmatrix}2\\0\\3\\\end{bmatrix}}-2{\begin{bmatrix}1\\0\\0\\\end{bmatrix}}={\begin{bmatrix}0\\0\\3\\\end{bmatrix}}} q 2 = q 2 ^ | | q 2 ^ | | = [ 0 0 1 ] {\displaystyle q_{2}={\frac {\hat {q_{2}}}{||{\hat {q_{2}}}||}}={\begin{bmatrix}0\\0\\1\\\end{bmatrix}}} q 3 ^ = c − ( c ∗ q 1 ) q 1 − ( c ∗ q 2 ) q 2 = [ 4 5 6 ] − 4 [ 1 0 0 ] − 6 [ 0 0 1 ] = [ 0 5 0 ] {\displaystyle {\hat {q_{3}}}=c-(c*q_{1})q_{1}-(c*q_{2})q_{2}={\begin{bmatrix}4\\5\\6\\\end{bmatrix}}-4{\begin{bmatrix}1\\0\\0\\\end{bmatrix}}-6{\begin{bmatrix}0\\0\\1\\\end{bmatrix}}={\begin{bmatrix}0\\5\\0\\\end{bmatrix}}} q 3 = q 3 ^ | | q 3 ^ | | = [ 0 1 0 ] {\displaystyle q_{3}={\frac {\hat {q_{3}}}{||{\hat {q_{3}}}||}}={\begin{bmatrix}0\\1\\0\\\end{bmatrix}}} 那么可知,
Q = [ 1 0 0 0 0 1 0 1 0 ] {\displaystyle Q={\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\\\end{bmatrix}}} 由 A = Q R {\displaystyle A=QR} ,可知,
R = [ 1 2 4 0 3 6 0 0 5 ] {\displaystyle R={\begin{bmatrix}1&2&4\\0&3&6\\0&0&5\\\end{bmatrix}}}
Matlab MATLAB以qr函数来执行QR分解法,其语法为
[ Q , R ] = q r ( A ) {\displaystyle [Q,R]=qr(A)} 其中Q代表正规正交矩阵, 而R代表上三角形矩阵。 此外,原矩阵A不必为正方矩阵; 如果矩阵A大小为 m × n {\displaystyle m\times n} ,则矩阵Q大小为 m × m {\displaystyle m\times m} ,矩阵R大小为 m × n {\displaystyle m\times n} 。
用途
解线性方程组 对于直接求解线性方程组的逆,用QR分解的方法求解会更具有数据的稳定性。 对于求解一个线性系统 A x = b {\displaystyle Ax=b} , 这里 A {\displaystyle A} 的维度是 m × n {\displaystyle m\times n} 。
如果 m ≤ n {\displaystyle m\leq n} , 那么 A T = Q R {\displaystyle A^{T}=QR} ,这里 Q T = Q − 1 {\displaystyle Q^{T}=Q^{-1}} )。
R {\displaystyle R} 的形式是 R = [ R 1 0 ] {\displaystyle R={\begin{bmatrix}R_{1}\\0\end{bmatrix}}} , R 1 {\displaystyle R_{1}} 是 R {\displaystyle R} 上不为0的部分。 那么对于
x = Q [ ( R 1 T ) − 1 b 0 ] {\displaystyle x=Q{\begin{bmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}b\\0\end{bmatrix}}} 如果 m > n {\displaystyle m>n} , 那么 A = Q R {\displaystyle A=QR} ,这里 Q T = Q − 1 {\displaystyle Q^{T}=Q^{-1}} )。本质是最小化 | | A x ^ − b | | {\displaystyle ||A{\hat {x}}-b||}
x ^ = R 1 − 1 ( Q 1 T b ) {\displaystyle {\hat {x}}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}b\right)}
參考文獻 ^ Trefethen, Lloyd N.; Bau, David III. Numerical linear algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics. 1997. ISBN 978-0-898713-61-9.
外部連結 MIT. QR Decomposition. Youtube. [2020-07-01 ] . (原始内容存档于2020-07-27). Poujh. QR Decomposition Givens旋转. Youtube. [2020-07-01 ] . (原始内容存档于2020-09-01).