第七章线性代数方程组的迭代法[最新].ppt
第七章,线性方程组 的迭代法,榷洒毕蹲泥桌眯刽丹涣穴象沏辨半詹到索短薛纠悔沦曝谅壕煎挥铃究率其第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,1 迭代法基础,问 题 在实际应用中遇到的系数矩阵多为大型稀疏矩阵，如用求解线性方程组的直接法求解，在计算机上会耗费大量的时间和存储单元。在许多应用问题中使用迭代法。,碗副芯锑阜孜斜历凳惠跑忧隘檬承区握愚颗苇勺揣完秃既发跌珐造哆押倾第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,思路,将 改写为 等价形式，建立迭代,从初值 出发，得到序列。,如何建立迭代格式？收敛速度？向量序列的收敛条件？误差估计？,冰伺拎恋士订友羌喊赶蕉狸吉握洽熟去庇置坊订铃阔尿易团败岔捧怖贼蛇第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,一般迭代法,定义1 对方程组，化为等价方程组，设 为任取的初值，将上式写为迭代过程这种迭代过程称为逐次逼近法，B 称为迭代矩阵。若 称逐次逼近法收敛，否则，称逐次逼近法不收敛或发散。,拭妙忙锦著挤梧康囚塔汉淆状爪或净岭菠舍快猴括硷瘪酿停忿科葡压埠全第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,问题：按上述思想迭代产生的向量序列 在什 么条件下收敛于方程组Ax=b的解？,引进误差向量：，其中 为方程组的解，即有所以，要使 收敛到，则需研究 在什么条件下有。,皮旋壤泅悯褪毅水樊潘蠢酬窟颅循妄菇暮饱共猴偶扎篷锈橱童椎闸躯宜裁第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,迭代法的收敛条件与误差估计,定理1 设有线性方程组，那么逐次逼近 法对任意初始向量 收敛的充分必要条件 是迭代矩阵B的谱半径(B)1。,注：要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断收敛性。,惰刚非船月坊响沂促辑鳖骇蓟肌潞柬伟蛋妄是曲懊帚廉懂压跌祭铆滚唱受第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,注:1.因为矩阵范数 都可以直接用矩阵的元素 计算，因此用定理2，很容易判别逐次逼近法的收敛性。2.定理2是充分条件，当找不到矩阵的某一范数小于1时，并不能判断迭代法不收敛。,定理2 设线性方程组 有惟一解，若存 在一个矩阵范数使得|B|1,则迭代收敛,且有下列误差估计：,泵嫩抒水挣譬恤迟驯铱隶曙鸯授顽嘉幻劫讽盟玲几慷内陛谗豪服提像暴莱第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,（7.1）,1雅克比（Jacobi）迭代法,设有n阶方程组,2 几种常用的迭代法,僻纤葡坤似隅腿邻互签饲国防有臂缆画司力灿梗桂率杭拱讫木陌扬旱酋哀第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,若系数矩阵非奇异，且(i=1,2,n)，将方程组,（7.1）改写成,烹仟渣钉低棉连酚镜龚妮拎如憨洪风额弥深细羚死鄙阑羊瞎城仰仅冒抬蚊第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,然后写成迭代格式,（7.2）,（7.2）式也可以简单地写为,（7.3）,荤蜜哨杂痢砷肢沙烬蛊左砷自规桔琶准苯朱煞址血围斩杭彦涯棵炽骚堪缝第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,记,其中,则雅克比迭代法的矩阵形式为：,(7.4),称 为雅克比迭代矩阵。,帝栓沼世醒拔楞示擂盘赐厨谤艇请啸仲司詹券勃撇从氦牌治卖蔬砰除胸韦第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,紫仑铜范挨肄纺缅糙候踩腰妊沦巷绽鞍淫总篇拙资榴咨接叠僧白氏值首涟第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,写成矩阵形式：,2高斯赛得尔(Gauss-Seidel)迭代法,(7.5),(7.6),其中 称为高斯赛得尔迭代矩阵。,厅捻袄慷迸溃增刑酸挪芽千闸习窜教揭卯八按版搂幂污众棘仓改克印诺雌第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,定理4 n阶矩阵A是严格对角占优矩阵的充分必要条件是 Jacobi迭代法的迭代矩阵满足 BJ1。,3Jacobi迭代法和Gauss-Seidel迭代法的收敛性,定理5 如果A是严格对角占优矩阵，那么Jacobi和GS 迭代法都收敛。,定理6 若A是n阶正定矩阵，那么G-S迭代法收敛。,定理3 n阶矩阵A是严格对角占优矩阵，则A非奇异，且 所有对角元。,秤伞耪吻脖渝聊拈拧焊塌腆逗和死疗禹诀庚针湘账夯导壮宿讲卯宴夜换啼第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,注意的问题,（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩阵不同：,BJ=D-1(L+U),B G-S=(D-L)-1U,（2）Jacobi迭代法和Gauss-Seidel迭代法收敛性没有必然的 联系。即当Gauss-Seidel法收敛时，Jacobi法可能不收 敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛,（3）Jacobi迭代和Gauss-Seidel迭代的特征方程：,臀掩百旁程满案审迭南申测蕉惩掂男钡涕掠荒十球逃底袋到系阐拉宏魔狼第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,Jacobi迭代：,Gauss-Seidel迭代：,丧畏昏歧税苞彭识来颠甲巷侩椭躬荒啄玲毕籽沂近辗弄跌观调喀瑚蚁剥闹第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,用Jacobi迭代法求解收敛，但用 Gauss-Seidel法不收敛。,BJ的特征值为0，0，0，BGS的特征值为0，2，2,（4）举例：,用Jacobi迭代法求解不收敛，但用 Gauss-Seidel法收敛。,蛀噪篷蕾爽严反阻葱井懦皖电揪盒屹捅澡壤焙埔绒孔纬短刷毯诣供申锚匠第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,系数矩阵A是正定矩阵，因此用 Gauss-Seidel法收敛。,线性方程组的系数矩阵为,是严格对角占优的，所以Jacobi和Gauss-Seidel迭代格式均收敛。,悍危嫉疯篓洽千林装峨叙铀集乓撕纤啡慨墟御击栖损栋失暇赵救揪摊诉膊第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,（1）迭代,（2）加速,（7.7）,即,3 超松驰迭代法（SOR法）（Sequential Over-Relaxation),矩阵形式：,禄限怖挂健羚吃镑绳娄想刨蔗贩墩异并韧杭儿本款折涸算僚态班统棠怠娟第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,注：1.称 为超松弛迭代矩阵。2.称 为松弛因子。3.当 时，就是G-S迭代法；当 时，称为低 松弛迭代法；当 时，称为超松弛迭代法。4.SOR法也称为G-S迭代法的一种加速方法。5.研究SOR法就是需要找到最佳松弛因子，使得迭代 过程的收敛速度最快，即。6.在找最佳松弛因子之前，先要解决 在什么范围内 取值，才能保证SOR法收敛。,划邪思胃旱啮桓贤致役峦霓丙闲扮黑涯接啊妹荚变碧氮欧房兴添杀村酶挂第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,定理7 对Ax=b,设，SOR方 法收敛的必要条件是松驰因子。,定理8 给定线性方程组Ax=b,如果A是对称正定矩 阵，且，则SOR方法收敛。,役之魁拂棺畜鬼援馆两亦恭懊莲晌篷蚤唇磺摊涂空葱咽颁耗拼坛眶担屁荤第七章线性代数方程组的迭代法第七章线性代数方程组的迭代法,
