计算方法线性方程组的迭代解法基本概念ch06ar

1、1第六章线性方程组的迭代解法计算方法 迭代法基本概念迭代法基本概念2本章内容本章内容n 迭代算法基本概念迭代算法基本概念n 矩阵分裂迭代算法矩阵分裂迭代算法n 共轭梯度算法共轭梯度算法3本讲内容本讲内容l 迭代算法的构造迭代算法的构造l 收敛性与收敛速度分析收敛性与收敛速度分析n 矩阵分裂迭代算法矩阵分裂迭代算法4线性方程组迭代解法线性方程组迭代解法l 运算量大，不适合大规模的线性方程组求解运算量大，不适合大规模的线性方程组求解l 无法充分利用系数矩阵的稀疏性无法充分利用系数矩阵的稀疏性q 直接法的缺点：直接法的缺点：从一个初始向量出发，按照一定的迭代格式，构造出一个趋从一个初始向量出发，按照

2、一定的迭代格式，构造出一个趋向于真解的无穷序列向于真解的无穷序列l 只需存储系数矩阵中的非零元素只需存储系数矩阵中的非零元素l 运算量不超过运算量不超过 O(kn2)，其中，其中 k 为迭代步数为迭代步数迭代法迭代法迭代法是目前求解大规模线性方程组的主要方法迭代法是目前求解大规模线性方程组的主要方法5矩阵分裂迭代法矩阵分裂迭代法矩阵分裂迭代法基本思想矩阵分裂迭代法基本思想Ax = b(1)( )kkxBxf k = 0, 1, 2, 给定一个初始向量给定一个初始向量 x(0)，可得，可得 迭代格式迭代格式其中其中 B = M-1N 称为称为迭代矩阵迭代矩阵 11xM NxM bA = M -

3、NMx = Nx + bM 非奇异非奇异A 的一个的一个矩阵分裂矩阵分裂6矩阵分裂迭代法矩阵分裂迭代法k = 0, 1, 2, 定义定义：若若 存在，则称该迭代法存在，则称该迭代法收敛收敛，否则称为，否则称为发散发散(1)( )kkxBxf ( )limkkx性质性质：若若 ，则，则 x* 为原方程组为原方程组 Ax = b 的解的解( )limkkxx 7向量序列的极限向量序列的极限定义定义：设向量序列设向量序列 ， ，若，若存在向量存在向量 ，使得，使得 ( )0kkx ( )( )( )( )12,Tkkkknxxxx 12,Tnxxxx ( )limkiikxx i = 1, 2, ,

4、 n则称向量序列则称向量序列 收敛到收敛到 x，记作，记作 ( )0kkx ( )limkkxx l 相类似地，可以定义矩阵序列的极限与收敛相类似地，可以定义矩阵序列的极限与收敛limkkAA 8向量序列的极限向量序列的极限定理定理：( )limkkxx ( )lim0kkxx定理定理：limkkAA lim0kkAA 定理定理：limkkAA lim0, RnkkA xx 证明：自学证明：自学(其中其中 | | 为任一算子范数为任一算子范数)9向量序列的极限向量序列的极限定理定理：lim0kkB ( )1B 证明：证明：自学自学定理定理：1( )limkkkBB 证明：证明：自学自学(其中其

5、中 | | 为任一矩阵范数为任一矩阵范数)10收敛性分析收敛性分析(1)( )kkxBxf 定理定理：对任意初始向量对任意初始向量 x(0)，上述迭代格式收敛的充要条件是，上述迭代格式收敛的充要条件是( )1B 证明：证明：自学自学定理定理：若存在算子范数若存在算子范数 | |，使得，使得 |B| 1，对任意的初始向量，对任意的初始向量 x(0)，上述迭代格式收敛。，上述迭代格式收敛。例例：考虑迭代法考虑迭代法 x(k+1) = Bx(k) + f 的收敛性，其中的收敛性，其中0.900.30.8B 11收敛性分析收敛性分析(1)( )kkxBxf B = M-1N定理定理：若存在算子范数若存在算子范数 | |，使得，使得 |B| = q 1，则，则证明：证明：自学自学( )(0)kkxxqxx 迭代法收敛迭代法收敛 ( )( )(1)1kkkqxxxxq ( )(1)(0)1kkqxxxxq 12收敛速度收敛速度第第 k 步的误差：步的误差：( )( )kkxx (0)kB ( )(0)kkB 平均每次迭代后的误差压缩率约为：平均每次迭代后的误差压缩率约为：1kkBl 若要求若要求 k 步迭代后上述误差比值不超过步迭代后上述误差比值不超过 ，则，则kB 11kkkB 11lnlnkkBk 1lnlnkkkB 13收敛速度收敛速度定义定义：迭代格式迭代格式 x(