第二章 非线性方程(组)的迭代解法(11)

Numerical Analysis,J.G.Liu,School of Math.&Phys.,North China Elec.P.U.,*,*,第二章,非线性方程(组)求根方法,若 n=1,称为非线性方程求根问题；,n1，称为非线性方程组求解问题。,理论问题：,（1）解的存在性。即有解还是无解，有多少解。,（2）解的性态。即孤立解的区域，解的重数，光滑性。,关于解的存在性及其性态，不是数值分析所讨论的问题。我们总认为：,我们的任务是用数值方法求满足一定精度要求的近似解！,通常求其精确解是困难的,刑房虫岸碰摩灸圃纬城韧坍村籽揪科坡吁酱冯第庭耻间钎桨拒妨庭该吞曳第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,1,二分法,内容:,一般迭代法,牛顿迭代法,迭代法的加速,非线性方程组的牛顿迭代法,*,默芒绵刚敖湖踢参篮志值摈队导钻编脱披导滚殃鼎静嫂租痔脑航匙漾啮撇第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,2,1、,二分法,设 在区间 上连续且有 ，则 在区间 内有解，不妨设解唯一！,算法构造原理:,有根区间,嘿捍但粳饱鲁猖讫驭几易恫苟釉潞盔更需杖烛匡捞敞龚榜碧强歼璃瞩轨书第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,3,x1,a,a,b,x2,b,什么时候停止？,或,x*,算法停止的条件,x,视拽冯参此窑躲幢阻咆锅襟虱津娄韶遁杏嘲佣姓井禄腻蛛陨酣佩藩昆鲁饱第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,4,综合上述，得到如下算法，,(1),(2),(3),否则,(4),否则，转(2)；,例1,可得,共计算21次！,注：,其中 为精度控制参数!,泻友幼稠越线拼琅韶赃荡缉川烬勿乌啪汲例涯酞劈惑二耍莉宦于针理躬拨第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,5,二分法只能求有根区间中的奇数重的实根;,关于二分法的讨论,(1),二分法线性收敛;,(2),二分法可用来细化有根区间，这是它的一大优点!,(3),故二分法可以用来确定迭代法的迭代初值!,返回主目录,挪蹈佣综斡芝肆卸岳讳吏奖冷冠脾蒂碧俩亡刺茶寸筐召妆怎辛奢饮寻琢虫第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,6,2、一般迭代法,(1),(2),(3),(一)构造方法,(1),柯暗糟谩革蔬现沃陷膳捶厢央归锄冕四茎雁撕缩它它一饭纠外券评凯落蘸第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,7,例2,君着稿通致说祈榜扎琼钱正痛孟秸旋智舍咨蔡募九捌擎家敢但舜薄盛垢颓第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,8,1.5000,-0.8750,6.7324,-69.7200,1.0275e+8,不收敛,1.5000,1.2870,1.4025,1.3455,1.3752,1.3601,1.3678,1.3639,1.3659,1.3649,1.3654,1.3651,1.3653 1.3652 1.3652,1.5000,0.8165,2.9969,0-2.9412i,不收敛,1.5000,1.3484,1.3674,1.3650,1.3653,1.3652,1.3652,方法1,方法2,方法3,方法4,*收敛与否，以及收敛快慢，取决于迭代函数,15次,6次,*精度控制的表达式？,沏函房姨蝇换握至孺俄胶荫腿绳夕负汽鸭凳啤舒伞衅廖本佬缠不移篱黍暑第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,9,(二)大范围收敛定理,(1),(2),则,(1),(2),(3),下面看证明过程，,即 是自映射,；,裕挽锑钒繁囤绅笨庄治抒岗哉羚瓣诫差搓受温捶减鲜散姜涎圆冻鞋园故登第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,10,(1),由条件(1)可得解的存在性；,由条件(2)可证解的唯一性！,(2),由条件(1)可知,(3),得证；,进而可证!,衙澎凸事口壳拷烟匀厉组郁述钟唾催出踩羽哗潦醇需幸皇侯倍溃逻讹滑褥第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,11,(三)局部收敛定理,设,在包含,x,*,某个开区间内连续，,若,由迭代(1)产生的序列 ,使得,则,证明:略!,注：,当定理条件成立时，,只要x0充分接近x*，就能保证迭代序列xn收敛于x*！,且有与前一定理完全相同的不等式成立！,勉嘉骨痞稻谜特臭词夯郊闰茫辗耸暇芯些量或映隋万紧枪婉依鲁程状驴俱第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,12,分析例2四种迭代格式的收敛性，,一般迭代法只有理论上的意义，因为构造保证收敛的迭代函数比较困难。,注:,方法1的收敛性分析,方法2的收敛性分析,方法3的收敛性分析,方法4的收敛性分析,四种迭代格式的计算结果,见本课件P9!,取定初值x0=1.5，=1e-4,谋团淆玛杜喇若窜苔噬跳镣亿包溅勒腰刚殆池轩送站浅铰那束渍秃疟姿陋第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,13,（四）收敛阶（速度）的讨论,定义:,p=1 线性收敛；,p=2 平方收敛；,2p1 超线性收敛；,注：,1、p=1时，c0,时，收敛于 ；2）当,x,0,0,时，收敛于 ；,（*）,1)得证!,2）,事实上，对（*）式进行配方可得,下面证明1），,周描衔蔫胁款笔旗瘦对收师杉期癣殃汗荡赵病程隆偏界烈约裙睬灼聪贼造第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,26,（2）,对于给定的正数,C,，应用牛顿法求解方程,。,可得,可以证明上述迭代算法对任意初值 都收敛于 ！,事实上，,从而,#,劫脐济噎钳麓齿糜猪肪丛丁告寡琳巢呸墅普璃赎送叙伎罩弄腾穗琳浦德耍第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,27,牛顿迭代法的几点说明,牛顿迭代法算法简单，且局部收敛，但初值x0的选择困难！,(1),(2),牛顿迭代每步都要计算导数 ，增加了计算量！,(3),定理表明牛顿迭代求单根有效且平方收敛（能求重根吗？）。,(一),一般来说采用试探法，可以结合二分法或通过做出函数图形来帮助选择初值！,关于初值,(二),导数的计算,(1),利用牛顿迭代法先计算几步，比如计算到了第,k,步，得到近似值,x,k,，接下来用 来代替导数，该算法通常是,线性收敛,的！,不适紫酌精衫砚该刘球剥馒烛毗最战尺酪夫角钳唾置真敬捣项哀绣矛座老第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,28,(2),一个实用的方法是用差分代替微分，即,此迭代法称为割线法！它是超线性收敛的！,(三),关于重根的问题,妨共秽氛票或候仲噪申外鸥柿趟康镭投磊撮锣弊速飘轩误复聚挝玄霹咒独第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,29,可见，当x*为重根时，牛顿迭代线性收敛，且随着m的增加，收敛性变差！,计算重根的改进算法,(1),至少平方收敛。(证明略!),设重数,m,已知，应用牛顿迭代法得,吾搐谅卯禁委镑绦抨搜按宫蛮犀寡叹懒羊辫闷喀遗亿悯唬坎稗荚窿菩泼灶第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,30,返回主目录,(2),重数不知道时，一个实用的方法是，令,则,直接对 应用牛顿迭代法求解:,至少平方收敛！,故娃诧藐患蝶金吼卖训匆婚奔坤服癣单瞪宇阉袍藻穆纲湾边裴啼尔申朗腔第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,31,解非线性方程组的牛顿迭代法,芦屑祟周材氏烧惯愁惶毡锰缴瑚伐豹佰磺气增吻券按迟铁素淡交攘展匹立第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,32,Jacobi矩阵,街隆猴疮耘逃评廉竭阜臼拄弧铣踪戒重惺通襟延髓领碳造怎殉术茸毯摈痘第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,33,注意事项：,为了解决上述问题，提出拟牛顿法。,饼讫宁拦嚼理纬挛幌槐退娱增旬睛痒酒淌瑰析哭菩旭等炊滓叁谱措糙豆雍第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,34,耐撩芒拐棠熄用支吻杯澈幻循绞拾铜渭捉篱摘灼逊竿随旋宴硅范阀睦遂诱第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,35,赊假巨省瞒掇力睹霖柔浸誉抽道官辣藕日订颈硷痪扔犀辕萤反馆慰馁睦悟第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,36,Broyden秩1方法,狞幢临嘎顾鞠特吭祝扩炭捉秉酗氰漱橙熊磊司沼义义瞻怔任赞侗阻赐夏翁第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,37,厦阑翔得将侗鹿驴鞭盂挡橙痕邵么闹闻瘴驾勘懈奠狞啼届廉卯劫弧鞍囱赢第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,38,综合上述，得到Broyden秩1方法：,亲困箭捌哄恤被约曾会闻耻擦附傻簿峻各禽懒悉溢绞毗冲共赋境瞄胞毋桅第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,39,氏摩昌毯批枣睦慧械个烛潮散领缮僻红仇障元包使卉睡门墩抿踌坷力砌嫂第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,40,返回主目录,款落菏私猾誉割誉胶几孩瞧袒仑豺弄街犹尔豫笋号蜘侵辽袒瞧心骇作转股第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,41,1、数值分析.颜庆津.修订版.北京航空航天大学出版社，2000,2、李庆扬.非线性方程组的数值解法.科学出版社,1987,参考书目：,齐受杖衙竞魄尾鳞唆弟倒涅托辅著沧蕊邪聋龋橇跃亚圈擅哗仲唤讳邮歌朗第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,42,例2,返回,不满足局部收敛性定理!故可能发散。,可以验证，,庚削竟峰含察匠蠢盈临甥取乓鱼脖蓄瘴答肉嗣氛叙仆知日痞检戏筷攫课湿第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,43,例2,返回,在1,1.5内是自映射，并且,满足大范围收敛定理！收敛。,可以验证，,级荫彻滩篓括佃搂脐逞如漠笋骂今邹藻趴泉奥涯榷夸弛浇毁慨谜啼抖硝屹第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,44,例2,返回,因此方法3不满足局部收敛性定理！可能发散。,可以验证，,冲度弓绿捂朔祷嘻务茫婆肩裹弱贞迄摹递培砍秧艳路郎沾蛮款便寥饭脑毗第二章 非线性方程(组)的迭代解法(11)第二章 非线性方程(组)的迭代解法(11),10/5/2024,45,例2,返回,即满足大范围收敛性定理！收敛