ch7非线性方程求根.ppt

河海大学理学院数值分析 数数 值值 分分 析析 Computational MethodComputational Method 河海大学理学院数值分析 Chapter Chapter 7 7 非线性方程求根非线性方程求根 河海大学理学院数值分析 第7章 非线性方程求根 71 方程求根与二分法 1.引言 设 若有 使 则称 是方程 的根或 的零点。 若 ， 当 时,称 为方程 的单根， 当 时,称 为方程 的m重根或 的m重零点。 河海大学理学院数值分析 定理 若 有m阶导数，则 是 的 m重根的充分必要条件是 ， 。 证明: 依据泰勒中值定理知. 泰勒公式： 河海大学理学院数值分析 2.二分法 零点定理 若 又 则 。 依据零点定理对区间 逐次分半进行根 的搜索，这就是二分法。 ， ； 河海大学理学院数值分析 具体作法如下： 设， 令 ， （1）若，则 是根； （2）若，令 ； （3）若 ，令 。 对再二分且同样的讨论，得和一半的区间 将此过程继续下去，得 则 。 河海大学理学院数值分析 定理 设 又 则由 二分法得到的 收敛于根 ，且有根 的 近似值 误差估计式： 。 河海大学理学院数值分析 72 迭代法及收敛性 1.不动点迭代法的概念 将 改写成等价形式 。若有 使 ,则将 称为 的不动点。 求 的根 ,也就是找 的不动点 。 设选择 （初始近似值）并构造 （2. 2） 计算公式（2. 2）称为迭代格式, 称为迭 代函数,得到的 称为迭代序列,用公式 （2. 2）逐步代入求近似解的方法称为迭代法( 或 不动点迭代法)。 河海大学理学院数值分析 若 ,则称迭代收敛,否则,就称迭 代 发散。若 , 迭代都收敛，则称 迭 代全局收敛。 河海大学理学院数值分析 压缩映象原理 设 若 (1)当 时，有 ， (2) 使 有 则 使 。 证明 河海大学理学院数值分析 压缩映象原理证明 证存在性。令 （1） ，则 （2），则 （3） ，据零点定理， ，使。 ； ； 证唯一性。若另有是不动点， 这与矛盾。 证毕 河海大学理学院数值分析 2.全局收敛 全局收敛性定理 设 若 时，有 ; ，使 有 迭代公式 则 , 迭代法收敛，且有以下估计式 （1） （2） （3） 河海大学理学院数值分析 证明 ， 证（1） 又由于 是固定数，而，所以， ，迭代收敛。 证（2） 所以， 河海大学理学院数值分析 注：全局收敛性定理中条件(2)换成 , ，定理结论仍成立。 证（3）因而 证毕 据拉格朗日定理， 河海大学理学院数值分析 3局部收敛和p阶收敛 定义 若 是 的不动点， ,使 , 由迭代公式 产生的序列 ，有 ， 则称迭代局部收敛。 定义 若 局部收敛性定理 是 的不动点， 在 连续，迭代公式 ，则 (1)当 时，迭代局部收敛； (2)当 时，迭代发散。 河海大学理学院数值分析 证明 由于 存在，故,当 时，存在，连续。且由 极限的保号性，当 时 ， 使 ；当 时，有 。 满足(2);当 时， 满足（1）；据全局收敛定理,在 上收敛。 当 时， 所以， ， ，迭代不收敛。 证毕 河海大学理学院数值分析 定义 设 ， 若 ， 则称迭代过程是p阶收敛。 特别地，p=1称为线性收敛，p1称为超线性收 敛，p=2称为平方收敛。 定理 若 , , 则迭代过程是p阶收敛。 河海大学理学院数值分析 证明 证毕 河海大学理学院数值分析 例 设方程 ，根 , 将 方程改写成下列等价形式：（1） ； （2） ；（3） 。 试建立相应的迭代格式，并分析它们的收敛性 ， 然后选取一个格式作为计算公式。 解 （1）， ； ， ；， 。 （2） （3） 河海大学理学院数值分析 ， ， 收敛； ， ，不收敛； ， ，收敛。 因为， ，取 作为计算公式。 解毕 河海大学理学院数值分析 74 牛顿法（切线法） 其牛顿迭代函数 由 解出 得。 河海大学理学院数值分析 例 设用牛顿迭代法求方程 内的根， 在 取 ，要求 。 解 ， ， 因为, 所以, 解毕 河海大学理学院数值分析 1牛顿迭代法及其收敛性 例 设 ,写出用牛顿法求 的迭代计 算公式，并分析收敛性。 解 令 ， 取 所以， 河海大学理学院数值分析 单减有下界， 存在，于是，对本题计算公 式取极限， 有 ，说明，本题计算公式在 上全局收敛。 解毕 河海大学理学院数值分析 牛顿迭代函数 设 是 的单根，即 , 。 , 故，牛顿法在 邻近至少是2阶收敛的。 。 河海大学理学院数值分析 2简化牛顿法 特别 即牛顿法。 河海大学理学院数值分析 75 弦截法与抛物线法 3弦截法 取 是1步迭代法，1阶收敛 河海大学理学院数值分析 4快速弦截法 取 是2步迭代法，1618阶收敛 河海大学理学院数值分析 5抛物线法（密勒法） 若用三点 , , 连接成抛物线取与 轴上靠近 的交点当 作 的近似值 。该法称作抛物线法或密 勒法.计算公式为 是3步迭代法，1840阶收敛. 河海大学理学院数值分析 证明 二次牛顿插值 其中 令 解出 号取与符号相同，即 河海大学理学院数值分析 6牛顿下山法（全局收敛） 的解 ，则 若视 为 在 处的高度，则 是山谷的最低点， 若 有 ， 则 是一个下山序列,若 ，且 ， ， 取 ， ，例取 河海大学理学院数值分析 7重根情形 复习定理 若 有k阶导数，则 是 的k重根的充分必要条件是 ， 。 河海大学理学院数值分析 牛顿迭代函数 ， ， 收敛。 ， 所以，收敛是1阶收敛。 河海大学理学院数值分析 (1)已知重数k 修改牛顿迭代函数 ，收敛是2阶收敛。 河海大学理学院数值分析 2.重数k未知 设 迭代函数 ，则 是 的单零点. 收敛是2阶收敛。 河海大学理学院数值分析 73 迭代收敛的加速方法 1.埃特金加速法 设 , , 是1阶收敛 ，且有 , , , , 相除得： 即： 解出： 河海大学理学院数值分析 埃特金加速法 河海大学理学院数值分析 2.斯蒂芬森迭代法 斯蒂芬森迭代 由于 ， 新迭代函数 河海大学理学院数值分析 76 非线性方程组的解法 非线性方程组 两种解法: 不动点迭代法(简单迭代法) 牛顿迭代法 河海大学理学院数值分析 1不动点迭代法（简单迭代法） 改写成等价形式 简单迭代法： 压缩映象原理和收敛性定理也成立。 河海大学理学院数值分析 2.牛顿迭代法 雅可比矩阵 牛顿迭代法 河海大学理学院数值分析 例 写出解以下非线性方程组的迭代格式 解 简单迭代法： 取 迭代至28步后