当前位置：文档之家 › Newton迭代法

Newton迭代法

  • 格式：doc
  • 大小：422.50 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

分析论述牛顿迭代法

分析论述牛顿迭代法

分析论述牛顿迭代法
牛顿迭代法（Newton's Iteration Method）是一种常用的数
值计算方法，它是由英国数学家牛顿发明的。

它的最大优点是收敛速度快，可以快速地求解方程的根，有效地减少计算时间，是解决方程组和非线性方程的有效方法。

牛顿迭代法是一种基于牛顿插值多项式的数值计算方法。

它把待求解函数f（x）看做一个多项式，然后按照牛顿插值
多项式的算法，从x0出发，反复求解f（x）的极值点，直至
收敛，从而找到函数f（x）的根。

牛顿迭代法的具体步骤如下：（1）给定函数f（x）的初
值x0；（2）计算f（x）的极值点x1；（3）根据误差e = |x1 - x0|，选定迭代次数或者误差界限；（4）更新x0 = x
1，重复（2）（3）步骤，直至误差小于指定界限；（5）得到函数f（x）的根。

牛顿迭代法的收敛速度很快，只需要几次迭代就可以求得函数f（x）的根，而且这种方法也比较简单易行，只要给出
初值，就可以用它来求解一般的非线性方程。

牛顿迭代法的主要缺点是只能求解单根问题，即一元函数的根。

另外，牛顿迭代法的初值必须比较接近函数f（x）的根，如果初值比较远，迭代收敛的速度就会变慢，甚至不收敛。

总之，牛顿迭代法是一种有效的求解一元函数的根的方法，它的收敛速度快，可以有效地减少计算时间。

但是，它只能求解单根问题，而且初值也必须比较接近函数f（x）的根，否
则它的收敛速度就会变慢。

第三章 迭代法s3 Newton迭代法

第三章 迭代法s3 Newton迭代法
1kkxx???其中fxfx?xx?????2fxfxxfx???x0?newton法至少二阶局部收敛定理设fx在其零点x的某个邻域内二阶连续可导且fx?0则存在x的某个?邻域nxx?x?使得对?x0?nxnewton法产生的序列以不低于二阶的收敛速度收敛到x
第三章 迭 代 法
第三节 Newton迭代法 Newton迭代法
Newton迭代法发散的例子 迭代法发散的例子
举例（ 举例（一）
例: 设计一个二阶收敛算法计算 a (a > 0)。 。 解：转化为求 x2-a = 0 的正根
2 f ( xk ) xk − a 1 a = xk − = xk + Newton 迭代： xk +1 = xk − 迭代： f ′( xk ) 2 a xk + a − 2 xk a xk +1 − a = − a = = 2 xk 2 xk 2 xk 2 k
(
)
2
(x
xk +1 − a
k
− a
)
2
=
1 2 xk
1 2 a
二阶收敛
练习：设计一个局部收敛的迭代算法只用加、 练习：设计一个局部收敛的迭代算法只用加、减、乘法 计算倒数1/ 计算倒数1/a。
Newton迭代 迭代
基本思想： 将非线性方程线性化 基本思想： 将非线性方程
的近似根， 展开: 设 xk 是 f (x)=0 的近似根， 将 f (x) 在 xk Taylor 展开 f ′′(ξ ) ′( xk )( x − xk ) + f ( x) = f ( xk ) + f ( x − xk )2 , ξ 在 xk 和 x 之间 之间. 2! f ( xk ) ≈ f ( xk ) + f ′( xk )( x * − xk ) x* ≈ xk − 0 = f ( x*) f ′( xk ) y f ( xk ) xk +1 = xk − f ′( xk )

研究生数值分析(5)牛顿(Newton)迭代法

研究生数值分析(5)牛顿(Newton)迭代法

z
0.612547 0.641384 0.641186
6 求方程 m重根的Newton法 设 s 是方程 f(x)=0 的 m 重根(m≥2), f(x)
在 s 的某邻域内有m阶连续导数 ,这时
f (s) f (s) f (m1) (s) 0, f (m) (s) 0
由Taylor公式,得
设 f '(x) 0 ，上式解为
x

