非线性方程的牛顿法.pptx

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

1、内容提纲（内容提纲（Outline)Outline)牛顿法及其几何意义牛顿法及其几何意义 收敛性及其收敛速度收敛性及其收敛速度 计算实例及其程序演示计算实例及其程序演示第1页/共35页取取x0 0作为初始近似值作为初始近似值，将将f(x)在在x x0 0做做TaylorTaylor展开展开:重复上述过程重复上述过程 作为第一次近似值作为第一次近似值一、牛顿法及其几何意义一、牛顿法及其几何意义Newton迭代公式迭代公式基本思路：基本思路：将非线性方程将非线性方程f(x)=0 线性化线性化第2页/共35页牛顿法的几何意义牛顿法的几何意义xyx*x0 x 1x 2牛顿法也称为切线法牛顿法也称为切线

2、法第3页/共35页（局部收敛性定理局部收敛性定理）设设 f(x)C2a,b，若若 x*为为 f(x)在在a,b上的根上的根,且且 f (x*)0，则存在则存在 x*的邻域的邻域 使得任取初始值使得任取初始值 ，Newton 法产生的序列法产生的序列 xk 收敛到收敛到 x*，且满足且满足至少平方收敛至少平方收敛二、牛顿法的收敛性与收敛速度二、牛顿法的收敛性与收敛速度第4页/共35页在在x*的附近的附近收敛收敛由由Taylor 展开：展开：令令k，由由 f (x*)0，即可得结论。即可得结论。证明：证明：Newton法法实际上是一种特殊的迭代法实际上是一种特殊的迭代法第5页/共35页思考题思考题

3、1 若若 ，Newton法法是否仍收敛？是否仍收敛？设设 x*是是 f 的的 m 重根，则令：重根，则令：且且Answer1:有局部收敛性有局部收敛性第6页/共35页Answer2:线性收敛线性收敛思考题思考题2当当x*是是 f(x)=0的的m重根重根,是否平方收敛？是否平方收敛？第7页/共35页注：注：注：注：Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0 第8页/共35页有根有根根唯一根唯一全局收敛性定理全局收敛性定理(定理定理4.7)：设设 f(x)C2a,b，若若(1)f(a)f(b)0；则由则由Newton法产生的序列法产生的序列 xk 单调地

4、收敛到单调地收敛到f(x)=0 在在 a,b 的唯一根的唯一根x*,且收敛速度至少是二阶且收敛速度至少是二阶的的保证保证产生的序列产生的序列xk单调有界单调有界保证保证Newton迭迭代函数代函数将将a,b映映射于自身射于自身第9页/共35页第10页/共35页将将f(x*)在在 xk 处作处作TaylorTaylor展开展开对迭代公式两边取极限，得对迭代公式两边取极限，得证明：证明：以为例证明 说明数列说明数列 xk 有下界有下界故故 xk 单调递减单调递减,从而从而 xk 收敛收敛.令令？第11页/共35页三、三、计算实例及其程序演示计算实例及其程序演示辅助工具辅助工具:VCVC程序设计语言

5、程序设计语言MatlabMatlab数学软件数学软件第12页/共35页(1)(1)选定初值选定初值x0,计算计算f(x0),f (x0)计算步骤计算步骤(2)(2)按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 (3)(3)对于给定的允许精度对于给定的允许精度，如果如果 则终止迭代，取则终止迭代，取 ;否则否则k=k+1，再转再转 步骤步骤(2)(2)计算计算允许精度允许精度最大迭代最大迭代次数次数迭代信息迭代信息第13页/共35页例题例题1用用NewtonNewton法求方程法求方程 的根的根,要求要求迭代格式一：迭代格式一：迭代格式二：迭代格式二：取初值取初值x x0 00.00

6、.0,计算如下：计算如下：对迭代格式一对迭代格式一:the iterative number is 27,the numerical solution is 0.442852706对迭代格式二对迭代格式二:the iterative number is 3,the numerical solution is 0.442854401第14页/共35页例题例题2 2求函数求函数 的正实根的正实根精度要求：精度要求：从图形中我们可以从图形中我们可以看出：看出：在在x=7和和x=8 之之间有一单根；间有一单根；在在x=1和和x=2 之之间有一重根。间有一重根。用用MatlabMatlab画图，查看根的

7、分布情形画图，查看根的分布情形第15页/共35页初值初值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第16页/共35页例3:设C为正实数,导出用牛顿法求 的公式,并证明解：设 ，则 于是有由于 所以在 内有一正根.又在 内,根据定理得牛顿迭代格式为:迭代序列的误差 满足第17页/共35页因为 ，所以注意:由上式可得:即

8、该迭代格式是2阶收敛的.第18页/共35页例4 求方程 的解解：设 ，则 f(0)=1,f(2)=-1 在0,2内,f(x)0,f(0)f(0)0,所以迭代格式为:第19页/共35页MATLAB程序为:function x,k=Newton(x0,dx,eps)%eps:tolerancek=0;while dxepsx(k+1)=x0-(exp(-x0/4)*(2-x0)-1)/(exp(-x0/4)*(x0-6)/4);dx=abs(x(k+1)-x0);x0=x(k+1);k=k+1;end第20页/共35页取x0=0及x0=3,计算结果比较精确。如果改写x0=8,又会怎样呢?计算结果如

