本节书摘来自华章出版社《数值分析（原书第2版）》一 书中的第1章，第1.4节，作者：（美）Timothy Sauer，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

牛顿方法，也被称为牛顿拉夫逊方法，通常比我们前面看到的线性收敛方法快得多.牛顿方法对应的几何图如图1.8所示.为了找到函数f（x）=0的根，　图1.8　牛顿方法中的一步.从x0开始，画出函数y=f(x)的切线.和x轴的交点记做x1，这是对于函数根的下一个近似给定一个初始估计x0，画出函数f在x0点的切线.用切线来近似函数f,求出其与x轴的交点作为函数f的根，但是由于函数f的弯曲，该交点可能并不是精确解.因而，该步骤要迭代进行.
从几何图像中我们可以推出牛顿方法的公式.x0点的切线斜率可由导数f′(x0)给出.切线上的一点是(x0,f(x0)).一条直线的点斜率方程是y-f(x0)=f′(x0)(x-x0)，因而切线和x轴的交点等价于在直线中令y=0:f′(x0)(x-x0)=0-f(x0)
x=x0-f(x0)f′(x0)求解x得到根的近似，我们称之为x1.然后，重复整个过程，从x1开始，得到x2，等等，进而得到如下的迭代公式:

仅仅6步之后，根就包图1.9　牛顿方法中的三步.例1.11的图示.从x0=-0.7开始，沿着切线方向画出牛顿方法的迭代.该方法看起来会收敛到根含8位正确的数字.关于误差以及它们变小的速度还有很多值得进一步描述.在表中我们注意到一旦确定收敛，xi中正确的数位在每一步中近似翻倍.我们在后面会看到，这就是“二次收敛”方法的一个特征.

1.4.1　牛顿方法的二次收敛

例1.11中的二次收敛，比我们前面在二分法和不动点迭代中看到的线性收敛速度要快.现在需要如下一个新的定义.
定义1.10　令ei表示一个迭代方法第i步后得到的误差.该迭代是二次收敛，如果满足下式M=limi→∞ei+1e2i<∞　　定理1.11　令f是二阶连续可微函数，f（r）=0.如果f′(r)≠0，则牛顿方法局部二次收敛到r.第i步的误差ei满足limi→∞ei+1e2i=M其中M=f″(r)2f′(r)证明　为了证明局部收敛，注意到牛顿方法是不动点迭代的一个特殊形式，其中g(x)=x-f(x)f′(x)该函数的导数g′(x)=1-f′(x)2-f(x)f″(x)f′(x)2=f(x)f″(x)f′(x)2因为g′(r)=0,根据定理1.6牛顿方法局部收敛.
为了证明二次收敛，51
53我们使用另一种方式导出牛顿方法，并仔细观察在每步中生成的误差.从误差中，我们想看到真实根和当前最优估计之间的差异.
我们推导的误差公式（1.24）可被看做ei+1≈Me2i(1.25)其中M=f″(r)/2f′(r)，基于假设f′(r)≠0.由于估计结果xi向r移动，并且由于ci在xi和r之间，随着牛顿方法收敛，该近似也会越来越好.对于线性收敛方法，这个误差公式应该和ei+1≈Sei进行比较，FPI方法中S=g′（r），二分法中S=1/2.
尽管S的值对于线性收敛方法很关键，但是M的值并不那么重要，这是由于误差公式中包含了上一步误差的平方.一旦误差远小于1，平方会带来进一步的减小;只要M不是太大，根据式（1.25）可以知道，误差也会进一步下降.
回到例1.11，分析输出结果的表来验证这个误差率.根据牛顿方法，误差公式（1.25）右边一列表示这个比率是ei/e2i-1，当迭代收敛到根，该误差率趋近M.对于f(x)=x3+x-1，导数为f′(x)=3x2+1与f″(x)=6x；最后在xc≈0.6823处得到M≈0.85，这和表右列中的误差率一致.
54这是例1.6使用的方法.
为了研究其对应的收敛性，计算在根a的位置上的导数f′(a)=2a

