非线性方程(组)的迭代解法.ppt

2020 2 12 1 第二章非线性方程 组 求根方法 若n 1 称为非线性方程求根问题 n 1 称为非线性方程组求解问题 理论问题 1 解的存在性 即有解还是无解 有多少解 2 解的性态 即孤立解的区域 解的重数 光滑性 关于解的存在性及其性态 不是数值分析所讨论的问题 我们总认为 我们的任务是用数值方法求满足一定精度要求的近似解 通常求其精确解是困难的 2020 2 12 2 二分法 内容 一般迭代法 牛顿迭代法 迭代法的加速 非线性方程组的牛顿迭代法 2020 2 12 3 1 二分法 设在区间上连续且有 则在区间内有解 不妨设解唯一 算法构造原理 有根区间 2020 2 12 4 x1 a x2 b 什么时候停止 或 x 算法停止的条件 x 2020 2 12 5 综合上述 得到如下算法 1 2 3 否则 4 否则 转 2 例1 可得 共计算21次 注 其中为精度控制参数 2020 2 12 6 二分法只能求有根区间中的奇数重的实根 关于二分法的讨论 1 二分法线性收敛 2 二分法可用来细化有根区间 这是它的一大优点 3 故二分法可以用来确定迭代法的迭代初值 返回主目录 2020 2 12 7 2 一般迭代法 1 2 3 一 构造方法 1 2020 2 12 8 例2 2020 2 12 9 1 5000 0 87506 7324 69 72001 0275e 8不收敛 1 50001 28701 40251 34551 37521 36011 36781 36391 36591 36491 36541 36511 36531 36521 3652 1 50000 81652 99690 2 9412i不收敛 1 50001 34841 36741 36501 36531 36521 3652 方法1 方法2 方法3 方法4 收敛与否 以及收敛快慢 取决于迭代函数 15次 6次 精度控制的表达式 2020 2 12 10 二 大范围收敛定理 1 2 则 1 2 3 下面看证明过程 即是自映射 2020 2 12 11 1 由条件 1 可得解的存在性 由条件 2 可证解的唯一性 2 由条件 1 可知 3 得证 进而可证 2020 2 12 12 三 局部收敛定理 若 由迭代 1 产生的序列 证明 略 注 当定理条件成立时 只要x0充分接近x 就能保证迭代序列 xn 收敛于x 且有与前一定理完全相同的不等式成立 2020 2 12 13 分析例2四种迭代格式的收敛性 一般迭代法只有理论上的意义 因为构造保证收敛的迭代函数比较困难 注 方法1的收敛性分析 方法2的收敛性分析 方法3的收敛性分析 方法4的收敛性分析 四种迭代格式的计算结果见本课件P9 取定初值x0 1 5 1e 4 2020 2 12 14 四 收敛阶 速度 的讨论 定义 p 1 线性收敛 p 2 平方收敛 2 p 1 超线性收敛 注 1 p 1时 c 1 2 满足局部收敛定理的简单迭代算法至少具有一阶收敛速度 2020 2 12 15 定理 简单迭代算法m阶收敛的充分条件 设 在包含x 某个开区间内连续 若 使得 则 注 1 给出了由迭代函数判断收敛速度的方法 2 给出了提高收敛速度的方法 由迭代产生的序列 xn 以m阶收敛速度收敛到x 证明 由泰勒公式和收敛阶定义可证 2020 2 12 16 例3 解 迭代函数为 2020 2 12 17 迭代函数为 解 返回主目录 2020 2 12 18 3 简单迭代法加速 如何对其加速 由微分中值定理得 事实上 设迭代算法产生的序列 其中介于和之间 2020 2 12 19 一 埃特金 Aitken 加速方法 令 作为的校正值 2020 2 12 20 二 steffensen加速算法 设迭代算法 对其应用Aitken加速方法 得到如下Steffensen算法 若在附近变化不大 2020 2 12 21 Steffensen算法的收敛性 注 1 可以用Steffensen算法对收敛缓慢的简单迭代算法加速 可以证明 2 对于至少平方收敛的算法 用Steffensen算法进行加速 意义不大 返回主目录 2020 2 12 22 4 牛顿迭代算法 将f x 在初值x0处做Taylor展开 取其线性部分做为f x 的近似 有 若 则有 记为 同理 我们可以得到 2020 2 12 23 这样一直下去 我们可以得到迭代序列 Newton迭代的迭代函数 2 牛顿迭代算法 切线法 其它构造方法 1 待定函数法 2 数值积分法 2020 2 12 24 收敛定理 单根的情形 2020 2 12 25 证明 由已知可得 所以至少平方收敛 利用收敛阶的定义来证明 注 也可以由收敛阶的判定定理来证 2020 2 12 26 应用举例 1 对于给定的正数C 应用牛顿法解二次方程x2 C 0 可得 证明上述迭代算法收敛 并求收敛阶 1 当x0 0时 收敛于 2 当x0 0时 收敛于 1 得证 2 事实上 对 式进行配方可得 下面证明1 2020 2 12 27 2 对于给定的正数C 应用牛顿法求解方程 可得 可以证明上述迭代算法对任意初值都收敛于 事实上 从而 2020 2 12 28 牛顿迭代法的几点说明 牛顿迭代法算法简单 且局部收敛 但初值x0的选择困难 1 2 牛顿迭代每步都要计算导数 增加了计算量 3 定理表明牛顿迭代求单根有效且平方收敛 能求重根吗 一 一般来说采用试探法 可以结合二分法或通过做出函数图形来帮助选择初值 关于初值 二 导数的计算 1 利用牛顿迭代法先计算几步 比如计算到了第k步 得到近似值xk 接下来用来代替导数 该算法通常是线性收敛的 2020 2 12 29 2 一个实用的方法是用差分代替微分 即 此迭代法称为割线法 它是超线性收敛的 三 关于重根的问题 2020 2 12 30 可见 当x 为重根时 牛顿迭代线性收敛 且随着m的增加 收敛性变差 计算重根的改进算法 1 至少平方收敛 证明略 设重数m已知 应用牛顿迭代法得 2020 2 12 31 返回主目录 2 重数不知道时 一个实用的方法是 令 则 直接对应用牛顿迭代法求解 至少平方收敛 2020 2 12 32 解非线性方程组的牛顿迭代法 2020 2 12 33 Jacobi矩阵 2020 2 12 34 注意事项 为了解决上述问题 提出拟牛顿法 2020 2 12 35 2020 2 12 36 2020 2 12 37 Broyden秩1方法 2020 2 12 38 2020 2 12 39 综合上述 得到Broyden秩1方法 2020 2 12 40 2020 2 12 41 返回主目录 2020 2 12 42 1 数值分析 颜庆津 修订版 北京航空航天大学出版社 20002 李庆扬 非线性方程组的数值解法 科学出版社 1987 参考书目 2020 2 12 43 例2 返回 不满足局部收敛