非线性方程求根 (2).ppt
非线性方程求根现在学习的是第1页，共57页 则可用搜索法求有根区间.x 1 0 1 2f(x)的符号 +现在学习的是第2页，共57页方程根的数值计算大致可分三个步骤进行:(1)判定根的存在性。(2)确定根的分布范围,即将每一个根用区间隔离开来。(3)根的精确化,即根据根的初始近似值按某种方法逐步精确化,直至满足预先要求的精度为止。现在学习的是第3页，共57页 设f(x)为定义在某区间上的连续函数,方程(1.1)存在实根。虽然方程(1.1)的根的分布范围一般比较复杂,但我们不难将函数f(x)的定义域分成若干个只含一个实根的区间。例如考虑方程 x2-2x-1=0 由图7.1所示,该方程的一个负实根在-1和0之间,另一个正实根在2和3之间。现在学习的是第4页，共57页 图 7.1 现在学习的是第5页，共57页 这样,我们总可以假设方程(1.1)在(a,b)内有且仅有一个单实根x*。由连续函数的介值定理知 f(a)f(b)0 若数值b-a较小,那么我们可在(a,b)上任取一点x0作为方程的初始近似根。例如,方程 f(x)=x3-x-1=0 由 于 f(1)0,f(1.5)0,又 f(x)在 区 间(1,1.5)上单调连续,故可知在(1,1.5)内有且仅有一个实根。于是可取某个端点或区间内某一个点的值作为根的初始近似值。现在学习的是第6页，共57页 设函数f(x)在区间a,b上单调连续,且 f(a)f(b)0 则方程(1.1)在区间(a,b)内有且仅有一个实根x。现在学习的是第7页，共57页二、二分法二、二分法二分法简述.且有现在学习的是第8页，共57页 (1.3)对于确定的精度,从式(1.3)易求得需要二等分的次数k。二分法具有简单和易操作的优点。其计算步骤如下,框图如图7.2所示。现在学习的是第9页，共57页1.计算步骤 输入有根区间的端点a,b及预先给定的精度;(a+b)/2 x;若f(a)f(x)0,则x=b,转向;否则x=a,转向。若b-a,则输出方程满足精度的根x,结束;否则转向。现在学习的是第10页，共57页 图 7.2 现在学习的是第11页，共57页2.计算框图(见下页）例1 求方程 f(x)=x3-x-1=0在区间(1,1.5)内的根。要求用四位小数计算,精确到小数点后两位。解 这里a=1,b=1.5，取区间(1,1.5)的中点由于f(1)0,f(1.25)0,则令 a1=1.25,b1=1.5得到新的有根区间(1.25,1.5)如此重复二分下去，二分法的计算结果如下表现在学习的是第12页，共57页取x6=1.3242，误差限|x6-x*|0.5/(27)0.005,故x6即为所求近似根，实际上根x*=1.324717现在学习的是第13页，共57页二分法优点：计算简单，收敛性有保证；二分法缺点：收敛不够快，特别是精度要求高时，工作量大，而且不能够求复根及双重根。现在学习的是第14页，共57页2 2 迭代法迭代法一、不动点迭代一、不动点迭代现在学习的是第15页，共57页现在学习的是第16页，共57页 如果点列Pk趋向于点P*，则相应的迭代值xk收敛到所求根x*.现在学习的是第17页，共57页kxk012345671.51.357211.330861.325881.324941.324761.324731.32472现在学习的是第18页，共57页虽然迭代法的基本思想很简单,但效果并不总是令人满意的。对于上例,若按方程写成另一种等价形式 x=x3-1建立迭代公式 xk+1=x3k-1,k=0,1,2,仍取初始值x0=1.5,则迭代结果为 x1=2.375 x2=12.3976这种不收敛的迭代过程称作是发散的。如下图：现在学习的是第19页，共57页现在学习的是第20页，共57页二、不动点的存在性与迭代法的收敛性二、不动点的存在性与迭代法的收敛性证明 先证不动点存在性。若现在学习的是第21页，共57页现在学习的是第22页，共57页现在学习的是第23页，共57页现在学习的是第24页，共57页三、局部收敛性与收敛阶三、局部收敛性与收敛阶现在学习的是第25页，共57页证明证明 由连续函数的性质，存在x*的某个邻域R：|x-x*|，使对于任意x R成立|(x)|L1.此外，对于任意xR，总有(x)R，这是因为|(x)-x*|=|(x)-(x*)|L|x-x*|x-x*|.于是依据定理2可以断定迭代过程xk+1=(xk)对于任意初值x0 R均收敛.证毕.现在学习的是第26页，共57页kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123 x0 x1 x2 x3 2398721.521.521.751.734751.73263121.751.7321431.732051现在学习的是第27页，共57页现在学习的是第28页，共57页现在学习的是第29页，共57页3 3 迭代收敛的加速方法迭代收敛的加速方法一、埃特金加速收敛方法一、埃特金加速收敛方法现在学习的是第30页，共57页现在学习的是第31页，共57页二、斯蒂芬森迭代法二、斯蒂芬森迭代法现在学习的是第32页，共57页kxkykzk0123451.51.416291.355651.329851.324801.324722.375001.840921.491401.347101.3251812.39655.238882.317281.444351.32714说明说明:(2.2)不收敛,(3.3)可能收敛;(2.2)线性收敛,(3.3)平方收敛!现在学习的是第33页，共57页kxkykzk0123.53.734443.733073.604143.733813.662023.73347现在学习的是第34页，共57页4 4 牛顿法牛顿法一、牛顿法及其收敛性一、牛顿法及其收敛性现在学习的是第35页，共57页 牛顿法是非线性方程线性化的方法。其计算步骤为:给出初始近似根x0及精度。计算 若x1-x0,则转向;否则,转向。输出满足精度的根x1,结束。牛顿法的计算框图见图7.4。现在学习的是第36页，共57页图 7.4 现在学习的是第37页，共57页 牛顿法有明显的几何解释，方程f(x)=0的根x*可解释为曲线y=f(x)与x轴的交点的横坐标.设xk是跟x*的某个近似值,过曲线y=f(x)上横坐标为xk的点Pk引切线,并将该切线与x轴的交点的横坐标xk+1作为x*的新的近似值.注意到切线方程为 y=f(xk)+f(xk)(x-xk).这样求得的值xk+1必满足（4.1）式，从而就是牛顿公式（4.2）的计算结果.由于这种几何背景,牛顿法亦称为切线法.oxyx*X k+1Pky=f(x)X k现在学习的是第38页，共57页现在学习的是第39页，共57页二、牛顿法应用举例二、牛顿法应用举例kxk01230.50.571020.567160.56714kxk012341010.75000010.72383710.72380510.723805现在学习的是第40页，共57页三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法现在学习的是第41页，共57页kxkxkxk f(xk)012341.51.347831.325201.324720.617.9发散0.6 -1.3841.140625 -0.6566431.36181 0.18661.32628 0.006671.32472 0.0000086现在学习的是第42页，共57页四、重根情形四、重根情形现在学习的是第43页，共57页现在学习的是第44页，共57页kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562现在学习的是第45页，共57页5 5 弦截法弦截法现在学习的是第46页，共57页现在学习的是第47页，共57页现在学习的是第48页，共57页现在学习的是第49页，共57页kxk012340.50.60.565320.567090.56714解 设取x0=0.5,x1=0.6作为开始值，用弦截法求得的结果见表7-10，比较例题7牛顿法的计算结果可以看出，弦截法的收敛速度也使相当快得。现在学习的是第50页，共57页现在学习的是第51页，共57页例11 用抛物线法求解方程f(x)=xex-1=0.解 设用表7-10的前三个值x0=0.5，x1=0.6，x2=0.56532作为开始值计算得现在学习的是第52页，共57页6 6 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点1.求根问题的敏感性与病态代数方程现在学习的是第53页，共57页（a）良态（b）病态图（7-8）现在学习的是第54页，共57页 现在学习的是第55页，共57页现在学习的是第56页，共57页现在学习的是第57页，共57页
