线性方程组的解法ppt课件

.,线性方程组的解法,解线性方程组的迭代法IterativeMethodsforLinearSystemsJacobi迭代和Gauss-Seidel迭代迭代法的矩阵表示MatrixformoftheIterativeMethods,.,线性方程组的解法在计算数学中占有极其重要的地位。线性方程组的解法大致分为迭代法与直接法两大类,雅可比(Jacobi)迭代法,举例说明雅可比迭代法的基本思路,例4.1,特点:系数矩阵主对角元均不为零,.,取迭代初值x1(0)=0，x2(0)=0，x3(0)=0,将方程改写成如下等价形式,据此建立迭代公式,.,x(0)000,x(1)0.77780.80000.8667,x(2)0.96300.96440.9778,x(3)0.99290.99350.9952,x(4)0.99870.99880.9991,x1*1.0000，x2*1.0000，x3*1.0000,准确解,可以看出，迭代每前进一步，结果就逼近准确解一步迭代过程收敛,.,矩阵形式:,以上这种迭代方法称雅可比(Jacobi)迭代法。基本思想：将方程组的求解问题转化为重复计算一组彼此独立的线性表达式。,.,(i=1,2,n;k=0,1,2,),(i=1,2,n),设有方程组,将第i个方程的第i个变量xi分离出来，据此建立分量形式的雅可比迭代公式,如果,.,用矩阵形式来表示雅可比迭代公式,设有方程组:AX=b其中A(aij)n为非奇异矩阵，X=(x1,x2,xn)T,b=(b1,b2,bn)T，唯一解为X*=(x1*,x2*,xn*)T将A分解为：AU+D+L其中,.,于是(U+D+L)X=b得XD(U+L)X+Db据此得矩阵形式的雅可比迭代公式X(k+1)D(U+L)X(k)+Db记BD(U+L)，fDb有B：迭代矩阵,任取X(0),迭代计算产生向量序列:,若,则迭代过程收敛。x*是方程组Ax=b的解,X(1),X(2),X(k),.,.,迭代法适用于解大型稀疏方程组,(万阶以上的方程组,系数矩阵中零元素占很大比例,而非零元按某种模式分布),背景:电路分析、边值问题的数值解和数学物理方程,问题:(1)如何构造迭代格式？(2)迭代格式是否收敛？(3)收敛速度如何？(4)如何进行误差估计？,.,高斯塞德尔Gauss-Seidel迭代法,Gauss-Seidel迭代法是通过对Jacobi迭代法稍加改进得到的。Jacobi迭代法的每一步迭代新值x(k+1)=x1(k+1),x2(k+1),xn(k+1)T都是用前一步的旧值x(k)=x1(k),x2(k),xn(k)T的全部分量计算出来的。那么在计算第i个分量xi(k+1)时，已经计算出x1(k+1),x2(k+1),xi-1(k+1)(i-1)个分量，这些分量新值没用在计算xi(k+1)上。将这些,.,(i=1,2,n),(i=1,2,n;k=0,1,2,),将这些分量利用起来，有可能得到一个收敛更快的迭代公式。具体作法：将分量形式的雅可比迭代公式右端前(i-1)个分量的上标为k换成k+1，即,分量形式的高斯-塞德尔迭代公式。,.,用矩阵形式来表示高斯-塞德尔迭代公式,DX(k+1)b-LX(k+1)-UX(k)即(D+L)X(k+1)-UX(k)+b如果(D+L)存在，则X(k+1)(D+L)UX(k)+(D+L)b记B(D+L)，f(D+L)b则,矩阵形式的高斯-塞德尔迭代公式。B：迭代矩阵,.,例,.,例,.,.,Jacobi迭代算法,A=9-1-1;-110-1;-1-115;b=7;8;13;x=0;0;0;er=1;k=0;whileer0.00005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=t;y(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-y(i),er);endx=y;xend,0.77780.80000.86670.96300.96440.97190.99290.99350.99520.99870.99880.99910.99980.99980.99981.00001.00001.00001.00001.00001.0000,.,Gauss-Seidel迭代算法,A=9-1-1;-110-1;-1-115;b=7;8;13;x=0;0;0;er=1;k=0;whileer0.00005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endxend,0.77780.87780.97700.98390.99610.99870.99940.99980.99991.00001.00001.00001.00001.00001.0000,.,从计算结果可以明显看出，Gauss-Seidel迭代法比Jacobi迭代法效果好。一般而言，Gauss-Seidel迭代法收敛速度比Jacobi迭代法快，但这两种迭代法的收敛范围并不完全重合，而只是部分相交，有的时候Jacobi迭代法可能比Gauss-Seidel迭代法收敛速度更快。甚至可以举出Jacobi迭代法收敛而Gauss-Seidel迭代法发散的例子。,.,Gauss-Seidel迭代法和Jacobi迭代法的异同：Jacobi迭代法：公式简单，每次只需做矩阵和向量的一次乘法；特别适合于并行计算；不足之处：需存放X(k)和X(k+1)两个存储空间。Gauss-Seidel迭代法：只需一个向量存储空间，一旦计算出了xj(k+1)立即存入xj(k)的位置，可节约一套存储单元；有时起到加速收敛的作用。是一种典型的串行算法，每次迭代中必须依次计算解的各个分量。,.,超松驰(SOR)迭代法,超松驰迭代法是迭代方法的一种加速方法，其计算公式简单，但需要选择合适的松驰因子，以保证迭代过程有较快的收敛速度。设有方程组AX=b其中A(aij)n为非奇异矩阵，X=(x1,x2,xn)T,b=(b1,b2,bn)T，记X(k)为第k步迭代近似值，则r(k)=bAX(k）表示近似解X(k)的残余误差，引进如下形式的加速迭代公式,.,X(k+1)X(k)+w(bAX)w称作松驰因子。其分量形式为选择适当的松驰因子，可期望获得较快的收敛速度。如果在计算分量xi(k+1)时，考虑利用已经计算出来的分量x1(k+1),x2(k+1),xi-1(k+1)，又可得到一个新的迭代公式特别当aii0时，将上面迭代公式应用于方程组,(i=1,2,n),.,由此得下列超松驰(SOR)迭代公式,(i=1,2,n;k=0,1,2,3,),当w1时，称超松驰法；当w1时，称低松驰法；当w1时，就是Gauss-Seidel迭代公式。所以超松驰(SOR)迭代法可以看成是Gauss-Seidel迭代法的加速，而Gauss-Seidel迭代法是超松驰方法的特例。,.,定理4.8若A是对称正定矩阵,则当0w2时SOR迭代法解方程组Ax=b是收敛的,定理4.9若A是严格对角占优矩阵,则当0w0.0005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(1-w)*t+w*(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endendk,k=10 x=1.19991.39991.5999,=1.2,只需k=6,.,块迭代法简介设ARnn,xRn,bRn将方程组Ax=b中系数矩阵A分块,其中,AiiRnini,AijRninj,xiRni,biRni,.,将A分解,A=DBLBUB,Jacobi块迭代DBx(k+1)=(LB+UB)x(k)+b,i=1,2,r,(2)Gauss-Seidel块迭代DBx(k+1)=LBx(k+1)+UBx(k)+b,i=1,2,r,.,迭代法的收敛性Convergenceofiterativemethod迭代矩阵谱半径Spectralradius对角占优矩阵diagonallydominantmatrix,.,原始方程:Ax=b,迭代格式:x(k+1)=Bx(k)+f,定理4.1(迭代法基本定理)迭代法x(k+1)=Bx(k)+f收敛的充要条件是(B)1,迭代法有着算法简单，程序设计容易以及可节省计算机存贮单元等优点。但是迭代法也存在着收敛性和收敛速度等方面的问题。因此弄清楚迭代法在什么样的条件下收敛是至关重要的。,.,证对任何n阶矩阵B都存在非奇矩阵P使B=P1JP其中,J为B的Jordan标准型,其中,Ji为Jordan块,其中,i是矩阵B的特征值,由B=P1JP,.,Bk=(P1JP)(P1JP)(P1JP)=P1JkP,迭代法x(k+1)=Bx(k)+f收敛,(i=1,2,r),.,例线性方程组Ax=b,分别取系数矩阵为,试分析Jacobi迭代法和Seidel迭代法的敛散性,(1),.,(2)A2=2,-1,1;1,1,1;1,1,-2,.,两种迭代法之间没有直接联系对矩阵A1,求A1x=b的Jacobi迭代法收敛,而Gauss-Seidel迭代法发散;对矩阵A2,求A2x=b的Jacobi迭代法发散,而Gauss-Seidel迭代法收敛.,.,证由(k)=B(k-1),得|(k)|B|(k-1)|(k=1,2,3,),所以,定理4.2(迭代收敛的充分条件)设有迭代公式x(k+1)=Bx(k)+f，如果|B|1,则对任意初始向量x(0)和任意f，迭代公式收敛。,|(k)|B|k|(0)|,|B|1,.,定义4.1A=(aij)nn,如果则称A为严格对角占优阵.,例4.1,.,定理4.3若Ax=b的系数矩阵A是严格对角占优矩阵,则Ja