第七章 非线性方程求根

一、重点内容提要 （一）问题简介 求单变量函数方程

f(x)?0 (7.1)

的根是指求x*（实数或复数），使得f(x*)?0.称x*为方程(7.1)的根,也称x*为函数f(x)mf(x)?(x?x*)g( x)f(x)的零点.若可以分解为

其中m为正整数,g(x)满足g(x)?0,则x*是方程(7.1)的根.当m=1时,称x*为单根;当m>1时,称x*为m重根.若g(x)充分光滑,x*是方程(7.1)的m重根,则有

(m?1)(m)f(x*)?f'(x*)?...?f(x*)?0,f(x*)?0

若f(x)在[a,b]上连续且f(a)f(b)?0,则方程(7.1)在(a,b)内至少有一个实根,称[a,b]为方程(7.1)的有根区间.有根区间可通过函数作图法或逐次搜索法求得.

(二)方程求根的几种常用方法 1.二分法

设f(x)在[a,b]上连续,f(a)f(b)?0,则f(x)?0在(a,b)内有根x*.再设f(x)?0在(a,b)内

1x0?(a0?b0)a?a,b0?b,计算f(x0).若f(x0)?0则x*?x,结束计2仅有一个根.令0和

算;若

f(a0)f(x0)?0,则令a1?x0,b1?b,得新的有根区间[a1,b1];若f(a0)f(x0)?0,则令

1b?a?(b0?a0)11a1?a0,b1?x0[a,b][a,b]?[a,b]1100112,得新的有根区间.,.再令1x1?(a1?b)1f(x1),同上法得出新的有根区间[a2,b2],如此反复进行,可得一有根区2计算

间套

...?[an,bn]?[an?1,bn?1]?...?[a0,b0]

11an?x*?bn,n?0,1,2,...,bn?an?(bn?1?a?1)?...?n(b0?a0)22且. 1lim(bn?an)?0,limxn?lim(an?bn)?x*n??n??2故 n??

因此,

xn?1(an?bn)2可作为f(x)?0的近似根,且有误差估计

2.迭代法

|xn?x*|?1(b?a)2n?1 (7.2)

将方程式(7.1)等价变形为 x??(x) (7.3)

若要求x*满足f(x*)?0则x*??(x*);反之亦然.称x*为函数?(x)的一个不动点.求方程(7.1)的根等价于求?(x)的不动点由式(7.3)产生的不动点迭代关系式(也称简单迭代法)为

xk?1??(xk)k,?0,1, 2... (7.4)

xk?1??(xk),k?0,1,2...,由式(7.4)产生的序列?xk?有

函数?(x)称为迭代函数.如果对任意极限

limxk?x*k??

则称不动点迭代法(7.4)收敛.

定理7.1(不动点存在性定理)设?(x)?C[a,b]满足以下两个条件: 1.对任意x?[a,b]有a??(x)?b;

2.存在正常数L?1,使对任意x,y?[a,b],都有|?(x)??(y)|?|x?y| (7.5) 则?(x)在[a,b]上存在惟一的不动点x*.

定理7.2(不动点迭代法的全局收敛性定理)设?(x)?C[a,b]满足定理7.1中的两个条件,则对任意

x0?[a,b],由(7.4)式得到的迭代序列?xk?收敛.到?(x)的不动点,并有误差估计式

|xk?x*|?L|xk?xk?1|1?L (7.6)

Lk|xk?x*|?|xk?xk?1|1?L和 (7.7)

定理7.3(不动点迭代法的局部收敛性定理)设x*为?(x)的不动点,?'(x)在x*的某个邻域连续,且|?'(x)|?1,则迭代法(7.4)局部收敛.

收敛阶的概念 设迭代过程(7.4)收敛于方程x??(x)的根x*,如果迭代误差

ek?xk?x*当k??时成产下列渐近关系式

ek?1?C(常数C?0)e k (7.8)

则称该迭代过程是p阶收敛的.特别地,p=1时称线性收敛,p>1时称超线性收敛,p=2时称平方

收敛.

(K)?(x)在所求根x*的邻近连续,并且 定理7.4(收敛阶定理)对于迭代过程(7.4),如果

?'(x*)??''(x*)?...??(p?1)(x*)?0?(p)(x*)?0

则该迭代过程在点x*的邻近是收敛的,并有

(7.9)

lim

ek?11(p)??(x*)k??epp!k (7.10)

斯蒂芬森(Steffensen)迭代法 当不动点迭代法(7.4)只有线性收敛阶,甚至于不收敛时,可用斯

蒂芬森迭代法进行加速.具体公式为

yk??(xk),zk??(yk)(yk?xk)2xk?1?xk?zk?2yk?xkk?0,1,2,... (7.11)

此法也可写成如下不动点迭代式

xk?1??(xk),k?0,1,2,...(?(x)?x)2?(x)?x??(?(x))?2?(x)?x (7.12)

定理7.5(斯蒂芬森迭代收敛定理) 设x*为式(7.12)中设?''(x)存在,?'(x*)?1,则x*是

?(x)的不动点,则x*是?(x)的不动点;

?(x)的不动点,则斯蒂芬森迭代法(7.11)是2阶收敛的.

3.牛顿迭代法

牛顿迭代法是一种特殊的不动点迭代法,其计算公式为

xk?1?xk? 其迭代函数为

f(xk),k?0,1,2,...f'(xk) (7.13)

?(x)?x?

f(x)f'(x)

牛顿迭代法的收敛速度 当f(x*)?0,f'(x*)?0,f''(x*)?0时,容易证