非线性方程的数值解法-2.ppt

第二章非线性方程的数值解法 NumericalSolutionsofNonlinearEquations 本章主要内容 1 二分法2 不动点迭代的构造及其收敛性判定 重点 3 Newton和Steffensen迭代4 弦割法与抛物线法 历史背景 求方程几何意义 基本定理 如果函数在上连续 且则至少有一个数使得 若同时的一阶导数在内存在且保持定号 即 或 则这样的在内唯一 1二分法 BisectionMethod 原理 若f C a b 且f a f b 0 则f在 a b 上至少有一实根 基本思想 逐步将区间分半 通过判别区间端点函数值的符号 进一步搜索有根区间 将有根区间缩小到充分小 从而求出满足给定精度的根的近似值 终止法则 x1 x2 a b Whentostop 或 不能保证x的精度 二分法算法给定区间 a b 求f x 0在该区间上的根x 输入 a和b 容许误差TOL 最大对分次数Nmax 输出 近似根x Step1Setk 1 Step2Computex f a b 2 Step3While k Nmax dosteps4 6Step4If x TOL STOP Outputthesolutionx Step5Ifx f a 0 Setb x ElseSeta x Step6Setk k 1 Computex f a b 2 GoToStep3 Step7Outputthesolutionofequation x STOP 3 由二分法的过程可知 4 对分次数的计算公式 1 2 令 解 例1 用二分法求方程在区间上的根 误差限为 问至少需对分多少次 简单 对f x 要求不高 只要连续即可 无法求复根及偶重根 收敛慢 注 用二分法求根 最好先给出f x 草图以确定根的大概位置 或用搜索程序 将 a b 分为若干小区间 对每一个满足f ak f bk 0的区间调用二分法程序 可找出区间 a b 内的多个根 且不必要求f a f b 0 2迭代法的理论 TheoryofIterationMethod f x 0 x g x 迭代函数 思路 从一个初值x0出发 计算x1 g x0 x2 g x1 xk 1 g xk 若收敛 即存在x 使得 且g连续 则由可知x g x 即x 是g的不动点 也就是f的根 f x 的根 g x 的不动点 一 不动点迭代 Fixed PointIteration 几何意义 下面选取5种迭代格式 法1 法4 法3 法2 法5 Lipschitz条件成立的充分条件 证明 g x 在 a b 上存在不动点 令 有根 不动点唯一 反证 若不然 设还有 则 而 当k 时 xk收敛到x L越收敛越快 可用来控制收敛精度 小 注 条件 II 可改为在 a b 满足Lipschitz条件 定理结论仍然成立 定理2 3 算法 不动点迭代给定初始近似值x0 求x g x 的解 输入 初始近似值x0 容许误差TOL 最大迭代次数Nmax 输出 近似解x或失败信息 Step1Seti 1 Step2While i Nmax dosteps3 6Step3Setx g x0 计算xi Step4If x x0 TOLthenOutput x 成功 STOP Step5Seti Step6Setx0 x 更新x0 Step7Output ThemethodfailedafterNmaxiterations 不成功 STOP 二 局部收敛性 LocalConvergence 注解 局部收敛性特点 假定解存在 且肯定存在解的一个邻域 使得对其中所有初始值 由迭代生成的序列收敛于解 半局部收敛特点 不知道解存在 但指出要从满足一定 通常很强 条件的初始值出发 保证收敛于某一 临近 解 全局 整体 收敛 肯定在全空间或至少其中一个很大的部分中 无论从何处出发 都能保证收敛于一个解 证明 因为在的某邻域连续 存在邻域 即对 则由定理2 3 迭代法 对收敛 即局部收敛 注 例3 已知方程在1 5附近有根 把方程写成三种不同的等价形式 1 对应迭代格式 2 对应迭代格式 3 对应迭代格式 判断迭代格式在的收敛性 选一种收敛格式计算 精确到小数点后第二位 解 1 迭代格式收敛 2 迭代格式收敛 3 迭代格式发散 选择 2 计算012341 51 4811 4731 4691 467 注 1 的大小反映了迭代法收敛的快慢 是收敛速度的一种度量 2 设迭代函数满足收敛定理的条件 则产生的序列满足 如果在或的邻域有若取 必有 此时有 证明 由Taylor公式 充分性 取极限得 必要性 设迭代式 是阶收敛的 则有 即 且 反证法 设结论不成立 则存在最小正整数 满足 情形一 情形二 由充分性证明知 迭代式 是阶收敛的 即 与阶收敛矛盾 证明方法与情形一类似 自己练习 一 使用两个迭代值的组合方法 3迭代收敛的加速方法 AcceleratingMethod 将x g x 等价地改造为 当和时 有 相应的迭代公式为 或者 选取特殊的 有可能使迭代加速 如 迭代公式为 几何意义如图示 注 1 这种迭代对原迭代公式 的各近似值在根的两侧往复地趋于时较为有效 又如 新的迭代函数为 根据定理2 5知 迭代法至少是二阶的 但由于不知道 故也得不到 因此可取其的近似值 即 从而有 二 Steffensen 斯蒂芬森 加速迭代法 三个迭代值组合 或者 若令 Steffensen迭代法的优点 可以改进收敛速度 有时也能把不收敛的迭代法改