第7章数值分析研究报告

《第7章数值分析研究报告》由会员分享，可在线阅读，更多相关《第7章数值分析研究报告（112页珍藏版）》请在金锄头文库上搜索。

1、1,第7章 非线性方程与方程组的数值解法,7.1 方程求根与二分法 7.2 不动点迭代法及其收敛性 7.3 迭代收敛的加速方法 7.4 牛顿法 7.5 弦截法与抛物线法 7.6 求根问题的敏感性与多项式的零点 7.7 非线性方程组的数值解法,2,7.1 方程求根与二分法,7.1.1 引言,（1.1）,本章主要讨论求解单变量非线性方程,其中 也可以是无穷区间.,如果实数 满足 ，则称 是方程(1.1)的 根，或称 是 的零点.,3,若 可分解为,其中 为正整数，且 则称 为方程(1.1)的 重根，或 为 的 重零点， 时为单根.,若 是 的 重零点，且 充分光滑，则,如果函数 是多项式函数，即,

2、（1.2）,其中 为实数，则称方程(1.1)为 次代数方程.,5,迭代法要求先给出根 的一个近似，若 且 ，根据连续函数性质可知 在 内至少有一个实根，这时称 为方程(1.1)的有根区间.,非线性问题一般不存在直接的求解公式，故没有直接 方法求解，都要使用迭代法.,通常可通过逐次搜索法求得方程 的有根区间.,6,例1 求方程 的有根区间.,解 根据有根区间定义，对 的根进行搜索计算，结果如下：,由此可知方程的有根区间为,7,检查 与 是否同号， 如果同号，说明所求的根 在 的右侧,这时令 否则 必在 的左侧， 这时令 见图7-1.,考察有根区间 ，取中点 将它分为 两半，,7.1.2 二分法,

3、假设中点 不是 的零点，然后进行根的搜索.,图7-1,不管出现哪一种情况，新的有根区间 的长度仅 为 的一半.,8,对压缩了的有根区间 又可施行同样的手续，即用 中点 将区间 再分为两半，然后通过根 的搜索判定所求的根在 的哪一侧，从而又确定一个新的 有根区间 ，其长度是 的一半.,如此反复二分下去，即可得出一系列有根区间,其中每个区间都是前一个区间的一半，因此 的长度,当 时趋于零.,9,就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点 ，该点显然就是所求的根.,作为根的近似，则在二分过程中可以获得一个近似根的序列,该序列必以根 为极限.,每次二分后，设取有根区间 的中点,10,

4、由于,只要二分足够多次（即 充分大），便有,这里 为预定的精度.,（1.3）,11,例2 求方程,在区间 内的一个实根，要求准确到小数点后第2位.,解 这里 ，而,取 的中点 ，将区间二等分，由于 ， 即 与 同号，故所求的根 必在 右侧，这时应令 ，而得到新的有根区间,如此反复二分下去, 按误差估计（1.3）式,欲使,只需 ，即只要二分6次，便能达到预定的精度.,12,计算结果如表7-2.,13,二分法是计算机上的一种常用算法，计算步骤为：,步骤1 准备 计算 在有根区间 端点处的值,步骤2 二分 计算 在区间中点 处的值,步骤3 判断 若 ，则 即是根， 计算过程结束，否则检验.,若 ，则

5、以 代替 ，否则以,代替 .,14,此时中点 即为所求近似根.,15,7.2 不动点迭代法及其收敛性,7.2.1 不动点与不动点迭代法,将方程（1.1）改写成等价的形式,（2.1）,若 满足 ，则 ；反之亦然，称 为函数 的一个不动点.,求 的零点就等价于求 的不动点.,选择一个初始近似值 ，将它代入(2.1)右端，即可求得,16,如此反复迭代计算,（2.2）,称为迭代函数.,如果对任何 ，由（2.2）得到的序列 有极限,则称迭代方程(2.2)收敛，且 为 的不动点， 故称（2.2）为不动点迭代法.,17,方程 的求根问题在 平面上就是要确定曲 线 与直线 的交点,对于 的某个近似值 ，在曲线

