3.3QR分解·83-其中R11ERnxn为上三角矩阵由QR分解的存在性证明过程可知，当A不是满秩矩阵时，存在一个置换矩阵P，使得AP的前r列是线性无关的，其中r=rank(A).因此我们可以对AP进行QR分解，于是我们可以得到下面的结论推论3.8设AECmxn(m≥n).则存在一个置换矩阵 P,使得3.1R1AP其中QECmxn单位列正交,R11ECrxT是非奇异上三角矩阵十上述结论也可简化为AP=QR11其中QECmxr单位列正交,RiiECrxr是非奇异上三角矩阵十通过GS正交化过程实现的QR分解中，Q和R都可能是复矩阵如果A是实矩阵，则上面证明中的运算都可以在实数下进行，因此Q和R都可以是实矩阵十如果A是非奇异的方阵，则QR分解也可以用来求解线性方程组Ar=b.+基于GS正交化的QR分解算法3.3的运算量大约为2mn?.在后面，我们会介绍基于Household变换的QR分解，在不需要计算Q的情况下，运算量大约为2mn2-2n3/3;如果需要计算Q,则需另外大约2mn2-2m3/3运算量推论3.9(满秩分解)设 A E Cmxn 且 rank(A)= l ≤ min(m,n),则存在满秩矩阵 F E Cmxl 和GEClxn,使得A=FG.下面给出OR分解的具体实现方法，分别基于MGS过程，Householder变换和Givens变换3.3.2基于MGS的QR分解在证明QR分解的存在性时，我们利用了Gram-Schmidt正交化过程。但由于数值稳定性方面的原因，在实际计算中，我们一般不采用Gram-Schmidt过程，取而代之的是修正的Gram-Schmidt过程（mod-ifiedGram-Schmidtprocess)，即MGS.本算法的运算量大约为2mn?算法3.4.基于MGS的QR分解%GivenAERmxn,computeQ=[q1....,qn]ERmxnandRERnxn suchthatA=QR1: Set R = [rix] = Onxn (the n X n zero matrix)
3.3 QR 分解 · 83 · 其中 R11 ∈ R n×n 为上三角矩阵. 由 QR 分解的存在性证明过程可知, 当 A 不是满秩矩阵时, 存在一个置换矩阵 P, 使得 AP 的前 r 列是线性无关的, 其中 r = rank(A). 因此我们可以对 AP 进行 QR 分解, 于是我们可以得到下面的结 论. 推论 3.8 设 A ∈ C m×n (m ≥ n). 则存在一个置换矩阵 P, 使得 AP = Q [ R11 R12 0 0 ] n×n , 其中 Q ∈ C m×n 单位列正交, R11 ∈ C r×r 是非奇异上三角矩阵. † 上述结论也可简化为 AP = Q [ R11 R12] , 其中 Q ∈ C m×r 单位列正交, R11 ∈ C r×r 是非奇异上三角矩阵. † 通过 GS 正交化过程实现的 QR 分解中, Q 和 R 都可能是复矩阵. 如果 A 是实矩阵, 则上面证明 中的运算都可以在实数下进行, 因此 Q 和 R 都可以是实矩阵. † 如果 A 是非奇异的方阵, 则 QR 分解也可以用来求解线性方程组 Ax = b. † 基于 GS 正交化的 QR 分解算法 3.3 的运算量大约为 2mn2 . 在后面, 我们会介绍基于 Household 变换的 QR 分解, 在不需要计算 Q 的情况下, 运算量大约为 2mn2 − 2n 3/3; 如果需要计算 Q, 则 需另外大约 2mn2 − 2n 3/3 运算量. 推论 3.9 (满秩分解) 设 A ∈ C m×n 且 rank(A) = l ≤ min{m, n}, 则存在满秩矩阵 F ∈ C m×l 和 G ∈ C l×n, 使得 A = F G. 下面给出 QR 分解的具体实现方法, 分别基于 MGS 过程, Householder 变换和 Givens 变换. 3.3.2 基于 MGS 的 QR 分解 在证明 QR 分解的存在性时, 我们利用了 Gram-Schmidt 正交化过程. 但由于数值稳定性方面的原 因, 在实际计算中, 我们一般不采用 Gram-Schmidt 过程, 取而代之的是 修正的 Gram-Schmidt 过程 (modified Gram-Schmidt process), 即 MGS . 本算法的运算量大约为 2mn2 . 算法 3.4. 基于 MGS 的 QR 分解 % Given A ∈ R m×n, compute Q = [q1, . . . , qn] ∈ R m×n and R ∈ R n×n such that A = QR 1: Set R = [rik] = 0n×n (the n × n zero matrix)
.84.第三讲线性最小二乘问题2:ifai=0then3:q1 = 04:else5:r11 = [[a1l26:q1 = a1/llall27: endif8:fork=2tondo9:qk = akfori=ltok-ldo10:11:rik=qiqk12:qk=qk-Tikqiend for13:14:if qk0then15:Tkk=Iql/216:qk= qk/rkkendif17:18: end for+由MGS得到的QR分解中QERmxn,RERnxn3.3.3基于Householder变换的QR分解由定理3.4可知，通过Householder变换，我们可以将任何一个非零变量ERn转化成rl2ei，即除第一个元素外，其它都为零.下面我们就考虑通过Householder变换来实现矩阵的QR分解。我们首先考虑m=n时的情形.设矩阵AERnxn，令HiERnxn为一个Householder变换，满足r1a110a21H.0anl于是T10120H,A:..A0其中 A2 ER(n-1)x(n-1).同样地,我们可以构造一个Householder变换 H2ER(n-1)x(n-1),将 A2的第
· 84 · 第三讲 线性最小二乘问题 2: if a1 = 0 then 3: q1 = 0 4: else 5: r11 = ∥a1∥2 6: q1 = a1/∥a1∥2 7: end if 8: for k = 2 to n do 9: qk = ak 10: for i = 1 to k − 1 do 11: rik = q ⊺ i qk 12: qk = qk − rikqi 13: end for 14: if qk ̸= 0 then 15: rkk = ∥qk∥2 16: qk = qk/rkk 17: end if 18: end for † 由 MGS 得到的 QR 分解中, Q ∈ R m×n, R ∈ R n×n. 3.3.3 基于 Householder 变换的 QR 分解 由定理 3.4 可知, 通过 Householder 变换, 我们可以将任何一个非零变量 x ∈ R n 转化成 ∥x∥2e1, 即 除第一个元素外, 其它都为零. 下面我们就考虑通过 Householder 变换来实现矩阵的 QR 分解. 我们首先考虑 m = n 时的情形. 设矩阵 A ∈ R n×n, 令 H1 ∈ R n×n 为一个 Householder 变换, 满足 H1 a11 a21 . . . an1 = r1 0 . . . 0 . 于是 H1A = r1 a˜12 · · · a˜1n 0 . . . A˜ 2 0 , 其中 A˜ 2 ∈ R (n−1)×(n−1) . 同样地, 我们可以构造一个 Householder 变换 H˜ 2 ∈ R (n−1)×(n−1) , 将 A˜ 2 的第
3.3QR分解.85.一列中除第一个元素外的所有元素都化为0，即a23a2n12...0H2A2 =A30令0H2i210则HzERnxn,且a12ainria130a23a2nr200H,HiA=::A300不断重复上述过程.这样，我们就得到一系列的矩阵Ik-0H.=1,2,3,4,...,n-1H0使得ai2..ainT10r2..a2nR.Hn-1...H2HiA-:00...Tn由于Householder变换都是正交矩阵，因此Hi,H2..,Hn-1也都是正交矩阵.令Q=(Hn-1.H,Hi)-1=H-"Hz....H--1=H,H2.Hn-1,则Q也是正交矩阵，且A=(Hn-1..H2Hi)-1R=QR以上就是基于Householder变换的QR分解的具体实现过程.最后所得到的上三角矩阵R就存放在A的上三角部分，矩阵Q可通过下面的算法实现Q= In,Q=QHk,k=1,2...,n-1+这里我们假定A是满秩的，如果A不是满秩，则可以考虑列主元QR分解
3.3 QR 分解 · 85 · 一列中除第一个元素外的所有元素都化为 0, 即 H˜ 2A˜ 2 = r2 a˜23 · · · a˜2n 0 . . . A˜ 3 0 . 令 H2 = [ 1 0 0 H˜ 2 ] . 则 H2 ∈ R n×n, 且 H2H1A = r1 a˜12 a˜13 · · · a˜1n 0 r2 a˜23 · · · a˜2n 0 0 . . . . . . A˜ 3 0 0 . 不断重复上述过程. 这样, 我们就得到一系列的矩阵 Hk = [ Ik−1 0 0 H˜ k ] , k = 1, 2, 3, 4, . . . , n − 1 使得 Hn−1 · · · H2H1A = r1 a˜12 · · · a˜1n 0 r2 · · · a˜2n . . . . . . . . . 0 0 · · · rn ≜ R. 由于 Householder 变换都是正交矩阵, 因此 H1, H2, . . . , Hn−1 也都是正交矩阵. 令 Q = (Hn−1 · · · H2H1) −1 = H −1 1 H −1 2 · · · H −1 n−1 = H1H2 · · · Hn−1, 则 Q 也是正交矩阵, 且 A = (Hn−1 · · · H2H1) −1R = QR. 以上就是基于 Householder 变换的 QR 分解的具体实现过程. 最后所得到的上三角矩阵 R 就存放在 A 的上三角部分. 矩阵 Q 可通过下面的算法实现 Q = In, Q = QHk, k = 1, 2, . . . , n − 1. † 这里我们假定 A 是满秩的, 如果 A 不是满秩, 则可以考虑列主元 QR 分解