第三章.方程组的迭代解法.ppt

* 第三章 线性方程组的迭代解法(韩金舫) 首先看一个形成大型方程组的例子。考虑下面的Poisson方程 的离散逼近，其边界条件为： 取 进行网格剖分,用二阶导数,按逐行自左至右和自下而 上的自然次序离散华可得下列线性方程组 其中　　　　　　　　　　　是　　　　　　　　　的近似值。这是一 种特殊形状的稀疏矩阵。随着　　和　　的减少，所得到的方程组的阶 数将增大。 　　对于大型线形代数方程组，常用迭代解法。它是从某些初始向量出 发，用设计好的步骤逐次算出近似解向量　　，从而得到向量序 列 。 　 　　 一般　　　的计算公式是 　　 称之为多步迭代法．若　　　只与　　有关，且　　是线性的，即 　　　　　　　 其中 ，称为单步线性迭代法， 称为迭代距阵。若 和 都与k 无关，即 称为单步定常线性迭代法。本章主要讨论具有这种形式的各种迭代方法。 3.1 基本迭代方法 3.1.1 迭代公式的构造 设 ， ，A非奇异， 满足方程组 Ax=b。 （3.1.1） 如果能找到距阵 ，向量 ，使 可逆，而且方程组 x=Bx+f (3.1.2) 的唯一解就是方程组（3.1.1）的解，则可从（3.1.2）式构造一个定常的线 性迭代公式 （3.1.3） 给定初始向量 , 由(3.1.3)可以产生序列 ,若它有极限 , 显然 就是(3.1.1)和(3.1.2)的解。 定义 3.1 若对任意初始向量 ，迭代公式（5.1.3）产生的 序列 都有 则称迭代法（3.1.3）是收敛的。 从（3.1.1）出发，可以由不同的途径得到各种不同的等价方程组 （3.1.2），从而得到不同的迭代法（3.1.3）。例如，设A可以分解为 ，其中M非奇异，则由（3.1.1）可得 令 就可以得到（3.1.2）的形式。不同的分解方式 ，可的不同的 B 和 f , 下面给出对应不同分解方式的常用迭代 计算公式。 3.1.2 Jacobi 迭代法和 Gauss-Seidel迭代法 1. Jacobi 迭代法 记 ， 可以把 A 分解为 （3.1.4） 其中 现设D非奇异，即 。方程组（3.1.1）等价于 由此构造迭代公式： （3.1.5） 其中迭代距阵 和向量 为 （3.1.6） （3.1.7） 称（5.1.5）为解（5.1.1）的Jacobi 迭代法，简称 J 法。 用 J 法计算向量序列 ，要用两组单元存放向量 和 。 迭代法可以写成分量形式 （3.1.8） 2. Gauss-Seidel 迭代法 在J 法中，计算