线性方程组·迭代方法与预处理 第四讲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
41 投影方法 什么是投影方法 在 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