第五章方程组的迭代法课件.ppt

1、第五章解线性方程组的迭代法 实际问题经过简单的分析可以直接归结 为线性方程组，或者微分方程，后者可以转换为线性方程组。两种方法：直接法：中小型稠密矩阵 迭代法：大型稀疏矩阵5.1 Jacobi迭代法和Gauss-Seidel迭代法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111设线性方程组简记 AX=bn其中1112121222n1n2n1212A()X,nnijn nnTTnnaaaaaaaaaaxxxbbbbn将方程组AX=b，改写成便于迭代的形式 建立迭代格式 向量X(0)事先给定，称为初始解向量，用公式逐步迭代求解的方法叫做迭代法

2、.如果由产生的序列 收敛，则称迭代法是收敛的，否则称为迭代法发散.XBXg(1)()(0,1,)kkkXBXg()1kkXn若将方程组改写为),2,1(1nibxanjijij),2,1()(11nixabaxnijjjijiiii0iia 1Jacobi迭代法n建立迭代格式其中(1)()11()(1,2,;0,1,2,)nkkiiijjjiij ixba xinka()()()()12(,)kkkkTnxxxXJacobi迭代法的矩阵表示n将方程组AX=b的系数A分解成 A=L+D+U其中D=diag(a11,a22,ann)，L和U分别是A的对角线下方元素和上方元素组成的严格下三角阵与严格

3、上三角阵.即000000000000000000211222112121nnnnnnaaaaaaaaaA()DXLU Xb()DLU Xb()DXLU Xb AXb11()XDLU XD b 迭代格式为：(1)1()1()kkXDLU XD b(1)1()1()kkXID A XD b对应的分量表示形式为：(1)()()11()(1,2,;0,1,2,)nkkkiiijjijiixxa xbinka另外一种矩阵形式是：的Jacobi迭代格式（三种）123121322531272xxxxxxx 写出方程组122130207系数矩阵为：022000000U000100200L 100030007D

4、(1)1()1(1)1()1()X(IDA)XDbkkkkXDLUXDb 迭 代 格 式 为：或 者Matlab计算过程如下：A=1-2 2;-1 3 0;2 0 7A=1 -2 2 -1 3 0 2 0 7 U=triu(A,1)U=0 -2 2 0 0 0 0 0 0 L=tril(A,-1)L=0 0 0 -1 0 0 2 0 0 D=diag(diag(A)D=1 0 0 0 3 0 0 0 7-inv(D)*(L+U)ans=0 2.000000000000000 -2.000000000000000 0.333333333333333 0 0 -0.285714285714286

5、0 0 b=5;-1;2;inv(D)*bans=5.000000000000000 -0.333333333333333 0.285714285714286 I=eye(3)I=1 0 0 0 1 0 0 0 1 I-inv(D)*Aans=0 2.000000000000000 -2.000000000000000 0.333333333333333 0 0 -0.285714285714286 0 0分量形式为:1232133125(22)1(1(0)31(2(20)7xxxxxxxxx (1)()()123(1)()()213(1)()()3125(22)1(1(0)31(2(20)7

6、kkkkkkkkkxxxxxxxxx Gauss-Seidel迭代法方程组改写为：()LD XUXb 11()()XLDUXLDb 即得迭代格式：(1)1()1()()kkXLDUXLDb Gauss-Seidel迭代法n迭代格式的分量形式：其中 1(1)(1)()111()(1,2,;0,1,2,)inkkkiiijjijjjj iiixba xa xinka()()()()12(,)kkkkTnxxxX的Gauss-Seidel迭代格式（两种）123121322531272xxxxxxx 写出方程组例n 分别用Jacobi迭代法与Gauss-Seidel迭代法求解方程组精确到小数点后四位，

7、并要求分别写出其迭代法的分量形式和矩阵形式.123123123202324812231530 xxxxxxxxx解n（1）用Jacobi迭代法，其迭代法的分量形式为(1)()()()()12323(1)()()()()21313(1)()()()()312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkkkkkkkkkkkkxxxxxxxxxxxxxxxk迭代法的矩阵形式为其中 (1)1()1()kkXID A XD b1100201 0 0202300.10.1510 1 0001810.12500

8、.12580 0 123 150.13330.2010015ID A 11241.2201121.58130215Db(1)()11(2)()22(1)()3300.10.151.20.12500.1251.50.13330.202.0kkkkkkxxxxxx 取初值X(0)=(0,0,0)，迭代可得(1)(2)(3)(4)(5)(6)(1.200 000,1.500 000,2.000 000),(0.750 000,1.100 000,2.140 000),(0.769 000,1.138750,2.120 000),(0.768125,1.138875,2.125 217),(0.767

9、 330,1.138332,2.125358),(0.767 363,1.138 414,2TTTTTXXXXXX(7).125356),(0.767 355,1.138 410,2.125368),TTX迭代7次，得近似值.n（2）用Gauss-Seidel迭代法，其迭代法的分量形式为(0.767 355,1.138 410,2.125368)TX(1)()()()()12323(1)(1)()(1)()21313(1)(1)(1)(1)(1)312121(2423)1.20.10.15201(12)1.50.1250.12581(3023)20.13330.215(0,1,2,)kkkkk

10、kkkkkkkkkkxxxxxxxxxxxxxxxk其迭代法的矩阵形式为其中(1)1()1()()kkXDLUXDLb 1110020200011()1800160823 1519112 4004015DL 11002002311()0001160800019112 400401500.10.1500.01250.106 2500.1583330.00125 DLU 110020241.211()0121.351608302.11191124004015DLb即 取初值X(0)=(0,0,0)，迭代可得(1)()11(1)()22(1)()3300.10.151.200.01250.10625

11、1.350 0.1583330.001252.11kkkkkkxxxxxx迭代5次，得近似值(1)(2)(3)(4)(5)(1.200 000,1.350 000,2.110 000),(0.748500,1.142 688,2.128738),(0.766 421,1.138105,2.125 432),(0.767 375,1.138399,2.125363),(0.767 356,1.138 410,2.125368).XXXXXTTTTT(0.767 356,1.138 410,2.12537)XTnQuestion:如何判断迭代出来的值和真实根很接近？向量和矩阵的模（范数）n为了研究

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

13、任一向量按某一确定的法则对应于一非负实数且满足非负性：，当且仅当时，奇次性：三角不等式：对任意都有，则称为向量 的范数。常见的向量范数121112221111(,.,)|(,1)|(|)(,2)()|(|)(,)|max|(,inf)Tnniiniinpppiiii nx xxxnorm xxnorm xornorm xxnorm x pxnorm xxxxxx 设向量nQuestion:如何判断迭代出的向量是真实解的精度较高的近似值？对 同 一 向 量 来 说，采 用 不 同 的 范 数，值 一 般 是 不 同 的，但 下 面 的 性 质 告 诉 我 们，有 限 维 向 量 的 模 是 相

14、互 等 价 的，所 以 在 讨 论 向 量 序 列 收 敛 时，可 采 用 任 意 一 种 范 数。向量范数性质R|,|,|nnm MmMRxxxx 性质 对中定义的任意两种范数则必存在两正数使得*limlim|0kkkkx xx x:|0,|0quetionxx由能否得出：？例已知12(1,2,3,4),xxxx求 矩阵范数,|,:1):|00|0;2)|;3)|,;4),|n nn nn nn nARAAAAkAkAkRABABA BRABABA BRAR定义 设任意若按某一确定的法则对应于一非负实数且满足非负性，当且仅当时，奇次性：，三角不等式：相容性：，则称为的一种范数。相容范数|,|

15、,|nn nxARRAxAxAx定义设分别为和的一种范数 如果则称该矩阵范数与此向量范数是相容的。算子范数（了解）0|1,|,|maxmax|,nn nnxxn nxRARRxAxAAxxR定理设并在上定义向量范数则为上的矩阵范数 且称其为算子范数。算子范数（了解）0|1|1)|max0|0,|00,0n nxAAAARRAAAAAxxx xxxxx证明(了解)：由向量范数的连续性知，在有界闭集上一定能达到最大值所以定义了到的一个对应法则。所以下面只要验证范数定义的四个条件。显然成立，若则，因为只有可能。算子范数（了解）|)|(|)(|max|)3|max|max|)2000 xxxxxxxx

