线性方程组的简单迭代法.pptx

《线性方程组的简单迭代法.pptx》由会员分享，可在线阅读，更多相关《线性方程组的简单迭代法.pptx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性方程组的简单迭代法线性方程组的简单迭代法n n引言引言3.1 3.1 简单迭代法简单迭代法 考虑线性方程组（1.1）其中 为非奇异矩阵，当 为低阶稠密矩阵时，第2章所讨论的选主元消去法是有效方法.但对于 的阶数 很大，零元素较多的大型稀疏矩阵大型稀疏矩阵方程组，利用迭代法求解则更为合适.迭代法通常都可利用迭代法通常都可利用 中有大量零元素的特点中有大量零元素的特点.第1页/共32页两个简单的例子两个简单的例子例例1 1 已知已知 ，任取，任取 ，则由，则由 例例2 2 已知方程已知方程 在在 附附近近有有根根.那么我们就能从那么我们就能从 开始，通过迭代公式开始，通过迭代公式 逐步

2、得到所要求的根逐步得到所要求的根.假定我们已会计算假定我们已会计算第2页/共32页 例例1 1求解方程组求解方程组 （1.2）记为 ,方程组的精确解是方程组的精确解是 .其中其中 现将现将(1.2)(1.2)改写为改写为 第3页/共32页（1.3）或写为或写为 ,其中其中 第4页/共32页 将这些值代入将这些值代入(1.3)(1.3)式右边式右边 (若若(1.3)(1.3)式为等式即求得式为等式即求得方程组的解，但一般不满足方程组的解，但一般不满足).).任取初始值，例如取任取初始值，例如取 再将 分量代入(1.3)式右边得到 ，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式迭

3、代公式)得到新的值 第5页/共32页（1.4）简写为 其中 表示迭代次数 迭代到第10次有 第6页/共32页 从此例看出，由迭代法产生的向量序列 逐步逼近方程组的精确解 .第7页/共32页迭代法的基本思想是构造一个向量序列X X(k)(k)，使其收敛到某个极限向量 X*，而X*就是 AX=b b 的准确解。问题：如何构造迭代序列？迭代序列在什么情况下收敛？第8页/共32页简单迭代法的迭代格式简单迭代法的迭代格式n阶线性代数方程组a11x1+a12x2+.+a1nxn=b1a21x1+a22x2+.+a2nxn=b2 an1x1+an2x2+.+annxn=bn若用矩阵和向量的记号来表示，可写成

4、 AX=b b第9页/共32页 设 ,并将 写为三部分 迭代矩阵迭代矩阵第10页/共32页易知，雅各布（Jacobi）迭代有A=D-L-UA=D-L-UL+U=D-AG G为迭代矩阵为迭代矩阵第11页/共32页第12页/共32页 的雅可比(Jacobi)迭代公式如下:研究雅可比迭代法的分量计算公式研究雅可比迭代法的分量计算公式.记 或 第13页/共32页于是，解 的雅可比迭代法的分量计算公式为 第14页/共32页方程组的迭代式的展开式如下：第15页/共32页第16页/共32页 由可知计算过程可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和计算一次矩阵和向量的乘法向量的乘法且计算过程

5、中原始矩阵矩阵A A始终不变.第17页/共32页例例1 1 用用J J法求解线性方程组法求解线性方程组方程组的精确解为方程组的精确解为方程组的精确解为方程组的精确解为x x x x*=(1,1,1)=(1,1,1)=(1,1,1)=(1,1,1)T T T T.解：解：第18页/共32页取初始向量取初始向量x x(0)(0)=(0,0,0)=(0,0,0)T T,迭代可得迭代可得计算结果列表如下:第19页/共32页k kx x1 1(k)(k)x x2 2(k)(k)x x3 3(k)(k)xx(k)(k)-x-x*0 0 0 01 1 1 12 2 2 23 3 3 34 4 4 45 5

6、5 56 6 6 67 7 7 70 01.41.41.111.110.9290.9290.99060.99061.011591.011591.0002511.0002510.99823640.99823640 00.50.51.201.201.0551.0550.96450.96450.99530.99531.0057951.0057951.00012551.00012550 01.41.41.111.110.9290.9290.99060.99061.011591.011591.0002511.0002510.99823640.99823641 10.50.50.20.20.0710.07

