第2章线性方程组的迭代法课件.ppt

1、科大研究生学位课程1第第2 2章章 解线性方程组的迭代法解线性方程组的迭代法n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111（2.1）或 Ax=b思思路路与解与解 f(x)=0 的不动点迭代相似的不动点迭代相似,将将Ax=b等价改写为等价改写为x=Mx+f,建立迭代建立迭代x(k+1)=Mx(k)+f,从从初值初值x(0)出发，得到序列出发，得到序列x(k).研究研究 内容：内容：如何建立迭代格式？如何建立迭代格式？收敛速度？收敛速度？向量序列的收敛条件？向量序列的收敛条件？误差估计？误差估计？（2.2）科大研究生学位课程2

2、2.1 迭代法的一般理论 为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。科大研究生学位课程3向量和矩阵的范数 而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。推广到n维空间，则称为向量范数。|22OPyx22122121)()(|yyxxPP科大研究生学位课程42.1.1 2.1.1 向量和矩阵的范数向量

3、和矩阵的范数向量的范数向量的范数 定义定义2.2 2.2 设是向量空间Rn上的实值函数,且满足条件:(1)非负性非负性:对任何向量xRn,x0,且x=0当 且仅当x=0 0 (2)齐次性齐次性:对任何向量x Rn 和实数,x=|x (3)三角不等式三角不等式:对任何向量x,yRn x+yx+y则称为空间Rn上的范数,x为向量x的范数.科大研究生学位课程5 记x=(x1,x2,xn)T,常用的向量范数有:向量的向量的1-1-范数范数:x1=|x1|+|x2|+|xn|向量的向量的2-2-范数范数:x2=22221nxxx 向量的向量的-范数范数:x=|max1inix 例例 设向量x=(2,-4

4、,3,1)T,求向量范数xp,p=1,2,.解解 由定义x1=10,x2=30,x=4.虽然不同范数的值可能不同，但它们间存在等价关系.定理定理 (范数的等价性范数的等价性)对于 Rn 上的任何两种范数和,存在正常数m,M,使得 m x x M x,xRn科大研究生学位课程6 常用的三种向量范数满足如下等价关系 x x1 nx,xRnnRnxxxx,2nRnxxxx,212 定义定义 设向量序列,),()()(2)(1)(Tknkkkxxxx k=1,2,向量,),(*2*1*Tnxxxx如果 0lim*)(xxkk则称向量序列x(k)收敛于向量x*,记作 )(,lim*)(*)(kkkkxx

5、xx或易见,nixxikik,2,1,*)(*)(xx科大研究生学位课程72.2.矩阵的范数矩阵的范数 定义定义2.3 2.3 设是以n阶方阵为变量的实值函数,且满足条件:(1)非负性非负性:A0,且A=0当且仅当A=0 0 (2)齐次性齐次性:A=|A,R (3)三角不等式三角不等式:A+BA+B (4)相容性相容性:ABAB则称A为矩阵A的范数.记A=(aij),常用的矩阵范数有:矩阵的矩阵的1-1-范数范数:A1 niijnja11max,也称矩阵的列范数列范数.矩阵的矩阵的2-2-范数范数:A2)(maxAAT,也称为谱范数谱范数.科大研究生学位课程8 矩阵的矩阵的-范数范数:A nj

6、ijnia11max,也称为行范数行范数.矩阵的矩阵的F F-范数范数:AF njiija1,2例例 设矩阵3211A求矩阵A的范数Ap,p=1,2,F.解解 A1=4,A=5,AF 151055532113121AAT010555令25515,25515,21得255152A所以科大研究生学位课程9 设是一种向量范数,则定义AxxAxAx0 x1maxmax 称之为由向量范数派生的矩阵算子范数矩阵算子范数.矩阵的算子范数满足 AxAx,xRn把满足上式的矩阵范数称为与向量范数与向量范数相容相容的矩阵范数的矩阵范数.对于p=1,2,矩阵范数Ap是由向量范数xp派生的矩阵算子范数,所以Ap是与x

7、p相容的矩阵范数.但AF不是一种算子范数,却与x2是相容的.设是一种算子范数,则1max xxII0 xnIF，但科大研究生学位课程10 矩阵的范数与矩阵的特征值之间也有密切的联系.设是矩阵A的特征值,x是对应的特征向量,则有 Ax=x利用向量和矩阵范数的相容性,则得|x=x=AxAx 于是|A 设n阶矩阵A的n个特征值为1,2,n,则称 ini1max)(A为矩阵A的谱半径谱半径.对矩阵的任何一种相容范数都有 (A)A 另外,0,一种相容范数,使 A(A)+科大研究生学位课程11 任何两种矩阵范数也具有等价性 m A A M A,ARnn 矩阵序列的收敛性也定义为矩阵序列的收敛性也定义为0l

8、imlim*)(*)(AAAAkkkk njiaaijkij,1,*)(。的充分必要条件是则设定理1)(0lim,AkAkRAnn科大研究生学位课程1212.3:|1,1|()|1|AIAIAA定理如果则为非奇异，且000det(-)0(-)00IAIA xxAxx证明：（反证法）若有非零解，即，使得0000|1|AxAxAxx而|1,A从而与假设矛盾-1(-)(-)IA IAI又11()()I IAA IAI11()()IAIA IA11|()|()|IAIAIA11|()|1|IAA科大研究生学位课程13把n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.221

9、12222212111212111（2.1）或 Ax=b改写成等价的方程组 nnnnnnnnnnnfxmxmxmxfxmxmxmxfxmxmxmx2211222221212112121111 或 x=Mx+f2.1.2 迭代格式的构造（2.2）科大研究生学位课程14由此建立方程组的迭代格式 x(k+1)=Mx(k)+f,k=0,1,2,(2.5)其中M称为迭代矩阵迭代矩阵。对任意取定的初始向量x(0),由(2.5)式可逐次算出迭代向量x(k),k=1,2,如果向量序列x(k)收敛于x*,由(2.5)式可得 x*=Mx*+f 从而x*是方程组x=Mx+f 的解,也就是方程组Ax=b的解.对迭代格

10、式(2.5),定义误差向量 e(k)=x(k)-x*,则迭代法收敛就是e(k)0 0.由于 x(k+1)=Mx(k)+f k=0,1,2,x*=Mx*+f k=0,1,2,科大研究生学位课程15 x(k+1)=Mx(k)+f k=0,1,2,x*=Mx*+f k=0,1,2,所以 e(k+1)=Me(k),k=0,1,2,递推可得 e(k)=Mke(0),k=0,1,2,可见,当k时,e e(k)0 0 Mk O O.对任意初始向量x(0),迭代法收敛(M)1.定理定理2.4证证:(必要性）若(M)0,使得(M)+1.则由定理2.2MkMk(M)+)k 0.若Mk0,k(M)=(Mk)Mk0,

11、所以(M)1.科大研究生学位课程16 若若M1,则对任意x(0),迭代法收敛,而且 定理定理2.5-6)9.2(1)0()1(xxMMxxk*(k)10.2(1)1()(*)(kkkxxMMxx 证证 由于 x(k+1)=Mx(k)+f,x(k)=Mx(k-1)+f x*=Mx*+f所以 x(k+1)-x(k)=M(x(k)-x(k-1),x(k+1)x*=M(x(k)x*)于是有 x(k+1)-x(k)Mx(k)-x(k-1)x(k+1)x*Mx(k)x*x(k+1)-x(k)=(x(k+1)x*)-(x(k)x*)x(k)x*-x(k+1)x*(1-M)x(k)x*科大研究生学位课程17所

12、以)()1(*)(11kkkxxMxx)1()(1kkxxMM)0()1(1xxMMk 上述定理只是收敛的充分条件,并不必要,如7.005.08.0M则M1=1.2,M=1.3,M2=1.09,MF=1.17但(M)=0.81,所以迭代法是收敛的.由由(2.10)(2.10)式可见式可见,M越小收敛越快越小收敛越快,且当且当x(k)-x(k-1)很小很小时时,x(k)x*就很小就很小,实际上用实际上用x(k)-x(k-1)作为作为迭代终止迭代终止的条件的条件.科大研究生学位课程18 ,即若使x(k)x*,只需)0()1(1xxMMkM)xx)M(1ln/)ln()0()1(k可以事先估计达到某

13、一精度需要迭代多少步可以事先估计达到某一精度需要迭代多少步.线性方程组的迭代法主要有线性方程组的迭代法主要有Jocobi迭代法、迭代法、Gauss-Seidel迭代法和超松弛迭代法和超松弛(Sor)迭代法迭代法.科大研究生学位课程19nnnnnnnnnnbxaxaxabxaxaxabxaxaxa221122222121112121112.2雅克比（雅克比（Jacobi）迭代法）迭代法若系数矩阵非奇异，且若系数矩阵非奇异，且 (i=1,2,n)，将方程组将方程组0iia改成改成11,221112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxax

14、abaxxaxaxabax科大研究生学位课程20然后写成迭代格式然后写成迭代格式)(11,)(22)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax（2.11）（2.11）式也可以简单地写为式也可以简单地写为),2,1(1)(1)1(nixabaxkjnijjijiiiki（2.11）科大研究生学位课程21写成写成矩阵形式矩阵形式：A=LUDBfJacobi 迭代迭代阵阵bDxULDxkk1)(1)1()(2.12)bxULDxbxULDbA

