计算方法3_线性方程组迭代解法

第3章线性方程组迭代解法Iterative11TechniquesforSolvingLinearSystems,(2.1),直接法是通过有限步运算后得到线性方程组的解，解线性方程组还有另一种解法，称为迭代法迭代法：不是用有限步运算求精确解，通过迭代产生近似解逼近精确解基本思想是将线性方程组AXB化为XBX+F,再由此构造一个向量序列X(k)X(k+1)=BX(k)+F若X(k)收敛在某个极限向量X*，则可得X*就是(2.1)式的准确解,线性方程组的迭代法主要有Jocobi迭代法、GaussSeidel迭代法和超松弛(SOR)迭代法Jacobi迭代和Seidel迭代由于收敛速度较慢，已经越来越不适应当前信息时代人们对计算速度和精度的要求，所以在实际应用中使用的并不多。但是，他们体现了迭代法的最基本的思想，是学习其它迭代法的基础,如何构造迭代序列X(n)?X(n)在什么条件下收敛?收敛速率如何?误差估计.,若在求解过程中X(k)X*(k)，由X(k+1)=(X(k)产生的迭代X(k)向X*的逼近，在数次迭代求解之后，由于机器跳动产生的X(k)值误差或是有效数字产生的舍入误差，都会在第k+1次迭代计算中自动弥补过来或逐步纠正过来。因此，在迭代求解过程中产生的各种误差是可以忽略的，即迭代求解无累积误差，实际上，X(k)只是解的一个近似，机器的舍入误差并不改变它的性质。,迭代过程中经常要遇到向量范数，矩阵范数以及序列极限的概念。,3.1向量和矩阵的范数NormsofVectorsandMatrices,数值分析中,经常要用向量和矩阵,为了应用的需要(误差分析),引入衡量向量和矩阵大小的度量范数.,对于实数xR,我们定义了绝对值,满足|x|0非负性|x|=|x|齐次性|x+y|x|+|y|三角不等式类似地,定义向量范数,Def3.1在实n维线性空间Rn中定义一个映射,它使任意XRn有一个非负实数与之对应,记为|X|,且该映射满足:正定性任意XRn,|X|0,ifandonlyifX=0时,|X|=0齐次性任意XRn,R,有|X|=|X|三角不等式任意X,YRn,有|X+Y|X|+|Y|则称该映射在Rn中定义了一个向量范数.,注:Rn中的范数不唯一.,常用的向量范数有三种:设X=(x1,x2,xn)TRn.则,注:(1)用范数的定义可验证上述皆为向量范数(2)p=1,2,|X|p即为|X|1,|X|2.(3)任意xRn:,定理3.2设|和|是Rn上任意两种范数，则存在正常数C1和C2，使得对一切XRn有C1|X|X|C2|X|,注:Rn中范数的等价性表明,虽范数值不同,但考虑到向量序列收敛性时,却有明显的一致性.,Def3.3Rn中X(x1,x2,xn)T和Y(y1,y2,yn)T则有,有解(x1,x2,x3)T(1,1,1)T，用Gauss消去法得到近似解,Def3.4Rn中的向量序列X(k),即X0,X1,XK,其中XK(x1(k),x2(k),xn(k)T.若对任意i（i=1,2,n）都有,注：向量序列收敛实际上是按分量收敛（数列收敛）利用向量范数，也可以说明向量序列收敛的概念。,定理3.5向量序列X(k)依分量收敛于X*的充要条件是,则向量X*(x1*,x2*,xn*)T称为X(k)的极限，记做,类似于向量范数，给出矩阵范数的定义。,Def3.6在线性空间Rnn中定义一个映射，使任意ARnn对应一个非负实数，记做|A|.如果该映射满足：,1.正定性：,（4.是矩阵乘法的需要，而1.2.3.为向量范数的推广。）,2.齐次性：,3.三角不等性：,4.相容性：,在Rnn中可定义多种范数。,有A=(aij)nnRnn称为frobenius范数,称为列范数,称为行范数,3.2Jacobi迭代法,(3.1),设有方程组,用矩阵表示,(3.1),其中A是系数矩阵，非奇异，X是解向量，B是右端项。,(3.2),(3.3),若令,则有B=D-1(D-A)=I-D-1A,G=D-1B方程(3.3)可记为X=BX+G,方程(3.3)可记为X=BX+G选取初始向量X0(x10,x20,xn0)T，代入方程(3.3)右端，可得到一个新向量，记为X1(x11,x21,xn1)T，一直进行下去，迭代格式X(n+1)=BX(n)+Gn=0,1,2,以上过程产生向量序列X(k),若收敛于X*，则有X*=BX*+G(I-B)X*=G=D-1BAX*=B即X*是方程(3.1)的解,(3.4),Jacobi迭代公式,唯一解X(1,2,-1,1)T,(3.5),简单迭代法用X(k)计算X(k+1)时,需要同时保留X(k)和X(k+1)。为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去,迭代格式为,这样所得的迭代法就称为Gauss-Seidel迭代法，也称为“异步迭代法”，简称为GS迭代法。,若令,则(3.5)式可写成X(k+1)=LX(k+1)+UX(k)+Gk=0,1,2,也可记为X(k+1)=(I-L)-1UX(k)+(I-L)-1G称(I-L)-1U为Seidel迭代法的迭代矩阵,(3.6),(3.7),例3.4用Seidel迭代法求解方程组,解：,取初始向量,要求,时迭代终止。,Seidel迭代格式为,计算结果可列表如下,注意：未必Seidel方法一定比Jacobi方法好。,3.3收敛性和误差估计,设nn阶矩阵A的特征值为i(i=1,2,3n),则称,为矩阵A的谱半径。,例：用GS迭代法求解例3.3,相关程序设计原始数据（A,b)可用一个二维数组存储，也可将A用一个二维数组，b用一个一维数组分别存储，存储需要一个一维数组。程序中应方便地对迭代方法和终止条件的选择以及对初始向量和值的设置。在迭代过程中，为反映迭代情况，可设置一些中间数据的输出，如迭带次数，迭代向量，迭代残向量等。当然不需要每迭代一次都作输出，这可作为收敛情况或不收敛情况的分析。作为不收敛的判定，可设置一个大的整数，当迭代次数超过该数时作为不收敛处理。GS迭代法的计算公式为：,请给出用C语言或其他语言求解下面方程组的程序及结果：,方法优缺点讨论由以上例题的求解过程可明显看出GS迭代法的收敛速度比简单迭代法快，但对于任意给定的一个方程组分别用简单迭代法和GS迭代法求解时，两种迭代法可能都收敛，也可能都不收敛。也有可能是GS迭代法收敛而J迭代法不收敛。但亦有相反情况，即简单迭代法收敛而GS迭代法不收敛。而且交换方程组中的方程和未知数的次序都会影响GS迭代法的计算结果，但这种交换对简单迭代法是没有影响的。,3.4松弛法,当使用Jacobi迭代法或Seidel迭代法解线性方程组时，可能会出现收敛极慢的情况，为了提高迭代收敛速度，我们再给出时SOR法，此方法又称为超松弛法（SuccessiveOverRelaxationMethod），它具有提高迭代收敛速度的功能。SOR法由Seidel迭代法演变而来，其基本思想是利用原迭代的第次迭代值及由产生的下一步Seidel迭代值的加权平均构成新的迭代格式。,松弛法可认为是Seidel法的加速,Seidel法X(k+1)=LX(k+1)+UX(k)+Gk=0,1,2,令X=X(k+1)X(k)=LX(k+1)+UX(k)+GX(k)X(k+1)=X(k)X松弛法思想X(k+1)=X(k)X,松弛法X(k+1)=(1-)X(k)(LX(k+1)+UX(k)+G)k=0,1,2,其中，称为松弛因子，当1时叫超松弛，当1时叫低松弛,也可记为X(k+1)=(I-L)-1(1-)I+U)X(k)+(I-L)-1G称(I-L)-1(1-)I+U)为松弛法的迭代矩阵,(3.8),(3.9),(3.10),唯一解X(3,4,-5)T,Seidel法,SOR法=1.25,3.5迭代法的特点,方法简单，每次迭代都是简单的重复运算，易于编制程