7、10.03550.03550.011590.011590.0057950.0057950.00176360.0017636可见可见,迭代迭代7次使得次使得迭代序列逐次迭代序列逐次收敛于方程组的解收敛于方程组的解,。第20页/共32页简单迭代法的算法如下：简单迭代法的算法如下：1.输入矩阵 A，右端项 b，维数 n，初始迭代向量 X(0),容许误差 e，容许最大迭代次数 N。2.置 k=1。3.对 i=1,2,n4.若 ，输出X，停机，否则转5。5.若 ，转3；否则输出失败信息，停机。第21页/共32页 对于任何由 变形得到的等价方程组 ，迭代法产生的向量序列 不一定都能逐步逼近方程组的解 .如

8、对方程组第22页/共32页n n一般迭代法收敛性的基本定理迭代法的收敛性迭代法的收敛性 设 其中 为非奇异矩阵，记 为精确解，于是 且设有等价的方程组（2.1）第23页/共32页 设有解 的迭代法 问题是：迭代矩阵 满足什么条件时，由迭代法产生的向量序列 收敛到 引进误差向量 由(2.1)式减(2.2)式得到误差向量的递推公式（2.2）第24页/共32页因此，研究迭代法(2.2)收敛性问题就是要研究迭代矩阵 满足什么条件时，有 设有矩阵序列 ,如果 个数列极限存在且有 则称 收敛于 ，记为 定义定义1第25页/共32页 定理定理1 1（2.3）(迭代法基本定理)设有方程组 及一阶定常迭代法（2

9、.4）对任意选取初始向量 ，矩阵 的谱半径 迭代法(2.4)收敛的充要条件是 所谓所谓“谱半径谱半径”，就是最大特征值（对于实数而言），就是最大特征值（对于实数而言）,如果是特征值是复数的话，谱半径就是特征值的最大模。如果是特征值是复数的话，谱半径就是特征值的最大模。第26页/共32页 推论推论设 ，其中 为非奇异矩阵且 非奇异，则 (1)解方程组的雅可比迭代法收敛的充要条件是 ，其中 定义定义2 2：若n阶矩阵A A=(aij)满足:则称矩阵A A是严格对角占优矩阵严格对角占优矩阵.定理定理2 2 设设A A是严格对角占优矩阵是严格对角占优矩阵,则解线性方程组则解线性方程组Ax=bAx=b的

10、的J J迭代迭代法收敛法收敛.第27页/共32页计算机实现程序计算机实现程序n n用雅各比迭代法下面线性方程组 第28页/共32页#include#include#include#include#define eps 1e-3#define eps 1e-3#define max 100#define max 100void Jacobi(float*a,int n,float x)void Jacobi(float*a,int n,float x)int i,j,k=0;int i,j,k=0;double epsilon,s;double epsilon,s;double*y=new do

11、ublen;double*y=new doublen;for(i=0;in;i+)xi=0;for(i=0;in;i+)xi=0;while(1)while(1)epsilon=0;epsilon=0;k+;k+;for(i=0;in;i+)for(i=0;in;i+)s=0;s=0;for(j=0;jn;j+)for(j=0;jn;j+)if(j=i)continue;if(j=i)continue;s+=*(a+i*(n+1)+j)*xj;s+=*(a+i*(n+1)+j)*xj;yi=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i);yi=(*(a+i*(n+1)+n

12、)-s)/(*(a+i*(n+1)+i);epsilon+=fabs(yi-xi);epsilon+=fabs(yi-xi);for(i=0;in;i+)xi=yi;for(i=0;in;i+)xi=yi;if(epsiloneps)if(epsilon=max)if(k=max)printf(printf(迭代发散迭代发散);return;);return;delete y;delete y;第29页/共32页void main()int i;float a45=10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,11,25;/*float a910

13、=31,-13,0,0,0,-10,0,0,0,-15,-13,35,-9,0,-11,0,0,0,0,27,0,-9,31,-10,0,0,0,0,0,-23,0,0,-10,79,-30,0,0,0,-9,0,0,0,0,-30,57,-7,0,-5,0,-20,0,0,0,0,7,47,-30,0,0,12,0,0,0,0,0,-30,41,0,0,-7,0,0,0,0,-5,0,0,27,-2,7,0,0,0,0,0,0,0,-2,29,-10;*/float x4;/float x9;Jacobi(a0,4,x);/Jacobi(a0,9,x);for(i=0;i4/*9*/;i+)；printf(x%d=%fn,i,xi);第30页/共32页n n作业题:P104 1第31页/共32页