非线性方程的牛顿法.ppt
数值分析数值分析非线性方程的牛顿法非线性方程的牛顿法(Newton Method of Nonlinear Equations)内容提纲（内容提纲（Outline)Outline)牛顿法及其几何意义牛顿法及其几何意义 收敛性及其收敛速度收敛性及其收敛速度 计算实例及其程序演示计算实例及其程序演示取取x0 0作为初始近似值作为初始近似值，将将f(x)在在x x0 0做做TaylorTaylor展开展开:重复上述过程重复上述过程 作为第一次近似值作为第一次近似值一、牛顿法及其几何意义一、牛顿法及其几何意义Newton迭代公式迭代公式基本思路：基本思路：将非线性方程将非线性方程f(x)=0 线性化线性化牛顿法的几何意义牛顿法的几何意义xyx*x0 x 1x 2牛顿法也称为切线法牛顿法也称为切线法（局部收敛性定理局部收敛性定理）设设 f(x)C2a,b，若若 x*为为 f(x)在在a,b上的根上的根,且且 f (x*)0，则存在则存在 x*的邻域的邻域 使得任取初始值使得任取初始值 ，Newton 法产生的序列法产生的序列 xk 收敛到收敛到 x*，且满足且满足至少平方收敛至少平方收敛二、牛顿法的收敛性与收敛速度二、牛顿法的收敛性与收敛速度在在x*的附近的附近收敛收敛由由Taylor 展开：展开：令令k，由由 f (x*)0，即可得结论。即可得结论。证明：证明：Newton法法实际上是一种特殊的迭代法实际上是一种特殊的迭代法思考题思考题1 若若 ，Newton法法是否仍收敛？是否仍收敛？设设 x*是是 f 的的 m 重根，则令：重根，则令：且且Answer1:有局部收敛性有局部收敛性Answer2:线性收敛线性收敛思考题思考题2当当x*是是 f(x)=0的的m重根重根,是否平方收敛？是否平方收敛？注：注：注：注：Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0 有根有根根唯一根唯一全局收敛性定理全局收敛性定理(定理定理4.7)：设设 f(x)C2a,b，若若(1)f(a)f(b)0；则由则由Newton法产生的序列法产生的序列 xk 单调地收敛到单调地收敛到f(x)=0 在在 a,b 的唯一根的唯一根x*,且收敛速度至少是二阶且收敛速度至少是二阶的的保证保证产生的序列产生的序列xk单调有界单调有界保证保证Newton迭迭代函数代函数将将a,b映映射于自身射于自身将将f(x*)在在 xk 处作处作TaylorTaylor展开展开对迭代公式两边取极限，得对迭代公式两边取极限，得证明：证明：证明：证明：以以为例证明为例证明 说明数列说明数列 xk 有下界有下界故故 xk 单调递减单调递减,从而从而 xk 收敛收敛.令令？三、计算实例及其程序演示计算实例及其程序演示辅助工具辅助工具:VCVC程序设计语言程序设计语言MatlabMatlab数学软件数学软件(1)(1)选定初值选定初值x0,计算计算f(x0),f (x0)计算步骤计算步骤(2)(2)按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 (3)(3)对于给定的允许精度对于给定的允许精度，如果如果 则终止迭代，取则终止迭代，取 ;否则否则k=k+1，再转再转 步骤步骤(2)(2)计算计算允许精度允许精度最大迭代最大迭代次数次数迭代信息迭代信息例题1用用NewtonNewton法求方程法求方程 的根的根,要求要求迭代格式一：迭代格式一：迭代格式二：迭代格式二：取初值取初值x x0 00.00.0,计算如下：计算如下：对迭代格式一对迭代格式一:the iterative number is 27,the numerical solution is 0.442852706对迭代格式二对迭代格式二:the iterative number is 3,the numerical solution is 0.442854401例题2求函数求函数 的正实根的正实根精度要求：精度要求：从图形中我们可以从图形中我们可以看出：看出：在在x=7和和x=8 之之间有一单根；间有一单根；在在x=1和和x=2 之之间有一重根。间有一重根。用用MatlabMatlab画图，查看根的分布情形画图，查看根的分布情形初值初值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例3:设C为正实数,导出用牛顿法求 的公式,并证明解：解：设 ，则 于是有由于 所以在 内有一正根.又在 内,根据定理得牛顿迭代格式为:迭代序列的误差 满足因为 ，所以注意:由上式可得:即该迭代格式是2阶收敛的.例例4 求方程 的解解：解：设 ，则 f(0)=1,f(2)=-1 在0,2内,f(x)0,f(0)f(0)0,所以迭代格式为: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取x0=0及x0=3,计算结果比较精确。如果改写x0=8,又会怎样呢?计算结果如下.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定理4.7指出：x0的选取是很要紧的的选取是很要紧的。例如此例，选x0=0则完全符合定理条件，可确保迭代格式收敛；选x0=3也可收敛；说明定理条件是充分条件；但如果选x0=8则发散。小结(1)当f(x)充分光滑且 x*是f(x)=0的单根时，牛顿法在x*的附近至少是平方收敛的。(2)当f(x)充分光滑且 x*是f(x)=0的重根时，牛顿法在x*的附近是线性收敛的。(3)Newton法在区间a,b上的收敛性依赖于初值x0 的选取。改进与推广改进与推广/*improvement and generalization*/重根重根 /*multiple root*/加速收敛法：加速收敛法：Q1:若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x*是是 f 的的 n 重根，则：重根，则：且且 。因为因为 Newtons Method 事实上是一种特殊的不动点迭代，事实上是一种特殊的不动点迭代，其中其中 ，则，则A1:有局部收敛性，但重数有局部收敛性，但重数 n 越高，收敛越慢。越高，收敛越慢。Q2:如何加速重根的收敛？如何加速重根的收敛？A2:将求将求 f 的重根转化为求另一函数的单根。的重根转化为求另一函数的单根。令，则令，则 f 的重根的重根 =的单根。的单根。正割法正割法 /*Secant Method*/：Newtons Method 一步要计算一步要计算 f 和和 f，相当于，相当于2个函数值，个函数值，比较费时。现用比较费时。现用 f 的值近似的值近似 f，可少算一个函数值。，可少算一个函数值。x0 x1切线切线/*tangent line*/割线割线/*secant line*/切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。收敛比收敛比Newtons Method 慢，且对初值要求同样高。慢，且对初值要求同样高。下山法下山法 /*Descent Method*/Newtons Method 局部微调：局部微调：原理：原理：若由若由 xk 得到的得到的 xk+1 不能使不能使|f|减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得 。xkxk+1注：注：注：注：=1 时就是时就是Newtons Method 公式。公式。当当 =1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。Algorithm:Newtons Descent 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 Nmax)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*/计算量未见得减小计算量未见得减小 求复根求复根 /*Finding Complex Roots*/Newton 公式中的自变量可以是复数公式中的自变量可以是复数记记 z=x+i y,z0 为初值，同样有为初值，同样有设设代入公式，令实、虚部对应相等代入公式，令实、虚部对应相等，可得，可得解非线性方程组的牛顿法将非线性方程组线性化，得到：将非线性方程组线性化，得到：其中F(xk)为F(x)在xk处的Jacobi矩阵：例：用牛顿法解方程组取初始值（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练习：练习：3.3.Newton Newton 迭代法是如何推出的迭代法是如何推出的?它若在单根附近收它若在单根附近收敛敛,是几阶收敛是几阶收敛?在重根附近是几阶收敛？求方程重根在重根附近是几阶收敛？求方程重根时时,能达到能达到2 2阶收敛的改进阶收敛的改进 Newton Newton 迭代公式是什么迭代公式是什么1.1.用牛顿法求方程用牛顿法求方程 在区间在区间 1 1，2 2 内内的一个实根，要求的一个实根，要求2.2.导出求立方根导出求立方根 的迭代公式，并讨论其收敛性。的迭代公式，并讨论其收敛性。首先导出求根方程首先导出求根方程 ，再对，再对 使用牛顿法使用牛顿法得迭代公式得迭代公式 ,用全局收敛性定理或局部收用全局收敛性定理或局部收敛性定理讨论其收敛性。敛性定理讨论其收敛性。
