4-2-1 Krylov子空间 设A∈Rnxn,T∈R”,我们称 Cm(A,r）≌span{r,Ar,.,Am-1r}CR” 是由A和r生成的Krylov子空间，通常简记为Km,或心. NOTA CCCP 1g63 基本性质 dim(Km)≤m Krylov子空间是嵌套的，即：K1CK2C·CKmC OKm(4,)={女=(A)r:p为次数不超过m-1的多项式 http://math.ecmu.edu.cn/-jypan 10/180
421 Krylov 子空间 设 A ∈ R n×n , r ∈ R n , 我们称 Km(A, r) ≜ span{r, Ar, . . . , A m−1 r} ⊆ R n 是由 A 和 r 生成的 Krylov 子空间, 通常简记为 Km, 或 K. 基本性质 dim(Km) ≤ m Krylov 子空间是嵌套的, 即: K1 ⊆ K2 ⊆ · · · ⊆ Km ⊆ · · · Km(A, r) = n x = p(A)r : p 为次数不超过 m − 1 的多项式o http://math.ecnu.edu.cn/~jypan 10/180
Krylov子空间方法 以Krylov子空间为搜索空间的迭代法就是Krylov子空间方法 http://math.ecmu.edu.cn/-jypan 11/180
Krylov 子空间方法 以 Krylov 子空间为搜索空间的迭代法就是 Krylov 子空间方法 约束空间 L 的选取 目前被广泛采用的取法有: L = K : 如 FOM, CG, SYMMLQ → 正交投影法 L = AK : 如 MINRES, GMRES L = K(A ⊺ , r) : 如 BiCG 不同的 L 导出不同的 Krylov 子空间方法 http://math.ecnu.edu.cn/~jypan 11/180
Krylov子空间方法 以Krylov子空间为搜索空间的迭代法就是Krylov子空间方法 约束空间C的选取 目前被广泛采用的取法有： OC=K:如FOM,CG,SYMMLQ → 正交投影法 OC=AK:如MINRES,GMRES OC=K(AT,r):如BiCG 不同的C导出不同的Krylov子空间方法 http://math.ecmu.edu.cn/-jypan 11/180
Krylov 子空间方法 以 Krylov 子空间为搜索空间的迭代法就是 Krylov 子空间方法 约束空间 L 的选取 目前被广泛采用的取法有: L = K : 如 FOM, CG, SYMMLQ → 正交投影法 L = AK : 如 MINRES, GMRES L = K(A ⊺ , r) : 如 BiCG 不同的 L 导出不同的 Krylov 子空间方法 http://math.ecnu.edu.cn/~jypan 11/180
4-2-2 Arnoldi过程 构造Km的一组标准正交基→Arnoldi过程 算法1基于MGS(Modified Gram-Schmidt)的Arnoldi过程 1:计算=/川l2 2:forj=1,2,..,m-1do 3: 四=A巧 4: for i=1,2,...,j do 5: h=(四防，) 6: 5=5-h时吃 7: end for 8: h+1=l四l2 9: if hj1j=0 then break,end if 10: y5+1=0/h+1 11:end for http://math.ecmu.edu.cn/-jypan 12/180
422 Arnoldi 过程 构造 Km 的一组 标准正交基 → Arnoldi 过程 算法 1 基于 MGS (Modified Gram-Schmidt) 的 Arnoldi 过程 1: 计算 v1 = r/∥r∥2 2: for j = 1, 2, . . . , m − 1 do 3: wj = Avj 4: for i = 1, 2, . . . , j do 5: hij = (wj , vi) 6: wj = wj − hijvi 7: end for 8: hj+1,j = ∥wj∥2 9: if hj+1,j = 0 then break, end if 10: vj+1 = wj/hj+1,j 11: end for http://math.ecnu.edu.cn/~jypan 12/180
注记 0 如果计算到第k(k<m)步时有+1，k=0,则方法会提前终止 此时A必定可以由1,2，，线性表出（不考虑舍入误差） O算法中的向量称为Arnoldi向量 需要指出的是，在算法中我们是用A乘以v,然后与之前的Arnoldi向量正交化， 而不是用A.(事实上，它们是等价的) 引理如果Arnoldi过程不提前终止（即k+1,k≠0，k=1,2,,m-1),则 y∈(A,T),j=1,2,,m. (板书) 秦http:/aath.ecmm.adt,cn/-j打pan 13/180
注记 如果计算到第 k (k < m) 步时有 hk+1,k = 0, 则方法会 提前终止. 此时 Avk 必定可以由 v1, v2, . . . , vk 线性表出 (不考虑舍入误差) 算法中的向量 vi 称为 Arnoldi 向量. 需要指出的是, 在算法中我们是用 A 乘以 vj , 然后与之前的 Arnoldi 向量正交化, 而不是用 Aj r. (事实上, 它们是等价的) 引理 如果 Arnoldi 过程不提前终止 (即 hk+1,k ̸= 0, k = 1, 2, . . . , m − 1), 则 vj ∈ Kj(A, r), j = 1, 2, . . . , m. (板书) http://math.ecnu.edu.cn/~jypan 13/180