数值分析线性代数方程组的迭代法精品文稿.ppt

《数值分析线性代数方程组的迭代法精品文稿.ppt》由会员分享，可在线阅读，更多相关《数值分析线性代数方程组的迭代法精品文稿.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值分析线性代数方程组的迭代法第1页，本讲稿共35页问题驱动：绗架设计问题驱动：绗架设计 绗架是能够承受重负载的轻量结构，在桥梁设计中，一个绗架是能够承受重负载的轻量结构，在桥梁设计中，一个个绗架和可旋转的支点连接起来，可以把力通过该绗架从一个个绗架和可旋转的支点连接起来，可以把力通过该绗架从一个节点传到另一个节点。如图节点传到另一个节点。如图7.1.1所示给出了一个所示给出了一个4个支点的绗个支点的绗架，架，和和都是支点。在左下角都是支点。在左下角是一个固定的点，是一个固定的点，绗架在右下角点绗架在右下角点可以水平移动量值。在支点可以水平移动量值。在支点施加施加10000N的力，绗架的受力情

2、况如图所示由的力，绗架的受力情况如图所示由 和和 给出。固定支点给出。固定支点同时受到水平方向的力同时受到水平方向的力 和垂直方向的力和垂直方向的力 的作用，但移动支点的作用，但移动支点只受到垂直方向的力只受到垂直方向的力 的作用的作用。第2页，本讲稿共35页图图7.1.1 绗架的受力分析图绗架的受力分析图第3页，本讲稿共35页 如果整个绗架处以平衡状态，每个支点的合力应为零向量，如果整个绗架处以平衡状态，每个支点的合力应为零向量，因此每个支点上力的水平分量和垂直分量之和都应该为零。由因此每个支点上力的水平分量和垂直分量之和都应该为零。由此可得到一个如表此可得到一个如表 7.1.1所示的线性方

3、程组，该方程组中的系数所示的线性方程组，该方程组中的系数矩阵中含有矩阵中含有46个零元素，而仅有个零元素，而仅有18个非零元素，通常把含有大个非零元素，通常把含有大量零元素的矩阵称为稀疏矩阵，由于使用直接法求解这类方程量零元素的矩阵称为稀疏矩阵，由于使用直接法求解这类方程组，会破坏系数矩阵的稀疏性，这种情况下一般采用迭代法求组，会破坏系数矩阵的稀疏性，这种情况下一般采用迭代法求解方程组。解方程组。表表7.1.1支点支点水平分量水平分量垂直分量垂直分量第4页，本讲稿共35页迭代法基础迭代法基础 问问问问 题题题题 在在实实际际应应用用中中遇遇到到的的系系数数矩矩阵阵多多为为大大型型稀稀疏疏矩矩阵

4、阵，如如用用求求解解线线性性方方程程组组的的直直接接法法求求解解，在在计计算算机机上上会会耗耗费费大大量量的的时时间间和和存存储储单单元元。在在许许多多应应用用问问题题中中使使用迭代法。用迭代法。第5页，本讲稿共35页思思路路将将 改写为改写为 等价形式等价形式 ，建立，建立迭代迭代 。从初值。从初值 出发，得到序出发，得到序列列 。研究内容：研究内容：如何建立迭代格式？如何建立迭代格式？收敛速度？收敛速度？向量序列的收敛条件？向量序列的收敛条件？误差估计？误差估计？一般迭代法一般迭代法第6页，本讲稿共35页迭代格式的构造迭代格式的构造把矩阵把矩阵A A分裂为分裂为 则则第7页，本讲稿共35页

5、将上式写为迭代过程将上式写为迭代过程这种迭代过程称为这种迭代过程称为逐次逼近法逐次逼近法，B B 称为称为迭代矩阵迭代矩阵。收敛性定义收敛性定义：若：若 称逐次逼近法称逐次逼近法收敛，收敛，否则，称逐次逼近法否则，称逐次逼近法不收敛或发散不收敛或发散。给定初值给定初值 就得到向量序列就得到向量序列第8页，本讲稿共35页问题问题：定理定理1 1 任意给定初始向量任意给定初始向量x x0 0，如果由逐次，如果由逐次逼近法产生的向量序列收敛于向量逼近法产生的向量序列收敛于向量x x*，那么，那么，x x*是方程组是方程组x=Bx+gx=Bx+g的解。的解。证明：证明：是否为方程组是否为方程组Ax=b

