华东师范大学：《迭代方法与预处理》课程教学课件（迭代方法与预处理）第四讲 Krylov子空间方法

线性方程组·迭代方法与预处理 第四讲Krylov子空间方法 目录 4.1 投影方法 4.2 Krylov子空间与Arnoldi过程 4.3 非对称线性方程组 4.4对称线性方程 4.5 收敛性分析 4.6基于双正交化过程的迭代方法 4.7 免转置迭代方法 4.8 正规方程的迭代方法

线性方程组 • 迭代方法与预处理 第四讲 Krylov 子空间方法 4.1 投影方法 4.2 Krylov 子空间与 Arnoldi 过程 4.3 非对称线性方程组 4.4 对称线性方程 4.5 收敛性分析 4.6 基于双正交化过程的迭代方法 4.7 免转置迭代方法 4.8 正规方程的迭代方法 目录

子空间方法 子空间方法基本思想：降维 原问题： Ax=b←→min‖b-Axl IERn 降维：设K是R”的一个子空间，dim(K)=m《n. 将原问题转化（近似）为 minllo-Azll 或 minllz-.ll ZEK E把 优点：自由度大大减少，问题规模从n降为m 运算量主要集中在矩阵向量乘积，非常适合稀疏线性方程组 问题：怎么我合适的子空间？怎么计算最佳近似解？怎么加快收敛速度？ http://math.ecmu.edu.cn/-jypan 2/180

子空间方法 子空间方法基本思想: 降维 原问题: Ax = b ⇐⇒ min x∈Rn ∥b − Ax∥ 降维: 设 K 是 R n 的一个子空间, dim(K) = m ≪ n. 将原问题转化 (近似) 为: min x∈K ∥b − Ax∥ 或 min x∈K ∥x − x∗∥ 优点: 自由度大大减少, 问题规模从 n 降为 m 运算量主要集中在矩阵向量乘积, 非常适合稀疏线性方程组 问题: 怎么找合适的子空间? 怎么计算最佳近似解? 怎么加快收敛速度? http://math.ecnu.edu.cn/~jypan 2/180

4-11‖ 投影方法 什么是投影方法 在K中寻找x*在某种意义下的最佳近似 定解条件：设置m个约束→保证最佳近似存在唯一 在通常情况下，我们要求残量满足正交性条件： r=b-A元⊥C, (4.1) 其中云是我们所要寻找的近似解，C是另一个m维子空间. 吕正交性条件(4.l)称为Petrov-Galerkin条件.若C=K,则称为Galerkin条件 巴子空间C也称为约束空间，K通常称为搜索空间， 素http://math.ecam.edu.cm/-jp回 3/180

4­1 投影方法 什么是投影方法 在 K 中寻找 x∗ 在某种意义下的最佳近似 定解条件: 设置 m 个约束 → 保证最佳近似存在唯一 在通常情况下, 我们要求残量满足正交性条件: r = b − A˜x ⊥ L, (4.1) 其中 ˜x 是我们所要寻找的近似解, L 是另一个 m 维子空间.  正交性条件 (4.1) 称为 Petrov-Galerkin 条件. 若 L = K, 则称为 Galerkin 条件  子空间 L 也称为约束空间, K 通常称为搜索空间. http://math.ecnu.edu.cn/~jypan 3/180

子空间投影法的一般描述 因此，投影方法一般可以描述为 find i∈K such that b-Ar⊥C. (4.2) http://math.ecmu.edu.cn/-jypan 4/180

子空间投影法的一般描述 因此, 投影方法一般可以描述为 find ˜x ∈ K such that b − A˜x ⊥ L. (4.2) 如果给定初值 x (0) , 为了能够充分利用初值的相关信息, 我们改为在仿射空间 x (0) + K 中寻 找最佳近似, 即 find ˜x ∈ x (0) + K such that b − A˜x ⊥ L. (4.3) 事实上, 如果将 ˜x 写成: ˜x = x (0) + ˆx, 其中 ˆx ∈ K, 则 (4.52) 就是 find ˆx ∈ K such that r0 − Aˆx ⊥ L, (4.4) 其中 r0 = b − Ax (0) 是初始残量. 这与 (4.2) 的形式是一样的. http://math.ecnu.edu.cn/~jypan 4/180

子空间投影法的一般描述 因此，投影方法一般可以描述为 find i∈K such that b-Az⊥C. (4.2) 如果给定初值x0,为了能够充分利用初值的相关信息，我们改为在仿射空间x0)+K中寻 找最佳近似，即 find i)+such that b-ALC. (4.3) http://math.ecmu.edu.cn/-jypan 4/180

子空间投影法的一般描述 因此, 投影方法一般可以描述为 find ˜x ∈ K such that b − A˜x ⊥ L. (4.2) 如果给定初值 x (0) , 为了能够充分利用初值的相关信息, 我们改为在仿射空间 x (0) + K 中寻 找最佳近似, 即 find ˜x ∈ x (0) + K such that b − A˜x ⊥ L. (4.3) 事实上, 如果将 ˜x 写成: ˜x = x (0) + ˆx, 其中 ˆx ∈ K, 则 (4.52) 就是 find ˆx ∈ K such that r0 − Aˆx ⊥ L, (4.4) 其中 r0 = b − Ax (0) 是初始残量. 这与 (4.2) 的形式是一样的. http://math.ecnu.edu.cn/~jypan 4/180

