数值分析解线性方程组的迭代法课件.ppt
第1页，此课件共28页哦一、迭代法的一般形式bAx 同解变形fBxx 构造迭代公式fBxxkk )()1(任取初始向量x(0)，代入迭代公式，产生向量序列x(k)，若x(k)收敛，则当k 充分大时，以x(k)作为方程组的近似解，就是迭代法.第2页，此课件共28页哦二、向量序列的收敛性定义1设 x(k)为Rn中的向量序列，xRn，如果0|lim)(xxkk其中|.|为向量范数，则称序列 x(n)收敛于 x，记为 xxkk )(lim第3页，此课件共28页哦定理1Rn中的向量序列 x(k)收敛于Rn中的向量 x 当且仅当),.,2,1(lim)(nixxikik 其中TnTknkkkxxxxxxxx),.,(,),.,(21)()(2)(1)(第4页，此课件共28页哦三、矩阵序列的收敛性定义2设 A(k)为 n 阶方阵序列，A为n阶方阵，如果0|lim)(AAkk其中|.|为矩阵范数，则称序列 A(n)收敛于A，记为 AAkk )(lim第5页，此课件共28页哦定理2设 A(k)=(aij)(k=1,2,)，A=(aij)均为 n 阶方阵，则矩阵序列A(n)收敛于矩阵A的充要条件为),.,2,1,(lim)(njiaaijkijk 第6页，此课件共28页哦请回答:对于任何一个方程组 x=Bx+f(由 Ax=b 变形得到的等价的方程组)，按迭代法作出的向量序列 x(k)是否一定逐步逼近方程组的解 x*呢？答：不一定！例如用迭代法解方程组 53521221xxxx其精确解为 4321xx若选初值 x(0)=(0,0)T进行迭代，则,.)20,15(,)5,5()2()1(TTxx 不可能收敛到精确解.第7页，此课件共28页哦因此下面我们将要研究几个问题：如何构造迭代公式？如何判断迭代公式收敛？在收敛条件下，如何判断收敛速度？第8页，此课件共28页哦一、Jacobi迭代法 迭代法（2）二、Gauss-Seidel迭代法三、超松弛迭代法第9页，此课件共28页哦一、Jacobi迭代法1.Jacobi迭代法举例例：求解方程组 3612363311420238321321321xxxxxxxxx其中 12361114238A 321xxxx 363320b精确解是x*=(3,2,1)T第10页，此课件共28页哦解：将原方程组改写为 12/)3636(11/)334(8/)2023(213312321xxxxxxxxx则迭代公式为：12/)3636(11/)334(8/)2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx若选 x(0)=(0,0,0)T,则迭代10次有x(10)=(3.000032,1.999838,0.9998813)T这就是Jacobi迭代法！第11页，此课件共28页哦2.Jacobi迭代法一般形式由方程组 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111的系数矩阵A非奇异，不妨设 aii0，方程组变形为 nnnnnnnnnnnnnabxaxaxaxabxaxaxabxaxax/).(./).(/).(1,22112222121211112121第12页，此课件共28页哦对应上述的方程组，可得迭代公式为(0)(0)(0)(0)12(1)()1(,.,)()1()Tnnkkiiijjjiij ixxxxxba xa初始向量其中 x(k)为第 k 次迭代向量.Jacobi迭代法的一般公式第13页，此课件共28页哦3.Jacobi迭代法的矩阵形式将方程组记为 Ax=b其中A非奇异且aii 0(I=1,2,n).将A分裂为 A=D其中 nnaaaD2211 0.002121nnaaaL 0.0.02112nnaaaU第14页，此课件共28页哦由此可将变形过程用矩阵表示为 Dx=(L+U)x+b即 x=D-1(L+U)x+D-1b简记为 x=B0 x+f故Jacobi迭代公式的矩阵形式为 fxBxxxxxkkTn)(0)1()0()0(2)0(1)0()(),.,(初始向量初始向量第15页，此课件共28页哦二、Gauss-Seidel迭代法1.Gauss-Seidel迭代法举例例：求解方程组 3612363311420238321321321xxxxxxxxx精确解是x*=(3,2,1)T第16页，此课件共28页哦解：将原方程组改写为 12/)3636(11/)334(8/)2023(213312321xxxxxxxxx则迭代公式为：若选 x(0)=(0,0,0)T,则迭代5次有x(5)=(2.999843,2.000072,1.000061)T这就是Gauss-Seidel迭代法:认为最新计算出的分量可能比旧的分量要好些！8/)2023()(3)(2)1(1 kkkxxx11/)334()(3)1(1)1(2 kkkxxx12/)3636()1(2)1(1)1(3 kkkxxx第17页，此课件共28页哦2.Gauss-Seidel迭代法一般形式对应于变形方程组 nnnnnnnnnnnnnabxaxaxaxabxaxaxabxaxax/).(./).(/).(1,22112222121211112121G-S迭代公式可写为：)(1)(),.,(1)(11)1()1()0()0(2)0(1)0(nijkjijijkjijiiikiTnxaxabaxxxxx初始向量初始向量其中 x(k)为第 k 次迭代向量.第18页，此课件共28页哦3.Gauss-Seidel迭代法的矩阵形式将方程组记为 Ax=b其中A非奇异且aii 0(I=1,2,n).将A分裂为 A=D其中 nnaaaD2211 0.002121nnaaaL 0.0.02112nnaaaU第19页，此课件共28页哦由此可将方程组的变形过程用矩阵表示为 Dx=(L+U)x+b这G-S迭代可表示为 Dx(k+1)=Lx(k+1)+Ux(k)+b整理得 x(k+1)=(DL)1Ux(k)+(DL)1b故G-S迭代公式的矩阵形式为 bLDUxLDxxxxxkkTn1)(1)1()0()0(2)0(1)0()()()(),.,(初始向量初始向量第20页，此课件共28页哦注：对有些问题Gauss-Seidel迭代法确实比Jacobi迭代法收敛得快;但也有Gauss-Seidel迭代法比Jacobi迭代法收敛得慢;1.甚至还有Jacobi迭代法收敛，而Gauss-Seidel迭代法发散的情形。第21页，此课件共28页哦三、超松弛迭代法1.超松弛迭代法的一般形式为了加速迭代过程的收敛，我们通过引入参数，在Gauss-Seidel迭代的基础上得到一种新的迭代法。记)()1(21),.,(kkTnxxxxxx 其中x(k+1)由G-S方法算出。于是有第22页，此课件共28页哦)(1)(11)1()(1kinijkjijijkjijiiiixxaxabax （i=1,2,n）可以把 x 看作G-S迭代的修正项，即第 k 次近似解 x(k)以此项修正后得到新的近似解 x(k+1)=x(k)+x 松弛法是将x 乘上一个参数因子作为修正项而得到新的近似值，其具体公式为：第23页，此课件共28页哦),.,2,1()()1(1)(11)1()()()1(nixaxabaxxxxnijkjijijkjijiiikiikiki x(k+1)=x(k)+x即按上式计算方程组近似解序列的方法称为松弛法，1时，称为超松弛法，简称SOR法第24页，此课件共28页哦2.超松弛迭代法举例例：用超松弛法求解下列方程组，取=1.4 3612363311420238321321321xxxxxxxxx精确解是x*=(3,2,1)T第25页，此课件共28页哦解：将原方程组改写为 12/)3636(11/)334(8/)2023(213312321xxxxxxxxx则迭代公式为：8/)2023(4.14.0)(3)(2)(1)1(1 kkkkxxxx11/)334(4.14.0)(3)1(1)(2)1(2 kkkkxxxx12/)3636(4.14.0)1(2)1(1)(3)1(3 kkkkxxxx第26页，此课件共28页哦3.超松弛迭代法的矩阵形式用分解式 A=D，则可写为)()1()()1()()1(kkkkUxLxbDxDx )()1(1)(11)1()()1(nijkjijijkjijikiiikiiixaxabxaxa 迭代公式也可写为：即bxUDxLDkk )()1()1()(显然对任何值，(DL)非奇异，故第27页，此课件共28页哦bLDxUDLDxkk1)(1)1()()1()(bxUDxLDkk )()1()1()(这就是松弛迭代法的矩阵表示。注：松弛法是G-S法的一种加速方法；具有计算公式简单，程序设计容易；(1)但需要选择较好的加速因子。第28页，此课件共28页哦
