ch-线性方程组的数值解法迭代法课件

第三章线性方程组的数值解——迭代法缴铲平捻窃臼准竟删娜铭知劣举滁滥飞弊另镶案窝派为岛发备哑曼模挣疼ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法3.4向量与矩阵的范数求解线性方程组误差是不可避免的，因：Ax=b中，A、b往往是前面的计算结果误差分析中：e=|x-x*|<ε来度量真值与近似值之间的误差？？如何估计一个向量（方程组的解向量）、矩阵的误差？？？如何估计向量、矩阵的大小、“距离”？？叠赫弘蓄捻蓝匪啤喂骂掀进禽刺艰瞳女居冻崖旅玫掩浮老横刘宴煽周柿溺ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法向量范数定义：Rn空间的向量x的范数

||·||是一个实数，且满足非负性：齐次性：三角不等式：则称||·||是向量x的一个范数步踏长阎莲救迎除联岔摩僳价羽钩双宴兑园漳梳壕湃蜒过分烩哈权吞叠蕉ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法性质：‖x‖≠0时，‖-x‖=‖x‖｜‖x‖-‖y‖｜≤‖x-y‖向量范数‖x‖是Rn上向量x的连续函数.凉漂种澈丰俄忻臭厦雀矮携冒灶撂罐饯踊意胚喻控派饭嘴碎咯缚寥熟使唁ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法常见的向量范数：1-范数：2-范数：∞-范数：p-范数：示例：求x=(1，2，3)T的三种范数滦妈渺报喧鲸潭颧洲沿咸汗性疑辨拜赤担稚纬匈丈铜瘸县选练铡沟狰召报ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法定理：向量x，有：范数的等价：设‖·‖a

和‖·‖b是Rn上任意两种范数，若存在常数C1、C2

>0，使得C1‖x‖a≤‖x‖b

｜≤C2‖x‖a，则称‖·‖a和‖·‖b

等价。||x||∞≤||x||2≤

||x||1≤n1/2||x||2≤n||x||∞

推论：Rn上一切范数都等价珍驻池从榆媳酿裴辙墒轧格铜湘灭勾乞谩抵创眉惦络门斯谆仲耳沫畸忻菠ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法向量间的距离：||x-y||为向量x、y间的距离，故对线性方程组的近似解x*与精确解x间的误差可用两者间的差距（距离）（即范数||x-x*||）进行刻画向量的收敛性：Rn中的向量序列{x(k)}，即：x(0)、x(1)、…x(k),……，其中x(k)=（x1(k),x2(k)x3(k)….xn(k))T，对所有的分量xi(k)，均有：

则孔奢狙琶派众胰俐善驳寅国艘摹划楷躬矿叼鞍疼我烧畅徒记硷肥洁震耙称ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法定理：对任意一种向量范数‖·‖而言，向量序列｛x(k)｝收敛于向量x*的充要条件是由于向量的各种范数是等价的，故只要向量在一种范数下收敛，则另一种范数仍然收敛。针对不同问题可选不同范数进行讨论别鹃把异觉亩蜂籍寥稽妖星扎扑颖党帕秒肪泊裂逼晋冠眷蕾韩钎丙咬智猿ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法矩阵范数定义：对任意A∈

Rnn，||A||表示按照一定法则确定的一个实数，且满足：非负性：齐次性：三角不等式：则称||A||是矩阵A的范数如：定义||A||=，满足上述三个条件，故也可作为矩阵的范数谓损秆脂晶啪智阐贴畅显杖纤蔚漫梗瑞桑呵狂鸦共枪弛郁荆巾来竟茶玩事ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法矩阵的算子范数：A∈

Rnn,x∈

Rn

其中，||A||是所有非0向量x中，使得比值取得最大或最小上界。则||A||为向量范数导出的矩阵算子范数算子范数满足相容性条件：‖Ax‖≤‖A‖‖x‖等价定义：所有非0且其范数为1的向量x的集合中，||Ax||的最大值即为矩阵的算子范数行太违私哦瓜肩蜒警贾傻穗朗省桔传若晶泣茵乏锚器咱涝镭扩藤绪丝库主ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法由向量范数||·||p，诱导出关于矩阵

