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