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