非線性方程求根

1、第 7 章 非線性方程求根 本章主要內(nèi)容： 1. 區(qū)間二分法 . 2 切線法 . 3. 弦位法 . 4. 一般迭代法 . 重點(diǎn)、難點(diǎn) 一、區(qū)間二分法 區(qū)間二分法是求方程 f(x)=0 根的近似值的常用方法。 基本思想：利用有根區(qū)間的判別方法確定方程根的區(qū)間 a,b , 將有根區(qū)間平分為 二；再利用有根區(qū)間的判別方法判斷那一個(gè)區(qū)間是有根區(qū)間；重復(fù)上述步驟，直到小區(qū) 間端點(diǎn)差的絕對(duì)值小于等于精度要求的數(shù)值， 則用將上一區(qū)間的分半值作為方程的根的 近似值。 區(qū)間二分法的計(jì)算步驟如下： 1. 計(jì)算區(qū)間端點(diǎn)的函數(shù)值 f(a) , f(b) (不妨設(shè) f(a) 0)； 確定初始有根區(qū)間 a,b. a b

2、a b 2. 二分有根區(qū)間 a,b ，并計(jì)算 f ( a b ) 取 x1 a b 2 1 2 3. 判斷： 若 f (x1) 0 ，則方程的根為 x x1 ； 若 f (x1) 0 ，則有根區(qū)間為 xa,x1 ；令 a,x1 a1,b1 若 f (x1) 0 ， 則 有 根 區(qū) 間 為 x x1,b ； 令 x1,b a1,b1 ab 4. 如果 b-a( 為誤差限)，則方程的根為 x a b ；否則轉(zhuǎn)向步驟 2， 2 繼續(xù)二分有根區(qū)間 a1,b1，并計(jì)算中點(diǎn)值，繼續(xù)有根區(qū)間的判斷，直到滿足精度要求為 止，即 bn-an 二分次數(shù)的確定：如果給定誤差限 ，則需要二分的次數(shù)可由公式 ln(b

3、a) ln n1 確定應(yīng)二分的次數(shù)。 ln 2 3 例 1 用區(qū)間二分法求方程 x 3 5x 3 0 在某區(qū)間內(nèi)實(shí)根的近似值(精確到 0.001) 【思路】參見上述區(qū)間二分法的計(jì)算步驟 解 f(1.8)=-0.168 0 f(x)在區(qū)間 1.8 ，1.9內(nèi)有一個(gè)根。 由公式 ln(b a) ln n ln 2 ln 0.1 ln 0.001 ln 2 1 5.644 取 n=6， 計(jì)算結(jié)果列表如下： n an bn xn f(x n) 1 1.8 1.9 1.85 + 2 1.8 1.85 1.825 - 3 1.825 1.85 1.8375 + 4 1.825 1.8375 1.83125

4、 - 5 1.83125 1.8375 1.834375 + 6 1.83125 1.834375 1.8328125 則方程在區(qū)間 1.8 ，1.9 內(nèi)所求近似值為 x* x = 1.8328125 區(qū)間二分法的優(yōu)點(diǎn)是計(jì)算程序簡單，只要f(x)在區(qū)間 a,b 上連續(xù)，區(qū) 間二分法就可使用， 但區(qū)間二分法不能用來求偶次重根， 由于區(qū)間二分法收斂比較 慢，在實(shí)際計(jì)算中，區(qū)間二分法常用來求比較好的含根區(qū)間和初始近似值，以便進(jìn) 一步使用收斂更快的迭代法求出更精確的近似值。 迭代序列收斂階的概念 設(shè)迭代序列 xn 收斂于 x* ，如果存在實(shí)數(shù) p 1與正常數(shù) c，使得 xx xn 1 x * lim