子空间投影法的一般描述 因此，投影方法一般可以描述为 find∈K such that b-Az⊥C. (4.2) 如果给定初值x0),为了能够充分利用初值的相关信息，我们改为在仿射空间x0)+K中寻 找最佳近似，即 find∈xo+K such that b-Ar⊥C. (4.3) 事实上，如果将元写成：元=o+金其中金∈尤，则(4.52)就是 find∈K such that ro-Ar⊥C, (4.4) 其中m=b一Ao)是初始残量.这与(4.2)的形式是一样的. http://math.ecmu.edu.cn/-jypan 4/180

子空间投影法的一般描述 因此, 投影方法一般可以描述为 find ˜x ∈ K such that b − A˜x ⊥ L. (4.2) 如果给定初值 x (0) , 为了能够充分利用初值的相关信息, 我们改为在仿射空间 x (0) + K 中寻 找最佳近似, 即 find ˜x ∈ x (0) + K such that b − A˜x ⊥ L. (4.3) 事实上, 如果将 ˜x 写成: ˜x = x (0) + ˆx, 其中 ˆx ∈ K, 则 (4.52) 就是 find ˆx ∈ K such that r0 − Aˆx ⊥ L, (4.4) 其中 r0 = b − Ax(0) 是初始残量. 这与 (4.2) 的形式是一样的. http://math.ecnu.edu.cn/~jypan 4/180

子空间方法需要考虑的三个问题 O如何选择K和C? ⑦如何计算近似解？ 若不满足精度要求，如何寻找新的K和C? http://math.ecmu.edu.cn/-jypan 5/180

子空间方法需要考虑的三个问题  如何选择 K 和 L?  如何计算近似解 ˜x?  若 ˜x 不满足精度要求，如何寻找新的 K 和 L? http://math.ecnu.edu.cn/~jypan 5/180

近似解的计算 设V=[,2,.,m和W=,u,,m分别是K和C一组基 http://math.ecmu.edu.cn/-jypan 6/180

近似解的计算 设 V = [v1, v2, . . . , vm] 和 W = [w1, w2, . . . , wm] 分别是 K 和 L 一组基. 由于 ˜x ∈ x (0) + K, 即 ˜x − x (0) ∈ K, 因此存在向量 y = [y1, y2, . . . , ym] ⊺ ∈ R m 使得 ˜x = x (0) + Vy 根据正交性条件可得 r0 − AVy ⊥ wi , (i = 1, 2, . . . , m) =⇒ W ⊺AVy = W ⊺ r0 若 W⊺AV 非奇异, 则 y = (W⊺AV) −1W⊺ r0 =⇒ ˜x = x (0) + V(W ⊺AV) −1W ⊺ r0 在实际计算中, 矩阵 W⊺AV 通常可以直接形成, 而无需另外计算. http://math.ecnu.edu.cn/~jypan 6/180

近似解的计算 设V=[,2,,m】和W=[,u,,0m分别是K和C一组基 由于x∈xo)+K,即元-o)∈K,因此存在向量y=[1,2,,mT∈Rm使得 i=x0)+Vy http://math.ecnu.edu.cn/-jypan 6/180

近似解的计算 设 V = [v1, v2, . . . , vm] 和 W = [w1, w2, . . . , wm] 分别是 K 和 L 一组基. 由于 ˜x ∈ x (0) + K, 即 ˜x − x (0) ∈ K, 因此存在向量 y = [y1, y2, . . . , ym] ⊺ ∈ R m 使得 ˜x = x (0) + Vy 根据正交性条件可得 r0 − AVy ⊥ wi , (i = 1, 2, . . . , m) =⇒ W ⊺AVy = W ⊺ r0 若 W⊺AV 非奇异, 则 y = (W⊺AV) −1W⊺ r0 =⇒ ˜x = x (0) + V(W ⊺AV) −1W ⊺ r0 在实际计算中, 矩阵 W⊺AV 通常可以直接形成, 而无需另外计算. http://math.ecnu.edu.cn/~jypan 6/180

近似解的计算 设V=[,2,,vmJ和W=[1,2,,wm分别是K和C一组基 由于交∈o)+K,即元-o)∈K,因此存在向量y=[h,欢，，mT∈Rm使得 元=xo)+Vy 根据正交性条件可得 o-AVy⊥， (i=1,2,.,m) → WTAVy=WTm http://math.ecnu.edu.cn/-jypan 6/180

近似解的计算 设 V = [v1, v2, . . . , vm] 和 W = [w1, w2, . . . , wm] 分别是 K 和 L 一组基. 由于 ˜x ∈ x (0) + K, 即 ˜x − x (0) ∈ K, 因此存在向量 y = [y1, y2, . . . , ym] ⊺ ∈ R m 使得 ˜x = x (0) + Vy 根据正交性条件可得 r0 − AVy ⊥ wi , (i = 1, 2, . . . , m) =⇒ W ⊺AVy = W ⊺ r0 若 W⊺AV 非奇异, 则 y = (W⊺AV) −1W⊺ r0 =⇒ ˜x = x (0) + V(W ⊺AV) −1W ⊺ r0 在实际计算中, 矩阵 W⊺AV 通常可以直接形成, 而无需另外计算. http://math.ecnu.edu.cn/~jypan 6/180