1.4.2　牛顿方法的线性收敛

定理1.11并不意味着牛顿方法总能二次收敛.回忆一下，我们需要除去f′(r)得到二次收敛.这个假设十分重要.下面的例子显示了一个牛顿方法不能二次收敛的实例.
例1.12　使用牛顿方法找到f(x)=x2的实根.
这看起来像是个小问题，因为我们知道有一个实根:r=0.但是常常对于一个我们透彻理解的例子使用一个新方法有启发意义.牛顿方法公式如下xi+1=xi-f(xi)f′(xi)=xi-x2i2xi=xi2令人惊讶的是，牛顿方法被简化到仅仅每步除2.由于根是r=0，我们有如下的牛顿迭代的表，其中初值x0=1:

牛顿方法收敛到了根r=0.误差公式是ei+1=ei/2，因而收敛是线性的，收敛速度和常数S=1/2成比例.
对于xm也有相似的结果，其中m是正整数，如下面例子所示.
例1.13　使用牛顿方法寻找f（x）=xm的一个根.
xi+1=xi-xmimxm-1i=m-1mxi55　　收敛　方程（1.28）和（1.29）表示在牛顿方法中，到根r的两个不同的收敛率.在单根位置上f′(r)≠0，并具有二次收敛速度，或者更快的收敛，该收敛遵从式（1.28）.在多重根位置上f′(r)=0，收敛是线性的，并遵从式（1.29）.在后者问题的线性收敛中，更慢的收敛速度使得牛顿方法和二分法以及FPI处于同一类.
这是牛顿方法在多重根上的一般情形的例子.注意到多重根定义1.9和f(r)=f′(r)=0等价.正好是在这种情况下，牛顿方法的误差公式中的导数失去了效力.对于多重根有不同的误差公式.我们已经见到的单项式的多重根模式代表了一般情况，下面的定理1.12对此进行总结.
定理1.12　假设在区间［a，b］上，（m+1）阶连续可微函数f在r点有一个m阶多重根，则牛顿方法局部收敛到r，第i步误差ei满足limi→∞ei+1ei=S(1.29)其中S=（m-1）/m.
例1.14　函数f(x)=sinx+x2cosx-x2-x的重根r=0，计算多重性，并估计利用牛顿方法精确到小数点后6位的收敛所需要的步数（使用x0=1）.
使用定理1.12，牛顿方法会线性收敛ei+1≈2ei/3.
使用初始估计x0=1，得到e0=1.在收敛值附近，误差在每一步中会下降2/3.所以，精确到小数点后6位，或者误差小于0.5×10-6，所需步数的粗略估计通过求解下式可以得到23n<0.5×10-6

56大约需要36步.表中显示了前面的20步.

我们注意到右列中的误差收敛率和预测的2/3一致.
如果我们预先知道重根，牛顿方法的收敛可以通过少量的改进得到改善.
定理1.13　如果在［a，b］区间上f 是 （m+1）阶连续函数，包含m>1的多重根，则改进的牛顿方法xi+1=xi-mf(xi)f′(xi)(1.32)收敛到r，并具有二次收敛速度.
回到例1.14，我们使用改进的牛顿方法得到二次收敛速度.5步之后，会收敛到根r=0，精确到小数点后8位:

在这张表中有几处需要注意.首先，直到第4步，在每一步中得到近似精确的数位翻倍，可以观测到收敛到近似根的速度为二次.而在第6、7…步中的精确数位的个数和第5步相同.牛顿方法不能收敛到机器精度的原因和1.3节相似，对于这点我们很熟悉.57我们知道0是重根.当使用牛顿方法得到的后向误差在εmach附近的时候，前向误差等于xi，在数量级上要比后向误差大得多.
牛顿方法如同FPI，可能不会收敛到根.下面的例子是一种可能不收敛的情况.
由于函数是连续函数，在x=0时取负值，并且对于x的大的正数和负数则取无穷大的正值，因此一定存在根.但是如图1.10所示，对于初始估计x0=1/2则找不到根.牛顿公式xi+1=xi-4x4i-6x2i-xi(1.33)通过替代得到x1=-1/2，进一步x2=1/2.牛顿方法在这个例子中，迭代的结果在1/2和-1/2之间变化，但是二者都不是根，所以求解根的过程失败.

