非线性方程(组)的数值解法——牛顿法、弦切法

1第七章非线性方程(组)的数值解法计算方法——Newton法——弦截法、抛物线法2本讲内容Newton法及其收敛性牛顿下山法弦截法与抛物线法3Newton法基本思想将非线性方程线性化2()()()()()()2!kkkkffxfxfxxxxx设xk是f(x)=0的近似根，将f(x)在xk处Taylor展开令：()0Px1()'()kkkkfxxxfx()Px()()()kkkfxfxxx条件：f’(x)04Newton法xyx*xkxk+15Newton法算法：(Newton法)(1)任取迭代初始值x0(2)对k=1,2,...,maxit，计算判断收敛性，若收敛，则停止计算，输出近似解1()'()kkkkfxxxfx6收敛性1()'()kkkkfxxxfxk=0,1,2,...迭代函数()()'()fxxxfx''(*)'(*)0,''(*)2'(*)fxxxfx牛顿法至少二阶局部收敛12*''(*)''(*)lim(*)2!2'(*)kkkxxxfxxxfx7举例例：用Newton法求f(x)=xex–1=0的解ex75.m8举例例：用Newton法求f(x)=x2–C=0的正根112kkkCxxx解：2112kkkxCxCx2112kkkxCxCx211kkkkxCxCxCxC2200kkkkxCxCqxCxC2221kkkqxCCq对任意x00，总有|q|1，即牛顿法收敛9牛顿法牛顿的优点牛顿法是目前求解非线性方程(组)的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。牛顿的缺点对重根收敛速度较慢（线性收敛）对初值的选取很敏感，要求初值相当接近真解先用其它算法获取一个近似解，然后使用牛顿法需要求导数！10简化的Newton法10()'()kkkfxfxxx线性收敛简化的Newton法基本思想：用f’(x0)替代所有的f’(xk)11Newton下山法1()'()kkkkfxxxfx下山因子的取法：从=1开始，逐次减半，直到满足下降条件基本思想：要求每一步迭代满足下降条件1kkfxfx具体做法：加下山因子Newton下山法保证全局收敛12重根情形()(*)()mfxxxgx(*)0gx且解法一：直接使用Newton法()()'()fxxxfx1'(*)1xm线性收敛解法二：改进的Newton法()()'()fxxxmfx'(*)0x二阶收敛缺点：需要知道m的值重根情形13重根情形()()'()fxxfx令x*是(x)=0的单重根解法三：用Newton法解(x)=02()()'()()'()['()]()''()xfxfxxxxxfxfxfx12()'()['()]()''()kkkkkkkfxfxxxfxfxfx迭代格式：14举例例：求x4-4x2＋4=0的二重根*2x212()4xxxx(1)普通Newton法ex76.m(2)改进的Newton法(3)用Newton法解(x)=0222()2xxxx232(2)()2xxxxx15弦截法与抛物线法弦截法与抛物线法目的：避免计算Newton法中的导数，且具有较高的收敛性（超线性收敛）弦截法（割线法）：用差商代替微商抛物线法：用二次多项式近似f(x)16弦截法弦截法迭代格式：111()()'()[,]kkkkkkkfxfxfxfxxxx111()()()kkkkkkkxxxxfxfxfxk=1,2,3,...注：弦截法需要提供两个迭代初始值17收敛性定理：设x*是f(x)的零点，f(x)在x*的某邻域U(x,)内有二阶连续导数，且f’(x)0，若初值x0，x1U(x,)，则当U(x,)充分小时，弦截法具有p阶收敛性，其中152p2(10)pp18弦截法几何含义xyx*xk-1xkxk+119抛物线法基本思想：用二次曲线与x轴的交点作为x*的近似值抛物线法20抛物线法yxk-2xk-1xkxk+121抛物线法计算过程二次曲线方程(三点Newton插值多项式)21()()[,]()kkkkpxfxfxxxx121[,,]()()kkkkkfxxxxxxx问题：p2(x)与x轴有两个交点，取哪个点？解决方法：取靠近xk的那个点!22抛物线法21()()[,]()kkkkpxfxfxxxx121[,,]()()kkkkkfxxxxxxx12122()4()[,,]kkkkkkkfxxxfxfxxx1121[,][,,]()kkkkkkkfxxfxxxxx取靠近xk的那个点23收敛性在一定条件下可以证明：抛物线法的收敛阶为1.840p32(10)ppp24作业教材238页，习题7教材239页，习题9、15