数值模拟导论 -第五讲 QR分解 雅克布 怀特 感谢 Deepak Ramaswamy, Michal Rewienski,Karen Veroy and Karen Veroy QR分解 SMA-HPC ?2003 MIT 奇异矩阵例子 LU分解的不足之处 拉杆 节点 负载力 虽然上面图形的节点矩阵是一个奇异矩阵，但是仍旧存在一种解法！ QR分解 SMA-HPC ?2003 MIT 奇异矩阵例子 LU分解的不足之处 虽然上面图形的节点矩阵是一个奇异矩阵，但是存在一种解法！ QR分解 SMA-HPC ?2003 MIT 奇异矩阵例子 回顾矩阵各列的加权和，并观察下面的等式。 11 2 2 ... NN xM xM x M b+ ++ = G GG 虽然矩阵 M是奇异矩阵但是向量 B在矩阵 M的列向量组成的向量空间内。 QR分解 SMA-HPC ?2003 MIT 正交化 如果 M有正交列向量 如果两向量正交则： 0 ij M Mij? =≠ G G 用第 i列乘以加权列向量得： 11 2 2 ( ... ) iNNi M xM xM x M M b? +++ =? G GG GG 利用正交向量将方程简化为： () () i ii i i i ii M b xM M M b x M M ? ?=??= ? G G GG G G QR分解 SMA-HPC ?2003 MIT 正交化 矩阵 M正交的几何意义 如果 0 ij M Mij? =≠ GG 且 1 jj MM?= G G 二维向量的几何意义 则矩阵 M正交 非正交 正交 QR分解 SMA-HPC ?2003 MIT 正交化 QR法的基本思想 原始矩阵 带有正交列向量的矩阵 T Qy b y Q b=?= 怎么来完成这一步变换？ QR分解 SMA-HPC ?2003 MIT 正交化 推导公式 给出 12 ,M M GG ，求 22121 QMrM=? G G 满足 ( ) 12 1 2121 0MQ M M rM? =? ? = GGGGG 即必有 12 12 11 M M r M M ? = ? G G G G QR分解 SMA-HPC ?2003 MIT 正交化 标准化 如果我们将向量标准化，公式将会变得简单，因此我们先来将向量 Q1标准化： 1111 11 11 11 1QMMQ r MM ==??= ? GGGG G GG 现在要求 22121 QMrQ=? GGG  以便满足 21 0QQ? = GG  得： 12 1 2 rQM=? G G 最后求得： 222 22 22 11 QQQ r QQ == ? GGG  GG  QR分解 SMA-HPC ?2003 MIT 正交化 2*2矩阵的变化过程 既然 Mx等于 Qy，那么我们可以找到 x与 y之间得关系。 QR分解 SMA-HPC ?2003 MIT 正交化 2*2矩阵的分解过程 标准正交化 上三角 如果给出 QR分解后，需要两步进行求解 第一步 T QRx b Rx Q b b= ?= =  第二步 回代解 Rx b=  QR分解 SMA-HPC ?2003 MIT 正交化 普通矩阵的 QR分解 3× 3矩阵的情况 为了确保第三列正交使： QR分解 SMA-HPC ?2003 MIT 正交化 分解 3*3矩阵必须解方 程求系数 QR分解 SMA-HPC ?2003 MIT 正交化 解方程求系数 将第 N个向量正交化 N2项内积需要 N3 步运算 QR分解 SMA-HPC ?2003 MIT 正交化 使用正交向量 3× 3矩阵的情况 为了保证第三列正交 ： QR分解 SMA-HPC ?2003 MIT 基本运算法则 改进的 Gram-Schmid法 for i＝ 1 n “每一原始列 ” 2 1 2 1 2 N ii i i ii ii i rMM QM N r N = ? =? ? ? = ? ≈ ? ∑ GG G G 需要标准化 步操作 for j＝ i＋ 1到 n 目标列右边的原始列 () 3 1 2 ij j i jjij i i n rMQ MMr NiN Q N = ? ←? ? ? ?? ≈ ? ? ? ∑ GG GGG 步操作 QR分解 SMA-HPC ?2003 MIT 基本运算法则 用图形表示 QR分解 SMA-HPC ?2003 MIT 基本运算法则 用图形表示 QR分解 SMA-HPC ?2003 MIT 基本运算法则 零列 如果有一列元素全为零该怎么办？ 此矩阵肯定是奇异矩阵！ 1.不要去标准正交化这一列。 2.不要将这一列作正交化的原始列。 3.尽可能的执行回代过程。 QR分解 SMA-HPC ?2003 MIT 基本运算法则 零列（序） QR分解结果 QR分解 SMA-HPC ?2003 MIT 奇异矩阵举例 回顾矩阵各列的加权和，并观察下面的等式。 当 M为奇异矩阵时会出现以下两种情况： 1.b属于向量空间 1 { ,..., } N MM b? G GG G 1N 属于向量空间{Q ,...,Q } 1 { ,..., } N MM G G ， x的精确度如何？ 2.b不属于向量空间 QR分解 SMA-HPC ?2003 MIT 最小值法 求解公式 定义残向量 R： R(x)＝ b－ Mx 求解 x，使之满足 Mx＝ b 求 x 使下式获最小值的： () () ()() 2 1 N T i i Rx Rx R x = = ∑ 等价于，如果 b属于向量空间 {cols(M)}推出 Mx＝ b和 () () min 0 T x Rx Rx= 最小值法扩展到非奇异或非平方的情况 QR分解 SMA-HPC ?2003 MIT 最小值法 一维空间最小值法 假设 x＝ 11 xe G ，因此存在 11 11 MxxMe xM== G G 一维空间最小值法 正交标准化 QR分解 SMA-HPC ?2003 MIT 最小值法 一位空间最小值法（图示） 一维最小值法产生的结果和 b在列向量上的投影相一致。 QR分解 SMA-HPC ?2003 MIT 最小值法 二维空间最小值法 现有 11 2 2 xxexe=+ G G 并且 11 2 2 MxxMexMe= + G G 用残向量最小值法 耦合项 QR分解 SMA-HPC ?2003 MIT 最小值法 二维向量最小值法 从更一般的角度考虑 耦合项 如果 12 0 TT pMMp= GG 耦合项为零 QR分解 SMA-HPC ?2003 MIT 最小值法 构建 MTM正交最小化方向 第 i次搜索方向等于 MTM正交化 单位向量 1 1 0 i TT ii jij i j j pe rp pMMp ? = =? = ∑ GG G G G 使用前面得到的正交化搜索方向 ( ) () ()() T ji ji T jj MpMe r MpMp ?= G G G G QR分解 SMA-HPC ?2003 MIT 最小值法 搜索方向上的最小值 单独做去藕最小值求的最小值 ()() 2 2 T T ii i i i vMp Mp vbMp? G GG 将其对 v求导 即： ()() 220 T T ii i i vMp Mp bMp? = G GG 求得 ： ()() T i i T ii bMp v MpMp = G G G QR分解 SMA-HPC ?2003 MIT 最小化 最小化算法 for i=1 到 n 对每一目标列 11 ii pe forj i = =? G G 到 对目标列左边的原始列 TT ij j i iiijj rpMMp pprp ? ← ? ? ?? ? ? GG GGG 正交化搜索方向 1 ii i i ii ii rMpMp pp r ? =? ? ? ? ? ? GG GG 标准化搜索方向 ii xxvp= + G QR分解 SMA-HPC ?2003 MIT 最小化法和 QR分解 法 比较 正交化 MTM正交 化 QR分解 SMA-HPC ?2003 MIT 搜索方向 正交单位向量 ——〉搜索方向 { N12 1 2 , ,..., } { , ,..., } nn MTM ee e pp p? GG G GG G   正交化 搜索方向 单位向量 可以使用其它的初始向量 { N 2 12 , , ,...}{, ,..., } n MTM bMbMb p p p? G GG   正交化 搜索方向 krylov子空间 为什么？ 概述 SMA-HPC ?2003 MIT QR算法 ——投影定理 ——将列向量正交化 ——修改 Gram-Schmidt 算法 QR和奇异矩阵 ——如果矩阵为奇异矩阵，则 Q的某一列为 零 QR分解的最小化法 ——极小化方法基础 ——正交搜索方向 ——QR和长度最小值法产生了同样的结果 简单提一下关于调整搜索方向