数值分析教学课件：4非线性方程求解

第四章非线性方程数值求解NumericalAnalysis§4.1一元方程求根华长生制作11）问题的提出

满足函数方程f(x)=0(1)的x称为方程(1)的根，或称为函数f(x)的零点。如果函数(x)可分解为

(x)=(xs)mg(x)且g(s)0,则称s是(x)的m重零点或(x)=0的m重根。当m=1时，称s是(x)的单根或单零点。若f(x)不是x的线性函数,则称(1)为非线性方程,

特别地,若f(x)是n次多项式，则称(1)为n次多项式方程或代数方程；若f(x)是超越函数，则称(1)为超越方程。2理论上已证明，对于次数n<=4的多项式方程,它的根可以用公式表示,而次数大于5的多项式方程,它的根一般不能用解析表达式表示.因此对于f(x)=0的函数方程,一般来说,不存在根的解析表达式,而实际应用中,也不一定必需得到求根的解析表达式,只要得到满足精度要求的根的近似值就可以了。常用的求根方法分为区间法和迭代法两大类。求根问题包括：根的存在性、根的范围和根的精确化。求根方法中最直观最简单的方法是二分法。32)预备知识定理1.(根的存在定理)

假设函数y=f(x)Ca,b,且f(a)·f(b)<0,则至少存在一点x(a,b)使得f(x)=0.(并称区间(a,b)为有根区间)定理2.

假设函数y=f(x)在a,b上单调连续,且f(a)·f(b)<0,则恰好只存在一点x(a,b)使得f(x)=0定理3.

假设函数y=f(x)在x=s的某一邻域内充分可微，则s是方程f(x)=0的m重根的充分必要条件是

41)问题给定方程f(x)=0,设f(x)在区间[a,b]连续,且f(a)f(b)<0,则方程f(x)在(a,b)内至少有一根

,为便于讨论,不妨设方程f(x)=0在(a,b)内只有一个(重根视为一个)实根，求满足精度要求的近似值实根。2)概念及基本思想概

念：二分法也称对分区间法、对分法等，是最简单的求根方法，属于区间法求根类型。

基本思想：利用连续函数的零点定理，将含根区间逐次减半缩小，就可以构造出收敛点列来逼近根。

53)构造原理定理1.(根的存在定理)

这个原理指出了根的存在区间可由两端点处的函数值是否反号确定，那么注意到，将含根区间分为两个长度相等的子区间后，在这两个子区间上也可利用零点原理确定根在那个子区间上，如此继续下去就达到将含根区间逐步缩小的目的，此时，在这一些相互包含的子区间中构造收敛的数列将它收敛于根，见下图

6abξx1x2x3xf(x)74)解题思路

89101xx*收敛比较慢的情况：

控制循环（K）的方法：

11由得因此只要对分次，则有注：因为为的一个端点，所以将区间对分后，取的中点作为的近似值，满足

?12①简单并保证收敛;②对f(x)

要求不高(只要连续即可).①无法求复根②收敛慢(仅与一个以1/2为比值的等比级数相同)

调用一次求解一个[a,b]间的多个根无法求得二分法的优缺点13确定根所在的范围［a,b］对有的函数也是一件困难的事。所幸的是，在实际应用中，根据其物理或工程的背景，在绝大部分场合是不困难的。对给定的函数也有确定范围的方法。14第四章非线性方程数值求解NumericalAnalysis§4.2不动点迭代法及其收敛定理华长生制作15

迭代法是求解非线性方程近似根的一种方法，这种方法的关键是确定迭代函数(x)，简单迭代法用直接的方法从原方程中隐含地求出x，从而确定迭代函数(x)，这种迭代法收敛速度较慢，迭代次数多，因此常用于理论中,Newton迭代法采用另一种迭代格式,具有较快的收敛速度，由牛顿迭代法可以得到很多其他迭代格式。迭代法求非线性方程的根16简单迭代法(基本迭代法)迭代法的建立与收敛性（1）17需要讨论的问题首先期望每个xk都在(x)的定义域上,保持有界而且收敛到精确解;如何选取适合的迭代函数

(x);

迭代函数

(x)迭满足什么条件,迭代序列收敛到精确解,收敛速度如何;怎样加速序列{xk}的收敛速度.18定理4.1(压缩性)说明:条件(2)可用更强更便于应用的条件代替:（映内性）(2)(3)19证:1o20：设方程在区间内有根，则有由故据此反复递推有故当时迭代值,即证.9

10定理4.1指出:只要构造的迭代函数满足由(2)式,只要因此,当迭代就可以终止,迭代终止的判断准则注：L越小，收敛越快。23改进条件：

24改进条件：

