非线性方程数值解法详解

《非线性方程数值解法详解》由会员分享，可在线阅读，更多相关《非线性方程数值解法详解（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表示迭代的收敛阶，表示 每步迭代的计算量.

4、EI越大，计算效率越高.,不动点迭代法,不动点迭代法的整体收敛性,定理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矛盾.

5、故1= 2 序列的收敛性 xk+1-=(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-1 xk+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)收

6、敛于 x=(x)的惟一根.,不动点迭代法的局部收敛性及收敛阶,定理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=

7、4-2x，如果不能时，试将方程改写成能用迭代法求解的形式.,方程为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)区 间内的唯一根.

8、,例 设F(x)=x+c(x2-3)，应如何选取c才能使迭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，则有 解得 .由题知取 .即迭代序列收敛于 . 故此

9、迭代式确是求 的三阶方法.,Newton迭代法,Newton迭代法,设有方程f(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(

10、x)=0的重根，设其重数为r,Newton迭代法的全局部收敛性,定理1.5 设f(x)在有根区间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满足 时，此算法是收敛的.,

11、解 考虑方程 则 为此方程的根， ，用Newton法求 此方程根的迭代公式为 迭代函数不含除法运算. 递推可得,解得 当 时， ，从而 故 ，此算法收敛.,简化 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)()

12、=-f (r+1)(),在处将G(xk), f(xk)Taylor展开 从而它具有二阶收敛格式.,根的重数未知 将Newton法修正为 其中 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) 取初值

13、x0=1.5,计算结果如表： 计算三步方法(2)和方法(3)均达到10位有效数字，而牛顿法只有线性收敛 ，要达到同样精度，需迭代30次.,弦截法,弦截法,在方程f(x)=0的根附近任取两初始近似根x0 ,x1 ，由迭代公式 逐次逼近f(x)=0的根 ，这种求根算法称为弦 截法. 收敛阶 ，效率指数,迭代加速收敛的方法,Aitken加速收敛方法,当序列xk为线性收敛时 当k较大时, , , 称为Aitken加速收敛方法,Steffensen加速迭代法,若xk为由不动点迭代法得到的序列， 又称为Steffensen加速迭代法. 当不动点迭代函数(x)在根的某邻域内 具有二阶导数，()=L1,且L0

14、，则Steffensen 迭代法是2阶收敛的.,利用加速方法确定根的重数r,Newton迭代法收敛缓慢时，表明有重根. 当根为重根时，Newton迭代法为线性收敛， 当接近收敛时， , 利用加速公式有,解非线性方程组的 拟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 )=