牛顿迭代法.docx
《牛顿迭代法.docx》由会员分享，可在线阅读，更多相关《牛顿迭代法.docx（22页珍藏版）》请在冰点文库上搜索。
牛顿迭代法
牛顿迭代法
李保洋
数学科学学院信息与计算科学学号：
060424067
指导老师：
苏孟龙
摘要：
牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，即牛顿迭代法.迭代法是一种不断用变量的旧值递推新值的过程•跟迭代法相对应的是
直接法或者称为一次解法，即一次性解决问题•迭代法又分为精确迭代和近似迭代
“牛顿迭代法”属于近似迭代法，本文主要讨论的是牛顿迭代法，方法本身的发现和演变和修正过程，避免二阶导数计算的Newton迭代法的一个改进，并与中国古代的算法，即盈不足术，与牛顿迭代算法的比较•
关键词：
Newton迭代算法；近似求解；收敛阶；数值试验；中国古代数学;
九章算术；Duffing方程；非线性方程；收敛速度；渐进性
0引言：
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题•迭代法又分为精确迭代和近似迭代•“二分法”和“牛顿迭代法”属于近似迭代法•
迭代算法是用计算机解决问题的一种基本方法•它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值•具体使
用迭代法求根时应注意以下两种可能发生的情况：
（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制•
（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败•
所以利用迭代算法解决问题，需要做好以下三个方面的工作：
1、确定迭代变量•在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量
2、建立迭代关系式.所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）.迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成.
3、对迭代过程进行控制，在什么时候结束迭代过程？
这是编写迭代程序必须
考虑的问题.不能让迭代过程无休止地重复执行下去.迭代过程的控制通常可分为两种情况：
一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的
迭代次数无法确定.对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件.
1牛顿迭代法：
牛顿迭代法（Newtonmethod）又称为牛顿-拉夫逊方法（Newton-Rapfsonmethod），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法.多数方程不存在求根公式，因此求精确根非常困难甚至不可能，从而寻找方程
的近似根就显得特别重要•方法使用函数fx的泰勒级数的前面几项来寻找方程
fx=0的根•牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程
fx=0的单根附近具有平方收敛性，而且该法还可以用来求方程的重根、复根.
另外该方法广泛用于计算机编程中：
解非线性方程fx]=0的牛顿（Newton）法是把非线性的方程线性化的一种近
似方法•把fx的x点附近展开泰勒（Taylor）级
'2
fx=fx0fX-X0fx0］亠ix-X0
取其线性部分作为非线性方程fx=0的近似方程，则有:
fX。
f'X。
X-x0=0；
设f'x。
=0,则其解为：
再把fx在％附近展开泰勒（Taylor）级数，也取其现行部分作为fxi；=0的近似方
程.若f%=0，则得:
这样，得到牛顿（Newton）法的一个迭代序列:
当选取初值Xo以后，过Xo,fXo「|做fX的切线，其切线方程为:
y-fX。
=f'&x-X。
；
求此切线方程和X轴的交点，即得：
x—X。
一fX'fX
牛顿法正因为有这一明显的几何意义，所以也叫切线法例：
用牛顿法求下面方程的根
fX=X32x210x-20=0；
解：
因fx]=3x2・4x*10，所以迭代公式为:
xn勺.二焉一X32x210x-203x24x10；
选取X（）=1计算结果列表:
N
牛顿法
弦位法
抛物线法
0
1
p
1
1
1.411764705882353
1.500000000000000
1.500000000000000
2
1.369336470588235
1.354430379746836
1.250000000000000
3
1.368808188617532
[1.368270259654687
1.368535857721367
4
1.369808107821375
1.368810350393887
1.368807906820180
5
1.368808107821373
1.368808107472217
1.368808107821681
6
1.368808107821373
p.368808107821373
1.368808107821373
7
1.368808107821373
1.368808107821373
从结果可以看出，牛顿法的收敛是很快的，X5误差10」5•但用牛顿法计算工作量比
较大，因每次计算迭代除了计算函数值外还要计算微商值•为此我们提出了简化牛顿法：
其公式为Xn1=Xn-fXn「f'X；用上面的公式计算，不再需要每步重新
计算微商值，所以计算量小一些，但收敛也要慢一些•为了避免计算导数还可以采用差商代导数的方案：
-5"Xn—
fXn-fXn^
关于牛顿迭代的收敛有下面结果：
如果fX在零点附近存在连续的二阶微商,
•是fX的一重零点，且初始X0充分接近于，那么牛顿迭代是收敛的，且有
&十仝|十"卩）/0'（匕）卜焉仝2
这表明牛顿法是二阶收敛的（平方收敛的）
最后考虑fx是多项式的特殊情况，此时fX,fx在某个x值，比如x=c时的计算可用综合除法•
设f（x）=axn+axn半+川an」x+an，除以x—c，得商q（x），余r:
（1）
fx二qxxc;r
其中:
qxi=boxn‘bxn，川bn/;
r=0=fc；
比较
（1）式两边xk的系数便知这些bk可以按下表进行：
a。
a1
a2
an」
an
b°c
be
b^c
bn」C
b0=a0
d=4+boc
b2=a2+de
=anV+bn_2c
bn=a.+bn」C
这一过程其实就是秦九韶算法，计算多项式值的嵌套算法：
fc二丨||aoaic■a?
cc川a.」can；
每个括号的值就是这里的bollllllbn.
至于导数的计算，注意到
（1）式可得：
f'x=qxq'xx-c；
于是：
f'c=qc；
因此再对b0||||||bn进行上述过程，或者再用一次秦九韶算法即可•
2一种修正的牛顿迭代法：
给出了牛顿迭代法的一种修正形式，并证明了当r=1/2时修正的牛顿迭代法
是二阶收敛的，当参数r=1/2时是三阶收敛的，数值实验表明，与经典牛顿迭代法相比，该修正牛顿迭代法具有一定的优势•众所周知，数值求解非线性方程
fx=0的根的方法很多.经典的牛顿迭代法是非线性方程组求根的一个基本方
法，它二次收敛到单根，线性收敛到重根•牛顿法因收敛速度快而得到广泛应用，也倍受学者的重视，近年来很多文献中提出各种改进的牛顿方法•文献［8］中利
用Newton迭代法和微分中值定理“中值点”的渐进性，提出了一种多点迭代法.
设f（x）满足下述条件:
fx卢c2l.a,b］,fafb：
：
0；
因此，当b与a的距离无限接近时有:
图1迭代法构适图
1
:
a-b-a.也就是说，在区间（a,b）不甚大时，中值点一定在其渐近位置
2
:
a2^a附近，并随区间变小而趋于其渐近位置.图所示迭代法构造图本方案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进行迭代求近似根的新方法•这种方法虽然在迭代中又只利用了一个其它点，但其计算精度却相当高，它的某一种特殊情形恰是通常的Newton迭代法.为了更加直观起见，我们
通过几何直观图来构造这种迭代法•设fx满足条件（A），当选定初值xo（仅要求fxof"x0），如图所示，作交点的切线交x轴于Bxo-丄旦,0
If（X。
）
AQ线段的斜率为:
X。
/;:
应丫。
fr。
“"仏）丿
重复上述过程，得到多点迭代公式
f（Xk）
Xk1=Xk-
f（Xk
fXk-Crf^H
、、、f（兀）丿
其中Xk[a,b]，k=1,2,3,111.
下面我们对上述事实，从理论上加以严格证明.
定理设fX满足条件（A），则由多点迭代公式
（1）产生的序列｛Xn｝必收敛于
［a,b］上的唯一a，这里xn：
=a,b丨，fa］=0.
证明函数fX在上连续，由连续函数根的存在定理，从fafb：
：
：
0知道fx在〔a,b上根存在，又由条件fx=0及fx保号知道，fx在〔a,b1上不变号，故fx在l.a,b1上是单调函数，因此fx在l.a,b］上根a存在且唯一.由定理
条件曲线y二fx可有如下四种不同情况：
（1）fa：
：
0,fb0,f"x0，则f'x单调上升，f'af'b0；
（2）fa<0,fb0,f"x0，则f'x单调下降，f'af'b0；
HIII
⑶fa0,fb<0,fx0,则fx单调上升，fafb：
：
0；
⑷fa0,fb:
:
:
0,f"x：
0,则f'x单调下降，f'af'b：
：
0.
通过对自变量的变号或对函数的变号可将四种情况归结为一种情况，所以我们只需对情况
（一）证明迭代过程
（1）收敛就可以了•
若初值人：
=[a,b],x0.a,所以fxo•0，故有
由
（一）的假设及f（E）cfx0一（1—r）『、“）可得:
Vf（x0）丿
般地，若Xn=a，同样可以证明由式
（2）得到的xn*满足axn十：
：
：
焉.所以由
式⑴产生的迭代序列｛xn｝单调下降且有下界.依极限理论必有极限.对式
（2）两边取极限，由极限理论可以求得fai=0.再由f'x=0，x^■l-a,b1，可知函数方程fx=0在〔a,b】上的根是唯一的，因此有a二a.
当r=1时，式⑵即为Newton迭代公式.
本文给出的这种多点迭代方法不仅可以被广泛应用于方程的近似求根，更重
要的是它为人们提供了一种新的迭代思想，拓宽人们在方程近似求根方面的思路•
例计算fx=x3-2x-5=0在（2,3）区间内的一个实根.
我们已知fx=0有一个精确到十二位有效数字的实根a=2.09455148154.
1
取x0=3，以Newton迭代法计算（记作x1n），取x^=3，r以式⑴计算（记
2
作X2n），其结果列表如表1.
表1计算结果:
迭代次数N
1
Xn
2
Xn
o
3
3
1
2.36
2.18468446
2
2.095136037
2.094726304
3
2.094551674
2.094551482
4
2.94551482
5
从这个数值例子，我们可以看出，式
（2）比Newton迭代法的收敛速度快得多，只进行三次迭代就已得满足精度要求的值了，而Newton迭代法需迭代5次才可得到满足精度要求的值•式
（2）可以被广泛应用，特别是编成数学软件后，用计算机求解方程近似根效果会更加显著.
3另外一种牛顿迭代法的修正：
Newton迭代法是方程求根的一种简单而直观的近似方法，但在实际运用中，我们常常觉察到，这种方法仅仅是利用了迭代点及该点的导数值，而没有充分利用其他点及其导数值•是否存在可利用的点，这些点我们应怎样确定•文［1］给出了
一种方法，但这种方法求根的关键在适当地选取xo和r或rn.选取不适当，就会出
现某次迭代的值不是迭代序列中的值•因此，我们会问这些值特别是Xo能否不依靠人为选取，而通过迭代点来选取，本文将利用Newton迭代法和微分中值定理“中值点”的渐近性，来寻找除迭代点以外的可利用点，给出一种多点迭代方法•
设fx满足下述条件：
fxc2a,b1,fafb：
0；
fx=0,fx在〔a,b1上保号.（A）
根据微分中值定理，存在匚三ia,b，使得f—bf―=fi而lima=1.因
b—afb-a2
1
此，当b与a的距离无限接近时有：
':
a-b-a.也就是说，在区间a,b不甚大时，中值点■一定在其渐近位置a1b-a附近，并随区间变小而趋于其渐近位置.本方案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进行迭代求近似根的新方法•
设fx满足下列条件（A）:
（1）fx在区间在区间la,b1上存在二阶导数;
⑵f'x在a,b1上不等于零；
⑶f"X在la,b1上不变号；
⑷fafb：
0；
当选定初值xo（仅要求f（xg）f（x）〉o），如图所示:
fxo一f!
x。
-
f（X。
）
X。
—',
f（x。
）丿
xo_
f'X。
-（1-ryif（兀）丿丿
如果令ux*i；'：
；x「m
引理1[5]对于迭代公式xk1=Gxk,如果门p在所求的根x*的邻近连续并且：
:
：
JX=:
：
Jx]=k儿P"x1=0，GPx=0，则该公式在X*的邻近是p阶收敛的.
定理1设方程fx的根为x*，函数fX在x*的的邻域内有至少四阶连续导数，
且f'x=0,则迭代公式（4）在的X*邻近至少是三阶收敛的.
证明迭代公式⑷的迭代函数为：
①ixawx—1Wx，其中
f（W（X））
fx<****
Wxk二xk-f'—，由于方程fx的根为x所以fX=0，从而可知Wx二X，
'*
w（x）=0；
W，，（x*）=f（X屮（X3对①（X）求导数得:
（f'（u（X*）））
fWXWXfuX.fWXfUXUX=打X=0；fuX
同理可得：
”X=GX*=WX*[-WX*=0.
由引理知迭代公式（4）在X*邻近至少是三阶收敛的.
引理2（[4]）假设函数f（x）在区间l.a,b1上存在二阶导数，且满足下列条件
⑴fx在la,b1上不等于零；
（2）f''x在l.a,b1上不变号;
⑶fafb：
：
0；
⑷设x：
=la,b1，且满足条件fxf"x0；
则由Newton迭代法xnx^fx^f'x0得到的序列：
焉』收敛于fx=0的惟
根x.
定理2假设函数fx在区间l.a,b1上存在二阶导数，且满足下列条件
（1）f'x在'a,b】上不等于零；
（2）f''x在l-a,b1上不变号;
（3）fafb-.0;
⑷设x：
=la,b],且满足条件fxf"x0.
则由多点迭代公式⑷得到的序列收敛于fx=0的惟一根x*.
证明函数fx在la,b]上连续，由连续函数根的存在定理，从fafb=：
0知道fx在l.a,b1上根存在，又由条件fx-0及fx的保号性知道，fx在l.a,bl上不变号，故fx在la,b1上是单调函数，因此fx在l.a,b1上的根x*存在且惟一.由定理条件，曲线y二fx可有如下四种不同情况：
（a）fa：
：
0,fb0,f"x0，则f'x单调上升，f'b—f'a0；
（b）fa=：
0,fb0,f"x：
：
0，则f'x单调下降，f'a_f'b0；
（c）fa0,fb:
:
0,f"x0，则f'x单调上升，f'a—f'b:
:
0；
（d）fa0,fb:
:
0,f"x：
：
0,则f'x单调下降，f'b—f'a：
：
0.
通过对自变量的变号或对函数的变号可以将四种情况归结为一种情况，所以
我们只需对其中一种情况证明迭代过程（4）是收敛的就可以了.
下面仅就情况（a）证明定理2，其余情况的证明类似.对情况（a）来说此时fx=0在a,b1上的根存在且惟一，且fx在l.a,b1上单调递增.首先证明，对任何初始近似xx*,b，由迭代公式（4）求出的逐次近似Xk都属于x*,b，并且单调递减.事实
上，由引理2的证明我们可知，只要uXk=xk-1-rx*,b，就有
xk<<,b，即Xk「uXk:
:
xk，再由⑶式得Xk!
：
：
：
Xk!
，另一方面（3）式可化为：
C）匸—XL仁—xl,f'T）\U（Xk））1丿l丿If（u（Xk））丿
f*—）*,,f'f©1
其中1•X,Xk1X,UXk.由fX单调递增且fX•0知一1，故
V丿f（u（Xk））
Xk1-X*・0因而由⑷式产生的序列单调递减并有下界，故limXn存在.
设limXn二x，
n\:
（4）式两边当k「：
时求极限得:
flx
if
f'X
X
kJ
x—ii—rj
1
）
丄.
7
X,x
-X*,b,fX在l.a,b1上单调递增，且fX*=0
所以:
X二X.
本方法代方法比Newton和文［4］的迭代法的收敛速度明显要快，而且对于
i，1，r越大效果越差！
对于例1,用MATLAB程序运算格式⑷，当V时'
在Xk>x*=0之前迭代格式会产生负值.所以，格式（4）的收敛速度和r的选取有关.
对于定理2中的四个条件，在MATLAB中通过简单的程序即可验证.
4中国古代算法盈不足术与牛顿迭代算法的比较：
首先介绍盈不足术九章算术中的第七章是盈不足术，这是求解方程的一种最古老的方法•为了说明该方法的基本思想，我们考虑该章的第一个例子：
今有共买物，人出8,盈3;人出7,不足4,问人数、物价各几何？
其求解过程为（见图1）:
=||02）+二|（21）-=|||（S3）
图1中国古代盈不足术的图解法
⑴把出率（8）和（7）放在第一行；
（2）把盈数（3）和不足数（4）放置在出率下面；
⑶计算维积（交差积）得（32）和（21），得和为（53）；
（4）盈减去不足数为4-3=1；
⑸从而得物价为531=53；
用现代数学的观点，盈不足术可表示为：
设X,和x2为两个近似物价，R,和&分别表示为盈或不足数，则物价为：
x=邛一吩；人数为丫=冬迟2；正如白尚恕
R-R2IX1—X2I
［7］指出的那样，在隋唐（581〜618年AD）盈不足术在中东被广泛流传，最早的阿
拉伯算术书是由al-Khowarizmi在公元825年写的，英文中的算术一词（algorithm）来自他的名字，他应该对九章算术和其他古代中国巨著很了解，并把盈不足术称为中国方法.Khitai指China，类似的写法有Khatai，Chatayn,Chataain等等.普遍认为中国算法是通过古代著名的意大利数学家LeonardoFibonacci（1170A1250?
年）
传给西方的，据记载Fibonacci随他父亲周游了埃及、西西里、希腊和叙利亚，这次周游使他接触了东方和阿拉伯的计算方法.在1202年，即他回家后不久他就出版了著名的《算经LiberAbaci》.该书也介绍了盈不足术，并把这种方法称为中国规则，这个名字来自中东，在那里中国算法称为Hisabl-Chatin，里Chation指China该书中的一些例子和算法和中国古代数学巨著完全一样.如在4世纪的孙子算经：
今有物不知其数，三三数之胜二，五五数之胜三，七七数之胜二，问物几何？
该问题的解题方法就是数论中的中国余数定理：
在Fibonacci的《算经》中阿拉伯语
DeRegulisel-Chatavn被译成拉丁文DuarumFalsdrumPosicionumRegula所以在西方这种方法被称作双假定方法，这实际上是九章算术中的盈不足术，即中国算法，它起源于中国是毫无疑问的，这正如钱宝琮［8］指出的那样可惜的是很多西方人认为这种方法起源于印度，并被阿拉伯人所掌握所以本作者强烈建议把双假设法改称为中国算法或中国方法.
中国算法与牛顿迭代算法考虑方程f'x=0设x「X2为方程的两个近似解，于是
我们得残量f为和fx2应用中国算法，我们可得
在九章算术中给出了在下列情况下的一些不等式:
（1）双盈，即fX,・0和fx20
（2）双亏，即fx,<0和fx2<0;
（3）一盈一亏，即fx,fx2:
:
0;
上述算法可以根据不等式的性质确定更合适的两个数x,,x2或x2,x3，再进行
计算定更精确的近似解，为了与牛顿迭代算法比较，我们把（5）写成如下形式：
x?
fX,—X1X2fx,x-x2
X3X,；
fX,-fX2fX,-fX2
如果引入导数f'X,，它定义为f'X,i=fXi-f*
那么我们马上可得：
X=为一丄^；
f（Xi）
这就是著名的牛顿迭代法，当两个近似值Xi和X2位于真解的两侧时，即
fXifX2.0，中国算法比牛顿迭代算法具有很大的优势，牛顿迭代算法可以更进一步的优化发展，可参考文献[10，11].
中国算法的改进：
中国算法可以看成是通过两个近似解的线性近似方法，见图2为了提高中国算法的精度，我们用三点Xi,X2,X3，而不用两点Xi,X2，用抛物线拟合该曲线，我们得近似解为：
X二X1f2f3
X2ff3
+
X3f2f1.
（f1一f2》f1—f3（
f2^ff2
f3
f3f2_f3f1
式中fi=f（X）；
综合概述：
迭代算法是一种用途非常广泛的方法，本文不仅介绍了这个方法很好的诠释这个方法，而且做了牛顿迭代法的两种修正，更做了牛顿迭和与中国古代算法的比较，不仅试读者更好理解了这个方法，更开阔了读者的视野，使读者更能留下
升级会员 