非线性方程数值解法详解课件.pptx

《非线性方程数值解法详解课件.pptx》由会员分享，可在线阅读，更多相关《非线性方程数值解法详解课件.pptx（57页珍藏版）》请在三一办公上搜索。

1、第一章,非线性方程和方程组的数值解法,非线性方程根的概念,给定非线性方程f(x)=0如果有使得f()=0，则称为f(x)=0的根或f(x)的零点.设有正整数m使得f(x)=(x-)mg(x) 且g()0 ，则当m2时，称为f(x)=0的m重根；当m=1时，称为f(x)=0的单根.若为f(x)=0的m重根，则 f()=f()=f (m-1)()=0, f (m)()0这里只讨论实根的求法.,求根步骤,（1）根的存在性.（2）根的隔离.（3）根的精确化.,非线性方程求根的数值方法,二分法迭代法 单点迭代法(不动点迭代，Newton迭代法) 多点迭代法(弦截法）,迭代法的一般理论,迭代法是一种逐次逼

2、近的方法，它的基本思想是通过构造一个递推关系式 (迭代格式) ，计算出根的近似值序列,并要求该序列收敛于方程的根.,单点迭代法,将方程f(x)=0改写成等价形式 x=(x) (1)建立迭代公式 xk+1=(xk) (2)在根的附近任取一点x0，可得一序列 .若 收敛，即 ，且(x)连续，则对(2)两端取极限有 =() ，从而为方程(1)的根，也称为(x)的不动点，这种求根算法称为不动点迭代法（Picard迭代法）. (x) 称为迭代函数.,多点迭代法,建立迭代公式 xk+1=(xk-n+1, ,xk-2, xk-1, xk) (3),对于迭代法需要考虑一下几个主要问题收敛性收敛速度计算效率,迭

3、代法的局全收敛性,定义1 设为f(x)=0的根，如果x0a, b，由迭代法产生的序列都收敛于根 ，则称该迭代法是全局收敛的。,迭代法的局部收敛性,定义2 设方程x=(x) 根, 如果存在的某个邻域 : x-，对任意初值x0，迭代过程所产生的序列均收敛于根 ，则称该迭代法是局部收敛的.,迭代过程的收敛速度,定义3 记 ek = - xk ，若则称迭代过程是p阶收敛的.特别地，当p=1时，称为线性收敛； 当p1时，称为超线性收敛， 当p=2时，称为平方收敛. p越大，收敛越快.,效率指数,定义3 称为效率指数. 其中p表示迭代的收敛阶，表示每步迭代的计算量. EI越大，计算效率越高.,不动点迭代法

4、,不动点迭代法的整体收敛性,定理1.1 设(x)满足 (1)当xa, b时，(x)a, b ； (2)x1, x2a, b ，有 (x1)-(x2)L x1-x2 ， L1 则对任意初值x0 a, b, 迭代过程 xk+1=(xk)收敛于 x=(x)的惟一根 ，且有误差估计式,证 根的存在性 由(2)知(x)连续. 令f(x)=x-(x), f(a)0, f(b)0, 从而f(x)=0在a, b 上有根，即x=(x)在a, b 上有根. 根的唯一性 设x=(x)在a, b 上有两根1, 2， 1 2 ， 1- 2=(1)-(2)L 1- 2 与 L1矛盾.故1= 2 序列的收敛性 xk+1-=

5、(xk)-()Lxk- , xk+1-Lk+1x0- 由0L1有,误差估计 xk+1-xk=(xk)(xk-1)Lxk-xk-1 xk+2-xk+1=(xk+1)(xk)L2xk-xk-1 xk+p-xk+p-1Lpxk-xk-1xk+p-xk xk+p-xk+p-1+xk+p-1-xk+p-2+ xk+1-xk (Lp+Lp-1+L) xk-xk-1 =令p，有,定理1.2 设(x)在a, b上具有一阶导数，且 (1)当xa, b时, (x)a, b ； (1) xa, b ，有(x)L1则对任意初值x0 a, b, 迭代过程 xk+1=(xk)收敛于 x=(x)的惟一根.,不动点迭代法的局

6、部收敛性及收敛阶,定理1.3 若(x)在方程x=(x)的根的邻域内有一阶连续的导数，且() 1,则迭代过程xk+1=(xk)具有局部收敛性证 由连续函数性质，存在的充分小邻域 : x-, 使当x 时，有 (x)L1 由微分中值定理有 (x)=(x)()=()x-x- 故(x)，由定理1.2知对任意初值x0 均收敛.,定理1.4 若(x)在方程x=(x)的根的邻域内有充分阶连续的导数，则迭代过程xk+1=(xk)是p阶收敛的充分且必要条件是 (j)()=0, j=1,2,p-1 (p)()0,证 充分性 必要性 （略）,例能不能用迭代法求解方程x=4-2x，如果不能时，试将方程改写成能用迭代法求

7、解的形式.,方程为x-4+2x =0.设f(x)= x-4+2x ，则f(1)0， f(x)= 1+2x ln20,故方程f(x)=0仅在区间(1, 2)内有唯一根.题中 (x)=4-2x，当时x(1,2)时, (x)=-2xln22ln21 ,由定理1.2不能用 来迭代求根. 把原方程改写为x=ln(4-x)/ln2, 此时(x)=ln(4-x)/ln2 , 则有 1当x1,2时， (x)1,ln3/ln2 1,2 2x(1,2) ，有 (x)= 由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求解(1,2)区间内的唯一根.,例设F(x)=x+c(x2-3)，应如何选取c才能使

8、迭xk+1=F(xk)代具有局部收敛性？,方程x=F(x)的根为 ，函数F(x)在根附近具有连续一阶导数，又F (x)=1+2cx，解 得解 得从而使迭代xk+1=F(xk) 具有局部收敛性,则 ，且c0. 令 得 ；令 得 .这时 为平方收敛.故当c取 时，这个迭代收敛较快.,例 设a0,x00,证明:迭代公式是计算 的三阶方法.,证 显然当a0，x00时，xk0（k=1,2,）.令 (x)=x(x2+3a)/(3x2+a)则故对 ，从而迭代收敛.设xk的极限为l，则有解得 .由题知取 .即迭代序列收敛于 .故此迭代式确是求 的三阶方法.,Newton迭代法,Newton迭代法,设有方程f(

9、x)=0，在f(x)=0的根附近任取一点x0作为初始近似根，由迭代公式 逐次逼近方程f(x)=0的根 ，这种求根算法称为Newton法（切线法），此公式称为Newton迭代公式.,Newton迭代法的收敛性及收敛阶,Newton法的迭代函数是从而 由此知若是f(x)=0的一个单根, f()=0, f()0, ()=0, ()=f()/f(), 则在根附近Newton法是局部收敛的, 并且是二阶收敛的,即 p=2.但如果是f(x)=0的重根，则Newton法仅是线性收敛的 ,即 p=1.,事实上，若是f(x)=0的重根，设其重数为r,Newton迭代法的全局部收敛性,定理1.5 设f(x)在有根

10、区间a, b上二阶导数存在，且满足 (1) f(a)f(b)0;则 Newton 迭代法收敛于f(x)=0在a, b内的惟一根.,例 研究求 的Newton公式证明：对一切 ,且序列xk是单调递减的，从而迭代过程收敛.,证 因a0，x00,故xk0 (k=1,2,).因此对一切k1,均有 ,利用这一结果，得故xk+1xk,即xk单调递减.根据单调有界原理知,xk收敛,例 设a为正实数，试建立求 的Newton迭代公式，要求在迭代函数中不用除法运算，并要求当取初值x0满足 时，此算法是收敛的.,解 考虑方程则 为此方程的根， ，用Newton法求此方程根的迭代公式为迭代函数不含除法运算.递推可得

11、,解得当 时， ，从而故 ，此算法收敛.,简化 Newton法与Newton下山法,简化 Newton法一般地，取C= f(x0). 若 是一阶收敛的.Newton下山法其中为下山因子，的选取应满足条件: f(xk+1)f(xk)保证所得序列是收敛的.,重根情形,已知根的重数r将Newton法修正为它是求r重根的二阶收敛格式.记ek+1 = -xk+1 =记由f()=f()=f (r-1)()=0有G (j)()=0, j=0,1,2,r ; G (r+1)()=-f (r+1)(),在处将G(xk), f(xk)Taylor展开从而它具有二阶收敛格式.,根的重数未知将Newton法修正为 其

12、中u(x)=0单根就是f(x)=0的r重根，故它是求f(x)=0重根的二阶收敛格式. 事实上 为u(x)=0单根.,例 方程x4-4x2+4=0的根= 是二重根，用下列方法求根 (1) Newton迭代法(1.3.11); (2)修正的Newton迭代法 (1.5.2); (3)修正的Newton迭代法 (1.5.4),解 三种方法的迭代公式： Newton迭代法 修正的Newton迭代法 (1.5.2)修正的Newton迭代法 (1.5.4)取初值x0=1.5,计算结果如表：计算三步方法(2)和方法(3)均达到10位有效数字，而牛顿法只有线性收敛，要达到同样精度，需迭代30次.,弦截法,弦截

13、法,在方程f(x)=0的根附近任取两初始近似根x0 ,x1 ，由迭代公式 逐次逼近f(x)=0的根 ，这种求根算法称为弦 截法. 收敛阶 ，效率指数,迭代加速收敛的方法,Aitken加速收敛方法,当序列xk为线性收敛时当k较大时, , ,称为Aitken加速收敛方法,Steffensen加速迭代法,若xk为由不动点迭代法得到的序列，又称为Steffensen加速迭代法. 当不动点迭代函数(x)在根的某邻域内具有二阶导数，()=L1,且L0，则Steffensen迭代法是2阶收敛的.,利用加速方法确定根的重数r,Newton迭代法收敛缓慢时，表明有重根.当根为重根时，Newton迭代法为线性收敛

14、，当接近收敛时， ,利用加速公式有,解非线性方程组的 拟Newton迭代法,非线性方程组的一般形式为令上述方程组可表示为 F(x)=0,给定非线性方程组F(x)=0，如果有x使得F(x)=0，则称x为F(x)=0的解.当n=1时，便是单个方程(非线性方程) f(x)=0,Newton法,若已知方程组F(x)=0的一个近似解xk=(x1k, x2k, xnk), 将F(x)的分量fi(x)在xk处用多元函数Taylor展开，取其线性部分有 F(x)F(xk)+F(xk)(x-xk ) 用线性方程组 F(xk)(x-xk )=F(xk)的解作为近似解便得解非线性方程组的Newton法 xk+1=x

15、k F(xk)-1F(xk)记Ak= F(xk),有,xk+1=xk-Ak-1F(xk) 其中为F(x)的Jaccobi矩阵.,例用Newton法求解方程组取x0=(1.5,1.0),解 Jacobi矩阵其Newton法为由 x0=(1.5,1.0)逐次迭代求得 x1=(1.5,0.75) x2=(1.488095, 0.755952) x3 =(1.488034, 0.755983) x3的每一位都是有效数字.,拟Newton法,依据k的不同的取法可建立不同的拟Newton法.任何nn秩m矩阵都能表示成UVT形式，其中U,V为秩m的nm矩阵. 若nn矩阵非奇异，则 (+UVT)-1=-1-1

16、U(E+VT-1U)-1VT-1 (SMW公式),若Ak (对一切k)可逆,记Hk=Ak-1Ak+1-1 =(k+k)-1=(k+UkVkT)-1 =k-1k-1Uk(E+VkTk-1Uk)-1VkTk-1 与其互逆的迭代格式为,秩1拟Newton法,设Ak=ukvkT ,ukvkRn 记rk=xk+1-xk ,yk=F(xk+1)-F(xk), 有 Ak+1rk=yk, Ak+1=Ak+ukvkT, (Ak+ukvkT) rk=yk, ukvkTrk=ykAkrk它确定的Ak+1满足拟Newton方程,从而建立了秩1拟Newton法,若k非奇异，则 (SM公式) Hk+1=Hk+Hk得到与之

17、互逆的秩1拟Newton法,1.Broyden秩1方法若取vk=rk0，于是得到一个秩1拟Newton法称之为Broyden秩1方法.它具有超线性收敛速度.与其互逆的秩1方法,2.对称秩1方法若取vk=F(xk+1)， ykAkrk =F(xk+1)F(xk)Akrk=F(xk+1)=vk于是由(2o)可得修正矩阵Ak对称，若A0对称，所有Ak(k=0,1,2)都对称,从而得到一个对称的秩1方法,与其互逆的秩1方法,例用逆Broyden方法求方程组的解，取x0=(0,0),解F(x0)=(-1,3.25)用逆Broyden方法迭代求解得 x1=(1.0625,-1)， r0=(1.0625,-1), F(x1)=(1.12890625,2.12890625) , y0=(2.12890625,-1.1210937),进行第二次迭代 ，迭代11次得解 x11=(1.54634088332, 1.39117631279) 若用Newton法求解，取相同的初始值x0 ，达到同一精度只需迭代7次，但它的计算量比逆Broyden方法大得多.,