数值分析2-计算方法2非线性方程的数值解法

第二章非线性方程的数值解法考察下列方程f x 0f x 可以是代数多项式 也可以是超越函数 求解精确解一般不可能 只能寻求数值解 2 1二分法若函数f x 在区间 a b 上连续 且f a f b 0则方程f x 0在区间 a b 上至少有一个实数根 二分过程 假定有根区间仅一个实数根x 如果f a f a b 2 0 则在区间 f a f a b 2 上有实数根 如果f a b 2 f b 0 则在区间 f a b 2 f b 上有实数根 于是 新的有根区间仅为原有根区间的一半 记作 a1 b1 重复上述二分过程 可得区间宽度不断减半的有根区间序列 a b a1 b1 a2 b2 ak bk 其中 令有根区间 ak bk 的中点xk ak bk 2为x 的近似值 在上述二分过程中 得到如下x 的近似值序列x0 x1 x2 xk 由于对于预先设定的精度 0 只要便有此时xk为满足精度要求的近似解 表2 1x6 1 324 x x x6 0 0039 0 005 例2 1用二分法求方程f x x3 x 1 0在区间 1 1 5 内的一个实根 要求误差不超过0 005 解 由公式 2 3 估计二分的次数于是 只要二分6次即可达到精度要求 二分过程见表2 1 2 2Jacobi 简单 迭代法1 Jacobi迭代法的基本原理考察方程f x 0 x x 在根x 的附近取一点x0作为x 的预测值 有x1 x0 重复上述步骤 有如下迭代公式xk 1 xk k 0 1 2 其中 x 为迭代函数 x0 x1 xk 为迭代序列 等价形式 如果迭代序列 xk 的极限存在 即x xk则迭代过程收敛 如果迭代序列 xk 的极限不存在 迭代过程发散 a 迭代收敛 b 迭代发散 例2 2求方程f x x3 x 1 0在x 1 5附近的根x 的近似值 解 将方程f x 0改写为如下等价形式x x 1 1 3 迭代公式为xk 1 xk 1 1 3 k 0 1 2 取x0 1 5 计算过程用6位有效数字表示 迭代结果见表2 2表2 2 如果将原方程改写为如下等价形式x x3 1则有迭代公式xk 1 xk 3 1迭代初值x0 1 5 则有x1 2 357 x2 12 39 迭代过程发散 2 Jacobi迭代过程的收敛性定理2 1如果迭代函数 x 满足如下条件 1 对任意x a b 有a x b 2 存在正数L 1 使对任意x a b 有 x L 1则迭代过程xk 1 xk 对任意x0 a b 均收敛于方程x x 的根x 且有如下误差事后估计式 证 由微分中值定理 x xk x xk 1 x xk 1 L x xk 1 式中 为x 与xk 1之间的一点 据此反复递推 x xk L x xk 1 L2 x xk 2 Lk x x0 显然 当k 时 xk x 迭代序列 xk 收敛于x 为确保收敛 全体迭代值xk应在 a b 上取值 为此对任意x a b 均有 x a b 对任意正整数p 有 xk p xk xk p xk p 1 xk p 1 xk p 2 xk 1 xk Lp 1 Lp 2 1 xk 1 xk 固定k并令p 有 定义2 1称迭代过程在根x 的附近具有局部收敛性 指的是如果存在邻域 x x 迭代过程xk 1 xk 对任意初值x0 收敛 由此可见 只要前后两次迭代值得差值足够小 就可使近似值xk 1达到任意精度 一般情形下 用 xk 1 xk 来控制迭代精度 定理2 2设 x 在方程x x 根的附近有连续的一阶导数 且 x 1则迭代过程xk 1 xk 具有局部收敛性 例2 3求方程x e x在x 0 5附近的一个根 要求精度 10 5 解 通过搜索方法 得有根区间 0 5 0 6 且有 x exp 0 5 1迭代公式xk 1 e xk对迭代初值x0 0 5收敛 经18次迭代后 x18 0 56714 满足所规定的精度要求 2 3Aitken加速迭代法设xk是第k次迭代近似值 由迭代公式得第k 1次迭代值 记作 k 1 即 k 1 xk 由微分中值定理 有 k 1 xk L xk 记 k 1 k 1 且有 xk 1 k 1 L k 1 于是 k 1 xk 1 xk k 1整理后 有如下事后估计式 k 1 k 1 k 12 k 1 2 k 1 由此 得下列Aitken迭代加速公式 校正 k 1 xk 再校正 k 1 k 1 改进xk 1 k 1 k 1 k 12 k 1 2 k 1 例2 4用Aitken方法求解方程f x x3 x 1 0在x 1 5附近的根 解 以如下迭代公式xk 1 xk 3 1为基础 构造Aitken迭代加速公式 k 1 xk 3 1 k 1 k 1 3 1xk 1 k 1 k 1 k 12 k 1 2 k 1 初值x0 1 5 经5次迭代 得x5 1 32472 例2 5证明求方程 2 1 0在1 2上有一个实根 用二分法求这个根 要求 10 3 若要求 10 6 需二分区间1 2多少次 1 3253 9 19例2 6设方程12 3 2cos 0的迭代格式为 1 4 23cos 1 证明对 0 均有lim 2 取 0 4 求此迭代格式的近似值 精度为 10 3 列出各迭代值 3 3475 3 2 4Newton迭代法1 Newton迭代法的构造思路设方程f x 0的根 xk为方程根的近似值将函数f x 在xk处做一阶Taylor展开用近似代替函数f x 于是f x 0 求解 得 由此得Newton迭代格式Newton迭代法的几何描述y切线法xk 2xk 1xkx 例2 7用Newton法求方程x e x在x 0 5附近的一个根 解 将x e x改为xex 1 0令f x xex 1Newton迭代公式为取x0 0 5 利用上述迭代公式 得x1 0 57102 x2 0 56716 x3 0 56714 例2 8用Newton法求115 精度 10 6解 将此问题转化为下列二次方程x2 115 0Newton迭代格式为xk 1 12 xk 115xk 初值x0 10 4次迭代得所要求的近似值115 10 723805 2 Newton迭代法的收敛性定义2 2设迭代序列 收敛于 误差为 如果有 1 0 称迭代序列是 阶收敛的 特别地 1 1 0 1 线性收敛 2 2 平方收敛 3 1 1 0 超 阶收敛的 例2 9设 在 的根 附近有连续的p导数 且 1 0 0证明迭代过程 1 是p阶级收敛的 例2 10设 是 0的一个根 且 0 为单根 证明Newton迭代法至少是二阶收敛的 3 Newton下山法例2 11求方程f x x3 x 1 0在x 1 5附近的根x 的近似值 解 设迭代初值 0 1 5 Newton迭代公式为 1 3 13 2 1迭代结果为 6位有效数字 1 1 34783 2 1 32520 3 1 32472如果初值为 0 0 6 则 1 17 9 迭代发散 对迭代过程附加一项要求 0 1下山条件具体方法为松弛法 记 1 取 1和 的加权平均作为迭代改进值 1 即 1 1 1于是 得Newton下山法迭代公式 1 下山因子 下山因子 的选取从 1开始 判断 1是否成立成立 则用Newton迭代法进行迭代不成立 则下山因子 依次在下述集合12 14 12 中选取 直至满足 1 在例2 8中 仍取初值 0 0 6 经过试探 找到 132 得到第一步 1 1 140625 比 0更接近于根x 从而保证迭代过程收敛 4 有重根情形的Newton迭代法设 为 0的 重根 即有 0 2Newton迭代法的迭代函数 1 1 2 2 2 1 2 1 1 0 1此时 Newton迭代法收敛 但仅为线性收敛 方案一将迭代函数 改造为 且有 0于是下述迭代公式 1 至少具有是二阶收敛的 缺点 事先知道 的重数 一般不可能 方案二令 且 则 1 由此可见 是 0的单根 0的重根 0的单根 取迭代函数 2 从而构造迭代法 1 2 例2 12方程 4 4 2 4 0的根 2是二重根 1 1 2 24 Newton迭代法 2 1 2 22 方案一 3 1 2 2 2 2方案二 初值 0 1 5方法 2 与 3 二阶方法 迭代第三步时精度到10 9 方法 1 为线性收敛 要到达相同精度需迭代30次 5 非线性方程组的Newton迭代法设有非线性方程组 1 1 2 0 2 1 2 0 1 2 0依次将上述 个方程在点 处做一