第6章线性方程组的迭代法教案

1、K12学习教育第6章 线性方程组的迭代法教案第六章解大型稀疏线性方程组的迭代法教学目的1. 掌握Jacobi迭代法，G-S迭代法解大型 线性方程组的方法及其收敛性的判别方法；2.掌握SOR迭代法及收敛的必要条件(0< a <2 ) ; 3. 了解三种迭代法之间 的改进关系从而掌握该思想方法；4.理解迭代法基本定理。教学重点及难点重点是三种迭代法及收敛性的判别方法；难点是迭代法基本定理及三种迭代法收敛定理的证 明。教学时数 8 学时 教学过程第六章解大型稀疏线性方程组的迭代法迭代法是一种 不断套用一个迭代公式，逐步逼近方程组的精确解的方法。 适合解大型稀疏线性方程组。大型稀疏线性方程

2、组直接法： 解低阶稠密线性方程组，电工学中的网络问题；用差分法或 有限元法解偏微分方程边值问题时得到的方程组。迭代法优 点：O(n)计算量：计算量小，近似解精度高。占用内存 单元较少。设计程序简单。考虑问题：如何构造解 Axb 的有效迭代法？收敛性与收敛速度怎样？3 § 1引言、例子为非奇异阵，方程组 Axb的精确解为x*,即Ax*bo迭代 法的定义：(k)定义1用逐步代入设 ARnnx(0)任取初始向量 B是迭代矩阵(1)*(k)(0)x 是 x 的 k 步近似求近似解的BxfxBk1)(k)x(kBxBx(k)ff,(k11,2,k,2,)K12学习教育K12学习教育方法，称为迭

3、代法。(k)*(0)xx,称迭代法如果对任意初始近似x,都有limk为收敛，否则称迭代法为发散。§2迭代法研究的问题：(k)x收敛)。构造各种解 Axb的有效迭代 法(有效：研究迭代法的收敛性及收敛速度。§3注：为迭代公式，简记为：设ARnn非奇异。问题：用迭代法解线性方程组Axb。将A分离为三部分，即令Aaij,aii0 ,基本思想： nnallAa2200a210an,naa0n1n,n1a120a1nDLUan1,n0 § 2 基 本迭代法常用的是将A分裂为AMN中M为可选择的非奇异阵使 Mxd容易求解，一般 M选为 A的奥 AxbMxNxb或 xM1NxM

4、1b 种近似，于是 1111 若记 BMNM(MA)IMA,fMb B 是 迭代矩阵，则x(0)(k1)(k) 注：M的选法不Bxf(k0,1,)x 同， 得到各种不同的迭代1BIMA法。fM1b并取初始向量x(0) 雅可比(Jacobi)迭代法AMN BIMA1.理论分析：若取 MD附角 阵)， 则 得 ADN,111 得 BIDADDADLUJ , ADLU1fMbDb(0)11x(k1)(k)Bxf(k0,1,)xJacobi 迭 代法：1 BD(LU)J1fDb(k)(k)(k)(k)T 若记 Jacobi 迭代法的分量形式： x(x1,xi,xn) 称为 Jacobi 迭代法的迭代阵

5、 x(k1)Bx(k)f(k0,1,) 有 aiixi(k1)Dx(k1)i1(LU)xnij(k)b , 即 nbiaj1x(k)jaji1ijx(k)jbiaj1jiijxjk,i1,2,n当 aii0时，得到Jacobi迭代法计算公式 2.求解Axb的Jacobi迭 代 法 计 算 公 式：(0)(0)(0)Tx(x1,xn)n1(k)x(k1)(biaijxj)iaiij1i1,2,nji此公式还有另一种推导方式k0,1,表示迭代次数。注：(k)(1)Jacobi 迭代法， 每迭代一次主要是计算一次矩阵乘向量Bx oa11x1a12x2a1nxnb1a21x1a22x2a2nxnb2A

