数值分析课件第二章.ppt

《数值分析课件第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数值分析第二章解非线性方程的数值方法一、二分法二、迭代法三、Newton法对给定方程f(x)=0,可以用各种方法转化成等价方程二、迭代法1迭代法的基本思想若x*是f(x)的根,即若,则有称x*为函数的一个不动点.设x0是一个近似解，可以构造序列迭代法(2.2)称为简单迭代法或单点迭代法.称函数为迭代函数.简单迭代法(2.2),若迭代序列{xk}保持有界,全在定义域内称为适定的;若进一步有称为是收敛的.若收敛，即存在x*使得则由的连续性和可得x*=(x*)，即x*是的不动点，也就是f(x)的零点。例求x3-x-1=0在1.5附近的根x*解xyy=xxyy=xx

2、yy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1x22收敛定理和误差估计定理1设在[a,b]上有连续的一阶导数,且(1)有(2)则有(1)函数在[a,b]上存在唯一的不动点x*由迭代公式(2.2)得到的序列(2)都收敛到方程的根x*(3)(4)证明(1)先证明存在性,作函数由条件(1)可知由连续函数根的存在定理可知,必有使得h(x*)=0，即再证明唯一性,设也是一个解,即那么因为L<1,所以有(2)由条件(2)和Lagrange中值定理得因为L<1,所以当时,

3、有(3)和(4)利用(2)的方法令即分别得定理1的几点说明(i)通常将条件(1)称为映内性；(ii)条件(2)也可以改为：存在常数L且0

4、近考察收敛性，称为局部收敛性.定义设有不动点x*,如果存在x*的某个邻域对任意的迭代(2.2)产生的序列且收敛到x*,则称(2.2)局部收敛.证明由连续函数的性质,存在x*的某个邻域对任意的有而根据定理1可以断定迭代过程(2.2)对任意初值均收敛.定理2若x*为迭代函数的不动点,在x*的某个邻域内有连续导数,且则迭代法(2.2)局部收敛.例只用四则运算不用开方求方程x2-3=0的根解例设试讨论a的取值范围使迭代公式(2.2)局部收敛到解因为所以由定理2可知只需即所以当时,迭代公式收敛.例5迭代收敛的阶则称该迭代为r阶收敛.(C为常数)(1)当r=1时称为线性收敛，

5、此时C<1；(2)当r=2时称为二次收敛，或平方收敛；(3)当r=1,C=0时称为超线性收敛.二分法线性收敛;定义设迭代收敛到的不动点x*.记ek=xkx*，若不动点迭代中，若则线性收敛则迭代公式是p阶收敛的，且定理3设迭代若在x*的某邻域内连续，且证明：根据泰勒展开有6迭代加速若则迭代公式(2.2)只是线性收敛的取初始点x0,令那么由此得迭代公式如何求L?再令得到由此得Steffensen加速法Steffensen加速法是平方收敛的.三、Newton法1Newton法基本思想设xk是f(x)=0的近似根,将f(x)在xk一阶Taylor展开:(在xk和x之间

6、)当f‘(x)0时,即将非线性方程线性化于是xyx*xkxk+1Newton法的几何意义Newton法的本质就是不断用切线来近似曲线，因此Newton法也成为切线法.2Newton法的算法(1)取初始点x0,最大迭代次数N和精度要求ε置k=0;(2)计算(3)若则停止计算;(4)若k=N则停止计算;否则置k=k+1,转(2).Newton法可以看作下面的不动点迭代：其中’(x*)=0Newton法至少二阶局部收敛3Newton法收敛性证明(略)Newton法也可以看作一类特殊的加速迭代取(x)=x-f(x)定理4设f(x)在其零点x*的某个邻域内二阶连续可导

7、且0，则存在x*的某个邻域N(x*)=[x*-,x*+],使得对x0N(x*)，Newton法产生的序列以不低于二阶的收敛速度收敛到x*.例设计一个二阶收敛算法计算(a>0).解：转化为求x2-a=0的正根Newton迭代：二阶收敛设x*是f(x)的m(m2)重根,Newton法是否收敛？4重根情况所以Newton迭代：线性收敛,且重数m越高,收敛越慢.提高收敛速度但m通常无法预先知道！法一：取二阶收敛法二：将求f(x)的重根转化为求另一个函数的单根.构造针对(x)的具有二阶收敛的Newton迭代：令，则x*是(x)的单重根.例取初始点x0=1.

8、5,分别用