牛顿法及牛顿下山法
简介：牛顿迭代法是求解单变量非线性方程f(x)=0中最实用的方法，该方法在单根附近二阶收敛。但应用时要选用较好的初值x0近似才能保证迭代收敛。为克服这一缺点，可使用牛顿下山法。下面对牛顿迭代法和牛顿下山法的概念、基本思想、程序实现及例题做进一步介绍。
一、牛顿法
1、定义及定理
如果函数f（x）在[a,b]上有二阶导数，f(a)*f(b)<0，且f'(x)与f"(x)在[a,b]上不变号，则有f(x)在[a,b]内有且仅有唯一的实根。此时，可以构造一种常用的切线迭代法来求方程根的近似值，这种方法称为Newton迭代法。
2、基本思想
首先选取函数值与二阶导数同号的端点，做曲线f(x)的切线，此切线与x轴交于[a,b]内一点x1;在做曲线f(x)对应于点x1的切线并交于x轴与另一点x2;依次类推，切线与x轴的交点将快速逼近函数f(x)的零点。此时，将切线与x轴的交点作为方程的近似根。适用情况如下图所示。
误差分析：当
时，
。其中m=min{|f'(a)|,|f'(b)|}。详细推导参照《高等数学简明教程上》，马知恩著。
具体步骤：
步1：选定初始近似值x0，计算f0=f(x0),f'0=f'(x0)。注意：取迭代初值x0，一般取x0=a，或x0=b(要求f(x0)与f''(x0)同号)。
步2：迭代。按公式
迭代一次，得到新的近似值x1，计算f1=f(x1),f'1=f'(x1)。
步3：误差控制。如果x1满足
,或
,或
，则迭代终止，以x1作为所求的根。否则转步骤4。此处
为允许误差。
步4：修改。如果迭代次数达到预先指定的次数N,或者f'1=0，则此方法失败；否则以(x1,f1,f'1)代替（x0,f0,f'0）转步骤2继续迭代。
3、程序实现
function x=newtoniteration(fun,dfun,x0,EPS) %简单牛顿迭代法
%fun即迭代函数，dfun即迭代函数的一阶导数，x0为迭代初值，EPS为精度
f=fcnchk(fun);
df=fcnchk(dfun);
x1=x0-f(x0)/df(x0);
d=norm(x1-x0);
k=1;
while d>=EPS
x0=x1;
x1=x0-f(x0)/df(x0);
d=norm(x1-x0);
k=k+1;
end
if k==1000
x='fasan';
else
x=x1; %切记要给x赋值
end
4、例题
用牛顿迭代法求解方程
。此方程在x=1.5附近有一个根x*
（1）x0=1.5;调用函数 x=newtoniteration('x^3-x-1','3*x^2-1',1.5,1.0e-5)，可得：
1.325200398950907
1.324718173999054
1.324717957244790
迭代次数为3，结果为x=1.324717957244790
（2）x0=0.6;调用函数 x=newtoni调用函数 x=newtoniteration('x^3-x-1','3*x^2-1',1.5,1.0e-5)，可得：
11.946802328608761
7.985520351936208
5.356909314795458
3.624996032946096
2.505589190106631
1.820129422319469
1.461044109887682
1.339323224262526
1.324912867718656
1.324717992637815
1.324717957244747
迭代一次的初值为x1=17.9，这个结果比x0=0.6更偏离了原来的根x*=1.32472.
由此可以发现，采用牛顿迭代法，在给定区间内求解非线性方程的根，初值的选择极为重要。它不仅影响在给定精度下的迭代次数，而且可能出现切线与x轴交点超出函数定义区域之外。因此又提出了牛顿下山法。
二、牛顿下山法
1、定义：在牛顿迭代过程中，若满足单调性|f(x(k+1))|<|f(x(k))|，则称牛顿法为牛顿下山法。迭代过程为：
为下山因子（
）
它改进了牛顿法对初值的依赖性，当所选初值不合适时（不满足单调性|f(x(k+1))|<|f(x(k))|），可以通过缩小下山因子，减小下一个点x(k+1)与x(k)的距离（缩小步长），若不合适则继续缩小。下山因子 可用逐步搜索法确定，即先令下山因子=1，判断单调性是否成立，若不成立将缩小1/2，直到单调性满足为止。
2、程序实现
function x=Newtondownhillmethod(fun,dfun,x0,EPS) %简单牛顿迭代法
%fun即迭代函数，dfun即迭代函数的一阶导数，x0为迭代初值，EPS为精度
f=fcnchk(fun);
df=fcnchk(dfun);
x1=x0-f(x0)/df(x0);
d=norm(x1-x0);
k=1;
r=1;
while d>=EPS
while abs(f(x1))>abs(f(x0)) %迭代过程一定具有单调性|f(k+1)|<|f(k)|
r=r/2; %调整下山因子保证其单调性
x2=x0-r*f(x0)/df(x0);
x1=x2;
end
x0=x1;
r=1;
x1=x0-f(x0)/df(x0);
disp(x1);
disp(f(x1));
d=norm(x1-x0);
k=k+1;
end
if k==1000
x='Iterative divergence'; %迭代公式发散
else
x=x1; %切记要给x赋值
end
x0=0.6;调用函数 x=newtoni调用函数 x=Newtondownhillmethod('x^3-x-1','3*x^2-1',1.5,1.0e-5)，可得：
1.3668
0.1866
1.3263
0.0067
1.3247
9.6739e-06
1.3247
2.0449e-11
x = 1.3247
可以发现：给定相同的初值x0=0.6，采用牛顿下山迭代法运算次数为4次。降低了运算量，提高了程序的运行效率。
切记牛顿下山法的条件为：|f(x(k+1))|<|f(x(k))|，只有这样，
，从而使序列{x(k)}收敛。
其实，Matlab软件中已经提供了求解非线性方程的根的命令fzero函数，其格式为：
1、c=fzero(f,v,[a,b])------求函数f关于自变量v在【a,b】内的零点c；
2、c=fzero(f,v,x0)----------求函数f关于自变量v在x0内的零点c；
>> fzero('x^3-x-1',x,0.6)
ans = 1.3247
不妥之处，敬请指点。
本文部分程序引用CSDN会员 Jxufe渣渣斯 的文章《牛顿迭代法的MATLAB程序》，在此表示感谢。