第一节 引言 二分法与迭代法.ppt

第二章方程求根 本章主要内容 1 二分法 2 简单迭代法 重点 3 牛顿迭代法 重点 4 割线法 本章难点 分析迭代法的收敛性 历史背景 本章解决一元函数方程 的求根问题 否则称其为超越方程 如 当为多项式函数时 称此方程为代数方程 如 若函数可表示成 2 1 则称是方程 2 1 的重根 根的存在性 连续函数介值定理 则这样的在内唯一 若函数在上连续 且 则至少有一个数 使得 若还单调 定理 方程f x 0的有根区间的确定 有根区间 方程在这样的区间内有且只有一个实根 1 描图法 将方程f x 0化为g x h x 的形式 画出g x 和h x 的简图 从两条曲线的交点的横坐标的位置 例2 1 求方程3x 1 cosx 0的有根区间 解 用描图法 将方程变形为 令g x 3x 1 h x cosx 做出两个函数的简图 确定有根区间 注 g x 和h x 的图形比较容易作出 由图可知 方程仅有一个实根 有根区间为 2 通过研究函数性态判断有根区间 例2 2求函数的有根区间 解 令 并对其求导数得 单调减少的 所以函数在上是 又 根据连续函数介值定理 方程在内有且仅有一个实根 所以是方程的有根区间 第一节二分法 若f x 在 a b 上连续 且f a f b 0 以此类推 上至少有一实根 则f x 在 a b 原理 基本思想 逐步将区间分半 通过判别区间端点函数值的符 号 进一步搜索有根区间 将有根区间缩小到充分小 从而求出满足精度的根的近似 二分法的实施步骤 1 找出方程的有根区间 若每次二分时所取区间中点都不是根 则上述过程将无限进 3 判断 若则是方程的根 a 若 则根属于 置 行下去 计算结束 否则 b 若 则根属于 置 注 上述过程中常取做机器零 当小于此数时认为是零 2 计算f x 在区间中点的值 如 误差分析 什么时候停止计算 按上述过程反复进行 可得一系列有根区间套 当n 时 区间长度趋近于零 因此区间必将最终收缩为 由于每一区间都是前一区间的一半 因此区间的长度 一点 显然就是所求的根 则 从而有下述误差估计式 只要 根据误差估计式 对于预先给定的精度 即 可由此确定最大对分次数 便有 因此 就是满足精度要求的近似解 二分法算法实现 问题 给定区间 a b 求f x 0在该区间上的根x 输入 a和b 容许误差TOL 最大对分次数Nmax 输出 近似根x Step1令k 1 Step2计算x a b 2和y f x Step3若k Nmax 做Steps4 6 Step4若 y TOL 停止 输出x Step5若y f a 0 置b x 否则 置a x Step6置k k 1 计算x f a b 2 转Step3 Step7输出方程的近似解x 停止 算法过程 解 例2 3用二分法求方程在区间上的根 误差限为0 0005 问至少需对分多少次 由题意知 最大对分次数 所以至少需对分次 对分9次后取有根区间的中点即为满足精度要求的根 算法简单直观 收敛性有保证 对f x 要求不高 只要连续即可 无法求复根及重根 收敛速度慢 注 用二分法求根 最好先给出f x 草图以确定根的大概位置 或用搜索程序 将 a b 分为若干小区间 对每一个满足f ak f bk 0的区间调用二分法程序 可找出区间 a b 内的多个根 且不必要求f a f b 0 第二节迭代法 f x 0 基本思想 从一个初值x0出发 计算 一 简单迭代法 f x 的根 若数列收敛 即存在 使得 称为迭代函数 称为的不动点 若函数还是连续的 则 即 即方程f x 0的一个根 这样就找到了函数的一个不动点 几何意义 解 下面选取5种迭代格式 1 即 2 即 3 即 4 即 5 即 法1 法4 法3 法2 法5 如何判定迭代法的收敛性呢 如何构造迭代函数才能使迭代法收敛 有如下充分条件 定理2 1 压缩映射原理 若迭代函数满足下列两个条件 2 0 L 1使得对 x a b 有 1 当x a b 时 则迭代过程对于任意初值均收敛于 方程的根 且有如下误差估计式 证明 先证当k 时 xk收敛到x 这是因为 再证定理中的误差估计式 利用三角不等式 所以 注 该定理结论表明只要相邻两次迭代值的距离 足够小 即可保证近似值具有足够的精度 所以可用 来判断是否满足迭代精度 问题 给定初始近似值x0 求的解 输入 初始近似值x0 容许误差TOL 最大迭代次数Nmax 输出 近似解x或失败信息 简单迭代法的算法实现 Step1置i 1 Step2当i Nmax时 作Step3 5 Step3置 否则 置i i 1 Step4若 x x0 TOL 则输出x 停止 Step6输出迭代失败信息 停止计算 Step5置x0 x 转Step2 二 局部收敛性 定义 局部收敛性 若存在的一个闭邻域 对任意 于 则称该迭代法局部收敛 初值 由迭代过程产生的序列均收敛 定理2 2 关于局部收敛 有如下判定定理 设为的解 在的某邻域连续 且 则迭代过程局部收敛 三 迭代法的收敛阶 及常数 使 注 1 的大小反映了迭代法收敛的快慢 是收敛速度 的一种度量 定义 设序列收敛到 若存在实数 则称序列是阶