线性方程组的简单迭代法.ppt
第三章第三章 求解线性方程组的迭代方法求解线性方程组的迭代方法2012年年11月月13日日n n引言引言3.1 3.1 简单迭代法简单迭代法 考虑线性方程组（1.1）其中 为非奇异矩阵，当 为低阶稠密矩阵时，第2章所讨论的选主元消去法是有效方法.但对于 的阶数 很大，零元素较多的大型稀疏矩阵大型稀疏矩阵方程组，利用迭代法求解则更为合适.迭代法通常都可利用迭代法通常都可利用 中有大量零元素的特点中有大量零元素的特点.两个简单的例子两个简单的例子例例1 1 已知已知 ，任取，任取 ，则由，则由 例例2 2 已知方程已知方程 在在 附近有根附近有根.那么我们就能从那么我们就能从 开始，通过迭代公式开始，通过迭代公式 逐步得到所要求的根逐步得到所要求的根.假定我们已会计算假定我们已会计算 例例1 1求解方程组求解方程组 （1.2）记为 ,方程组的精确解是方程组的精确解是 .其中其中 现将现将(1.2)(1.2)改写为改写为 （1.3）或写为或写为 ,其中其中 将这些值代入将这些值代入(1.3)(1.3)式右边式右边 (若若(1.3)(1.3)式为等式即求得式为等式即求得方程组的解，但一般不满足方程组的解，但一般不满足).).任取初始值，例如取任取初始值，例如取 再将 分量代入(1.3)式右边得到 ，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式迭代公式)得到新的值 （1.4）简写为 其中 表示迭代次数 迭代到第10次有 从此例看出，由迭代法产生的向量序列 逐步逼近方程组的精确解 .迭代法的基本思想是构造一个向量序列X X(k(k)，使其收敛到某个极限向量 X*，而X*就是 AX=b b 的准确解。问题：如何构造迭代序列？迭代序列在什么情况下收敛？简单迭代法的迭代格式简单迭代法的迭代格式n阶线性代数方程组a11x1+a12x2+.+a1nxn=b1a21x1+a22x2+.+a2nxn=b2 an1x1+an2x2+.+annxn=bn若用矩阵和向量的记号来表示，可写成 AX=b b 设 ,并将 写为三部分 迭代矩阵迭代矩阵易知，雅各布（Jacobi）迭代有A=D-L-UA=D-L-UL+U=D-AG G为迭代矩阵为迭代矩阵 的雅可比(Jacobi)迭代公式如下:研究雅可比迭代法的分量计算公式研究雅可比迭代法的分量计算公式.记 或 于是，解 的雅可比迭代法的分量计算公式为 方程组的迭代式的展开式如下：由可知计算过程可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和计算一次矩阵和向量的乘法向量的乘法且计算过程中原始矩阵矩阵A A始终不变.例例1 1 用用J J法求解线性方程组法求解线性方程组方程组的精确解为方程组的精确解为x x*=(1,1,1)=(1,1,1)T T.解：解：取取初始向量初始向量x x(0)(0)=(0,0,0)=(0,0,0)T T,迭代可得迭代可得计算结果列表如下: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 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.0710.03550.03550.011590.011590.0057950.0057950.00176360.0017636可见可见,迭代迭代7次使得次使得迭代序列逐次迭代序列逐次收敛于方程组的解收敛于方程组的解,。简单迭代法的算法如下：简单迭代法的算法如下：1.输入矩阵 A，右端项 b，维数 n，初始迭代向量 X(0),容许误差 e，容许最大迭代次数 N。2.置 k=1。3.对 i=1,2,n4.若 ，输出X，停机，否则转5。5.若 ，转3；否则输出失败信息，停机。对于任何由 变形得到的等价方程组 ，迭代法产生的向量序列 不一定都能逐步逼近方程组的解 .如对方程组n n一般迭代法收敛性的基本定理迭代法的收敛性迭代法的收敛性 设 其中 为非奇异矩阵，记 为精确解，于是 且设有等价的方程组（2.1）设有解 的迭代法 问题是：迭代矩阵 满足什么条件时，由迭代法产生的向量序列 收敛到 引进误差向量 由(2.1)式减(2.2)式得到误差向量的递推公式（2.2）因此，研究迭代法(2.2)收敛性问题就是要研究迭代矩阵 满足什么条件时，有 设有矩阵序列 ,如果 个数列极限存在且有 则称 收敛于 ，记为 定义定义1 定理定理1 1（2.3）(迭代法基本定理)设有方程组 及一阶定常迭代法（2.4）对任意选取初始向量 ，矩阵 的谱半径 迭代法(2.4)收敛的充要条件是 所谓所谓“谱半径谱半径”，就是最大特征值（对于实数而言），就是最大特征值（对于实数而言）,如果是特征值是复数的话，谱半径就是特征值的最大模。如果是特征值是复数的话，谱半径就是特征值的最大模。推论推论设 ，其中 为非奇异矩阵且 非奇异，则 (1)解方程组的雅可比迭代法收敛的充要条件是 ，其中 定义定义2 2：若n阶矩阵A A=(aij)满足:则称矩阵A A是严格对角占优矩阵严格对角占优矩阵.定理定理2 2 设设A A是严格对角占优矩阵是严格对角占优矩阵,则解线性方程组则解线性方程组Ax=bAx=b的的J J迭代迭代法收敛法收敛.计算机实现程序计算机实现程序n n用雅各比迭代法下面线性方程组#include#include#include#include#define#define epseps 1e-3 1e-3#define max 100#define max 100void void Jacobi(floatJacobi(float*a,inta,int n,floatn,float x)x)intint i,j,ki,j,k=0;=0;double double epsilon,sepsilon,s;double*y=new double*y=new doublendoublen;for(ifor(i=0;i=0;in;i+)xin;i+)xi=0;=0;while(1)while(1)epsilon=0;epsilon=0;k+;k+;for(ifor(i=0;i=0;in;in;i+)+)s=0;s=0;for(jfor(j=0;j=0;jn;jn;j+)+)if(jif(j=i)continuei)continue;s+=*(s+=*(a+ia+i*(n+1)+j)*(n+1)+j)*xjxj;yiyi=(*(=(*(a+ia+i*(n+1)+n)-s)/(*(*(n+1)+n)-s)/(*(a+ia+i*(n+1)+i);*(n+1)+i);epsilon+=epsilon+=fabs(yi-xifabs(yi-xi););for(ifor(i=0;i=0;in;i+)xin;i+)xi=yiyi;if(epsilonif(epsilon=max)=max)printfprintf(迭代发散迭代发散);return;);return;delete y;delete y;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=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);n n作业题:P104 1
