數(shù)值分析教學(xué)課件：4非線性方程求解

第四章非線性方程數(shù)值求解NumericalAnalysis§4.1一元方程求根華長生制作11）問題的提出

滿足函數(shù)方程f(x)=0(1)的x稱為方程(1)的根，或稱為函數(shù)f(x)的零點(diǎn)。如果函數(shù)(x)可分解為

(x)=(xs)mg(x)且g(s)0,則稱s是(x)的m重零點(diǎn)或(x)=0的m重根。當(dāng)m=1時，稱s是(x)的單根或單零點(diǎn)。若f(x)不是x的線性函數(shù),則稱(1)為非線性方程,

特別地,若f(x)是n次多項(xiàng)式，則稱(1)為n次多項(xiàng)式方程或代數(shù)方程；若f(x)是超越函數(shù)，則稱(1)為超越方程。2理論上已證明，對于次數(shù)n<=4的多項(xiàng)式方程,它的根可以用公式表示,而次數(shù)大于5的多項(xiàng)式方程,它的根一般不能用解析表達(dá)式表示.因此對于f(x)=0的函數(shù)方程,一般來說,不存在根的解析表達(dá)式,而實(shí)際應(yīng)用中,也不一定必需得到求根的解析表達(dá)式,只要得到滿足精度要求的根的近似值就可以了。常用的求根方法分為區(qū)間法和迭代法兩大類。求根問題包括：根的存在性、根的范圍和根的精確化。求根方法中最直觀最簡單的方法是二分法。32)預(yù)備知識定理1.(根的存在定理)

假設(shè)函數(shù)y=f(x)Ca,b,且f(a)·f(b)<0,則至少存在一點(diǎn)x(a,b)使得f(x)=0.(并稱區(qū)間(a,b)為有根區(qū)間)定理2.

假設(shè)函數(shù)y=f(x)在a,b上單調(diào)連續(xù),且f(a)·f(b)<0,則恰好只存在一點(diǎn)x(a,b)使得f(x)=0定理3.

假設(shè)函數(shù)y=f(x)在x=s的某一鄰域內(nèi)充分可微，則s是方程f(x)=0的m重根的充分必要條件是

41)問題給定方程f(x)=0,設(shè)f(x)在區(qū)間[a,b]連續(xù),且f(a)f(b)<0,則方程f(x)在(a,b)內(nèi)至少有一根

,為便于討論,不妨設(shè)方程f(x)=0在(a,b)內(nèi)只有一個(重根視為一個)實(shí)根，求滿足精度要求的近似值實(shí)根。2)概念及基本思想概

念：二分法也稱對分區(qū)間法、對分法等，是最簡單的求根方法，屬于區(qū)間法求根類型。

基本思想：利用連續(xù)函數(shù)的零點(diǎn)定理，將含根區(qū)間逐次減半縮小，就可以構(gòu)造出收斂點(diǎn)列來逼近根。

53)構(gòu)造原理定理1.(根的存在定理)

這個原理指出了根的存在區(qū)間可由兩端點(diǎn)處的函數(shù)值是否反號確定，那么注意到，將含根區(qū)間分為兩個長度相等的子區(qū)間后，在這兩個子區(qū)間上也可利用零點(diǎn)原理確定根在那個子區(qū)間上，如此繼續(xù)下去就達(dá)到將含根區(qū)間逐步縮小的目的，此時，在這一些相互包含的子區(qū)間中構(gòu)造收斂的數(shù)列將它收斂于根，見下圖

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

89101xx*收斂比較慢的情況：

控制循環(huán)（K）的方法：

11由得因此只要對分次，則有注：因?yàn)闉榈囊粋€端點(diǎn)，所以將區(qū)間對分后，取的中點(diǎn)作為的近似值，滿足

?12①簡單并保證收斂;②對f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根②收斂慢(僅與一個以1/2為比值的等比級數(shù)相同)

調(diào)用一次求解一個[a,b]間的多個根無法求得二分法的優(yōu)缺點(diǎn)13確定根所在的范圍［a,b］對有的函數(shù)也是一件困難的事。所幸的是，在實(shí)際應(yīng)用中，根據(jù)其物理或工程的背景，在絕大部分場合是不困難的。對給定的函數(shù)也有確定范圍的方法。14第四章非線性方程數(shù)值求解NumericalAnalysis§4.2不動點(diǎn)迭代法及其收斂定理華長生制作15

迭代法是求解非線性方程近似根的一種方法，這種方法的關(guān)鍵是確定迭代函數(shù)(x)，簡單迭代法用直接的方法從原方程中隱含地求出x，從而確定迭代函數(shù)(x)，這種迭代法收斂速度較慢，迭代次數(shù)多，因此常用于理論中,Newton迭代法采用另一種迭代格式,具有較快的收斂速度，由牛頓迭代法可以得到很多其他迭代格式。迭代法求非線性方程的根16簡單迭代法(基本迭代法)迭代法的建立與收斂性（1）17需要討論的問題首先期望每個xk都在(x)的定義域上,保持有界而且收斂到精確解;如何選取適合的迭代函數(shù)

(x);

迭代函數(shù)

(x)迭滿足什么條件,迭代序列收斂到精確解,收斂速度如何;怎樣加速序列{xk}的收斂速度.18定理4.1(壓縮性)說明:條件(2)可用更強(qiáng)更便于應(yīng)用的條件代替:（映內(nèi)性）(2)(3)19證:1o20：設(shè)方程在區(qū)間內(nèi)有根，則有由故據(jù)此反復(fù)遞推有故當(dāng)時迭代值,即證.9

