《计算方法 学习.pptx》由会员分享，可在线阅读，更多相关《计算方法 学习.pptx（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、解决的问题求方程f(x)=0的实根本章恒设f(x)连续第1页/共62页主要内容何谓数值解法根的存在性介值定理根的存在范围根的隔离根的精确化方法重点算法：对分法、迭代法和牛顿法第2页/共62页Step 1Step 2Step 3判断是否有根,确定根的存在范围；n次的代数方程最多有n个根，可能有一对共轭复根根的隔离，求隔根区间试值法、作图法、扫描法根的精确化对分法、迭代法、牛顿法、弦割法非线性方程的求解过程第3页/共62页2.2 根的隔离-试值法根据函数的性质，进行一些试算。根据函数的性质，进行一些试算。例例2.1 求方程求方程的隔根区间。的隔根区间。，其定义域为，其定义域为其导函数为其导函数为所
2、以当所以当时，时，函数单调上升；当，函数单调上升；当时，时，函数单调下降；当，函数单调下降；当时，时，解解 设设，函数单调上升。，函数单调上升。第4页/共62页试值法于是在每个区间上至多只有一个根。于是在每个区间上至多只有一个根。取几个特殊的点计算函数值，取几个特殊的点计算函数值，f(-4)=-40，f(-3)=1，f(-1)=5，f(0)=-8，f(2)=-4，f(3)=37 所以，隔根区间可取为所以，隔根区间可取为(-4,-3)、(-1,0)和和(2,3)。由于由于f(x)为三次多项式，至多有为三次多项式，至多有3个实根。个实根。因此方程因此方程f(x)=0所有的隔根区间为所有的隔根区间为
3、(-4,-3)、(-1,0)和和(2,3)。第5页/共62页的函数曲线f(x)=0所有的隔根区间为所有的隔根区间为(-4,-3)、(-1,0)和和(2,3)第6页/共62页2.2 根的隔离-作图法例例2.2 求方程求方程的隔根区间。的隔根区间。解解 ，当，当x0时，时，画出，画出的草图如图的草图如图2-1，从图中可大致确定隔根区间为从图中可大致确定隔根区间为(-2,-1)、(-1,1)和和(1,2)。第7页/共62页y=x3-3x-1的曲线图第8页/共62页2.2 根的隔离扫描法扫描法就是将有根区间等分为若干个子区间，然后逐个小区间检验是不是隔根区间，检验的办法就是判断区间端点的函数值是否异号
4、。连续函数的介值定理：第9页/共62页扫描法ab令令x=a,取步长取步长h，检验区间，检验区间x,x+h上是否有根上是否有根x+hxx,x+h为一隔根区间，继续看下一个区间是否有根为一隔根区间，继续看下一个区间是否有根x+2hx x+h直到直到xb为止为止第10页/共62页扫描法的算法(1)输入有根区间的端点输入有根区间的端点a,b及子区间长度及子区间长度h；(2)(3)若若，则，则；输出隔根区间；输出隔根区间(4)(5)若若xb-h/2，则返回，则返回(3)；否则结束。；否则结束。第11页/共62页扫描法的算法2、赋初值1、输入数据3、判断x,x+h内是否有根4、继续判断下一个区间输入有根区
5、间的端点a,b及子区间长度h 若若xc；(3)若若f(c)=0，则输出，则输出c，结束；，结束；否则若否则若，则，则否则否则(4)若若b-a=eps)c=(a+b)/2;if(f(c)=0)break;else if(f(a)*f(c)0)b=c;else a=c;printf(%f,c);第19页/共62页从一个初值从一个初值 x0 出发，计算出发，计算 x1=(x0),x2=(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x*使得使得 ，且，且 连续，则由连续，则由 可知可知 x*=(x*)，即，即x*是是 的不动点，也就是的不动点，也就是f 的根。的根。2.4 迭代法f(x
6、)=0 x=(x)等价变换等价变换f(x)的根的根(x)的不动点的不动点思思路路第20页/共62页迭代法举例(1)将方程将方程改写成等价形式改写成等价形式则迭代公式为则迭代公式为取初始近似值为取初始近似值为x0=1.5，迭代结果见下表。，迭代结果见下表。(k=0,1,2,)k1234xk2.37512.39651904.00286902441984由表可见，迭代是发散的。例例2.3 求方程求方程在在x0=1.5附近的根的近似值，精度要求为附近的根的近似值，精度要求为10-4。第21页/共62页迭代法举例例例2.3 求方程求方程在在x0=1.5附近的根的近似值，精度要求为附近的根的近似值，精度要
7、求为10-4。解解 (2)可将方程改写成等价形式可将方程改写成等价形式于是有迭代公式于是有迭代公式 (k=0,1,2,)将初值x0=1.5代入，可得迭代序列x1,x2,，第22页/共62页例2.3k123456xk1.357209 1.330861 1.325884 1.324939 1.324760 1.324726可见迭代法可见迭代法(2.4)是收敛的，是收敛的，就是满足精度要求的一个近似根。就是满足精度要求的一个近似根。取初值x0=1.5第23页/共62页迭代法的收敛性什么因素影响收敛？什么因素影响收敛？(x)(x)不同不同两种方法的区别？两种方法的区别？迭代收敛定理迭代收敛定理对于同一
8、个方程，不同的做法收敛性是不一样的，那么，收敛还是发散受什么条件的影响？两种做法主要的区别在什么地方？(x)满足什么条件会收敛？叙述证明思考思考第25页/共62页迭代收敛定理 定理2.1 设迭代函数满足时，(2)存在正数L1，对任意，均有则在a,b内存在唯一根，并且对任意初始值，迭代法 (k=0,1,2,)(1)当收敛于，且 分析定理：已知条件 结论 两个不等式代表的意义第27页/共62页定理分析 已知条件已知条件-迭代函数迭代函数(x)(x)有界（有界性）有界（有界性）迭代函数的导数有界，小于迭代函数的导数有界，小于1 1（压缩性）（压缩性）结论迭代收敛迭代收敛迭代序列的极限就是方程的根迭代
9、序列的极限就是方程的根两个不等式的意两个不等式的意义误差事后估计的依据误差事后估计的依据收敛速度和收敛速度和L L的关系的关系123第28页/共62页 证：证：先证根的存在性，先证根的存在性，由条件由条件(1)知，在区间知，在区间a,b上有上有 当当F(a)=0或或F(b)=0时，时，a或或b就是方程的根，否则有就是方程的根，否则有因因连续，所以连续，所以F(x)也连续，由连续函数性质可知，也连续，由连续函数性质可知，存在存在，使，使，即，即，于是，于是是方程的根。是方程的根。作辅助函数作辅助函数第30页/共62页可知，可知，F(x)在区间在区间a,b上上严格严格单调上升，所以单调上升，所以F
10、(x)在此区间上至多有一个根，根的唯一性得证。在此区间上至多有一个根，根的唯一性得证。再证根的唯一性。再证根的唯一性。第31页/共62页最后证明迭代序列的极限就是方程的根。由最后证明迭代序列的极限就是方程的根。由根据微分中值定理，必存在根据微分中值定理，必存在介于介于xk与与之间，及之间，及介于介于xk与与xk-1之间，使得之间，使得由条件由条件(2)知知(2.8)第32页/共62页于是于是整理可得整理可得此即此即(1)式。式。将上式代入将上式代入(2.6)式后，即得式后，即得此即此即(2.7)式。式。再反复利用再反复利用(2.8)式的第式的第2式，可得式，可得第33页/共62页由由可知必有可
11、知必有即即故迭代法收敛于方程的根得证。故迭代法收敛于方程的根得证。第34页/共62页构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有两个要素：1、等价形式(x)2、初值选取x0定理的应用第35页/共62页局部收敛定理迭代过程往往就在根的附近进行，只要假定在附近连续，且满足，则根据连续函数的性质，一定存在的某邻域S：，使得在S上满足定理2.1的条件，故在S中任取初始值x0，迭代公式必将收敛于方程的根这种收敛称为局部收敛。第36页/共62页关于不动点原理取一个浅盒和一张纸，纸恰好盖住盒内的底面。可想而知此时纸上的每个点与正在它下面的盒底上的那些点配成对。把这张纸拿起来，随机地揉成一个小
12、球，再把小球扔进盒里。拓扑学家已经证明，不管小球是怎样揉成的，也不管它落在盒底的什么地方，在揉成小球的纸上至少有一个这样的点，它恰好处在它盒底原来配对点的正上方。第37页/共62页迭代法的算法 (1)输入初始近似值x0，精度要求eps，控制最大迭代次数M；(3)当keps时做循环 ，(4)如果eps，则输出x1；否则输出迭代失败信息。(2)第38页/共62页xyy=xx*y=g(x)x0p0 x1p1 xyy=xx*y=g(x)x0p0 x1p1迭代法的几何意义第39页/共62页第40页/共62页第41页/共62页迭代法的加速（选学）如何加快迭代收敛的速度？根据不等式 知L越小，收敛速度越快加
13、快收敛速度的办法就是设法让L变小第42页/共62页迭代法的加速1 松弛法在x=(x)的两端同时加上x，得变形为：相当于根据迭代收敛定理，导数要尽可能地小，所以取第43页/共62页迭代法的加速这样，迭代公式变为：令则此即松弛法，不收敛的迭代函数，经加速后一般也能获得收敛。第44页/共62页迭代法的加速2 埃特金法（Altken）松弛法中计算导数不方便，用差商代替导数，用 代替得得迭代公式埃特金公式有时可能使一个本来不收敛的迭代格式获得收敛。第45页/共62页2.5 牛顿法将f(x)在初值处作Taylor展开取线性部分作为f(x)的近似，有：若，则有记为类似，我们可以得到xyx*x0第46页/共6
14、2页可以得到迭代序列Newton迭代的等价方程为：所以若f(x)在a处为单根，则所以，迭代格式收敛第47页/共62页收敛速度 定义2.1 设由迭代公式产生的迭代序列(k=0,1,2,)收敛于方程的根，记，若存在实数及非零常数c，使得 则称迭代过程是p阶收敛的。当p=1时，称为线性收敛；当p1时，称为超线性收敛；当p=2时，称为平方收敛。显然，p越大收敛速度越快。第48页/共62页简单迭代的收敛速度 由微分中值定理可知，必存在一点介于xk与之间，使得于是由此可知，简单迭代法至少是线性收敛的。第49页/共62页收敛速度函数在a处作Taylor展开若a为p重根，取迭代格式为：即牛顿迭代收敛速度快，格
15、式简单，应用广泛牛顿法的收敛速度第50页/共62页注：注：注：注：Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0注：牛顿法初值选择的规则：注：牛顿法初值选择的规则：f(x0)f(x0)0第52页/共62页第53页/共62页第54页/共62页第55页/共62页牛顿法举例例2.4 用牛顿法求 解 将求转化为求方程则相应的牛顿迭代公式为 (k=0,1,2,)(2.12)可选取任意大于的数，比如2作为根的初始近似值 的根可选取任意大于的数，比如2作为根的初始近似值 注：牛顿法初值选择的规则：注：牛顿法初值选择的规则：f(x)f(x)0第56页/共62页牛顿法求重根将重根变成另外一个方程的单根f(x)/f(x)=0第57页/共62页2.6 弦割法将Newton迭代中的导数，用差商代替，有格式是2步格式。收敛速度比Newton迭代慢x0 x1切线 割线 第58页/共62页双点弦割第59页/共62页单点弦割第60页/共62页第一次作业 2.7 证明计算的牛顿迭代公式为并用此迭代公式计算，精度要求为10-6。第61页/共62页感谢您的观看。第62页/共62页