牛顿方法还有其他可能失败的方式.如果在任何迭代步中出现f′(xi)=0，显而易见，该方法就不能继续.还有其他的例子中迭代会发散到无穷（见习题6）或者模仿随机数生成（见编程问题13）.尽管不是所有的初始估计都会收敛到根，定理1.11和定理1.12保证在每个根近邻中的初始估计收敛到根.
1.应用牛顿方法迭代两步，初始估计x0=0.

2.应用牛顿方法迭代两步，初始估计x0=1.
3.使用定理1.11或定理1.12，在利用牛顿方法收敛到给定根的过程中通过前一项的误差ei估计误差ei+1.收敛速度是线性的还是二次的？58
5.考虑方程8x4-12x3+6x2-x=0.对于两个解x=0和x=1/2，不进行计算，试确定二分法和牛顿方法哪一个会收敛更快（例如，精确到小数点后8位）.
6.画出一个函数f以及对应的初始估计，使得对应的牛顿方法发散.
8.证明：对于函数f（x）=ax+b应用牛顿方法，会在一步中收敛.
9.证明对f(x)=x2-A应用牛顿方法，会得到习题1.6中的迭代结果.
10.找出对函数f(x)=x3-A应用牛顿方法得到的不动点迭代.参看习题1.2.10.
11.使用牛顿方法构造二次收敛方法，计算正数A的n阶根，其中n是正整数.证明二次收敛性.
12.假设牛顿方法应用于f（x）=1/x.如果初始估计是x0=1，找出x50.
13.（a）函数f(x)=x3-4x其中一个根r=2.如果使用牛顿方法第4步后的误差ei=xi-r是e4=10-6，估计e5.（b）使用与（a）相同的方程，应用到另一个根r=0.（注意:常用公式在这里没有用.）
14.令g(x)=x-f(x)/f′(x)表示函数f的牛顿方法迭代.定义h（x）=g（g（x））是牛顿方法相邻两步的结果，则根据微积分的链式法，h′(x)=g′(g(x))g′(x).（a）如习题1.15，假设c是h的不动点，但是c不是g的不动点.请证明,如果c是函数f（x）的拐点，即f″（x）=0，则不动点迭代h局部收敛于c.而且对于初始估计c，牛顿方法本身并不收敛到f的根，而会得到一个振荡的序列{c，g（c）}.（b）验证（a）中的稳定振荡在例1.15中也出现过.编程问题14将详细研究这个例子.
1.每个方程有一个根.使用牛顿方法求近似根，精确到小数点后8位.
2.每个方程有一个实数根.使用牛顿方法求近似根，精确到小数点后8位.
3.使用牛顿方法尽可能精确地找到唯一根，并确定根的多重性.然后使用改进牛顿方法二次收敛到根.报告每个方法中最优近似的前向和后向误差.
4.对下面问题实施编程问题3中的步骤.
5.由一个高为10m的圆柱构成的发射井的顶部是一个半球，体积400m3.确定发射井底部的半径，精确到小数点后4位.
6.一个10cm高的圆锥盛有60cm3的冰淇淋，其顶部是一个半球.确定冰淇淋半球的半径，精确到小数点后4位.
7.在区间［-2，2］上考虑函数f(x)=esin3x+x6-2x4-x3-1.在这个区间上画出函数，找出所有的三个根，精确到小数点后6位.确定哪一个根是二次收敛，并找出线性收敛的根对应的多重性.
10.设f(x)=54x6+45x5-102x4-69x3+35x2+16x-4.在区间［-2，2］上画出函数，使用牛顿方法找出该区间上所有的5个根.对于哪些根，牛顿方法线性收敛？对于哪些根，二次收敛？
11.对于低温和低压中的气体的理想气体定律是PV=nRT，其中P是压强（单位atm），V是体积（单位L），T是温度（单位K），n是气体的摩尔数，R=0.0820578是气体的摩尔常数.下面的van der Waals方程P+n2aV2(V-nb)=nRT涵盖了该假设不能成立的非理想情况.使用理想气体定律计算一个初始估计，然后使用牛顿方法求解van der 13.（a） 找出函数f(x)=(1-3/(4x))1/3的根.（b） 使用牛顿方法，初始估计在根的附近，画出前50步的迭代.这是另外一种通过生成混乱的轨迹使得牛顿方法可能失败的情形.（c） 为什么定理1.11和定理1.12失效？
14.（a） 固定实数a，b>0，并使用选择的值画出函数f(x)=a2x4-6abx2-11b2的图.由于a=2，b=1/2对应情况在例1.15已经出现，所以不要使用a=2，b=1/2.（b） 使用牛顿方法找出f（x）的正根和负根.然后找出正的初始估计区间［d1，d2］，其中d2>d1，对于哪一个牛顿方法:（c） 收敛到正根，（d） 收敛到负根，（e） 不收敛到任何根.你的区间中不能包含任何初始估计f′(x)=0，这是由于此时牛顿方法没有定义.60

