《解线性方程组的迭代法.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代法.ppt（39页珍藏版）》请在金锄头文库上搜索。
1、理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学解线性方程组的迭代法 直接法得到的解是理论上准确的，但是它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n400），但是在很多实际问题中，我们要求解的方程组n很大，而系数矩阵中含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。 迭代法是一种逐次逼近的方法，其基本思想是：使用某个固定的公式，对解的近似值进行反复校正，从而得到一个近似解序列，
2、使之收敛于方程组的解。 迭代法具有算法简单、运算速度快的特点。但这种方法获得的是方程组解的近似值。理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学对方程组做等价变换从某一初值 x(0) 出发，我们可以构造序列若同时：所以，序列收敛与初值的选取无关与初值的选取无关如令A=D-L-U，于是 x=D-1(L+U)x+D-1b,理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理
3、工大学定义5.1：设G为n阶方阵，若Gk0，则称G为收敛矩阵定理：即矩阵G为收敛矩阵，当且仅当G的谱半径1由知，若有某种范数则，迭代收敛理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学迭代法的收敛性迭代法的收敛性定理定理：迭代法X(m+1)=GX(m)+g 收敛的充分必要条件是迭代矩阵G为收敛矩阵，即G的谱半径(G)1。定理定理： 迭代法X(m+1)=GX(m)+g 的迭代矩阵G的某种范数|G|qeps) x1=x2; for(i=0;i=n;i+) x2i=0; for(j=
4、0;ji;j+) x2i += Aij*x1j for(j=i+1;j1. Jacobi迭代不收敛。迭代矩阵为G的特征值为：1=4.02408, 2=-2.01204 3.10115 i, 1=4.02408； 2,3=3.69668理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学将方程组变形，化为：理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学G的谱半径(G
5、)= 0.308507 1.Jacobi迭代收敛。此时迭代矩阵为G的特征值分别为： 0.308507, - 0.154254 + 0.18304 i, -0.154254 - 0.18304 i理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 收敛条件收敛条件 迭代格式收敛的充要条件是G的谱半径eps) for(i=0;in;i+) for(j=0;ji;j+) x2i += Aij*x2j for(j=i+1;jn;j+) x2i += Aij*x2j x2i=-(x2i-b
6、i)/Aii 4、输出解x2Gauss-Siedel迭代算法理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 迭代矩阵迭代矩阵是否是原来的方程的解？A=(D-L)-UGauss-Siedel迭代法的收敛性迭代法的收敛性理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 收敛条件收敛条件 迭代格式X=GX+g 对任意的初值X0和向量g，收敛的充要条充要条件件是G的谱
7、半径 (G)1.Jacobi迭代不收敛。G的谱半径(G)=0.5eps) for(i=0;in;i+) temp-0 for(j=0;ji;j+) temp += Aij*x2j for(j=i+1;jn;j+) temp += Aij*x2j temp = -(x2i-bi)/Aii x2i = (1-omega)*x2i+omega*temp 4、输出解x2理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 迭代矩阵迭代矩阵定理： 松弛迭代收敛定理： A对称正定，则松弛迭代收
8、敛是否是原来的方程的解？理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 SORSOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(G )达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.当松弛因子1时，称该算法为超松弛因子法；理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工
9、大学 定理定理 若SORSOR方法收敛, 则02. 证证 设SORSOR方法收敛, 则(G )1,所以 |det(G )| =|12 n|1而 det(G ) =det(D - L)-1 (1 - )D+U) =det(E - D - 1L) - 1det(1 - )E+D-1U) =(1-)n于是 |1 - |1, 或 02理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 定理定理 用SORSOR法法解方程组Ax=b， 证证 设是G 的任一特征值, y是对应的特征向量, 则
10、(1-)D+Uy= (D - L)y于是 (1 - )(Dy,y)+(Uy,y)=(Dy,y) - (Ly,y)1）若A是对称正定矩阵, 则当02时收敛；2）若矩阵A按行(列)严格对角占优, 则当00 (Uy,y)=(y,Ly)=(Ly,y)= - i 0(Ay,y)=(Dy,y) -(Ly,y) -(Uy,y) = - 2所以理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学当02时,有 ( - +)2 -( - )2= (2 - )(2 - ) = (2 - )(2 - )0
11、所以|21, 因此(G )1,即S0R方法收敛.可得 =2/ 设是B的任一特征值, y是对应的特征向量, 则 (L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学当A对称正定时,即2 - 0时,|0而 (2D - A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =+2即,当A对称正定时,JacobiJacobi迭代法收敛2D-A正定.理学院University of Shanghai for Science a
12、nd TechnologyCollege of Science 上海理工大学上海理工大学共轭梯度法给定对称正定矩阵ARnn，求解方程组AX=b的共轭梯度法如下：1.选定初值X(0) Rn, 设r(0)=d(0)=b-AX(0);2. r(k+1)= r(k) - (k) A d(k); 其中3. d(k+1)= r(k+1) + (k) d(k); 其中4. X(k+1)= X(k)+ (k) d(k) ;理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学定理：设矩阵ARnn对称正定，X(k)为用共轭梯度法求解方程组AX=b所产生的迭代序列，并取条件数那么：1)用不超过n次迭代即可获得精确解；2)对每次迭代结果的误差估计为：其中范数|X|A=(AX , X)
