第二章,非线性方程的数值解法

第二章非线性方程的数值解法 NumericalSolutionsofNonlinearEquations 本章主要内容 1 二分法2 不动点迭代的构造及其收敛性判定 重点 3 Newton和Steffensen迭代 重点 4 割线法5 非线性方程组的迭代解法 历史背景 求方程几何意义 基本定理 如果函数在上连续 且则至少有一个数使得 若同时的一阶导数在内存在且保持定号 即 或 则这样的在内唯一 1二分法 Bisection 原理 若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迭代法的理论 TheoryofIteration 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 ThefailedafterNmaxiterations 不成功 STOP 当x很大时 此处可改为 二 局部收敛性 LocalConvergence 注解 局部收敛性特点 假定解存在 且肯定存在解的一个邻域 使得对其中所有初始值 由迭代生成的序列收敛于解 半局部收敛特点 不知道解存在 但指出要从满足一定 通常很强 条件的初始值出发 保证收敛于某一 临近 解 全局 整体 收敛 肯定在全空间或至少其中一个很大的部分中 无论从何处出发 都能保证收敛于一个解 证明 因为在的某邻域连续 存在邻域 即对 则由定理2 3 迭代法 对收敛 即局部收敛 注 例3 已知方程在1 5附近有根 把方程写成三种不同的等价形式 1 对应迭代格式 2 对应迭代格式 3 对应迭代格式 判断迭代格式在的收敛性 选一种收敛格式计算 精确到小数点后第二位 解 1 迭代格式收敛 2 迭代格式收敛 3 迭代格式发散 选择 2 计算012341 51 4811 4731 4691 467 注 1 的大小反映了迭代法收敛的快慢 是收敛速度的一种度量 2 设迭代函数满足收敛定理的条件 则产生的序列满足 如果在或的邻域有若取 必有 此时有 证明 由Taylor公式 充分性 取极限得 必要性 设迭代式 是阶收敛的 则有 即 且 反证法 设结论不成立 则存在最小正整数 满足 情形一 情形二 由充分性证明知 迭代式 是阶收敛的 即 与阶收敛矛盾 证明方法与情形一类似 自己练习 一 使用两个迭代值的组合方法 3迭代收敛的加速方法 Accelerating 将x g x 等价地改造为 当和时 有 相应的迭代公式为 或者 选取特殊的 有可能使迭代加速 如 迭代公式为 几何意义如图示 注 1 这种迭代对原迭代公式 的各近似值在根的两侧往复地趋于时较为有效 又如 新的迭代函数为 根据定理2 5知 迭代法至少是二阶的 但由于不知道 故也得不到 因此可取其的近似值 即 从而有 二 Steffensen 斯蒂芬森 加速迭代法 三个迭代值组合 或者 若令 Steffensen迭代法的优点 可以改进收敛速度 有时也能把不收敛的迭代法改进为收敛的二阶方法 艾特肯 Aitken 加速方法 下面选取3种迭代格式 显示计算结果 证明 设斯蒂芬森 Steffensen 的迭代为 其中 设 则 反之 设 型 洛比塔法则 由Taylor公式 则 上式中用替换 即证 代入上述结果 返回 4牛顿法 Newton Raphson 一 牛顿迭代公式的推导 1 待定参数法 不动点迭代的关键是构造满足收敛条件的迭代函数 一种自然的选择是令 为了加速不动点迭代的收敛过程 应尽可能使迭代函数在处有更多阶导数等于零 定理2 5 令 取 因此 选取迭代函数 Newton Raphson迭代格式 称之为牛顿 拉夫森方法 简称牛顿法 原理 将非线性方程线性化 取x0 x 将f x 在x0做一阶Taylor展开 在x0和x之间 2 Taylor展开法 Taylor sexpansion 将 x x0 2看成高阶小量 则有 解 等价于求方程的正根 解法一 等价于求方程的正根 解法二 等价于求方程的正根 证明 Newton s事实上是一种特殊的不动点迭代其中 则 收敛 由Taylor展开 在单根 simpleroot 附近收敛快 只要 则令可得结论 Th2 5 有根 根唯一 产生的序列单调有界保证收敛 证明 因为f C2 a b 由 1 和 2 知f x 在 a b 内有唯一根 下面由条件 1 2 分4种情况讨论 仅证明第一种情况 其它情况类似讨论 由中值定理 使得 由 另一方面 由Taylor展开得 介于 之间 重复以上过程 可得 归纳法 自己证 因此 数列单调下降且有下界 令 由Taylor展开得 注 Newton s收敛性依赖于x0的选取 x Th2 9中条件 3 的几何意义 证明仿照Th2 9 重根 multipleroot 加速收敛法 Q1 若 Newton s是否仍收敛 设x 是f的n重根 则 且 因为Newton s事实上是一种特殊的不动点迭代 其中 则 A1 有局部收敛性 但重数n越高 收敛越慢 Q2 如何加速重根情况时的收敛速度 A2 将求f的重根转化为求另一函数的单根 令 则f的重根 的单根 求复根 FindingComplexRoots Newton公式中的自变量可以是复数 记z x iy z0为初值 同样有 设 代入公式 令实 虚部对应相等 可得 5弦割法与抛物线法 SecantandParabola 割线 secantline 切线斜率 割线斜率 需要2个初值x0和x1 Newton s每一步要计算f和 为了避免计算导数值 现用f的值近似 从而得到弦割法 割线法 x2 一 弦割法 收敛速度介于NewtonandBisection之间 例1证明方程在区间内有唯一根 且使得对任意的初始值 由割线法产生的序列都收敛于 证明 令 方程存在根 方程存在唯一根 Muller方法的思想来源于弦割法 利用3个已知点构造一条抛物线 取其与x轴的交点构造下一次迭代值 x 二 抛物线法 Muller 几何图示 xk 1 Muller方法的具体实现 设已知三个点 则过上述三个点的抛物线方程为 取该抛物线与x轴的交点作为下一次迭代值 即 然后取新的相邻的三次迭代值重复上述过程 即为Muller方法 Muller方法中抛物线根的计算方法 首先要将抛物线化为规范形式 引入新的变量 将上述变量代入前面的抛物线方程 得 其中 的两个零点为 取的两个零点中靠近的那个零点 则有 Muller方法的迭代公式为 具体计算步骤见教材P39 算法 Muller方法给定初始近似值x0 x1 x2 求f x 0的根 输入 初值x0 x1 x2 容许误差TOL 输出 近似解x Step1Seti 1 Step4If t4 x2 x1 TOLStep2dosteps3 7thenOutput x STOP Step3Computet3 x2 x1 x1 x0 Step5Seti d3 1 t3 Step6Setx0 x1 x1 x2 x2 x a f x0 t32 f x1 t3d3 f x2 t3 Step7gotoStep2 b f x0 t32 f x1 d32 f x2 t3 d3 c f x2 d3 t4 2c b sign b sqrt b2 4ac x x2 t4 x2 x1 Muller法的优点 初值的选取范围比Newton法和弦割法宽 而且可以一次求得方程的一对复根