-254.第七讲Krylov子空间选代法算法7.6.GMRES(k)：带重启的GMRES方法1:设定重启步数k（<n)2:选取初值r(0),停机标准e>0,以及最大送代步数IterMax3: ro = b- Ar(0), β= Iroll24:ifβ/6l2<ethen停止计算，输出近似解=z(0)5:6: end if7: for iter=l to ceil(IterMax/k) do%外循环8:U1= ro/β9:=βBei10:for j = l to k do调用GMRES循环11:end for12:13:m=jg(m) = H(1 : m,1 : m)s(1 : m)14:r(m) = r(0) + Vmy(m)15:if relres< then16:17:breakend if18:(0)=2(m)%重启GMRES19:ro = b - Ar(0), β= roll220:21: end for22: if relres<e then输出近似解r(m）及相关信息23:24:else25:输出算法失败信息26: end if带重启的GMRES方法需要注意的问题：（1）如何选取合适的重启步数k?一般只能依靠经验来选取；(2）不带重启的GMRES方法能保证算法的收敛性，但带重启的GMRES方法却无法保证，有时可能出现停滞现象(stagnation)
· 254 · 第七讲 Krylov 子空间迭代法 算法 7.6. GMRES(k): 带重启的 GMRES 方法 1: 设定重启步数 k (≪ n) 2: 选取初值 x (0) , 停机标准 ε > 0, 以及最大迭代步数 IterMax 3: r0 = b − Ax(0) , β = ∥r0∥2 4: if β/∥b∥2 < ε then 5: 停止计算, 输出近似解 x = x (0) 6: end if 7: for iter=1 to ceil(IterMax/k) do % 外循环 8: v1 = r0/β 9: ξ = βe1 10: for j = 1 to k do 11: 调用 GMRES 循环 12: end for 13: m = j 14: y (m) = H(1 : m, 1 : m)\ξ(1 : m) 15: x (m) = x (0) + Vmy (m) 16: if relres < ε then 17: break 18: end if 19: x (0) = x (m) % 重启 GMRES 20: r0 = b − Ax(0) , β = ∥r0∥2 21: end for 22: if relres < ε then 23: 输出近似解 x (m) 及相关信息 24: else 25: 输出算法失败信息 26: end if 带重启的 GMRES 方法需要注意的问题: (1) 如何选取合适的重启步数 k? 一般只能依靠经验来选取; (2) 不带重启的 GMRES 方法能保证算法的收敛性, 但带重启的 GMRES 方法却无法保证, 有时 可能出现停滞现象 (stagnation)
7.3共轭梯度法255.7.3共轭梯度法共轭梯度法（ConjugateGradient,CG）是当前求解对称正定线性方程组的首选方法.CG算法可以从优化角度得出，也可以从代数角度推导.我们这里就从代数角度来介绍CG算法7.3.1算法基本过程我们首先给出CG算法的一个性质，然后根据这个性质来推导CG算法，定理7.5设A对称正定，则(m) = arg(7.9)minr-ArEr(0)+Km的充要条件是r(m)Ea(0)+Km 且b-Ar(m)1Km.(7.10)(板书)证明.首先证明充分性.设 r(m)满足(7.10).记= z(m)-2(0),则EKm且ro-Ai1Km.由正交投影的性质可知，是最佳逼近问题ren l - A-1rllA的解,即= arg min Ila - A-1r()/A= arg min / - A-1(b - Ar(0)/AC= arg min II(r(0) + a) - llA.所以,(m)=2(0)+是最佳逼近问题min[T-TArEr(0)+Km的解，即结论(7.9)成立口必要性只需利用正交投影的性质即可，见作业7.3当A对称正定时,Arnoldi过程就转化为Lanczos过程,且AVm=Vm+1Tm+1,m= VmTm+βBmm+1emVTAVm = Tm,其中Tm=tridiag(βi,αi+1,βi+1)，见（7.3).由定理7.5可知，此时我们需要在r(0)+Km寻找最优近似解(m)满足b- Ar(m) 1 Km.(7.11)根据这个性质，我们就可以给出CG算法
7.3 共轭梯度法 · 255 · 7.3 共轭梯度法 共轭梯度法 (Conjugate Gradient, CG) 是当前求解对称正定线性方程组的首选方法. CG 算法 可以从优化角度得出, 也可以从代数角度推导. 我们这里就从代数角度来介绍 CG 算法. 7.3.1 算法基本过程 我们首先给出 CG 算法的一个性质, 然后根据这个性质来推导 CG 算法. 定理 7.5 设 A 对称正定, 则 x (m) = arg min x∈x(0)+Km ∥x − x∗∥A (7.9) 的充要条件是 x (m) ∈ x (0) + Km 且 b − Ax(m) ⊥ Km. (7.10) (板书) 证明. 首先证明充分性. 设 x (m) 满足 (7.10). 记 x˜ = x (m) − x (0) , 则 x˜ ∈ Km 且 r0 − Ax˜ ⊥ Km. 由正交投影的性质可知, x˜ 是最佳逼近问题 min x∈Km ∥x − A −1 r0∥A 的解, 即 x˜ = arg min x∈Km ∥x − A −1 r (0)∥A = arg min x∈Km ∥x − A −1 (b − Ax(0))∥A = arg min x∈Km ∥(x (0) + x) − x∗∥A. 所以, x (m) = x (0) + ˜x 是最佳逼近问题 min x∈x(0)+Km ∥x − x∗∥A 的解, 即结论 (7.9) 成立. 必要性只需利用正交投影的性质即可, 见作业 7.3. □ 当 A 对称正定时, Arnoldi 过程就转化为 Lanczos 过程, 且 AVm = Vm+1Tm+1,m = VmTm + βmvm+1e T m, V T mAVm = Tm, 其中 Tm = tridiag(βi , αi+1, βi+1), 见 (7.3). 由定理 7.5 可知, 此时我们需要在 x (0) + Km 寻找最优 近似解 x (m) , 满足 b − Ax(m) ⊥ Km. (7.11) 根据这个性质, 我们就可以给出 CG 算法