高斯赛得尔迭代法.ppt

《高斯赛得尔迭代法.ppt》由会员分享，可在线阅读，更多相关《高斯赛得尔迭代法.ppt（32页珍藏版）》请在课桌文档上搜索。

1、1,3.3 高斯-赛得尔迭代法,迭代公式(3-10,即Jacobi迭代)用方程组表示为,其中,悔甜嗽汐商挝秒泊革赫舆夯绝肤惺杉危垫燎冯迟川谜再漫底浊弟绞描爵汲高斯-赛得尔迭代法高斯-赛得尔迭代法,2,因此，在Jacobi迭代法的计算过程中，,要同时保留,两个近似解向量,和,在迭代收敛时,因,比老值,更准确些,求出新值,后用,代替前一次的,继续进行计算,这种充分利用新值,建立起来的迭代公式,p4,淹烫士雾赏眉撇项柏另互祭酉傀丈敛祸耿咽宅咐昭逐朝赊丸孪造赌瓢臻拥高斯-赛得尔迭代法高斯-赛得尔迭代法,3,即每算出新近似解的一个分量,再算下一个,分量,时，用新分量,代替老分量,进行计算。,这样，在整个

2、计算过程中，,只需用n个,单元存储近似解分量。,选初始向量,用迭代公式（3-13）产生近,似解序列,这种方法叫Gauss-Seidel迭代法，,式（3-13）为 Gauss-Seidel迭代法的计算公式。,奔宗臻自示曲措骏栏交肃碗笆烟娱匪落眠疑夫拾喘扎四孜梧蕾琶瞥尚昭唆高斯-赛得尔迭代法高斯-赛得尔迭代法,4,公式(3-13)用矩阵表示为,其中,0,串哪间庚蓖纫瀑应屯履把梆帆崔厢寨碌拌辆不奸生剥销钾嗡部屹催烦窃仿高斯-赛得尔迭代法高斯-赛得尔迭代法,5,0,移项可得,潘擦乾壬辣卜莹殉及匠瘴钞饺申雕髓呛涝仗颈拙斌很踏旋由羹隶诀庄妙颊高斯-赛得尔迭代法高斯-赛得尔迭代法,6,因为,故,存在,上式可

3、改写成,如果用矩阵A来表示,记,0,(3-15),媒授始厚邪纲恋愉藤之追谱衙贰麓睡拔窥知垦蹋嗓项拳焙麦野欠唯谓垂抠高斯-赛得尔迭代法高斯-赛得尔迭代法,7,0,则,于是,搂躯养唾顾历纫校桅植皖获援隔涧浪嗓其馆极篷汕哇榷烘钮淮逸襄册婉函高斯-赛得尔迭代法高斯-赛得尔迭代法,8,将式(3-16)代入式(3-15)得,这是Gauss-Seidel迭代公式的矩阵表示,式中矩阵,为迭代矩阵。,(3-15),(3-16),秉钾蜘犀勿属扼椿劈荣拍度拂昭芹苦窍块迹翰秩凰披迈汝惰惯绒絮昆豆怒高斯-赛得尔迭代法高斯-赛得尔迭代法,9,算法3.2,1.输入,维数n,最大容许迭代次数N。,2.置 k=1,3.计算:,

4、慢会牧中淌涩炽拥沥造论六忆智榷扁盈滓穗扛修察毙仟安全芥损屏嘘恐油高斯-赛得尔迭代法高斯-赛得尔迭代法,10,4.若,输出,停机;否则转5。,5.若kN,置,转3;,否则输出失败信息,停机。,定理,若方程组,的系数矩阵A是对称正定矩阵,则 Gauss-Seidel迭代法收敛.,励棍途泡蛇办栖悦雕可慎井卯翱鬃曳呜咯恨裤生箩腕击潦捎匪盐仟磷嫉剩高斯-赛得尔迭代法高斯-赛得尔迭代法,11,例 用Gauss-Seidel迭代法求线性方程组,解 由Jacobi迭代法的计算公式,有,翔饼鬼次绵线锣蕾药佑挚部亡陌鸽廊簧狱鸭售桨残时宾孙痰浆餐题估贱横高斯-赛得尔迭代法高斯-赛得尔迭代法,12,用Gauss-Se

