数值分析非线性方程的数值解法.ppt

第二章非线性方程的数值解法 简介 Introduction 我们知道在实际应用中有许多非线性方程的例子 例如 1 在光的衍射理论 thetheoryofdiffractionoflight 中 我们需要求x tanx 0的根 2 在行星轨道 planetaryorbits 的计算中 对任意的a和b 我们需要求x asinx b的根 3 在数学中 需要求n次多项式xn a1xn 1 an 1x an 0的根 求f x 0的根 2 1对分区间法 BisectionMethod 原理 若f x C a b 且f a f b 0 则f x 在 a b 上必有一根 x1 x2 a1 b2 x b1 a2 误差分析 第k步产生的xk有误差 对于给定的精度 可估计二分法所需的步数k 例1用二分法求在 1 2 内的根 要求绝对误差不超过解 f 1 50 1 2 f 1 25 0 1 25 1 375 f 1 313 0 1 360 1 368 f 1 5 0 1 1 5 12 例2 求方程f x x3 e x 0的一个实根 因为f 0 0 故f x 在 0 1 内有根用二分法解之 a b 0 1 计算结果如表 kabkxkf xk 符号0010 5000 10 5000 0 7500 20 7500 0 8750 3 0 87500 8125 4 0 81250 7812 5 0 78120 7656 60 7656 0 7734 7 0 77340 7695 80 7695 0 7714 90 7714 0 7724 100 7724 0 7729 取x10 0 7729 误差为 x x10 1 211 Remark1 求奇数个根 Findsolutionstotheequation ontheintervals 0 4 Usethebisectionmethodtocomputeasolutionwithanaccuracyof10 7 Determinethenumberofiterationstouse 0 1 1 5 2 5 and 3 4 利用前面的公式可计算迭代次数为k 23 Remark2 要区别根与奇异点 Considerf x tan x ontheinterval 0 3 Usethe20iterationsofthebisectionmethodandseewhathappens Explaintheresultsthatyouobtained 如下图 Remark3 二分发不能用来求重根 f x 0 x g x f x 的根 g x 的不动点 2 2单个方程的迭代法 f x 0化为等价方程x g x 的方式是不唯一的 有的收敛 有的发散Forexample 2x3 x 1 0 1 如果将原方程化为等价方程 由此可见 这种迭代格式是发散的 取初值 2 如果将原方程化为等价方程 仍取初值 依此类推 得x3 0 9940 x4 0 9990 x5 0 9998x6 1 0000 x7 1 0000 已经收敛 故原方程的解为x 1 0000 同样的方程 不同的迭代格式有不同的结果 什么形式的迭代法能够收敛呢 收敛性分析 定义2若存在常数 0 1 使得对一切x1 x2 a b 成立不等式 g x1 g x2 x1 x2 1 则称g x 是 a b 上的一个压缩映射 称为压缩系数 考虑方程x g x g x C a b 若 I 当x a b 时 g x a b II 在 a b 上成立不等式 g x1 g x2 x1 x2 1 则 1 g在 a b 上存在惟一不动点x 2 任取x0 a b 由xk 1 g xk 得到的序列 xk a b 收敛于x 3 k次迭代所得到的近似不动点xk与精确不动点x 有有误差估计式 2 3 定理2 2 1 3Fixed PointIteration 证明 g x 在 a b 上存在不动点 不动点唯一 当k 时 xk收敛到x x x g x g x x x 因0 1 故必有x x 若有x a b 满足g x x 则 xk x g xk 1 g x xk 1 x 2 xk 2 x k x0 x 0 令G x g x x x a b 由条件 知G a g a a 0 G b g b b 0 由条件 知G x 在 a b 上连续 又由介值定理知存在x a b 使G x 0 即x g x 3Fixed PointIteration 可用来控制收敛精度 越小 收敛越快 4 xk x g xk 1 g x xk 1 x xk xk 1 xk x 故有 xk x 1 xk xk 1 这就证明了估计式 2 5 xk xk 1 g xk 1 g xk 2 xk 1 xk 2 k 1 x1 x0 联系估计式 6 可得 xk x k 1 1 x1 x0 即估计式 3 成立 Remark 定理条件非必要条件 而且定理2 2 1中的压缩条件不好验证 一般来讲 若知道迭代函数g x C1 a b 并且满足 g x 1 对任意的x a b 则g x 是 a b 上的压缩映射 例题 已知方程2x 7 lgx 0 求方程的含根区间 考查用迭代法解此方程的收敛性 在这里我们考查在区间 3 5 4 的迭代法的收敛性 很容易验证 f 3 5 0将方程变形成等价形式 x lgx 7 2 由定理2 2 1知 迭代格式xk 1 lgxk 7 2在 3 5 4 内收敛 局部收敛性定理 定理2 2 2 设x 为g的不动点 g x 与g x 在包含x 的某邻域U x 即开区间 内连续 且 g x 0 当x0 x x 时 迭代法 3 产生的序列 xk x x 且收敛于x 证明略 作为练习 Wedon tknowx howdoweestimatetheinequality 举例 用一般迭代法求x3 x 1 0的正实根x 容易得到 g x 在包含x 的某邻域U x 内连续 且 g x 1 例题 用一般迭代法求方程x lnx 2在区间 2 内的根 要求 xk xk 1 xk 10 8 解 令f x x lnx 2 f 2 0 故方程在 2 4 内至少有一个根 将方程化为等价方程 x 2 lnx 因此 x0 2 xk 1 2 lnxk产生的序列 xk 收敛于X 取初值x0 3 0 计算结果如下 7314617745293 146188209103 146191628113 146192714123 146193060133 146193169143 146193204 kxi03 00000000013 098612289231413378664314570220963 146037143 另一种迭代格式 03 0000000001314619344133 146193221 程序演示 由此可见 对同一个非线性方程的迭代格式 在收敛的情形下 有的收敛快 有的收敛慢 定义1 设序列 xk 收敛于x 若存在p 1和正数c 使得成立 则称 xk 为p阶收敛的 特别 p 1 要求c 1 称线性收敛 1 p 2 称超线性收敛p 2 称平方收敛 迭代法的收敛阶 收敛速度 定理2 2 3 设x 为g的不动点 p 2为正整数 g在x 的某邻域 x 内p阶连续可微 且g x g x g p 1 x 0 而g p x 0 则存在 0 当x0 x x x0 x 时 由迭代法 3 产生的序列 xk 以p阶收敛速度收敛于x Prove 1 由g x 0 必存在 0 当x0 x x U x 时 由迭代格式 3 产生的序列 xk 收敛于x 并有xk x x 2 由泰勒公式有xk 1 g xk g x g x xk x g p 1 x xk x p 1 p 1 g p x xk x xk x p p 0 1 利用g在x 的各阶导数条件及g x x 上式可改写成 11 3 由于g在x 处p阶连续可微且g p x 0 知必存在x 的某邻域 x 当x U x 时 有g p x 0 由于x xk x x x U x 故g p x xk x 0 k 0 1 2 可见 当初值x0 x 时 由 11 式可推出诸xk x 于是由 11 式有 上式令k 取极限 即 xk 有p阶收敛速度 NewtonIterativeMethod 牛顿法及其几何意义收敛性及其收敛速度计算实例及其程序演示 取x0作为初始近似值 将f x 在x0做Taylor展开 重复上述过程 作为第一次近似值 一 牛顿法及其几何意义 Newton迭代公式 基本思路 将非线性方程f x 0线性化 牛顿法的几何意义 x1 x2 牛顿法也称为切线法 局部收敛性定理 设f x C2 a b 若x 为f x 在 a b 上的根 且f x 0 则存在x 的邻域使得任取初始值 Newton法产生的序列 xk 收敛到x 且满足 至少平方收敛 二 牛顿法的收敛性与收敛速度 在x 的附近收敛 由Taylor展开 令k 由f x 0 即可得结论 证明 Newton法实际上是一种特殊的迭代法 设x 是f的m重根 则令 且 Answer1 有局部收敛性 Answer2 线性收敛 结论 Newton法的收敛性依赖于x0的选取 x 有根 根唯一 全局收敛性定理 定理2 3 1 设f x C2 a b 若f a f b 0 则由Newton法产生的序列 xk 单调地收敛到f x 0在 a b 的唯一根x 且收敛速度至少是二阶的 保证Newton迭代函数将 a b 映射于自身 将f x 在xk处作Taylor展开 对迭代公式两边取极限 得 说明数列 xk 有下界 故 xk 单调递减 从而 xk 收敛 令 三 计算实例及其程序演示 辅助工具 VC程序设计语言Matlab数学软件 1 选定初值x0 计算f x0 f x0 计算步骤 2 按公式迭代得新的近似值xk 1 3 对于给定的允许精度 如果则终止迭代 取 否则k k 1 再转步骤 2 计算 允许精度 最大迭代次数 迭代信息 例题1 用Newton法求方程的根 要求 取初值x0 0 0 计算如下 对迭代格式一 theiterativenumberis27 thenumericalsolutionis0 442852706对迭代格式二 theiterativenumberis3 thenumericalsolutionis0 442854401 例题2 求函数的正实根精度要求 从图形中我们可以看出 在x 7和x 8之间有一单根 在x 1和x 2之间有一重根 用Matlab画图 查看根的分布情形 初值x0 8 0时 计算的是单根 Theiterativenumberis28 Thenumericalsolutionis7 600001481初值x0 1 0 计算的是重根 Theiterativenumberis1356 Thenumericalsolutionis1 198631981 迭代过程的收敛速度 一种迭代法要具有实用价值 不但要肯定它是收敛的 还要求它收敛的比较快 所谓迭代过程的收敛速度 是指在接近收敛时迭代误差的下降速度 具体地说 如果迭代误差当时成立 常数 则称迭代过程是阶收敛的 特别地 时称线性收敛 时称平方收敛 迭代过程的收敛速度 迭代过程的加速 设是根的某个近似值 用迭代公式校正一次得假设在所考察的范围内改变不大 其估计值为 则有据此可导出如下加速公式 其一步分为两个环节 迭代 改进 埃特金算法 前面加速方案有个缺点是其中含有导数的有关信息而不便于实际应用 设将迭代值再迭代一次 可得据此构造出不含导数信息的加速公式 迭代 迭代 改进 这一加速方法称为埃特金算法 埃特金算法 开方公式 对于给定正数应用牛顿迭代法解二次方程可导出求开方值的计算公式设是的某个近似值 则自然也是一个近似值 上式表明 它们两者的算术平均值将是更好的近似值 定理开方公式对于任意给定的初值均为平方收敛 开方公式 牛顿下山法 一般地说 牛顿法的收敛性依赖于初值的选取 如果偏离较远 则牛顿法可能发散 为了防止发散 通常对迭代过程再附加一项要求 即保证函数值单调下降 满足这项要求的算法称为下山法 牛顿下山法采用以下迭代公式 其中称为下山因子 弦截法 用差商替代牛顿公式中的导数可得到以下离散化形式 从几何图形上看 上面的公式求得的实际上是弦线与轴的交点 因此称这种方法为弦截法 改用差商代替牛顿法中的导数有以下快速弦截法迭代公式 弦截法 弦截法 小结 1 当f x 充分光滑且x 是f x 0的单根时 牛顿法在x 的附近至少是平方收敛的 2 当f x 充分光滑且x 是f x 0的重根时 牛顿法在x 的附近是线性收敛的 3 Newton法在区间 a b 上的收敛性依赖于初值x0的选取 解非线性方程组的牛顿法 将非线性方程组线性化 得到 其中F xk 为F x 在xk处的Jacobi矩阵 例 用牛顿法解方程组 取初始值 1 1 1 计算如下 Nxyz01 00000001 00000001 000000002 18932601 59847511 39390061 85058961 44425141 27822401 78016111 42443591 23929241 77767471 42396091 23747381 77767191 4239605