15、x )()(bDxULDx11)(科大研究生学位课程22算法算法2.1（Jacobi迭代法）：迭代法）：(0)(0)(0)(0)112(0)1(0)(0)1.(),(,),(,),.2.1.3.1,2,()/4.,55.,1,(1,2,),3 ijnnniiijjiijj iiiAabbbn xxxxNkinxba xaxxxkNkk xxin 输入维数最大容许迭代次数置对若输出 停机；否则转。若置转；否则，输出失败信息，停机。()(1,kkMxx）评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变的稀疏性，需两组工作单元，存。程序见P19。科大研究生学位课程232.2.2 Jac

16、obi迭代法的收敛条件迭代法的收敛条件 迭代格式收敛(B)1。若B1迭代法收敛.定理：若系数矩阵A满足下列条件之一，则Jacobi迭代收敛。A为行对角占优阵A为列对角占优阵 A满足nijjijiiaa,1jiijjjaa1,1nijjiijiaa对于Jacobi迭代，我们有一些保证收敛的充分条件.引理引理 若A是严格对角占优矩阵,则det(A)0.证证 A=D-L-U=D(I-D-1(L+U)=因为A是严格对角占优矩阵,所以det(D)0,而且1max11nijjiiijniaaB因此,(B)B1,故=1不是B的特征值,det(I-B)0.所以,det(A)0.D(I-B)科大研究生学位课程2

17、4证明：)(1ULDB iiijijijiiijiaaaaB 1max1max1 jiiiijiaaB 由条件知，A为列对角占优阵，则AT为行对角占优阵，有)()(1TADIB证毕A为行对角占优阵A为列对角占优阵)(1TTADI11)(DAIDAITT1max11nijjiijiniaa科大研究生学位课程25 为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：iinijkjijijkjijikiaxaxabx1)1(11)()(2.3 .3 高斯高斯赛得尔赛得尔(Gauss-Seidel)迭代法迭代法逐一写出来即为

18、科大研究生学位课程26)(1)(1)(414)(313)(212111)1(1knnkkkkxaxaxaxabax)(1)(2)(424)(323)1(121222)1(2knnkkkkxaxaxaxabax)(1)(3)(434)1(232)1(131333)1(3knnkkkkxaxaxaxabax)(1)1(11)1(33)1(22)1(11)1(knnnknknknnnnknxaxaxaxabax 只存一组向量即可。只存一组向量即可。写成写成矩阵形式矩阵形式：bDUxLxDxkkk1)()1(1)1()(bUxxLDkk )()1()(bLDUxLDxkk1)(1)1()()(B fG

19、auss-Seidel 迭代阵迭代阵2.3 .3 高斯高斯赛得尔赛得尔(Gauss-Seidel)迭代法迭代法(2.14)(2.16)科大研究生学位课程27(0)(0)(0)(0)112(0)1111121(0)111.(),(,),(,),.2.1.3.()/()/(2,1)(ijnnnjjjiniiijjijjiijjinnAabbbn xxxxNkxba xaxba xa xainxba 输入维数最大容许迭代次数置计算11(0)(0)/4.,55.,1,(1,2,),3nnjjnnjiixaxxxkNkk xxin若输出停机；否则转。若置转；否则，输出失败信息，停机。程序见P23。算法算

20、法2.2（Gauss-Seidel迭代法）：迭代法）：科大研究生学位课程28 例例 用雅可比迭代法解方程组用雅可比迭代法解方程组 2.453.82102.7210321321321xxxxxxxxx 3.12.11.1x )2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx解：雅解：雅 可可 比比 迭迭 代代 格式为格式为科大研究生学位课程29kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15 11 1.099993 1.199993 1.29999112 1.09

21、9998 1.199998 1.299997 取取计算如下计算如下 Tx)0,0,0()0()2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx科大研究生学位课程30 解：解：Gauss-Seidel 迭代格式为迭代格式为 )2.4(51)3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 例例 用用GaussSeidel 迭代法解上题。迭代法解上题。2.453.82102.7210321321321xxxxxxxx

22、x科大研究生学位课程31取取 x(0)=(0,0,0)T 计算如下：计算如下：kx1(k)x2(k)x3(k)10.720.9021.1644 81.0999981.1999991.3 )2.4(51)3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx科大研究生学位课程322.3.2 收敛条件收敛条件我们看一下Gauss-Seidel迭代法收敛的充分条件定理：若A满足下列条件之一，则Seidel i迭代收敛。A为行或列对角占优阵A对称正定阵（证略书上定理2.9）迭代格式收敛(B)1。若B1迭代法收敛.det(

23、I-B)=det(I-(D-L)-1U)证明：=det(D-L)-1)det(D-L)-U)=0所以有 det(D-L)-U)=0nnnnnnaaaaaaaaa212222111211UL)(D科大研究生学位课程33nnnnnnaaaaaaaaa212222111211UL)(D 若|1,则矩阵(D-L)-U 是严格对角占优矩阵,这与 det(D-L)-U)=0矛盾,所以|1,于是(B)1.二种方法都存在二种方法都存在收敛性问题收敛性问题。有例子表明：有例子表明：Gauss-Seidel法收敛时，法收敛时，Jacobi法可能法可能不收敛；而不收敛；而Jacobi法收敛时，法收敛时，Gauss-

