Krylov子空间方法 Krylov子空间方法的一般流程： (1)令m=1 (2)定义Krylov子空间Km(A,o); (3)在仿射控间xo)+Km中找出原问题的近似解(b-A立上C): (④)如果这个近似解满足精度要求，则迭代结束 否则令m←m+1,返回第(2)步. http://math.ecmu.edu.cn/-jypan 19/180
Krylov 子空间方法 Krylov 子空间方法的一般流程: (1) 令 m = 1 (2) 定义 Krylov 子空间 Km(A, r0); (3) 在 仿射空间 x (0) + Km 中找出原问题的近似解 (b − A˜x ⊥ L); (4) 如果这个近似解满足精度要求, 则迭代结束; 否则令 m ← m + 1, 返回第 (2) 步. http://math.ecnu.edu.cn/~jypan 19/180
Krylov子空间方法的基本框架 1: 选取初始向量xO) 2: 计算0=b-Ao),边=m/川ol2 3: 寻找近似解：)∈o)+K1 4:fa)满足精度要求then 5: 终止迭代 6:end if 7:for m=2 to n do 8: 调用Arnoldi过程计算向量m 9: 寻找近似解：m)∈xo)+Km (b-Axm⊥C) 10: ifm满足精度要求then 11: 终止迭代 12: end if 13:end for http://math.ecnu.edu.cn/-jypan 20/180
Krylov 子空间方法的基本框架 1: 选取初始向量 x (0) 2: 计算 r0 = b − Ax(0) , v1 = r0/∥r0∥2 3: 寻找近似解: x (1) ∈ x (0) + K1 4: if x (1) 满足精度要求 then 5: 终止迭代 6: end if 7: for m = 2 to n do 8: 调用 Arnoldi 过程计算向量 vm 9: 寻找近似解: x (m) ∈ x (0) + Km (b − Ax(m) ⊥ L) 10: if x (m) 满足精度要求 then 11: 终止迭代 12: end if 13: end for http://math.ecnu.edu.cn/~jypan 20/180
4-831 非对称线性方程组 4.3非对称线性方程组 4.3.1完全正交方法(F0M) C=K 4.3.2广义极小残量法(GMRES) →C=AK 4.3.3 GMRES实施细节 4.3.4带重启的GMRES https://math.ecnu.edu.cn/-jypan/Teaching/IMP
43 非对称线性方程组 4.3 非对称线性方程组 4.3.1 完全正交方法 (FOM) → L = K 4.3.2 广义极小残量法 (GMRES) → L = AK 4.3.3 GMRES 实施细节 4.3.4 带重启的 GMRES https://math.ecnu.edu.cn/~jypan/Teaching/IMP
4-3-1 完全正交方法(FOM) 取Cm=Km,得到的方法为完全正交方法(Full Orthogonalization Method) find )Km such that b-AiLm 设 =20)+Vmiy 其中∈Rm.由正交性条件b-A元⊥Km可知 0=Vin(6-Ai)=Vi(6-Az(0)-A Vmi) =Vinn-VinA Vmi =VI(Bu)-VIA Vmi=Be1-Hmi 如果Hm非奇异，则立=Hme1.所以 )+B VmHm e1. http://math.ecnu.edu.cn/-jypan 22/180
431 完全正交方法 (FOM) 取 Lm = Km, 得到的方法为完全正交方法 (Full Orthogonalization Method) find ˜x ∈ x (0) + Km such that b − A˜x ⊥ Km 设 ˜x = x (0) + Vm˜y , 其中 ˜y ∈ R m. 由正交性条件 b − A˜x ⊥ Km 可知 0 = V ⊺ m(b − A˜x) = V ⊺ m(b − Ax(0) − AVm˜y) = V ⊺ mr0 − V ⊺ mAVm˜y = V ⊺ m(βv1) − V ⊺ mAVm˜y = βe1 − Hm˜y 如果 Hm 非奇异, 则 ˜y = H−1 m e1. 所以 ˜x = x (0) + βVmH −1 m e1. http://math.ecnu.edu.cn/~jypan 22/180
算法2完全正交方法(FOM) 1:给定初值xo),计算%=b-Axo)和B=‖rol2 2:计算)=o/3 3:forj=1,2,.,m-1do %开始迭代 4: 西=A 5: fori=1,2,..,jdo%Arnoldi过程 6: h时=（四，），四5=四-h 7: end for 8: h5+1j=四ll2 9: ifh+ij=0,then set m=jand break,end if%Arnoldi过程提前终止 10: y5+1=0/h+1j 11:end for 12:求解线性方程组Hm立=Be1 13:计算近似解元=zo+Vm http://math.ecmu.edu.cn/-jypan 23/180
算法 2 完全正交方法 (FOM) 1: 给定初值 x (0) , 计算 r0 = b − Ax(0) 和 β = ∥r0∥2 2: 计算 v1 = r0/β 3: for j = 1, 2, . . . , m − 1 do % 开始迭代 4: wj = Avj 5: for i = 1, 2, . . . , j do % Arnoldi 过程 6: hij = (wj , vi), wj = wj − hijvi 7: end for 8: hj+1,j = ∥wj∥2 9: if hj+1,j = 0, then set m = j and break, end if % Arnoldi 过程提前终止 10: vj+1 = wj/hj+1,j 11: end for 12: 求解线性方程组 Hm˜y = βe1 13: 计算近似解 ˜x = x (0) + Vm˜y http://math.ecnu.edu.cn/~jypan 23/180