计算方法-解线性方程组的迭代法

第9次解线性方程组的迭代法计算方法(NumericalAnalysis)主要内容1.迭代法的基本思想2.雅可比（Jacobi）迭代法3.雅可比迭代法的矩阵表示4.高斯-塞德尔（Gauss-Seidel）迭代法5.Gauss—Seidel迭代法的矩阵表示6.Jacobi迭代与Gauss-Seidel迭代算法实现迭代法的基本思想•迭代法是求解线性方程组，尤其是具有大型稀疏矩阵的线性方程组的重要方法之一。•凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时却会发散。•一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。第六章解线性方程组的迭代法§6.1迭代法的基本思想a)将线性方程组转化为便于迭代的等价方程组若非奇异，，则线性方程组nnRAnRbbAxbAx1有唯一解，n),1,2,(ix(0)ib)对任选一组初始值，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。…dGxx步骤1：经过某变换构造出方程组(1)的一个等价同解方程组迭代法的基本步骤任务：设非奇异，，求解方程组nnRAnRbbAx(1)步骤2：建立迭代公式：0,1,...kd,Gxx(k)1)(k步骤3：选定初始向量,反复使用迭代式进行迭代，期望逼近精确解，直到满足精度要求为止。T(0)n(0)2(0)1(0)x,,x,xx…收敛定义：如果T(k)n(k)2(k)1x,,x,xT*n*2*1*x,,x,xx当k∞时，存在极限则称迭代法是收敛的，否则就是发散的。n1,2,...,i，xxlim*i(k)ik迭代法是收敛的意味着：……【注1】可以构造各种不同的迭代公式。k)0,1,(kdGxx(k)1)(kdGxx**收敛时，在迭代公式中令，则*x故是方程组bAx的解。【注2】并非所有的迭代公式都收敛…例1用迭代法求解线性方程组35x2x3x2x2121解：构造方程组的等价方程组34x2xx3xxx212211建立迭代公式：34x2xx3xxx(k)2(k)11)(k2(k)2(k)11)(k1迭代不收敛的例子0xx(0)2(0)1取：3,x3x(1)2(1)1迭代解离精确解1x1,x210xx(0)2(0)1进行迭代计算得：15,x15x(4)2(4)1越来越远。迭代不收敛。原因是迭代公式不正确。3,x3x(2)2(2)19,x9x(3)2(3)133,x33x(5)2(5)1Home34x2xx3xxx(k)2(k)11)(k2(k)2(k)11)(k1雅可比（Jacobi）迭代法§6.2雅可比（Jacobi）迭代法例2.利用迭代法求解方程组3612x3x6x33x11x4x202x3x8x321321321已知精确解：x*=(3,2,1)T§6.2.1雅可比迭代法算法构造解：以下列独特的方式分离出321，xx,x3x41x21x3x111x114x25x41x83x213312321右端不含x1右端不含x2右端不含x33x41x21x3x111x114x25x41x83x(k)2(k)11)(k3(k)3(k)11)(k2(k)3(k)21)(k1由此，建立迭代公式：取初始向量TT(0)3(0)2(0)1(0)(0,0,0))x,x,(xxn...,2,1,k),x,x,(x(k)3(k)2(k)1进行迭代,可以逐步得出一个近似解的序列：同学们，迭代两次当迭代到第10次有:TT(10)3(10)2(10)1(10))0.9998811.999874(3.000032,)x,x,(xx，结果表明，此迭代过程收敛于方程组的精确解x*=(3,2,1)T。当近似解能达到预先要求的精度，迭代终止，以最后得到的近似解作为线性方程组的解。3x3x25x(1)3(1)2(1)11x1126x823x(2)3(2)2(2)1176171x2245x2269x(3)3(3)2(3)1考察一般的方程组，将n元线性方程组nnnn2n21n12n2n2221211n1n212111bxaxaxabxaxaxabxaxaxa…………n,1,2,ibxain1jjij写成…若,分离出变量n),1,2,(i0,aiiix…n,1,2,i)xa(ba1xjnij1jijiiii…由此，得到如下的被称为解方程组的Jacobi迭代公式：n1,2,i)xa(ba1xnij1j(k)jijiii1)(ki…实际计算中，要用雅可比迭代法公式的分量形式:)bxaxaxa(a1x)bxaxaxa(a1x)bxaxaxa(a1xn(k)1n1nn(k)2n2(k)1n1nn1)(kn2(k)n2n(k)323(k)121221)(k21(k)n1n(k)313(k)212111)(k1(k=0,1,2,…)…………例3试用雅可比迭代法解线性方程组解：先构造雅可比迭代公式：12x-2xx1x-xx12x2xx(k)2(k)11)(k3(k)3(k)11)(k2(k)3(k)21)(k11x2x2x1xxx12x-2xx3213213211x3x-3x321精确解12x-2xx1x-xx12x2xx(k)2(k)11)(k3(k)3(k)11)(k2(k)3(k)21)(k10x0x0x(0)3(0)2(0)11x1x1x(1)3(1)2(1)13x1x1x(2)3(2)2(2)1--1x3x-3x(3)3(3)2(3)11x3x-3x(4)3(4)2(4)1结论：该迭代收敛到：1x3x-3x(*)3(*)2(*)1•问题：对于一个有解的线性方程组，其雅可比迭代是否一定收敛呢？•回答：Sorry,我现在也不知道。Home雅可比迭代法的矩阵表示§6.2.2雅可比迭代法的矩阵表示bAxn),1,2,0(iaii121311121232223132112100000000nnnnnnnnnnaaaaaaaaAaaaaaaa记作设方程组的系数矩阵A非奇异，且主对角元素，则可将A分裂成DLUA=D-L-U………………bAx则等价于即显然D可逆，于是有这样便得到一个迭代公式令则有fBxx(k)1)(k，k=0,1,2…称为雅可比迭代公式,B称为雅可比迭代矩阵。bU)x-L-(DbU)x(LDxbDU)x(LDx11bDU)x(LDx1(k)11)(kbDfU),(LDB110-aa-a-a-a-0a-a-a-a-0aaaB1)-n(nn2n12n23211n13121nn22110aa-aa-aa-aa-aa-0aa-aa-aa-aa-0nn1)-n(nnnn2nnn1222n22232221111n11131112nnn222111n21nn2211n211nn2211abababbbba1a1a1bbbaaafnnn222111(k)n(k)2(k)1nn1)-n(nnnn2nnn1222n22232221111n111311121)(kn1)(k21)(k1abababxxx0aa-aa-aa-aa-aa-0aa-aa-aa-aa-0xxx由矩阵表达的雅可比迭代公式如下：例4.写出如下方程组的雅可比迭代公式的矩阵形式3612x3x6x33x11x4x202x3x8x321321321363320xxx12361-11423-8321解：先将方程组表达为矩阵形式：bDU)x(LDx1(k)11)(kfBxx(k)1)(k0a3-a6-a10a4-a2-a30B333322221111363320xxx12361-11423-8321041-21-1110114-41-830bDfU),(LDB11332536332012100011100081bDf13325xxx041-21-1110114-41-830xxx(k)3(k)2(k)11)(k31)(k21)(k1Home高斯-塞德尔（Gauss-Seidel）迭代法§6.3高斯-塞德尔（Gauss-Seidel）迭代法§6.3.1高斯-塞德尔迭代法的基本思想•在Jacobi迭代法中，每次迭代只用到前一次的迭代值。现在修改Jacobi迭代法，使得若每次迭代充分利用当前最新的迭代值。1)(kix•在求时，使用用新分量：1)(k1i1)(k21)(k1x,,x,x…代替旧分量就得到高斯-赛德尔迭代法。(k)1i(k)2(k)1x,,x,x…已经计算出的分量，马上就使用)xaxa(ba1x1i1jn1ij(k)jij1)(kjijiii1)(ki(i=1,2,…,nk=0,1,2,…)高斯-塞德尔迭代法格式为：旧分量新分量)bxaxaxaxa(a1x)bxaxaxaxa(a1x)bxaxaxaxa(a1x)bxaxaxaxa(a1xn1)(k1n1nn1)(k3n31)(k2n21)(k1n1nn1)(kn2(k)n2n(k)4241)(k2221)(k121331)(k32(k)n2n(k)424(k)3231)(k121221)(k21(k)n1n(k)414(k)313(k)212111)(k1高斯-塞德尔迭代法分量形式格式为：……………3612x3x6x33x11x4x202x3x8x321321321例5.使用高斯-塞德尔迭代法解方程组解：确定迭代公式：)/123x6x-(36x)/11x4x-(33x)/82x3x(20x1)(k21)(k11)(k3(k)31)(k11)(k2(k)3(k)21)(k1同学们,计算：k=0,k=1,k=2取初值{0,0,0}当