李晓辉 任伟和 程长胜
摘 要：本文主要讲了求解非线性方程的牛顿迭代法。文章首先引入牛顿迭代法的公式、迭代函数。紧接着文章又介绍了牛顿迭代法的局部收敛性以及它的收敛速度，并通过数值实验验证了牛顿迭代法求解非线性方程的有效性。
关键词：牛顿迭代法;局部收敛;收敛速度
中图分类号：O010224 文献标识码：A
一、绪论
类似于线性方程组Ax=b求解的问题，非线性方程的一般问题可化为f（x）=y，即“对于什么样的x的值，函数f取值为y”，这里可以暂且先把f当成单变量函数，通常把y移项并吸收进f，从而一般形式可记为f（x）=0，因此，一个一般的一元非线性方程的求解问题有如下形式：
给定函数f，寻找x（实的或复的），使得f（x）=0。若存在一点x*满足该性质，称x*是方程f（x）=0的根或函数的零点。这类问题称为求根问题或求零点问题。
此外，方程的根的情况可分为单根和重根。一般的非线性方程的重数可以定义如下：
若f（x）=（x-x*）m·g（x）且g（x）≠0，其中，m为自然数，称x*为f（x）的m重根，m=1时也称单根。若区间[a，b]上有方程的一个实根，称该区间为方程的一个有根区间，如果能把方程的有根区间的长度缩短到一定的范围内，那么就求到了一个近似根，通常采用的都是数值求解的办法，因此若假设要求有根区间长度为0（即求到精确解），这些数值求解的办法通常都会产生一个逐渐逼近根的一个无穷序列。
求方程的近似根，一般要考虑如下几个问题：
（1）根的存在性问题，即方程有没有实根，有几个根。
（2）有根区间的确定。本文介绍的算法通常是假设有根的前提下给出求近似根的方法，一般需要以别的辅助工具先确定有根区间。
（3）求出足够近似的根，即在制定精度下缩小有根区间，或通过某些判别条件断定近似根的精度。
二、Newton迭代公式的构造
简单迭代是将非线性方程f（x）=0通过代数恒等变形，将原方程化成等价方程x=φ（x），从而形成迭代式xk+1=φ（xk）。
Newton迭代法则是将非线性方程f（x）=0在x0点展开，即f（x）=f（x0）+f′（x0）（x-x0）+f″（ξ）2！（x-x0）2，并令p（x）=f（x0）+f′（x0）（x-x0），用线性方程p（x）=0近似代替非线性方程f（x）=0，再从p（x）=0中解得x=x0-f（x0）f′（x0），并令x1=x0-f（x0）f′（x0）作为f（x）=0的根的第一级近似值。一般的，记：
xk+1=xk-f（xk）f′（xk）（2.1）
作为方程f（x）=0的根的第k+1级近似值，我们称公式（2.1）为Newton迭代公式，其中xk为第k次迭代的初值。Newton迭代公式（2.1）也可以由加速迭代公式
xk+1=xk+f（xk）=φ（xk）
xk+1=ωkxk+1+（1-ωk）xk（2.2）
其中ωk=11-L称为松弛因子，L=φ′（xk），ωk=11-φ′（xk）=-1f′（xk），将ωk=11-φ′（xk）=-1f′（xk）代入（2.2）的第二个式子即得xk+1=xk-f（xk）f′（xk），这就是Newton迭代公式，其迭代函数是φ（x）=x-f（x）f′（x）。
另外，Newton迭代公式还有一种推导形式：
假设非线性方程为：
f（x）=0（2.3），令y=f（x）（2.4）
它的反函数为：
x=F（y）（2.5）
如果方程（2.3）中左端函数f（x）在区间[a，b]上连续，有且只有一个实根，则有f（a）f（b）<0。
现在假设x=α是方程（2.3）的一个实根，其中α∈[a，b]，则有：
f（α）=0（2.6）
α=F（0）（2.7）
如果对反函数式（2.5）在y点展成泰勒级数，则根据式（2.7）有：
α=F（0）=F（y）+F′（y）（0-y）+F″（y）2（0-y）2+…（2.8）
如果取展开式（2.8）中的前两项，可得：
α≈F（y）-F′（y）·y
再利用反函数与反函数的导数概念，即y=f（x），x=F（y），F′（y）=1f′（x），则有α≈x-f（x）f′（x），令φ（x）=x-f′（x）f（x），就可以得到方程（2.3）的等价形式为x=x-f（x）f′（x）.此式被称为牛顿迭代式。在区间[a，b]上取一个初值x0，就可以得到牛顿迭代格式xn+1=xn-f（xn）f′（xn）。
三、Newton迭代法局部收敛性分析
定义3.1：（局部收敛）若存在x*的某邻域R=x|x-x*<δ，对任意的x0∈R，由xk+1=φ（xk）所产生的点列收敛，则称xk+1=φ（xk）在R上收敛于x*。
定理3.1（局部收斂判别定理）设xk+1=φ（xk），R=x|x-x*<δ，若φ（x）满足：
（1）φ′（x）在R内连续;（2）φ′（x*）
q<1，
则有以下结论：
（1）xk+1=φ（xk）在R上唯一地收敛于x*;
（2）xk-x*
11-qxk+1-xk。
证明：由（1）φ′（x）在R内连续，由连续函数的性质，存在x*的某邻域R=x|x-x*<δ，使对于任意x∈R成立φ′（x）
q<1，此外，对于任意x∈R，总有φ（x）∈R，这是因为φ（x）-x*=φ（x）-φ（x*）
x-x*，满足逼和条件，又由于条件（2）满足压缩条件。由此可以得到与全局收敛判别定理相类似的结论。
推论3.1 Newton迭代法在单实根邻近处局部收敛。
证明：设f（x）=0的一个单实根为x*，在Newton迭代公式中，φ（x）=x-f（x）f′（x），φ′（x）=f（x）f″（x）[f′（x）]2，φ′（x*）=f（x*）f″（x*）[f′（x*）]2，因为x*为f（x）=0的一个单实根，所以f（x）=（x-x*）ψ（x），且ψ（x*）≠0，而f′（x*）=（x-x*）ψ′（x*）+ψ（x*）=ψ（x*）≠0，所以φ′（x*）=0，由定理3.1和推论3.1知结论成立。
四、Newton迭代法的收敛速度
为了进一步研究收敛速度问题，我们引入阶的概念。
定义4.1 设由迭代公式xk+1=φ（xk）得到迭代序列xk收敛于方程x=φ（x）的根x*，记ek=xk-x*，若limk→
ek+1ekp=c≠0（p>0），称序列xk是p阶收敛的。特别地，p=1时称线性收敛，p>1时称超线性收敛，p=2时称平方收敛。显然p越大，收敛速度越快。
定理4.1 设由迭代公式xk+1=φ（xk）得到迭代序列xk，若φ（p）（x）在所求的根x*的某个邻域内连续，且φ′（x*）=…=φ（p-1）（x*）=0，φ（p）（x*）≠0，则迭代序列xk在所求的根x*的邻域内是p阶收敛。
证明：利用φ（xk）在x*的泰勒展开，并注意到xk+1=φ（xk），x*=φ（x*）和ek=xk-x*，
由φ（xk）=φ（x*）+φ′（x*）（xk-x*）+…+φ（p）（x*）p！（xk-x*）p+…，可得：
ek+1=φ′（x*）ek+…+φ（p）（x*）p！ekp+…
于是，根据阶的定义式，若φ′（x*）≠0，则xk是一阶收敛（线性收敛）;若φ′（x*）=…=φ（p-1）（x*）=0，φ（p）（x*）≠0，则xk是p阶收敛。证毕。
上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数φ（x）的选取。如果当x∈[a，b]时，φ′（x）≠0，则该迭代过程只可能是线性收敛。
对于牛顿公式，其迭代函数为φ（x）=x-f（x）f′（x），φ′（x）=f（x）f″（x）[f′（x）]2，假定x*是f（x）的一个单根，即f（x*）=0，f′（x*）≠0，则由上式知φ′（x*）=0，于是由定理4.1可知，牛顿法在根x*邻近是局部平方收敛的。
由于牛顿法是局部收敛，因此牛顿法对初值要求比较严格，初值只有在根的附近才能保证收敛。实际上，常常用二分法或逐步搜索法选取好的初值。
定理4.2 设x*是f（x）=0的根，函数f（x）在x*的某一邻域U（x*，δ），（0<δ<1）内具有二阶连续导数，迭代函数为φ（x）=x-f（x）f′（x），当x∈U（x*，δ）时，φ（x）∈U（x*，δ），对于x0∈U（x*，δ），牛顿迭代公式产生的迭代序列为xk。如果φ′（x*）=f（x*）f″（x*）[f′（x*）]2<1，那么迭代序列xk收敛于x*;如果x*是f（x）=0的单根，那么迭代序列xk在x*的附近是二阶收敛的，即平方收敛，且limk→
xk+1-x*（xk-x*）2=f″（x*）2f′（x*）;如果x*是f（x）=0的二重根，那么迭代序列xk在x*附近是一阶收敛的，即线性收敛的，且重数越高收敛越慢。
定理4.3 设方程f（x）=0满足下列条件：
（1）f（x）在区间[a，b]上的f′（x）与f″（x）均存在，且f′（x）与f″（x）的符号在区间[a，b]上均各自保持不变;
（2）f（a）f（b）<0;
（3）f（x0）f″（x0）>0，x0，x∈[a，b];
则方程f（x）=0在区间[a，b]上有且只有一个实根。由牛顿迭代格式计算得到的近似值序列收斂于方程f（x）=0的根。
五、牛顿迭代法的计算步骤
用牛顿迭代法解非线性方程f（x）=0的基本计算步骤是：
第一步：给出初始近似根及精度ε。
第二步：计算f0f（x0），f′0f′（x0），x1x0-f（x0）f′（x0）。
第三步：判断若x1-x0<ε，则转向第四步;否则x0x1，转向第三步。
第四步：输出满足精度的根x，即α≈x，结束。
六、数值实验
例1.用牛顿迭代法求方程xx=10的一个实根，精度要求为ε=10-6。
解：该方程的一个实根在2与3之间，即a=2，b=3。并且可以将原方程同解变换为f（x）=xlgx-1而f（a）=f（2）=2lg2-1<0，f（b）=f（3）=3lg3-1>0，因此方程满足f（a）f（b）<0的条件，且f′（x）=lgx+lge>0，x∈[2，3]，f″（x）=lgex>0，x∈[2，3]，即f′（x）与f″（x）在区间[2，3]上各自保持符号不变，并且还可以看出f″（x）与f（3）同号，因此取x0=3，采用牛顿迭代格式xn+1=xn-f（xn）f′（xn），其计算结果如下表所示。
从上表可以看出，当n=3时，其迭代值已满足精度要求，最后取实根的近似值为x=2.506184。
参考文献：
[1]李庆扬.数值分析.武漢：华中科技大学出版社，1986.12.
[2]张光澄.实用数值分析.成都：四川大学出版社，2004.1.
[3]王金铭.数值分析.大连：大连理工大学出版社，2007.8.
[4]任玉杰.数值分析及其MATLAB实现.北京：高等教育出版社，2007.3.
[5]徐士良.数值方法与计算机实现.北京：清华大学出版社，2006.2.
[6]欧阳联渊.计算机数值计算方法.北京：国防工业出版社，1997.1.
[7]薛毅.数值分析.北京：北京工业大学出版社，2005.3.
作者简介：李晓辉（1984— ），女，硕士研究生，所学专业为计算数学，研究方向为最优化计算方法，多年来从事数学在各个领域的应用研究。
