1、线性方程组的解法线性方程组的解法线性方程组的解法在计算数学中占有极其线性方程组的解法在计算数学中占有极其重要的地位。重要的地位。线性方程组的解法大致分为线性方程组的解法大致分为迭代法迭代法与与直接直接法法两大类两大类雅可比雅可比(Jacobi)迭代法迭代法举例说明雅可比迭代法的基本思路举例说明雅可比迭代法的基本思路 131581079321321321xxxxxxxxx例例4.1特点特点:系数矩阵主系数矩阵主对角元均不为零对角元均不为零第1页/共39页 15/)13(10/)8(9/)7(213312321xxxxxxxxx取迭代初值取迭代初值x1(0)=0，x2(0)=0，x3(0)=0将方
2、程改写成如下等价形式将方程改写成如下等价形式据此建立迭代公式据此建立迭代公式 15/)13(10/)8(9/)7()()()1()()()1()()()1(213312321kkkkkkkkkxxxxxxxxx第2页/共39页 x(0)0 0 0 x(1)0.7778 0.8000 0.8667 x(2)0.96300.96440.9778 x(3)0.99290.99350.9952 x(4)0.99870.99880.9991x1*1.0000，x2*1.0000，x3*1.0000准确解准确解可以看出，迭代每前进一步，结果就逼近准确解一步可以看出，迭代每前进一步，结果就逼近准确解一步 迭
3、代过程收敛迭代过程收敛第3页/共39页矩阵形式矩阵形式:15/1310/89/7015/115/110/1010/19/19/10)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxxfBxx)()1(kk以上这种迭代方法称以上这种迭代方法称雅可比雅可比(Jacobi)迭代法。迭代法。基本思想：基本思想：将方程组的求解问题转化为重复将方程组的求解问题转化为重复计算一组彼此独立的线性表达式。计算一组彼此独立的线性表达式。第4页/共39页 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111(i=1,2,n;k=0,1,2,)nijkj
4、ijijkjijiiikixaxabax1)(11)()1(1injjijbxa 1(i=1,2,n)设有方程组设有方程组将第将第i个方程的第个方程的第i个变量个变量xi分离出来，据此建立分量形式分离出来，据此建立分量形式的的雅可比迭代公式雅可比迭代公式如果如果迭代发散迭代发散否则否则迭代收敛迭代收敛*)(limikikxx 第5页/共39页用矩阵形式来表示雅可比迭代公式用矩阵形式来表示雅可比迭代公式设有方程组设有方程组:AX=b 其中其中A(aij)n为非奇异矩阵，为非奇异矩阵，X=(x1,x2,xn)T,b=(b1,b2,bn)T，唯一解为，唯一解为X*=(x1*,x2*,xn*)T将将A
5、分解为：分解为：AU+D+L其中其中 0000U2112nnaaa nnaaa00D2211 0000L2121nnaaa第6页/共39页于是于是 (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),迭代计算产生向量序列迭代计算产生向量序列:若若*lim)(xxkk 则迭代过程收敛。则迭代过程收敛。x*是方程组是方程组 Ax=b 的解的解X(1),X(2),X(k),第7页/共
6、39页第8页/共39页迭代法适用于解迭代法适用于解大型稀疏方程组大型稀疏方程组(万阶以上的方程组万阶以上的方程组,系数矩阵中零元素占很系数矩阵中零元素占很大比例大比例,而非零元按某种模式分布而非零元按某种模式分布)背景背景:电路分析、边值问题的数值解和数学物电路分析、边值问题的数值解和数学物理方程理方程问题问题:(1)如何构造迭代格式？如何构造迭代格式？(2)迭代格式是否收敛？迭代格式是否收敛？(3)收敛速度如何？收敛速度如何？(4)如何进行误差估计？如何进行误差估计？第9页/共39页高斯塞德尔高斯塞德尔Gauss-Seidel迭代法迭代法Gauss-Seidel迭代法是通过对迭代法是通过对J
7、acobi迭代法稍加迭代法稍加改进得到的。改进得到的。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)上。将这上。将这些些第10页/共39页injjijbxa 1(i=1,2,n)n
8、ijkjijijkjijiiikixaxabax1)(11)1()1(1(i=1,2,n;k=0,1,2,)将这些分量利用起来，有可能得到一个收敛更将这些分量利用起来，有可能得到一个收敛更快的迭代公式。快的迭代公式。具体作法：将分量形式的雅可比迭代公式右端具体作法：将分量形式的雅可比迭代公式右端前前(i-1)个分量的上标为个分量的上标为k换成换成k+1，即，即分量形式的分量形式的高斯高斯-塞德尔迭代公式塞德尔迭代公式。第11页/共39页用矩阵形式来表示高斯用矩阵形式来表示高斯-塞德尔迭代公式塞德尔迭代公式DX(k+1)b-LX(k+1)-UX(k)即即 (D+L)X(k+1)-UX(k)+b如
9、果如果(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：迭代矩阵迭代矩阵第12页/共39页例例 131581079321321321xxxxxxxxx15/)13()(2)(1)1(3kkkxxx 15/1310/89/7015/115/110/1010/19/19/10)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxx9/)7()(3)(2)1(1kkkxxx 10/)8()(3)(1)1(2kkkxx
10、x 15/)13(10/)8(9/)7(213312321xxxxxxxxx 000)0(3)0(2)0(1xxx第13页/共39页例例 131581079321321321xxxxxxxxx15/)13()1(2)1(1)1(3 kkkxxx 15/1310/89/700010/1009/19/10115/115/10110/1001)(3)(2)(1)1(3)1(2)1(1kkkkkkxxxxxx9/)7()(3)(2)1(1kkkxxx 10/)8()(3)1(1)1(2kkkxxx 15/)13(10/)8(9/)7(213312321xxxxxxxxx 000)0(3)0(2)0(1
11、xxx第14页/共39页 15/1310/89/7135/21350/109/190/109/19/1015/1310/89/700010/1009/19/10115/1150/110110/100115/1310/89/700010/1009/19/10115/115/10110/1001)(3)(2)(1)(3)(2)(1)(3)(2)(1)1(3)1(2)1(1kkkkkkkkkkkkxxxxxxxxxxxx第15页/共39页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
12、=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;xend 131581079321321321xxxxxxxxx0.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.0000
13、第16页/共39页Gauss-Seidel迭代算法迭代算法 131581079321321321xxxxxxxxxA=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 xend 0.7778 0.8778 0.9770 0.9839 0.9961 0.9987 0.9994 0.9998
14、 0.9999 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000第17页/共39页从计算结果可以明显看出，从计算结果可以明显看出，Gauss-Seidel迭迭代法比代法比Jacobi迭代法效果好。迭代法效果好。一般而言，一般而言，Gauss-Seidel迭代法收敛速度比迭代法收敛速度比Jacobi迭代法快，但这两种迭代法的收敛范围迭代法快，但这两种迭代法的收敛范围并不完全重合，而只是部分相交，有的时候并不完全重合，而只是部分相交，有的时候Jacobi迭代法可能比迭代法可能比Gauss-Seidel迭代法收迭代法收敛速度更快。甚至可以举出敛速度更快。甚至可以举出
15、Jacobi迭代法收敛迭代法收敛而而Gauss-Seidel迭代法发散的例子。迭代法发散的例子。第18页/共39页Gauss-Seidel迭代法和迭代法和Jacobi迭代法的异同：迭代法的异同：Jacobi迭代法：公式简单，每次只需做矩阵和向量迭代法：公式简单，每次只需做矩阵和向量的的 一次乘法；特别适合于并行计算；一次乘法；特别适合于并行计算；不足之处：需存放不足之处：需存放X(k)和和X(k+1)两个存储空间。两个存储空间。Gauss-Seidel迭代法：只需一个向量存储空间，一迭代法：只需一个向量存储空间，一旦计算出了旦计算出了xj(k+1)立即存入立即存入xj(k)的位置，可节约一套存
16、储单的位置，可节约一套存储单元元；有时起到加速收敛的作用。；有时起到加速收敛的作用。是一种典型的串行算法，每次迭代中必须依次计算解是一种典型的串行算法，每次迭代中必须依次计算解的各个分量。的各个分量。第19页/共39页超松驰超松驰(SOR)迭代法迭代法超松驰迭代法是迭代方法的一种加速方法，其计超松驰迭代法是迭代方法的一种加速方法，其计算公式算公式 简单，但需要选择合适的松驰因子，以保简单，但需要选择合适的松驰因子，以保证迭代过程有较快的收敛速度。证迭代过程有较快的收敛速度。设有方程组设有方程组 AX=b 其中其中A(aij)n为非奇异矩阵，为非奇异矩阵，X=(x1,x2,xn)T,b=(b1,
17、b2,bn)T，记，记X(k)为第为第k步迭代近似值，则步迭代近似值，则 r(k)=b AX(k）表示近似解表示近似解X(k)的残余误差，引进如下形式的加速迭的残余误差，引进如下形式的加速迭代公式代公式第20页/共39页 X(k+1)X(k)+w(b AX)w称作松驰因子。其分量形式为称作松驰因子。其分量形式为选择适当的松驰因子，可期望获得较快的收敛速选择适当的松驰因子，可期望获得较快的收敛速度。如果在计算分量度。如果在计算分量xi(k+1)时，考虑利用已经计算时，考虑利用已经计算出来的分量出来的分量x1(k+1),x2(k+1),xi-1(k+1)，又可得到一，又可得到一个新的迭代公式个新的
18、迭代公式特别当特别当aii0时，将上面迭代公式应用于方程组时，将上面迭代公式应用于方程组1)()()1(njkjijikikixabwxx(i=1,2,n)nijkjijijkjijikikixaxabwxx)(11)1()()1(iiinjjiiijabxaa 1第21页/共39页由此得下列由此得下列超松驰超松驰(SOR)迭代公式迭代公式)(11)1()()1(nijkjijijkjijiiikikixaxabaxx(i=1,2,n;k=0,1,2,3,)当当w1时，称超松驰法；当时，称超松驰法；当w1时，称低松时，称低松驰法；当驰法；当w1时，就是时，就是Gauss-Seidel迭代迭代公
19、式。公式。所以超松驰所以超松驰(SOR)迭代法可以看成是迭代法可以看成是Gauss-Seidel迭代法的加速，而迭代法的加速，而Gauss-Seidel迭代法是超松驰方法的特例。迭代法是超松驰方法的特例。第22页/共39页定理定理4.8 若若A是对称正定矩阵是对称正定矩阵,则当则当0w2时时SOR迭代法解方程组迭代法解方程组 Ax=b 是收敛的是收敛的定理定理4.9 若若A是严格对角占优矩阵是严格对角占优矩阵,则当则当0w0.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)*
20、t+w*(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endendkk=10 x=1.1999 1.3999 1.5999=1.2,只需只需k=6第24页/共39页 块迭代法简介块迭代法简介设设 ARnn,xRn,bRn将方程组将方程组A x=b中系数矩阵中系数矩阵A分块分块 rrrrrrrrbbbxxxAAAAAAAAA2121212222111211其中其中,AiiRnini,AijRninj,xiRni,biRni第25页/共39页将将A分解分解,A=DB LB UB(1)Jacobi块迭代块迭代 DB x(k+1)=(LB+UB)x(k)+b ijkji
21、jikiiixAbxA)()1(i=1,2,r(2)Gauss-Seidel块迭代块迭代 DB x(k+1)=LB x(k+1)+UBx(k)+b rijkjijijkjijikiiixAxAbxA1)(11)1()1(i=1,2,r第26页/共39页迭代法的收敛性迭代法的收敛性Convergence of iterative method迭代矩阵谱半径迭代矩阵谱半径Spectral radius对角占优矩阵对角占优矩阵diagonally dominant matrix第27页/共39页原始方程原始方程:Ax=b迭代格式迭代格式:x(k+1)=Bx(k)+f定理定理4.1(迭代法基本定理迭代
22、法基本定理)迭代法迭代法 x(k+1)=Bx(k)+f收敛的收敛的充要条件充要条件是是 (B)1迭代法有着算法简单，程序设计容易以及可节迭代法有着算法简单，程序设计容易以及可节省计算机存贮单元等优点。但是迭代法也存在省计算机存贮单元等优点。但是迭代法也存在着收敛性和收敛速度等方面的问题。因此弄清着收敛性和收敛速度等方面的问题。因此弄清楚迭代法在什么样的条件下收敛是至关重要的。楚迭代法在什么样的条件下收敛是至关重要的。第28页/共39页证证 对任何对任何 n 阶矩阵阶矩阵B都存在非奇矩阵都存在非奇矩阵P使使 B=P 1 J P其中其中,J 为为B的的 Jordan 标准型标准型nnrJJJJ 2
23、1iinniiiJ 11其中其中,Ji 为为Jordan块块其中其中,i 是矩阵是矩阵B的特征值的特征值,由由 B=P 1 J P第29页/共39页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收敛收敛 0Blim kk0Jlim kk0lim kik(i=1,2,r)1|i(i=1,2,r)1|max1 iri 谱半径谱半径 (B)1第30页/共39页1005-1.2604e)B(J 例例 线性方程组线性方程组 Ax=b,分别取系数矩阵为分别取系数矩阵为 122111221A1 211111112A2试分析试分析J
24、acobi 迭代法和迭代法和 Seidel 迭代法的敛散迭代法的敛散性性 022101220JB(1)第31页/共39页 200320220SB12)(SB(2)A2=2,-1,1;1,1,1;1,1,-2 02/12/11012/12/10JB11180.1)(JB 第32页/共39页 2/1002/12/102/12/10SB12/1)(SB 两种迭代法之间没有直接联系两种迭代法之间没有直接联系对矩阵对矩阵A1,求求A1x=b 的的Jacobi迭代法收敛迭代法收敛,而而Gauss-Seidel迭代法发散迭代法发散;对矩阵对矩阵A2,求求A2x=b 的的Jacobi迭代法发散迭代法发散,而而
25、Gauss-Seidel迭代法收敛迭代法收敛.第33页/共39页证证 由由(k)=B (k-1),得得|(k)|B|(k-1)|(k=1,2,3,)0lim)(kk 所以所以定理定理4.2(迭代收敛的充分条件迭代收敛的充分条件)设有迭代公式设有迭代公式 x(k+1)=Bx(k)+f，如果，如果|B|1,则对任意初始向则对任意初始向量量x(0)和任意和任意f，迭代公式收敛。，迭代公式收敛。|(k)|B|k|(0)|0|lim|lim)0()(kkkkB|B|-1|+|-1|10|-1|+|-1|15|-1|+|-1|a11|a12|+|a13|a22|a21|+|a23|a33|a31|+|a3
26、2|第35页/共39页定理定理4.3 若若Ax=b的系数矩阵的系数矩阵A是严格对角占优是严格对角占优矩阵矩阵,则则Jacobi迭代和迭代和Seidel迭代均收敛迭代均收敛证证 由于矩阵由于矩阵A严格对角占优严格对角占优由由A矩阵构造矩阵构造Jacobi迭代矩阵迭代矩阵BJ=D-1(D A)第第i行绝对值求和行绝对值求和 nijjijiiaa1|1所以所以1|1max|11 nijjijiiniJaaB1|11 nijjijiiaa nijjijiiaa1|第36页/共39页例例4.2 试对下列方程组建立收敛的迭代公式试对下列方程组建立收敛的迭代公式 12401122133311321321321xxxxxxxxx解解 通过观察可发现这个方程组的系数矩阵不是对通过观察可发现这个方程组的系数矩阵不是对角占优的。但经行交换后可得下列等价形式角占优的。但经行交换后可得下列等价形式 13331112401122321321321xxxxxxxxx此等价形式的系数矩阵是严格对角占优阵，据此此等价形式的系数矩阵是严格对角占优阵，据此建立的雅可比迭代公式和高斯塞德尔迭代公式建立的雅可比迭代公式和高斯塞德尔迭代公式收敛。收敛。第37页/共39页收敛速度：称收敛速度：称R(B)=-ln(B)为迭代法的渐为迭代法的渐进收敛速度简称收敛速度。进收敛速度简称收敛速度。第38页/共39页
