文档介绍：数值模拟导论-第七讲
Krylov子空间矩阵解法
雅克比·怀特
感谢Deepak Ramaswamy, Michal
Rewienski,Karen Veroy and Jacob White
概要
·回顾GCR
-最小残向量解法
-Krylov 子空间
-与多项式关系
·回顾特征值和范数
-诱导范数
-谱半径定理
·收敛速度的评估
-Chebychev多项式
·预处理
-对角预处理
-近似LU预处理
G G
{}w0 ,⋅⋅⋅,wk−1
GCR算法
rbAx00=−
for j=0 to k-1
j
p j = r 残留值便是下一次的搜索方向
for i=0 to j-1
T
p j ←−pMpMppjjii( ) ()正交搜索方向
1
p ← p
jjT 标准化
()()Mpjj Mp
jjj+1 T 更新结果
xxrMpp=+( ) ( jj)
jjj+1 T 更新残向量
rrrMpMp=−( ) ( j ) j
SMA-HPC ©2003 MIT
GCR算法标准化
图示运算步
1)正交化 Mrsi′
2)解xk 计算r的最小值
SMA-HPC ©2003 MIT
k GGk G
rx11MxM= b+++=− Mx 2 2... xMbNN
GCR算法
开始的几步
0
00 r
第一步搜索方向 p =
· rbMxb= −=, 0 0
Mr
10T
·残向量最小值解法 xrMpp= (( ) 00)
rp1 −β
·第二步搜索方向 p = 0
1 1
M ()rp− 0
SMA-HPC ©2003 MIT
k GGk G
rx11MxM= b+++=− Mx 2 2... xMbNN
GCR算法
开始的几步(续)
·残向量最小值解法 21 1T
xx=+(( rMpp) 11)
第三步搜索方向 220020
· rbMxr=−= −γγ2,1 MrMr − 2,0
rpp1 −−ββ
p = 2,0 0 2,1 1
2 1
M ()rpp−−ββ2,0 0 2,1 1
SMA-HPC ©2003 MIT
k GGk G
rx11MxM= b+++=− Mx 2 2... xMbNN
GCR算法
GCR的第k步
k −1 T
kk
prk =−∑() MrMpp()jj 正交和标准化搜索方向
j=0
p k
pk =
Mp k
T
α= rMpk ()
kk( ) 第k步运算的最佳步长
kk+1
xx=+α kk p
kk+1 更新结果和残余值
rr=−α kk Mp
SMA-HPC ©2003 MIT
k GGk G
rx11MxM= b+++=− Mx 2 2... xMbNN
GCR算法
多项式梗概
如果在GCR中对所有jk≤的有α j ≠ 0 ,那么
00 k
1)向量空间{}p01,pp ,...,k = 向量空间{} rMrMr , ,...,
2
xMrk+10= ξ, ξ r k +1
2)是k () k k次多项式,最小值为 2
kk++1100 0 0
3) r=− b Mx = r − Mξξkkk( Mr) =( I − M( M)) r ≡℘+1 ( Mr)
0
这里℘k+1 ()M r 是(k+1)次多项式,如果℘k +1 (01)= 那
2
么他的最小值为 r k +1
2
SMA-HPC ©2003 MIT
Krylov方法残向量最小值
多项式梗概
k +1 2
如果x 属于向量空间rMr00, ,..., Mrk 最小化r k +1 :
{ } 2
2
xMrk+10= ξ, ξ r k +1
1)是k () k k次多项式,最小化 2
kk++1100 0 0
2) r=− b Mx = r − Mξξkkk( Mr) =() I − M( M) r ≡℘+1 ( Mr)
0
这里℘k +1 ()M r 是(k+1)次多项式,如果℘k +1 (01)=
2
那么他可以最小化 r k +1
2
这里多项式作为解题工具,只有一个作用。那就是
最小化残向量。
SMA-HPC ©2003 MIT
方法“与外界物热交换
Krylov 的例子”
绝缘棒和矩阵
吸热
近端温度远端温度
离散化