1、毕业论文文献综述 信息与计算科学 非线性方程的 Newton 解法 一、前言部分 在实际情况中 ,经常会遇到求解高次 代数方程 或含有 三角函数 、 指数函数 、对数函数等超越函数 的 超越方程 问题 ,我们把这些方程统称为非线性方程 1。 在非线性方程中 ,除了二次、三次、四次代数方程外 ,求解其他的方程不但没有一般的公式 ,而且若只依据方程本身来判别是否有根及根的个数是很困难的 。 因此，研究非线性方程的数值解法非常必要。非线性方程的求根通常分为两个步骤： 一是对根的搜索，分析方程存在多少个根，找出每个根所在区间；二是根的精确化，求得根的足够精确的近似值。 科学研究和工程计算中常常遇到求解
2、非线性方程（组）的问题。 数值分析中牛顿迭代法是求解非线性方程的基本方法。此外，它还有二分法，简单迭代法，割线法、插值法等。 在求方程近似根的方法中最直观、最简单的方法是二分法 2。二分法以连续函数的介值定理为基础。考虑方程 0fx 。设函数 ,f x C a b 且 0f a f b ，则方程在 ,ab 内至少存在一个根。二分法的基本思想是：用对分区间的方法根据分点处函数 fx的符号逐步将有根区间缩小，使在足够小的区间内，方程有且仅有一根。 迭代法 2是数值计算中一类典型方法，不仅用于方程求根，而且用于方程组求解，矩阵求特征值等方面。迭代法的基本思想是一种逐次逼近的方法。首先取一个粗糙的近似
3、值，然后用同 1个递推公式，反复校正这个初值，直到满足预先给出的精度要求为止。 割线法 3的基本思想 是任取两个互异点，做出通过这两个点的割线，用割线的 x 截距作为函数零点的新近似并放弃最早的那个点，此时我们并不清楚当前的这两个点是否构成有根区间，因而在迭代过程中，割线法即可以是反线性插值（有根区间时），也可以是外推（非有根区间）。 本文综述 非线性方程的 Newton 格式，包括相应的收敛性分析和误差分析。 伴随着牛顿法理论的发展与实际应用，如何改进牛顿算法，来减少计算量以提高运算效率 4是目前的争论焦点。 二、主题部分 2.1 牛顿法的起源和发展 5 有关特殊的 非线性方程求根问题的迭代
4、法最早出现在古希腊、巴比伦和印第安人的著作中。这些方法比微积分的发明还要早，它们都基于代数和几何推理。牛顿法的历史令人关注，这种方法只有一部分归功于牛顿本人。虽然早在 1665 年牛顿就使用了与割线法等价的方法，但直到 1669 年牛顿才第一次提出了与现在的牛顿法基本等价的方法。令人惊讶的是，牛顿提出的方法本身并没有使用导数（他是在文章中的另一处介绍的），而是基于二项展开式，因此开始只适用于多项式。牛顿法在很大程度上是受到了另一个与之紧密相关的方法的影响，这种方法是在 1600 年由 Vieta 所 提出的。 1690 年，拉弗森（ Raphson） 对牛顿法作了简化和改进，称为牛顿 -拉弗森
5、方法，至今仍被经常使用。在牛顿法中使用导数是由辛普森（ Simpson） 在 1740 年首次提出的，这才是我们现在所称的牛顿法，辛普森还将这种方法从一维空间扩展到多维空间。 1798 年，拉格朗日提出了牛顿法简单而精巧的表达式，并在 1831年由傅立叶作了推广，此时 Vieta 和辛普森的贡献似乎被遗忘，只留下了与该方法有关的牛顿的名字（有时也有拉弗森的名字）。辛普森在牛顿法中的贡献可能要比在辛普森法中的贡献还要大。 2.2 牛顿法的格式 2-10 用迭代法求方程 0fx （ 2-2-1） 的根时，首先要把它写成等价形式 xx （ 2-2-2） 迭代函数 x 构造得好坏，不仅影响收敛速度，而
6、且迭代格式有可能发散。怎样选择一个迭代函数能够 保证迭代序列一定收敛呢？ 构造迭代函数的一条重要途径是用近似方程来代替原方程去求根。因此如果能将非线性方程（ 2-2-1）用线性方程来代替，那么，求近似根问题就很容易解决，而且十分方便。 Newton法就是把非线性方程线性化的一种方法。 设 kx 是式（ 2-2-1）的一个近似根，把 fx在 kx 处作 1 阶 Taylor 展开，即 k k kf x f x f x x x 于是我们得到如下近似方程 0k k kf x f x x x （ 2-2-3） 设 0kfx ，则方程（ 2-2-3）的解为 kkkfxxx fx 取 x 作为原方程（ 2
7、-2-1）的新的近似根 1kx ，即令 1 kkk kfxxx fx 0,1,2,k （ 2-2-4） 称式（ 2-2-4）为 Newton 迭代格式。用 Newton 迭代格式（ 2-2-4）求方程（ 2-2-1）根的方法称为 Newton 迭代法，简称 Newton 法。 2.3 牛顿法的收敛性和误差分析 1、收敛性 6-10 牛顿法的迭代公式类似于不动点迭代法： 1 nn n nnfxx x g xfx 如果 1gx ，则迭 代法收敛。对 gx求导数，我们立即得到使方法收敛的条件是 2 1f x f xgx fx 这里要求函数 fx和它的导数 fx ， fx 都连续。下面我们证明牛顿法是
8、二阶收敛的。 如前所述，我们有 1nnR x g R g x （ 2-3-1） 把 ngx 在 nxR 处作泰勒展开，有 2/2n n ng x g R g R R x g R x （ 2-3-2） 其中 介于 R 和 nx 之间。因为 0fR ，所以由式（ 2-3-1）有 2 0f R f RgR fR 进而由式（ 2-3-2）推出 2/2nng x g R g R x （ 2-3-3） 取 nne R x 表示第 n 次迭代误差，则由式（ 2-3-3）可得 211 /2n n n ne R x g R g x g e 这就证明了牛顿法是二阶收敛的。 2、误差分析 7-10 对于误差，我们指
9、的是 量 nne x r （不考虑舍入误差 .）假定 f 连续并且 r 是 f 的单零点，因此 0f r f r 。从牛顿迭代的定义，我们有 11 nn n nnfxe x r x rfx n n n nn nnf x e f x f xe f x f x （ 2-3-4） 用泰勒定理，我们有 210 2n n n n n n nf r f x e f x e f x e f 这里 n 介于 nx 与 r 之间的一个数。重新组织此式，得 212n n n n ne f x f x f e 将其代入（ 2-3-4）式得 2 2 21 1122nn n n nnf f re e e C ef x
10、f r （ 2-3-5） 假设 1C 且 410ne 。则由（ 2-3-5）式，我们有 81 10ne 且 162 10ne 。这使我们感觉只要再额外的迭代一点就能使计算精度超过机器精度！ 这个等式告诉我们 1ne 大约为 2ne 乘以一个常数。这种令 人满意的状态称为二次收敛。它说明在许多应用中，随着牛顿法的每次迭代，精度明显倍增。 2.4 牛顿法的变形 8-10 1简化牛顿法 在牛顿迭代（ 2-24）中需要计算 fx 。如果计算 fx 存在实际困难，可以采用简化牛顿法，即 1 kkkfxxx c 这里 c 是一个常数。此时对应的 Picard 迭代中的 fxxx c fxxx c 由迭代收
11、敛条件 11fxxLc 得简化牛顿法收敛条件 0 1 1 2fxLLc 一般来说简化牛顿法的收敛阶是线性的，只有当 c f x 时收敛阶才是二阶的。当然要取 c f x 是困难的，但是当 c 是 fx 较好的近似时收敛速度还是很快的。 2牛顿下山法 定理 1：设 fx在有限区间 ,ab 上二阶导数存在且 0fx ， fx 不变号，在区间端点满足条件： 0f a f b /f a f a b a ， /f b f b b a （ 2-4-1） 则牛顿法（ 2-2-4）对任意初近似 0 ,x ab 皆收敛。 由定理 1 的证明可以导出，定理 1 中的条件（ 2-4-1）可以用条件 000f x f
12、 x （ 2-4-2） 代替。而且此时由（ 2-2-4）产生的序列 kx 是单调收敛于 0fx 的唯一解。这就是说此时只要初始近似值 0x 满足条件（ 2-4-2）则迭代（ 2-2-4）是收敛的。但是在有些问题中，条件（ 2-4-1）或（ 2-4-2）是很难保证的，尽管我们知道只要 0x 充分靠近 x 即可。 可以用所谓的牛顿下山法来扩大初始近似 0x 的选取范围，即 1 kkkkfxxx fx 0,1,k 这里 称为下山因子，此值在迭代过程中可以逐步改进。 设根的误差限为 xe ，残量误差限为 fe ， 的下界为 e ，选取初始近似 0x 和 0 1 。 为一个小的量，用于 1kx 的摄动。
13、牛顿下山法的计算过程如下： （ 1） 由 kx 计算 1 kkk kfxxx fx 。 （ 2） 比较 1kfx 和 kfx （ a） 当 1kkf x f x *若 1k k xxx ，停止计算， 1kx 作为根的近似 *若 1k k xxx ，用 1kx 代替 kx 返回（ 1）。 （ b） 当 1kkf x f x *若 e 当 1kff x e 时， nx 作为根的近似并结束迭代 当 1kff x e 时，以 1kx 作为 kx 返回（ 1） *当 e 时，用 2 代替 ， 返回（ 1）。 2.5 牛顿法与其他方法的关系 6 插值法与牛顿法有密切的关系。线性插值法的算法是 111nnn
14、nnnnfxxxf x f xxx 我们注意到分式中的分母是导数定义中的差商，而这个差商是导数的一个近似，因此线性插值法与牛顿法很相似。 牛顿法与割线法也很相似，因为割线法是不要求两点在根两侧的线性插值法。正由于这两个值比线性插值中的两点靠得更近，所以差商对导数的近似也会更好。 由此我们知道对牛顿法有可供选择的方法求导数。如果已经求得了函数 fx在 相距很近的两点的值，则可以用函数关于这两点的差商作为导数的近似值。这听起来好像是作了一次额外的函数运算，但是避免了函数的求导运算（收敛阶有所降低）。 2.6 牛顿法的现状和发展 方程求根的牛顿法因为方法简单和收敛速度快而被广泛应用于科学与工程计算中
15、 , 如非线性断裂问题、弹塑性问题及其他非线性力学问题、电路问题、电力系统计算、经济与非线性规划问题、逆变消谐问题等 9。 70年代以后，很多学者对牛顿法误差估计及收敛性进行了研究，并绘出了一些新的结果11-12，牛顿法思想直观自然，从微分的角度来说，是在局部 以直代曲。伴随着牛顿法理论的发展与实际应用，人们围绕牛顿法提出了各种改进的牛顿算法，来减少计算量以提高运算效率。其中有简化牛顿法，它以固定的 0fx 代替 kfx ；有拟牛顿法，它的基本思想是用差商代替导数，其中以 Broyden提出的算法为代表，文 13给出了 Broyden法的半局部收敛性定理，这些定理在理论上都是很有意义的；还有牛
16、顿型法，等等 4。 2.7实际应用 14 在雷达、对抗领域 , 常常利用未知位置的辐射源的 辐射信号 , 确定出该辐射源及其空间或地理位置 ; 对测向定位而言 , 则需利用已知地理位置的辐射源 , 来确定航行中物体的空间或地理位置。 中长波的无线电信号 , 可以沿地球表面传播较远的距离 , 远距离定位时 , 测向方式要考虑地球曲率的影响。为了解算出航行中物体的地理坐标 , 首先假定一个辅助的球形地球 , 将椭球地球的各种参数投影到辅助球面上 , 采用平面近似方法 , 解算出舰船概位 , 再反算到地球椭球上 , 经过概位修正 ,得到舰船位置。 对概位进行修正的算法有很多 , 主要有闭合形式解 ,
17、 选代及最小二乘解 , 最优估值解( 如卡尔曼滤波、神经网络、小波变换 ) 等。牛顿迭代法因简单有效 , 而被经常采用。 在双信号台测向定位中利用牛顿迭代法进行概位修正的方法 , 分析了牛顿迭代法对概位误差的消除过程。通过仿真表明 : 在满足舰船导航精度要求下 , 牛顿迭代法的迭代次数少 , 且误差很小 , 达到了概位修正的要求。在无线电测向定位的解算中 , 利用辅助的球形地球 , 将椭球地球的各种参数投影到辅助球面上 , 采用平面近似方法 ,解算出舰船概位 , 都可以利用牛顿迭代法进行概位修正。 三、总结部分 牛顿迭代法就是一种常用的方法 ,其收敛性好 ,具有二阶收敛速 度 ,但是 ,它每次
18、要计算导数 ,计算复杂 ,计算量较大 ,特别当 fx本身比较复杂 ,或者其导数无法计算 ,或者计算导数需要很多计算量的时候就不适合使用了 ;另外 ,牛顿迭代法对初值的选取相当敏感 ,如果初值 x 偏离较远 , 则牛顿迭代法可能发散 (导致迭代失败 ) 或者收敛很慢 (效率太低 )15。 通过对非线性方程的数值解法的分析得知 :非线性方程的数值解法是直接从方程出发 ,逐步缩小根的存在区间 ,或逐步将根的近似值精确化 ,直到满足 问题对精度的要求。具有相当强的实际意义。寻求一种快速、高效的非线性方程求根方法是一个重要课题 ,其在某些实际问题中起着关键作用 。而牛顿法就是一种很好的方法， 但是它要比
19、其他方法需要更多的求函数求值，使得计算比较麻烦，因而，很多学者在其基础上研究，有了拟牛顿法，牛顿法的变形，修正的牛顿法等。 随着计算机技术的迅速发展，牛顿法的一些限制性因素必将得到改善，基于牛顿法的更好的数值方法也会诞生。而且在 计算机蓬勃发展的时代，数值计算法日趋重要，牛顿法的运用也会更加广泛，其地位也会越来越重要。 四、参考文献 1于信 对数学软件 MATLAB 辅助教学的探索 J 山东商业职业技术学院学报 ， 2002 3， 2（ 3）： 70-73 2孙志忠 ， 袁慰平，闻震初 数值分析 M 第 2版 南京：东南出版社， 2002 1： 21-43 3美 里德 数值分析与科学计算 M
20、张威等译 北京：清华大学出版社， 2008 5： 10-43 4刘忠礼 不精确 Newton-like方法及其应用 D北京： 北方工业大学， 2007 5 5英 希思 科学计算导论 M 第 2版 张威等译 北京：清华大学出版社， 2001 10： 198-213 6美 杰拉尔德， 美 惠特莱 应用数值分析 M 第 7版 吕淑娟译 北京：机械工业出版社， 2006 8：32-46 7美 金凯德等著 数值分析 M 第 3版 王国荣等译 北京：机械工业出版社， 2005 9： 63-66 8蒋长锦 科学计算和 C程序集 M 合肥：中国科学技术大学出版社， 1998 9： 417-422 9倪健 解非
21、线性方程牛顿迭代法的一种新的加速技巧 J 广西科学院学报 ， 2010 2， 26（ 1）： 1-3 10封建湖，车刚明，聂玉峰 数值分析原理 M 北京：科学出版社， 2001 9： 198-207 11L.Rall A note 0n the convergence of Newtons methodJ SIAM J.Numer.Anal.， 1979， 16(1)：1-10 12王兴华关于牛顿法的收敛域 J科学通报数理化专 辑， 1980， 1： 40-42 13J.E.Dennis On the convergence of Broydens method for nonlinear systems of equationsJ Math.Comp.， 1971， 5(115)： 559-567 14胡国方 基于牛顿迭代法的概位修正误 差分析 J 舰船电子工程 ， 2010 8，（ 8）： 111-113 15李万斌 解非线性方程的免导数牛顿算法 J 怀化学院学报 ， 2010 5， 29（ 7）： 34-37
