第四章解线性方程组的迭代法.doc

解线性方程组的迭代法 对于阶数不高的方程组，直接法非常有效，对于阶数高，而系数矩阵稀疏的线性方程组却存在着困难，在这类矩阵中，非零元素较少，若用直接法求解，就要存贮大量零元素。为减少运算量、节约内存，使用迭代法更有利。本章介绍迭代法的初步内容。 §1 雅克比法、赛得尔法、超松驰法 1．雅克比（Jacobi）迭代法 设有n阶方程组 （4.1） 若系数矩阵非奇异，且 (i = 1, 2,…, n)，将方程组（4.1）改写成 然后写成迭代格式 （4.2） （4.2）式也可以简单地写为 （4.3） 对（4.2）或（4.3）给定一组初值后，经反复迭代可得到一向量序列，如果X (k)收敛于，则就是方程组（4.1）的解。这一方法称为雅克比（Jacobi）迭代法或简单迭代法，（4.2）或（4.3）称为Jacobi迭代格式。 下面介绍迭代格式的矩阵表示： 设D = diag (a11, a22, …, ann)，将方程组AX = b中的系数矩阵表示成三个特殊矩阵的代数和矩阵： A = D –L-U 其中 由于 ，D为可逆对角阵，L、U分别为严格上、下三角阵，于是 利用D可逆，得到等价方程组 则迭代格式的向量表示为 ， 称为雅克比迭代矩阵。 2．高斯――赛得尔（Gauss-Seidel）迭代法 显然，如果迭代收敛，应该比更接近于原方程的解（i = 1, 2,…, n），因此在迭代过程中及时地以代替（i = 1, 2,…, n-1），可望收到更好的效果。这样（4.2）式可写成： （4.5） （4.5）式可简写成 （i = 1, 2,…, n） 此为G－S迭代格式。 G－S迭代格式的矩阵表示： （4.6） ， 称为高斯-赛德尔迭代矩阵。 关于上述迭代法的误差控制，可按类似于第二章非线性方程求根的迭代法处理，设?为允许的绝对误差限，可以检验 是否成立，以决定计算是否终止，进一步的讨论稍后进行。 实际计算时，如果线性方程组的阶数不高，建立迭代格式也可以不从矩阵形式出发，以避免求逆矩阵的计算。 3．超松驰法 使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。 松驰法是一种线性加速方法。这种方法将前一步的结果与高斯――赛得尔方法的迭代值适当进行线性组合，以构成一个收敛速度较快的近似解序列。改进后的迭代方案是： 迭代 加速 所以 （4.7） 这种加速法就是松驰法。其中系数称松驰因子。可以证明，要保证迭代格式（4.7）收敛必须要求 当 = 1时，即为高斯――赛得尔迭代法，为使收敛速度加快，通常取，即为超松驰法。 松驰因子的选取对迭代格式（4.7）的收敛速度影响极大。实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子。 §2 迭代法的收敛条件 由§1中迭代格式的矩阵形式知，方程组AX = b的雅克比迭代法、高斯――赛得尔迭代法和松驰法的矩阵形式都可以写成下式： （4.8） 当然，不同的迭代法其迭代矩阵B和F的元素是不同的。所以我们讨论迭代格式（4.8）的收敛性，就具有普遍意义。 下面，我们不加证明地给出迭代格式（4.8）收敛的充分必要条件。 定理1：对任意初始向量X(0)及常向量F，迭代格式（4.8）收敛的充分必要条件是迭代矩阵B的谱半径?(B) 1。 这一结论在理论上是颇为重要的，但实际用起来不甚方便，为此我们着重研究更为实用的判别迭代格式收敛的充分条件。 考虑迭代向量序列{X(k)}的收敛问题： 若 于是 收敛的意思是： 依范数收敛是 当k??，从而得以下定理： 定理2：若迭代矩阵Ｂ的某种范数则（4.8）确定的迭代法对任意初值X(0)均收敛于方程组X = BX + F的唯一解x*。 下面给出直接计算时的收敛性定理。为给出这个定理，先介绍对角占优的概念。 定义1：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素的绝对值，即 则称矩阵A按行严格对角占优，类似地，也有按列严格对角占优。 定理3：若线性方程组AX = b的系数矩阵A按行严格对角占优，则雅克比迭代法和高斯――赛得尔迭代法对任意给定初值均收敛。 证明：记 为第k次近似值的误差， （1）由雅克比迭代法 记 则有 上式对 i = 1, 2,…, n成立