xk

f (xk ) f ' (xk )
于是方程 f(x)=0的新的近似根xk+1，可由牛顿
迭代公式
xk 1

xk

f (xk ) f ' (xk )
k 0,1, 2,
求出
牛顿迭代公式具有明显的几何意义。 方程 y f (xk ) f '(xk )(x xk ) 是曲线 y=f(x)在点 (xk , f (xk )) 处的切线方程，迭代公式就是切线与x轴 交点的横坐标。因此，牛顿迭代法又称为切线法。
这表明牛顿迭代法用于求单根时至少是二阶收敛的。
（2）若 x* 是方程 f (x) 0 的 m(m 2) 重根，
即
f (x) (x x*)m q(x)
(q(x*) 0)
此时有
g ' (x*) lim g ' (x) lim
x x*
x x*
f (x) f '' (x) [ f ' (x)]2
k
xk
k
xk
4 0.635498 8 0.640964
5 0.643719 9 0.641285
6 0.640061 10 0.641142

Newton迭代法求解非线性方程

Newton迭代法求解非线性方程

Newton迭代法求解非线性方程一、 Newton 迭代法概述构造迭代函数的一条重要途径是用近似方程来代替原方程去求根。

因此，如果能将非线性方程f (x )=0用线性方程去代替，那么，求近似根问题就很容易解决，而且十分方便。

牛顿(Newton)法就是一种将非线性方程线化的一种方法。

设k x 是方程f (x )=0的一个近似根，把如果)(x f 在k x 处作一阶Taylor 展开，即：)x x )(x ('f )x (f )x (f k k k -+≈ (1-1)于是我们得到如下近似方程：0)x x )(x ('f )x (f k k k =-+ (1-2)设0)('≠k x f ，则方程的解为：x ̅=x k +f (x k )f (x k )́(1-3)取x ~作为原方程的新近似根1+k x ，即令： )x ('f )x (f x x k k k 1k -=+, k=0,1,2,…(1-4)上式称为牛顿迭代格式。

用牛顿迭代格式求方程的根的方法就称为牛顿迭代法，简称牛顿法。

牛顿法具有明显的几何意义。

方程：)x x )(x ('f )x (f y k k k -+= (1-5)是曲线)x (f y =上点))x (f ,x (k k 处的切线方程。

迭代格式(1-4)就是用切线式(1-5)的零点来代替曲线的零点。

正因为如此，牛顿法也称为切线法。

牛顿迭代法对单根至少是二阶局部收敛的，而对于重根是一阶局部收敛的。

一般来说，牛顿法对初值0x 的要求较高，初值足够靠近*x 时才能保证收敛。

若要保证初值在较大范围内收敛，则需对)x (f 加一些条件。

如果所加的条件不满足，而导致牛顿法不收敛时，则需对牛顿法作一些改时，即可以采用下面的迭代格式：)x ('f )x (f x x k k k 1k λ-=+,⋯=,2,1,0k (1-6)上式中，10<λ<，称为下山因子。

牛顿-拉夫逊方法_百度百科

牛顿-拉夫逊方法_百度百科
设r是f(x) = 0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y = f(x)的切线L，L的方程为y = f(x0)+f'(x0)(x-x0)，求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0)，称x1为r的一次近似值。过点（x1,f(x1)）做曲线y = f(x)的切线，并求该切线与x轴的横坐标 x2 = x1-f(x1)/f'(x1)，称x2为r的二次近似值。重复以上过程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f'(x(n))，称为r的n+1次近似值，上式称为牛顿迭代公式。
解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点附近展开成泰勒级数 f(x) = f(x0)+(x－x0)f'(x0)+(x－x0)^2*f''(x0)/2! +… 取其线性部分，)+f'(x0)(x－x0)=f(x)=0 设f'(x0)≠0则其解为x1=x0－f(x0)/f'(x0) 这样，得到牛顿法的一个迭代序列：x(n+1)=x(n)－f(x(n))/f'(x(n))。
牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。

牛顿迭代法(Newton‘s Method)

牛顿迭代法(Newton‘s Method)

牛顿迭代法（Newton’s Method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson Method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

与一阶方法相比，二阶方法使用二阶导数改进了优化，其中最广泛使用的二阶方法是牛顿法。

考虑无约束最优化问题：其中 \theta^{\ast} 为目标函数的极小点，假设 f\left( \theta \right) 具有二阶连续偏导数，若第 k 次迭代值为 \theta^{k} ，则可将f\left( \theta \right)在\theta^{k}近进行二阶泰勒展开：这里，g_{k}=x^{\left( \theta^{k} \right)}=∇f\left( \theta^{k} \right)是f\left( \theta \right) 的梯度向量在点 \theta^{k}的值， H\left( \theta^{k} \right) 是 f\left( \theta \right) 的Hessian矩阵：在点 \theta^{\left( k \right)}的值。

函数 f\left( \theta \right) 有极值的必要条件是在极值点处一阶导数为0，即梯度向量为0，特别是当H\left( \theta\right) 是正定矩阵时，函数 f\left( \theta \right) 的极值为极小值。

牛顿法利用极小点的必要条件：这就是牛顿迭代法。

迭代过程可参考下图：在深度学习中，目标函数的表面通常非凸（有很多特征），如鞍点。

因此使用牛顿法是有问题的。

如果Hessian矩阵的特征值并不都是正的，例如，靠近鞍点处，牛顿法实际上会导致更新朝错误的方向移动。

这种情况可以通过正则化Hessian矩阵来避免。

常用的正则化策略包括在Hessian矩阵对角线上增加常数α 。

正则化更新变为：这个正则化策略用于牛顿法的近似，例如Levenberg-Marquardt算，只要Hessian矩阵的负特征值仍然相对接近零，效果就会很好。

牛顿迭代法

xn1 xn e 1 xn (1ห้องสมุดไป่ตู้ xn )e xn
xn
x exp(x)-1 1 0 -1 0 0.5 x 1
(n = 0, 1, · · · · · )
f=inline('x*exp(x)-1'); f1=inline('(x+1)*exp(x)'); x0=0.5;er=1;k=0; while er>0.00001 x=x0-f(x0)/f1(x0); er=abs(x-x0) x0=x;k=k+1 end
( x ) f ( x ) f ( x ) /[ f ( x )] 0
* * * * 2
f ( x ) ( x ) * f (x )
* *
所以, Newton迭代法至少平方收敛。
9/26
例2. 求 f(x)=xex – 1= 0 在 x0=0.5 附近的根 解: f ( x) (1 x)e x 迭代格式为
收敛到的牛顿迭代初值点集合收敛到的牛顿迭代初值点集合收敛到的牛顿迭代初值点集合2526由于现代意义上的标准化是在资本主义企业里发展起来的资本家所关心的是标准化的应用效果不可能支持企业里的标准化工作者去从事理论研究
牛顿(Newton)迭代法 平方根算法求 初值: x1=1.5
(n = 1,2,· · · · · )
17/26
f ( x1 ) x2 x1 ( x1 x0 ) f ( x1 ) f ( x0 ) f ( xn ) xn 1 xn ( x n x n 1 ) f ( x n ) f ( x n 1 ) ( n =1,2,· · · · · · ·)
例2.8 确定悬链线方程

数值分析3-牛顿迭代法

§3 牛顿迭代法Newton Iteration————切线法牛顿迭代法是最著名的方程求根方法。

已经通过各种方式把它推广到解其他更为困难的非线性问题。

【例如】非线性方程组、非线性积分方程和非线性微分方程。

虽然牛顿法对于给定的问题不一定总是最好的方法，但它的简单形式和快的收敛速度常常使得解非线性问题的人优先考虑它。

迭代一般理论告诉我们，构造好的迭代函数可使收敛速度提高。

然而迭代函数的构造方法又各不相同，方法多样。

牛顿法是受几何直观启发，给出构造迭代函数的一条重要途径。

牛顿迭代的基本思想:方程f(x)=0的根，几何意义是曲线y=f(x)与ox轴y=0的交点。

求曲线与y=0的交点没有普遍的公式，但直接与0x 轴的交点容易计算。

用直线近似曲线y=f(x)，从而用直线方程的根逐步代替f(x)=0的根。

即把非线性方程逐步线性化。

方法：设x k是f(x)=0的一个近似根，把f(x)在x k处作一阶Taylor 展开，得到))(()()(k k k x x x f x f x f -'+≈ （19）设)(k x f '≠0，由于0)())(()(=≈-'+x f x x x f x f k k k所以求得解记为1+k x ，有牛顿迭代公式：（20） 按牛顿迭代计算称为牛顿迭代法。

牛顿法的几何意义：选初值x k 以后，过))(,(k k x f x p 点，作曲线y=f(x)的切线，其切线方程为))(()()(k k k x x x f x f x f -'+= (21)切线与ox 轴的交点，为1+k x ，则)(/)(1k k k k x f x f x x '-=+（22）牛顿迭代法也称为切线法。

迭代法的收敛性：如果取)(/)()(k k x f x f x x g '-=，则有x=g(x)，从而牛顿迭代公式就是)(1k k x g x =+因此就可以由考察g(x)的性质，来讨论迭代法的收敛性及收敛速度。

牛顿迭代法

一 .牛顿迭代法简介1.牛顿迭代法的产生背景牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。

方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。

牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x)=0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根,此时线性收敛，但是可通过一些方法变成超线性收敛。

另外该方法广泛用于计算机编程中。

利用牛顿迭代法来解决问题需要做好的工作：（1）确定迭代变量。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

（2）建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

（3）对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

2.牛顿迭代法的概述牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。

方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。

7.3 Newton迭代法


4
f a f b b a, b a; f ' a f ' b
则对任意的初始值x0 a , b ,由Newton法产生 的序 xk 列都收敛到方程f ( x ) 0在区间 a , b 内的 唯一解x * , 且收敛阶数为2. 在定理7.3.3中 条件 1 保证方程f ( x ) 0在区间 a , b 内至少有一个根.
Newton法的一个重要应用是计算平方根 d , d 0. 令
xk xk 1
因此
f ' xk 1
f xk 1
xk 1 3 xk 1 1 xk 1 , k 1, 2, . 2 3 xk 1 1
x0 3 x0 1 ( 0.7)3 0.7 1 x1 x0 0.7 0.12712550607. 2 2 3 x0 1 3( 0.7) 1
0 f x f ' x
*
1 2 f x f x f ' x x x f " ( x ) x x , 2
7.3.2

1 x x f " ( x* ) 2
*


x
*
x

2
.
7.3.3
关于初始点的选取, 有如下定理.
定理7.3.3 设函数f ( x )在区间 a , b 上具有二阶导数,
且满足以下条件 :
1 2 3
f a f b 0; f ( x ) 0, x a , b ; f ( x )在区间 a , b 上不变号;
设f ( x )在区间[a , b]上二阶连续可微, 设x [a , b] 是方程 7.3.1的根x *的近似, 且f ' x 0及 | x * x | “较小”.考虑f ( x )关于x展开的一阶Taylor多项式
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第四章 一元方程求根/非线性方程组数值解法初步4．3 Newton 迭代法 1. Newton 迭代法解一元非线性方程组0)(=x f （4.3.1）的Newton 迭代法是不动点迭代法的一种特殊形式。

可从不同途径导出Newton 迭代公式，这里采用Taylor 展开。

设方程0)(=x f 的根*x 的一个近似值0x ,将)(x f 在0x 附近展开得20000)(!2)(''))((')()(0x x f x x x f x f x f -+-+==ξ 或表示为 200000)()('2)('')(')(x x x f f x f x f x x ---=ξ （4.3.2）其中设0)('0≠x f ，''f 存在、连续，而ξ在x 与0x 之间。

忽略上式最后一项*x 的一个新近似值)(')(0001x f x f x x -= 把1x 代替上式右端的0x ，并设0)('1≠x f ，于是又得新近似值)(')(1112x f x f x x -=如此继续，可知当),2,1,0(0)(' =≠k x f k 可得),2,1,0()(')(1 =-=+k x f x f x x k k k k （4.3.3）这就是著名的Newton （牛顿）迭代公式。

在迭代序列收敛的情况下，取一定精度的迭代值kx 作为方程0)(=x f 的根*x 的近似值，这就是解方程组0)(=x f 的Newton 迭代法。

显然，它以在*x 附近函数0)(=x f 线性化为基础，并以),2,1,0(0)(' =≠k x f k 为前提。

例 4.3.1 用Newton 迭代法求下列方程的近似根：1-x xe =0解 令 1)(-=x xe x f ,则x x xe e x f +=)(',于是迭代公式为),1,0(11 =+--=+k ex e e x x x kkkxk x x k k k 整理得),1,0(11 =+--=-+k x e x x x kxk k k k取5.00=x 请同学们自己动手完成2．Newton 迭代法的收敛性Newton 迭代公式作为不动点迭代，其迭代函数为 )(')()(x f x f x x -=ϕ 从而有222)]('[)('')()]('[)('')()]('[1)('x f x f x f x f x f x f x f x =--=ϕ 可见，如果在方程0)(=x f 的根*x 的某个邻域内0)('0≠x f (从而有0)('*≠x f ，即*x 是单根的情况)，''f 存在并连续（从而有界），则只要x 足够靠近*x ，(从而|)(|x f 足够靠近0)，就有1|)('|<≤L xϕ,于是根据定理4.2.1的推论，Newton 迭代公式收敛于*x ，并且0)(*=x f 导致 0)('*=x ϕ，于是又根据收敛阶的判定定理4.2.4 ，可知Newton 迭代公式在单根附近至少是2阶的。

下面陈述定理。

定理 4.3.1 设0)(*=x f , 0)('*≠x f , 且在*x 的邻域上''f 存在、连续，则可得(1) Newton 迭代公式在单根情况下至少2阶收敛；(2) )('2)('')()(lim **2**1x f x f x x x x k k k =--+∞→ （4.3.4） 证明： 只须证明结论(2). （4.3.2）式中的0x 和x 可分别换为k x 和*x ， 在k x 这一点用Taylor 展开得2**)()('2)('')(')(k k k k k x x x f f x f x f x x ---=ξ再与)(')(1k k k k x f x f x x -=+相减，则易得2**1)()('2)(''k k k x x x f f x x -=-+ξ注意到：当∞→k 时，*x →ξ， *x x k →，由上式取极限即可得结论(2)3．Newton 法的计算机算法 ① )(00x f F =； )(''00x f F =② 如果 0'0=F ，则输出“方法失败”并停机③ 对 ,,,2,1K k =做a. '/0001F F x x -=b. )(11x f F =; )(''11x f F =c. 如果101||ε<-x x 或 21||ε<F ，则输出近似解1x 和k 值并停机。

d. 如果 0'1=F ，则输出“方法失败”并停机e. '';;101010F F F F x x ===④ 输出“经K 次迭代仍无满足要求的近似解”并停机。

4．Newton 法对方程重根的处理 对于 *x 为0)(=x f 的m 重根(1>m )的情形，这时)()()(*x g x x x f m -=其中g2阶可导，0)(*≠x g ，于是由)(')()()()()()(')()(*1**x g x x x g x x m x g x x x x f x f x x mm m -+---=-=-ϕ=)(')()()()(**x g x x x mg x g x x x -+-- '***)(')()()()()()()()(1)('⎥⎦⎤⎢⎣⎡-+---+-=x g x x x mg x g x x x g x x x mg x g x m ϕ令*x x =带入上式，可知当1>m 时，111)('*<-=mx ϕ 0)('*≠x ϕ 根据收敛阶判别定理，Newton 法在重根的情形下只能保证有1阶收敛的。

对此 ，人们提出改善重根情形Newton 法收敛性的两种方法。

方法1： 如果已知重根的重数m ,则利用m 构造迭代公式),2,1,0()(')(1 =-=+k x f x f m x x k k k k这时迭代函数)(')()(x f x f m x x -=ϕ，容易求出0)('*=x ϕ，故迭代公式)(')(1k k k k x f x f mx x -=+至少2阶收敛的。

这种方法的缺点是要事先知道重根的重数，但实际应用中往往不知道。

方法2：做)(')()(x f x f x F =。

如果*x 是0)(=x f 的m 重根(1>m ),则*x 是0)('=x f 的1-m 重根，从而*x 是)(x F 的单根。

于是对0)(=x F 使用Newton 迭代，则新的迭代公式也是2阶收敛。

注意到))]('[)('')()]('[/())(')(()')(')(/()(')()(')(22x f x f x f x f x f x f x f x f x f x f x F x F -== )('')()]('[)(')(2x f x f x f x f x f -= 新迭代公式),2,1,0()('')()]('[)(')(21 =--=+k x f x f x f x f x f x x k k k k k k k 这种方法缺点是需要f的2阶导数。

5．Newton 法应用的几点注意① Newton 迭代法可用来求平方根，如求)0(>c c 。

令 c x =，则c x =2得方程0)(2=-=c x x f其正根想x>0 即cNewton 迭代公式 ),2,1,0(221 =--=+k x cx x x kk k k或整理成),2,1,0)((211=+=+k x cx x kk k 且 221)(21)2(21c x x c c x x x c x k kk k k k -=+-=-+故对任意的00>x ,均有 ),2,1,0( =>k c x k 。

又有0)(2121<-=-+k kk k x c x x x 故知迭代序列}{k x 是有下界的单调递增递减序列，从而有极限*x 。

对迭代公式两边取极限得)(21***xcx x +=，即c x =，这说明只需要取00>x 迭代公式收敛于c .② Newton 迭代法也可用来求方程的复根***υi u x +=(如果有复根的话)，这时初值应取 000υi u x +=，并在迭代时用复数运算即可。

③ Newton 迭代法对初值的近似程度要求很高，因此，应用中必要时先用二分法求出足够精确的0x ，然后在用 Newton 法迭代到收敛为止。

④解决Newton 法初值0x 近似要求的另一种途径是结合所谓“下山算法”。

对方程0)(=x f ，下山算法是指在迭代过程中附加一个使)(x f 按模下降的约束条件|)(||)(|1k k x f x f <+ 以确保迭代过程不发散或不原地踏步。

把下山算法和Newton 法结合称为Newton 下山法，其做法是：引入下山因子λ，将Newton 公式修改为 ),2,1,0()(')(1 =-=+k x f x f x x k k k k λ对初值0x ，依次以 ,21,21,12=λ(或再加上限制λελ≥，λε为下山因子的下界)计算出相应的1x ，并相应检验下降条件，直至出现下降条件|)(||)(|1k k x f x f <+成立。

然后才继续以Newton 公式(1=λ)加速(2阶)迭代。

如果又出现下降条件不成立，又重新操作上述选择λ的过程。

4．4 Aitken 加速方案/Steffensen 迭代法仅有线性收敛速度的一般不动点迭代法并不理想，而具有2阶收敛速度的Newton 法则要求条件较高。

因此，突破线性收敛速度的研究得到广泛的关注，已经提出一些效果显著的可行方案。

1．Aitken 加速方案假设迭代序列 }{k x 线性收敛，按线性收敛的定义应有0*1*≠≈--+k kk C x x x x ，同理，也应有011*2*≠≈--+++k k k C x x x x 。

因此，当k 充分大时，1+≈k k C C ，故有1*2**1*+++--≈--k k k k x x x x x x x x 从中解出*x ，则得kk k k k k k k k k k k x x x x x x x x x x x x x +---=+--=+++++++++12212212212*2)(2 ( 4.4.1 )或kk k k k k x x x x x x x +---==++++12212*2)( ( 4.4.2 ) 这表明，当由某种迭代计算出k x ，1+k x ,2+k x 之后，用（4.4.1）式或(4.4.2)式的值作为*x 的近似值，并记为k x ，可望得到有更好的近似效果。