麻省理工学院：《数值模拟导论》第七讲 Krylov子空间矩阵解法

数值模拟导论-第七讲 Kyov子空间矩阵解法 雅克比怀特 感谢 Deepak ramaswamy, Michal Rewienski, Karen very and Jacob White

数值模拟导论 -第七讲 Krylov子空间矩阵解法 雅克比·怀特 感谢Deepak Ramaswamy, Michal Rewienski,Karen Veroy and Jacob White

概要 回顾GCR 最小残向量解法 Krylov子空间 与多项式关系 回顾特征值和范数 诱导范数 谱半径定理 收敛速度的评估 Chebychev多项式 预处理 对角预处理 一近似LU预处理

·回顾GCR －最小残向量解法 －Krylov 子空间 －与多项式关系 ·回顾特征值和范数 －诱导范数 －谱半径定理 ·收敛速度的评估 －Chebychev多项式 ·预处理 －对角预处理 －近似LU预处理 概要

GCR算法 r0=b-Axo for j=0 to k-1 P;= 残留值便是下一次的搜索方向 for i=0 to j-1 p←P-(M)()正交搜索方向 (4)( 标准化 x=x+(r)() P更新结果 =r-(2)(),更新残向量 SMA-HPC C2003 MIT

GCR算法 SMA-HPC ©2003 MIT { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G { } 0 1 , , − ⋅⋅⋅ w wk G G for j＝0 to k－1 for i＝0 to j-1 正交搜索方向 标准化 更新结果 更新残向量 0 0 r b Ax = − ( ) ( ) T j j j ii p ← − p Mp Mp p ( )( ) 1 j j T j j p p Mp Mp ← ( ) ( ) 1 T j jj j j x x r Mp p + = + ( ) ( ) 1 T j jj j j r r r Mp Mp + = − j j p = r 残留值便是下一次的搜索方向

GCR算法 标准化 图示运算步 1)正交化Ms 2)解x计算r的最小值 k+1 M SMA-HPC C2003 MIT

GCR算法 SMA-HPC ©2003 MIT 标准化 图示运算步 1）正交化 2）解 计算r的最小值 i Mr s ′ k x

GCR算法 开始的几步 第一步搜索方向=b=Mb2=b,R=w 残向量最小值解法x-() ·第二步搜索方向 PI M(-A) SMA-HPC C2003 MIT

·第一步搜索方向 GCR算法 SMA-HPC ©2003 MIT 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G k k r = b − Mx 开始的几步 0 0 r b Mx b = − = 0 0 0 r p Mr = (( ) ) 1 0 0 0 T x r Mp p = ( ) 1 1.0 0 1 1 1.0 0 r p p M r p β β − = − ， ·残向量最小值解法 ·第二步搜索方向

GCR算法 开始的几步(续) 残向量最小值解法=2+()1p 第三步搜索方向2=b-M42=2-72b-3Mf2 B10P0-B21P p2 M(-BoPo-BP SMA-HPC C2003 MIT

GCR算法 SMA-HPC ©2003 MIT 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G k k r = b − Mx 开始的几步（续） ·第三步搜索方向 ·残向量最小值解法 (( ) ) 21 1 1 1 T x x r Mp p = + 2 2 0 0 20 2,1 2,0 r b Mx r Mr M r =− = − − γ γ ( ) 1 2,0 0 2,1 1 2 1 2,0 0 2,1 1 rpp p M rpp β β β β − − = − −

GCR算法 GCR的第k步 =-2(M)()P正交和标准化搜索方向 Pk Pk 第k步运算的最佳步长 x=x +ak pk a, Mp 更新结果和残余值 SMA-HPC C2003 MIT

GCR算法 SMA-HPC ©2003 MIT 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G k k r = b − Mx GCR的第k步 ( ) ( ) 1 0 k T k k k j j j p r Mr Mp p − =  = −∑ k k k p p Mp =   ( ) ( ) T k k k α = r Mp k k 1 k k xx p α + = + k k 1 k k r r Mp α + = − 正交和标准化搜索方向 第k步运算的最佳步长 更新结果和残余值

GCR算法 多项式梗概 如果在GCR中对所有j≤k的有a1≠0,那么 1)向量空间(pP…}=向量空间(,Mb…M 2)x“=5(M),是k次多项式,最小值为 3)r=b-M2=-M(M0)2=(=M45(MO)=p(0)r 这里(M)是(K+1)次多项式,如果(0)=1那 么他的最小值为 SMA-HPC C2003 MIT

如果在GCR中对所有 的有 ，那么 1） 2） 是k次多项式，最小值为 3） j k ≤ GCR算法 SMA-HPC ©2003 MIT 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G 11 2 2 ... N N x M xM x M b + ++ = GG G k k r = b − Mx 多项式梗概 0 α j ≠ { } { } 0 0 0 1 , ,..., , ,..., k k 向量空间 向量空间 p p p r Mr Mr = ( ) 1 0 , k k x Mr ξ + = k ξ 2 1 2 k r + ( ) ( ( )) ( ) 1 10 0 0 0 1 k k k kk r b Mx r M M r I M M r M r ξ ξ + + = − = − = − ≡℘ + 这里 是（k＋1）次多项式，如果 那 么他的最小值为 ( ) 0 k 1 M r ℘ + ℘k+1 (0 1 ) = 2 1 2 k r +

Kyov方法 残向量最小值 多项式梗概 如果x属于向量空间{MF…Mb最小化“: 1)x=5(M0y,5是k次多项式,最小化“ 2)=b-M=-M5(M0)2=(1-M51(MO)=9(M) 这里(M)是(k+1)次多项式,如果(0)=1 那么他可以最小化 这里多项式作为解题工具,只有一个作用。那就是 最小化残向量。 SMA-HPC C2003 MIT

如果 属于向量空间 最小化 ： 1） 是 k次多项式，最小化 2 ） 这里 是（ k ＋ 1）次多项式，如果 那么他可以最小化 这里多项式作为解题工具，只有一个作用。那就是 最小化残向量。 Krylov方法 SMA-HPC ©2003 MIT 残向量最小值 多项式梗概 k 1 x + { } 0 0 , ,..., k r Mr Mr 2 1 2 k r + ( ) 1 0 , k k x Mr ξ + = ( ) ( ) ( ) ( ) 1 10 0 0 0 1 k k k kk r b Mx r M M r I M M r M r ξ ξ + + = − = − = − ≡℘ + ( ) 0 k 1 M r ℘ + ℘ k +1 (0 1 ) = k ξ 2 1 2 k r + 2 1 2 k r +

Krylov方法 “与外界物热交换 的例子 绝缘棒和矩阵 吸热 Incoming Heat T(0)● T(1) Near End Far End Temperature Discretization Temperature 近端温度 远端温度 离散化 Nodal Equation Form 节点平衡方程 SMA-HPC C2003 MIT

吸热 Krylov 方法 SMA-HPC ©2003 MIT “与外界物热交换 的例子” 绝缘棒和矩阵 近端温度 远端温度 离散化 节点平衡方程