求解非线性方程的迭代算法研究.doc

求解非线性方程的迭代算法研究 XX XX 学院 XX 专业 XX 班 陕西 XX 72X000 指导教师 XX 摘要 在利用数学工具研究社会现象和自然现象 或解决工程技术等问题时 很多问题都可以归结为非线性 方程 的求解问题 无论在理论研究方面还是在实际应用中 求解非线性方程都占了非常重要的地位 迭 0fx 代法是求解非线性方程 根的一种最重要的方法 而迭代法的优劣对于非线性问题求解速度的快慢和 0fx 结果的好坏都有很大的影响 所以从实际出发 进行高计算效能迭代算法的研究具有重要的科学价值和实际意 义 关键词 牛顿法 迭代法 非线性方程 收敛的阶 目录 1 引言 3 2 基础知识 4 3 NEWTON 迭代法 5 3 1NEWTON 迭代法的推导 5 3 2NEWTON 迭代法的收敛 7 4 其它迭代格式和变形的牛顿法 10 4 1 其它的迭代的格式 10 4 2 变形的牛顿法 11 结束语 错误 未定义书签 参考文献 13 ZUODIAN 14 TUTOR QUANSHUANGYAN 14 1 引言 近几十年来 数值工作者们不断在原有的迭代法基础上的提出一些新的迭代格式 事实上这些 新方法大多是根据实际情况的需要对经典的迭代格式进行修正和变形 因此Newton法等一系列经典 的迭代法就成为我们讨论新的迭代方法的起点 数学家们对这些方法都做了很深入的研究 关于这 方面的文章著作也是数不胜数 其中有非常丰富的理论结果和证明技巧是可以借鉴的 最基本的迭 代法 自然对我们的讨论也是最核心的 所以在就来重点讨论Newton迭代法 2 基础知识 非线性方程 就是因变量与自变量之间的关系不是线性的关系 这类方程很多 例如平方关系 对数关系 指数关系 三角函数关系等等 求解此类方程往往很难得到精确解 经常需要求近似解 问题 在利用数学工具研究社会现象和自然现象 解决物理 化学 生物 工程技术 甚至社会经济 等实际问题时 往往都可以归结为求解某个非线性方程 1 1 0fx 的根的问题 就方程 1 1 的形式而言 可能是 次多项式 Fn10naxax 也可能是由多种函数组成的非线性方程 譬如 在人口增长模型中假设某一地区人口的数量随时间 连续增长 即 dNtt 其中N t 表示该地区在t时刻的人口总数 为人口增长率常数 该 微分方程的解为 0 tte 其中N 0为该地区的初始人口总数 但上述模型没有考虑到外部移民 的迁入的情况 若允许移民以某常速率u进入该地区 则微分方程是 dtNtv 其解为 0 1 ttte 现假设某地区有100万人口 第一年内有43 5万移民迁入 第一年末总计人口156 4万 根据 上述数据可以推算出该地区的增长率常数 满足方程 43 5156 tte 上面这个微分方程的解析解比较容易求出 所以求解这类问题就可转化为求解非线性方程的问 题 谈到解非线性方程 就不得不提迭代法 它是最有效最便利的求解方法 迭代法就是从预知的 解的初始近似值 简称初值 开始 采用某种迭代格式构造一近似值序列 0121 kxx 逐步逼近于所求方程的真解 对方程 1 1 求近似根 先将其改写成等价的方程 xf 1 2 所谓等价就是 如果 是方程 1 1 的根 那么 fx 反之如果 满足方程 1 2 x x 那么 最简单的等价变换是令 当然还可以根据 的特点来变换 0fx fxF Fx 称为迭代函数 为函数 的一个不动点 求 的零点就等价于求 的不动点 选 xxf 择一个初始近似值 将它代入 1 2 式右端 即可求得0 0 xf 可以如此反复迭代计算 1 3 1 1 23kkf 如果得到的序列 有极限 kx limkx 则迭代方程 1 3 收敛 我们称 1 3 为不动点迭代法 不动点迭代法是最简单的迭代法 它是一 种逐次逼近的方法 其基本思想是将隐式方程 1 2 归结为一组显示的计算公式 1 3 就是说迭 代过程实质上是一个逐步显示化的过程 但是迭代序列 能否作为方程的根 的好的近似 或者能否收敛于 以及能否快速的收敛kx x x 到 呢 这些都是我们后面所要探讨的问题 对于一种解法 为了考察它的有效性 一般都要讨论 x 它的收敛性和收敛速度 即考虑在什么样的条件下构造的序列是收敛的 以及序列中的近似值是按 什么样的误差下降速度来逼近真解的 迭代过程的收敛条件 一般与方程的性态 函数 在解附 Fx 近的性质 零点的分布状态等 以及初值的近似度有关 而某些方法仅与初值的近似度有关 故有 时也称收敛条件为收敛范围 迭代过程的收敛速度 是指在接近收敛过程中近似值误差的下降速度 一般来说 它主要由方法所决定 方程的性态也会有一些影响 如果由一种迭代解法构造出来的近 似值序列 与解 的误差为123 kxx 1limkrkxK 或者 当 充分接近于解 时有关系式kx x 1 rkkxx 当r 1时 称该迭代法具有 阶的收敛速度 通常具有 阶收敛速度的算法 当接近收敛时其近似值 的误差将按幂次为r的速度下降 因此 越大 误差就下降的越多 收敛速度就越高 越小 误差 就下降的越少 收敛速度就越低 3 Newton 迭代法 3 1Newton 迭代法的推导 对于求解非线性方程 2 1 0fx 的零点问题 有很多种迭代方法 其中最为著名的就是Newton迭代法 2 2 1 nnfxx 这些迭代法是如何被取得的呢 事实上迭代法的推导方法也是多种多样的 下面我们就以Newton迭代 法为例 介绍公式 2 2 的几个导出途径 方法一 作泰勒级数展开并取线性部分 记 x是方程 2 1 的根 于是 2 0 kkkkkkxffxfxfx 将右边的二次项去掉 即得 0kkkff 令 满足1kx 1 kkkfxfx 即得公式 2 2 方法二 重节点反插值 可以把方程 2 1 的根看做函数 yfx 所表示的曲线与x轴的交点 函数 yfx 有反函数 xy 求根 x即为求 在 处有函数值 即 kkx 将 在 作重 0 k kkyf 0ky 节点插值 即得 2 0 kkkky 由数学分析可知 则得 1 kkyfx 21 0 kkkkkfxyfxf 令 1 kkfxx 此即为公式 2 2 方法三 为了求曲线 与 轴的交点 用过 处的切线与 轴的交点来近似 yf kxfx 因为过 的切线方程为 kxf kkkyfxfx 它与 轴的交点的横坐标即为 1 kkfx 不同于以上三种传统的推导方法 Weerakoon 1 和Fernando运用Newton Leibniz公式和Newton Cots求积公式又提出了一种新的导出Newton法的方法 对于Newton Leibniz公式 2 3 nxfxftd 可用零阶Newton Cots求积公式 2 矩形公式 nxnftf 来代替 2 3 式中的定积分 并且令 就可得到Newton公式 类似0 的 将定积分替换为一阶Newton Cots公式 梯形公式 2nxnxftdffx 可得到一个隐格式的迭代法 11 nnfxx 为了把隐式变为显式 这里 1 nnfxx 由此可以得到一个三阶方法 12 nnnfxxfx 显然这两种方法的不同之处就在于选择的求积公式不同 所以得到了不同的收敛阶 后来 Frontini和Sormani 又丰富了Weerakoon和Fernando的结果 通常的插值型求积公式 高于零阶 可以统一记为 2 4 1 0 n mxniinftdxAf 其中 ininx i 0 1 2 m 1 是区间 0 1 上的求积节点 是相应的求积系im iA 数且满足条件 把 2 4 式中的 换为 代入 2 3 中 假设miA f 是 的一个根 令 可得到 fx x 2 5 1 0 nnmiiifxA 其中 2 6 ininx 显然这是一个隐格式 那么用Newton迭代 来代替上式中的 就可 nfx 得到一个显式方法 2 7 11 0 nnmiiifxxA 这里 2 8 ninifxx 只要在 2 5 式中代入不同的求积公式 就可以得到不同格式的迭代法 显然这族迭代法的形 式会随着求积公式的变化而变化 计算代价也会随之增加 但是已经证明了由以上推导方法得出的 迭代法 除Newton法以外 的收敛阶是独立于求积公式的选择的 换句话说 就是虽然选择不同的求 积公式可以得到不同的迭代格式 但是这些迭代法的收敛阶最高只能达到三阶收敛 之所以收敛阶 无法提高 我们发现是因为上面的方法在将隐格式转化为显式时 是用Newton迭代来代替 于是 我们尝试使用敛阶高于二阶的迭代法代替 同时提高求积公式的代数精度 如此得到的迭代法的 收敛阶就会随之提高 3 2Newton 迭代法的收敛 到目前为止 已经有很多不同的迭代方法被数值工作者们提出了 在Ortega和Rheinboldt 中已 经有了比较详细的介绍 其中最经典的就是二阶收敛的Newton迭代法 1 nnFxx 2 9 众所周知 Newton迭代法形式简单 收敛速度也比较快 在具体计算中一直都是求解非线性方 程 2 9 最重要的迭代方法 数百年来 虽然新的迭代格式层出不穷 然而几乎所有的迭代法的研究 都是以Newton迭代法的证明技巧和分析方法为基础的 有关Newton迭代法的收敛性方面的研究是数 不胜数 其中有很多理论结果都被借鉴 无论是理论研究还是实际应用 Newton迭代在迭代法的历 史上所起的作用是其它任何迭代法所无法替代的 关于Newton迭代法的研究情况已有很长的历史 十九世纪初 Cauchy就在实数空间冗中对 Newton法的收敛性进行了初步的研究 但所给的条件涉及求解一阶导数极小值之类的整体条件 1937 年 Ostrowski 10 在复数空间C中对Newton法的收敛性进行了深刻的研究 后来Kantorovich 5 成功 的给出了Banach空间内Newton法的著名的Newton Kantorovich收敛性定理 关于这方面的文献 4 和 7 他给出的收敛条件为 1 设F是由Banach空间X的一个非空凸集 到同型空间y的Frechet可微算子 2 存在点 0 x 假设 存在 且 10 Fx 100 Fxa 3 1 yb 4 2 ab 5 0 Bxt 其中 12abt Kantorovich关于Newton法收敛性的著名工作可以说是解方程算法现代研究的起点 后来有很多 数学家都对此定理进行了改进 他们主要是针对上述条件 给出了一些修正条件 来减弱 Kantorvich 9 条件 后来 Wang和Guo将这些收敛性和唯一性定理的条件加以了统一 该条件包括了 著名的经典Kantorovich条件 给出了方程 1 1 解的唯一性及Newton法的收敛性定理 前面列举 的这些收敛性条件都是仅考虑了P7的Lipschitz条件 Huang指出F的二阶的导数在收敛性条件中也是 有用的 同时弥补了Kantorvoich条件不能判断从某个指定点出发的Newton迭代序列是否收敛 后来 Gutierrez zhang分别又将此条件改进 此外 Argyros在文献中利用了F的高阶导数信息 提出了 两个收敛条件 Kantorovich关于Newton法的收敛性定理一直被视为收敛性分析思想的典范 它的特点是对F可 微性要求较弱 但需要F的某阶导数的整体性态 为此在1986年国际数学家大会的大报告上 Smale 2 用 尸的解析性条件取代了Kantorovich的整体性假设 即F的某些阶导数在某个足够大的区域中具有 Lipschitz连续的假定 完全只用F在初始点的信息来判断Newton迭代方法的收敛性 这对连续复杂 性的研究是极为重要的 为了解脱对F的区域信息的依赖 Smale假设F在x解析 并且F在x的Taylor级 数收敛球内这种解析性不被人为破坏 并且令 aFx 其中 1 Fxx 1 12 sup kkF Smale证明存在一个绝对常数 当 0 x 时 从 出发的Newton迭代 1 4 都有0 0 x 意义并且收敛 后来王兴华 3 和韩丹夫 4 求得了 的最好结果 即 不仅如此 王兴华等032 人还证明了 是半局部行为下的普适常数 这一结果揭示了关于零点数值过程在半局部行为32 上的统一性 有关Newton法的研究 除了上面所列 还有很多的学者作了大量的研究工作 并且积 累了很多的文献 证明迭代法的收敛性的一个很不错的技巧是优函数技术 这是Kantorovich为了证明Banach空 间内的Newton迭代法的收敛性而提出来的 Kantorvich在中提出利用优界函数原理的新证法 其思 想就是将一个高维迭代过程和另一个一维迭代过程进行比较 由一维过程的收敛性导出原过程的收 敛性 即立足于以下事实 11 nnxt 010 njjnjxt ntN 收敛 nx是个Cauchy序列 在证明的过程中 使用的优函数主要有两种 一种是代数多项式 Kantor vich就是把二次多项 式 21 htbt 作为优函数来证明Newton迭代法的收敛性的 当然还可以根据不同情况使用更高次的代数多项 式 用代数多项式作优函数的最大好处是可以得到精确的显式误差估计 另一种是有理多项式 最先 被Smale提出 其形式为 2 1tt 此优函数不仅可被用来证明各种迭代法在点估计判据下的收敛性 更重要的是 能够在同等条件下 比较不同算法的效率 除了优函数方法 还有一种证明迭代序列收敛的技巧是递归法 对此Gutierrez 6 和Hernandez 7 等 人对Halley迭代 Chebyshev迭代 Super Halley迭代 Jarratt型迭代的收敛性进行了一系列工作 在 早期的文章中 用到的是四个实序列 现在减少到两个实序列 递归关系在不断的简化 不过无论 是优函数方法还是递归法 它们实际上都是逐步归纳的方法 逐步归纳法的实质就是使后面一步迭 代的逼近误差小于前一步迭代的逼近误差 在证明迭代过程的收敛性时 运用了每前进一步迭代都 不会破坏定理假设条件的技巧 前面叙述了这么多 都只是理论方面的分析 那么如何具体使用迭代法来求解非线性方程呢 下面我 们就给出Newton迭代法求解方程的具体迭代步骤 以本苹开头列举的非线性方程为例 求解方程 43 5156 0 1 tte 首先确定迭代初值 利用迭代格式 0 x 143 5 6 43501xxnnn ne 经过几步迭代以后 直到 6 fx 我们可得方程的解为0 1009979 其具体过程见下表 迭代次数 n nfx 1 1 5 392 738 2 0 7311697 115 456 3 0 257358 22 5612 4 0 1120077 1 48188 5 0 1010548 7 62834E 03 6 0 1009979 2 04904E 07 4 其它迭代格式和变形的牛顿法 4 1 其它的迭代的格式 自Newton迭代法产生以来 又有很多种迭代方法被构造 其中有代表性的迭代法有 三阶收敛 的Chebyshev迭代 Halley迭代 Super Halley迭代 Newton凸加速 迭代及其变形 四阶收敛的 Jarratt迭代法及其变形 另外还有实用的导数超前计值的 导数滞后计值的 避免导映照求逆等 变形的Newton迭代法 以及 阶收敛的King Wemer等两点迭代格式 12 三阶迭代法 Chebyshev迭代 Halley迭代 Super Haley迭代和四阶Jarratt型迭代可以概况为以 下形式此式 1 nnyxFx 2 10 1 ns 1 10 nnnnnnsFxyxtyxdtx 0 1 1 当 时 1 5 式即为Newton迭代法 2 当 1 1 2nnsas 时 0 a 11 nnnnFxxF 2 10 式变为一族具有三阶收敛的迭代 其中包括Cheby shev a 0 迭代法 Halley a 1 2 迭代法 Super Haley a 1 迭代法等 b 1 10 22 33nnnnnsxtyxdtFxFF 将其代入 2 10 式 迭代法中避免了求二阶Frechet导数 但同时又能保持三阶收敛的速 度 所以 b 中方法更有实际意义 3 当 1 1 2nnss 时 a 101 2 33nnnFxtyxdtFx 是具有四阶收敛的迭代方法 可将其写成 2 11 1 22 3nnn nnfxfxx ff 显然这个方法在每步迭代时 只要计算一个函数值和两个导数值 它最大的优势就在于用较小的计 算代价取得很快的收敛速度 并且 2 11 式可用于求解非线性方程组 我们认为迭代法 2 11 是很 有价值的方法 b 1 1 3nnnnnsFxyxFx 这也是一个四阶收敛的迭代方法 另外四阶收敛的迭代法还有 nnxy 1 2 nn nxFx Ostrowski 10 和Traub提出的 后来韩给出了其在Smale点估计下的收敛性分析 此迭代法在一 次迭代过程中只需要计算两个函数值和一个导数值 对于求解那些函数的导数值比较难计算的方程 这是个不错的选择 从表面看来 这一迭代法似乎比迭代法 2 11 更有优势 但是它仅适用于一维 情形 这就使得此迭代法的实用性大大降低了 除了以上提到的这些三 四阶收敛的迭代法 还有很多变形的Newton迭代法 尽管Newton迭代 是一个很强有力的方法并且收敛很快 但数值工作者还是从应用需要出发对它做了种种改进 这主 要是因为在各种问题中映照的计值及其求逆的计算代价可能是很大的 所以希望变形的迭代法能够 尽量少的涉及这种计算而不影响收敛速度 或者虽然做了同样的计算却能获得更快的收敛速度 关 于这方面的改进最为典型的要数三个变形的Newton迭代法了 王兴华 韩丹夫和孙方裕给出了其详 细的收敛性分析 4 2 变形的牛顿法 一大类在计算实践中行之有效的变形都可以写成 1 0 nnxAFxN 的形式 这里用以代替 的映照 有如下一些取法 F E 1 即1 nmnAx 11 1 mknxkmkN 这里是m一个取定的自然数 而方括号表示取整数的部分 就是说 我们并不在每步迭代都计算 导映照并求逆 而是每隔m步计算一次 并将其逆保持使用m步 这种方法可以叫做减少导映照计值 次数的Newton迭代 当m 1时 这就是平常的Newton迭代 设 是减少导映照计算次数的Newton迭代nx 产生的收敛于方程 1 1 的迭代序列 则其子序列 的渐近收敛阶是m l 如果用这种方法来求解m 多元非线性方程组 与Newton迭代相比无疑能提高渐近效率 2 即11 nnnAFxA 1 nnxAFx 1 1 1 nmkxkmkN 其中 任意指定 使之接近于 这是避免导映照求逆的Newton迭代 其原理是借鉴当年没0A10Fx 有除法硬件的计算机中求倒数的迭代法以求 的逆 不过只迭代一次 这已足以达到Newton1 nx 迭代的组合算式中对导映照之逆的精度要求 所以这种避免导映照求逆的Newton迭代仍保持平常的 Newton迭代的渐近收敛阶 这一思想后来也被应用于变形其它的迭代法 来避免计算导数的逆 3 有一个适当的超前量 1 nnnAFx 比 11 x 2f 即 11 nnxFx 1 2n 我们称这种迭代法为导映照超前计值的Newton迭代 它并没有增加计值代价 但其渐近收敛阶 却提高到了 12 若令 则上式变为 nxy 2 12 11 1 2 nn nxyxFxy 这一两点迭代格式是W Werner 9 提出的 事实上 早在发表的六年之前R F King 8 就已经在 同一家杂志上提出了一个与 2 12 等价的迭代格式了 11 2 nnyxyx 所以迭代法 2 12 被称为King Werner迭代法 对于这三种变形迭代法 已经证明它们的收敛条件与Newton迭代是完全相同的 这个结论排除 了对变形可能影响收敛性的担心 从而可以只从计算方便的考虑出发来选择变形 更重要的是 它们 都可以直接应用于解方程组 所以这三种变形的迭代法是非常具有实用价值的 前面讨论的这些迭代方法都是建立在非线性算子F是可导算子的前提之上的 若F是不可导算子 以上迭代方法便不能使用 一种解决方案便是把F分成两个算子之和 可导部分记为日 不可导但 Lipschitz连续部分记为G 由此求解非线性方程 1 1 就变为求解方程 0 HxG 于是Newton迭代法变为 11 nnnnxx 小结 以最经典的Newton迭代为例 详细的给出了它的几个收敛性条件 以及常用的证明技巧 同时 还介绍了其它一些有代表性的迭代方法 简略的分析了它们各自的特点 从这些内容可以发现 关 于迭代法的研究主要是从以下几个方面进行的 迭代法的提出和推导 即如何构造迭代格式 由迭 代格式所产生的序列需要具备什么条件才能收敛到方程的根 迭代法的收敛速度和计算效能等 高阶 迭代算法的导出 参考文献 1 S Weerakoom T G I Fernando A variant of Newton S method with accelerated third order convergence Appl Math Lett 13 2000 87 93 2 S Smaie On the Efficiency of Algorithms of Analysis Bull Mew Ser 3 王兴华 韩丹夫 Newton迭代的区域估计与点估计 计算数 学 12 1990 47 53 4 王兴华 韩丹夫 孙方裕 若干变形Newton迭代的点估计 计算数 学 2 1990 145 156 Amer Math Soc 13 1985 87 121 5 L V Kantorovich On the Newton method for Functional equations Docklady Akademii Nauk SSSR 59 1948 1237 1240 6 J M Gutierrez A New Semilocal Convergence Theorem for Newton Method J Comp and Appl Math 79 1997 131 145 7 M A Hernandez and M A Salanova A family of Newton type iterative proceases lnern J Comput Math 51 1994 205 214 8 R F King Tangent method for nonlinear equations Numer Math 18 1972 298 304 9 W Werner Uber ein Verfahem der ordnung 1 以 zur Nullstellenbestim mung Numer Math 32 1979 333 342 10 A Ostrowski Solution of Equations and Systems of Equations Academic Press New York 1960 2nd ed 1966 3rd ed 1973 ZuoDiAn Gread08 Class1 Major Of Information and Computing Science Mathematics and Computer Science Dept Shaanxi University of Technology Hanzhong 723000 Shaanxi Tutor QuanShuangYan Abstract When we make use of mathematical tools to research social phenomena and natural phenomena or to resolve the engineering and other problems a lot of problems can be ended up with solving the equationf x 0 the nonlinear equations have a very important role in research of both theory and practical application The iterative method is an important method to slove the equationf x 0 whether the nonlinear equations will be solved well or not is directly affected by the choice of iterative method Therefore the research on iterative method with high efficiency means a lot in terms of both scientific research and practical application Keywords newton s method iterative methods nonlinear equations simple root