线性方程组的解法.ppt

线性方程组的解法,解线性方程组的迭代法 Iterative Methods for Linear Systems Jacobi迭代和Gauss-Seidel迭代 迭代法的矩阵表示 Matrix form of the Iterative Methods,线性方程组的解法在计算数学中占有极其重要的地位。 线性方程组的解法大致分为迭代法与直接法两大类,雅可比(Jacobi)迭代法,举例说明雅可比迭代法的基本思路,例4.1,特点:系数矩阵主对角元均不为零,取迭代初值x1(0) =0， x2(0) =0， x3(0) =0,将方程改写成如下等价形式,据此建立迭代公式,x(0) 0 0 0,x(1) 0.7778 0.8000 0.8667,x(2) 0.9630 0.9644 0.9778,x(3) 0.9929 0.9935 0.9952,x(4) 0.9987 0.9988 0.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 得 X D (U+L)X +Db 据此得矩阵形式的雅可比迭代公式 X(k+1)D(U+L)X(k) +Db 记 BD (U+L)， f Db 有 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;-1 10 -1;-1 -1 15; b=7;8;13;x=0;0;0; er=1;k=0; while er0.00005 er=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+A(i,j)*x(j); end x(i)=t; y(i)=(b(i)-s)/A(i,i); er=max(abs(x(i)-y(i),er); end x=y;x end,0.7778 0.8000 0.8667 0.9630 0.9644 0.9719 0.9929 0.9935 0.9952 0.9987 0.9988 0.9991 0.9998 0.9998 0.9998 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000,Gauss-Seidel迭代算法,A=9 -1 -1;-1 10 -1;-1 -1 15; b=7;8;13;x=0;0;0; er=1;k=0; while er0.00005 er=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+A(i,j)*x(j); end x(i)=(b(i)-s)/A(i,i); er=max(abs(x(i)-t),er); end x end,0.7778 0.8778 0.9770 0.9839 0.9961 0.9987 0.9994 0.9998 0.9999 1.0000 1.0000 1.0000 1.0000 1.0000 1.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) = b AX(k） 表示近似解X(k)的残余误差，引进如下形式的加速迭代公式,X(k+1) X(k)+w(b AX) 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是严格对角占优矩阵,则当0w1时SOR迭代法解方程组 Ax = b 是收敛的,例4.3 用SOR方法解方程组(w=1.4),w=input(input: w:=); A=2 -1 0;-1 2 -1;0 -1 2; b=1;0;1.8; x=1;1;1; er=1;k=0; while er0.0005 er=0;k=k+1; for i=1:3 s=0;t=x(i);x(i)=0; for j=1:3 s=s+A(i,j)*x(j); end x(i)=(1-w)*t+w*(b(i)-s)/A(i,i); er=max(abs(x(i)-t),er); end end k,k=10 x= 1.1999 1.3999 1.5999,=1.2,只需k=6,块迭代法简介 设 ARnn, xRn, bRn 将方程组A x = b中系数矩阵A分块,其中, AiiRnini, AijRninj , xiRni, biRni,将A分解, A = DB LB UB,Jacobi块迭代 DB x(k+1) = (LB + UB)x(k) + b,i=1,2, r,(2)Gauss-Seidel块迭代 DB x(k+1) = LB x(k+1)+ UBx(k) + b,i=1,2, r,迭代法的收敛性 Convergence of iterative method 迭代矩阵谱半径 Spectral radius 对角占优矩阵 diagonally dominant matrix,原始方程: Ax = b,迭代格式: x(k+1) = Bx(k) + f,定理4.1(迭代法基本定理) 迭代法 x(k+1) = Bx(k) + f收敛的充要条件是 (B) 1,迭代法有着算法简单，程序设计容易以及可节省计算机存贮单元等优点。但是迭代法也存在着收敛性和收敛速度等方面的问题。因此弄清楚迭代法在什么样的条件下收敛是至关重要的。,证 对任何 n 阶矩阵B都存在非奇矩阵P使 B = P 1 J P 其中, J 为B的 Jordan 标准型,其中, Ji 为Jordan块,其中,i 是矩阵B的特征值, 由 B = P 1 J P,B k = (P 1 J P) (P 1 J P) (P 1 J P)= P 1 J k P,迭代法 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.1 A=(aij)nn, 如果 则称A为严格对角占优阵.,例4.1,定理4.3 若A