线性方程组的迭代法

1、第六章 线性方程组的迭代法一、教学目标及基本要求通过对本节的学习，使学生掌握线性方程组的数值解法。二、教学内容及学时分配本节主要介绍线性方程组的数值解法，迭代公式的建立，迭代收敛性。三、教学重点难点1教学重点：迭代公式的建立、迭代收敛性。2. 教学难点：迭代收敛性。四、教学中应注意的问题多媒体课堂教学为主。适当提问，加深学生对概念的理解。6.2 解线性方程组的迭代法 重要性：解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的地位和作 用。如弹性力学、电路分析、热传导和振动、 以及社会科学及定量分析商业经济中的各种问 题。在实际问题中产生的线性方程组的类型有很多， 如按系数矩阵含零元素多

2、少分类， 有稠 密和稀疏 （零元素占 80%以上 ）线性方程组之分；如按阶数的高低分类，有高阶（阶数在 1000阶以上 ）中阶、 （5001000 阶 ） 和低阶 （500 阶以下 ）线性方程组之分；如按系数矩阵的形状和 性质分类， 有对称正定、 三对角、对角占优线性方程组之分。 因为数值解法必须考虑方法的 计算时间和空间效率以及算法的数值稳定性。 因此， 不同类型的线性方程组， 其数值解法也 不相同。但是，基本的方法可以归结为两大类，即直接法和迭代法。分类：线性方程组的解法可分为直接法和迭代法两种方法。（a） 直接法：对于给定的方程组，在 没有舍入误差的假设下，能在预定的运算次数内求 得精确

3、解 。最基本的直接法是 Gauss 消去法，重要的直接法全都受到 Gauss消去法的启发。 计算代价高。 但实际计算中由于舍入误差的存在和影响， 这种方法也只能求得线性方程组的 近似解，如何避免舍入误差的增长是设计直接法时必须考虑的问题。（b） 迭代法：基于一定的递推格式，产生逼近方程组精确解的近似序列。 收敛性 是其为 迭代法的前提， 此外， 存在收敛速度与误差估计问题。 迭代法要求方程组系数矩阵具有某种 特殊形式（如对角占优阵） ，是解高阶稀疏矩阵方程组的重要方法。6.1 迭代公式的建立 迭代法的基本思想是用逐次逼近的方法求线性方程组的解。 设有方程组 Ax b （ 1）将其转化为等价的便

4、于迭代的形式 x Bx f （ 2）这种转化总能实现，如令 B I A, f b ）并由此构造迭代公式x(k 1)Bx( k)f (3)其中， B 称为迭代矩阵 f 称为 迭代向量 。对任意的初始向量 x(0) ，由( 3)式可求得向 量序列 x(k) 若 lim x(k) x*，则 x(k) 就是方程组 Ax b的解。此时称迭代公式( 3)是 k收敛的，否则称为发散的。 构造的迭代法是否收敛，取决于迭代矩阵 B 的性质 。5.1.1 雅可比迭代公式10x1 x2 2x3 7.2例1 求解方程组x1 10x2 2x3 8.3x1 x2 5x3 4.2 k 1kkx10.1x20.2x30.72

5、x1k 10.1x2k0.2x3k0.72x20.1x10.2x30.83x2k 10.1x1k0.2x3k0.83x30.2x10.2x20.84x3k 10.2x1k0.2x2k0.84设取迭代初值(x)(x,xn(0)(0,0,0)T ，随着迭代次数增加，越来越接近精确解 x(0) x1(0) , x(20) , ,xn(0) T (1.1,1.2,1.3)Tn 设有方程组aij xj bi (1)j1矩阵形式为 Ax b，设系数 矩阵 A 为非奇异 且 aii 0(i 1,2, ,n)，从(1)式的第 i个方程中解出 xi ，得其等价形式xiaiinbiaij x jj 1,j i(i

6、 1,2, n)2)取初始向量 x(0)x1(0) , x(20) , ,xn(0) ，对( 2)式应用迭代法，可建立相应的迭代公式(k 1)xiaii(k)aij xjbi3)j 1, j i记为矩阵形式 x(k 1)x(k) f ( 4)a11若将系数矩阵 A 分解为 D L U ，其中 Da22ann00a120a13 a23a1n a2na210La31a32 0U0an 1nan1an2ann 100则方程组 Ax b变为 (D L U)x b Dx (L U )x bx D 1 L U x D 1b D 1(D A)x D 1b D 1Ax D1b(3)，( 4)分别称为雅克比迭代

