线性方程组的简单迭代法.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 = b1 a21x1 + 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 100 void 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;