第七章非线性方程与方程组的数值解法-1课件

1第第7 7章章 非线性方程与方程组的非线性方程与方程组的数值解法数值解法27.1 7.1 方程求根与二分法方程求根与二分法7.2 7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性7.37.3 迭代法收敛的加速方法迭代法收敛的加速方法7.4 7.4 NewtonNewton法法7.5 7.5 弦截法与抛物线法弦截法与抛物线法7.6 7.6 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点7.7 7.7 非线性方程组的数值解法非线性方程组的数值解法3 7.1 7.1 方程求根与二分法方程求根与二分法 7.1.1 7.1.1 引言引言（1.1）本章主要讨论单变量非线性方程 的求根问题，这里 一类特殊的问题是多项式方程（1.2）的求根问题，其中系数 为实数.4 方程 的根 ，又称为函数 的零点，它使 ，若 可分解为 其中 为正整数，且 当 时，称 为单根，若 称 为（1.1）的 重根，或 为 的 重零点.若 是 的 重零点，且 充分光滑，则 当 为代数多项式（1.2）时，根据代数基本定理可知，次方程在复数域有且只有 个根（含复根，重根为 个根）.时方程的根是大家熟悉的，时虽有求5根公式但比较复杂，可在数学手册中查到，但已不适合于数值计算，而 时就不能用公式表示方程的根.通常对 的多项式方程求根与一般连续函数方程（1.1）一样都可采用迭代法.迭代法要求先给出根 的一个近似，若 且 ，根据连续函数性质可知 在 内至少有一个实根，这时称 为方程（1.1）的有根区间.通常可通过逐次搜索法求得方程（1.1）的有根区间.例例1 1 求方程 的有根区间.解 根据有根区间定义，对 的根进行搜索计算，结果如下：6由此可知方程的有根区间为 7 7.1.2 7.1.2 二分法二分法 考察有根区间 ，取中点 将它分为两半，假设中点 不是 的零点，然后进行根的搜索.检查 与 是否同号，如果确系同号，说明所求的根 在 的右侧,这时令 ；否则 必在 的左侧，这时令 .见图7-1.图7-18 不管出现哪一种情况，新的有根区间 的长度仅为 的一半.对压缩了的有根区间 又可施行同样的手续，即用中点 将区间 再分为两半，然后通过根的搜索判定所求的根在 的哪一侧，从而又确定一个新的有根区间 ，其长度是 的一半.如此反复二分下去，即可得出一系列有根区间 其中每个区间都是前一个区间的一半，因此 的长度 当 时趋于零，就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点 ，该点显然就是所求的根.9 每次二分后，设取有根区间 的中点 作为根的近似值，则在二分过程中可以获得一个近似根的序列 该序列必以根 为极限.由于（1.3）只要二分足够多次（即 充分大），便有 这里 为预定的精度.10 例例2 2 求方程 在区间 内的一个实根，要求准确到小数点后第2位.解解 这里 ，而 取 的中点 ，将区间二等分，由于 ，即 与 同号，故所求的根 必在 右侧，这时应令 ，而得到新的有根区间 如此反复二分下去,按误差估计（1.3）式,欲使11只需 ，即只要二分6次，便能达到预定的精度.计算结果如表7-1.12 二分法是计算机上的一种常用算法，计算步骤为：步骤步骤1 1 准备准备 计算 在有根区间 端点处的值 步骤步骤2 2 二分二分 计算 在区间中点 处的值 步骤步骤3 3 判断判断 若 ，则 即是根，计算过程结束，否则检验.若 ，则以 代替 ，否则以 代替 .反复执行步骤2和步骤3，直到区间 长度小于13允许误差 ，此时中点 即为所求近似根.147.2 7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性7.2.1 7.2.1 不动点迭代法不动点迭代法 将方程（1.1）改写成等价的形式（2.1）若要求 满足 ，则 ；反之亦然，称 为函数 的一个不动点.求 的零点就等价于求 的不动点，选择一个初始近似值 ，将它代入(2.1)右端，即可求得 如此反复迭代计算（2.2）15 称为迭代函数.如果对任何 ，由（2.2）得到的序列 有极限 则称迭代方程(2.2)收敛，且 为 的不动点，故称（2.2）为不动点迭代法不动点迭代法.上述迭代法是一种逐次逼近法，其基本思想是将隐式方程（2.1）归结为一组显式的计算公式（2.2），就是说，迭代过程实质上是一个逐步显示化的过程.方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 对于 的某个近似值 ，在曲线 上可确定一点 ，它以 为横坐标，而纵坐标则等于 16过 引平行 轴的直线，设此直线交直线 于点 ，然后过 再作平行于 轴的直线，它与曲线 的交点记作 ，则点 的横坐标为 ，纵坐标则等于图7-217 例例3 3 求方程（2.3）在 附近的根 解解 设将方程（2.3）改写成下列形式 按图7-2中箭头所示的路径继续做下去，在曲线 上得到点列 ，其横坐标分别为依公式 求得的迭代值 如果点列 趋向于点 ，则相应的迭代值 收敛到所求的根 据此建立迭代公式 18各步迭代的结果见表7-2.如果仅取6位数字，那么结果 与 完全相同，这时可以认为 实际上已满足方程(2.3)，即为所求的根.19但若采用方程（2.3）的另一种等价形式建立迭代公式 仍取迭代初值 ，则有 结果会越来越大，不可能趋于某个极限.这种不收敛的迭代过程称作是发散发散的.一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.20 7.2.2 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察 在 上不动点的存在唯一性.定理定理1 1 设 满足以下两个条件：1 对任意 有 2 存在正常数 ，使对任意 都有（2.4）则 在 上存在唯一的不动点 证明证明 先证不动点存在性.若 或 ，显然 在 上存在不动点.因 ，以下设 及 ，定21义函数显然 ，且满足 ，由连续函数性质可知存在 使 ，即 即为 的不动点.再证唯一性.设 都是 的不动点，则由(2.4)得 引出矛盾.故 的不动点只能是唯一的.证毕.22 定理定理2 2 设 满足定理1中的两个条件，则对任意 ，由（2.2）得到的迭代序列 收敛到 的不动点 ，并有误差估计（2.5）证明证明 设 是 在 上的唯一不动点，由条件1，可知 ，再由（2.4）得 因 ，故当 时序列 收敛到 .再证明估计式（2.5），由（2.4）有（2.6）23反复递推得 于是对任意正整数 有在上式令 ，注意到 即得式（2.5）.证毕.迭代过程是个极限过程.在用迭代法实际计算时，必须按精度要求控制迭代次数.24 误差估计式（2.5）原则上可用于确定迭代次数，但它由于含有信息 而不便于实际应用.根据式（2.6），对任意正整数 有 在上式中令 知 由此可见，只要相邻两次计算结果的偏差 足够小即可保证近似值 具有足够精度.对定理1和定理2中的条件2，在使用时如果 且对任意 有 25（2.7）则由中值定理可知对 有 表明定理中的条件2可用（2.7）代替.例3中，当 时，,在区间 中，故（2.7）成立.又因 ，故定理1中条件1也成立.所以迭代法是收敛的.而当 时，在区间 中 不满足定理条件.26 7.2.3 7.2.3 局部收敛性与收敛阶局部收敛性与收敛阶 上面给出了迭代序列 在区间 上的收敛性，通常称为全局收敛性.定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性.定义定义1 1 设 有不动点 ，如果存在 的某个邻域 ，对任意 ，迭代（2.2）产生的序列 ，且收敛到 ，则称迭代法（2.2）局部收敛局部收敛.定理定理3 3 设 为 的不动点，在 的某个邻域连续，且 ，则迭代法（2.2）局部收敛.证明证明 由连续函数的性质，存在 的某个邻域 ，使对于任意 成立 27此外，对于任意 ，总有 ，这是因为 于是依据定理2可以断定迭代过程 对于任意初值 均收敛.证毕.讨论迭代序列的收敛速度.例例4 4 用不同方法求方程 的根 解解 这里 ，可改写为各种不同的等价形式 ，其不动点为 由此构造不同的迭代法：28取 ，对上述4种迭代法，计算三步所得的结果如下表.29 注意 ，从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件，迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 .30 定义定义2 2 设迭代过程 收敛于方程 的根 ，如果迭代误差 当 时成立下列渐近关系式 则称该迭代过程是 阶收敛阶收敛的.特别地,时称线性收线性收敛敛，时称超线性收敛超线性收敛，时称平方收敛平方收敛.定理定理4 4 对于迭代过程 ，如果 在所求根 的邻近连续，并且（2.8）则该迭代过程在点 邻近是 阶收敛的.31 证明证明 由于 ，据定理3立即可以断定迭代过程 具有局部收敛性.再将 在根 处做泰勒展开，利用条件（2.8），则有 注意到 ，由上式得 因此对迭代误差，当 时有（2.9）这表明迭代过程 确实为 阶收敛.证毕.32 上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取.如果当 时 ，则该迭代过程只可能是线性收敛.在例4中，迭代法（3）的 ，故它只是线性收敛，而迭代法（4）的 ，而 由定理4知 ，即该迭代过程为2阶收敛.337.3 7.3 迭代收敛的加速方法迭代收敛的加速方法7.3.1 Aitken7.3.1 Aitken加速收敛方法加速收敛方法 设 是根 的某个近似值，用迭代公式校正一次得 由微分中值定理，有 其中 介于 与 之间.假定 改变不大，近似地取某个近似值 ，则有（3.1）若将校正值 再校正一次，又得 34由于 将它与（3.1）式联立，消去未知的 ，有 由此推知 在计算了 及 之后，可用上式右端作为 的新近似，记作 .35 一般情形是由 计算 ，记（3.2）(3.2)称为埃特金（Aitken）加速方法.可以证明 它表明序列 的收敛速度比 的收敛速度快.367.3.2 Steffensen7.3.2 Steffensen迭代法迭代法 埃特金方法不管原序列 是怎样产生的，对 进行加速计算，得到序列 .如果把埃特金加速技巧与不动点迭代结合，则可得到如下的迭代法：（3.3）称为斯蒂芬森(Steffensen)迭代法.它的理解为，要求 的根 ，令 ，已知 的近似值 及 ，其误差分别为 37 过 及 两点做线性插值函数，它与 轴交点就是（3.3）中的 ，即方程 的解 实际上（3.3）是将不动点迭代法（2.2）计算两步合并成一步得到的，可将它写成另一种不动点迭代（3.4）38其中（3.5）定理定理5 5 若 为（3.5）定义的迭代函数 的不动点，则 为 的不动点.反之，若 为 的不动点，设 存在，则 是 的不动点，且斯蒂芬森迭代法（3.3）是2阶收敛的.解解 例3中已指出,下列迭代 是发散的，现用(3.3)计算，取 ，计算结果如下表.例例5 5 用斯蒂芬森迭代法求解方程 39 计算表明它是收敛的，这说明即使迭代法（2.2）不收敛，用斯蒂芬森迭代法（3.3）仍可能收敛.至于原来已收敛的迭代法（2.2），由定理5可知它可达到2阶收敛.更进一步还可知若（2.2）为 阶收敛，则（3.3）为 阶收敛.40 例例6 6 求方程 在 中的解.解解 由方程得 ，取对数得 若构造迭代法 由于 ,且当 时，根据定理2此迭代法是收敛的.若取 迭代16次得 ，有六位有效数字.若用（3.3）进行加速，计算结果如下：p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日