5、p c ，則稱序列 xn 是 p 階收斂于 x* 。 n xn x p n 特別地，當(dāng) p 1 時(shí)，稱序列 xn 為線性(一次)收斂 ； xn 為線性收斂時(shí)，必須要 求 c 1 。 當(dāng) p 2 時(shí)，稱序列 xn 為平方(二次)收斂 ； 當(dāng) 1 p 2時(shí)，稱序列 xn 為 超線性收斂 ； 收斂階 p 越大， 則序列 xn 與 x* 的誤差縮減越快， 也就是序列 xn 收斂越快。 二、切線法 (牛頓法 ) 1. 切線法的基本思想： 假設(shè)方程 f(x)=0 在區(qū)間 a,b 上有唯一根 x*,過曲線 y= f(x) 上的 一點(diǎn)( x0,f(x0)，作曲線的切線，用此切線與 x 軸的交點(diǎn)的橫坐標(biāo) x1

6、作為方程的根 x*的新 的近似值 , 再過點(diǎn)( x1,f(x 1)，作曲線的切線，則又得到新的近似值,按此方法進(jìn)行迭代計(jì) 算，直到滿足精度要求為止。 f(xn) 切線法 (牛頓法 )的迭代公式為 xn 1 xnn (n 0,1,.) f (xn) 2.切線法的收斂性 我們利用定理( 7.1)來判斷切線法的收斂性。定理( 7.1)還給出了一個(gè)初始值 x0的選擇方法， 定理 7.1. 設(shè) f(x)在 a,b 上存在二階連續(xù)導(dǎo)數(shù)，且滿足條件 f(a)f(b)0 ， 則選擇區(qū)間的右端點(diǎn)；若 f/(x)0 在有根區(qū)間上選擇初始值 x0，代入迭代公式進(jìn)行計(jì)算 f (x) x3 5x 3 f (x) 3x2

7、 5 f (x) 6x 解 f (2) 1 0, f (2) 12 0取初始值 x0 2 代入迭代公式 xnxn 1 f (xn 1) 2xn3 3 f (xn 1) 3xn2 5 計(jì)算得 n 0 1 2 3 4 xn 1 1.857142857 1.83478735 1.834243504 1.834243185 x4 x3 0.000000319 0.000001 x 1.834243185 例 3 證明 計(jì)算 3 a 的切線法迭代公式為 1a xn 1(2xn2 ) ( n=0,1, ) 3xn 解 因?yàn)橛?jì)算 3 a 等同于求方程 x3 a 0 的根， 將 f (x) x3 a, f (

8、x) 3x2，代入切線法迭代公式得： xn3 a 1a xn 1 xn3x23(xn x2 ) ,n 0,1, 3xn3xn 三 、弦位法 1. 弦位法的基本思想：假設(shè)方程 f(x)=0 在區(qū)間 a,b上有唯一根 x*,在區(qū)間 a,b 內(nèi)的 曲線 y= f(x) 上任取兩點(diǎn)作弦， 用此弦與 x 軸的交點(diǎn)橫坐標(biāo)作為方程根的近似值。 按此方法 進(jìn)行迭代計(jì)算，直到滿足精度要求為止。 弦位法分為單點(diǎn)弦法和雙點(diǎn)弦法。 2.單點(diǎn)弦法 建立弦的迭代公式時(shí)，固定其中一個(gè)點(diǎn)，而另一個(gè)點(diǎn)變動(dòng)的迭代求根 方法。 單點(diǎn)弦法的迭代公式 xn 1xn cxnf (xn )(n 0,1,.) n 1nf (c)f (xn

9、) n ( 1)單點(diǎn)弦法的收斂性 利用定理 7.2 判斷其收斂性。單點(diǎn)弦法收斂所滿足條件和切線法的收斂條件相同，不 同的是單點(diǎn)弦法迭代公式所產(chǎn)生的序列是線性收斂于 f(x)=0 在區(qū)間 a,b 上有唯一根 x* 。我 們計(jì)算時(shí)應(yīng)注意，在選擇固定點(diǎn) c時(shí)，也要求滿足條件 f(c)f (x) 0. f(x 0)f (x) 0 。 (2)單點(diǎn)弦法的計(jì)算步驟同切線法類似。 3雙點(diǎn)弦法 建立弦的迭代公式時(shí)， 兩個(gè)點(diǎn)都變動(dòng)的迭代求根方法。 雙點(diǎn)弦法的迭代公式為 xn 1 xn xn xn 1 f(xn) f(xn 1) f(xn) (n 0,1,.) 1)雙點(diǎn)弦法收斂性 利用定理( 7.3)判斷。 f(x

10、) 在a,b上滿足的條件為 : f(a)f(b) 0; f/(x)0 KR1,其中 K=M 2/2m1, M2 = max f/(x) , m1 = minf/(x), R=max x0-x *， x1-x* . 則以 a,b為初始值， 由雙點(diǎn)弦法迭代公式得到的序列超線性收斂于方程 f(x)=0 在區(qū)間 a,b 的唯一根 x*。 (2)雙點(diǎn)弦法的計(jì)算步驟同切線法類似。但在計(jì)算時(shí)應(yīng)注意收斂性的判斷和初始值 的選 擇。 例 4 試導(dǎo)出計(jì)算 a (a 0)的單點(diǎn)弦法迭代公式，并用它計(jì)算3，準(zhǔn)確到 10 6。 解 因?yàn)橛?jì)算 a (a 0) 等同于求方程 x2 a 0 的正根， 令 f (x) x2 a

