数值计算方法No非线性方程求根.pptx

《数值计算方法No非线性方程求根.pptx》由会员分享，可在线阅读，更多相关《数值计算方法No非线性方程求根.pptx（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第二章 非线性方程求根 2.1 二分法 2.2 迭代法 2.3 牛顿迭代法与弦割法 2.4 迭代法的收敛阶与加速收敛方法第1页/共55页2本章要点本章主要介绍非线性方程求根方法,尤其是迭代法主要方法二分法、简单迭代法、Newton迭代法、SOR方法和Aitken加速方法P.本章作业第2页/共55页3有唯一根有多根所有根均为单根有重根然后在每个区间上判断是否有根 2.1 二分法第3页/共55页4若成立统计根的个数则所有的有根区间均为单根区间则继续对分区间,并重新判断直到找到所有根的所在区间然后在每个有根区间进行求根第4页/共55页5可得一系列的小区间和中点第5页/共55页6小区间中点显然每个小

2、区间都有单根搜索法二分法第6页/共55页7例8.解:由于可知方程的解在区间0,10内将区间0,10等分成三等份0,3.333.33,6.676.67,100,3.33内至少有一个根第7页/共55页85,6.673.33,5将3.33,6.67再分成两个区间5,6.67内至少有一个根3.33,5内至少有一个根0,3.335,6.673.33,5因此找到了三个有单根的区间依此类推结果为对分第8页/共55页9 2.2 迭代法方程是在科学研究中不可缺少的工具方程求解是科学计算中一个重要的研究对象几百年前就已经找到了代数方程中二次至五次方程的求解公式但是,对于更高次数的代数方程目前仍无有效的精确解法对于

3、无规律的非代数方程的求解也无精确解法因此,研究非线性方程的数值解法成为必然第9页/共55页10设非线性方程-(1)本节主要研究单根区间上的求解方法第10页/共55页11一、简单迭代法(基本迭代法)-(2)将非线性方程(1)化为一个同解方程继续-(3)称(3)式为求解非线性方程(2)的简单迭代法第11页/共55页12则称迭代法(3)收敛,否则称为发散-(4)如果将(2)式表示为与方程(2)同解收敛第12页/共55页13例1.解:(1)将原方程化为等价方程发散第13页/共55页14显然迭代法发散(2)如果将原方程化为等价方程第14页/共55页15仍取初值x2=0.9644x3=0.9940 x4=

4、0.9990 x5=0.9998x6=1.0000 x7=1.0000依此类推,得已经收敛,故原方程的解为同样的方程不同的迭代格式有不同的结果什么形式的迭代法 能够收敛呢?迭代函数的构造有关第15页/共55页16定理1.-(5)-(6)-(7)(局部收敛性)第16页/共55页17证:由条件(1)由根的存在定理,由第17页/共55页18由微分中值定理第18页/共55页19证毕.第19页/共55页20定理1指出,由(6)式,只要因此,当迭代就可以终止,只要构造的迭代函数满足此时虽收敛但不 一定是唯一根-(8)第20页/共55页21例2.用迭代法求方程的近似解,精确到小数点后6位解:本题迭代函数有两

5、种构造形式因此采用迭代函数第21页/共55页22d1=0.1000000d2=-0.0105171d3=0.1156e-002d4=-0.1265e-003d5=0.1390e-004d6=-0.1500e-005d7=0.1000e-006由于|d7|=0.1000e-0061e-6因此原方程的解为x7=0.090525x1=0.1000000 x2=0.0894829x3=0.0906391x4=0.0905126x5=0.0905265x6=0.0905250 x7=0.0905251第22页/共55页23由定理1的(7)式出,迭代法收敛就越快定义1.-(9)第23页/共55页24不可能

6、直接确定第24页/共55页25定理2.第25页/共55页26例3.为线性收敛证明:所以第26页/共55页27例4.至少是平方收敛的由定义1第27页/共55页28注意例4与例3的迭代法是相同的,两例有何区别?证明:令则所以由定理2该迭代法至少是平方收敛的第28页/共55页29如果将非线性方程令化为等价方程如果令即则 2.3 Newton迭代法一、Newton迭代法第29页/共55页30于是取-(10)-(11)-(12)(12)式称为Newton迭代法参见例4，可知Newton迭代法至少平方收敛局部收敛性第30页/共55页31例5.用Newton迭代法求方程的根:解:由Newton迭代法x0=0

7、.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553迭代四次精度达10-8 Newtonddf.m第31页/共55页32Newton迭代法需要求每个迭代点处的导数复杂！-(12)-(13)这种格式称为简化Newton迭代法精度稍低二、Newton迭代法的变形弦割法第32页/共55页33则Newton迭代法变为-(14)这种格式称为弦割(截)法收敛阶约为1.618几何意义第33页/共55页34例6.用简化Newton法和弦截法解例(5)中方程的根，解:由简化Newton法并和Newton 迭代法比较由弦截法Newtondd