24、Seidel法也可能法也可能不收敛。不收敛。科大研究生学位课程342.4 逐次超松弛迭代法逐次超松弛迭代法记)()1()(kkkxxx则)()()1(kkkxxx可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有)()()1(kkkxxx)()()1(1)1(bUxLxDxkkk对GaussSeidel迭代格式)1()()()1()()1()1()(kkkkkkxxxxxx)()(1)(1)1(1)()1(kkkkkxbDUxDLxDxx)()1(1)(1)1(1)()1(bDUxDLxDxxkkkk(2.22)bDxUDIxLDIkk1)(1)1(1)1()(科大研究生学位课程35

25、故故SOR的迭代格式的迭代格式bDxUDIxLDIkk1)(1)1(1)1()(bDLDIxUDILDIxkk111)(111)1()()1()(bLDfUDLDB11)()1()(bLDxUDLDxkk1)(1)1()()1()(（2.23）SOR的迭代矩阵的迭代矩阵科大研究生学位课程36)(1)1(11)1(1kjnijijkjijijiiikixaxabax),2,1()1()1()()1(nixxxkikiki)(1)1(11)()1()1(kjnijijkjijijiiikikixaxabaxx用分量形式讨论，设用分量形式讨论，设加速加速（迭代公式）（迭代公式）是松驰因子是松驰因子(

26、02),当01时叫超松弛，=1时，就是Gauss-Seidel迭代法。科大研究生学位课程37(0)(0)(0)(0)112(0)(0)11111121(0)(0)111.(),(,),(,),.2.1.3.(1)()/(1)()/ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxbaxaxxba xa xa 输 入维 数最 大 容 许 迭 代 次 数，参 数置计 算1(0)1(0)(0)(2,1)(1)()/4.,55.,1,(1,2,),3nnnnnjjnnjiiinxxbaxaxxxkNkk xxin若输 出停 机；否 则 转。若置转；否 则，输 出 失 败 信

27、 息，停 机。程序见P28。算法算法2.3（SOR迭代法）：迭代法）：科大研究生学位课程38 例 用SORSOR方法解线性方程组7910431017210424321321321xxxxxxxxx解解 SORSOR方法迭代公式为方程组的精确解是x*=(2,1,-1)T.)91047(9)101723(17)42410(4)(3)1(2)1(1)(3)1(3)(3)(2)1(1)(2)1(2)(3)(2)(1)(1)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx取x(0)=(0,0,0)T,=1.46,计算结果如下:科大研究生学位课程39kx1(k)x2(k)x3(k)012

