第四章非線性方程的數(shù)值解法

1、數(shù)數(shù) 值值 分分 析析武武 漢漢 大大 學(xué)學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院基礎(chǔ)數(shù)學(xué)系數(shù)學(xué)與統(tǒng)計學(xué)院基礎(chǔ)數(shù)學(xué)系劉丁酉 主頁主頁4.1 引言引言4.2 二分法和試位法二分法和試位法4.3 迭代法迭代法4.4 迭代加速收斂的方法迭代加速收斂的方法4.5 Newton迭代法和割線法迭代法和割線法4.6 非線性方程組的數(shù)值解法非線性方程組的數(shù)值解法4 4 非線性方程的數(shù)值解非線性方程的數(shù)值解法法主頁主頁4.1 4.1 引言引言( )0f x , , , , xRfC a ba b()0f x主頁主頁本章主要討論數(shù)值求解方程（4.1.1）其中 也可以是無窮區(qū)間。如果實數(shù) 滿足方程（4.1.1），即 ，則稱 是方程（4.1

2、.1）的根，或稱 是 的零點。 兩類方程：兩類方程：1.代數(shù)方程代數(shù)方程：1110( ),nnnnf xa xaxa xa0na 5n 其中 ，易知，對于 情形，它無求根公式，只能用數(shù)值方法求根。 2. 2.超越方程超越方程：例如，方程 等，也只能用數(shù)值法求根。21sin,302xxxxexxx( )f x1 1根的存在性。方程有沒有根？若有根，有幾個根？根的存在性。方程有沒有根？若有根，有幾個根？2 2這些根大致在哪里？如何把根隔離開來？這些根大致在哪里？如何把根隔離開來？3 3根的精確化根的精確化定理定理1 1（介值定理）（介值定理）設(shè)函數(shù)設(shè)函數(shù) f f ( (x x) ) 在區(qū)間在區(qū)間a

3、, ba, b上連續(xù)，如果上連續(xù)，如果 f f ( (a a) ) f f ( (b b) 0) 0，則方程則方程 f f ( (x x) = 0 ) = 0 在在a, ba, b內(nèi)至少有一實根內(nèi)至少有一實根x x* *。 數(shù)值求根需要探討的問題：數(shù)值求根需要探討的問題：1畫出畫出 f(x) 的略圖，從而看出曲線與的略圖，從而看出曲線與x 軸交點的位置。軸交點的位置。f(x)0 xhx 0 x*ba2從左端點從左端點x = a出發(fā)，按某個預(yù)先選定的步長出發(fā)，按某個預(yù)先選定的步長h一步一步地向右跨，每跨一步都檢驗每步起點一步一步地向右跨，每跨一步都檢驗每步起點x0和終點和終點x0 + h的函數(shù)值