6、Ax=b的解？的解？第9页，本讲稿共35页迭代法的收敛条件迭代法的收敛条件定理定理 当当k 时，时，Bk 0 0 (B)1)1定理定理2 2 设线性方程组设线性方程组x=Bx+gx=Bx+g有惟一解，那么逐次逼有惟一解，那么逐次逼近法对任意初始向量近法对任意初始向量X X收敛的充分必要条件是迭代收敛的充分必要条件是迭代矩阵矩阵B B的谱半径的谱半径 (B B)11。证明：证明：因此，因此，第10页，本讲稿共35页注：要检验一个矩阵的谱半径小于注：要检验一个矩阵的谱半径小于1 1比较困难，比较困难，所以我们希望用别的办法判断收敛性。所以我们希望用别的办法判断收敛性。定理定理3 3 若逐次逼近法的

7、迭代矩阵满若逐次逼近法的迭代矩阵满 足足B1B1，那么逐次逼近法收敛。那么逐次逼近法收敛。RemarkRemark:因为矩阵范数因为矩阵范数 都可以都可以直接用矩阵的元素计算，因此直接用矩阵的元素计算，因此,用定理用定理3 3，很，很容易判别逐次逼近法的收敛性。容易判别逐次逼近法的收敛性。第11页，本讲稿共35页定理定理 4 （充分条件）（充分条件）若存在一个矩阵范数使得若存在一个矩阵范数使得|B|1,则则迭代收敛，且有下列误差估计：迭代收敛，且有下列误差估计：证明：证明：迭代法的误差估计迭代法的误差估计误差表达式误差表达式及收敛速度及收敛速度。停机准则。停机准则。第12页，本讲稿共35页第1

8、3页，本讲稿共35页（4 4.1）1 1雅克比（雅克比（JacobiJacobi）迭代法）迭代法设有设有n n阶方程组阶方程组几种常用的迭代格式几种常用的迭代格式第14页，本讲稿共35页若系数矩阵非奇异，且若系数矩阵非奇异，且 (i=1,2,n)，将方程组将方程组（4.1）改写成改写成第15页，本讲稿共35页然后写成迭代格式然后写成迭代格式（4.2）（4.2）式也可以简单地写为式也可以简单地写为（4.3）第16页，本讲稿共35页写成写成矩阵形式矩阵形式：A=LUDBJacobi 迭代阵迭代阵(4.4)第17页，本讲稿共35页第18页，本讲稿共35页第19页，本讲稿共35页 Algorithm:

9、Jacobi Iterative Method Solve .Given an initial approximation .Input:the number of equations and unknowns n;the matrix entries a ;the entries b;the initial approximation X0;tolerance TOL;maximum number of iterations Mmax.Output:approximate solution X or a message of failure.Step 1 Set k=1;Step 2 Whi

10、le(k Mmax)do steps 3-6Step 3 For i=1,n Set ;/*compute xk*/Step 4 If then Output(X);STOP;/*successful*/Step 5 For i=1,n Set X 0 =X ;/*update X0*/Step 6 Set k+;Step 7 Output(Maximum number of iterations exceeded);STOP./*unsuccessful*/What if aii=0?迭代过程中，迭代过程中，A 的元素的元素不改变，故可以不改变，故可以事先调整事先调整好好 A 使得使得aii

11、 0，否则否则 A不可逆不可逆。必须等必须等X(k)完全计算完全计算好了才能计算好了才能计算X(k+1)，因此，因此需要需要两组向量两组向量存储。存储。A bit wasteful,isnt it?第20页，本讲稿共35页 只存一组向量即可。只存一组向量即可。写成写成矩阵形式矩阵形式：BGauss-Seidel 迭代阵迭代阵2 2高斯高斯赛得尔赛得尔(Gauss-Seidel)(Gauss-Seidel)迭代法迭代法(4.5)(4.6)第21页，本讲稿共35页BG-SGauss-Seidel 迭代阵迭代阵其迭代格式的矩阵形式为其迭代格式的矩阵形式为事实上，这相当于对系数矩阵事实上，这相当于对系