25定义1：如果存在的某个邻域，使迭代过程对于任意初值均收敛，则称迭代过程在根邻近具有局部收敛性。定理4.2设为方程的根，在的邻域存在且连续并满足,则迭代过程局部收敛。13例解:本题迭代函数有两种构造形式:,迭代法发散.(2)迭代法收敛.(1)27迭代法的收敛阶(描述收敛速度)

定义2.:设

若有实数p>0,使

则称序列是p阶收敛,相应的迭代法称为p阶方法.特别地,

p=1,称线性收敛;

1<p<2,称超线性收敛;

p=2,称平方收敛。(4)28判别收敛阶的两定理29定理4.4：对于迭代过程，如果在所求根的邻近连续，并且:

(*),则该迭代过程在点邻近是P阶收敛的。证明省!1131第四章非线性方程数值求解NumericalAnalysis§4.3Newton迭代法华长生制作32

§4.3Newton迭代法将f(x)在点xn作Taylor展开:

——Taylor展开线性化f(x)=0

近似于

f(xn)+f′(xn)(x-xn)=0(1)从(1)解出x,

记为xn+1,则1.Newton迭代公式建立33它对应的迭代方程为显然是f(x)=0的同解方程，故其迭代函数为

在f(x)=0的根x*

的某个邻域内,在x*

的邻域R内，对任意初值，应用公式（2）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一.42.Newton迭代法的几何意义

与x轴(y=0)的交点x，作为下一个迭代点xn+1,即

用f(x)在xn

处的切线Newton迭代法又称切线法.353、牛顿迭代法的步骤步一、准备。选定初始近似值，计算步二、迭代。按公式迭代一次，得到新的近似值，计算步三、控制。如果满足或.则终止迭代，以作为所求的根；否则转步四。此处是允许误差,15而 其中c是取绝对误差或相对误差的控制常数，一般可取c=1。步四、修改。如果迭代次数达到预定指定的次数N，或者 ,则方法失败；否则以代替转步二继续迭代。16例

用Newton迭代法求下面方程的一个正根,计算结果精确到7位小数.解:由Newton迭代法x1

=1.4666667,…,x4

=1.3688081x5

=1.3688081迭代5次精度达10-7x*

≈

1.368808384.Newton迭代法收敛定理（1）Newton迭代公式在单根情况下至少2阶收敛;

（2）

定理4.3.1

设f(x*)=0,,且在x*

的邻域上存在,连续,则可得证：将f(x)在xn

处作2阶Taylor展开,并将解x*代入注意到ξn在xn

及x*之间,及,故39

所以，Newton法至少二阶收敛.

注意到ξn在xn

及x*之间,及,故40

Newton法在重根情形下的收敛阶20

Newton迭代法的特征

Newton迭代公式是一种特殊的不动点迭代,其迭代函数为:

Newton迭代是局部线性化方法,它在单根附近具有较高的收敛速度.

方法有效前提:425.Newton迭代法的应用----------开方公式

对于给定正数应用牛顿迭代法解二次方程可导出求开方值的计算公式设是的某个近似值，则自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。

定理

开方公式对于任意给定的初值均为平方收敛。

43牛顿迭代法的优缺点优点：

在单根附近,牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。

缺点:1.重根情形下为局部线性收敛;2.牛顿迭代法计算量比较大:因每次迭代除计算函数值外还要计算导数值;3.选定的初值要接近方程的解，否则有可能得不到收敛的结果;21牛顿迭代法的改进缺点克服:

1.重根为局部线性收敛------改进公式或加速2.每步都要计算导数值-----简化Newton迭代法

或弦截法3.初值近似问题-------二分法求初值或”下山算法”21方法一.若已知重数m(m>1),则利用m构造新的迭代公式:此时,,至少2阶收敛.不实用:m往往不确定.方法二.取,再对函数F(x)用Newton迭代:此时,X*为F(x)的单根,所以是2阶收敛.但要用到二阶导数.6.Newton法的改进(I)---重根情形46Newton迭代法需要求每个迭代点处的导数f’(xk)复杂！这种格式称为简化Newton迭代法精度稍低6.Newton法的改进(II)47则Newton迭代法变为这种格式称为弦截法(割线法)（书P111例题4.7）收敛阶约为1.61848

例4.4用简化Newton法和弦截法解下面方程的根，并和Newton迭代法比较

解:由简化Newton法由弦截法由Newton迭代法49x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550x7=0.3472959759x8=0.3472964208x9=0.3472963440x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553简化Newton法由弦截法要达到精度10-8简化Newton法迭代11次弦截法迭代5次Newton迭代法迭代4次x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553由Newton迭代法50无论哪种迭代法：Newton迭代法简化Newton法弦截法用Newton迭代法求解:x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收敛均与初值的位置有关.例:x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.963110-10x5=0收敛发散迭代法的局部收敛性516.Newton法的改进(III):牛顿下山法一般地说，牛顿法