首先，迭代法解方程的实质是按照下列步骤构造一个序列x0,x1,…,xn,来逐步逼近方程f(x)=0的解:

1）选取适当的初值x0；

2）确定迭代格式，即建立迭代关系，需要将方程f(x)=0改写为x=φ(x)的等价形式；

3) 构造序列x0，x1，……，xn，即先求得x1=φ(x0)，再求x2=φ(x1)，……如此反复迭代，就得到一个数列x0， x1，……，xn，若这个数列收敛，即存在极值，且函数 φ(x)连续，则很容易得到这个极限值

首先我们将方程写成这种形式：

用初始根x0=1.5带入右端，可以得到

这时，x0和x1的值相差比较大，所以我们要继续迭代求解，将x1再带入公式得

直到我们我们得到的解的序列收敛，即存在极值的时候，迭代结束。

下面是这个方程迭代的次数以及每次xi的解（i=0,1,2....）

我们发现当k=7和8的时候，方程的解已经不再发生变化了，这时候我们就得到了此方程的近似解。

注意：如果方程无解，算法求出的近似根序列就不会收敛，那么迭代过程就会变成死循环。因此，在使用迭代算法前应先考察方程是否有解，并在算法中对迭代次数给予限制。

下面再写一个求解方程组的例子加深一下理解：

精确度为1e-8，迭代次数为100

迭代法求解方程的过程是多样化的，比如二分逼近法求解，牛顿迭代法等。

下面就是效率比较高且比较常用的牛顿迭代法：

牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，如下图所示。

首先, 选择一个接近函数f(x)零点的x0, 计算相应的f(x0)和切线斜率f'(x0)（这里f ' 表示函数f的导数）。然后我们计算穿过点 (x0,f (x0))且斜率为f '(x0)的直线方程

和x轴的交点的x的坐标，也就是求如下方程的解

将新求得交点的x坐标命名为x1。如图4所示，通常x1会比x0更接近方程f(x) = 0的解。接下来用x1开始下一轮迭代 .

上式就是有名的牛顿迭代公式。已经证明, 如果f' 是连续的, 并且待求的零点x是孤立的, 那么在零点x周围存在一个区域, 只要初始值x0位于这个邻近区域内, 那么牛顿法必定收敛。

求形如ax^3+bx^2+cx+d=0方程根的算法，系数a、b、c、d的值依次为1、2、3、4，由主函数输入。求x在1附近的一个实根。求出根后由主函数输出。

由以上的公式可得到代码：

接下来说一下二分逼近法

用二分法求一元非线性方程f(x)= x^3/2+2x^2-8=0（其中^表示幂运算）在区间[0，2]上的近似实根r，精确到0.0001.