多网格方法基本思路
Author : zbzhen, Last modification time : Tue Aug 15 17:59:06 2023
这里只给出定性分析，不给出复杂的理论分析
假设
U h = K h − 1 F h , U 2 h = K 2 h − 1 F 2 h U_h=K_h^{-1}F_h,\quad U_{2h} =K_{2h}^{-1}F_{2h} U h = K h − 1 F h , U 2 h = K 2 h − 1 F 2 h
其中h h h
细网格的信息更多，因此可以通过某个限制算子R R R F 2 h = R F h F_{2h}=RF_{h} F 2 h = R F h
U 2 h = K 2 h − 1 F 2 h = K 2 h − 1 R F h U_{2h} =K_{2h}^{-1}F_{2h}=K_{2h}^{-1}RF_{h} U 2 h = K 2 h − 1 F 2 h = K 2 h − 1 R F h
此外，可以通过插值算子I I I U 2 h U_{2h} U 2 h I U 2 h I U_{2h} I U 2 h U h U_h U h I U 2 h ≈ U h I U_{2h}\approx U_h I U 2 h ≈ U h
K h − 1 F h = U h ≈ I U 2 h = I K 2 h − 1 R F h K_h^{-1}F_h = U_h \approx I U_{2h} = I K_{2h}^{-1}RF_{h} K h − 1 F h = U h ≈ I U 2 h = I K 2 h − 1 R F h
从而可以认为
K h − 1 ≈ I K 2 h − 1 R K_h^{-1} \approx I K_{2h}^{-1}R K h − 1 ≈ I K 2 h − 1 R
有限维空间中，算子和矩阵可以认为是同一回事，这里不妨直接把它们直接混用, 上面出现的算子，也可以都认为是矩阵
求解某线性方程组，若
U = K − 1 F U=K^{-1}F U = K − 1 F
则有
U = U ~ + K − 1 ( F − K U ~ ) U = \widetilde{U} + K^{-1}(F-K\widetilde{U}) U = U + K − 1 ( F − K U )
根据前面的分析，K − 1 K^{-1} K − 1
下面给出两网格算法(two-mg)
U = two-mg ( U 0 , K h , K 2 h , F h ) U = \operatorname{two-mg}(U_0, K_h, K_{2h}, F_h) U = two-mg ( U 0 , K h , K 2 h , F h )
输入: U 0 U_0 U 0 K h , K 2 h , F h K_h, K_{2h}, F_h K h , K 2 h , F h 输出: U U U U ≈ K h − 1 F h U\approx K_h^{-1}F_h U ≈ K h − 1 F h
初值为U 0 U_0 U 0 K h U h = F h K_h U_h = F_h K h U h = F h U ~ \widetilde{U} U
U ^ = U ~ + I K 2 h − 1 R ( F h − K h U ~ ) \widehat{U} = \widetilde{U} + I K_{2h}^{-1}R(F_h-K_h\widetilde{U}) U = U + I K 2 h − 1 R ( F h − K h U ) 初值为U ^ \widehat{U} U K h U h = F h K_h U_h = F_h K h U h = F h U U U
通常情况下，这里的经典迭代法采用的是松弛雅克比迭代，迭代公式为
U ← U + w D − 1 ( F − K U ) U \leftarrow U + wD^{-1}(F-KU) U ← U + w D − 1 ( F − K U )
其中D = diag ( K ) D=\operatorname{diag}(K) D = diag ( K ) w = 0.6 w=0.6 w = 0.6
下面给出两网格算法(two-mg)具体形式
U = two-mg ( U 0 , K h , K 2 h , F h , D ) U = \operatorname{two-mg}(U_0, K_h, K_{2h}, F_h,D) U = two-mg ( U 0 , K h , K 2 h , F h , D )
输入: U 0 U_0 U 0 K h , K 2 h , F h , D K_h, K_{2h}, F_h, D K h , K 2 h , F h , D 输出: U U U U ≈ K h − 1 F h U\approx K_h^{-1}F_h U ≈ K h − 1 F h
U ~ = U 0 + w D − 1 ( F h − K h U 0 ) \widetilde{U} =U_0 + wD^{-1}(F_h-K_hU_0) U = U 0 + w D − 1 ( F h − K h U 0 ) U ^ = U ~ + I K 2 h − 1 R ( F h − K h U ~ ) \widehat{U} = \widetilde{U} + I K_{2h}^{-1}R(F_h-K_h\widetilde{U}) U = U + I K 2 h − 1 R ( F h − K h U ) U = U ^ + w D − 1 ( F h − K h U ^ ) U =\widehat{U} + wD^{-1}(F_h-K_h\widehat{U}) U = U + w D − 1 ( F h − K h U )
和经典迭代算法相比，两网格算法(two-mg)明显的特点是加入了第二步的计算, 减少计算量的地方是近似求逆，即I K 2 h − 1 R I K_{2h}^{-1}R I K 2 h − 1 R K h − 1 K_h^{-1} K h − 1
如果网格步长h h h K 2 h − 1 K_{2h}^{-1} K 2 h − 1
function u = V_Cycle ( u, f, h)
eps = zeros ( size ( rhs) ) ;
if smallest_grid_size_is_achieved
eps = smoothing ( eps, rhs, 2 * h) ;
else
u = smoothing ( u, f, h) ;
rhs = Rh ( f - Kh * u) ;
eps = V_Cycle ( eps, rhs, 2 * h) ;
u = u + Ih ( eps) ;
u = smoothing ( u, f, h) ;
end
end