12、数矩阵A A作的另一个分裂：作的另一个分裂：第22页，本讲稿共35页定理定理5 5 n n阶矩阵阶矩阵A A是按行是按行严格严格对角占优矩阵的对角占优矩阵的充分必要条件是充分必要条件是JacobiJacobi迭代法的迭代矩阵满足迭代法的迭代矩阵满足 BBJ J1.1.定理定理6 6 n n阶矩阵阶矩阵A A是按列是按列严格严格对角占优矩阵的对角占优矩阵的充分必要条件是充分必要条件是JacobiJacobi迭代法的迭代矩阵迭代法的迭代矩阵满足满足 B BJ J1 11.1.相关性质相关性质第23页，本讲稿共35页 JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Sei

13、del迭代法的收敛性迭代法的收敛性 定理定理 7 7 如果如果A A是按行是按行(列列)严格对角占优的严格对角占优的矩阵，那么矩阵，那么JacobiJacobi和和G GS S迭代法都收敛迭代法都收敛.定理定理 8 8 设设A A是不可约对角占优矩阵，是不可约对角占优矩阵，那么那么Jacobi迭代法与迭代法与GS迭代法都收敛迭代法都收敛.第24页，本讲稿共35页定理定理 9 9 若若A A是是n n阶正定矩阵，那么，阶正定矩阵，那么，G-SG-S迭代法迭代法收敛收敛.定理定理 10 10 设设A A是有正对角元的是有正对角元的n n阶对称矩阵，阶对称矩阵，那么那么JacobiJacobi迭代法

14、收敛的充分必要条件是迭代法收敛的充分必要条件是A A和和2D-A2D-A同为正定矩阵同为正定矩阵.第25页，本讲稿共35页注意的问题注意的问题（2）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的收敛迭代法的收敛 性没有必然的联系性没有必然的联系：即当即当Gauss-Seidel法收敛时，法收敛时，Jacobi法可能不收敛；法可能不收敛；而而Jacobi法收敛时，法收敛时，Gauss-Seidel法也可能不收敛。法也可能不收敛。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代迭代法的迭代 矩阵不同：矩阵不同：BJ=D-1(L+U),B G-S=(D-L)-1U

15、第26页，本讲稿共35页（3 3）JacobiJacobi迭代和迭代和Gauss-SeidelGauss-Seidel迭代的特征方程：迭代的特征方程：JacobiJacobi迭代迭代第27页，本讲稿共35页Gauss-SeidelGauss-Seidel迭代迭代第28页，本讲稿共35页举例举例用用Jacobi迭代法求解不收敛，但用迭代法求解不收敛，但用 Gauss-Seidel法收敛。法收敛。用用Jacobi迭代法求解收敛，迭代法求解收敛，但用但用 Gauss-Seidel法不收敛。法不收敛。BJ的特征值为的特征值为0，0，0，而而BGS的特征值为的特征值为 0，2，2第29页，本讲稿共35页

16、系数矩阵系数矩阵A A是正定矩阵，因此用是正定矩阵，因此用 Gauss-Seidel Gauss-Seidel法收敛法收敛.是正定矩阵，因此用是正定矩阵，因此用 Jacobi Jacobi迭代法收敛迭代法收敛利用定理利用定理7A A是有正对角元是有正对角元的的n n阶对称矩阵阶对称矩阵第30页，本讲稿共35页线性方程组的系数矩阵为线性方程组的系数矩阵为是严格对角占优的，所以是严格对角占优的，所以Jacobi和和Gauss-Seidel迭代格式迭代格式均收敛。均收敛。第31页，本讲稿共35页3 3超松驰法（超松驰法（Sequential Over-Relaxation)Sequential Ov

17、er-Relaxation)（1）迭代）迭代（2）加速）加速（4.7）矩阵形式：矩阵形式：即即第32页，本讲稿共35页超松弛法的收敛性超松弛法的收敛性定理定理1111 SOR SOR方法收敛的必要条件是方法收敛的必要条件是松驰因子松驰因子 20w定理定理1212 给定线性方程组给定线性方程组Ax=b,Ax=b,如果如果A A是对称正定是对称正定阵，且阵，且w（0 0，2 2），则），则SORSOR方法收敛。方法收敛。第33页，本讲稿共35页桥梁绗架问题的求解桥梁绗架问题的求解可用一个可用一个 的矩阵描述该方程组，其状态方程组可表示成的矩阵描述该方程组，其状态方程组可表示成 第34页，本讲稿共35页由由Gauss-Seidel迭代法可得迭代法可得由此可建立迭代格式由此可建立迭代格式取初始向量取初始向量 ，经，经Matlab求解经求解经 次迭代可得次迭代可得 第35页，本讲稿共35页