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

1.4　牛顿方法

牛顿方法，也被称为牛顿拉夫逊方法，通常比我们前面看到的线性收敛方法快得多.牛顿方法对应的几何图如图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=x0-f(x0)f′(x0)求解x得到根的近似，我们称之为x1.然后，重复整个过程，从x1开始，得到x2，等等，进而得到如下的迭代公式:

例1.11　找出用于方程x3+x-1=0的牛顿方法公式.
由于f′(x)=3x2+1，公式如下xi+1=xi-x3i+xi-13x2i+1=2x3i+13x2i+1从初始估计x0=-0.7开始，迭代公式得到x1=2x30+13x20+1=2(-0.7)3+13(-0.7)2+1≈0.1271
x2=2x31+13x21+1≈0.9577这些步骤在图1.9中以几何的方式显示.更多的步骤如下表所示:

仅仅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我们使用另一种方式导出牛顿方法，并仔细观察在每步中生成的误差.从误差中，我们想看到真实根和当前最优估计之间的差异.
定理0.8中的泰勒公式告诉我们在给定点和另一个近邻点之间的函数值的差异.对于这两个点，我们使用根r和当前在第i步时的估计xi，第i步后，取两项后面的余项:f(r)=f(xi)+(r-xi)f′(xi)+(r-xi)22f″(ci)这里，ci在xi和r之间.由于r是根，因此，0=f(xi)+(r-xi)f′(xi)+(r-xi)22f″(ci)
-f(xi)f′(xi)=r-xi+(r-xi)22f″(ci)f′(xi)假设f′(xi)≠0.通过重整等式，我们可以比较下一步的牛顿迭代结果和根:xi-f(xi)f′(xi)-r=(r-xi)22f″(ci)f′(xi)
xi+1-r=e2if″(ci)2f′(xi)
ei+1=e2if″(ci)2f′(xi)(1.24)在方程中，我们定义了第i步的误差是ei=xi-r.由于ci在r和xi之间，它会如同xi一样收敛到r，limi→∞ei+1e2i=f″(r)2f′(r)上面的式子满足二次收敛的定义.
我们推导的误差公式（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，这和表右列中的误差率一致.
有了对于牛顿方法的新的理解，我们可以更加全面地解释例1.6中的平方根计算.令a是一个正数，考虑利用牛顿方法寻找方程f(x)=x2-a的根.对于任意a，迭代如下xi+1=xi-f(xi)f′(xi)=xi-x2i-a2xi=x2i+a2xi=xi+axi2(1.26)
54这是例1.6使用的方法.
为了研究其对应的收敛性，计算在根a的位置上的导数f′(a)=2a
f″(a)=2(1.27)由于f′(a)=2a≠0，收敛率为ei+1≈Me2i(1.28)牛顿方法是二次收敛方法，其中M=2/(2·2a)=1/(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处于同一类.
唯一根为r=0，因而定义ei=xi-r=xi得到ei+1=Sei其中S=(m-1)/m.
这是牛顿方法在多重根上的一般情形的例子.注意到多重根定义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）.
很容易验证f(x)=sinx+x2cosx-x2-x
f′(x)=cosx+2xcosx-x2sinx-2x-1
f″(x)=-sinx+2cosx-4xsinx-x2cosx-2并且以上所有式子在r=0的值都为0.而且三阶导数f(x)=-cosx-6sinx-6xcosx+x2sinx(1.30)满足f(0)=-1，所以根r=0是一个三重根，意味着多重性m=3.
使用定理1.12，牛顿方法会线性收敛ei+1≈2ei/3.
使用初始估计x0=1，得到e0=1.在收敛值附近，误差在每一步中会下降2/3.所以，精确到小数点后6位，或者误差小于0.5×10-6，所需步数的粗略估计通过求解下式可以得到23n<0.5×10-6
n>log10(0.5)-6log10(2/3)≈35.78(1.31)

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，可能不会收敛到根.下面的例子是一种可能不收敛的情况.
例1.15　对函数f(x)=4x4-6x2-11/4使用牛顿方法，初始估计x0=1/2.
由于函数是连续函数，在x=0时取负值，并且对于x的大的正数和负数则取无穷大的正值，因此一定存在根.但是如图1.10所示，对于初始估计x0=1/2则找不到根.牛顿公式xi+1=xi-4x4i-6x2i-11416x3i-12xi(1.33)通过替代得到x1=-1/2，进一步x2=1/2.牛顿方法在这个例子中，迭代的结果在1/2和-1/2之间变化，但是二者都不是根，所以求解根的过程失败.

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

(a) x3+x-2=0(b) x4-x2+x-1=0(c) x2-x-1=0
2.应用牛顿方法迭代两步，初始估计x0=1.
(a) x3+x2-1=0(b) x2+1/(x+1)-3x=0(c) 5x-10=0
3.使用定理1.11或定理1.12，在利用牛顿方法收敛到给定根的过程中通过前一项的误差ei估计误差ei+1.收敛速度是线性的还是二次的？58
(a) x5-2x4+2x2-x=0；r=-1,r=0,r=1(b) 2x4-5x3+3x2+x-1=0;r=-1/2,r=1
4.参照习题3估计误差ei+1.
(a) 32x3-32x2-6x+9=0;r=-1/2,r=3/4(b) x3-x2-5x-3=0；r=-1,r=3
5.考虑方程8x4-12x3+6x2-x=0.对于两个解x=0和x=1/2，不进行计算，试确定二分法和牛顿方法哪一个会收敛更快（例如，精确到小数点后8位）.
6.画出一个函数f以及对应的初始估计，使得对应的牛顿方法发散.
7.令f(x)=x4-7x3+18x2-20x+8.牛顿方法是否会二次收敛到根r=2？确定limi→∞ei+1/ei，其中ei表示第i步的迭代误差.
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.4节编程问题
1.每个方程有一个根.使用牛顿方法求近似根，精确到小数点后8位.
(a) x3=2x+2(b) ex+x=7(c) ex+sinx=4
2.每个方程有一个实数根.使用牛顿方法求近似根，精确到小数点后8位.
(a) x5+x=1(b) sinx=6x+5(c) lnx+x2=3
3.使用牛顿方法尽可能精确地找到唯一根，并确定根的多重性.然后使用改进牛顿方法二次收敛到根.报告每个方法中最优近似的前向和后向误差.
(a) f(x)=27x3+54x2+36x+8(b)f(x)=36x4-12x3+37x2-12x+159
4.对下面问题实施编程问题3中的步骤.
(a)f(x)=2ex-1-x2-1(b)f(x)=ln(3-x)+x-2
5.由一个高为10m的圆柱构成的发射井的顶部是一个半球，体积400m3.确定发射井底部的半径，精确到小数点后4位.
6.一个10cm高的圆锥盛有60cm3的冰淇淋，其顶部是一个半球.确定冰淇淋半球的半径，精确到小数点后4位.
7.在区间［-2，2］上考虑函数f(x)=esin3x+x6-2x4-x3-1.在这个区间上画出函数，找出所有的三个根，精确到小数点后6位.确定哪一个根是二次收敛，并找出线性收敛的根对应的多重性.
8.对下面问题进行编程问题7中的步骤，区间为［0，3］，计算f(x)=94cos3x-24cosx+177sin2x-108sin4x-72cos3xsin2x-659.使用牛顿方法找出函数f(x)=14xex-2-12ex-2-7x3+20x2-26x+12在区间［0，3］上的根.对于每个根，打印对应的迭代序列，误差ei，和收敛到非0极限的相关误差率ei+1/e2i或者ei+1/ei.把该极限和由定理1.11中得到的期望M或者定理1.12中得到的S进行匹配.
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 Waals方程找出1摩尔氧气在320K温度，15atm压强下的体积.对于氧气a=1.36L2-atm/mole2，b=0.003183L/mole.写出你的初始估计和具有3个有效数字的解.
12.使用编程问题11中的数据找出1mole苯蒸气在700K温度，20atm压强下的体积.对于苯蒸气，a=18.0 L2-atm/mole2，b=0.1154L/mole.
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