New ton 迭代法求解非线性方程 一、 Newton 迭代法概述 构造迭代函数的一条重要途径是用近似方程来代替原方程去求根。因此，如果能将非线性方程f(x) = 0用线性方程去代替，那么，求近似根问题就很容易解决，而且十分方便。牛顿(Newton)法就是一种将非线性方程线化的一种方法。 设kx 是方程f(x) = 0的一个近似根，把如果)(xf在kx 处作一阶Taylor 展开，即： )xx)(x('f)x(f)x(fkkk (1-1) 于是我们得到如下近似方程： 0)xx)(x('f)x(fkkk (1-2) 设0)('kxf，则方程的解为： x̅ = xk + f(xk)f(xk)́ (1-3) 取x~ 作为原方程(1.1)的新近似根1kx，即令： )x('f)x(fxxkkk1k, k=0,1,2,… (1-4) 上式称为牛顿迭代格式。用牛顿迭代格式求方程的根的方法就称为牛顿迭代法，简称牛顿法。 牛顿法具有明显的几何意义。方程： )xx)(x('f)x(fykkk (1-5) 是曲线 )x(fy 上点))x(f,x(kk处的切线方程。迭代格式(1-4)就是用切线式(1-5)的零点来代替曲线的零点。正因为如此，牛顿法也称为切线法。 牛顿迭代法对单根至少是二阶局部收敛的，而对于重根是一阶局部收敛的。一般来说，牛顿法对初值0x 的要求较高，初值足够靠近*x 时才能保证收敛。若要保证初值在较大范围内收敛，则需对)x(f加一些条件。如果所加的条件不满足，而导致牛顿法不收敛时，则需对牛顿法作一些改时，即可以采用下面的迭代格式： )x('f)x(fxxkkk1k,,2,1,0k (1-6) 上式中， 10，称为下山因子。因此，用这种方法求方程的根，也称为牛顿下山法。 牛顿法对单根收敛速度快，但每迭代一次，除需计算)x(fk 之外，还要计算)x('fk 的值。如果)x(f比较复杂，计算)x('fk 的工作量就可能比较大。为了避免计算导数值，我们可用差商来代替导数。通常用如下几种方法： 1. 割线法 如果用 1kk1kkxx)x(f)x(f代替)x('fk ，则得到割线法的迭代格式为： )x(f)x(f)x(fxxxxk1kk1kkk1k (1-7) 2. 拟牛顿法 如果用)x(f))x(fx(f)x(fk1kkk代替)x('fk ，则得到拟牛顿法的迭代格式为： ))x(fx(f)x(f)x(fxx1kkkk2k1k (1-8) 3. Steffenson 法 如果用)x(f)x(f))x(fx(fkkkk代替)x('fk ，则得到拟牛顿法的迭代格式为： )x(f))x(fx(f)x(fxxkkkk2k1k (1-9) 二、 算法分析 1. 割线法 割线法的迭代公式为： )x(f)x(f)x(fxxxxk1kk1kkk1k,k=0,...