16、xxxxxxxBABABABARAAAAAkAkkAkAnxxx于是，则由算子范数（了解）1|max|,|)(|max|)(|010 xxIxIIRBAABBAxxBABABAxxBAnnx则为单位矩阵中任何矩阵算子范数对推论。同理可证即有所以对常见的矩阵范数1111|maxnijj niAa 范数：2max2|()TAAA范数：11|max|niji njAa 范数：列范数行范数谱范数例题112221,|(1,2,)24:|max2|2|,|1|45|max2|1|,|2|46222181014241017810|0101723.466,1.534|23.4664.84pTTAApAAA A

17、IA AA 例设矩阵求解因为由解得，故4。nMatlab计算过程如下：2范数：norm(A)1范数：norm(A,1)无穷范数：norm(A,inf)矩阵的谱半径11 2,()max|(),iii n(i,.,n)AAAAAAA 定义设为矩阵 的特征值 则称为矩阵 的谱半径。矩阵 的谱半径不是 的一种范数但可能与 的任何一种范数有某种关系。例题12212421|02433,33()33AIAA求矩阵的谱半径。解：由得：特征值。所以求特征值命令eig(A)2,(1)()|,|;(2),()|1,0()maxn nTARAAAAAAAAAAAAAAAxxxxxxxx定理 设则这里为 的任意一种范数

18、若则。证明（）设为矩阵 的任一特征对，即则由于，故有由 的任意性，有。2max12(2)|()|()21,()33,|5,|6,24|4.844,()|TpAAAAAAAAAAAA因为，故。显然所以。例2120121,A011TA 矩阵求（A）（A）,（A A），解：A的特征值为：lm=eig(A)lm=1.500000000000000+1.658312395177701i 1.500000000000000-1.658312395177701i 1.000000000000000()A为：norm(lm,inf)ans=2.236067977499790AA 的特征值为：lm1=eig(A

19、*A)lm1=0.936075017171059 2.921124938072438 9.1428000447564982A为：sqrt(9.142800044756498)ans=3.023706342348162迭代法的收敛性n定理（迭代法的基本收敛定理）迭代过程 X(k+1)=BX(k)+g对于任意任意初始向量X(0)及右端向量g均收敛的充要条件是迭代矩阵B的谱半径(B)1,并且(B)愈小，收敛速度愈快.(B)由于求是一件很困难的事。因此我们给出一个充分条件。B表示B的任意一种范数定理（迭代法收敛的充分条件）若迭代法 X(k+1)=BX(k)+g的迭代矩阵B满足，B=q0则 是正定矩阵，

20、如果 既对称又是正定矩阵，则称A为对称正定矩阵n定理 若线性方程组的系数矩阵是对称正定矩阵，则用Jacobi迭代法和Gauss-Seidel迭代法都是收敛的。怎么判断矩阵是对称正定矩阵，直接从定义判断不方便，我们有如下几个结论：对称性很容易判定。下面是如何判断正定性。n矩阵的任意特征值都大于零，则是正定矩阵；n矩阵的所有顺序主子式都大于零，则是正定矩阵；n对角元素为正实数and（强对角占优矩阵or不可约对角占优矩阵），是正定矩阵。n顺序主子式：位于矩阵的前k行前k列交叉位置上的元素按照原来的相对位置构成的k阶子式。顺序主子式是行列式。Question:如何编程计算所有的顺序主子式？（让学生黑板练习）SOR方法nSOR方法n为了解决大型稀疏矩阵收敛速度较慢，引入SOR方法。回忆回忆Gauss-Seidel迭代迭代松弛迭代法是由Gauss-Seidel迭代演变而来，具体步骤如下：(1)()(1)(1)()(1)(1)(1)()02kkkkkkkkkxGaussSeidelxxxxxxxx（1）、对做迭代，得到，记做；（2）、对和做加权平均，得到。即（1-）为保证收敛，必须保证