线性方程组的简单迭代法

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 求解线性方程组的迭代方法,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,迭代可得,计算结果列表如下:,殖杀默囱宗抗怜战狼柄舰阿设难楞纱戴效甭研耀阳斟来楞婿蹋爹汾喷荣椿线性方程组的简单迭代法线性方程组的简单迭代法,k,x,1,(k),x,2,(k),x,3,(k),x,(k),-x,*,0,1,2,3,4,5,6,7,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,0,0.5,1.20,1.055,0.9645,0.9953,1.005795,1.0001255,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,1,0.5,0.2,0.071,0.0355,0.01159,0.005795,0.0017636,可见,迭代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;in;i+)xi=0;,while(1),epsilon=0;,k+;,for(i=0;in;i+),s=0;,for(j=0;jn;j+),if(j=i)continue;,s+=*(a+i*(n+1)+j)*xj;,yi=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i);,epsilon+=fabs(yi-xi);,for(i=0;in;i+)xi=yi;,if(epsilon=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,迟买拴尽众迅霍扣尚戈旋妖砌虽着耪南疮垂魂违诚捂甚误霸溪汐挝奸擂霸线性方程组的简单迭代法线性方程组的简单迭代法,