东南大学 - 数值分析 - 第二章 - 牛顿迭代法

东南大学《数值分析》上机练习——算法与程序设计实验报告

第二章 非线性方程的解法

——牛顿迭代法

****（学号） ****（姓名）

算法与程序题目见教材P56 上机题目20。

一、算法原理

根据题目的要求，是关于用牛顿迭代法法求解方程f(x)?0的通用算法。该法是一种通过斜率迭代的算法，其速度比二分法和简单迭代法都要快。其简单原理如下：

设f?C2[a,b],且存在数p?[a,b],满足f(p)?0。如果f?(p)?0,则存在一个数??0,对任意初始值p0?[p??,p??],使得由如下定义的迭代序列{pk}?k?0收敛到p：

pk?g(pk?1)?pk?1?f(pk?1),其中k?1,2,?

f?(pk?1)(1)

对于函数f(x)?x3/3?x=0，则其递推规则是

32pkpk?2?1,其中k?1,2,?

3pk?1-3(2)

?定义序列{pk}?则序列{pk}?也可表示为limpk?x?。现简要证明： k?0，k?0收敛到x，

x??

对于f(x)?x3/3?x，得f'(x)?x2-1，写出牛顿迭代公式

f(x)x3/3?x g(x)?x??x?2?f(x)x-1(3)

该公式可化简为

2x3g(x)?2

3x?3(4)

二、流程图

题目要求于用牛顿迭代法法求解方程f(x)?0的通用算法。其计算过程主要

第二章 非线性方程的解法

用到迭代g(x)?x?f(x)，图流程图1所示。 ?f(x)输入各参数 k=1 迭代pk?g(pk?1)?pk?1?f(pk?1),其中k?1,2,? f?(pk?1) T break 计算各误差 误差在允许范围之内 F k=k+1 k

三、计算代码

核心代码 1) p1=……;

2) if (err

程序1：Newton.m

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Description : 牛顿迭代法 % Author : panyunqiang % Versoin : 1.0

% Date : 2012-9-21

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [p0, err, k, y]=Newton(p0, delta, epsilon, maxN) % input - p0 is the initial approximation to a zero of f % - delta is the tolerance for p0

% - epsilon is the tolerance for the function values y % - maxN is the maxium number of iterations %output - p0 is the Newton approximation to a zero % - err is the error estimate for p0

东南大学《数值分析》上机练习——算法与程序设计实验报告

% - k is the number of iterations % - y is the function value f(p0) for k=1:maxN %%递归

p1=2*p0^3/(3*p0^2-3); %%计算误差

err=abs(p1-p0);

relerr=2*err/(abs(p1)+delta); p0=p1;

%%当前求出的根的函数值 y=p0^3/3-p0; %%判断

if (err

程序2：Newton_Step.m

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Description : 寻找题目中关于牛顿迭代法收敛的尽可能大的delta % 搜索步进为step=10^(-6),即精确到小数点后六位 % Author : panyunqiang % Versoin : 1.0

% Date : 2012-9-21

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% format long step=10^(-6);

delta=10^-8;epsilon=10^-8;maxN=1000; ps=0.6;

[p0, err, k, y]=Newton(ps, delta, epsilon, maxN); while((abs(p0)<=epsilon)&(p0~=NaN)) ps=ps+step;

[p0, err, k, y]=Newton(ps, delta, epsilon, maxN); end

ps-step

四、计算结果及分析

?a) 运行程序Newton_Step.m，获得Newton局部收敛于x2=0的初始值的

范围?= 0.774596，六位有效数字。通过改变程序Newton_Step.m

中的搜索步进step，可以获得不同的?精度。 b) 运行程序Newton.m,输出结果如下：

第二章 非线性方程的解法

1、输入x0?(-?,1)时

>> p0=newton(-2,10^(-12),10^(-12),1000) p0 =

-1.732050807568877 2、输入x0?(-1,-?)时

>> p0=newton(-0.85,10^(-12),10^(-12),1000) p0 =

1.732050807568877 3、输入x0?(-?,?)时

>> p0=newton(-0.001,10^(-12),10^(-12),1000) p0 =

-1.975314567913087e-028 4、输入x0?(?,1)时

>> p0=newton(0.85,10^(-12),10^(-12),1000) p0 =

-1.732050807568877 5、输入x0?(1,+?)时

>> p0=newton(2,10^(-12),10^(-12),1000) p0 =

1.732050807568877

%收敛到根3 从上面的结果可知，牛顿迭代法具有非常高的收敛速度（程序newton.m运行迭代次数k很小），进一步还会发现每次迭代后的精确位数大致都会翻倍，即具有二阶收敛性。同时，可以看出，当x0?(-?,1)?(-?,?)?(1,+?)时，程序会收敛到x0所属区间的那个根；而当x0?(-1,-?)?(?,1)，则不会收敛到x0所属区间的那个根。可以画出函数图像观察迭代过程，如图2所示。其中x0?(-1,-?)，

*为初始值，经过一次迭代后得到x1，三次迭代后就接近准确值x3=3了。事实%收敛到根-3

%收敛到根3 %收敛到根0

%收敛到根-3

上，我们通过matlab仿真观察每次迭代的结果，如下表所示，也能看出Newton迭代法收敛迅速，且与图2所示的切线基本符合一致。

表1 Newton迭代收敛情况

迭代次数 0 1 2 3 4 5 xn -0.855 1.549156 1.770525 1.733270 1.732052 1.732051 东南大学《数值分析》上机练习——算法与程序设计实验报告

f(x)=x/3-x0.8 0.63f(x)x3*=1.732x2*=0x1*=-1.7320.40.2y0初始值 x0x1x2-0.2-0.4x3=x3*-0.6-0.8 -2-1.5-1-0.500.511.522.5x

图2 Newton法迭代过程

五、结论

此次题目主要涉及牛顿迭代法。通过题目，我们可以看出，牛顿迭代法的效率是很高的。但该法的其中一个苛刻条件是二阶可导且一阶导数不能为0。有以下几个缺陷：1，有可能所得的序列左右来回飘移，不会收敛。2，序列会趋于重复或基本重复，造成循环。3，还有可能发生离散振荡序列。当根的阶数大于1时，迭代的速度会变慢，此时有一种更好的方法求解，即牛顿-拉夫森迭代的加速收敛法。而哈利法则是其另一种途径。

本文来源：https://www.bwwdw.com/article/zh48.html