数值计算方法第二章

第二章非线性方程数值解法在科学计算中常需要求解非线性方程 (2.1)即求函数的零点非线性方程求解没有通用的解析方法，常采用数值求解算法数值解法的基本思想是从给定的一个或几个初始近似值出发，按某种规律产生一个收敛的迭代序列，使它逐步逼近于方程(2.1)的某个解本章介绍非线性方程实根的数值求解算法：二分法、简单迭代法、Newton迭代法及其变形，并讨论它们的收敛性、收敛速度等2.1二分法一、实根的隔离定义2.1设非线性方程(2.1)中的是连续函数如果有使，则称为方程(2.1)的根，或称为函数的零点；如果有，且在邻域内连续，为正整数，则称为方程(2.1)的重根当时，称为方程的单根非线性方程根的数值求解过程包含以下两步(1) 用某种方法确定有根区间称仅存在一个实根的有根区间为非线性方程的隔根区间，在有根区间或隔根区间上任意值为根的初始近似值；(2) 选用某种数值方法逐步提高根的精度，使之满足给定的精度要求对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在位置，特别是对于连续函数，也可以从两个端点函数值符号确定出有根区间当函数连续时，区间搜索法是一种有效的确定较小有根区间的实用方法，其具体做法如下设是方程(2.1)的一个较大有根区间，选择合适的步长，由左向右逐个计算，如果有，则区间就是方程的一个较小的有根区间一般情况下，只要步长足够小，就能把方程的更小的有根区间分离出来；如果有根区间足够小，例如区间长度小于给定的精度要求，则区间内任意一点可视为方程(2.1)的根的一个近似例2.1确定出方程的一个有根区间 解由知为上的单调递增函数，进而在内最多只有一个实根经计算知，所以在区间内有惟一实根如果希望将有根区间再缩小，可以取步长，在点，计算出函数值的符号，最后可知区间内有一个实根二、二分法 二分法是求非线性方程实根近似值的最简单的方法其基本思想是将有根区间分半，通过判别函数值的符号，逐步缩小有根区间，直到充分逼近方程的根，从而得到满足一定精度要求的根的近似值设在区间上连续，且方程(2.1)在区间内有惟一实根记，中点将区间分为两个小区间和，计算函数值，根据如下3种情况确定新的有根区间：(1) 如果，则是所要求的根；(2) 如果，取新的有根区间；(3) 如果，取新的有根区间新有根区间的长度为原有根区间长度的一半对有根区间施以同样的过程，即用中点将区间再分为两半，选取新的有根区间，并记为，其长度为的一半(如图2.1所示)图2.1 二分法示意图重复上述过程，建立如下嵌套的区间序列其中每个区间的长度都是前一个区间长度的一半，因此的长度为由和，得当时，显然，有总结得到如下收敛定理：定理2.1设在隔根区间上连续，且，则由二分法产生的序列收敛于方程(2.1)在上的根，并且有误差估计 (2.2)设预先给定根的绝对误差限为，要求，只要成立，这样求得对分次数 (2.3)取为大于的最小整数此时是方程(2.1)的满足精度要求的根近似值注：由于舍入误差和截断误差存在，利用浮点运算不可能精确计算函数值，二分法中的判断几乎不可能满足，取而代之为判断条件，其中为根近似值的函数值允许误差限总结以上内容，给出如下算法算法2.1 (二分法) 输入端点、根的绝对误差限、根近似值的函数值允许误差限；输出近似解或失败信息；Step 1用公式(2.3)计算最大迭代次数；Step 2对循环执行Step 35；Step 3，计算；Step 4若，则输出，end；Step 5若，则，否则例2.2用二分法求在上的根的近似值，要求解由于在区间上，故在上有惟一实根确定循环次数为，利用二分法计算结果见表2.1表2.1二分法计算结果有根区间12345678910111.0,2.01.0,1.51.25,1.51.25,1.3751.3125,1.3751.343725,1.3751.359375,1.3751.359375,1.36718751.3632813,1.36718751.3632813,1.36523441.36425785, 1.36523441.51.251.3751.31251.343751.3593751.36718751.36328131.36523441.364257851.3647461252.3751.7968950.16210940.84838870.35098270.09640880.03235580.03215000.00007200.01604600.0079887二分法具有如下特点(1) 优点：计算简单，对函数的光滑性要求不高，只要它连续，且在两端的函数值异号，算法收敛就可以保证；(2) 缺点：只能求单实根和奇数重实根，收敛较慢，与为公比的等比级数相同当函数连续时，方程(2.1)的实重根可转换为的实单根一般在求方程根近似值时不单独使用二分法，而常用它为其它数值方法提供初值2.2简单迭代法简单迭代法是求解非线性方程根的近似值的一类重要数值方法本节将介绍简单迭代法的基本思想、收敛条件、收敛速度以及相应的加速算法一、简单迭代法的基本思想简单迭代法采用逐步逼近的过程建立非线性方程根的近似值首先给出方程根的初始近似值，然后用所构造出的迭代公式反复校正上一步的近似值，直到满足预先给出的精度要求为止在给定的有根区间上，将方程(2.1)等价变形为 (2.4)在上选取作为初始近似值，用如下迭代公式() (2.5)建立序列如果有，并且迭代函数在的邻域内连续，对式(2.5)两边取极限，得因而是(2.4)的根，从而也是(2.1)的根称为迭代函数，所得序列为迭代序列将这种求方程根近似值的方法称为简单迭代法，简称迭代法 例2.3试用方程的不同形式的变形建立迭代公式，并试求其在附近根的近似值 解利用方程的变形建立如下4种迭代公式 (1) ， (2) (3) (4) 取初值，迭代计算，结果见表2.2表2.2迭代法计算结果公式(1)公式(2)公式(3)公式(4)0123456781.51.35721.330861.325881.324931.324761.324721.324711.324711.52.37512.39651904.016.902443.288573.556514.49856inf1.51.290991.332141.323131.325061.324641.324731.324711.324711.51.93754.1053536.148223634.76.601241.438291.4877inf例2.3表明非线性方程的不同等价形式对应不同的迭代过程，从某一初值出发，有的迭代收敛快，有的收敛慢，甚至不收敛那么迭代函数满足什么条件时才能保证迭代序列收敛? 迭代序列的误差如何估计? 怎样才能建立收敛速度快的迭代公式?定理2.2若函数在区间上具有一阶连续导数，且满足条件 对任意，有； 存在常数：，使得对任意有成立则(1) 方程在上有惟一实根(2) 对任意，迭代公式(2.5)收敛，且(3) 迭代公式(2.5)有误差估计式 (2.6) (2.7)(4) (2.8)证明(1)构造函数，由条件知，因此在上至少存在一个实根，又由条件知当时，所以在内存在惟一实根，即在内存在惟一实根，记为(2)由及条件知，并且有，二者作差，并由微分中值定理得 (2.9)其中，介于与之间结合条件，得 (2.10)反复递推，有， 因，故(3)由式(2.10)得从而 (2.11)又由于 (2.12)其中介于和之间综合式(2.11)及式(2.12)得误差估计由式(2.12)反复递推，得并代入式(2.6)得误差估计 (4)由式(2.9)得两端取极限，并注意到的连续性和(因为介于与之间)，得误差估计(2.6)称为后验误差估计，也称为误差渐进估计，误差估计(2.7)称为先验误差估计定理2.2条件成立时，对任意，迭代序列均收敛，故称定理2.2为全局收敛性定理下面讨论邻近的收敛性，即局部收敛性定理2.3设存在方程根的闭邻域以及小于的正数，使得连续且则对任意，迭代收敛证明由在内连续，且有，则对任意，有由定理2.2知迭代过程对任意初值均收敛二、迭代法的收敛阶为刻画迭代法收敛速度的快慢，引进收敛序列的收敛阶概念 定义2.2 设迭代序列收敛到，记，如果存在常数和实数，使得 (2.13)则称序列是阶收敛的当时，称为线性收敛的，此时要求；为超线性收敛越大，序列收敛到越快称为渐进常数，越小，收敛越快所以迭代法的收敛阶是对迭代法收敛速度的一种度量 显然，由定理2.2(4)知，当时简单迭代法线性收敛，渐进常数 算法2.2 (简单迭代法) 输入初始值、容许误差；输出近似解或失败信息；Step 1对循环执行Step 23；Step 2；Step 3若，则输出，end；否则，转向Step2例2.4求方程的最大实根的近似值，要求绝对误差不超过解(1)确定有根区间方程等价形式为作函数和的图形，如图2.2所示，知方程的最大实根在区间内(2)建立迭代公式，判别收敛性将方程等价变形为迭代函数，迭代公式由，知在区间内仅有一根又，所以，当时，图2.2 函数和的图形因为，所以对于一切有由定理2.2知，迭代法收敛(3) 迭代计算取，有，因为，所以方程的最大根三、迭代法的加速对于收敛的迭代序列，理论上迭代次数足够多时，就可以使计算结果满足任意给定的精度要求但在应用中，有的迭代过程收敛极为缓慢，计算量很大，因此研究迭代格式的加速方法是非常必要的1.线性收敛序列的Aitken加速法设是一个线性收敛的序列，极限为即有小于的正数使得由于它线性收敛，误差减少的速度较慢，值得采用加速技术下面介绍Aitken加速法对充分大的，有 由上面两式得解得利用上式右端的值可定义另一序列，即得Aitken加速公式 (2.14)它仍然收敛到，但收敛速度更快证明请参考文献19 2.Steffensen迭代法Aitken加速方案是对任意线性收敛序列构建的，并不限定如何获得将Aitken加速方法用于简单迭代法产生迭代序列时，得到著名的Steffensen迭代法，具体迭代公式如下 (2.15)或者直接写成可以证明Steffensen迭代法在一定的条件下与原简单迭代法的迭代序列具有相同的极限，但Steffensen迭代法收敛速度更快，可以达到二阶收敛证明请参考文献19例2.5对例 2.3用Steffensen迭代法求方程根的近似值，要求 解(1) 简单迭代法 将原方程化成，建立迭代公式易验证该迭代公式在区间上满足定理2.2的条件，产生的迭代序列收敛(2) Steffensen迭代法 加速公式为(1) 取初值，简单迭代法和Steffensen迭代法计算结果见表2.3注意：Steffensen迭代法每一迭代步的计算量大约是原简单迭代法计算量的两倍表2.3简单迭代法和Steffensen迭代法计算结果迭代法Steffensen法0123456789101.51.3483997251.3673763721.3649570151.3652647481.3652255941.3652305751.3652299411.3652300221.3652300121.3652300131.51.92.43.13.94.06.38.11.01.31.51.3652652231.3652300131.3652300131.33.52.52.3Newton迭代法 Newton迭代法是求解非线性方程根的近似值的一种重要数值方法其基本思想是将非线性函数逐步线性化，从而将非线性方程(2.1)近似地转化为一系列线性方程来求解下面讨论其格式的构造、收敛性、收敛速度以及有关变形一、Newton 迭代法的构造设是方程(2.1)的某根的一个近似值，将函数在点处作Taylor展开取前两项近似代替，即用线性方程近似非线性方程(2.1)设，则用线性方程的根作为非线性方程根的新近似值，即定义 (2.16)上式即是著名的Newton迭代公式它也是一种简单迭代法，其中迭代函数 Newton迭代法具有明显的几何意义(如图2.3所示)方程的根即为曲线与轴的交点的横坐标设是的某个近似值，过曲线上相应的点作切线，其方程为它与轴的交点横坐标就是只要初值取得充分靠近根，序列就会很快收敛到所以Newton迭代法也称为切线法图2.3 Newton迭代法的几何意义二、收敛性定理2.4设是方程(2.1)的单根，在的邻域上连续且则存在，当时，Newton法产生的序列至少二阶收敛 证明(1) Newton法迭代函数的导数为显然，在邻域上连续又，一定存在的某个闭邻域，当时，有从而Newton法产生的序列收敛(2)将在处作一阶Taylor展开 (2.17)其中介于与之间又由Newton迭代公式有 (2.18)式(2.17)与式(2.18)相减从而 (2.19)由迭代法收敛阶的定义知，Newton迭代法至少具有二阶收敛速度上述定理给出了Newton法局部收敛性，它对初值要求较高，初值必须充分靠近方程根时才可能收敛，因此在实际应用Newton法时，常常需要试着寻找合适的初值下面的定理则给出Newton法在有根区间上全局收敛的一个充分条件 定理2.5设是方程(2.1)在区间上的根且在上存在，如果(1) 对于任意有，； (2) 选取初值，使则Newton法产生的迭代序列单调收敛于，并具有二阶收敛速度 (a) (b) (c) (d)图2.4定理2.5的几何解释 证明满足定理条件(1)共有4种情形，如图2.4所示下面仅以图2.4()情况进行证明，此时满足对任意有，初值 首先用数学归纳法证明有下界当时，成立假设时，不等式成立将在处作一阶Taylor展开，得于是又由Newton迭代公式，有 (2.20)式(2.20)右端的第二项大于零，因此由数学归纳法知， 其次证明单调递减由，知，于是Newton迭代公式(2.16)的第二项大于零，从而故迭代序列单调减少 序列单调减少有下界，它必有极限，记为，它满足，进而有对两端取极限，并利用，的连续性，得=0结合函数在上的单调性知 因此，Newton法产生的迭代序列单调收敛于，利用式(2.20)及式(2.19)知该Newton迭代序列二阶收敛算法2.3 (Newton迭代法) 输入初始近似值、 容许误差；输出近似解或失败信息；Step 1对循环执行Step 23；Step 2；Step 3若，则输出，end；否则，转向step2 例2.6利用非线性方程的Newton迭代公式计算的近似值，使得，并证明对任意，该迭代法均收敛解(1) 建立计算公式 其中(2) 判断收敛性 在区间内，当选取初值时，存在足够大的，使得由定理2.5知，该迭代公式产生的迭代序列都收敛于当选取初值时， 这样，从起，以后的都大于 故该迭代公式对任何初值都收敛 (3) 取初值，迭代计算，结果见表2.4表2.4Newton法计算结果0123421.751.73214291.73205081.7320508从表2.4可见，迭代4步后已经满足精度要求，精确解三、Newton迭代法的变形Newton迭代格式构造容易，迭代收敛速度快，但对初值的选取比较敏感，要求初值充分接近真解，另外对重根收敛速度较慢（仅有线性收敛速度），而且当函数复杂时，导数计算工作量大下面从不同的角度对Newton法进行改进1 Newton下山算法Newton迭代法的收敛性依赖于初值的选取，如果偏离较远，则Newton迭代法有可能发散，从而在实际应用中选出较好的初值有一定难度，而Newton下山法则是一种降低对初值要求的修正Newton迭代法方程(2.1)的根也是的最小值点，若把看成在处的高度，则是山谷的最低点若序列满足单调性条件 (2.21)则称为称为的下山序列在Newton迭代法中引入下山因子，将Newton迭代公式(2.16)修正为 (2.22)适当选取下山因子，使得单调性条件(2.21)成立，即称为Newton下山法对下山因子的选取是逐步探索进行的一般地，从开始反复将因子的值减半进行试算，一旦单调性条件(2.21)成立，则称“下山成功”；反之，如果在上述过程中找不到使条件(2.21)成立的下山因子，则称“下山失败”，这时可对进行扰动或另选初值，重新计算2 针对重根情形的加速算法假设是方程的重根，并且存在函数，使得有 (2.23)式中在的某邻域内可导，则Newton迭代函数，其导数在处的值所以，由定理2.2知Newton迭代法此时只有线性收敛速度为了加速收敛，可以采用如下两种方法方法一令，则是方程的单根，将Newton迭代函数修改为因此有重根加速迭代公式 (2.24)它至少二阶收敛方法二将Newton迭代函数改为这时，由此得到加速迭代公式 (2.25)3 割线法Newton法每步需要计算导数值如果函数比较复杂时，导数的计算量比较大，此时使用Newton法不方便为了避免计算导数，可以改用平均变化率替换Newton迭代公式中的导数，即使用如下公式 (2.26)上式即是割线法的迭代公式割线法也具有明显的几何意义，如图2.5所示，依次用割线方程的零点逐步近似曲线方程的零点割线法的收敛速度比Newton法稍慢一点，可以证明其收敛阶约为1.618，证明请参考文献4此外在每一步计算时需要前两步的信息，即这种迭代法也是两步法两步法在计算前需要提供两个初始值与图2.5割线法的几何意义例2.7已知方程有一个二重根，分别用Newton法(2.16)和重根Newton法(2.24)和(2.25)求其近似值，要求解，由Newton法(2.16)得由Newton法(2.24) 得由Newton法(2.25) 得利用上述三种迭代格式，取初值，分别计算，结果见表2.5表2.5Newton法和重根Newton法计算结果式(2.16)式(2.24)式(2.25)01231014151.41.40714291.41068711.41245251.41419981.41421271.41421311.41.41414141.4142