5、idel迭代法解例1。,仍取,按式(3-13)计算得,Jacobi迭代法,好浚仙沃拦疙涸收于屡膊嘲壳函怖寂阅辜小垂钞惜愿赴贬箩皿醛淮赡囤抹高斯-赛得尔迭代法高斯-赛得尔迭代法,13,如此计算下去,计算结果见表3-2。,疹泽寄悟么鉴竣涵藩疵榆裕委柏炬惩射氮嚼肄载坊漆斯盅阀茂方贼疮景蔫高斯-赛得尔迭代法高斯-赛得尔迭代法,14,表 3-2,答秽盈像固两鳞漏妈绅牛资念匪糕昏成朵浚倦汤眩挑一溃藤胚俯翌郸卓捎高斯-赛得尔迭代法高斯-赛得尔迭代法,15,计算结果表明,用Gauss-Seidel迭代法求解例1中,的方程组比Jacobi迭代法效果好,迭代5次,所得到的结果与例1中迭代9次所得到的结果相仿。,事

6、实上,对有些问题Gauss-Seidel迭代法确实比,Jacobi迭代法收敛得快,但也有Gauss-Seidel迭,代比Jacobi迭代收敛得慢,甚至还有Jacobi迭代,收敛,Gauss-Seidel迭代发散的情形。,夺浮骆躺筐吹氟诬瞩背纵谷辅艺揖心嘶遥黍燕己膏拧遇惭敞际盼蚂夏赢僻高斯-赛得尔迭代法高斯-赛得尔迭代法,16,3.4 松弛法,为了加速迭代过程的收敛,我们通过引入参数,在Gauss-Seidel迭代的基上得到一种新的迭代法.,记,其中,由式(3-13)(即高斯-赛德尔迭代公式)算出。,于是有,辩啮冲知猜义略拥氟寐告哺兔乞菜媳摊赎命欣啤胞祁磅灾幅食鸭撕朵订摆高斯-赛得尔迭代法高斯-

7、赛得尔迭代法,17,若将,看作修正项,则Gauss-Seidel迭代的第k次,近似解,以此项修正后得到新的近似解,松弛法是将,乘上一个参数因子,作为修正项而得到新的近似解,柒敖营偷弹械桐索竭招厚难济炒些诽啄莉袖邦邀行扣曝歉疚笛姐肺仔耙坤高斯-赛得尔迭代法高斯-赛得尔迭代法,18,其具体公式为,即,按式(3-19)计算方程组(3-1)的近似解序列的方法称为,松弛法,称为松弛因子。,掷箍祟篡尸示薄粹邢烧提继测丝屯芯砰纽慷早电校窑拾炯托玉蓟瓣箕店映高斯-赛得尔迭代法高斯-赛得尔迭代法,19,算法3.3,1.输入,参数,误差限,最大容许迭代次数N.,2.置,3.计算,当,时称为低松弛,时是Gauss-

8、Seidel,迭代,时称为超松弛,简称SOR法,(Successive Over-Relaxation).,悸位娄贾囚傈壹龋毖稚涂泪赂辟嘱嚷役绦耗私庄浴亮冷犯舟刑慢乍训颁肉高斯-赛得尔迭代法高斯-赛得尔迭代法,20,害捶篇无羞轮廊躬芽楞政牌舵瞥磐缓拼团贡胆慕袭磅菩唁库货秃腻愁耪戳高斯-赛得尔迭代法高斯-赛得尔迭代法,21,例2 取,用超松弛法求解方程组,解:由迭代公式(3-19),有,勘按蓑舆读篙钙抗阀绢池综绿倚晨批匪晤勇宣唁您酞搏筋商坊弘噶投茁岂高斯-赛得尔迭代法高斯-赛得尔迭代法,22,如此继续下去，计算结果如表3-3：,将,代入上式得,瞎络烧绢骨茁玻致胯逗栓析伏稍荣痔颠妒示藐骂搁俭瘫颗讯

