第二章非线性方程的数值解法

第二章非线性方程的数值解法第一页，共五十七页，编辑于2023年，星期四求非线性方程根的一些常用方法：区间分割法（逐步搜索法、二分法）迭代法牛顿法割线法第二页，共五十七页，编辑于2023年，星期四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重根。第三页，共五十七页，编辑于2023年，星期四2.1.1逐步搜索法思路：先把区间[a,b]均分为N等分，从初始值x0=a开始，步长h＝（b－a）/N来增值。每跨一步进行一次根的搜索。计算速度慢，一般用于确定根的位置例：求连续函数f(x)在有限区间[a,b]上的根。2.1.2二分法思路：二分法的基本思想就是逐步对分区间,经过对根的搜索，将有根区间的长度缩小到充分小，从而求出满足精度的根的近似值。第四页，共五十七页，编辑于2023年，星期四二分法的步骤：

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

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

分析：

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

二分法第七页，共五十七页，编辑于2023年，星期四优点：简单，对f(x)

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

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

对于给定的精度,可估计二分法所需的步数k：第八页，共五十七页，编辑于2023年，星期四求方程f(x)=0的根的二分法算法第九页，共五十七页，编辑于2023年，星期四2.2简单迭代法2.2.1迭代原理2.2.2迭代的收敛性2.2.3迭代的收敛速度2.2.4迭代的加速第十页，共五十七页，编辑于2023年，星期四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迭代法原理：第十一页，共五十七页，编辑于2023年，星期四

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

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

，也就是说，迭代过程是一个逐步显式化的过程。x=φ(x)第十二页，共五十七页，编辑于2023年，星期四例题例2.2.1试用迭代法求方程在区间(1，2)内的实根。解：由建立迭代关系

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

(x)[a,b]；(II)存在0<

L<1，使所有

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

(xk)收敛于x*简单迭代法推论验后误差估计：误差估计式：验前误差估计：第十八页，共五十七页，编辑于2023年，星期四证明：①φ

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

时，

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

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

的邻域进行。

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

第二十一页，共五十七页，编辑于2023年，星期四

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

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

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

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

第二十三页，共五十七页，编辑于2023年，星期四2.2.4迭代过程的收敛速度迭代过程的收敛速度，是指在收敛时迭代误差的下降速度。

定义：设迭代过程

收敛于

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

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

收敛速度是误差的收缩率，阶数越高，收敛得越快。特别地，时称线性收敛，时称平方收敛或二次收敛，时称超线性收敛。迭代法的收敛速度常用收敛阶表示第二十四页，共五十七页，编辑于2023年，星期四

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

如何实际确定收敛阶？第二十五页，共五十七页，编辑于2023年，星期四例题例：证明函数在区间[1，2]上满足迭代收敛条件。证明：第二十六页，共五十七页，编辑于2023年，星期四例题

第二十七页，共五十七页，编辑于2023年，星期四例题若取迭代函数，不满足收敛定理，故不能肯定收敛到方程的根。第二十八页，共五十七页，编辑于2023年，星期四2.2.5迭代过程的加速

对于收敛的迭代过程,只要迭代足够多次,就可以使结果达到任意的精度。但有时迭代过程收敛缓慢,从而使计算量加大.因此迭代过程的加速是个重要的课题.常用迭代加速方法加权法埃特金加速法斯蒂芬生算法第二十九页，共五十七页，编辑于2023年，星期四

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

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

Steffensen加速：第三十页，共五十七页，编辑于2023年，星期四2.3牛顿迭代法2.3.1迭代公式的建立2.3.2牛顿迭代法的收敛情况2.3.3牛顿迭代法的修正法第三十一页，共五十七页，编辑于2023年，星期四2.3牛顿法原理：将非线性方程线性化——Taylor展开取x0

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

x0)2看成高阶小量，则有：线性xyx*x0x1迭代公式：迭代函数：第三十二页，共五十七页，编辑于2023年，星期四牛顿切线法2.3.2牛顿切线法的收敛情况

定理

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

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

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

修正迭代格式（平方收敛）n证明过程见书p42第四十二页，共五十七页，编辑于2023年，星期四改进二：

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

原理：若由xk

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

割线

切线斜率

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

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

可以证明，双点弦截法具有超线性敛速度，收敛的阶为：第五十一页