11、, f (x) 2x ，代入單點(diǎn)弦法迭代公式，得： xn 1xn c xn f (c) f (xn) f (xn) xn c xn (x2 2 2 (xn cxn a) cxn a c xn 例5 分別用單點(diǎn)弦法和雙點(diǎn)弦法求方程 x3 3x 1 0 在1 ，2內(nèi)根的近似值， -3 精確到 10-3 【思路】參見單點(diǎn)弦法和雙點(diǎn)弦法的計(jì)算步驟 解 方法一 . 單點(diǎn)弦法 f(x) x3 3x 1 f(1) 3 0, f (2) 1 0 f x 在區(qū)間 1, 2 內(nèi)有根 且在區(qū)間 1, 2 內(nèi) f (x) 3x2 3 0, f (x) 6x 0 取初始值 x0 1, 代入迭代式 xn 1xn c xn

12、 f(c) f (xn ) f(xn) 得方程根的近似值 21 x1 1 3 1.75, f x10.890625 1 1 ( 3) 1 2 1.75 x2 1.75 0.890625 1.867768595, f x20.087483863 2 1 ( 0.890625) 2 2 1.867768595 x3 1.867768595 0.087483863 1.878406099, 3 1 ( 0.087483863) f x30.007432423 2 1.878406099 x4 1.878406099 0.007432423 1.879303169 4 1 ( 0.001130637

13、) f( x4) 0.000623407 2 1.879303169 x5 1.879303169 0.000623407 1.879378365 5 1 ( 0.000623407 ) f(x5) 0.000052236 , x5 x4 0.000075196 10 3, 方程的近似根為 x 1.879378365 方法二 . 雙點(diǎn)弦法 3 f(x) x3 3x 1 f(1) 3 0, f (2) 1 0 在區(qū)間 1, 2內(nèi)方程 f x 0有根 .且 f (x) 3x2 3 0, f (x) 6x 0 取 x0 1.9, x1 2 f (1.9) 0.159 0， f (2) 1 0 f(1

14、.9) f (x)0 0 f (2) f (x) 0 代入迭代式 xn 1 xn xn xn 1 f(xn ) f (xn 1) f (xn ) 得方程根的近似值 x2 2 1.9 1 (0 .159 ) 1 1.881093936 f x20.012996164 1.881093936 2 x3 1.881093936 0.012996164 1.879528266 , 3 0.012996164 1 f x30.001086562 x4 1.879528266 1.879528266 1.881093936 0.001086562 0.012996164 0.001086562 1.879

15、429134 , x4 x3 0.00009913 10 3 方程根的近似值為 x x4 1.879429134 . 四、 一般迭代法 一般迭代法的基本思想： 若方程 f(x)=0 在區(qū)間 a,b 上有唯一根 x*,將方程變形為同解 方程 x= ( x)，且 ( x )連續(xù)，則建立迭代公式 xn+1=(xn) (n=0,1, ,)。 設(shè) x0是方 程的一個(gè)近似根 , 將它代入迭代公式進(jìn)行迭代，求出的一系列近似根，直到滿足精度要 求為止。 1. 一般迭代法的迭代公式： xn 1 (xn) (n 0,1, ,) 2.一般迭代法的收斂性 建立一般迭代法的迭代公式可以有許多方法，但是有些迭代公式產(chǎn)生的

16、迭代序 列不收斂，所以判斷迭代公式的收斂性就十分重要。我們利用定理(7.4)判斷一般迭 代法的收斂性問題。 3. 一般迭代法的計(jì)算步驟同切線法類似。 計(jì)算時(shí)也應(yīng)注意收斂性的判斷和初始值 的選擇。 例6設(shè) x(x ), max (x) 1 證明 由 xn 1 (xn) n 0,1, ，得到的序列 xn 收斂于 x 。 證明 由 xn 1 (xn) n 0,1, ， x (x ) 兩式相減，應(yīng)用中值定理得 xnx*(xn 1)(x* )(n) xn 1x*xnx*nxnx* 由 1 得 xnx (n ) 。 例7 用一般迭代法求方程 4x e x 0在區(qū)間0，1內(nèi)的根，要求 xn+1-xn 10-

17、4 思路】 判斷方程近似根的斂性 根據(jù)所給方程找一個(gè)能表示為x= (x)的同解方程 ,建立迭代式，并 .選取初始近似根 x0(一般選有根區(qū)間的端點(diǎn)值 ),然后逐次迭代 , 直 到滿足精度要求為止。 把方程改寫為 x (x) 1 1x ， 該方程迭代公式為 4e xn 1 4exn 在 0, 1 區(qū)間內(nèi) (x) 4ex 14 1, 方程近似根序列收斂于 方程 f (x) 0的唯一根 x 取初始值 x0 0. 代入 xn(xn 1), 求得 : x1 1 41e0 0.25 , x2 0.25 4e 0.194700195 , x3 1 4e01.1947 0.205770346 , x4 0.2

18、058 0.203504999 , 4e x5 0.2035 0.203966531 , 4e x6 1 4e01.2040 0.203872416 , x6 x5 0.000094 10 4 滿足精度要求。 方程根的近似值為 x x6 0.203872416 第 8 章常微分方程數(shù)值解法 本章主要內(nèi)容： 1歐拉法、改進(jìn)歐拉法 . 2龍格 -庫塔法。 3單步法的收斂性與穩(wěn)定性。 重點(diǎn)、難點(diǎn) 一、微分方程的數(shù)值解法 在工程技術(shù)或自然科學(xué)中， 我們會(huì)遇到的許多微分方程的問題， 而我們只能對(duì)其中 具有較簡單形式的微分方程才能夠求出它們的精確解。對(duì)于大量的微分方程問題我們 需要考慮求它們的滿足一定精度

19、要求的近似解的方法，稱為微分方程的數(shù)值解法。本 dy f （x,y） 章我們主要討論常微分方程初值問題 dx 的數(shù)值解法。 y（x0 ） y0 數(shù)值解法的基本思想是：在常微分方程初值問題解的存在區(qū)間 a,b 內(nèi)，取 n+1 個(gè) 節(jié)點(diǎn) a=x0 x1xN=b （其中差 hn= x n xn-1稱為步長，一般取 h 為常數(shù)，即等步長）， 在這些節(jié)點(diǎn)上把常微分方程的初值問題離散化為差分方程的相應(yīng)問題，再求出這些點(diǎn) 的上的差分方程值作為相應(yīng)的微分方程的近似值（滿足精度要求） 二、歐拉法與改進(jìn)歐拉法 歐拉法與改進(jìn)歐拉法是用數(shù)值積分方法對(duì)微分方程進(jìn)行離散化的一種方法。 將常微分方程 y f（x, y）變?yōu)?/p>