9、下.x(1)=8;for k=2:3x(k)=x(k-1)-(2-x(k-1)*exp(-x(k-1)/4)-1)/(exp(-x(k-1)/4)*(x(k-1)-6)/4);end xx=8.0000 34.7781 869.1528第21页/共35页定理4.7指出：x0的选取是很要紧的。例如此例，选x0=0则完全符合定理条件，可确保迭代格式收敛；选x0=3也可收敛；说明定理条件是充分条件；但如果选x0=8则发散。第22页/共35页小结小结(1)当f(x)充分光滑且 x*是f(x)=0的单根时，牛顿法在x*的附近至少是平方收敛的。(2)当f(x)充分光滑且 x*是f(x)=0的重根时，牛顿法

10、在x*的附近是线性收敛的。(3)Newton法在区间a,b上的收敛性依赖于初值x0 的选取。第23页/共35页改进与推广改进与推广/*improvement and generalization*/重根重根 /*multiple root*/加速收敛法：加速收敛法：Q1:若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x*是是 f 的的 n 重根，则：重根，则：且且 。因为因为 Newtons Method 事实上是一种特殊的不动点迭代，事实上是一种特殊的不动点迭代，其中其中 ，则，则A1:有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越慢。越高，收敛越慢。Q2:

11、如何加速重根的收敛？如何加速重根的收敛？A2:将求将求 f 的重根转化为求另一函数的单根。的重根转化为求另一函数的单根。令，则令，则 f 的重根的重根 =的单根。的单根。第24页/共35页 正割法正割法 /*Secant Method*/：Newtons Method 一步要计算一步要计算 f 和和 f，相当于，相当于2个函数值，个函数值，比较费时。现用比较费时。现用 f 的值近似的值近似 f，可少算一个函数值。，可少算一个函数值。x0 x1切线切线/*tangent line*/割线割线/*secant line*/切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。

12、收敛比收敛比Newtons Method 慢，且对初值要求同样高。慢，且对初值要求同样高。第25页/共35页 下山法下山法 /*Descent Method*/Newtons Method 局部微调：局部微调：原理：原理：若由若由 xk 得到的得到的 xk+1 不能使不能使|f|减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得 。xkxk+1注：注：注：注：=1 时就是时就是Newtons Method 公式。公式。当当 =1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。第26页/共35页 Algorithm:Newtons Desc

13、ent MethodFind a solution to f(x)=0 given an initial approximation x0.Input:initial approximation x0;f(x)and f(x);minimum step size of xmin;tolerance TOL1 for x;tolerance TOL2 for ;maximum number of iterations Nmax.Output:approximate solution x or message of failure.Step 1 Set k=1;Step 2 While(k Nma

14、x)do steps 3-10Step 3 Set =1;Step 4 Set ;/*compute xk*/Step 5 If|x x0|TOL2 then GOTO Step 4;/*compute a better xi*/Step 9 Set x0=x0+xmin;/*move forward anyway to avoid deadlock*/Step 10 Set k+;Step 11 Output(Method failed after Nmax iterations);STOP./*unsuccessful*/计算量未见得减小计算量未见得减小第27页/共35页 求复根求复根 /

15、*Finding Complex Roots*/Newton 公式中的自变量可以是复数公式中的自变量可以是复数记记 z=x+i y,z0 为初值，同样有为初值，同样有设设代入公式，令实、虚部对应相等代入公式，令实、虚部对应相等，可得，可得第28页/共35页解非线性方程组的牛顿法解非线性方程组的牛顿法将非线性方程组线性化，得到：将非线性方程组线性化，得到：第29页/共35页其中其中F(xk)为为F(x)在在xk处的处的JacobiJacobi矩阵：矩阵：第30页/共35页例：用牛顿法解方程组第31页/共35页取初始值（取初始值（1 1，1 1，1 1），计算如），计算如下下N x y z0 1.

16、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页/共35页练习：练习：3.3.Newton Newton 迭代法是如何推出的迭代法是如何推出的?它若在单根附近收它若在单根附近收敛敛,是几阶收敛是几阶收敛?在重根附近是几阶收敛？求方程重根在重根附近是几阶收敛？求方程重根时时,能达到能达到2 2阶收敛的改进阶收敛的改进 Newton Newton 迭代公式是什么迭代公式是什么1.1.用牛顿法求方程用牛顿法求方程 在区间在区间 1 1，2 2 内内的一个实根，要求的一个实根，要求2.2.导出求立方根导出求立方根 的迭代公式，并讨论其收敛性。的迭代公式，并讨论其收敛性。第33页/共35页首先导出求根方程首先导出求根方程 ，再对，再对 使用牛顿法使用牛顿法得迭代公式得迭代公式 ,用全局收敛性定理或局部收用全局收敛性定理或局部收敛性定理讨论其收敛性。敛性定理讨论其收敛性。第34页/共35页感谢您的观看！第35页/共35页