第二章 非线性方程求解.ppt

第二章 非线性方程求解 第二章非线性方程求解目录 1对分法 2迭代法2 1迭代法的基本思想2 2迭代法的收敛条件2 3Steffensen方法 简单迭代法的加速 3Newton法与弦截法3 1Newton法3 2弦截法 第二章非线性方程求解概述 很多科学计算问题常常归结为求解方程 例如 从曲线y x和y lgx的简单草图可看出方程lgx x 0有唯一的正根x 但是没有求x 的准确值的已知方法 即使是对代数方程 要求其精确解也是困难的 对于二次方程ax2 bx c 0 我们可以用熟悉的求根公式 对于三 四次代数方程 尽管存在求解公式 但并不实用 而对于大于等于五次的代数方程 它的根不能用方程系数的解析式表示 至于一般的超越方程 更没有求根公式 因此 为求解一个非线性方程 我们必须依靠某种数值方法来求其近似解 对于方程 2 1 要求得其准确解一般来说是不可能的 求方程根的近似解 一般有下列几个问题 3 根的精确化 已知一个根的粗略近似值后 建立计算方法将近似解逐步精确化 直到满足给定精度为止 设函数f x 在区间 a b 上连续 严格单调 且f a f b 0 则在 a b 内方程f x 0有且仅有一个实根 根据此结论 我们可以采用如下两种方法求出根的隔离区间 1 根的存在性 方程是否有根 如果有根 有几个根 2 根的隔离 确定根所在的区间 使方程在这个小区间内有且仅有一个根 这一过程称为根的隔离 完成根的隔离 就可得到方程的各个根的近似值 关于根的存在性是纯数学问题 不详细介绍 可查阅有关代数学内容 根的隔离主要依据如下结论 求根的隔离区间的两种方法 1 描图法 画出y f x 的草图 由f x 与x轴交点的大概位置来确定有根区间 也可利用导函数f x 的正 负与函数f x 的单调性的关系来确定根的大概位置 例1求f x 3x 1 cosx 0的有根区间 解 将方程变形为3x 1 cosx绘出曲线y 3x 1及y cosx 由图8 1可知 方程只有一个实根 例2 紧接下屏 2 逐步搜索法 从区间 a b 的左端点a出发 按选定的步长h一步步向右搜索 若 则区间 a jh a j 1 h 内必有根 搜索过程也可以从b开始 这时应取步长h 0 求出根的隔离区间后 就可采用适当的方法 使其进一步精确化 解 令f x 4x3 12x2 0 可得驻点x1 0 x2 3 由此而得到三个区间 0 0 3 3 f x 在此三个区间上的正负号分别为 由此可见 函数f x 在此三个区间上为 减 减 增 并且因为f 0 f 0 1 0 f 3 260所以仅有二个实根 分别位于 0 3 3 内 又因f 4 1 0 所以 二个隔根区间确定为 0 3 3 4 1对分法 设f x 在区间 a b 上连续 严格单调 且f a f b 0 则方程f x 0在 a b 内存在唯一实根 对分法的基本思想是 用对分区间的方法 通过判别函数f x 在每个对分区间中点的符号 逐步将有根区间缩小 最终求得一个具有相当精确程度的近似根 具体步骤为 若每次对分区间时所取区间中点都不是根 则上述过程将无限地进行下去 当n 时 区间将最终收缩为一点x 显然x 就是所求方程的根 对分法的误差估计 作为x 的近似值 则误差为 只要n足够大 即区间对分次数足够多 xn的误差就可足够小 且只要f x 连续 对分区间总是收敛的 式 8 2 不仅可以估计对分区间法的误差 而且可以给定的误差限 估计出对分区间的次数 因为由式 2 2 有 若取区间 an bn 的中点 例3 解 因为f x 连续且f x 3x2 10 0 x 故f x 在 上单调增加而f 1 90所以原方程在 1 2 内有唯一实根 f x 3 10 x 20 f x 3 10 x 20 double solve f ans 1 5946 0 7973 3 4506i 0 7973 3 4506i 对分法的优缺点 对分法的优点是计算简单 方法可靠 容易估计误差 但它收敛较慢 不能求偶次重根 也不能求复根 因此 一般在求方程近似根时 很少单独使用 常用于为其他高速收敛算法 如牛顿法 提供初值 2简单迭代法 迭代法是求解方程f x 0的根的一种主要方法 它是利用同一个迭代公式 逐次逼近方程的根 使其得到满足预先给定精度要求的近似值 2 1迭代法的基本思想 迭代法是一种重要的逐次逼近法 其基本思想是 设方程f x 0在区间 a b 内有一根x 将方程化为等价方程x x 并在 a b 内任取一点x0作为初始近似值 然后按迭代公式计第二章非线性方程求解算 产生迭代序列x0 x1 xn 显然 若 xn 收敛于x x 在x 处连续 就有 这种求根方法称为迭代法 式 2 3 称为迭代格式 x 称为迭代函数 x0称为迭代初值 xn 称为迭代序列如果迭代序列收敛 则称迭代格式 2 3 收敛 否则称为发散 即 x 是方程f x 0的解 故 当n充分大时 可取xn作为方程的近似解 满足x x 的点x也称为不动点 例4 解 容易验证 方程在 1 2 内有根 取x0 1 5 迭代法举例续 例5 解 对方程进行变换 可得如下三种等价形式 分别按以上三种形式建立迭代格式 并取x0 1进行迭代计算 结果如下 例5的计算结果表明 将一方程化为等价方程的方法很多 由此可构造许多不同的迭代函数 得到多种迭代格式 而它们所产生的迭代序列则可能收敛 也可能发散 可能收敛很快 也可能收敛很慢 迭代法的收敛性取决于迭代函数在方程的根的邻近的性态 迭代法的几何含义 从几何上看 迭代法是将求曲线y f x 的零点问题化为求曲线y x 与直线y x的交点 迭代过程如图2 2所示 从初始点x0出发 沿直线x x0走到曲线y x 得点 x0 x0 再沿直线y x0 走到直线y x 交点为 x1 x1 如此继续下去 越来越接近点 x x 当然 迭代过程也可能出现图8 3所示的情况 此时点 xn xn 越来越远离交点 x x 迭代序列发散 由此可见 使用迭代法必须解决两个问题 一是迭代格式满足什么条件才能保证收敛 二是如何判别迭代收敛的速度 建立收敛快的迭代格式 迭代法的几何含义 续 压缩映象原理的证明 由条件 2 易得 x 在 a b 上连续 令 x x x 则 x 也在 a b 上连续 且 由连续函数介值定理 存在 a b 使得 0 即 所以方程x x 在 a b 内有根 假设方程x x 在 a b 内有两个根x1 x2 由条件 2 有 导出矛盾 唯一性得证 存在性 唯一性 2 2迭代法的收敛条件 三大定理 定理2 6 压缩映象原理 设函数 x 在区间 a b 上满足条件 则方程x x 在 a b 内有唯一的根x 且对任意初值x0 a b 迭代序列 证明见下屏 压缩映象原理的证明 由条件 2 易得 x 在 a b 上连续 令 x x x 则 x 也在 a b 上连续 且 由连续函数介值定理 存在 a b 使得 0 即 所以方程x x 在 a b 内有根 假设方程x x 在 a b 内有两个根x1 x2 由条件 2 有 导出矛盾 唯一性得证 存在性 唯一性 对任意的x0 a b 由迭代公式有 即对任意初值x0 a b 迭代序列 xn 均收敛到方程的根x 压缩映象原理的证明 续1 收敛性 压缩映象原理的证明 由条件 2 易得 x 在 a b 上连续 令 x x x 则 x 也在 a b 上连续 且 由连续函数介值定理 存在 a b 使得 0 即 所以方程x x 在 a b 内有根 假设方程x x 在 a b 内有两个根x1 x2 由条件 2 有 导出矛盾 唯一性得证 存在性 唯一性 类似地 对任意正整数K 有 定理2 6证明中的两个误差估计式 2 5 2 6 是很有意义的 误差估计公式 利用 两个重要误差公式说明 1 式 2 5 说明 在正常情况下 即L不太接近于1 若L接近于1 则收敛速度很慢 可用相邻两次迭代值之差的绝对值来估计误差 控制迭代次数 就停止计算 取xn作为方程的近似根 这种用相邻两次计算结果来估计误差的方法 称为事后估计法 即当给定精度 时 如果有 2 而式 2 6 的误差估计 称为事前估计法 因为用它可以估计出要达到给定精度 所需次数n 事实上 由 注意 定理2 6给出了判别迭代收敛的充分条件 在实际计算时 由于L比较难求 而我们所讨论的函数通常是可导函数 因此 实用的收敛条件是用导数的界得到的 见下屏 迭代法的收敛条件之二 推论1 1 对任意的x a b 有 x a b 2 存在常数0 L 1 使得对任意x a b 都有 则方程x x 在 a b 上有唯一的根x 且对任意初值x0 a b 迭代序列 均收敛于x 并有 证明见下屏 设函数 x 在区间 a b 上满足条件 证明 设x y为 a b 上的任意两点 由微分中值定理 在x y之间至少存在一点 使得 于是 即 x 满足定理2 6的条件 2 故结论成立 推论1应用举例 采用的三种迭代格式 在隔根区间 1 1 2 内有 用推论1判别简单迭代法的收敛性比定理2 6方便 如对例题5 第一种迭代格式发散 第二 三种迭代格式收敛且第三种迭代格式比第二种迭代格式中的L要小 因而收敛要快得多 这与实际迭代结果完全吻合 故可取n 7 只需迭代7次就可达到所要求的精度 根据推论1可知 对第三种迭代格式 为使与方程近似根的误差不超过10 6 可估计迭代次数 应用举例 Leonardo于1225年研究了方程 曾经轰动一时 因为没有人知道他用的是什么方法 我们现在可用迭代法求解 还可用Newton法 弦截法求解 迭代法的收敛条件之三 定理2 7 定理2 3强调迭代初值x0应取在根x 的邻域中 如果对任意给定的x0 迭代格式均收敛 则称此格式具有全局收敛性 但这样的格式是极其稀少的 如果对根x 的某邻域内的任一点x0 迭代格式均收敛 则此格式具有局部收敛性 即可保证对其中任取的一点x0迭代收敛 事实上 在用迭代法求解方程 2 1 时 常常先用对分区间求得较好的初值 然后再进行迭代 本定理给出的就是局部收敛性条件 具体解题时 虽然无法判别隔根区间是否为以x 为中心的邻域 但只要它足够小 且在邻域中满足 2 3Steffensen方程 简单迭代法的加速 收敛速度 收敛速度的阶 成立 则称 xn 是r阶收敛的 或称 xn 的收敛阶为r 收敛阶r的大小刻划了序列 xn 的收敛速度 r越大 收敛越快 r 1线性收敛r 1超线性收敛r 2平方收敛 设序列 xn 收敛于x 若存在正数r和a使得 xn 的r阶收敛定理 定理2 8 设迭代函数 x 在x 邻近有r阶连续导数 且x x 并且有 证明 1 x 满足收敛定理的条件 xn x 紧接下屏 2 利用Taylor公式将 x 在x 附近展开 这表明 xn 是r阶收敛的 一阶收敛即为线性收敛 收敛速度较慢 下面想法加速 1 Aitken加速法 若序列 xn 线性收敛于x 可按式 当n充分大时 有 紧接下屏 Aitken加速法 续 由此式可推导出 由此可得比值 3Newton法与弦截法 3 1Newton法 将非线性方程线性化 以线性方程的解逐步逼近非线性方程的解 这就是Newton法的基本思想 设已知方程f x 0的近似根x0 f x 在其零点x 邻近一阶连续可微 且f x 0 当x0充分接近x 时 f x 可用Taylor公式近似表示为 则方程f x 0可用线性方程近似代替 即 Newton法 续 解此线性方程得 取此x作为原方程的新近似值x1 重复以上步骤 于是得迭代公式 按式 2 7 求方程f x 0近似解称为Newton法 Newton法的几何意义 如此继续下去 xn 1为曲线上点 xn f xn 处的切线与x轴的交点 因此Newton法是用曲线的切线与x轴的交点作为曲线与x轴交点的近似 故Newton法又称为切线法 Newton迭代法有着明显的几何意义如图3 4所示 过点 x0 f x0 作曲线y f x 的切线 切线方程为 y f x0 f x x x0 该切线与x轴的交点的横坐标即为新的近似值x1 而x2则是曲线上点 x1 f x1 处的切线与x轴的交点 Newton法举例 例7 解 因为f x 3x2 10 故Newton迭代公式为 x1 1 5970149 x2 1 5945637 x3 1 5945621 x4迭代三次所得近似解就准确到8位有效数字 代入初值x0得 可见Newton法收敛很快 一般地 有如下屏定理3 5 Newton法收敛定理 定理3 5 设函数f x 在其零点x 邻近二阶连续可微 且f x 0 则存在 0 使得对任意x0 x x Newton法所产生的序列 xn 至少二阶收敛于x 按式 2 7 Newton法的迭代函数为 于是有 证明 由已知f x 在x 邻近连续 因而 x 在x 邻近连续 且 根据定理2 4 Newton法产生的序列 xn 至少二阶收敛于x 定理3 5表明 当初值x0充分接近x 时 Newton法的收敛速度较快 但当初值不够好时 可能会不收敛或收敛于别的根 这可从Newton法的几何意义看到 紧接下屏 定理 在Newton法中 我们为了保证方法收敛 由局部收敛性可知 初始值尽量靠近所求根 但这是一个不易办到的事 如果函数f x 具有更强的性质 则初始值的取法较随便一些 2 分别不变号 使 则Newton迭代法产生的数列 收敛到方程f x 0 3 取初值 上具有二阶连续导数且满足条件 1 唯一的根 Newton法的几何意义及其优劣 如图3 5 a 所示 应用中可由实际问题的背景来预测利用对分区间法求得较好的初值x0 使在其邻近f x f x 不变号 并且使f x0 f x0 0 这就能保证收敛 如图3 5 b d Newton法具有收敛快 稳定性好 精度高等优点 它是求解非线性方程的有效方法之一 但它每次迭代均需要计算函数值与导数值 故计算量较大 而且当导数值提供有困难时 Newton法无法进行 例 用Newton迭代法于方程导出的迭代公式 并用此求的值 3 2计算重根的牛顿迭代法 若x 为方程f x 0的m m 1 重根 则f x 可表为 其中g x 0 此时用牛顿迭代法求x 仍然收敛 只是收敛速度将大大减慢 事实上 因为 计算重根的牛顿迭代法 续1 可见用牛顿法求方程的重根仅为线性收敛 为了提高求重根的收敛速度 有两种可供选择方法 1 方法之一是将求重根的问题转化为求单根 注意到函数 计算重根的牛顿迭代法 续2 上述迭代格式右端较复杂 应用起来不方便 2 另一种求m重根的方法是采用如下迭代格式 可以证明它是求m重根x