1、牛顿迭代法 摘要 ：迭代法 是一种不断用变量的旧值递推新值的过程 ，在现代计算机计算方面有着重要应用。牛顿迭代法 是 牛顿 在 17 世纪提出的一种在实数域和复数域上近似求解方程的方法 ， 多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。 关键字 ： 迭代 ； 方程 ； 算法 前言 ： 牛顿法 （ Newtons method）又称为 牛顿 -拉弗森方法 （ Newton-Raphson method）， 牛顿法是一种特殊形式的迭代法，它是求解非线性方程最有效的方法之一。其基本思想是：利用泰勒公式将非线 性函数在方程的某个近似根处展开，然后截取其线
2、性部分作为函数的一个近似，通过解一个一元一次方程来获得原方程的一个新的近似根 。 一、 牛顿迭代法的 起源 在 计算数学 中， 迭代 是通过从一个 初始估计 出发寻找一系列 近似解 来解决问题（一般是解 方程 或者 方程组 ）的 数学 过程，为实现这一过程所使用的方法统称为 迭代法 。 迭代法是求方程近似根的一个重要方法，也是计算方法中的一种基本方法，它的算法简单，是用于求方程或方程组近似根的一种常用的算法设计方法。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程 f(x) = 0 的单根附近具有平 方收敛，而且该法还可以用来求方程的重根、复根。牛顿法是方程求根的一个有力方法，常常能快速
3、求出其他方法求不出或者难以求出的解。 牛顿法最初由 艾萨克 牛顿 在 流数法 （ Method of Fluxions， 1671 年 完成，在牛顿死后的 1736 年 公开发表）。 约瑟夫 拉弗森 也曾于 1690 年 在 Analysis Aequationum 中提出此方法。 二、牛顿迭代法的思想及分析 设当前点为 xk，将 f(x)在 xk 处泰勒展开并截取线性部分得 f(x)f(xk)+f(xk)(xxk) 令上式右端为 0，解得 xk+1=xkf(xk)/f(xk),k=0,1, 该式 称为牛顿迭代公式。根据导数的几何意义及上述推导过程可知，牛顿法的几何上表现为： xk+1是函数
4、f(x)在点 (xk,f(xk)处的切线与 x 轴的交点。因此，牛顿法的本质是一个不断用切线来近似曲线的过程，故牛顿法也称为切线法 。 牛顿迭代法实质上是一种线性化方法 牛顿迭代方法能够有效的基本条件是：迭代公式必须是收敛的（也就是通过迭代运算，每一次的结果必须 是更接近真实值的） 。 具体使用迭代法求根时应注意以下两种可能发生的情况：（ 1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代 算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；（ 2） 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败 。 牛顿迭代法具有
5、较高的收敛速度 ，它的收敛阶数为 P=2；而牛顿迭代法的局部收敛性较强， 只有初值充分地接近 x才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制，必须再增加条件建立以下收敛的充分条件 。 设函 数 f(x) C2a,b,且满足 1) f(a)f(b) 0； 2) f(x) 0，（ x a,b）； 3) f”(x)在 a,b上恒正或恒负； 初值 x0 a,b满足 f(x0)f”(x0) 0 时，由牛顿法产生的序列收敛到 f(x)=0 在 a,b上的唯一根。 由此可知 ，牛顿法的收敛性依赖于初值 x0的选取，如果 x0偏离 x较远，则牛顿法可能收敛缓慢甚至发散。 例如，用牛顿法求方程 x3x1
6、=0 的近似根，如果取 x0=1.5，用牛顿迭代公式 : xk+1=xk(x3kxk1)/(3x2k1) 迭代 3 次可得结果： x1=1.3478， x2=1.3252， x3=1.3247,其误差小于 105。但如果取x0=2.0，则要得到同样精度的解需要迭代 65 次！因此，为了保证当 x0远离 x时，迭代仍然收敛，可在牛顿迭代公式中增加一个参数，改为 xk+1=xkkf(xk)/f (xk),k=0,1, 其中 k的选择保证 |f(xk+1)| #include using namespace std; int main() double diedai(int a,int b,int
7、c,int d,double x); int a,b,c,d; double x=10000.0; coutabcd; x=diedai(a,b,c,d,x); coutx; return 0; double diedai(int a,int b,int c,int d,double x) x=x-(a*pow(x,3.0)+b*pow(x,2.0)+c*pow(x,1.0)+d)/(3*a*pow(x,2.0)+2*b*pow(x,1.0)+c); if(abs(a*x*x*x+b*x*x+c*x+d)=0.000001) return x; else return diedai(a,b,c
8、,d,x); 四、 牛顿迭代法的优 缺 点 牛顿迭代法公式简单，使用方便，易于编程，收敛速度快，是易于求解非线性方程根的有效方法。但同时牛顿迭代法的计算量大，每次迭代都要计算函数值与导 数值，迭代速度较慢。 结论： 在 多数方程不存在求根公式，求精确根非常困难，甚至不可能 的情况下 ，寻找方程的近似根就显得特别重要。方法使用函数 f(x）的泰勒级数的前面几项来寻找方程 f(x) = 0 的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程 f(x) = 0 的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。 参考文献 ： 1 马昌凤，现代数值计算方法 2 黄明游，数值计算方法，科学出版社 3 百度百科 http:/ 4 维基百科 http:/www.wikipedia.org/