4、，若的函數(shù)值，若0)()(00hxfxf那么所求的根那么所求的根x*必在必在x0與與x0+h之間，這里可取之間，這里可取x0或或x0+h作為根的初始近似。作為根的初始近似。 基本步驟：基本步驟：例例1 1：考察方程：考察方程01)(3xxxfx00.51.01.5f (x) 的符號的符號4.2 4.2 二分法和試位法二分法和試位法主頁主頁4.2.1 4.2.1 二分法二分法4.2.2 4.2.2 試位法試位法4.2.14.2.1二分法二分法 二分法是方程求根中最為簡單、直觀的一種求根進代法，其理論基礎(chǔ)是高等數(shù)學(xué)中閉區(qū)間上連續(xù)函數(shù)的介值定理。 主頁主頁 執(zhí)行步驟執(zhí)行步驟1計算計算f (x)在有解

5、區(qū)間在有解區(qū)間a, b端點處的值端點處的值，f (a)，f (b)。2計算計算f (x)在區(qū)間中點處的值在區(qū)間中點處的值f (x1)。3判斷若判斷若f (x1) = 0，則則x1即是根，否則檢驗即是根，否則檢驗：（1）若若f (x1)與與f (a)異號異號，則知解位于區(qū)間則知解位于區(qū)間a, x1， b1=x1, a1=a;（2）若若f (x1)與與f (a)同號同號，則知解位于區(qū)間則知解位于區(qū)間x1, b， a1=x1, b1=b。主頁主頁反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間便可得到一系列有根區(qū)間：(a, b), (a1, b1), , (ak, bk), 4、當(dāng)當(dāng)11kka

6、b時時)(211kkkbax5、則、則即為根的近似即為根的近似簡單簡單; 對對f (x) 要求不高要求不高(只要連續(xù)即可只要連續(xù)即可) .無法求復(fù)根及偶重根無法求復(fù)根及偶重根 收斂慢收斂慢 主頁主頁例例2 2： 求方程01)(3xxxf的根。kakbkxkf (xk)的符號的符號011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-主頁主頁 4.3 迭代法迭代法1 1簡單迭代法簡單迭代法簡單迭代法的基本思想第一

7、步:求出與方程f(x)=0等價的方程x=g(x)第二步:給定 ，由迭代格式： xn+1=g(xn)n=0,1,2, 產(chǎn)生一收斂的數(shù)列xn 設(shè)X*是xn的極限,若g(x)是連續(xù)的,再由第一步可推出X*是f(x)=0的解.xn+1是f(x)=0解的第n+1次近似; x0是解的初始近似;g(x)是迭代函數(shù); xn+1=g(xn)是迭代格式.0X主頁主頁2.2.幾何意義幾何意義 的根從幾何上看是 與 交點的橫坐標(biāo)。( )xg xyx yg x例例3 3 求方程 在 附近的根。310 xx 01.5x 解解：方程 等價方程為310 xx (1)31xx 311kkxx012871.51.35721,1.

8、33086,1.32472xxxxx 1.32472x(2)1xx 311kkxx01231.5,2.375,12.396,1903.739xxxx 主頁主頁 由上面例子可看出，迭代格式可能收斂，也可能發(fā)散。因而須解決以下兩個問題：（1）怎樣選擇迭代格式 及 使 收斂？1kkxg x0 x kx（2）給出誤差 的估計式，并給出控制迭代次數(shù)的具體方法。kxx3.3.迭代過程的收斂性迭代過程的收斂性簡單迭代法的兩個基本問題: (1)如何選取初值和迭代公式. (2)如何停止迭代過程xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)

