【教学课件】第七章非线性方程求根

《【教学课件】第七章非线性方程求根》由会员分享，可在线阅读，更多相关《【教学课件】第七章非线性方程求根（50页珍藏版）》请在金锄头文库上搜索。

1、第七章第七章 非线性方程求根非线性方程求根7.1 方程求根与二分法7.2 迭代法及其收敛性7.3 迭代法收敛的加速方法7.4 牛顿法7.5 弦截法与抛物线法7.6 解非线性方程组的牛顿迭代法 本章讨论非线性方程 的求根问题，其中一类特殊的问题就是多项式方程的求根。方程 的根 又称为 的零点，它使若 可表示为 ，其中 为正整数，且 。当 时，称 为单根，若 称 为 重根，或 的 重零点。若 是 的 重零点，且 充分光滑，则7.1 方程求根与二分法方程求根与二分法 当 为代数多项式时，根据代数基本定理可知，次方程在复数域有且只有 个根，因此可利用迭代法求代数方程的根。n二分法 若 ，且 ，根据连续

2、函数性质可知 在 内至少有一个实根，此时称 为方程若 可表示为 ，其中 为正整数，且 。当 时，称 为单根，若 称 为 重根，或 的 重零点。若 是 的 重零点，且 充分光滑，则7.1 方程求根与二分法方程求根与二分法7.1 方程求根与二分法方程求根与二分法 当 为代数多项式时，根据代数基本定理可知，次方程在复数域有且只有 个根，因此可利用迭代法求代数方程的根。n二分法 若 ，且 ，根据连续函数性质可知 在 内至少有一个实根，此时称 为方程的有根区间。例：求方程 的有根区间。解：通过计算部分点的函数值，得到如下结果：由此得到方程的有根区间为：。0123456 的符号7.1 方程求根与二分法方程

3、求根与二分法n二分算法 设已找到有根区间 ，满足 ，且在 上只有一个零点，步骤如下：(1)先设 对于一般的区间 ，设其中点为：(2)检验 的符号，若与 同号，就取 ，的有根区间。例：求方程 的有根区间。解：通过计算部分点的函数值，得到如下结果：由此得到方程的有根区间为：。0123456 的符号7.1 方程求根与二分法方程求根与二分法n二分算法 设已找到有根区间 ，满足 ，且在 上只有一个零点，步骤如下：(1)先设 对于一般的区间 ，设其中点为：(2)检验 的符号，若与 同号，就取 ，否则取 这样必有所以 就是新的有根区间，继续此过程，即可得到结果。算法：(1)令(2)若 或 ，则输出 ，结束(

4、3)若 ，则令 ，否则令(4)转向1)7.1 方程求根与二分法方程求根与二分法 这样，我们得到了一个序列 ，为确定 的收敛性我们有如下的定理：定理：设 则二分算法产生的序列 满足 其中 为方程的根。证明：因为 由 对分得到，所以对 否则取 这样必有所以 就是新的有根区间，继续此过程，即可得到结果。算法：(1)令(2)若 或 ，则输出 ，结束(3)若 ，则令 ，否则令(4)转向1)7.1 方程求根与二分法方程求根与二分法 这样，我们得到了一个序列 ，为确定 的收敛性我们有如下的定理：定理：设 则二分算法产生的序列 满足 其中 为方程的根。证明：因为 由 对分得到，所以对区间长度而 ，且 ，所以故

5、当 时，且有误差估计式7.1 方程求根与二分法方程求根与二分法例：已知 在 有一个零点，用二分法计算的结果如下：区间长度而 ，且 ，所以故当 时，且有误差估计式7.1 方程求根与二分法方程求根与二分法例：已知 在 有一个零点，用二分法计算的结果如下：n有根区间11.0,2.01.52.37521.0,1.51.25-1.7968731.25,1.51.3750.1621141.25,1.3751.3125-0.8483951.3125,1.3751.34375-0.3509861.34375,1.3751.359375-0.0964171.359375,1.3751.36718750.0323

6、681.359375,1.3671875 1.36328125-0.032157.1 方程求根与二分法方程求根与二分法 ，另外，如果要求 ，可以从令 ，可得 ，即计算17次即可。7.2 迭代法及其收敛性迭代法及其收敛性n不动点迭代法 将方程 改写成等价的形式 ，则的根 也满足方程 ，反之亦然。称 为 的不动点。而求 的根的问题就成为求 的不动点问题。选取初值 ，以公式 进行迭代，称为迭代函数，若 收敛到 ，则 就是 的不动点，这种方法就称为不动点迭代法。将 转化为 的方法可以是多种多样的，例：在 上可有以下方法：(1)(2)(3)(4)取 ，有的收敛，有的发散，有的快，有的慢。7.2 迭代法及

