解非线性方程省公共课一等奖全国赛课获奖课件.pptx

4.4 非线性方程牛顿法非线性方程牛顿法(Newton Method of Nonlinear Equations)内容提要（内容提要（Outline)牛顿法及其几何意义牛顿法及其几何意义 收敛性及其收敛速度收敛性及其收敛速度 计算实例及其程序演示计算实例及其程序演示第1页取取x0 0作为初始近似值作为初始近似值，将将 f(x)在在x0 0做做TaylorTaylor展开展开:重复上述过程重复上述过程 作为第一次近似值作为第一次近似值一、牛顿法及其几何意义一、牛顿法及其几何意义Newton迭代公式迭代公式基本思绪：基本思绪：将非线性方程将非线性方程 f(x)=0 线性化线性化第2页牛顿法几何意义牛顿法几何意义xyx*x0 x 1x 2牛顿法也称为切线法牛顿法也称为切线法,迭代函数迭代函数第3页（局部收敛性定理局部收敛性定理）设设 f(x)C2a,b，若若 x*为为 f(x)在在a,b上根上根,且且 f (x*)0，则存在则存在 x*邻域邻域 使使得任取初始值得任取初始值 ，Newton 法产生序列法产生序列 xk 收敛到收敛到 x*，且满足且满足最少平方收敛最少平方收敛二、牛顿法收敛性与收敛速度二、牛顿法收敛性与收敛速度定理定理4.4.1 第4页在在x*附近附近收敛收敛由由Taylor 展开：展开：令令k，由由 f (x*)0，即可得结论。即可得结论。证实：证实：Newton法法实际上是一个特殊迭代法实际上是一个特殊迭代法迭代函数为：迭代函数为：第5页思索题思索题1 若若 ，Newton法法是否仍收敛？是否仍收敛？设设 x*是是 f m 重根，则令：重根，则令：且且Answer1:有局部收敛性有局部收敛性第6页Answer2:线性收敛线性收敛思索题思索题2当当x*是是 f(x)=0m重根重根,是否平方收敛？是否平方收敛？第7页结论：结论：结论：结论：Newton法收敛性依赖于法收敛性依赖于x0 选取。选取。局部收敛定理对初始值局部收敛定理对初始值 x0 要求较高。要求较高。x*x0 x0 x0 第8页有根有根根唯一根唯一 (全局收敛性定理全局收敛性定理):设设 f(x)C2a,b,若若(1)f(a)f(b)0；则由则由Newton法产生序列法产生序列 xk 单调地收敛到单调地收敛到f(x)=0 在在 a,b 唯一根唯一根x*,且收敛速度最少是二阶且收敛速度最少是二阶确保确保产生序列产生序列xk单调有界单调有界确保确保Newton迭迭代函数代函数将将a,b映射于本身映射于本身定理定理4.4.2 第9页将将f(x*)在在 xk 处作处作TaylorTaylor展开展开对迭代公式两边取极限，得对迭代公式两边取极限，得证实：证实：证实：证实：以以为例证实为例证实 说明数列说明数列 xk 有下界有下界故故xk单调递减单调递减,从而从而xk收敛收敛.令令？第10页定理定理4.4.3 (全局收敛性定理全局收敛性定理):设设 f(x)C2a,b,若若(1)f(a)f(b)0；(2)在整个在整个a,b上上 f (x)0,f (x)0；(3)则对任何则对任何 ,Newton 迭代格式产生序列迭代格式产生序列 都收敛于都收敛于f(x)=0 根根 x*.注注:定理条件定理条件(3)确保了从确保了从 x*两侧任取两侧任取 x0,所得到数所得到数列列 xk 均在均在a,b内内.第11页三、三、计算实例及其程序演示计算实例及其程序演示辅助工具辅助工具:VC VC程序设计语言程序设计语言 Matlab Matlab数学软件数学软件第12页(1)(1)选定初值选定初值x0,计算计算f(x0),f (x0)计算步骤计算步骤(2)(2)按公式按公式 迭代迭代 得新近似值得新近似值xk+1 (3)(3)对于给定允许精度对于给定允许精度，假如假如 则终止迭代，取则终止迭代，取 ;不然不然k=k+1，再转再转 步骤步骤(2)(2)计算计算允许精度允许精度最大迭代次最大迭代次数数迭代信息迭代信息第13页例例1 1：用用Newton法求方程法求方程 根根,要求要求 迭代格式一：迭代格式一：迭代格式二：迭代格式二：取初值取初值 x00.0,0.0,计算以下：计算以下：对迭代格式一对迭代格式一:the iterative number is 27,the numerical solution is 0.442852706对迭代格式二对迭代格式二:the iterative number is 3,the numerical solution is 0.442854401解：解：第14页第15页例题例题2求函数求函数 正实根正实根精度要求：精度要求：从图形中我们能够从图形中我们能够看出：看出：在在x=7和和 x=8 之间有一单根；之间有一单根；在在x=1和和x=2 之之间有一重根。间有一重根。用用MatlabMatlab画图，查看根分布情形画图，查看根分布情形第16页初值初值x08.0 时,计算是单根计算是单根,The iterative number is 28,The numerical solution is 7.600001481初值初值x01.0,计算是重根计算是重根,The iterative number is 1356,The numerical solution is 1.198631981取初值取初值x08.0,用牛顿迭代公式计算以下：用牛顿迭代公式计算以下：取初值取初值x01.0,用牛顿迭代公式计算以下：用牛顿迭代公式计算以下：第17页小小 结结(1)当当f(x)充分光滑且充分光滑且 x*是是f(x)=0单根时，牛顿单根时，牛顿法在法在 x*附近最少附近最少是平方收敛。是平方收敛。(2)当当f(x)充分光滑且充分光滑且 x*是是f(x)=0重根时，牛顿重根时，牛顿法在法在 x*附近附近是线性收敛。是线性收敛。(3)Newton法在区间法在区间a,b上收敛性依赖于初值上收敛性依赖于初值x0 选取。选取。(4)Newton法突出优点：收敛速度快法突出优点：收敛速度快 缺点：需计算函数导数。缺点：需计算函数导数。第18页四四 重根情形重根情形NewtonNewton迭代法迭代法重根情形重根情形NewtonNewton迭代法是线性收敛迭代法是线性收敛,且有且有由此易知若迭代函数为：由此易知若迭代函数为：则则NewtonNewton迭代格式迭代格式 为平方收敛为平方收敛.但但 m 通常未知通常未知,故惯用修改方法：故惯用修改方法：令令若若x*为为f(x)m重根重根,则则x*为为u(x)=0单根单根,第19页取取则得则得:此格式二阶收敛此格式二阶收敛,但要计算二阶导数但要计算二阶导数.第20页4.5 弦截法与抛物线法弦截法与抛物线法 一、一、单点弦截法单点弦截法 固定一点固定一点 P0(x0,f(x0),用差商用差商 代替代替Newton公式中公式中 ,则得离散化公式则得离散化公式:称为单点弦截法称为单点弦截法,是一个简单迭代法是一个简单迭代法.几何意义几何意义:依次用弦线代替曲线依次用弦线代替曲线,用线性函数零点作为用线性函数零点作为f(x)零零点近似值点近似值.第21页定理定理4.5.1 设设 f(x)在在a,b上满足：上满足：(1)f(a)f(b)0;(2)在在a,b上连续且不变号上连续且不变号;(3)选取初始值选取初始值 ,使得使得 ,选选 定定a,b中一个中一个,另一个为另一个为 .则由迭代格式则由迭代格式 所产生序列所产生序列 xk 单调地收敛于单调地收敛于f(x)=0在在a,b上唯一根上唯一根 x*,且收敛速度是线性且收敛速度是线性.第22页二、二、双点弦截法双点弦截法 若若 用差商用差商 代替代替Newton公式中公式中 ,则得公式则得公式:称为双点弦截法称为双点弦截法.注：注：双点弦截法与前面介绍迭代法有显著区分双点弦截法与前面介绍迭代法有显著区分,前面所讲述前面所讲述迭代法计算迭代法计算 xk+1时只用到时只用到 xk,故称为单步迭代故称为单步迭代;而双点弦截法而双点弦截法计算计算 xk+1时时,却同时用到前面两步结果却同时用到前面两步结果 xk-1和和 xk,故称为多步故称为多步迭代迭代.说明：说明：单点弦截是双点弦截特殊情况单点弦截是双点弦截特殊情况.第23页几何解释：几何解释：xyx*xk-1xkxk+1Pk-1PkPk+1为为 斜率斜率直线方程为：直线方程为：定理定理4.5.2 (局部收敛定理局部收敛定理)设设 f(x)=0,假如：假如：(1)f(x)在根在根 x*某个领域内有连续二阶导数某个领域内有连续二阶导数,且且(2)任取任取 属于该领域属于该领域;则由双点弦截公式所得序列则由双点弦截公式所得序列 收敛于根收敛于根 x*,且收敛速度且收敛速度 第24页定理定理4.5.2 (全局性收敛定理全局性收敛定理)设设 f(x)C2a,b,且且 (1)f(a)f(b)0；(2)在整个在整个a,b上上 f (x)0,f (x)0；(3)则则 由双点弦截公式所得序列由双点弦截公式所得序列 收敛于收敛于 f(x)=0 唯一根唯一根 x*.例例1：用用单点弦截和双点弦截求方程单点弦截和双点弦截求方程 在在2,3内特殊情况内特殊情况.解解:(1)单点弦截法单点弦截法取取 ，单点弦截公式为：单点弦截公式为：第25页(2)双点弦截法双点弦截法取取 ，双点弦截公式为：双点弦截公式为：三、弦截法与三、弦截法与Aitken迭代法联络迭代法联络 设设对于对于 在在 和和 两两点处使用弦截法点处使用弦截法,则得则得即为即为Aitken迭代公式迭代公式第26页四、抛物线法四、抛物线法 若用过三点若用过三点 和和 抛物线抛物线与与x 轴交点横坐标作为轴交点横坐标作为 xk+1,则得抛物线法或则得抛物线法或Mlller方法方法.一条抛物线有两个实零点时一条抛物线有两个实零点时,取与取与 xk 较近那个零点作为较近那个零点作为xk+1.第27页4.5 非线性方程组迭代算法非线性方程组迭代算法一、不动点迭代格式一、不动点迭代格式(简单迭代格式简单迭代格式)取初值取初值 代入计算即可代入计算即可.二、二、Newton迭代格式迭代格式第28页将非线性方程组线性化：将非线性方程组线性化：设设 为为 第第k 次近似解次近似解,由由Taylor公公式得式得用线性方程组用线性方程组即即近似代替近似代替 ,用用(*)解作为解作为 第第k+1次近似解次近似解,则得则得Newton迭代格式：迭代格式：第29页这里这里第30页例：例：用牛顿法解方程组用牛顿法解方程组第31页取初始值取初始值(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第32页练习：练习：3.3.Newton Newton 迭代法是怎样推出迭代法是怎样推出?它若在单根附近收敛它若在单根附近收敛,是几阶收敛是几阶收敛?在重根附近是几阶收敛？求方程重根时在重根附近是几阶收敛？求方程重根时,能到达能到达2 2阶收敛改进阶收敛改进 Newton Newton 迭代公式是什么迭代公式是什么1.1.用牛顿法求方程用牛顿法求方程 在区间在区间 1 1，2 2 内内2.2.一个实根，要求一个实根，要求2.2.导出求立方根导出求立方根 迭代公式，并讨论其收敛性。迭代公式，并讨论其收敛性。第33页首先导出求根方程首先导出求根方程 ，再对，再对 使用牛顿法使用牛顿法得迭代公式得迭代公式 ,用全局收敛性定理或局部收用全局收敛性定理或局部收敛性定理讨论其收敛性。敛性定理讨论其收敛性。第34页