8、f.m第34页/共55页35x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550 x7=0.3472959759x8=0.3472964208x9=0.3472963440 x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553简化Newton法由弦截法要达到精度10-8

9、 简化Newton法迭代11次弦截法迭代5次Newton迭代法迭代4次第35页/共55页36无论前面哪种迭代法：Newton迭代法简化Newton法弦截法Newton迭代法x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收敛均与初值的位置有关如x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.9631e-010 x5=0收敛发散第36页/共55页37-(15)这种方法称为Newton下山法，第37页/共55页38例7.解:1.先用Newton迭代法x4=9.70724 x5=6.54091 x6=4.46497 x7=3.13384

10、x8=2.32607 x9=1.90230 x10=1.75248x11=1.73240 x12=1.73205x13=1.73205迭代13次才达到精度要求Newtonddf.m第38页/共55页392.用Newton下山法,结果如下k=0 x0=-0.99 fx0=0.666567k=1 x1=32.505829 f(x)=11416.4 w=0.5 x1=15.757915 f(x)=1288.5 w=0.25 x1=7.383958 f(x)=126.8 w=0.125 x1=3.196979 f(x)=7.69 w=0.0625 x1=1.103489 f(x)=-0.655k=2

11、x2=4.115071 f(x)=19.1 w=0.5 x2=2.60928 f(x)=3.31 w=0.25 x2=1.85638 f(x)=0.27k=3 x3=1.74352 f(x)=0.023k=4 x4=1.73216 f(x)=0.00024k=5 x5=1.73205 f(x)=0.00000k=6 x6=1.73205 f(x)=0.000000第39页/共55页40考虑方程fc4.m和dfc4.mNewtonddf.m实验：第40页/共55页41 2.4 迭代法的加速解非线性方程Newton系列迭代法都涉及到收敛速度问题如何加快迭代法的速度呢？也涉及到初值的选取问题如何改善

12、迭代法的适用范围呢？第41页/共55页42非线性方程迭代法的加速对于迭代法上式的迭代函数令迭代改变量即求导并令-(9)第42页/共55页43得因此有松弛迭代法:-(10)从后面的例子可以看出,加速效果是明显的甚至一些不收敛的迭代法经过松弛加速后也能收敛第43页/共55页44不方便中值定理差商近似代替导数即第44页/共55页45于是可以得到迭代格式:其中-(11)上组公式称为Altken公式或Altken加速第45页/共55页46将(11)式综合后可得一个解析式表示的迭代法:-(12)上式称为Steffensen迭代法Altken公式与Steffensen公式是等价的加速效果也是很明显的例2中将

13、比较不同加速方法第46页/共55页47例2.对迭代格式进行加速解方程组解:x0=0.5x1=0.375x2=0.3509115x3=0.3477369x4=0.3473496x5=0.3473028x6=0.3472971x7=0.3472964(1)直接使用迭代格式迭代7次,得到满足精度的解第47页/共55页48(2)对迭代格式进行松弛加速x0=0.5x1=0.3333333x2=0.3472222x3=0.3472964x4=0.3472964迭代4次,得到满足精度的解第48页/共55页49(3)对迭代格式进行Altken加速(11)式x0=0.5x1=0.3451613x2=0.3472

14、961x3=0.3472964迭代3次,得到满足精度的解从以上3种结果可见,迭代法加速技术效果比较明显迭代格式显然不收敛第49页/共55页50 x0=1.5x1=1.5350706x2=1.5321124x3=1.5320889x4=1.5320889迭代4次,得到满足精度的解对迭代格式进行松弛加速x=1.5x=1.5333333x=1.5320906x=1.5320889x=1.5320889迭代4次,得到满足精度的解对迭代格式进行Altken加速可见加速技术可能将不收敛的迭代法加速为收敛第50页/共55页51主讲：鲜思东重庆邮电学院附、多根区间上的逐次逼近法有唯一根有多根所有根均为单根有重根用迭代法求解然后在每个区间上判断是否有根第51页/共55页52主讲：鲜思东重庆邮电学院故有且由例3.对于Newton迭代法趋于零Newton迭代法也只是线性收敛此时Newton迭代法可能不收敛第52页/共55页53主讲：鲜思东重庆邮电学院考察函数而应该用定义求导Tailor展开第53页/共55页54主讲：鲜思东重庆邮电学院所以由定理2，迭代法至少是二阶收敛第54页/共55页55主讲：鲜思东重庆邮电学院感谢您的观看。第55页/共55页