7、其收敛性迭代法及其收敛性n迭代过程的几何表示 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 ，对于 的某个近似值 ，在曲线 上可确定一点 ，它的横坐标为而纵坐标为 ，过 引 轴的平行线，交 于迭代函数，若 收敛到 ，则 就是 的不动点，这种方法就称为不动点迭代法。将 转化为 的方法可以是多种多样的，例：在 上可有以下方法：(1)(2)(3)(4)取 ，有的收敛，有的发散，有的快，有的慢。7.2 迭代法及其收敛性迭代法及其收敛性n迭代过程的几何表示 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 ，对于 的某个近似值 ，在曲线 上可确定一点 ，它的横坐标为而纵坐标为 ，过

8、引 轴的平行线，交 于 ，然后过 再作 轴的平行线，它与 的交点记作 ，则 的横坐标为 ，而纵坐标为 ，按图中箭头所示路经继续做下去，在曲线上得到点列 其横坐标分别为按公式 求得的迭代值 如果点列 趋向于点 ，则相应的迭代值 收敛到所求的根 。7.2 迭代法及其收敛性迭代法及其收敛性7.2 迭代法及其收敛性迭代法及其收敛性 例3：求方程 在 附近的根 。解：将方程改写为 ，由此建立迭代公式：计算结果如下表：这是一个收敛的例子，也有不收敛的迭代公式，如我们对于同样的问题，如果将方程改写为令一种迭代公式 ，仍取初值 ，则迭代发散。为此，我们要研究 存在性及迭代法的收敛性。0123456781.5

9、1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 1.324727.2 迭代法及其收敛性迭代法及其收敛性 定理1：(存在性)设 满足以下两个条件：(1)对任意的 ，有(2)存在 ，使对任意 都有则 在 上存在唯一的不动点 。证明：先证不动点的存在性。若 或 ，则 或 就是不动点。因此由 可设 及 ，定义函数 ，显然 且满足 由函数的连续性可知存在 使 ，即 ，即为 的不动点。7.2 迭代法及其收敛性迭代法及其收敛性再证唯一性。设 及 都是 的不动点，则由定理的条件(2)，得到矛盾，故 的不动点是唯一的。证毕。定理2：(收敛的充分条件

10、)设 满足定理1的两个条件，则对任意 ，由 得到的迭代序列 收敛到 的不动点 ，并有误差估计证明：设 是 在 上的唯一不动点，由条件1可知 ，再由条件2得因 ，故当 时，序列 收敛到 。7.2 迭代法及其收敛性迭代法及其收敛性由迭代公式可得据此反复递推，得到于是对任意正整数 ，有在上式令 ，注意到 即得到结果。证毕。7.2 迭代法及其收敛性迭代法及其收敛性 根据定理2的结论，对于给定的计算精度，迭代次数是可以预先确定的，但由于公式中含有常数 ，使得计算迭代次数较为复杂，根据估计式我们得到：令 ，得到由此可知，只要相邻两次计算结果的偏差 足够小即可保证近似值 有足够的精度。7.2 迭代法及其收敛

11、性迭代法及其收敛性 对于定理中的条件2，在实际使用时，如果 且对任意的 有则由中值定理可知 有它表明定理中条件2可由 替代。7.2 迭代法及其收敛性迭代法及其收敛性n局部收敛性 前面讨论的收敛性称为全局收敛性，现在我们讨论局部收敛性。定义1：设 有不动点 ，如果存在 的某个领域 ，对任意 ，迭代公式 产生的序列 且收敛到 ，则称该迭代法局部收敛。定理3：设 为 的不动点，在 的某个领域连续，且 ，则迭代法 收敛。证明：由连续函数的性质，存在 的某个领域 ，使对任意 成立 ，此外，对于任意 ，总有 ，这是因为于是依据定理2可断定迭代过程对于任意的初值收敛7.2 迭代法及其收敛性迭代法及其收敛性n

