线性方程组的解法解线性方程组的迭代法 Iterative Methods for Linear SystemsJacobi迭代和Gauss-Seidel迭代迭代法的矩阵表示 Matrix form of the Iterative Methods线性方程组的解法在计算数学中占有极其 重要的地位。 线性方程组的解法大致分为迭代法与直接 法两大类雅可比(Jacobi)迭代法举例说明雅可比迭代法的基本思路例4.1特点:系数矩阵主 对角元均不为零取迭代初值x1(0) =0， x2(0) =0， x3(0) =0将方程改写成如下等价形式据此建立迭代公式x(0)000x(1) 0.77780.80000.8667x(2)0.96300.96440.9778x(3)0.99290.99350.9952x(4) 0.99870.99880.9991x1* 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：迭代矩阵( k=0,1,2, )X(k+1)= BX(k) + f任取 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则( k=0,1,2,)X(k+1)= BX(k) + f矩阵形式的高斯-塞德尔迭代公式。 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.00005er=0;k=k+1;for i=1:3s=0;t=x(i);x(i)=0;for j=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;x end0.7778 0.8000 0.86670.9630 0.9644 0.97190.9929 0.9935 0.99520.9987 0.9988 0.99910.9998 0.9998 0.99981.0000 1.0000 1.00001.0000 1.0000 1.0000Gauss-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.00005er=0;k=k+1;for i=1:3s=0;t=x(i);x(i)=0;for j=1:3s=s+A(i,j)*x(j);endx(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endx end0.7778 0.8778 0.97700.9839 0.9961 0.99870.9994 0.9998 0.99991.0000 1.0000 1.00001.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时，称超松驰法；当w0.0005er=0;k=k+1;for i=1:3s=0;t=x(i);x(i)=0;for j=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);end end kk=10 x= 1.1999 1.39991.5999 =1.2,只需k=6块迭代法简介设 ARnn, xRn, bRn将方程组A x = b中系数矩阵A分块其中, AiiRnini, AijRninj , xiRni, biRni将A分解, A = DB LB UB (1)Jacobi块迭代 (2) DB x(k+1) = (LB + UB)x(k) + bi=1,2, r(2)Gauss-Seidel块迭代DB x(k+1) = LB x(k+1)+ UBx(k) + bi=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) (i = 1, 2, r)(i = 1, 2, r)谱半径 (B) |-1| + |-1|10 |-1| + |-1|15 |-1| + |-1|a11| |a12| + |a13|a22| |a21| + |a23|a33| |a31| + |a32|定理4.3 若Ax=b的系数矩阵A是严格对角占优 矩阵,则Jacobi迭代和Seidel迭代均收敛证 由于矩阵A严格对角占优由A矩阵构造Jacobi迭代矩阵BJ = D-1(D A)第i行绝对值求和所以例4.2 试对下列方程组建立收敛的迭代公式解 通过观察可发现这个方程组的系数矩阵不是对 角占优的。但经行交换后可得下列等价形式此等价形式的系数矩阵是严格对角占优阵，据此建 立的雅可比迭代公式和高斯塞德尔迭代公式收敛 。收敛速度：称R(B)=-ln(B) 为迭代法的渐 进收敛速度简称收敛速度。