7、法的 分量形式和矩阵形式 ，分量形式用于编程，矩阵形式用 于讨论迭代法的收敛性。流程图 P1586。 1。 2高斯 赛德尔( Gauss-Seidel)迭代法雅克比 (Jacobi)迭代法的优点是公式简单， 迭代矩阵容易计算。 在每一步迭代时， 用 x( k) 的全部分量代入求出 x(k 1) 的全部分量，因此称为 同步迭代法，计算时需保留两个近似解向 量x(k)和x(k 1)。但在雅克比迭代过程中， 对已经计算出的信息未能充分利用， 即在计算第 i个分量 xi(k 1) 时，已经计算出的最新分量 x1 , xi 1 没有被利用。从直观上看在收敛的前提下，这些 新的分量 x1(k 1) , x

8、i( k1 1)应比旧分量 x1(k), xi(k1) 更好，更精确一些。因此，如果每计算出一 个新的分量便立即用它取代对应的旧分量进行迭代， 可能收敛更快， 并且只需要存储一个近 似解向量即可。考察例 1，设已得到近似值 x1( k ) , x 2(k ) , x3( k) ，则x1 0.1x2 0.2x3 0.72x2 0.1x1 0.2x3 0.83x3 0.2x1 0.2x2 0.84x1k 1 0.1x2k 0.2x3k 0.72新值 x1k 1 常比老值 x1k 精确，后面得计算用 x1k 1 代替 x1kx2k 1 0.1x1k 1 0.2x3k 0.83再用 x2k 1 代替

9、x2kx3k 1 0.2 x1k 1 0.2x2k 0.84由此得x1k 1 0.1x2k 0.2x3k 0.72x2k 1 0.1x1k 1 0.2x3k 0.83x3k 1 0.2x1k 1 0.2x2k 1 0.84据此思想可构造高斯 赛德尔( Gauss-Seidel)迭代法，其迭代公式为xi(k 1 )aiii1aij x(jk 1)j1naij x(jk) biji1矩阵形式为 X(k 1) BX (k) f仍将系数矩阵 A 分解为 D L U则方程组 Ax b变为 (D L U )x b Dx Lx Ux b 将最新分量代替旧分量，得D (k 1) L (k 1) U ( k)

10、bD L ( k 1) U (k) bx(k 1) (D L) 1Ux(k ) (D L) 1b11D L 1Uf (D L ) 1b在多数情况下用高斯 赛德尔迭代法比雅克比迭代法收敛快。 但也有相反的情况， 即高 斯 赛德尔迭代法比雅克比迭代法收敛慢， 甚至还有雅克比迭代法收敛， 高斯 赛德尔迭代 法发散的情形。6.1.3 高斯 赛德尔( Gauss-Seidel)迭代法 超松弛迭代法是高斯 赛德尔迭代法的一种改进， 是解大型稀疏矩阵方程组的有效方法之一。将前一步得结果xik 与高斯赛德尔迭代值xik 1 加权平均，得到更好得近似值 xik 1。 (k 1 ) 迭代 xiaiii1aijj1(k 1 ) x(jk 1 )nji1aij x(jk)biij j i加速 xik 1 xik 1 (1 ) xik合并后 xik 1i1(k 1 ) aij x j aiij 1nji1aij x(jk)bi(1)xik系数 称为松驰因子。当 1时, 为高斯 赛德尔迭代法 .