20、 y（xn1） y（xn） xxn1 f（t,y（t）dt xn 1歐拉法（歐拉折線法） 歐拉法是求解常微分方程初值問題的一種最簡單的數(shù)值解法。 歐拉法的基本思想：用左矩陣公式計(jì)算（）式右端積分，則得歐拉法的計(jì)算公式 為： ba yn 1 yn hf(xn,yn) (n 0,1,.,N 1) h N 歐拉法局部截?cái)嗾`差 Rn 1 h2 y ( n 1) n1 2 n 1 xnn 1 xn 1 或簡記為 O（ h2）。 我們在計(jì)算時(shí)應(yīng)注意歐拉法是一階方法，計(jì)算誤差較大。 歐拉法的幾何意義：過點(diǎn) A0（x0，y0），A1（ x1，y1），A n（x n，y n ），斜率分 別為 f（x0，y0），

21、f（x1，y1），f（x n，y n）所連接的一條折線，所以歐拉法亦稱為 歐拉折線法。 例 1 用歐拉法解初值問題 10 2xy (0 x 1) dx y(0) 1 在x0 (0.2) 1 處的近似解。(計(jì)算過程保留 4位小數(shù))。 【思路】 用歐拉法求解常微分方程的初值問題時(shí)，首先熟練掌握歐拉公式的一般 形式， 根據(jù)具體題目寫出找出歐拉公式的迭代式，并根據(jù)初始條件和所給 步長進(jìn)行迭代求解。 解 f(x，y) 2xy ， h 0.2， 歐拉公式為： yn 1 yn hf (xn, yn) yn 0.2( 2xnyn) (1 0.4xn)yn (n 0,1,2,3,4,5) 列表計(jì)算如下： n x

22、n yn y(xn) y(xn)-yn 0 0 1 1 0 1 0.2 1 0.9608 -0.0392 2 0.4 0.92 0.8521 -0.0679 3 0.6 0.7728 0.6977 -0.0751 4 0.8 0.5873 0.5273 -0.06 5 1 0.3994 0.3679 -0.0315 2改進(jìn)歐拉法 改進(jìn)歐拉法比歐拉法的計(jì)算準(zhǔn)確，是對(duì)歐拉法的改進(jìn)。改進(jìn)歐拉法的基本思想： 用梯形公式計(jì)算()式右端積分，則得改進(jìn)歐拉法的計(jì)算公式為： h b a yn 1 ynf(xn,yn) f(xn 1,yn 1) (n 0,1,., N 1) h 2N 11 利用改進(jìn)歐拉法計(jì)算常

23、微分方程初值問題時(shí)，我們應(yīng)注意此公式為隱式表達(dá)式， 需要對(duì)它進(jìn)行迭代求解。計(jì)算時(shí)可以采用一次迭代和多次迭代，因此，就有改進(jìn)歐拉法 預(yù)估 -校正法公式和反復(fù)迭代的改進(jìn)歐拉法預(yù)估-校正法公式。 改進(jìn)歐拉法預(yù)估 -校正法公式： yn01 yn hf(xn,yn) h yn1 yn h2 f(xn,yn) f(xn 1,yn01) (n 0,1,., N 1) 反復(fù)迭代的改進(jìn)歐拉法預(yù)估 -校正法公式： yn01 yn hf (xn,yn) ynm11 yn h2 f(xn,yn) f(xn 1,ynm1) (n 0, ,N 1, m 0,1,.)., 改進(jìn)歐拉法的局部截?cái)嗾`差 h3 Rn 1 h y

