数值分析(颜庆津)-第4章-学习小结

第4章非线性方程与非线性方程组的迭代解法--------学习小结一、本章学习体会本章我们主要学习了非线性方程的几种解法，主要有对分法、简单迭代法、steffensen迭代法、Newton法、割线法等。这几种方法都有其思想，并且它们的思想彼此之间有一定的联系。本章的思路大致可以理解为：1.如何选取迭代公式；2.如何判断迭代公式的收敛速度；3.如何进行迭代公式的修正，以加速收敛；4.如何选取最适合的迭代方法。二、本章知识梳理具体求根通常分为两步走，第一步判断根是否存在，若存在，确定根的某个初始近似值；第二步，将初始近似值逐步加工成满足精度要求的结果。求初始近似值，即确定根的大致区间（a,b），使（a,b）内恰有方程的一个根。本章的学习思路：针对一种迭代方法，找出迭代公式，并判断其收敛性，一般选取收敛速度最快的迭代公式，所以自然的提出了如何使收敛加速的问题。4.1非线性方程的迭代解法非线性方程的迭代解法有：对分法、简单迭代法、steffensen迭代法、Newton法、割线法等。4.1.1对分法设0,bfafbaCxf且，根据连续函数的介值定理，在区间ba,内至少存在有一个实数s，使0sf。现假设在ba,内只有一个实数s，使0sf并要把s求出来，用对分法的过程：令bbaa00,对于Mk,....,2,1,0执行计算2kkkbax若kfabkk或，则停止计算取kxs否则转（3）kkkkkkbbaaafxf11,,0则令kkkkkkbbxaafxf11,,0则令若Mk则输出M次迭代不成功的信息；否则继续。对分法的局限：对分法只能求实根，而且只能求单根和奇数重根，不能求偶数根和复数根4.1.2简单迭代法及其收敛性迭代法是一种逐次逼近法,用某个固定公式反复校正根的近似值,使之逐步精确化,最后得到满足精度要求的解。1、简单迭代法的基本思想是：将方程f(x)=0化为一个等价的方程)(xx从而构成序列,2,1,0)(1kxxkk产生序列kx收敛于s，在kx收敛的情况下，当K足够大时就可取kx作为方程的近似根。一个方程可等化为好几个迭代公式，到底如何选取，取决于其收敛速度。而收敛速度要看区间内跟的情况2、收敛条件非局部收敛条件：设函数baCx,，且在ba,内可导，且满足两个条件：（1）当x[a,b]时，(x)[a,b]（2）当任意x[a,b]，存在0L1，使1)('Lx则有如下的结论：方程x=(x)在[a,b]上有唯一的根s,对任意初值x0[a,b]时，迭代序列xk+1=(xk)(k=0,1,…)收敛于s。成立误差估计式：011xxLLxskk11kkkxxLLxs对收敛性做如下定义：设ss，s'在包含s的某个开区间内连续。如果1)('x，则存在0当],[ssx时，有简单迭代法产生的序列],[ssxn且收敛于s.4.1.3简单迭代法的收敛速度1、简单迭代法收敛速度的定义一种迭代格式要具有实用意义，不但需要肯定是收敛的，还要求它收敛得比较快，就是说要有一定的收敛速度。所以有如下定义：设由某方法确定的序列{xk}收敛于方程的根x*，如果存在正实数p，使得Cxsxsrkkk1lim（C为非零常数）则称序列{xk}收敛于s的收敛速度是r阶的，或称该方法具有r阶敛速。当r=1时，称该方法为线性（一次）收敛；当r=2时，称方法为平方（二次）收敛；当1r2时，称方法为超线性收敛。由该定义易见，一个方法的收敛速度实际就是绝对误差的收缩率，敛速的阶p越大，绝对误差缩减得越快，也就是该方法收敛得越快。线性收敛条件设函数baCx,，),('baCx，且满足两个条件：（1）当x[a,b]时，(x)[a,b]（2）当任意x[a,b]，存在0L1，使1)('Lx其中L为常数则对任取的],[0bax，由简单迭代法产生的序列kx收敛于方程的唯一根s,并且当sx0时，kx是收敛的。3.m阶收敛条件设)(),()(xxsm在包含s的某个开区间内连续（m≥2）.如果)1,...,2,1(0)(misi）（0)()(sm则存在当],[ssx但sx0时，由简单迭代法产生的序列kx是以m阶速度收敛的。4、迭代过程的加速加权法迭代法加速法)(1kkxx迭代kkkkkkxxLLxxLLxLx11111111改进埃特金加速法)(1kkxx迭代)(1kkxx迭代kkkkkkkxxxxxxx11211112)(改进4.1.4steffensen迭代法)(),(kkkkyzxykkkkkkkxyzxyxx2)(21....)2,1,0(k设ss，s'在包含s的某个开区间内具有二阶连续导数。如果1)('s，则存在0当],[ssx时，由steffensen迭代法产生的序列kx至少以二阶收敛速度收敛于s.4.1.5Newton法1、基本思想设：已知方程f(x)=0的一个近似根x0，把f(x)在x0处作泰勒展开，200000)(!2)())((')()(xxxfxxxfxfxf若取前两项来近似代替f(x)（称为f(x)的线性化），则得近似的线性方程0))((')(000xxxfxf设0)('0xf，解之得)(')(000xfxfxx我们取x作为原方程f(x)=0的近似根x1，即)(')(0001xfxfxx，一般地f(x)0。再重复用上述方法得)(')(1112xfxfxx一般地，有迭代公式),2,1,0()(')(1kxfxfxxkkkk公式称为求解f(x)=0的牛顿迭代公式。牛顿法有明显的几何意义。方程f(x)=0的根s在几何上表示曲线y=f(x)与x轴的交点。当我们求得s的近似值xk以后，过曲线y=f(x)上对应点（xk,f(xk)）作f(x)的切线，其切线方程为))((')(kkkxxxfxfy求此切线方程和x轴的交点，即得s的新的近似值xk+1必须满足方程0))((')(kkkxxxfxf这就是牛顿法的迭代公式)(')(1kkkkxfxfxx的计算结果。2.Newton法的收敛性（1）、局部收敛定理设s是方程的根，在包含s的某个开区间内)(''xf连续且0)('xf，则存在0当],[ssx时，由Newton迭代法产生的序列kx至收敛于s.若sxsf0,0)(''则序列是平方收敛的。（2）、非局部收敛设f(x)在[a,b]上存在二阶连续导数，且满足下列条件：（1）f(a)f(b)0；（2）f’(x)0；（3）f(x)存在且不变号；（4）取x0[a,b]，使得f(x)f(x0)0则由方程确定的牛顿迭代序列{xk}收敛于f(x)在[a,b]上的唯一根s,并且至少是平方收敛的。3.Newton法的缺点Newton法的一个明显缺点是对每一个K都要计算它的导数，导数计算比较麻烦，尤其当导数的绝对值很小时，计算要非常精确。否则会产生很大的舍入误差。4.1.7割线法1、迭代公式...)2,1,0()()())((111kxfxfxxxfxxkkkkkkk2、割线法的收敛设0)(sf，在s的某邻域内)(''xf连续且0)('xf，则存在0，当Ixx01,时，由割线法产生的序列kx收敛于s，且收敛速度的阶至少为1.618.4.1.8单点割线法迭代公式)()())((001xfxfxxxfxxkkkkk，,2,1,0k收敛性设函数)(xf在区间ba,上存在二阶连续导数，且满足条件：（1）0)()(bfaf；（2）)(xf在区间ba,上不变号；（3）当bax,时，0)(xf；（4）baxx,,10且0)()(00xfxf，0)()(10xfxf。则由单点割线法产生的序列kx单调收敛于方程0)(xf在ba,内唯一的根，并且收敛速度是一阶的。4.2非线性方程组的迭代解法1、非线性方程组的相关定义若f：1RRDn在)int(Dx处可微，则f在x处关于各自变量的偏导数jxxf)(),,2,1(nj存在，且有Tnxxfxxfxxfxf)(,,)(,)()(21，f在x处的导数)(xf又称为f在x处的梯度，又可记为)(xgradf和)(xf定义：设F：nnRRD，)int(Dx，若存在矩阵nnRxA)(，使极限0)()()(lim0hhxAxFhxFh成立，则称F在x处可微，矩阵)(xA称为F在x处的导数，记为)()(xAxF；若D是开区域且F在D内每点处都可微，则称F在D可微。设F：nnRRD，在)int(Dx处可微的充分必要条件是F的所有分量if),,2,1(ni在x处可微；若F在x处可微，则nnnnnnnjixxfxxfxxfxxfxxfxxfxxfxF)()()()()()()()(2112111设F：nnRRD，①若F在)int(Dx处的Jacobi矩阵存在且连续，则F在x处可微，并称F在x处连续可微，且nnjixxfxF)()(。②若F在)int(Dx处可微，则F在x处连续。③若F在开区域D内可微，DD0为开凸域，则对任意的0Dx和0Dhx，等式hhxfhxfhxfxFhxFTnnTT)()()()()(2211成立，其中),,2,1(10nii2、非线性方程组的迭代方法（1）简单迭代法（压缩映像原理）设G：nnRRD在闭区域DD0上满足两个条件：①G把0D映入它自身，即00)(DDG；②G在0D上是压缩映射，即存在常数)1,0(L，使对任意的0,Dyx，有yxLyGxG)()(则有下列结论：对任取的0)0(Dx，由迭代公式),1,0)(()()1(kxGxkk产生的序列Dxk，且收敛于方程组)(xGx在0D内的唯一解x；成立误差的估计式)0()1()(1xxLLxxkk)1()()(1kkkxxLLxx设G：nnRRD，)int(Dx是方程组)(xGx的解，G在x处可微。若)(xG的谱半径1))((xG，则存在开球DxxxD0,0，使对任意的0)0(Dx，由迭代法),1,0)(()()1(kxGxkk产生的序列0Dxk且收敛于x。Newton法（将非线性方程线性化）设)int(Dx是方程组0)(xF的解，F：nnRRD在包含x的某个开区域DS内连续可微，且)(xF非奇异，则存在闭球，使对任意的00Dx，由Newton发),1,0)(()()(1)()()1(kxFxFxxkkkk产生的序列Dxk)(且超线性收敛于x；若更有)(xF在域S内二次连续可微，则序列)(kx至少是平方收敛的。优点：收敛快缺点：要求)0(x很靠近x，要求),,2,1)((nixfi各个偏导。三、本章思考题四、本章测验题二分法求0)(xf在],[ba内的根，二分次数n满足（）（A）只与函数有关（C）与根的分离区间、误差限及函数有关（B）只与误差限有关（D）只与根的分离区间以及误差限有关答案：（D）