求代数方程的近似根(解).ppt

数学实验 实验三 求代数方程的近似根(解) 代数方程近似求解 相关概念 主要内容 对分法 对分法 对分法收敛性 主要内容 不动点迭代法 迭代法的收敛性 迭代法收敛性判断 迭代法收敛性判断 迭代法的加速 松弛迭代法 主要内容 牛顿迭代法 牛顿法迭代公式 牛顿法迭代公式 Matlab 解方程函数 多项式的零点 线性方程组求解 非线性方程的根 非线性方程的根 fzero 举例 符号求解 符号求解 上机作业 * * 解方程（代数方程）是最常见的数学问题之一，也是众多应用领域中不可避免的问题之一 目前还没有一般的解析方法来求解非线性方程，但如果在任意给定的精度下，能够解出方程的近似解，则可以认为求解问题已基本解决，至少可以满足实际需要 本实验主要介绍一些有效的求解方程的数值方法：对分法，不动点迭代法 和 牛顿法。同时要求大家学会如何利用Matlab 来求方程的近似解 问题背景和实验目的 如果 f(x) 是一次多项式，称上面的方程为线性方程；否则称之为非线性方程 线性方程 与 非线性方程 本实验主要讨论非线性方程的数值求解 对分法 本实验讨论的数值算法 牛顿迭代法 不动点迭代一般形式 松弛加速迭代法 不动点迭代法 基本思想 将有根区间进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止 适用范围 求有根区间内的 单重实根 或 奇重实根 数学原理：介值定理 设 f(x) 在 [a, b] 上连续，且 f(a) f(b)0，则由介值定理可得，在 (a, b) 内至少存在一点 ? 使得 f(?)=0 具体步骤 设 f(x) 在区间 [a,b] 内连续，且 f(a)f(b)0。 对于给定的精度要求 ? ，若有 |f(z)|? ，则 z 就是我们所需要的 f(x)=0 在区间 [a,b] 内的 近似根 例：用对分法求 x3 - 3x + 1 = 0 在 [0, 1] 中的解。（fuluA.m） (1) 令 x = (a+b)/2, 计算 f(x) (2) 若 |f(x)| ?，则停止计算，输出近似解 x (3) 若 f(a) · f(x) 0，则令 b = x; 否则令 a = x (4) 返回第一步 收敛性分析 设方程的根为 x* ? (ak , bk ) ，又 ，所以 0(k ?) 对分法总是收敛的 对分法的收敛速度通常较慢 对分法通常用来试探实根的分布区间，或给出根的一个较为粗糙的近似 根据上面的算法，我们可以得到一个每次缩小一半的区间序列 {[ak , bk ]} ，在 (ak , bk ) 中含有方程的根。 对分法 本实验讨论的数值算法 牛顿迭代法 不动点迭代一般形式 松弛加速迭代法 不动点迭代法 基本思想 构造 f (x) = 0 的一个等价方程： 从某个近似根 x0 出发，计算 得到一个迭代序列 k = 0, 1, 2, ... ... ? (x) 的不动点 f (x) = 0 x = ? (x) 等价变换 f (x) 的零点 若 收敛，即 ，假设 ?(x) 连续，则 收敛性分析 即 注：若得到的点列发散，则迭代法失效！ 定义： 如果存在 x* 的某个 邻域 ? =(x*-? , x* +? ), 使得对 ? x0 ? ? 开始的迭代 xk+1 = ?(xk) 都收敛, 则称该迭代法在 x* 附近局部收敛。 定理 ： 已知方程 x =?(x)，且 (1) 对 ? x?[a, b]，有 ?(x)?[a, b]； (2) 对 ? x?[a, b]，有|?’(x)|?q 1； 则对 ?x0?[a, b] ，由迭代 xk+1 = ?(xk) 得到的点列都收敛，且 以上所给出的收敛性定理中的条件的验证都比较困难，在实际应用中，我们常用下面不严格的判别方法： 当有根区间 [a, b] 较小，且对某一 x0?[a, b] ，|?’(x0)| 明显小于 1 时，则我们就认为迭代收敛 例：用不动点迭代法求 x3 - 3x + 1 = 0 在 [0, 1] 中的解。 （fuluB.m） q 越小，迭代收敛越快 ?’(x*) 越小，迭代收敛越快 设迭代 xk+1 = ?(xk) ，第 k 步和第 k+1 步得到的近似根分别为 xk 和 ?(xk) ，令 其中 wk 称为加权系数或权重。得新迭代 xk+1 = ?(xk) 加权系数 wk 的确定：令 ?’(x)=0 得 松弛法迭代公式： 松弛法具有较好的加速效果 甚至有些不收敛的迭代，加速后也能收敛 缺点：每次迭代需计算导数 例：用