数值计算方法第二章

11第二章非线性方程数值解法在科学计算中常需要求解非线性方程()0fx(2.1)即求函数()fx的零点．非线性方程求解没有通用的解析方法，常采用数值求解算法．数值解法的基本思想是从给定的一个或几个初始近似值出发，按某种规律产生一个收敛的迭代序列0{}kkx，使它逐步逼近于方程(2.1)的某个解．本章介绍非线性方程实根的数值求解算法：二分法、简单迭代法、Newton迭代法及其变形，并讨论它们的收敛性、收敛速度等．§2.1二分法一、实根的隔离定义2.1设非线性方程(2.1)中的()fx是连续函数．如果有*x使*()0fx，则称*x为方程(2.1)的根，或称为函数()fx的零点；如果有*()()()mfxxxgx，且()gx在*x邻域内连续，*()0gx，m为正整数，则称*x为方程(2.1)的m重根．当1m时，称*x为方程的单根．非线性方程根的数值求解过程包含以下两步(1)用某种方法确定有根区间．称仅存在一个实根的有根区间为非线性方程的隔根区间，在有根区间或隔根区间上任意值为根的初始近似值；(2)选用某种数值方法逐步提高根的精度，使之满足给定的精度要求．对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在位置，特别是对于连续函数()fx，也可以从两个端点函数值符号确定出有根区间．当函数()fx连续时，区间搜索法是一种有效的确定较小有根区间的实用方法，其具体做法如下设[,]ab是方程(2.1)的一个较大有根区间，选择合适的步长()/hban，kxakh，(0,1,,)kn．由左向右逐个计算()kfx，如果有1()()0kkfxfx，则区间1[,]kkxx就是方程的一个较小的有根区间．一般情况下，只要步长h足够小，就能把方程的更小的有根区间分离出来；如果有根区间足够小，例如区间长度小于给定的精度要求，则区间内任意一点可视为方程(2.1)的根的一个近似．例2.1确定出方程32()3430fxxxx的一个有根区间．解由22()3643(1)10fxxxx知()fx为(,)上的单调递增函数，进而()fx在(,)内最多只有一个实根．经计算知(0)0f，(2)0f，所以()0fx在区间[0,2]内有惟一实根．12如果希望将有根区间再缩小，可以取步长0.5h，在点0.5x，1x，1.5x计算出函数值的符号，最后可知区间[1.5,2]内有一个实根．二、二分法二分法是求非线性方程实根近似值的最简单的方法．其基本思想是将有根区间分半，通过判别函数值的符号，逐步缩小有根区间，直到充分逼近方程的根，从而得到满足一定精度要求的根的近似值．设()fx在区间[,]ab上连续，()()0fafb，且方程(2.1)在区间(,)ab内有惟一实根*x．记1aa，1bb，中点111()/2xab将区间11[,]ab分为两个小区间11[,]ax和11[,]xb，计算函数值1()fx，根据如下3种情况确定新的有根区间：(1)如果1()0fx，则1x是所要求的根；(2)如果11()()0fafx，取新的有根区间2211[,][,]abax；(3)如果11()()0fxfb，取新的有根区间2211[,][,]abxb．新有根区间22[,]ab的长度为原有根区间11[,]ab长度的一半．对有根区间22[,]ab施以同样的过程，即用中点222()/2xab将区间22[,]ab再分为两半，选取新的有根区间，并记为33[,]ab，其长度为22[,]ab的一半(如图2.1所示)．图2.1二分法示意图重复上述过程，建立如下嵌套的区间序列1122[,][,][,][,]kkabababab其中每个区间的长度都是前一个区间长度的一半，因此[,]kkab的长度为11()2kkkbaba由*[,]kkxab和()/2kkkxab，得*11()()22kkkkxxbaba当k时，显然，有*kxx．总结得到如下收敛定理：xoy()yfx*x1a1b2a2b3a3b1x3x2x13定理2.1设()fx在隔根区间[,]ab上连续，且()()0fafb，则由二分法产生的序列0{}kkx收敛于方程(2.1)在[,]ab上的根*x，并且有误差估计*1()(1,2,)2kkxxbak(2.2)设预先给定根*x的绝对误差限为，要求*kxx，只要1()2kba成立，这样求得对分次数ln()lnln2bak．(2.3)取k为大于(ln()ln)/ln2ba的最小整数．此时kx是方程(2.1)的满足精度要求的根近似值．注：由于舍入误差和截断误差存在，利用浮点运算不可能精确计算函数值，二分法中的判断()0kfx几乎不可能满足，取而代之为判断条件0()kfx，其中0为根近似值的函数值允许误差限．总结以上内容，给出如下算法算法2.1(二分法)输入端点,ab、根的绝对误差限、根近似值的函数值允许误差限0；输出近似解c或失败信息；Step1用公式(2.3)计算最大迭代次数k；Step2对1,,nk循环执行Step3～5；Step3()/2cab，计算()fc；Step4若0()fc，则输出c，end；Step5若()()0fcfb，则ac，否则bc．例2.2用二分法求32()4100fxxx在[1,2]上的根*x的近似值，要求*31102kxx．解由于在区间[1,2]上，(1)5f，(2)14f，2()38(38)0fxxxxx，故()0fx在[1,2]上有惟一实根*x．确定循环次数为11k，利用二分法计算结果见表2.1．表2.1二分法计算结果k有根区间[,]kkabkx()kfx123456[1.0,2.0][1.0,1.5][1.25,1.5][1.25,1.375][1.3125,1.375][1.343725,1.375]1.51.251.3751.31251.343751.3593752.375–1.7968950.1621094–0.8483887–0.3509827–0.0964088147891011[1.359375,1.375][1.359375,1.3671875][1.3632813,1.3671875][1.3632813,1.3652344][1.36425785,1.3652344]1.36718751.36328131.36523441.364257851.3647461250.0323558–0.03215000.0000720–0.0160460–0.0079887二分法具有如下特点(1)优点：计算简单，对函数()fx的光滑性要求不高，只要它连续，且在两端的函数值异号，算法收敛就可以保证；(2)缺点：只能求单实根和奇数重实根，收敛较慢，与1/2为公比的等比级数相同．当函数()fx连续时，方程(2.1)的实重根可转换为()0()fxfx的实单根．一般在求方程根近似值时不单独使用二分法，而常用它为其它数值方法提供初值．§2.2简单迭代法简单迭代法是求解非线性方程根的近似值的一类重要数值方法．本节将介绍简单迭代法的基本思想、收敛条件、收敛速度以及相应的加速算法．一、简单迭代法的基本思想简单迭代法采用逐步逼近的过程建立非线性方程根的近似值．首先给出方程根的初始近似值，然后用所构造出的迭代公式反复校正上一步的近似值，直到满足预先给出的精度要求为止．在给定的有根区间[,]ab上，将方程(2.1)等价变形为()xx(2.4)在[,]ab上选取0x作为初始近似值，用如下迭代公式1()kkxx(0,1,2,k)(2.5)建立序列0{}kkx．如果有*limkkxx，并且迭代函数()x在*x的邻域内连续，对式(2.5)两边取极限，得**()xx因而*x是(2.4)的根，从而也是(2.1)的根．称()x为迭代函数，所得序列0{}kkx为迭代序列．将这种求方程根近似值的方法称为简单迭代法，简称迭代法．15例2.3试用方程3()10fxxx的不同形式的变形建立迭代公式，并试求其在1.5附近根的近似值．解利用方程的变形建立如下4种迭代公式(1)311kkxx，(2)311kkxx(3)111kkxx(4)3112kkkxxx取初值01.5x，迭代计算，结果见表2.2．表2.2迭代法计算结果k公式(1)公式(2)公式(3)公式(4)0123456781.51.35721.330861.325881.324931.324761.324721.324711.324711.52.37512.39651904.016.902449103.2885729103.5565188104.4985626510inf1.51.290991.332141.323131.325061.324641.324731.324711.324711.51.93754.1053536.148223634.76.6012412101.4382938101.487711410inf例2.3表明非线性方程的不同等价形式对应不同的迭代过程，从某一初值出发，有的迭代收敛快，有的收敛慢，甚至不收敛．那么迭代函数()x满足什么条件时才能保证迭代序列收敛?迭代序列0{}kkx的误差如何估计?怎样才能建立收敛速度快的迭代公式?定理2.2若函数()x在区间[,]ab上具有一阶连续导数，且满足条件①对任意[,]xab，有()[,]xab；②存在常数L：01L，使得对任意[,]xab有()xL成立．则(1)方程()xx在[,]ab上有惟一实根*x(2)对任意0[,]xab，迭代公式(2.5)收敛，且*limkkxx(3)迭代公式(2.5)有误差估计式*11kkkLxxxxL(2.6)16*101kkLxxxxL(2.7)(4)**1*lim()kkkxxxxx(2.8)证明(1)构造函数()()gxxx，由条件①知()()0gaaa，()()0gbbb，因此()0gx在[,]ab上至少存在一个实根，又由条件②知当[,]xab时，()1()10gxxL，所以()0gx在[,]ab内存在惟一实根，即()xx在[,]ab内存在惟一实根，记为*x．(2)由0[,]xab及条件①知，[,]kxab(1,2,)k，并且有1()kkxx，**()xx，二者作差，并由微分中值定理得***1()()()()kkkkxxxxxx(1,2,)k(2.9)其中，k介于kx与*x之间．结合条件②，得**1kkxxLxx(1,2,)k(2.10)反复递推，有**2*1*1100kkkkxxLxxLxxLxx，(1,2,)k因01L，故*limkkxx．(3)由式(2.10)得***1111*1kkkkkkkkkkxxxxxxxxxxxxLxx从而*111kkkxxxxL(2.11)又由于111()()()()kkkkkkkxxxxxx1kkLxx(1,2,)k(2.12)其中k介于kx和1kx之间．综合式(2.11)及式(2.12)得误差估计*11kkkLxxxxL由式(2.12)反复递推，得111210kkkkkxxLxxLxx并代入式(2.6)得误差估计*11011kkkkLLxxxxxxLL(1,2,)k(4)由式(2.9)得*1*()kkkxxxx17两端取极限，并注意到()x的连续性和*limkkx(因为k介于*x与kx之间)，得**1*lim()kkkxxxxx