非线性方程数值解法

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

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

3、主要问题n收敛性n收敛速度n计算效率迭代法的全局收敛性 n定义1 设为f(x)=0的根，如果x0a, b，由迭代法产生的序列都收敛于根 ，则称该迭代法是全局收敛的.迭代法的局部收敛性 n定义定义2 设方程x=(x)有根, 如果存在的某个邻域 : x-，对任意初值x0，迭代过程所产生的序列均收敛于根 ，则称该迭代法是局部收敛的.迭代过程的收敛速度 n定义定义3 设迭代过程xk+1=(xk)产生的序列 收敛于方程x=(x)的根 ，记 ek =- xk ，若则称迭代过程是p阶收敛的.特别地，当p=1时，称为线性收敛； 当p1时，称为超线性收敛， 当p=2时，称为平方收敛. p越大，收敛越快.1lim

4、0kpkkeCe 0kkx效率指数n定义定义3 称为效率指数. 其中p表示迭代的收敛阶，表示每步迭代的计算量. EI越大，计算效率越高.1pEI 不动点迭代法不动点迭代法的整体收敛性n定理1.1 设(x)满足 (1)当xa, b时，(x)a, b ； (2)x1, x2a, b ，有 (x1)-(x2)Lx1-x2 ， L1 则对任意初值x0 a, b, 迭代过程 xk+1=(xk)收敛于 x=(x)在a, b上的惟一根 ，且有误差估计式11011kkkkkLxxxLLxxxLn证 根的存在性 由(2)知(x)连续. 令f(x)=x-(x), f(a)0, f(b)0, 从而f(x)=0在a,

5、 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-=(xk)-()Lxk- , xk+1-Lk+1x0- 由0L1有 limkkx 误差估计 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，有111pkkL

6、LxxL11011kkkkkLxxxLLxxxLn定理1.2 设(x)在a, b上具有一阶导数，且 (1)当xa, b时, (x)a, b ； (1) xa, b ，有(x)L1则对任意初值x0 a, b, 迭代过程 xk+1=(xk)收敛于 x=(x)在a, b上的惟一根. 不动点迭代法的局部收敛性及收敛阶n定理1.3 若(x)在方程x=(x)的根的邻域内有一阶连续的导数，且() 1,则迭代过程xk+1=(xk)具有局部收敛性n证 由连续函数性质，存在的充分小邻域 : x-, 使当x 时，有 (x)L1 由微分中值定理有 (x)=(x)()=()x-x- 故(x)，由定理1.2知对任意初值x

7、0 均收敛.n定理1.4 若(x)在方程x=(x)的根的邻域内有充分阶连续的导数，则迭代过程xk+1=(xk)是p阶收敛的充分且必要条件是 (j)()=0, j=1,2,p-1 (p)()0n证 充分性 1( )1lim( )0!kppkkxpx1()kkxx( )11( )()!ppkkxxp(1)1( )11( )( )()( )()( )()(1)!ppppkkkxxxpp n必要性(反证法) 设迭代法xk+1=(xk)是p阶收敛的，如果结论不成立，那么必有最小正整数p0p，使得 (j)()=0, j=1,2, p0-1 (p0)()0 由充分性的证明知此迭代法是p0阶收敛 的，矛盾.必

8、要性得证.例能不能用迭代法求解方程x=4-2x，如果不能时，试将方程改写成能用迭代法求解的形式. n方程为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，当时x1,2时, (x)=-2xln22ln21 ,由定理1.2不能用 来迭代求根. 把原方程改写为x=ln(4-x)/ln2, 此时(x)=ln(4-x)/ln2 , 则有 1当x1,2时， (x)1,ln3/ln2 1,2 2x1,2 ，有 (x)= 由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求