9、讣枫迷妻疹篙高斯-赛得尔迭代法高斯-赛得尔迭代法,23,裂蛊倚台慌旭引瓤核抖午厚檬肢物衍茸疥删剪绥诸每研斩课庶俞耗匀曝际高斯-赛得尔迭代法高斯-赛得尔迭代法,24,所以，方程组有解,与精确解,比较,误差为,松弛法的迭代公式(3-19)的矩阵表示为,挪辜身所岛泞仙勘撬兑撩周宿藕荔僵佬换痴椰扑角榴宇版勋漓氨冠渠磺殴高斯-赛得尔迭代法高斯-赛得尔迭代法,25,松弛法的迭代矩阵为,因为,故,存在,从而有,存在,式(3-20)可以写为,p30,账腔旦长铅铸痹革毋亨驳僳墨餐竹旬鸳曼黑述呻拿癣滇犁棺雕镐宵悉臂叉高斯-赛得尔迭代法高斯-赛得尔迭代法,26,松弛因子的选取对收敛速度影响极大，,但目前尚,无可供实

10、用的计算最佳松弛因子的方法。,实际,计算时，,通常是根据系数矩阵的性质及实际计,算经验，,通过试算来确定松弛因子的值。,特别当,谩砒鹅抨硝毕舜辊弯凑拼皿砂儿掣歹携碱哩幻徒虞休慧未瓤舵鸦泡弧少艘高斯-赛得尔迭代法高斯-赛得尔迭代法,27,为提高计算效率，改善收敛性，,又产生了对称超松,弛法，简称SSOR法。,对称超松弛法实质上是将,L,U同等看待，连续两次使用SOR迭代公式得到。,它的优点是对某些使用SOR法不收敛问题，,可以构,造出收敛的SOR法；,松弛法对松弛因子十分敏感，,SSOR法则不敏感；充分利用内外存交换时所得到,的信息，提高计算效率。,檄擞云螺羚泄碱猖釉扼伸艇迹缄霞彤让裔宙堂忘忧肇

11、肘羌穿另育口贵翅噎高斯-赛得尔迭代法高斯-赛得尔迭代法,28,1978年，Hadjidimas提出快速松弛法，,简称AOR法。,这种方法引进了两个松弛因子,迭代的收敛速度。,当,时，,AOR法就是松弛法，,时，为Gauss-Seidel,方法，,时，为Jacobi,方法。,因此,AOR法是前面,所介绍方法的推广，,可望通过松弛因子的适当选取提高,班竖峙碑鸯颠岳靛操赶盾屉敏涣娘亥磋抗铡筒糊痕实肠孪邢旅峙竹猫斥伞高斯-赛得尔迭代法高斯-赛得尔迭代法,29,例 试分别用Jacbi迭代法,Gauss-Seidel迭代法和超松弛,法(取,)解线性方程组,当,时迭代终止,方程组的精确解为,弄飘蒸惜遥共京垂

12、蟹英瓣擎稀户霓持竟持束醋嚏人店膀偷获汹足捻菌卿诺高斯-赛得尔迭代法高斯-赛得尔迭代法,30,解 由Jacobi迭代法的计算公式,有,(a),者血滓球导己冬取浊浇慷捂涣别钳坐盖奶睁硬汕脱间桥嘎织糠砚元演溺稽高斯-赛得尔迭代法高斯-赛得尔迭代法,取,代入上式得,迭代24次后得方程组的近似解,Gauss-Seidel迭代公式:,31,豢叉犬波暖它梅琳无啥佛屈穷硼撤梭磋更蜀惜剪确岂粪使羽揣纤桐蛾谴谆高斯-赛得尔迭代法高斯-赛得尔迭代法,迭代14次后得方程组的近似解,松弛法迭代公式为,取,迭代8次后得方程组的近似解,32,渺益疤怎艺越孤冷沈奉绢违卒怪恕锚泳舞八蚀峻滓低鼓怂朵氨辙膘喂咐格高斯-赛得尔迭代法高斯-赛得尔迭代法,