24、( n 1) xnn 1 xn 1 或簡記為 O 12 h3）。從局部截?cái)嗾`差的形式看，改進(jìn)歐拉法是二階方法，因此，它比歐拉法更精確。 例 2 用預(yù)估 - 校正法求初值問題 2 y y xy2 (0 x 1) y(0) 1 在 x=0（0.2）1 的解。 【思路】掌握預(yù)估 -校正法的計(jì)算公式，根據(jù)已知條件迭代求解。 2 解 步長 h=0.2，將 f （x,y） y xy2 代入預(yù)估 -校正公式，整理得 (0) yn 1 n1 yn 1 2 0.8yn 0.2xnyn2 0.9yn 0.1xnyn2 0.1( yn(0)1 xn 1(yn(0)1)2 列表計(jì)算如下： 12 n x n y n y

25、(x n) 0 0 1 1 1 0.2 0.80720 0.80463 2 0.4 0.63690 0.63145 3 0.6 0.49048 0.48918 4 0.8 0.37780 0.37720 5 1 0.29103 0.29100 例 3 用改進(jìn) 歐拉法求解例 1 的初值問題 ,要求 10 3 【思路】掌握改進(jìn)歐拉法的計(jì)算公式，根據(jù)已知條件迭代求解，并檢驗(yàn)迭代解是 否滿足精度要求，若滿足則確定此解為常微分方程在某點(diǎn)的近似解。 解 將 f (x,y) 2xy 代入改進(jìn)歐拉法的計(jì)算公式得： yn(0)1 yn hf (xn, yn) yn 0.2( 2xn yn) (1 0.4xn )

26、yn ynm1 yn h f(xn,yn) f(xn 1,ynm11)yn 0.2xnyn xn 1ynm11) n 1 2 列表計(jì)算如下： n xn 0 yn yn1 yn2 yn3yn y(xn) y(x n)-y n 0 0 1 1 1 1 1 0 1 0.2 1 0.96 0.9616 0.9615 0.9608 -0.0007 2 0.4 0.8846 0.8523 0.8549 0.8549 0.8521 -0.0028 3 0.6 0.7181 0.7003 0.7025 0.7022 0.6977 -0.0045 4 0.8 0.5337 0.5325 0.5327 0.532

27、7 0.5273 -0.0054 5 1 0.3622 0.3750 0.3725 0.3730 0.3679 -0.0051 13 三、龍格 -庫塔法 1龍格 -庫塔法 龍格 -庫塔法具有精度高、收斂、穩(wěn)定，不需要計(jì)算高階導(dǎo)數(shù)等優(yōu)點(diǎn)，是求解微分 方程初值問題的一組著名的顯示單步方法， 廣泛應(yīng)用于求解常微分方程的初值問題。 本 章我們介紹了二、三、四階龍格 -庫塔法。 龍格 -庫塔法的基本思想： 在計(jì)算初值問題 y f ( x, y)的數(shù)值解時(shí)，考慮均差 y(xn 1) y(xn)，則由微 y(x0) y0h 分中值定理可得 y(xn 1) y(xn ) hy (xnh) (01)， 由初值問

28、題可得 公 式 為 ：y(xk 1) y(xk) hf (xkh,y(xk h) 上 式 中 f(xkh, y(xk h) 稱為區(qū)間上的平均斜率。如果給平均斜率一種計(jì)算方法，就 可得到計(jì)算 y(x n+1)的近似值 yn+1 的公式。 如果僅取 xn處的斜率值 f (xn , yn )作為平均斜率的近似值，則得到的yn 1的公式 為歐拉公式； 如果取 xn , xn 1處的斜率值 f(xn,yn)，f(xn 1, yn 1)的平均值作為平均斜率的近 似值，則得到的 yn 1 的公式改進(jìn)歐拉公式。 二階龍格 - 庫塔法的公式和局部截?cái)嗾`差： yn 1 yn h( 1k12k2) k1 f (xn

29、,yn) 1 n n k2f (xn 1, yn hk1) 在上式中選擇不同的參數(shù)，會(huì)得到不同的二階龍格-庫塔法公式，所以二階龍格 -庫 塔法公式不唯一。二階龍格 -庫塔法公式的局部截?cái)嗾`差為 (h3)。 常見的二階龍格 -庫塔法公式有以下兩種 改進(jìn)歐拉法迭代公式 14 h yn 1 yn 2(k1 k2) k1 f (xn,yn) k2 f(xn 1,yn hk1) yn 1 yn hk2 k1 f (xn,yn) hh k2 f (xn h2,yn 2hk1) 三階龍格 - 庫塔法的公式和局部截?cái)嗾`差： 常見的三階龍格 -庫塔法公式為 h yn 1 yn(k1 4k2 k3) 6 k1 f

30、(xn,yn) k2 f(xn h,yn hk1) 22 k3 f(xn h,yn hk1 2hk2) 三階龍格 -庫塔法公式的局部截?cái)嗾`差為 ( h4)。 yn 1 yn hk2 k1 f (xn,yn) hh k2 f (xn h,yn hk1) 22 四階龍格 - 庫塔法公式 h yn 1 n y ) k1 h n y h 通常所說的龍格 -庫塔法是指四階龍格 -庫塔法，也稱為標(biāo)準(zhǔn)龍格 -庫塔法。由于它 是一步法，(即已知 yn ，就可以求出 yn 1 ，無需知道 yn 1， yn 2 ，的值)且它的計(jì)算 f( x，y )的值，計(jì) 精度高，所以應(yīng)用較多，但在計(jì)算時(shí)，因?yàn)槊恳徊蕉夹枰?jì)算四次 算量較大，所以，一般用來計(jì)算前幾項(xiàng)的近似值，即“表頭” 四階龍格 -庫塔法公式為的公式和局部截?cái)嗾`差： 15 h yn 1 yn h(k1 2k2 2k3 k4 ) 6 k1 f (xn,yn) hh k2 f (xn 2,yn 2k1) hh k3 f (xn