28、32003.652.321669102.56613991.999998700.88458820.42309390.69482611.00000130-0.2021098-0.22243214-0.4952594-1.0000034 从结果可见,迭代20次时已获得精确到小数点后五位的近似解.如果取=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.科大研究生学位课程402.4.2 SOR迭代法的收敛条件迭代法的收敛条件 迭代格式收敛(B)1。若B1迭代法收敛.对于SOR迭代，我们有一些收敛的结果.定理定理2.102.10 SORSOR方法收敛的必要条件是0

29、2.证证 设SORSOR方法收敛,则(B)1,所以|det(B)|=|12 n|1而 det(B)=det(D-L)-1(1-)D+U)=det(I-D-1L)-1 det(1-)I+D-1U)=(1-)n于是|1-|1,或 02科大研究生学位课程41 定理定理2.112.11 设A是对称正定矩阵,则当00科大研究生学位课程42(Dy,y)=0 (Uy,y)=(y,Ly)=(Ly,y)=-i 0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以)()()1(ii2222222)()(|当02时,有 (-+)2-(-)2=(2-)(2-)=(2-)(2-)0所以|21,因此(B)1

30、,即S0R方法收敛.科大研究生学位课程43 推论推论2.12.1 A是对称正定矩阵,Jacobi迭代法收敛的充要条件是2D-A也对称正定。证证设是Jacobi迭代矩阵B的任一特征值,y是对应的特征向量,则(L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)可得 =2/当A对称正定时,即2-0时,|0而 (2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2即,当A对称正定时,JacobiJacobi迭代法收敛2D-A正定.科大研究生学位课程44 SORSOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(B)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.