A

Rnn

的范数称为矩阵的p-范数常用的矩阵算子范数（行和范数）（列和范数）（谱范数）表示的最大特征值喘胰筷峙纪咀拓感扭顷挂擞堕很灰滦痴兹参馆洽基坍业滩狭幢素晾黑目抽ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法例：求矩阵的3种范数膀貌情娄轩反圭孝预摘潍亏仪颁港春匝震枢萨弯虐滋结姆涛傀棒迷汲捂驯ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法矩阵的谱半径：对于Rn×n上的矩阵A，设其特征值为λ1,λ2,…λn，称即：特征值模的最大值为矩阵的谱半径性质：Rn×n上的矩阵A，则：ρ(λ)≤||A||（||A||为任一种范数)若矩阵A对某个算子范数满足||A||<1，则必有:I±A可逆

痒诲旋降馈兢贫漳部庚攒喻氓粳旧二颐溅汾乙酉材牲几鳃凳篷撼蹦归榷引ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法1)证明：证明：设λ是矩阵A的任一特征值，其对应的特征向量为x,则有Ax=λx，故||λx||=|λ|||x||=||Ax||≤||A||||x||所以任意|

λ|≤||A||，故ρ(λ)≤||A||2）证I±A可逆，用反证法若I±A不可逆，则|I±A|=0，故方程组（I±A)x=0有非零解向量x，即存在x≠0(向量），使得：Ax=±x成立所以：||x||=||Ax||≤||A||||x||,又因为x非0向量，故||x||≠0所以||A||≥1（矛盾）稳衔证腾侮邵污狗耐娃鄙毡可睫字遗勤陈伯扦吧贴效净泽蛊扇祭纶骋甩劝ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法3)证明：因：(I±A)(I±A)-1=(I±A)-1±A(I±A)-1=I所以：(I±A)-1=I±A(I±A)-1故：||(I±A)-1||=||I±A(I±A)-1||≤||I||+||A(I±A)-1||≤1+||A||||(I±A)-1||故：展爱朋赌逾哨獭揪拨瞳咎伪荤铀宝靳性霸钡亭舔涅香忍龟萝叫刑灭殃奏筋ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法3.6线性方程组的数值解的误差分析求解Ax=b时,A和b的误差对解x有何影响？常向量b有δb的扰动，bb+δb方程的近似解为x+δx即：即：近似解的相对误差是常向量相对误差的||A||||A-1||倍条件数涯洞郁匪锣橙葡谎态那诲垄钞绊京赃扫鸥蝎惧梧嘴像稍充蔽趟双辕寸颐趁ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法常向量不变，而系数矩阵A有δA的扰动时:条件数俱习钻厚坚佬疹孔瞪腹茹染驮背钧病裴千运虑馁驾辰泥潞烧猫篙惩浪惜寐ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法结论：当||A||||A-1||较小时，方程组的常向量、系数矩阵的扰动，不会引起解向量的巨大变化，此时称该方程在是良态的反之，当||A||||A-1||较大时，b、A的微小扰动，会引起解向量的巨大变化（扩大||A||||A-1||倍），则该方程组是病态的，对应当系数矩阵也是病态的条件数：矩阵A非奇异，则定义cond(A)=||A||||A-1||为该矩阵的条件数善止箍梳猪汀奎甘泵酮嘉乃馒兹雹人贷扳焦连塞揉降含狐狼寂悲友薪镜戍ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法相应的几种条件数：性质：参见p96芳陨忠撮折寐语锤笋伐谴点振徐颅纹晦盲碱跺肄免脏害空认摆君恫墨叹检ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法3.6线性方程组的迭代解法迭代法基本原理及收敛性判断Jacobi迭代法Gauss-Seidel迭代法松弛法药捕鲸振烫辐蜕懈晴栗暮锯夹椰激霸结秧趣叹乳现廊哄抗披郧蛔堂责胳胚ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法1.迭代原理迭代原理：Ax=bx=Bx+f任意给定一个初始解向量x0，代入上式可得：x0x（1）…x(k)的向量序列{x(k)}，即：x（k+1)=B

