第七章 非线性方程求根优秀PPT.ppt
第七章 非线性方程求根现在学习的是第1页，共33页求根问题包括下面三个问题：求根问题包括下面三个问题：根的存在性：即根的存在性：即f f(x x)=0)=0有没有根？若有，有几有没有根？若有，有几个根？个根？哪儿有根？确定有根区间哪儿有根？确定有根区间 根的精确化：已知一个根的近似值后，能否将它根的精确化：已知一个根的近似值后，能否将它精确到足够精度？精确到足够精度？本章假设本章假设 f f CCa a,b b，且，且 f f(a a)f f(b b)0)0，则，则 f f 在在(a a,b b)上至少有一根，上至少有一根，(a,b)(a,b)即为有根即为有根区间。问题区间。问题1 1、2 2得到解决。得到解决。现在学习的是第2页，共33页2.1 根的搜索根的搜索 1.逐步搜索法逐步搜索法设设f(a)0，有根区间为，有根区间为(a,b)，从，从x0=a出发，出发，按某个预定按某个预定步长步长(例如例如h=(b-a)/N)一步一步向一步一步向右跨，每跨一步进行一次根的搜右跨，每跨一步进行一次根的搜索，即判别索，即判别f(xk)=f(a+kh)的符号，的符号，若若f(xk)0(而而f(xk-1)0),则有根区间则有根区间缩小为缩小为xk-1,xk(若若f(xk)=0，xk即为即为所求根所求根),然后从然后从xk-1出发，把搜索出发，把搜索步长再缩小，重复上面步骤，直到步长再缩小，重复上面步骤，直到满足精度：满足精度：|xk-xk-1|为止，此时取为止，此时取x*(xk+xk-1)/2作为近似根。作为近似根。无法求复根及偶重根无法求复根及偶重根 计算量大，收敛慢计算量大，收敛慢 简单简单;对对f(x)要求不高要求不高 (只要连续即可只要连续即可).x0=abxk-1xkx*鉴赏鉴赏:现在学习的是第3页，共33页 2.二分法二分法 /*Bisection Method*/(逐步搜索法的改进逐步搜索法的改进)设设f(x)的有根区间为的有根区间为a,b=a0,b0,f(a)0.将将a0,b0,对分，中点对分，中点x0=(a0+b0)/2),计算计算f(x0),若若f(x0)=0,x*=x0 0,有根区间有根区间:a1,b1=a,x0对对a1,b1对分，如此反复进行，得到一系列有根区间：对分，如此反复进行，得到一系列有根区间：f(ak)0,f(bk)0,f(x*)=lim f(ak)=lim f(bk)abx1x2x*现在学习的是第4页，共33页When to stop?取xk=(ak+bk)/2 (ak,bk的中点)，显然有 limxk=x*.算法和收敛性说明算法和收敛性说明。或或不能保证不能保证 xk的精度的精度abx1x2x*2xkx*现在学习的是第5页，共33页第第1步产生的步产生的有误差有误差第第 k 步产生的步产生的 xk 有误差有误差对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：简单，总收敛简单，总收敛;对对f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 误差分析误差分析鉴赏鉴赏:现在学习的是第6页，共33页步步1 给出精度给出精度eps;计算计算f(a),f(b);k:=1;步步2 二分二分 计算计算步步3 判断判断 若若 则则 是根，是根，计算结束计算结束.否则否则,检验检验:若若 ,则有根区间则有根区间为为 ,令令 否则有根区间为否则有根区间为 ,令令步步4 若若 ,输出输出 作为所求的作为所求的根根.否则否则,k:=k+1,转步转步2.算法算法现在学习的是第7页，共33页2.2 迭代法迭代法f(x)=0 x=g(x)等价变换等价变换f(x)的根的根g(x)的不动点的不动点思思路路从一个初值从一个初值 x0 出发，计算出发，计算 x1=g(x0),x2=g(x1),xk+1=g(xk),若若 收敛，即存在收敛，即存在 x*使得使得 ，且，且 g 连续，则由连续，则由 可可知知 x*=g(x*)，即，即x*是是 g 的不动点，也就是的不动点，也就是f 的根。的根。现在学习的是第8页，共33页迭代法的基本步骤如下：迭代法的基本步骤如下：1、给出方程的局部等价形式、给出方程的局部等价形式2、取合适的初值，产生迭代序列、取合适的初值，产生迭代序列3、求极限、求极限易知，该值为方程的根易知，该值为方程的根一定收敛吗？现在学习的是第9页，共33页 迭代过程的几何表示 O x*x2 x1 x0 xy现在学习的是第10页，共33页xyy=xx*y=g(x)x0p0 x1p1 xyy=xx*y=g(x)x0p0 x1p1现在学习的是第11页，共33页现在学习的是第12页，共33页若满足：若满足：1、2、可导，且存在正数可导，且存在正数L11时称为超线性收敛时称为超线性收敛,p p=2=2时称为平方收敛时称为平方收敛.现在学习的是第20页，共33页定理定理 迭代过程迭代过程 ,若若 在所求根在所求根 的的邻近连续邻近连续,并且并且则迭代过程在则迭代过程在 邻近是邻近是p阶收敛收敛的阶收敛收敛的.根据 ,知迭代具有局部收敛性.利用泰勒展开,得到于是有现在学习的是第21页，共33页Newton 法的收敛速度法的收敛速度函数在a处作Taylor展开若a为m重根，取迭代格式为：即假定假定 是是f(x)的一个单根的一个单根,Newton迭代法在根迭代法在根 的邻近是平方收敛的的邻近是平方收敛的.重根情形重根情形Newton仍收敛仍收敛,但只是线性收敛但只是线性收敛,改为改为(*)法是法是2阶收敛的阶收敛的.(*)现在学习的是第22页，共33页鉴赏Newton迭代法 优点优点:算法简单算法简单,求单根时平方收敛求单根时平方收敛,收敛速度收敛速度 快快.是求是求解非线性方程的有效方法之一解非线性方程的有效方法之一.缺点缺点:局部收敛局部收敛,收敛性依赖于初值的选取收敛性依赖于初值的选取,每次迭代均需计算函数值与导数值每次迭代均需计算函数值与导数值.故计算量较大故计算量较大.而而且当导数值提供有困难时，且当导数值提供有困难时，Newton法无法进行。法无法进行。现在学习的是第23页，共33页 例例 用用NewtonNewton迭代法求方程迭代法求方程xex-1=0-1=0在在0.50.5附近的根附近的根,精度要精度要求求=10=10-5-5.解解 NewtonNewton迭代格式为迭代格式为kxk(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.00000000现在学习的是第24页，共33页现在学习的是第25页，共33页注：注：注：注：Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0现在学习的是第26页，共33页小结小结(1)(1)当当f(x)充分光滑且充分光滑且 x*是是f(x)=0的单根时，的单根时，牛顿法在牛顿法在x*的附近至少的附近至少是平方收敛的。是平方收敛的。(2)(2)当当f(x)充分光滑且充分光滑且 x*是是f(x)=0的重根时，的重根时，牛顿法在牛顿法在x*的附近的附近是线性收敛的。是线性收敛的。(3)Newton(3)Newton法在区间法在区间a,b上的收敛性依赖于初上的收敛性依赖于初值值x0 0 的选取。的选取。现在学习的是第27页，共33页2.4 弦截法弦截法将将Newton迭代中的导数，用差商代替，有格式迭代中的导数，用差商代替，有格式这是这是2步格式步格式.超线性收敛超线性收敛,收敛阶收敛阶1.618,收敛速度比收敛速度比Newton迭代慢迭代慢.x0 x1切线切线 割线割线 现在学习的是第28页，共33页鉴赏鉴赏割线法与切线法割线法与切线法 割线法与切线法都是线性化方法割线法与切线法都是线性化方法,几何意义明显几何意义明显,算法程序简单算法程序简单,局局部收敛部收敛,收敛速度快收敛速度快.二者有本质区别二者有本质区别:切线法是单点迭代切线法是单点迭代,割线法是两点迭代法割线法是两点迭代法,计算时必计算时必须先给出两个初始值须先给出两个初始值.割线法收敛阶割线法收敛阶p=1.618,切线法收敛阶切线法收敛阶p=2.但割线法但割线法不需要计算不需要计算导数值导数值.现在学习的是第29页，共33页2.52.5解非线性方程组的牛顿法简介解非线性方程组的牛顿法简介将非线性方程组线性化，得到：将非线性方程组线性化，得到：现在学习的是第30页，共33页其中F(xk)为F(x)在xk处的Jacobi矩阵：现在学习的是第31页，共33页例：用牛顿法解方程组现在学习的是第32页，共33页取初始值（1，1，1），计算如下N x y z0 1.0000000 1.0000000 1.0000000012.1893260 1.5984751 1.393900621.8505896 1.4442514 1.278224031.7801611 1.4244359 1.239292441.7776747 1.4239609 1.237473851.7776719 1.4239605 1.237471161.7776719 1.4239605 1.2374711现在学习的是第33页，共33页
