数值分析：7.3-7.4非线性方程求解.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 非线性方程数值求解,Numerical Value Analysis,7.3,Newton,迭代法,7.3,Newton,迭代法,将,f(x),在点,x,n,作,Taylor,展开,:,Taylor,展开线性化,f(x)=0,近似于,f(x,n,)+,f,(x,n,)(x-x,n,)=0,(1),从,(1),解出,x,记为,x,n+1,则,1.Newton,迭代公式建立,2,它对应的迭代方程为 显然是,f(x)=0,的同解方程，故其迭代函数为,在,f(x)=0,的根,x*,的某个邻域 内,在,x的邻域,R,内，对任意初值 ，,应用,公式（,2,）,来解方程的方法就称为,牛顿迭代法,。它是解代数方程和超越方程的有效方法之一,.,4,2.Newton,迭代法的几何意义,与,x,轴,(y=0),的交点,x,，,作为下一个迭代点,x,n+1,即,用,f(x),在,x,n,处,的切线,Newton,迭代法又称切线法,.,4,3,、牛顿迭代法的步骤,步一,、准备。选定初始近似值 ，计算,步二,、迭代。按公式 迭代一次，得到新的近似值 ，计算,步三,、控制。如果 满足 或,.,则终止迭代，以 作为所求的根；否则转步四。此处 是允许误差,15,而 其中,c,是取绝对值或相对误差,的控制常数，一般可取,c=1,。,步四,、修改。如果迭代次数达到预定指定的次数,N,，,或者,则方法失败；否则以 代替 转步二继续迭代。,16,例,用,Newton,迭代法求下面方程的一个正根,计算结果精确到,7,位小数,.,解:,由,Newton,迭代法,x,1,=,1.4666667,x,4,=,1.3688081,x,5,=,1.3688081,迭代,5,次,精度达,10,-7,x,*,1.368808,7,4.Newton,迭代法收敛定理,（,1,）,Newton,迭代公式在单根情况下至少,2,阶收敛,;,定理,7.3.1,设,f(x*)=0,且在,x*,的邻域,上 存在,连续,则可得,8,4.Newton,迭代法收敛定理,证：,将,f(x),在,x,n,处作,2,阶,Taylor,展开,并将解,x*,代入,9,所以，,Newton,法至少二阶收敛,.,注意到,n,在,x,n,及,x*,之间,10,Newton,法在重根情形下的收敛阶,20,有局部线性收敛性,重数,m,越高,越接近于,1,收敛越慢。,20,Newton,迭代法的特征,Newton,迭代公式是一种特殊的不动点迭代,其迭代函数为,:,Newton,迭代是局部线性化方法,它在单根附近具有较高的收敛速度,.,方法有效前提,:,13,5.Newton,迭代法的应用,-,开方公式,对于给定正数 应用牛顿迭代法解二次方程,可导出求开方值 的计算公式,设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。,定理,开方公式对于任意给定的初值 均为平方收敛。,14,牛顿迭代法的优缺点,在单根附近,牛顿迭代法具有平方收敛的速度，,所以在迭代过程中只要迭代几次就会得到很,精确的解。,优点,缺点,重根情形下为局部线性收敛,;,2.,牛顿迭代法计算量比较大,:,因每次迭代除计算函数值外还要计算微商值,;,3.,选定的初值要接近方程的解，否则有可能得,不到收敛的结果,;,21,牛顿迭代法的改进,缺点克服,:,局部线性收敛,-,改进公式或加速,2.,每步都要计算微商值,-,简化,Newton,迭代法或弦截法,3.,初值近似问题,-,二分法求初值或,”,下山算法,”,21,方法一、,若已知重数,m(m,1),则利用,m,构造新的,迭代公式,:,此时,至少,2,阶收敛,.,6.Newton,法的改进,(I)-,重根情形,不实用,:m,往往不确定,.,17,方法二、,取,再对函数,F(x),用,Newton,迭代,:,此时,X*,为,F(x),的单根,所以是,2,阶收敛,.,缺点：要用到二阶导数,.,18,Newton,迭代法,需要求每个迭代点处的导数,复杂！,这种格式称为,简化,Newton,迭代法,精度稍低,6.Newton,法的改进,(II),19,则,Newton,迭代法变为,这种格式称为弦截法,收敛阶约为,1.618,20,例,用简化,Newton,法和弦截法解下面方程的根，并和,Newton,迭代法比较,解:,由简化,Newton,法,由弦截法,由,Newton,迭代法,21,x,0,=0.5,x,1,=0.3333333333,x,2,=0.3497942387,x,3,=0.3468683325,x,4,=0.3473702799,x,5,=0.3472836048,x,6,=0.3472985550,x,7,=0.3472959759,x,8,=0.3472964208,x,9,=0.3472963440,x,10,=0.3472963572,x,11,=0.3472963553,x,0,=0.5;,x,1,=0.4;,x,2,=0.3430962343,x,3,=0.3473897274,x,4,=0.3472965093,x,5,=0.3472963553,x,6,=0.3472963553,简化,Newton,法,由弦截法,要达到精度,10,-8,简化,Newton,法迭代,11,次,弦截法迭代,5,次,Newton,迭代法迭代,4,次,x,0,=0.5;,x,1,=0.3333333333,x,2,=0.3472222222,x,3,=0.3472963532,x,4,=0.3472963553,由,Newton,迭代法,22,无论哪种迭代法：,Newton,迭代法,简化,Newton,法,弦截法,用,Newton,迭代法求解,:,x,0,=2,x,1,=-3.54,x,2,=13.95,x,3,=-279.34,x,4,=122017,是否收敛均与初值的位置有关,.,例:,x,0,=1,x,1,=-0.5708,x,2,=0.1169,x,3,=-0.0011,x,4,=7.9631,10,-,10,x,5,=0,收敛,发散,迭代法的,局部收敛性,23,6.Newton,法的改进,(III):,牛顿下山法,一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。,为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：,满足这项要求的算法称为下山法。,牛顿下山法采用以下迭代公式：,其中 称为下山因子。,牛顿下山法只有线性收敛,.,24,第七章 非线性方程数值求解,Numerical Value Analysis,7.4,Aitken,加速方案,/,Steffensen,迭代法,改进、加速收敛,/*accelerating convergence*/,有些迭代过程虽收敛，但速度很慢。为了达到所要求的精度，需要迭代的次数很多，由此必须设法加速迭代过程。,1.,基本思想,上式说明，将预测值,x,0,和校正值,x,1,作,线性组合,作为,x,*,的一个新近似值，可能比,x,1,更好。令：,介于,x,0,与,x,*,之间，设 变化不大，则有,微分中值定理,x,0,-,x,*,的,预测值,26,一般地，有,线性组合,校正,残差,27,简单迭代公式的加速,设 是根 的某个近似值，用迭代公式校正一次得,假设 ，则有,据此可导出如下加速公式：,其一步分为两个环节：,迭代,:,改进,:,28,29,在方法,1,中含有,L,（或,q,）,，实际应用中不便。下面设法消除,L,（或,q,）,，,得到一种新的,加速方法,-,Aitken,（,埃特金）方法。,x,0,prediction,推广，有下面一般计算公式,：,x,1,=,g,(,x,0,),updating,x,2,=,g,(,x,1,),further,updating,30,埃特金迭代法求方程的实根,31,定理,7.4.1,设序列 线性收敛于,x*,则 的,Aitken,序列 存在,且,即 比 更快收敛于,x*.,32,33,Steffensen,迭代,在,Aitken,加速法中,只要有三个相邻的点就可以进行,加速,即对任意线性收敛序列 构建的,.,现将其与不,动点迭代 方法结合起来,:,迭代函数 迭代初始值 迭代序列,34,或写成不动点迭代形式,35,See you next time!,应用数值分析,：,例题,7.3.2,；,习题,7.10,、,7.15,、,7.16,、,7.18,36,