6、xbaxaxaxbn22nnnn n11aii0a11x1b1a12x2a1nxna22x2b2a21x1a2nxnaxbaxaxnn2 2nn1n1nnn n1x(ba1jxj)11a11a11x1b1a12x2a1nxni2n1a22x2b2a21x1a2 nxnx(b2a2jxj)Axb2ai122j2axbaxaxnn22nn1n1nnnn1(0)n1( k1)(k) 于 是 xi 给 定， xi(biaijxj)x1(bax)njjnnaiij1ai1nnji(i1,2,n)(1)Jacobi迭代法实际上是近似解 x(k)(x1(k),xi(k),xn(k)T说明：的 n-1 分量

7、x1(k),xi(k1),xi(k1),xn(k)计 算x(k1)(x1(k1),xi(k1),xn(k1)T的第 i 个分量。(2)若x*(k) 收敛于x,则x*(k1)比x(k)(k1)(k) 更接近于x。则 xi比xi更*考虑问题：(k1)x(ik1),x(k1)T 的第i个分量 x(k1) 时，它 的 前 i1 个 计 算 x(k1)(x1(k1),xiin(k1)(k1)(k1)(k1)分量 x1,xi1 均已求出,设想用 x1,xi1,代替Jacobi(k)(k)(k)T迭代法中的x(k)(x1(k),xi(k),xn) 的前 i1 个分量:x1,xi1。 接近于xi o ADLU

8、AM高斯-塞德尔迭代法取分裂阵MDLfF三角阵),得 ADLN 111 得 BI(DL)A(DL)(DL)A)(DL)UG 于是得到解 Axb 的G-S迭代法：N其中G称为G-S迭代法的迭代阵K12学习教育K12学习教育x(0)(k1)(k)Bxfx1B(DL)UG1f(DL)bBIM1Ax(k1)Bx(k)f(k0,1,)1fM(k)(k)(k)1b(DL)b(k)T若记 G-S 迭代法的分量形式：x(x1,xi,xn), (k1)(k1)(k)LxUxb 式有(DL)x(k1)Ux(k)b 或Dx当aii0 时得到以下解 Axb的G-S迭 代法计算公式：x(0)(x1(0),xn(0)Ti

9、1(k1)1(k1)x(baxmjjaiij1n其中k =1,2,表示迭代次数aijxj(k)(i1,2,n) ji1或写成增 量 修 正 的 形 式： (k1)(k)iaiixxi(k)j1(k)xixxiii11(k1)(kk)(biaijxjaa ijijxxjj)(i1,2,n)xiaiij1jjiix 其中 k =1,2,i表示迭代次数 nn (k1)1i1(biaijxj(k1)naji1ijxj(k)优点：(1) 可知，计算x(k1)第i个分量时，利用已经计算由的最新 (k)(k1)(k1) 分量xj(j1,2,i1),因此，计算 xi就可冲掉xi,于是利)x(k1)分量。用G-

10、S迭代法解只需要一组工作单 元，用来保存x(k或G-S迭代存贮少。(2)G-S迭代法每迭代 一次主要计算一次矩阵乘向量。计算量小， (3)当J-迭代与 G-S迭代都收敛时，G-S迭代的收敛速度快。G-S迭代法可看 作J迭代法的一种修正或改进。例2用Jacobi迭代法，G-S迭代法解下述方程组8x1x2x38Tx(1,1,1) 精确解2x110x2x311或Axb(k1)(k)(k)x1(8x2x3)/8(k1)x1x25x33(k)(k)x2(112x1( 3x1(k)Jacobi 迭代公式： (k) 其 中， K12学习教育K12学习教育x(k)(k)(k)Tx3)/10(k)x3(k1)x2)/5(x1,x2,x3),(k0,1,)表6-1(0), 计 算 结 果 见 表 6-1。x(5)x(k)(k)(k)(k)xx(1)x(2)x(3)x(4).6600.99649964且 有 x(5)x G-S 迭 代 公 式 (k1)(k)(k)x1(8x2x3)/8(k1)(k1)(k)(112x1x3)/10x2(k1)(k1)(k1)(3x1x2)/5x3(k)(k)(k)(k)Tx(x1,x2,x3),(k,),其中， 计 算 结 果 见： 表 6-2x(k)(k)(k)(k)x(0)x(1)x(2)x(3)x(4).99996875999968750x2x3