第六章 非线性方程

第六章非线性方程求根 引言基本概念与二分法不动点迭代法及其收敛性牛顿法 引言 在科学研究和工程应用中经常遇到求解非线性方程的问题 对于非线性方程 6 1 其中 若 为不高于4次的多项式函数 则这样的方程有解析的求根公式可用 若 为高于4次的多项式函数或者不为多项式函数 则往往没有求根公式 只能采用适当的数值方法求得达到精度要求的近似解 6 1基本概念与二分法 几个有关方程根的基本概念 定义6 1对于单变量方程 若存在 使得 则称 为 的零点 或称 为方程 的根 若 可表示为 其中 或者 为正整数 则称 是 的 重零点 或称 是方程 的 重根 定理6 1设函数 则点 是 的 重零点 当且仅当 6 1 2二分法 用计算机求解非线性方程分两步进行 一是根的隔离 即找出隔离区间 二是根的精确化 即从隔离区间的近似值出发 利用迭代法计算满足精度要求的根的近似值 若 在 上连续 且 则由连续函数的性质 在 内至少有一实根 把区间缩小 使函数在这个区间内只有一个实根 这种方法称为根的隔离 这个区间称为隔根区间 利用二分法来缩小隔根区间的基本思想是通过计算隔根区间的中点以及中点处的函数值 逐步将隔根区间对半缩小 二分法基本步骤 记隔根区间 为 其中点 若 则 即为 若 则当 时 是隔根区间 否则 隔根区间为 记此隔根区间为 并且它满足 重复以上过程 继续对分 如果在某次对分时得到的中点则即为所求的根计算结束 若否 则得到一系列隔根区间 满足 这里 当 时 由区间套定理 收缩为一点 这个点就是方程的根 同时 每次二分时所求出的中点 形成一个 无穷数列 且 这保证了 即 收敛于 由此可见 二分法不仅是一种缩小隔根区间的方法 还是一种独立的求根方法 实际计算时 对事先给定的精度要求 只要二分 的次数 满足不等式 即 就可以停止计算 取最后区间 的中点 作为方程根的近似值 二分法简单可靠 易于在计算机上实现 只要函数连续 隔根区间的中点序列总是收敛到方程的根 缺点 不能求偶数重根 不能求复根 收敛速度比较慢 因此常用它来为其它数值求解方法提供初始值 二分法图示 6 2不动点迭代法及其收敛性 迭代法是求解非线性方程组的主要方法 其基本思想是将变形成递推公式 通过此公式将所求方程根的初始近似值逐步精确化 直至获得满足精度要求的近似值为止 迭代法涉及的基本问题 迭代函数 的构造 迭代 数列 的收敛性和收敛速度 误差估计等 最关键的是迭代函数 的构造 它决定了迭代序列 的收敛性和收敛速度 6 2 1不动点迭代法的基本概念 对于给定的方程 将它化为等价方程 6 2 若 则 也满足 此时称 是 的不动点 选定一个初始值 利用递推关系 6 3 得到数列 若 存在 则称迭代过程 6 3 是收敛的 否则称它是发散的 若 连续且数列 收敛 则一定收敛于 即 我们称此种方法为不动点迭代法 称式 6 3 为不动点迭代格式 为迭代函数 从几何上看 是求直线 与曲线 的交点的横坐标 6 2 2迭代函数的构造 需要指出的是将方程变形时 迭代函数 的形 式并不惟一 下面的例题说明了这一点 例 用迭代法求方程 在 上的根时 可以将原方程转化为以下各种形式 区间 1 2 3 4 5 设 则 且 在 上单调 因此方程在 上必有一根 取 作为初始值 分别用以上五中迭代公式 计算 结果见下表 由上表可以看出 选用不同的迭代格式 会产生不同敛散性的迭代序列 格式 1 发散 格式 2 出现负数开方 无法继续 3 4 5 均收敛 但速度不一 其中 5 收敛最快 在用迭代法求根时 需注意 1 迭代序列需收敛 迭代函数及初值要满足一定条件 2 对于收敛的迭代序列 选取收敛速度快的迭代格式 3 对于收敛缓慢的迭代序列 加快其收敛速度 6 2 3迭代过程的收敛性 定义6 2若从 中任意选取初值 均能保证迭代格式 收敛 则称该迭代格式具有大范围收敛性 定理6 2 大范围收敛判别定理 设迭代格式 在 上连续且满足以下条件 1 当 时 有 映内性 2 存在正数 使对任意的 有 成立 则有如下结论 1 在 上存在惟一的不动点 2 对任意的初始近似值 迭代过程 所产生的迭代数列收敛于 3 误差估计式 证明 1 先证不动点的存在性 令 由于 的连续性知 连续 满足定理中条件 1 故 由连续函数的性质知 在 上必存在一点 使 即 下用反证法证其惟一性 若原方程在 内有两根 即 则由定理中条件 2 得 矛盾 故不动点惟一 2 证明迭代数列的收敛性 由已知条件可得 因为 故 即 故迭代数列收敛 3 证明 的误差估计式 因为 所以 而 故 6 4 又 于是 事后误差估计 6 5 事前误差估计 对于给定的允许误差 当 较小时 常用前后两次 迭代是否满足 来终止迭代过程 此外 由式 6 5 可以确定达到精度要求所需的迭代次数 当误差要求为 时 即要求 只要 可解出 为取整函数 取值为不大于 的最大整数 在实际应用中 经常将第二个条件换成更强的条件 即 在 上可导 且存在常数 使得对 有 定理6 2中映内性与压缩性的条件对于较大的区间难 以检验 实际应用中只考虑局部收敛情况 定义6 3设函数 有不动点 若存在邻域 使迭代格式 对任意的初值 均收敛 则称该迭代格式 具有局部收敛性 定理6 3 局部收敛判别定理 设 为 的不动点 在 的某邻域 内连续 且有 则 1 在 内存在惟一不动点 2 对任意选取的初始近似值 迭代过程 所产生的迭代数列收敛于 3 误差估计式为 证明过程与定理6 2类似 它具有明显的几何意义 下面的四幅图画出了迭代过程的发散与收敛的几何表述 6 2 4迭代过程的收敛速度与收敛阶 设迭代过程 6 3 产生的数列 收敛于 并 记 若存在非零常数 以及实数 使得 6 6 则称该迭代过程是 阶收敛的 时 称序列 线性收敛 此时 时 称序列 超线性收敛 时 称序列 平方收敛 越大 收敛速度越快 定理6 4若 在 的某个邻域内有 阶连续导数 且 则对任意靠近 的初始值 迭代公式 是 阶收敛的 若记 则有 6 9 6 8 证明 因为 由定理6 3知 迭代格式局 部收敛 取充分接近 的近似值 由泰勒展式 其中 介于 与 之间 由已知条件 上式可化为 即 由 的连续性 两边取极限得 即 对于收敛的迭代过程 只要迭代次数足够多 总能得到满足精度要求的近似根 但若迭代过程收敛缓慢 计算量太大 我们需要对迭代过程加速 斯特芬森迭代法就是一种常用的加速方法 6 2 5斯特芬森加速法 设由迭代格式 6 3 得到的迭代序列 线性收敛于 方程 的根 且 则有 对充分大的 有 解得 令 将上式右端作为 的修正值 则上式可写为 6 10 可看成另一种迭代格式 6 11 迭代函数 6 12 式 6 11 称为斯特芬森格式 斯特芬森迭代法主要用于改善线性收敛或不收敛的情况 对于本来是超线性收敛的迭代法 斯特芬森迭代法的加速效果可能不显著 定理6 5迭代格式 6 11 中的迭代函数 如上定义 则有以下结论 1 若 是 的不动点 在 的邻域内存在 一阶连续导数 且 则 也是 的不动 点 反之也成立 2 若 是 的不动点 在 的邻域存在且 连续 且 则斯特芬森迭代法是局部收 敛的 3 若 则斯特芬森迭代法是平方收敛的 若 则斯特芬森迭代法是超平方收敛的 6 3牛顿法 牛顿迭代法用线性方程代替原方程 建立迭代格式求近似根 其最大优点是在单根附近的近似根序列具有较高的收敛速度 还可以用来求代数方程的重根 复根 6 3 1牛顿迭代公式的构造 设 是非线性方程 的一个近似根 将 在 处作泰勒展开 得到近似的线性方程 若 求此线性方程的根 记为 即 将 在 处泰勒展开 得到近似的线性方程 若 记此线性方程的根为 则 以此类推 一般地 若 则 6 13 上式称为方程 的牛顿迭代公式 它也是一种 不动点迭代法 其迭代函数为 其中 牛顿法的几何意义是每次在近似根附近以切线代替曲线 并以切线与横轴的交点近似曲线与横轴的交点 如图 因此 牛顿法又称为切线法 6 3 2牛顿迭代法的收敛性 由定理6 4 可以得到牛顿迭代法的局部收敛定理 定理6 6设 是方程 的根 在 的邻 域内连续 则牛顿迭代法局部收敛 且求单根时 牛顿迭代至少二阶收敛 求重根时 牛顿迭代只有一阶收敛 证明 已知牛顿迭代函数 两边求导得 当 是 的单根时 有 且一般有 由此可得 由定理6 4知 此时牛顿法至少是二阶局部收敛 且 当 是 的 重根时 有 且 此时 故 于是 因为 所以 故此时牛顿法是一 阶局部收敛的 且 局部收敛性限制了牛顿法的使用范围 为保证牛顿法的大范围收敛性 须增加一些条件 定理6 7给定 设 在 上存在二阶连 续导数 且满足条件 1 2 3 不变号 4 初始值 且 则可得 1 在 内有惟一根 2 由初始值产生的牛顿迭代序列收敛于 3 即牛顿迭代二阶收敛 6 3 3牛顿迭代法的变形 虽然牛顿法的迭代收敛速度快 但每一步迭代都需计算和的值 计算量大 其次对初值选 择要求比较高 偏离精确值很远的初值产生的迭代 序列往往不收敛到所求的根 为了克服这些缺点 产生了若干牛顿法的变形 1 求重根的牛顿变形法 定理6 6表明 当 是 的 重根时 牛顿迭代一阶收敛 但收敛缓慢 改善如下 法一 若 已知 构造 6 14 此时迭代函数 由定理6 6推导过程知 故 6 14 式局部收敛且至少二阶收敛 不过 实际计算时往往很难知道根的重数 此时直接用上式难以计算 则可考虑法二 法二 令 若 是 的 重根 则 是 的 重根 从而 是 的单根 因此 由定理6 6 对 采用牛顿迭代法所得的 近似根序列至少具有2阶收敛性 由于 则方程 的牛顿迭代公式为 6 15 这种方法不要求知道具体重根数 但需要求 的二阶导数 2 牛顿下山法 牛顿法的收敛性依赖于初值的选取 若初值偏离所求根较远 则牛顿法可能发散 为了防止迭代过程发散 我们对其附加限制 使迭代过程单调 即 6 16 构造牛顿下山公式 6 17 其中 称为下山因子 构造牛顿下山公式的重点是选择合适的下山因子 先取 若计算结果满足下山条件式 6