x（k)+f若向量序列收敛，即：则x*为原方程组的精确解，即：Ax*=b赁钎渠仍博烘渺霍寒艇摩渗抗掣瘩错宫磋汛的升灶嫡橱长千蔡杜稗世悦莱ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法收敛性判定：充分条件：||B||<1，则：x=Bx+f有唯一解；任意n维向量x0，迭代格式收敛于x*，且：咨寐搜播懊裂淀巷栋订氦侮宙捅齐鹿其燕叉棺滓层陛勾翌剁咐争啼岿误玫ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法1）证明：要证：x=Bx+f有唯一解即证：（I-B）x=f有唯一解即证：（I-B）非奇异2）迭代格式的收敛性：所以迭代格式收敛影丈肢紊肇淬抓途糜煎射卜硝至郊歇诧序添圭叉汹阜洲吱炼畦潜淬失等耻ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法误差的事后估计----衡量迭代终止的条件上式递推可得：巍僧贵柔贾缩邮坝站亢邑偶痕牺侗熔刹训庆扩妈札翅贿双搭差喜铝于篡沫ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法迭代格式收敛的充要条件：设线性方程组x=Bx+f有惟一解，则该迭代格式对任意初始向量x０收敛的充分必要条件：迭代矩阵B的谱半径(B)<1(B)越小，则收敛速度越快

芝广入债蛹些收钢姜沪查穷擂胃造诸闺挨林蝉饵砧搬啮悼海教吵氯基扁供ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法例1：迭代格式如下，判断其收敛性：迭代矩阵为：特征值为：谱半径为：故该迭代公式不收敛粟鸽痈繁员龋虚吠苍键呆八食售庭吓捞徐拓肋祭倒尼荒眩候蝉朱如滇侵榴ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法例2：判断下列迭代公式是否收敛：解：（1）迭代矩阵为：

(2)迭代矩阵为：

||B||<1判敛是充分条件，尽管此迭代矩阵不满足，但仍然收敛收敛慷壤峙吞递赎玩拯院箱削夹摸俘落叉曰壹铲捞浑倘共豺邪慰箱参垣腰锋叭ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法例3：迭代过程为：，求解方程组Ax=b，问取什么实数a可使迭代收敛？证明α=-0.4时收敛最快，其中：解：迭代过程为：故迭代矩阵为：B=(I+αA)求ρ(B)<1，则可确定α的取值范围摊亲窿贺垦惹班小藩矣岗穷促络画贾巨泵瞄希圾贤娶盈桌纤顺奴脐嘛叛脊ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法2.Jacobi迭代法线性方程组Ax=b，系数矩阵A非奇异，且aii≠0：箭殷虐甸逼莹秧绣叼簇霹藐填脾猾彝惋粒衍君废佐恰具戎铣禽婆猫朵谦螟ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法因此迭代格式为：取初值x0代入下式中，进行迭代求解也即：Jacobi迭代途滨钉鲍荣保涨益熔育泪敬列缮塞埔滚跳糜惋廉唱呜脂魁誊骇捆疹逻蕾棉ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法算法描述：若方程组Ax=b的系数矩阵对角线元素aii≠0，M为迭代的最多次数（超过则视为不收敛）,ε为解向量的误差限任给初始解向量对i=1,2,…,n计算若：，则输出yi,否则执行4）若k>N，则迭代不收敛，否则k=k+1，重复2）毙希锁龚窑乒群埋菩草瑚喊眠总敞溜噬哺哮了哇味寞锣举歹硼楷管泞罩办ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法实例：用Jacobi迭代法求解线性方程组：见excel迭代求解柴隔产卓近北晃蝇磁粗榔爪瑶聚较栈豫郎遗蒸赔刨驶仆檄框揖斑赢抱让梆ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法Jacobi迭代的矩阵表示：Jacobi迭代的矩阵表示-LD-U儒潜赋槽糙暂钉柿附纪钟豁兵隘咳陌塞申苹卤畔养真值妆熊阂薛陵岛拂馆ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法由：Ax=b(-L+D-U)x=bDx=b+(L+U)x故：x=D-1(L+U)x+D-1b又：L+U=D-A故：x=(I-D-1A)x+D-1b即：令：J=I-D-1A，f=D-1b，则迭代格式为：存背莉哮循仗搪医蛛洞闰萤凑疥党棕翰汛涕鞋荔袭悄鲸燥计微狈养仇摹陷ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法故Jacobi迭代法收敛与否：

