数值计算课件-第二章非线性方程的数值解法

第二章非线性方程的数值解法非线性方程求解的基本问题：根的个数；根的位置。 对于非线性方程，由于f(x)的多样性，求其根尚无一般的解析方法可以使用。求解方程的根，一般有两种情形：求出在给定范围内的某个根求出方程的全部根，而根的数目和位置事先不知道本章介绍几种方程求根的方法。这些方法大部分是要已知根的范围，而且在此范围内只有一个根。求非线性方程根的一些常用方法：区间分割法（逐步搜索法、二分法）迭代法牛顿法割线法2.1区间搜索法预备知识：方程的根：单根、重根。根的存在性定理：定理：若f在[a,b]上连续，且f(a)·f(b)<0，则f在(a,b)上必有一根；若f在[a,b]上连续且单调则f在(a,b)上有且仅有一根。定理函数f(x)对于x*有f(x*)=0，但则称为方程的单根。如果有但，则称是方程的m重根。2.1.1逐步搜索法思路：先把区间[a,b]均分为N等分，从初始值x0=a开始，步长h＝（b－a）/N来增值。每跨一步进行一次根的搜索。计算速度慢，一般用于确定根的位置例：求连续函数f(x)在有根区间[a,b]上的根。2.1.2二分法思路：二分法的基本思想就是逐步对分区间,经过对根的搜索，将有根区间的长度缩小到充分小，从而求出满足精度的根的近似值。二分法的步骤：

在有根区间取中点，计算函数值，若，就得到方程的实根，否则检查与是否同号，如同号，说明待求的根在的右侧，这时令；如在的左侧，这时令，这样新的有根区间的长度为之半。二分法abx0x1a1x*b1

对压缩了的有根区间又可施以同样的手续，即用中点将区间分为两半，然后判定待求的根在的哪一侧，从而又确定一个新的有根区间，其长度为的一半。如此反复，即可得出一系列有根区间其中的长度二分法每次二等分后，设取有根区间的中点作为根的近似值，则在二分过程中可以获得一个近似根的序列，该序列以根为极限。误差

分析：

若取区间的中点作为的近似值，则误差估计为：所以在实际计算时，只要二分足够多次，便有。这里，为预定精度。

二分法优点：简单，对f(x)

要求不高(只要连续即可).注：用二分法求根，最好先给出f(x)

草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，二分法二分法特点：缺点：收敛慢（等比级数）无法求复根及偶重根

对于给定的精度,可估计二分法所需的步数k：求方程f(x)=0的根的二分法算法2.2简单迭代法2.2.1迭代原理2.2.2迭代的收敛性2.2.3迭代的收敛速度2.2.4迭代的加速2.2简单迭代法f(x)=0x=φ(x)等价变换f(x)的根φ

(x)的不动点思路从一个初值x0

出发,计算x1=φ(x0),x2=φ(x1),…,xk+1=φ(xk),…若收敛，即存在x*使得

，只要φ

连续，则，也就是x*=φ(x*)，即x*是φ

的根，也就是f的根。若｛xk｝发散，则迭代法失败。2.2.1迭代法原理：

迭代法：是一种逐次逼近的方法。它是用某个固定公式反复校正根的近似值，使之逐步精确，最后得到满足精度要求的结果。xk+1=φ(xk)称为迭代格式，φ(x)称为迭代函数x0称为迭代初值,数列称为迭代序列

迭代法思想：将隐式方程的求根问题归结为计算一组显式xk+1=φ(xk)

，也就是说，迭代过程是一个逐步显式化的过程。x=φ(x)例题例2.2.1试用迭代法求方程在区间(1，2)内的实根。解：由建立迭代关系

k=10,1,2,3…….计算结果如下:例题精确到小数点后五位例题但如果由建立迭代公式仍取，则有，显然结果越来越大，是发散序列xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1简单迭代法收敛定理考虑方程x=φ(x),φ(x)在[a,b]上连续,若(I)对所有x[a,b]，有φ

(x)[a,b]；(II)存在0L<1，使所有

x[a,b]有|φ’(x)|L<1。则：1）方程x=φ(x)在[a,b]上的解x*存在且唯一。2）任取x0[a,b]，由迭代过程xk+1=φ

(xk)收敛于x*简单迭代法推论验后误差估计：误差估计式：验前误差估计：证明：①φ

(x)在[a,b]上有根？令有根②根唯一？反证：若不然，设还有，则在和之间。而③当k

时，

xk收敛到x*？3简单迭代法有根L<1④⑤可用来控制收敛精度L越收敛越快小注：定理条件非必要条件，对某些问题在区间[a,b]上不满足|φ’(x)|L<1，迭代也收敛。实际应用中还是用此定理判断收敛性，当不满足收敛条件时，改变迭代公式使之满足。3简单迭代法2.2.3迭代法局部收敛性

对以上定理中的条件⑴，所有，，一般不容易验证。实际使用迭代法时，通常总是在根

的邻域进行。

定义如果存在的某个邻域，是任意指定的正数，使迭代过程对于任意初值1均收敛，则迭代过程在根邻域具有局部收敛性。

证:由于，存在的充分小邻域，使成立，据微分中值定理，有:

注意到，又当时，故有:由收敛定理的条件⑴可以断定对于任意收敛。局部收敛性定理：设函数在的根邻近有连续的一阶导数，且，则迭代过程具有局部收敛性。由于在实际应用中根x*

事先不知道，故条件|φ′(x*)|<1无法验证。但已知根的初值x0在根x*邻域，又根据φ′(x)的连续性，则可采用

|φ′(x0)|<1来代替|φ′(x*)|<1，判断迭代的收敛性。

2.2.4迭代过程的收敛速度迭代过程的收敛速度，是指在收敛时迭代误差的下降速度。

定义：设迭代过程

收敛于

的根，令迭代误差，若存在常数和，使

，则称序列是阶收敛的，称渐近误差常数。

收敛速度是误差的收缩率，阶数越高，收敛得越快。特别地，时称线性收敛，时称平方收敛或二次收敛，时称超线性收敛。迭代法的收敛速度常用收敛阶表示

定理对迭代过程，若在所求根的邻域连续，且则迭代过程在邻域是阶收敛的.证:p28Q:

如何实际确定收敛阶？例题例：证明函数在区间[1，2]上满足迭代收敛条件。证明：例题

例题若取迭代函数，不满足收敛定理，故不能肯定收敛到方程的根。2.2.5迭代过程的加速

对于收敛的迭代过程,只要迭代足够多次,就可以使结果达到任意的精度。但有时迭代过程收敛缓慢,从而使计算量加大.因此迭代过程的加速是个重要的课题.常用迭代加速方法加权法埃特金加速法斯蒂芬生算法

Aitken加速：简单迭代法xyy=xy=

φ(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收敛得略快。

Steffensen加速：2.3牛顿迭代法2.3.1迭代公式的建立2.3.2牛顿迭代法的收敛情况2.3.3牛顿迭代法的修正法2.3牛顿法原理：将非线性方程线性化——Taylor展开取x0

x*，将f(x)在x0做一阶Taylor展开:，在x0和x*之间。将(x*

x0)2看成高阶小量，则有：线性化xyx*x0x1迭代公式：迭代函数：牛顿切线法2.3.2牛顿切线法的收敛情况

定理

（局部收敛性）设函数在包含的某邻域内有阶连续导数，是方程的单根，则当初值充分接近时，牛顿切线法收敛，且至少为二阶收敛。并有这里单根意味着：牛顿切线法2.3.2牛顿迭代法的收敛情况

定理设函数满足且在邻域连续，则牛顿迭代法在收敛，且至少为二阶收敛。并有牛顿切线法证明：牛顿法事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：只要f’(x*)0在单根附近收敛快牛顿切线法注：牛顿法收敛性依赖于x0的选取。x*x0x0x0具有局部恒收敛性，收敛性依赖于初值的选取。收敛性好（至少平方收敛）每次计算要计算导数，效率不高牛顿法特点：例题例1:用Newton法求的近似解。（取8位有效数字）。解：由零点定理。例题例题例2:用Newton法计算。解：牛顿迭代法算法框图Newton迭代法算法牛顿切线法改进牛顿法的改进与推广改进一：重根时的收敛速度及改进：Q1:若，牛顿法是否仍收敛？设x*是f的n重根，则：且。因为牛顿法事实上是一种特殊的不动点迭代，其中，则A1:

有局部收敛性，收敛慢（线性收敛）。Q2:如何加速重根的收敛？A2:

修正迭代格式（平方收敛）n证明过程见书p42改进二：

牛顿下山法——扩大初值范围的修正牛顿法：

原理：若由xk

得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。xkxk+1通过适当选取的保证函数值能单调下降牛顿切线法改进下山法：迭代过程中保证函数值单调下降，即牛顿下山法：将牛顿法与下山法结合使用的算法下山因子牛顿下山法几点讨论实用中从=1开始反复将减半计算。一旦单调下降则称“下山成功”。反之则称“下山失败”，需另选初值x0计算。牛顿切线法改进当≠1时。牛顿下山法只有线性收敛速度，但对初值的选取却可放的很宽。常用牛顿下山法选取初值。实用中常用牛顿下山法选取初值。为加快收敛速度，转入牛顿法来求解根的精确值。牛顿法每一步要计算f和f’，相当于2个函数值，且有些导数难求。为了避开导数的计算，用差商代替导数。x0切线

割线

切线斜率

割线斜率2.4弦截法：x2x1用割线斜率（差商）替换切线斜率，代入牛顿法迭代公式：上式中，固定弦的一个端点（x0,f(x0)），而另一端点变动，称为单点弦法。2.4.1单点弦法：单点弦法几何意义因为f(x*)=0，故求导数得

所以0<’(x*)<1，所以单点弦法仅为线性收敛。单点弦法收敛速度：迭代函数：当初值x0充分接近时很接近f’(x*)2.4.2双点弦法：为了加快收敛速度，弦的两个端点都在变动，称为双点弦法或称快速弦截法。迭代时需要2个初值xk和xk－1。双点弦法迭代公式：。双点弦法几何意义P1P2双点弦法收敛速度：双点弦截法的收敛性与牛顿迭代法一样，即在根的某个邻域内，f(x)有直至二阶的连续导数，且f’(x*)0，具有局部收敛性，同时在邻域