6、 上可确定 一点 ，它以 为横坐标，而纵坐标则等于,就是说，迭代过程实质上是一个逐步显示化的过程.,过 引平行 轴的直线，设此直线交直线 于点 ，,然后过 再作平行于 轴的直线，,与曲线 的交点,上述迭代法是一种逐次逼近法，其基本思想是将隐式 方程 归结为一组显式的计算公式 .,18,则点 的横坐标为 ，,图7-2,记作 ，,纵坐标则等于,按图7-2中箭头所示的路径继续做下去.,在曲线 上得到点列，,其横坐标分别为,19,例3 求方程,（2.3）,在 附近的根,解 设将方程（2.3）改写成下列形式,依公式 求得的迭代值,如果点列 趋向于点 ，则相应的迭代值 收敛 到所求的根,据此建立迭代公式,

7、20,各步迭代的结果见表7-3.,这时可以认为 实际上已满足方程(2.3)，即为所求的根.,如果仅取6位数字，那么结果 与 完全相同，,21,但若采用方程（2.3）的另一种等价形式,建立迭代公式,仍取迭代初值 ，则有,结果会越来越大，不可能趋于某个极限.,这种不收敛的迭代过程称作是发散的.如图7-3.,一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.,图7-3,22,7.2.2 不动点的存在性与迭代法的收敛性,首先考察 在 上不动点的存在唯一性.,定理1 设 满足以下两个条件：,1. 对任意 有,2. 存在正常数 ，使对任意 都有,（2.4）,则 在 上存在唯一的不动点,23,

8、因 ，,以下设 及 ，,若 或 ，则不动点为 或 ，,存在性得证.,定义函数,显然 ，,由连续函数性质可知存在 ,且满足,使 ,即,即为 的不动点.,证明 先证不动点存在性.,24,再证唯一性.,设 都是 的不动点，,引出矛盾.故 的不动点只能是唯一的.,则由(2.4)得,25,（2.5）,定理2 设 满足定理1中的两个条件，则 对任意 ，由（2.2）得到的迭代序列 收敛到 的不动点 ，并有误差估计,证明 设 是 在 上的唯一不动点， 由条件，可知 ，再由（2.4）得,因 ，故当 时序列 收敛到 .,26,再证明估计式（2.5），,由（2.4）有,（2.6）,反复递推得,于是对任意正整数 有,

9、27,在上式令 ，注意到 即得式（2.5）.,迭代过程是个极限过程.,在用迭代法实际计算时，必须按精度要求控制迭代次数.,原则上可以用误差估计式（2.5）确定迭代次数，但由 于它含有信息 而不便于实际应用.,根据式（2.6），对任意正整数 有,在上式中令 知,28,对定理1和定理2中的条件2，如果 且对任意 有,（2.7）,则由中值定理可知对 有,表明定理中的条件2可用（2.7）代替.,29,例3中，当 时， , 在区间 中， ，故（2.7）成立.,又因 ，故定理1中条件1也成立. 所以迭代法是收敛的.,而当 时， ，在区间 中 不满足定理条件.,30,7.2.3 局部收敛性与收敛阶,上面给出

10、了迭代序列 在区间 上的收敛性，,定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性.,定义1 设 有不动点 ，如果存在 的某个邻域 对任意 ，迭代（2.2）产生的序列 且收敛到 ，则称迭代法（2.2）局部收敛.,通常称为全局收敛性.,31,证明 由连续函数的性质，存在 的某个邻域 使对于任意 成立,定理3 设 为 的不动点， 在 的某个邻 域连续，且 ，则迭代法（2.2）局部收敛.,此外，,对于任意 ，,总有 ，,于是依据定理2可以断定迭代过程 对于任意 初值 均收敛.,这是因为,32,讨论迭代序列的收敛速度.,例4 用不同方法求方程 的根,解 这里 ，可改写