12、关于收敛速度问题的例 用不同的方法求方程 的根 。解：这里 ，可改写为各种不同的等价形式：(1)(2)(3)(4)取 ，对上述4种迭代法，计算三步所得结果如下7.2 迭代法及其收敛性迭代法及其收敛性注意 ，从计算结果看到迭代法(1)和(2)均不收敛，且它们均不满足定理3种的局部收敛条件迭代法(3)和(4)均满足局部收敛条件，且(4)比(3)快，这是因为(4)的 。为了衡量收敛速度，可以给出如下的定义。方法1方法2方法3方法402222131.51.751.752921.734751.7321433871.51.7323611.7320517.2 迭代法及其收敛性迭代法及其收敛性 定义2 设迭代

13、过程 收敛于方程 的根 ，如果迭代误差 当 时成立下列渐进关系式则称该迭代过程是 阶收敛的，特别地，时称线性收敛，时称超线性收敛，时称平方收敛。定理4 对于迭代过程 ，如果 在所求根 的邻近连续，并且 (*)则该迭代过程在点 邻近是 阶收敛的。证明：由于 ，据定理3立即可以断定迭代过程 具有局部收敛性。再将 在根 处做泰勒展开，利用条件(*)，得到7.2 迭代法及其收敛性迭代法及其收敛性 在 与 之间，注意到 由上式得到因此对迭代误差，当 时有这表明迭代过程 确实为 阶收敛。证毕。定理说明，迭代过程的收敛速度依赖于迭代函数的选取，如果 ，则迭代过程只可能时线性收敛。在例4中，迭代法(3)的 ，

14、故它只是线性收敛，迭代法(4)的 ，但 ，故为2阶。7.3 迭代法收敛的加速方法迭代法收敛的加速方法n埃特金加速收敛方法 有的迭代过程虽然收敛，但速度很慢，因此迭代过程的加速是一个重要课题。设 是根 的某个近似值，用迭代公式校正一次得 ，而有微分中值定理，有其中 介于 与 之间。假设 改变不大，近似地取某个近似 ，则有若将校正值 再校正一次，又得 ，由于 在两式中消去 ，得到 ，由此推得：7.3 迭代法收敛的加速方法迭代法收敛的加速方法在计算了 及 之后，可用上式右端作为 的新近似，记作 ，一般情形是由 计算 ，记该方法称为埃特金加速方法。可以证明：它表明序列 的收敛速度比 的收敛速度快。7.

15、3 迭代法收敛的加速方法迭代法收敛的加速方法n斯蒂芬森迭代法 埃特金方法不管原序列 是怎样产生的，对 进行加速计算，得到序列 ，如果把埃特金加速技巧与不动点迭代结合，则得到如下的迭代法：称为斯蒂芬森迭代法，它可以这样理解：我们要求 的根 ，令已知 的近似值 及 ，其误差分别为通过把误差外推到零，即过 及 两点做线性插值函数，它与 轴的交点就是迭代法的结果。7.3 迭代法收敛的加速方法迭代法收敛的加速方法即方程 的解：实际上就是将两个步骤合成一个步骤，如果把它看成一个不动点迭代 ，则 (*)关于上述不动点迭代法有以下的局部收敛性：定理5 若 为(*)定义的迭代函数 的不动点，则 为 的不动点。反

16、之，若 为 的不动点，设 存在，则 是 的不动点，且斯法是2阶的。7.3 迭代法收敛的加速方法迭代法收敛的加速方法 证明：设 是 的不动点，即 ，则有：即 ，所以 ，即 是 的不动点。反之，若 是 的不动点，且设 ，则故 与 有相同的不动点。现设 且 ，则此时，若 收敛，且只是一阶的，但 却可以是二阶的。7.3 迭代法收敛的加速方法迭代法收敛的加速方法因为：取 ，即有：故：回到一般的 ，即有：所以：即 具有二阶收敛性。证毕。7.3 迭代法收敛的加速方法迭代法收敛的加速方法 例5 用斯蒂芬森迭代法求解方程 。解：前面的例3中已经指出迭代格式 是发散的，现用斯蒂芬森迭代法，取 ，则有迭代公式：取 ，得到：书上的方法是通过 得到的，结果一致。特别注意：对于发散的算法 ，斯蒂芬森迭代法仍可能收敛。进一步还可证明斯蒂芬森迭代法的收敛阶可以高一阶。7.4 牛顿法牛顿法n牛顿法 对于方程 ，如果 是线性函数，则它的求根是容易的，牛顿法就是一种将非线性方程 逐步线性化的方法。设已知方程 有近似根 (假定 )，将函数 在点 展开，有 ，于是方程 可近似地表示为 ，这是一个线性方程，记其根为 ，则 的计算