电子科大 数值分析课件第四章 线性方程组的迭代解法

第四章线性方程组的迭代解法迭代法的基本思想Jacobi迭代和Gauss－Seidel迭代迭代法的收敛性超松弛迭代分块迭代法第四章线性方程组的迭代解法4.1迭代法的基本思想：例：求解方程组3612363311420238321321321xxxxxxxxx其精确解是x*=(3,2,1)T。现将原方程组改写为)3636(121)334(111)2023(81213312321xxxxxxxxx简写为x=B0x+f，其中01231261110114828300B12361133820f任取初始值，如取x(0)=(0,0,0)T，代入x=B0x+f右边，若等式成立则求得方程组的解，否则，得新值x(1)=(x1(1),x2(1),x3(1))T=(2.5,3,3)T，再将x(1)代入，反复计算，得一向量序列{x(k)}和一般的计算公式（迭代公式）：)3636(121)334(111)2023(81)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx简写为x(k+1)=B0x(k)+fk=0,1,2,……x(10)=(3.000032,1.999838,0.999813)T迭代到第10次时有||ε(10)||∞=||x(10)–x*||=0.000187定义：（1）对于给定方程组x=Bx+f，用迭代公式x(k+1)=Bx(k)+f(k=0,1,2,……)逐步代入求近似解的方法称迭代法；（2）若k∞时limx(k)存在（记为x*），称此迭代法收敛，显然x*就是方程组的解，否则称迭代法发散；（3）B称为迭代矩阵。问题：如何建立迭代格式？收敛速度？向量序列的收敛条件？误差估计？设Ax=b，A非奇异，且对角元不为零，将原方程组改写为4.2Jacobi迭代与Gauss－Seidel迭代)(1)(1)(111,212121222212121111nnnnnnnnnnnnxaxabaxxaxabaxxaxabax4.2.1Jacobi迭代法又代入，反复继续，得迭代格式：),,,()0()0(2)0(1)0(nxxxx),,,()1()1(2)1(1)1(nxxxx)(1)(1)(1)(11,)(11)1()(2)(121222)1(2)(1)(212111)1(1knnnknnnnknknnkkknnkkxaxabaxxaxabaxxaxabax称Jacobi迭代法。选取初始向量代入上面方程组右端得1112111111122221222222121...1............1nnnnnnnnnnnnbaaaxaaxbaaaaaaaxbaaa112111111111222221222222120...0..............0nnnnnnnnnnnnnaabaaaxxxxabaaaaIxxbaaaaaJacobi迭代法的矩阵表示：nnnnnnnnbbbxxxaaaaaaaaa2121212222111211()1,(1)()1,1[]nkijjnjjikkiiiijjjjiiiiiiiaxbxbaxaaa112111111111222221222222120...0..............0nnnnnnnnnnnnnaabaaaxxxxabaaaaxxbaaaaa计算公式为：(i=1,2,……,n)，(k=0,1,2,……表迭代次数)JkJkfXBX)()1(矩阵表示：nnaaaD22110002121nnaaaL0002112nnaaaU则BJ=I-D-1A=D-1(L+U)，fJ=D-1b，称BJ为Jacobi迭代矩阵。（aii≠0）JkJkfXBX)()1(将方程组Ax＝b的系数矩阵A分解为：A=D-L-U例1:用Jacobi迭代法求解方程组，误差不超过10-4。1233204121114238321xxx解:4121114238A4000110008D000100230U012004000L)(1ULDBJ04121111011441830bDf1335.2迭代法使用取初值JacobixT,]000[)0(fxBxkJk)()1(),,2,1,0(nk04121111011441830fxBxJ)0()1(335.2000T]3,3,5.2[924.42)0()1(xx04121111011441830fxBxJ)1()2(335.2335.2T]1,3636.2,875.2[1320.22)1()2(xx04121111011441830fxBxJ)2()3(335.213636.2875.2T]9716.0,0455.2,1364.3[4127.02)2()3(xx依此类推,得方程组满足精度的解为x12迭代次数：12次x4=3.02411.94780.9205d=0.1573x5=3.00031.98401.0010d=0.0914x6=2.99382.00001.0038d=0.0175x7=2.99902.00261.0031d=0.0059x8=3.00022.00060.9998d=0.0040x9=3.00031.99990.9997d=7.3612e-004x10=3.00001.99990.9999d=2.8918e-004x11=3.00002.00001.0000d=1.7669e-004x12=3.00002.00001.0000d=3.0647e-0050000.10000.20000.3321xxx若在迭代时尽量利用最新信息，则可将迭代格式变为4.2.2Gauss－Seidel迭代法)(1)(1)(1)1(11,)1(11)1()(2)1(121222)1(2)(1)(212111)1(1knnnknnnnknknnkkknnkkxaxabaxxaxabaxxaxabax称Gauss－Seidel迭代法.计算公式：1112)(111)1(111baxaaxnjkjjkiiinijkjijiiijkjijiikibaxaaxaax1111)(11)1()1(nnnnjkjnjnnknbaxaax1111)1()1(（i=2,3,……,n-1）nijkjijijkjijikiiixaxabxa1)(11)1()1(][nijkjijiijkjijxabxa1)(1)1((i=1,2,…,n)即其中BG-S=(D-L)-1U称Gauss－Seidel迭代矩阵。bLDUXLDXkk1)(1)1()()(SGkSGkfXBX)()1()()(2)(1,111221)1()2(2)1(121222111000knkknnnnknkknnnnxxxaaabbbxxxaaaaaa(D–L)x(k+1)=b＋Ux(k)故Gauss－Seidel迭代格式：1.矩阵的范数（三种算子范数、谱半径、谱范数、F-范数）前一次课内容回顾3.迭代法求解线性方程组（Jacobi迭代、Gauss-Seidel迭代及其矩阵表示）2.线性方程组求解的误差分析（病态方程组、良态方程组、扰动分析、事后误差估计）1233204121114238321xxx例2.用Gauss-Seidel迭代法求解例1方程组要求误差仍然不超过10-4。解:Gauss-Seidel迭代格式为3)2(413)4(1115.2)23(81)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxxx1=2.50002.09091.2273d=3.4825x2=2.97732.02891.0041d=0.5305x3=3.00981.99680.9959d=0.0465x4=2.99981.99971.0002d=0.0112x5=2.99982.00011.0001d=3.9735e-004x6=3.00002.00001.0000d=1.9555e-004x7=3.00002.00001.0000d=1.1576e-005取初值x(0)=(0,0,0)T通过迭代，至第7步得到满足精度的解x7：从例1和例2可以看出，Gauss-Seidel迭代法的收敛速度比Jacobi迭代法要快。Jacobi迭代法和Gauss-Seidel迭代法统称为简单迭代法。4.3迭代法的收敛性设求解线性方程组的迭代格式为fBxxkk)()1(fBxx**将上面两式相减,得*)(*)()1(xxBxxkk*)()(xxkk令,2,1,0k而方程组的精确解为x*，则则)()1(kkB)1(2kB)0(1kB为非零常数向量注意*)0()0(xx因此迭代法收敛的充要条件*)(limlim)1()1(xxkkkk00lim1kkB可转变为引理：迭代格式0limkkBfBxxkk)()1(收敛的充要条件为定理：迭代格式fBxxkk)()1(收敛的充要条件为迭代矩阵的谱半径(B)1。证:对任何n阶矩阵B，都存在非奇矩阵P，使B=P–1JP其中，J为B的Jordan标准型。nnrJJJJ21iinniiiJ11其中,Ji为Jordan块其中λi是矩阵B的特征值，由B=P–1JPBk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f收敛=0limkkB0limkkJ0lim