10定理4.1指出:只要構(gòu)造的迭代函數(shù)滿足由(2)式,只要因此,當(dāng)?shù)涂梢越K止,迭代終止的判斷準(zhǔn)則注：L越小，收斂越快。23改進(jìn)條件：

24改進(jìn)條件：

25定義1：如果存在的某個鄰域，使迭代過程對于任意初值均收斂，則稱迭代過程在根鄰近具有局部收斂性。定理4.2設(shè)為方程的根，在的鄰域存在且連續(xù)并滿足,則迭代過程局部收斂。13例解:本題迭代函數(shù)有兩種構(gòu)造形式:,迭代法發(fā)散.(2)迭代法收斂.(1)27迭代法的收斂階(描述收斂速度)

定義2.:設(shè)

若有實(shí)數(shù)p>0,使

則稱序列是p階收斂,相應(yīng)的迭代法稱為p階方法.特別地,

p=1,稱線性收斂;

1<p<2,稱超線性收斂;

p=2,稱平方收斂。(4)28判別收斂階的兩定理29定理4.4：對于迭代過程，如果在所求根的鄰近連續(xù)，并且:

(*),則該迭代過程在點(diǎn)鄰近是P階收斂的。證明省!1131第四章非線性方程數(shù)值求解NumericalAnalysis§4.3Newton迭代法華長生制作32

§4.3Newton迭代法將f(x)在點(diǎn)xn作Taylor展開:

——Taylor展開線性化f(x)=0

近似于

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

記為xn+1,則1.Newton迭代公式建立33它對應(yīng)的迭代方程為顯然是f(x)=0的同解方程，故其迭代函數(shù)為

在f(x)=0的根x*

的某個鄰域內(nèi),在x*

的鄰域R內(nèi)，對任意初值，應(yīng)用公式（2）來解方程的方法就稱為牛頓迭代法。它是解代數(shù)方程和超越方程的有效方法之一.42.Newton迭代法的幾何意義

與x軸(y=0)的交點(diǎn)x，作為下一個迭代點(diǎn)xn+1,即

用f(x)在xn

處的切線Newton迭代法又稱切線法.353、牛頓迭代法的步驟步一、準(zhǔn)備。選定初始近似值，計(jì)算步二、迭代。按公式迭代一次，得到新的近似值，計(jì)算步三、控制。如果滿足或.則終止迭代，以作為所求的根；否則轉(zhuǎn)步四。此處是允許誤差,15而 其中c是取絕對誤差或相對誤差的控制常數(shù)，一般可取c=1。步四、修改。如果迭代次數(shù)達(dá)到預(yù)定指定的次數(shù)N，或者 ,則方法失敗；否則以代替轉(zhuǎn)步二繼續(xù)迭代。16例

用Newton迭代法求下面方程的一個正根,計(jì)算結(jié)果精確到7位小數(shù).解:由Newton迭代法x1

=1.4666667,…,x4

=1.3688081x5

=1.3688081迭代5次精度達(dá)10-7x*

≈

1.368808384.Newton迭代法收斂定理（1）Newton迭代公式在單根情況下至少2階收斂;

（2）

定理4.3.1

設(shè)f(x*)=0,,且在x*

的鄰域上存在,連續(xù),則可得證：將f(x)在xn

處作2階Taylor展開,并將解x*代入注意到ξn在xn

及x*之間,及,故39

所以，Newton法至少二階收斂.

注意到ξn在xn

及x*之間,及,故40

Newton法在重根情形下的收斂階20

Newton迭代法的特征

Newton迭代公式是一種特殊的不動點(diǎn)迭代,其迭代函數(shù)為:

Newton迭代是局部線性化方法,它在單根附近具有較高的收斂速度.

方法有效前提:425.Newton迭代法的應(yīng)用----------開方公式

對于給定正數(shù)應(yīng)用牛頓迭代法解二次方程可導(dǎo)出求開方值的計(jì)算公式設(shè)是的某個近似值，則自然也是一個近似值，上式表明，它們兩者的算術(shù)平均值將是更好的近似值。

定理

開方公式對于任意給定的初值均為平方收斂。

43牛頓迭代法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：

在單根附近,牛頓迭代法具有平方收斂的速度，所以在迭代過程中只要迭代幾次就會得到很精確的解。

缺點(diǎn):1.重根情形下為局部線性收斂;2.牛頓迭代法計(jì)算量比較大:因每次迭代除計(jì)算函數(shù)值外還要計(jì)算導(dǎo)數(shù)值;3.選定的初值要接近方程的解，否則有可能得不到收斂的結(jié)果;21牛頓迭代法的改進(jìn)缺點(diǎn)克服:

1.重根為局部線性收斂------改進(jìn)公式或加速2.每步都要計(jì)算導(dǎo)數(shù)值-----簡化Newton迭代法

或弦截法3.初值近似問題-------二分法求初值或”下山算法”21方法一.若已知重?cái)?shù)m(m>1),則利用m構(gòu)造新的迭代公式:此時,,至少2階收斂.不實(shí)用:m往往不確定.方法二.取,再對函數(shù)F(x)用Newton迭代:此時,X*為F(x)的單根,所以是2階收斂.但要用到二階導(dǎo)數(shù).6.Newton法的改進(jìn)(I)---重根情形46Newton迭代法需要求每個迭代點(diǎn)處的導(dǎo)數(shù)f’(xk)復(fù)雜！這種格式稱為簡化Newton迭代法精度稍低6.Newton法的改進(jìn)(II)47則Newton迭代法變?yōu)檫@種格式稱為弦截法(割線法)（書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法由弦截法要達(dá)到精度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是否收斂均與初值的位置有關(guān).例:x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.963110-10x5=0收斂發(fā)散迭代法的局部收斂性516.Newton法的改進(jìn)(III):牛頓下山法一般地說，牛頓法