9、x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1定理4.3.1 如果 g(x)滿足下列條件 （1）當(dāng)xa, b時，g(x)a, b （2）當(dāng)任意xa, b時，存在0 L 1，使 則方程x = g (x)在a, b上有唯一的根x*,且對任意初值 x0a, b時，迭代序列xk+1=g (xk) (k = 0, 1, ) 收斂于x*。1)( Lxg(4.3.1) 證證:先證解的存在性： 作輔助函數(shù) f(x)=x-g(x),由條件知 f(x)在a,b上連續(xù),且 f(a)f(b)0;由連續(xù)函數(shù)的零點定理,至少存在一x* a, b,使使 f(x*)=0. 再證解的唯一性： 設(shè)f

10、(x1)=0,那么根據(jù)微分中值定理有 x1- x*=g(x1)-g(x*)=g(x2)(x1- x*)即有 根據(jù)條件有 , ,即即 最后證迭代數(shù)列收斂：首先,由于 不等式兩邊取極限得 1112120()()()()()()()nnnnnnnxxg xg xg yxxL xxL xxL xxnxx12()(1()0 xxg x10 xx1xx 定理 4.3.1中的條件要求對任意的 ，均有不等式(4.3.1)成立.這時對任意的 ,迭代數(shù)列收斂.稱此迭代格式為全局收斂. , xa b 定義定義4.3.14.3.1 設(shè) 是方程 的解,如果存在一個正數(shù) ,使得迭代過程對于任意的 均收斂,則稱這種迭代格式

11、為局部收斂.0 , xa b( )xg x0(, )xU xx定理定理4.3.2 設(shè)x*是方程x= g(x)的解,如果當(dāng)xU(x*,) 時，有則對任意初值x0 U(x*,)，迭代序列xk+1=g (xk) (k = 0, 1, )收斂于x*。 如果當(dāng)xU(x*,) 時，有則對任意初值x0 U(x*,)，迭代序列xk+1=g (xk) (k = 0, 1, )發(fā)散。1)( Lxg(4.3.2)1)( Mxg4 4迭代法迭代終止的條件迭代法迭代終止的條件 定理定理4.3.34.3.3 設(shè) 是 的解,如果對于任意的 ,均有 則有誤差估計式 x),(*xUx1)( Lxg*111nnnxxxxL( )

12、xg x證明證明 首先有再由微分中值定理有所以有nnnnxxxxxx11*nnnnxxLxxgxgxgxx*1*)( )()(*111nnnxxxxL 欲使絕對誤差限為 ,只要就夠了.故只要即可. 至此,我們可以依迭代法編寫程序進行計算了.*111()1nnnxxxxL11)1 (Lxxnn1 5 5迭代過程的收斂速度迭代過程的收斂速度定義定義4.3.1： 設(shè)由某方法確定的序列xk收斂于方程的根x*，如果存在正實數(shù)p，使得Cxxxxpkkk*1*lim（C為非零常數(shù)）則稱序列xk收斂于x*的收斂速度是p階的，或稱該方法具有p 階斂速。當(dāng)p = 1時，稱該方法為線性(一次)收斂；當(dāng)p = 2時，

13、稱方法為平方（二次）收斂；當(dāng)1 p0;所以在0,1方程至少有一個解. 又方程的等價形式為 令 ,則 于是, 即解的迭代格式為( )1/5/10 xg xe( )102xf xex1510 xex x0,1, g(x)11010 xee 均有 01011510nxnxxe( )/10 xg xe 由于所以取極限得 根據(jù)定義知:此迭代格式為線性收斂.*111()()1010nnxxnnxxeeexx *1*110nnnxxexx *1*1lim10 xnnnxxexx4.5 4.5 Newton迭代法和割線法迭代法和割線法1、牛頓法及其收斂性、牛頓法及其收斂性x*x0 x1x2xyf(x)原理：將

14、非線性方程線性化, )()(0000 xxxfxf0100()()f xxxfx只要 f C1，每一步迭代都有f ( xk ) 0， 而 且 *limxxkk 則 x*就是 f (x)的根。)()(1kkkkxfxfxx (4.5.1)( )()(0000 xxxfxfx令 求f (x)在 x1 處的切線方程:)( )()(1111xxxfxfx1211()()f xxxfx一般地 定理定理4.5.1 設(shè)f (x)在a, b上滿足下列條件：（1）f (a) f (b) 0則由（4.5.1）式確定的牛頓迭代序列xk收斂于f (x)在a, b上的唯一根x*。Newton法的收斂性依賴于法的收斂性依

15、賴于x0 的選取。的選取。x*x0 x0 x02 2牛頓法收斂的階牛頓法收斂的階 定理定理4.5.2 對于方程f(x)=0,設(shè)f(x)充分光滑，x*是f(x)=0在a,b內(nèi)的根.（1）x*是單根,則牛頓迭代格式是2階收斂的;（2） x*是m重根,則牛頓迭代格式是線性收斂的.此定理的證明涉及到定理2.4,請大家自己看例例5 5：求方程 的解01)2(4xex解解:設(shè) 則 f(0)=1, f(2)= -1 注:x0=3 or 81)2()(4xexfx44)410(41)( ,)46()( xxexxfexxf, 2 , 1,)46(1)2(04410nexxexxxnnxnnxnn在0,2內(nèi),f(x)0, f(0)f(0)0, 所以迭代格式為:例例6:6:設(shè)C為正實數(shù),導(dǎo)出用牛頓法求 的公式,并證明迭代敘列的誤差 滿足解:設(shè) ,則 于是有由于 所以在 內(nèi)有一正根.又在 內(nèi), 根據(jù)定理2.5得牛頓迭代格式為:CCxennnnnxee221Cx Cx 22)( ,2)( ,)(2xfxxfCxxf012) 1(,)0(CCfCf1 , 0C1 , 0C0)( , 0)( xfxf)lim( 2, 1n210