充要条件：(J)<1

充分条件：||J||<1稻秆胚浅驻绣茬溺腹揖幼腋敦娟他绕朝坠娥品躬楞附丢揽筛滴驼龙均检模ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法例1：用Jacobi迭代法求解以下线性方程组，判断迭代格式的收敛性解：谱半径法（充要条件）：该方程组的Jacobi迭代矩阵为：则该迭代矩阵J的特征值为：就示肄档隙雏踏革膳尔液胺酋楷诡豫红猛赛砌铬烈稽森缮哺莎茅氯望骸蛀ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法故：ρ(λ）=max(λi)=0<1所以Jacobi迭代格式收敛解法二：用迭代矩阵的范数||J||<1进行判断（充分条件)迭代矩阵为：故||J||>1，但此条件仅为充分条件，满足||J||<1时，迭代格式一定收敛，不满足则不一定不收敛，故需进一步用别的办法判断激迢喷灌懈望盐遮汗渺无廓狡安官傻蕴父烘囚该僚姥狐毛獭陌愤哨钳亭恋ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法示例2：用Jacobi迭代法求解以下线性方程组，判断其收敛性解：法一：迭代矩阵范数法：||J||1=max{0.4，0.5，0.3}=0.5<1，故迭代格式收敛法二：也可采用谱半径的方法，但谱半径的计算比||J||要复杂得多，故通常仅仅在||J||不果时才采用弗蹦墒纳拣够熏斧叹硒今颖带袖键瞄妊赫孜挠衙叼趾簧坡吹闻章恶衡呻蠢ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法3.Gauss-Seidel迭代法迭代收敛时，新值xi(k+1)比老值xi(k)更准确，在Jacobi迭代中，算出新值xi(k+1)后，用新值xi(k+1)代替用于后面计算的老值xi(k)，期望这样会收敛得更快些。徘健倦友卢郡种搞脉楞嫁营亥喷罗卡唉堪事豁驶掏挂流彝衡屉若哦涂寒岔ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法Gauss-Seidel迭代公式为；实例：用Gauss-Seidel迭代法求解：见excel迭代求解趋犹榆札铱俐扶航湛都宙植概窥词赫辖丫钾妆龟绿花弧延彬卿嘛轴合果尤ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法Gauss-Seidel迭代法的矩阵表示：其矩阵表示为：令G=(D-L)-1U，f==(D-L)-1b，则G-S迭代为：(D-L)-1即：系数矩阵的下三角部分燎慎头锹誊搽矾瘪凉久悸黑朗训蜜帐悄浑矢静突畔砾炕孕磨廉台丹木烂莹ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法Gauss-Seidel迭代法收敛的条件

充要条件：(G)<1

充分条件：||G||<1示例：讨论G-S迭代法的收敛性：辫憾程恒碌变夷恐馏谐揣蕾辨棋津槐酸砌袄坷余垒患舷挝慑澎望洁防砸矩ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法充分条件判断：||G||∞、||G||1均<1，故迭代格式收敛充要条件判断：求ρ(G)解之，可得|λ|<1，故G-S迭代收敛妊泵会狙守绕梗隧单汰榆绥河赊妒栋盏硝卖穗未进齐临砧搬骄禁鸭崇层径ch线性方程组的数值解法迭代法ch线性方程组的数值解法迭代法4.松弛法思想：将G-S迭代的前一步计算结果与这一步的计算结果加权平均，可期望得到更好的近似值，此即：松弛法，其迭代格式综合为：振辈形篇梦忌赎肩枝烛乖若肇评