11、为各种不同的等价形式 其不动点为 由此构造不同的迭代法：,33,取 ，对上述4种迭代法，计算三步所得的结果如下表.,34,从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.,注意 .,迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 .,35,定义2 设迭代过程 收敛于方程 的根 ，如果迭代误差 当 时成立下列 渐近关系式,则称该迭代过程是 阶收敛的.,特别地, 时称线性收敛，,时称超线性收敛，,时称平方收敛.,36,定理4 对于迭代过程 ，如果 在所 求根 的邻近连续，并且,则该迭代过程在点 邻近是 阶收敛的.,（2.8

12、）,证明 由于 ，据定理3立即可以断定迭代 过程 具有局部收敛性.,再将 在根 处做泰勒展开，利用条件（2.8），,则有,37,注意到 ，,因此对迭代误差，,当 时有,（2.9）,这表明迭代过程 确实为 阶收敛.,由上式得,上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取.,如果当 时 ，则该迭代过程只可能是线性收敛.,38,在例4中，迭代法（3）的 ，故它只是线性 收敛.,而迭代法（4）的 ，而 由定理4知 ，该迭代过程为2阶收敛.,39,7.3 迭代收敛的加速方法,7.3.1 埃特金加速收敛方法,设 是根 的某个近似值，用迭代公式迭代一次得,由微分中值定理，有,其中 介于 与 之间.

13、,假定 改变不大，近似地取某个近似值 ，,（3.1）,则有,40,由于,将它与（3.1）式联立，消去未知的 ，,由此推知,在计算了 及 之后，可用上式右端作为 的新近 似，记作 .,若将校正值 再迭代一次，又得,有,41,一般情形是由 计算 ，,(3.2)称为埃特金（Aitken） 加速方法.,可以证明,它表明序列 的收敛速度比 的收敛速度快.,（3.2）,记,42,7.3.2 斯蒂芬森迭代法,埃特金方法不管原序列 是怎样产生的，对 进 行加速计算，得到序列 .,如果把埃特金加速技巧与不动点迭代结合，则可得到 如下的迭代法：,称为斯蒂芬森(Steffensen)迭代法.,（3.3）,43,它的

14、理解为，要求 的根 ，,已知 的近似值 及 ，其误差分别为,过 及 两点做线性插值函数.,它与 轴交点就是（3.3）中的 ，即方程,的解,令,44,实际上（3.3）是将不动点迭代法（2.2）计算两步合 并成一步得到的，可将它写成另一种不动点迭代,（3.4）,其中,（3.5）,45,定理5 若 为（3.5）定义的迭代函数 的不动点， 则 为 的不动点.反之，若 为 的不动点， 设 存在， ，则 是 的不动点， 且斯蒂芬森迭代法（3.3）是2阶收敛的.,解 例3中已指出, 下列迭代,是发散的，现用(3.3)计算，取 .,例5 用斯蒂芬森迭代法求解方程,计算结果如下表.,46,至于原来已收敛的迭代法

15、（2.2），由定理5可知它可达到2阶收敛.,计算表明它是收敛的，这说明即使迭代法（2.2）不收 敛，用斯蒂芬森迭代法（3.3）仍可能收敛.,47,例6 求方程 在 中的解.,解 由方程得等价形式 ，取对数得,由此构造迭代法,且当 时， ，,由于 ,根据定理2此迭代法是收敛的.,48,若取 迭代16次得 ，有六位有效数 字.,若用（3.3）进行加速，计算结果如下 ：,这里计算2步（相当于（2.2）迭代4步）结果与 相同，,说明用迭代法（3.3）的收敛速度比迭代法（2.2）快得多.,49,7.4 牛顿法,7.4.1 牛顿法及其收敛性,设已知方程 有近似根 （假定 )，,将函数 在点 展开，有,于是方程 可近似地表示为,（4.1）,牛顿法是一种线性化方法，其基本思想是将非线性方程 逐步归结为某种线性方程来求解.,50,这是个线性方程，记其根为 ，,则 的计算公式为,（4.2）,这就是牛顿(Newton)法.,牛顿法的几何解释.,方程 的根 可解释为,曲线 与 轴的交点的横坐标,图7-4,（图7-4).,51,设 是根 的某个近似值，过曲线 上横坐标为 的点