9、解(1,2)区间内的唯一根. 142kxkx1111114ln242 ln22ln2x例设F(x)=x+c(x2-3)，应如何选取c才能使迭xk+1=F(xk)代具有局部收敛性？ n方程x=F(x)的根为 ，函数F(x)在根附近具有连续一阶导数，又F (x)=1+2cx，解 得解 得从而使迭代xk+1=F(xk) 具有局部收敛性,则 ，且c0. 令 得 ；令 得 .这时 为平方收敛.故当c取 时，这个迭代收敛较快. 123,3 (3)1 2 31Fc 103c12 31c13c 103c)3(F(3)12 30Fc 12 3c ( 3)12 30,Fc 12 3c ( )20Fxc12 3例

10、设a0,x00,证明:迭代公式是计算 的三阶方法.n证法一 显然 是方程x=x(x2+3a)/(3x2+a)的根.事实上此方程有根 0, 若a0，x00，则xk0（k=1,2,）. 当x00时， .事实上212(3 )3kkkkxxaxxaaaaalimkkxa23122(3 )()33kkkkkkxxaaxaxaxaxa23122(3 )()33kkkkkkxxaaxaxaxaxa2121333110333110()()()()()()kkkkkkkkaxaxaxaxaxaxaxax300()kkkaxaxaxax令 解得由|q|1有即迭代序列收敛于故此迭代式确是求 的3阶方法.00axqa

11、x331()1kkkqxaq331limlim()1kkkkkqxaaqa12311limlim034()kkkkkaxxaaaxa n证法二 迭代函数(x)=x(x2+3a)/(3x2+a)故此迭代式是求 的3阶方法.()aaa()0a3()02aa()0aNewton迭代法Newton迭代法 n设有方程f(x)=0，在f(x)=0的根附近任取一点x0作为初始近似根，由迭代公式 逐次逼近方程f(x)=0的根 ，这种求根算法称为Newton法（切线法），此公式称为Newton迭代公式.1()(0,1,2,)()kkkkf xxxkfxNewton迭代法的收敛性及收敛阶nNewton法的迭代函数

12、是从而 由此知若是f(x)=0的一个单根, f()=0, f()0, ()=0, ()=f()/f(), 则在根附近Newton法是局部收敛的, 并且是二阶收敛的,即 p=2.但如果是f(x)=0的重根，则Newton法仅是线性收敛的 ,即 p=1. ( )( )( )f xxxfx2( )( )( )( )f x fxxfx1112EI事实上，若是f(x)=0的重根，设其重数为r, ( )1( )2( )1( )( )()()()rrfxxxr f ( )( )1( )lim10,( )1xxxr ( )( )( )f xxxfx( )1( )2()1()()rrfxxr f(1)1( )1

13、(1)2( )1211( )( )()( )()()()(1)!11( )( )()( )()()()(2)!(1)!rrrrrrrrffxfxfxrrxffxfxfxrrNewton迭代法的全局部收敛性n定理1.5 设f(x)在有根区间a, b上二阶导数存在，且满足 (1) f(a)f(b)0;则 Newton 迭代法收敛于f(x)=0在a, b内的惟一根. 例 研究求 的Newton公式证明：对一切 ,且序列xk是单调递减的，从而迭代过程收敛.n证 因a0，x00,故xk0 (k=1,2,).因此对一切k1,均有 ,利用这一结果，得故xk+1xk,即xk单调递减.根据单调有界原理知,xk收

14、敛a101(),0(0,1,2,)2kkkaxxxkx1,2,kkxa121()21()2kkkkkaxxxaxaaxkxa12/111122222kkkkkkxxa xaaxxxa例 设a为正实数，试建立求 的Newton迭代公式，要求在迭代函数中不用除法运算，并要求当取初值x0满足 时，此算法是收敛的.n解 考虑方程则 为此方程的根， ，用Newton法求此方程根的迭代公式为迭代函数不含除法运算.递推可得1a020 xa1( )0f xax21( )fxx 1a1()(2)(0,1,2,)()kkkkkkf xxxxaxkfx2111(2)(1)(0,1,2,)kkkkaxaxaxaxk

15、201(1)(0,1,2,)kkaxaxk解得当 时， ，从而此算法收敛.2011(1) (0,1,2,)kkxaxka020 xa011ax20lim(1)0kkax1limkkxa简化 Newton法与Newton下山法n简化 Newton法一般地，取C= f(x0). 若 是一阶收敛的.nNewton下山法其中为下山因子，的选取应满足条件: f(xk+1)f(xk)保证所得序列是收敛的.1(),0,1,2,kkkf xxxkC1()(01),0,1,2,()kkkkf xxxkfx( )( )11,fxxC重根情形n已知根的重数r将Newton法修正为它是求r重根的二阶收敛格式.记ek+

16、1 = -xk+1 =记由f()=f()=f (r-1)()=0有G (j)()=0, j=0,1,2,r ; G (r+1)()=-f (r+1)()1()0,1,2,()kkkkf xxxrkfx()()kkkf xxrfx()()()()kkkkxfxrf xfx( )()( )( )G xx fxrf x( )( )(1)( )( )( )()( )( )jjjjGxrfxx fxjfx在处将G(xk), f(xk)Taylor展开从而它具有二阶收敛格式.(1)11(1)211( )( )1221()()(1)!1(1)()()(1)!rrkrkkrrrkGeGreer rffer(1

17、)12( )1( )lim0(1)( )rkrkkeGer rfn根的重数未知将Newton法修正为 其中u(x)=0单根就是f(x)=0的r重根，故它是求f(x)=0重根的二阶收敛格式. 事实上，设是f(x)=0的r重根 为u(x)=0单根.1()0,1,2,()kkkku xxxku x( )( )( )f xu xfx1( )()( )( )( )()( )()( )rrrf xxg xu xfxr xg xxg x( )()( )()( )g xxrg xxg x例 方程x4-4x2+4=0的根= 是二重根，用下列方法求根 (1) Newton迭代法(1.3.11); (2)修正的Ne

18、wton迭代法 (1.5.2); (3)修正的Newton迭代法 (1.5.4)n解 三种方法的迭代公式： Newton迭代法 修正的Newton迭代法 (1.5.2)修正的Newton迭代法 (1.5.4)取初值x0=1.5,计算结果如表：计算三步方法(2)和方法(3)均达到10位有效数字，而牛顿法只有线性收敛，要达到同样精度，需迭代30次.2kkkkxxxx4221212(2)2kkkkkxxxxx2122kkkkxxxxkxk方法(1)方法(2)方法(3)1x11.4583333331.4166666671.4117647062x21.4366071431.4142156861.4142

19、114383x31.4254976191.4142135621.414213562弦截法 弦截法 n在方程f(x)=0的根附近任取两初始近似根x0 ,x1 ，由迭代公式 逐次逼近f(x)=0的根 ，这种求根算法称为弦 截法. 收敛阶 ，效率指数111()(0,1,)()()kkkkkkkxxxxf xkf xf x251p152EI迭代加速收敛的方法Aitken加速收敛方法当序列xk为线性收敛时当k较大时, , ,称为Aitken加速收敛方法1lim0kkkxCx21()kkxCx1()kkxCx2211212kkkkkkkx xxxxxx221212kkkkkkx xxxxx121kkkkx

20、xxx1lim0kkkxCxSteffensen加速迭代法若xk为由不动点迭代法得到的序列，将Aitken加速收敛技巧与不动点迭代结合得如下迭代法: 又称为Steffensen加速迭代法.2211212kkkkkkkx xxxxxx1()kkxx21()kkxx 当不动点迭代函数(x)在根的某邻域内具有二阶导数，()=L1,且L0，则Steffensen迭代法是2阶收敛的. 有时即使原来不收敛的迭代法，利用Steffensen加速迭代法仍可能收敛；至于原来收敛的迭代法它可达到2阶收敛；更进一步对于原来p阶收敛的迭代法，Steffensen加速迭代法为p+1阶收敛.利用加速方法确定根的重数rNe

21、wton迭代法收敛缓慢时，表明有重根.当根为重根时，Newton迭代法为线性收敛，当接近收敛时， ,利用加速公式有11lim1kkkaxaxr 221121212112kkkkkkkkkkkx xxxrxxxxxxx221111kkkkxerxe121kkkxrxx解非线性方程组的 拟Newton迭代法 n非线性方程组的一般形式为令上述方程组可表示为 F(x)=00),(0),(0),(21212211nnnnxxxfxxxfxxxf1122( )0( )0( ),( )0nnf xxfxxF xxfxx 0n给定非线性方程组F(x)=0，如果有x 使得F(x )=0，则称x 为F(x)=0的

22、解.n当n=1时，便是单个方程(非线性方程) f(x)=0Newton法n若已知方程组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=xk F(xk)-1F(xk)记Ak= F(xk),有 xk+1=xk-Ak-1F(xk) 其中为F(x)的Jaccobi矩阵.111122221212( )nnnnnnfffxxxfffxxxF xfffxxx

23、例用Newton法求解方程组取x0=(1.5,1.0)n解 Jacobi矩阵其Newton法为由 x0=(1.5,1.0)逐次迭代求得 x1=(1.5,0.75) x2=(1.488095, 0.755952) x3 =(1.488034, 0.755983) x3的每一位都是有效数字.112122221212( ,)230( ,)250f x xxxfx xxx1212( )42F xxx21121221( )4128xF xxxx( )( )( )1212( )( )( )( )2( )2211122223128412()()5kkkkkkkkkkxxxxxxxxxx拟Newton法依据k

24、的不同取法可建立不同的拟Newton法.n任何nn秩m矩阵都能表示成UVT形式，其中U,V为秩m的nm矩阵. 若nn矩阵非奇异，则 (+UVT)-1=-1-1U(E+VT-1U)-1VT-1 (SMW公式)1-11111-()()()()()1kkkkkkkkkkkkkxxA F xAxxF xF xAAArankAmn若Ak (对一切k)可逆,记Hk=Ak-1Ak+1-1 =(k+k)-1=(k+UkVkT)-1 =k-1k-1Uk(E+VkTk-1Uk)-1VkTk-1 Hk+1 =HkHkUk(E+VkTHkUk)-1VkTHk与其互逆的迭代格式为11111-() ()()(),()1k

25、kkkkkkkkkkkkxxH F xHF xF xxxHHHrankHm秩1拟Newton法 rank(Ak)=1 设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法T1()(1 )kkkkkkuyA rv rT1()(2 )kkkkkkkAyA rvv r11TT1T()1(),0,0,1,2,.kkkkkkkkkkkkkkxxA F xAAyA rvvrkvrn若k非奇异，则 (SM公式) Hk+1=Hk+Hk得到与之互逆的秩1拟Newton法 11111()(1)kkkkkkkkkkkAu vAAu vAvAu1 )()1kkkkkkkkkkkkkkkkH u v HrH yv HHv H uv H y 代入(1TT1T()(),0kkkkkkkkkkkkkkkkkxxH F xv HHHrH yvH yv H yn1.Broy