32Jacobi迭代法和Gauss-Seidel迭代法

3.2Jacobi迭代法和Gauss-Seidel迭代法本节主要内容Jacobi迭代法Gauss-Seidel迭代法先看下面一个简单的例子.考虑线性方程组例3.2.13.2.1Jacobi迭代法1231010911027,02108xxx其精确解为T*1,1,1.x【解】把线性方程组改写为121232310910272108xxxxxxx1221332191010117105101455xxxxxxx取=[0,0,0]，由上式可构造迭代公式如下0Tx进一步改写为1121213132191010117,0,1,2,105101455kkkkkkkxxxxxkxx1310.kkxx直到计算结果见下表：1kxT*1,1,1.x从计算结果看出，向量序列收敛到方程组的精确解kk000030.99500.98500.990010.90000.70000.800040.99850.99750.997020.97000.95000.940050.99980.99920.9995k1xk2xk3xk1xk2xk3x2kx3kx3kx1kx2kxJacobi迭代法.以上迭代法称为CarlGustavJacobi,1804--18511804.JacobiAbelJacobi卡尔雅可比（）是一位德国数学家.年生于波茨坦是历史上最伟大的数学家之一，他在数学方面的突出成就是和挪威数学家相互独立地奠定了椭圆函数论的基础.的工作还包括代数学、变分法、复变函数论、微分方程和数学史等方面.Jacobi在数值计算方面的主要贡献是提出求解线性方程组的迭代法以及求解矩阵的特征值和特征向量的方法等.卡尔.雅可比下面考虑一般的情形：(3.2.1)方程组的分量形式为0,iia因所以有,Axb其中A是n阶非奇异矩阵.且其主对角元素0(1,2,,)iiain0iia(1,2,,).in1,1,2,,.nijijjaxbin1,1,1,2,,.niijjjjiiiixaxbina(3.2.1)(3.2.2)其中从而得到Jacobi迭代法的分量形式：11,1,1,2,,.nkkiijjjjiiiixaxbina下面推导Jacobi迭代法的矩阵形式：把系数矩阵A分解成三部分：,ADLU1122diag(,,,),nnDaaa(3.2.4)(3.2.3)(3.2.5)(3.2.1)于是方程组改写为即211,11,212,100,00nnnnnnaLaaaaa121,112,121,0000nnnnnnaaaaaUa()DxLUxb11().xDLUxDb11()JDLUIDA任取向量，则Jacobi迭代法可写成如下的矩阵形式：111(),0,1,2,kkxDLUxDbk111(),BDLUIDAJfDb若记，则有1kkxJxf称矩阵J为Jacobi迭代法的迭代矩阵.(3.2.8)0x3.2.2算法与程序2.12.2.当时，执行步骤kN步骤2,1Nk精度最大迭代次数.令.算法3.1Jacobi迭代法说明：为简单起见，假定系数矩阵A非奇异，且，且假设Jacobi迭代法收敛.0(1,2,,)iiain步骤1输入系数矩阵A，右端向量b，以及初始向量0,x1,2,,对，计算in步骤2.111,1.nkkiijjijjiiixaxba111:,:1若，则算法停止，输出方程组的近似解x；否则，令.kkkkkxxxxkk步骤2.2步骤3输出信息“算法超出最大迭代次数！”，算法终止.算法3.1的Matlab程序Matlab程序如下：%Jacobi.mfunctionx=Jacobi(A,b,x0,eps,N)%功能：用Jacobi迭代法解n阶线性方程组Ax=bn=length(b);x=ones(n,1);k=0;whilek=Nfori=1:n%步骤2x(i)=(b(i)-A(i,[1:i-1,i+1:n])*x0([1:i-1,i+1:n]))/A(i,i);endk=k+1Ifnorm(x-x0,inf)eps，break；endx0=x;endifkNwarning(‘算法超出最大迭代次数！’)；elsedisp(['迭代次数=',num2str(k)])xend例3.2.2用Jacobi迭代法程序Jacobi.m求解线性方程组：12341012061111325.2110111031815xxxx编写M文件调用函数Jacobi.m，并运行【解】clcclearallformatlongA=[10,-1,2,0;-1,11,-1,3;2,-1,10,-1;0,3,-1,8];b=[6;25;-11;15];x0=[0;0;0;0];eps=1e-3;N=300;x=Jacobi(A,b,x0,eps,N);计算结果为迭代次数=10x=1.0001185986914151.999767947010035-0.9998281428744760.9997859784600503.2.3Gauss-Seidel迭代法Jacobi(3.2.2)将迭代法的迭代公式改写为11111,1,2,,.inkkkiijjijjijjiiixaxaxbina(3.2.9)11 (1)kkixixii注意到计算的第个分量时前面的个分量已经计算出来，如果计算第个分量时，前个分量使用最新的值，则得到111111 ,1,2,,.inkkkiijjijjijjiiixaxaxbina (3.2.10) GaussSeidel.上式即为迭代法的分量形式(1)iGaussSeidel下面推导迭代法的矩阵形式：(3.2.3),(3.2.1)据将方程组改写为(),DLUxb                       ,DxLxUxb即(3.2.10)根据式，取迭代公式为11,kkkDxLxUxb111                      ()(),kkxDLUxDLb即GaussSeidel.这就是迭代法的矩阵形式Gauss-Seidel迭代法的矩阵形式111()(),()若记，则有GDLUIDLAfDLb1,kkxGxfGaussSeidel.G迭代矩阵称为迭代法的Gauss-Seidel迭代法的迭代矩阵11()()GDLUIDLA例3.2.311211213113219,1010117,1051014,55kkkkkkkxxxxxxxT13010.0,0,03.2.kkxxx直至取初始向量，迭代结果见表GaussSeidel3.2.1用迭代法解例的线性方程组，其迭代公式为表3.2k1xk2xk3xk1xk2xk3xkk000030.995700.997850.9995710.900000.700000.8000040.999790.999890.9999820.970000.957000.9914051.000000.999991.00000T*53*3.2101,1,1.GaussSeidelJacobi.从表可知，其中是方程组的精确解对于本例子，迭代法比迭代法收敛得快xxx3.2.4Gauss-Seidel迭代法的步骤与程序GaussSeidel下面给出迭代法的具体步骤：Gauss-Seid算法e3.2l迭代法0(1,2,,)GaussSeidel.iiAain说明：为简单起见，假定系数矩阵非奇异，且，且假设迭代法收敛0,.0.步骤1输入系数矩阵，右端向量，以及初始向量，精度最大迭代次数令AbxNk,2.步骤2当时执行步骤2.1-2.kN1,2,,步骤2.1对，计算in111111:.inkkkiijjijjijjiiixaxaxba!.步骤3输出信息超出最大迭代次数，算法终止111:,:1步骤2.2若，则算法停止，输出方程组的近似解x；否则，令.kkkkkxxxxkk算法3.2的Matlab程序%Gauss_Seidel.mfunctionx=Gauss_SeidelA,b,x0,eps,N%GaussSeidel.nAxb功能：用迭代法解阶线性方程组nlengthb;xonesn,1;k0;whilekNfori1:nxiAi,1:i1*x1:i1Ai,i1:n*x0i1:nbi/Ai,i;...endkk1;ifnormxx0,infepsbreakend，；x0x;endifkNWarning('')算法超出最大迭代次数！；elsedisp(['=',num2str(k)])迭代次数endx例3.2.4GaussSeidelGauss_Seidel.m3.2.2.用迭代法程序求解例的线性方程组  MGauss_Seidel.m,.编写如下文件调用函数并运行解clcclearallformatlongA10,1,2,0;1,11,1,3;2,1,10,1;0,3,1,8;b6;25;11;15;x00;0;0;0;eps1e3;N300;xGauss_SeidelA,b,x0,eps,N;运行结果如下：=5x1.0000912802859952.0000213422464591.0000311471834450.999988103259647迭代次数