数值分析 第三讲线性最小二乘问题 QR分解 专 目录 3.1问题介绍 3.2 Householder变换和Givens变换 3.3QR分解 M 3.4奇异值分解 3.5线性最小二乘问题的求解方法 https://math.ecnu.edu.cn/-jypan/Teaching/NA
数值分析 第三讲 线性最小二乘问题 QR 分解 3.1 问题介绍 3.2 Householder 变换和 Givens 变换 3.3 QR 分解 3.4 奇异值分解 3.5 线性最小二乘问题的求解方法 目录 https://math.ecnu.edu.cn/~jypan/Teaching/NA
3-3|OR分解 3.3QR分解 3.3.1QR分解的存在性与唯一性 3.3.2基于MGS的QR分解 3.3.3基于Householder分解的QR分解 3.3.4基于Givens变换的QR分解 3.3.5 QR分解的稳定性 潘建瑜@MATH.ECNU https://math.ecnu.edu.cn/~jypan/Teaching/NA
3-3 QR 分解 3.3 QR 分解 3.3.1 QR 分解的存在性与唯一性 3.3.2 基于 MGS 的 QR 分解 3.3.3 基于 Householder 分解的 QR 分解 3.3.4 基于 Givens 变换的 QR 分解 3.3.5 QR 分解的稳定性 潘建瑜 @MATH.ECNU https://math.ecnu.edu.cn/~jypan/Teaching/NA
QR分解 A-QR 全Q分解是将一个矩阵分解一个正交矩阵（酉矩阵）和一个三角矩阵的乘积 空Q分解被广泛应用于线性最小二乘问题的求解和矩阵特征值的计算 http://math.ecnu.edu.cn/-jypan 3/25
QR 分解 A = QR QR 分解是将一个矩阵分解一个正交矩阵 (酉矩阵) 和一个三角矩阵的乘积. QR 分解被广泛应用于线性最小二乘问题的求解和矩阵特征值的计算. http://math.ecnu.edu.cn/~jypan 3/25
3-3-1QR分解的存在性与唯一性 定理设A∈Cmxn(m之n,则存在一个单位列正交矩阵Q∈Cmxm(即Q*Q=Inxn) 和一个上三角矩阵R∈Cnxn,使得 A=QR (3.1) 若A列满秩，则存在一个具有正对角线元素的上三角矩阵R使得(3.1)成立，且此时QR 分解唯一，即Q和R都唯一 多存在性可通过构造法证明 假定A列满秩，记A=[a1,a2,.·,an]∈Cmx”,则QR分解就是对A的列向量组进行 Gram-Schmidt正交化过程 http://ath.ecnu.edu.cn/-jypan 4/25
3-3-1 QR 分解的存在性与唯一性 定理 设 A ∈ C m×n (m ≥ n), 则存在一个单位列正交矩阵 Q ∈ C m×n (即 Q∗Q = In×n) 和一个上三角矩阵 R ∈ C n×n , 使得 A = QR (3.1) 若 A 列满秩, 则存在一个具有正对角线元素的上三角矩阵 R 使得 (3.1) 成立, 且此时 QR 分解唯一, 即 Q 和 R 都唯一. 存在性 可通过构造法证明. 假定 A 列满秩, 记 A = [a1, a2, . . . , an] ∈ C m×n , 则 QR 分解就是对 A 的列向量组进行 Gram-Schmidt 正交化过程. http://math.ecnu.edu.cn/~jypan 4/25
算法Gram-Schmidt过程 1:r11=llaill2 2:q1=a1/T11 3:for j=2 to n do 4: qi=aj 5: for i=1toj-1 do 6: r)=aj%g表示共轭转置 7: qj=qi-rijqi 8: end for 9 ris llgjlle 10: 4贴=巧/T方 11:end for http://math.ecnu.edu.cn/-jypan 5/25
算法 Gram-Schmidt 过程 1: r11 = ∥ a 1 ∥ 2 2: q 1 = a 1 / r11 3: for j = 2 to n do 4: qj = a j 5: for i = 1 to j − 1 do 6: rij = q ∗i a j % q ∗i 表示共轭转置 7: qj = qj − rij q i 8: end for 9: rjj = ∥ qj ∥ 2 10: qj = qj / rjj 11: end for http://math.ecnu.edu.cn/~jypan 5/25
由Gram-Schmidt正交化过程可知 T2j a1=T1191,a5=T1j91+T2592+…+Tj9=[91,92,…,95l 记Q=[q1,q2,,9nl,R=[rij]nxn,其中 rijl qiaj, fori≤j T= (3.2) 0, fori>j 则 T11 T12 Tin T22 T2n [a1,a2,,an=[q1,92,,9n ,即A=QR Tn-1n Tnn http://nath.ecnu.edu.cn/-jypan 6/25
由 Gram-Schmidt 正交化过程可知 a1 = r11q1, aj = r1jq1 + r2jq2 + · · · + rjjqj = [q1, q2, . . . , qj ] r1j r2j . . . rjj 记 Q = [q1, q2, . . . , qn], R = [rij ]n×n, 其中 rij = q ∗ i aj , for i ≤ j 0, for i > j (3.2) 则 [a1, a2, . . . , an] = [q1, q2, . . . , qn] r11 r12 · · · r1n r22 · · · r2n . . . rn−1,n rnn , 即 A = QR http://math.ecnu.edu.cn/~jypan 6/25
都A不满秩情形：参见讲义。 多A满秩时的QR分解的存在唯一性：板书. http://math.ecnu.edu.cn/-jypan 7/25
A 不满秩情形: 参见讲义. A 满秩时的 QR 分解的存在唯一性: 板书. http://math.ecnu.edu.cn/~jypan 7/25
QR分解的另一种形式 有时也将QR分解定义为：存在酉矩阵Q∈Cmxm使得 A=QR 其中R [B1 Cmxn是上三角矩阵 http://nath.ecnu.edu.cn/-jypan 8/25
QR 分解的另一种形式 有时也将 QR 分解定义为: 存在酉矩阵 Q ∈ C m×m 使得 A = QR , 其中 R = [ R11 0 ] ∈ C m×n 是上三角矩阵. http://math.ecnu.edu.cn/~jypan 8/25
A不是满秩矩阵情形 多设rak(A)=r≤n,则存在置换矩阵P,使得AP的前r列是线性无关。 因此我们可以对AP进行QR分解 http://math.ecnu.edu.cn/-jypan 9/25
A 不是满秩矩阵情形 设 rank(A) = r ≤ n, 则存在置换矩阵 P, 使得 AP 的前 r 列是线性无关. 因此我们可以对 AP 进行 QR 分解. 推论 设 A ∈ C m×n (m ≥ n), 且秩为 r (0 ≤ r ≤ 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 http://math.ecnu.edu.cn/~jypan 9/25
A不是满秩矩阵情形 多设rak(A)=r≤n,则存在置换矩阵卫，使得AP的前r列是线性无关。 因此我们可以对AP进行QR分解 推论设A∈Cmxm(m≥n,且秩为r(0≤r≤n,则存在一-个置换矩阵P,使得 AP=Q R11R12 00 nxn 其中Q∈Cmxn单位列正交，R1∈Crxr是非奇异上三角矩阵. http://nath.ecnu.edu.cn/-jypan 9/25
A 不是满秩矩阵情形 设 rank(A) = r ≤ n, 则存在置换矩阵 P, 使得 AP 的前 r 列是线性无关. 因此我们可以对 AP 进行 QR 分解. 推论 设 A ∈ C m×n (m ≥ n), 且秩为 r (0 ≤ r ≤ 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 http://math.ecnu.edu.cn/~jypan 9/25