數(shù)值分析2-計算方法2非線性方程的數(shù)值解法

1、第二章 非線性方程的數(shù)值解法考察下列方程 f(x)=0f(x)可以是代數(shù)多項式，也可以是超越函數(shù)。求解精確解一般不可能，只能尋求數(shù)值解。,§2.1 二分法 若函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，且 f(a)f(b)<0則方程 f(x)=0在區(qū)間[a,b]上至少有一個實數(shù)根。,二分過程：（假定有根區(qū)間僅一

2、個實數(shù)根x*）如果 f(a)f((a+b)/2)<0，則在區(qū)間[f(a),f((a+b)/2] 上有實數(shù)根。如果 f((a+b)/2)f(b)<0，則在區(qū)間[f((a+b)/2,f(b)] 上有實數(shù)根。于是，新的有根區(qū)間僅為原有根區(qū)間的一半，記作[a1,b1]，重復(fù)上述二分過程，可得區(qū)間寬度不斷減半的有根區(qū)間序列 [a,b] [a1,b1] [a2,b2]

3、 … [ak,bk] …其中,令有根區(qū)間 [ak,bk]的中點xk=(ak+bk)/2為 x* 的近似值，在上述二分過程中，得到如下x*的近似值序列 x0,x1,x2,…,xk,…由于 對于預(yù)先設(shè)定的精度ε>0，只要

4、 便有此時xk為滿足精度要求的近似解。,表2.1 x6=1.324 ≈x* |x*-x6| ≤ ≈0.0039 ≤0.005,例2.1 用二分法求方程f(x)=x3-x-1=0在區(qū)間[1,1.5]

5、內(nèi)的一個實根，要求誤差不超過0.005。,解：由公式（2.3）估計二分的次數(shù)于是，只要二分6次即可達到精度要求，二分過程見表2.1,§2.2 Jacobi（簡單）迭代法1、Jacobi迭代法的基本原理 考察方程 f(x)=0 x=φ(x) 在根x*的附近取一點x0作為x*的預(yù)測值，有

6、x1=φ(x0)重復(fù)上述步驟，有如下迭代公式 xk+1=φ(xk) (k=0,1,2,…)其中φ(x)為迭代函數(shù)，x0,x1,…,xk,…為迭代序列。,,等價形式,如果迭代序列{xk}的極限存在，即 x*= xk則迭代過程收斂。如果迭代序列{xk}的極限不存在，迭代過程發(fā)散。,(a)迭代收斂,(b)迭代發(fā)散,例2.2 求方程f(x)=x

7、3-x-1=0在x=1.5附近的根x*的近似值。解：將方程f(x)=0改寫為如下等價形式 x=(x+1)(1/3)迭代公式為 xk+1=(xk+1)(1/3) (k=0,1,2,…)取x0=1.5，計算過程用6位有效數(shù)字表示，迭代結(jié)果見表2.2 表2.2,如果將原方程改寫為如下等價形式 x=x3-1則有迭代

8、公式 xk+1=(xk)3-1迭代初值x0=1.5，則有 x1=2.357,x2=12.39,…迭代過程發(fā)散。,2、Jacobi迭代過程的收斂性定理2.1 如果迭代函數(shù)φ(x)滿足如下條件（1）對任意x [a,b]，有 a ≤ φ(x) ≤b（2）存在正數(shù)L<1，使對任意

9、x [a,b]，有 |φ’(x)|≤L<1則迭代過程xk+1= φ(xk) 對任意x0 [a,b]均收斂于方程x=φ(x)的根x*，且有如下誤差事后估計式,證：由微分中值定理 |x*-xk| =|φ(x*)-φ(xk-1)|=|φ’(ξ)(x*-xk-1)| ≤L|x*-xk-1|式中ξ為x*與xk-1之間的一點。 據(jù)此反復(fù)遞推

10、 |x*-xk|≤L|x*-xk-1|≤L2|x*-xk-2|≤…≤Lk|x*-x0| 顯然，當(dāng)k→∞時，xk→x*,迭代序列{xk}收斂于x*。為確保收斂，全體迭代值xk應(yīng)在[a,b]上取值，為此對任意x [a,b] ，均有φ(x) [a,b]。 對任意正整數(shù)p，有|xk+p-xk|≤|xk+p-xk+p-1|+|xk+p-1-xk+p-2|+ … + |xk+1-xk| =

11、(Lp-1+Lp-2+ … +1)|xk+1-xk|固定k并令p→∞,有,定義2.1 稱迭代過程在根x*的附近具有局部收斂性，指的是如果存在鄰域△:|x - x*|≤δ， 迭代過程xk+1=φ(xk)對任意初值x0 △ 收斂。,由此可見，只要前后兩次迭代值得差值足夠小，就可使近似值xk+1達到任意精度。一般情形下，用 |xk+1 - xk|<ε來控制迭代精度。,定理2.2 設(shè)

12、φ(x)在方程x=φ(x)根的附近有連續(xù)的一階導(dǎo)數(shù)，且 |φ’(x)|<1則迭代過程xk+1= φ(xk)具有局部收斂性。例2.3 求方程 x = e-x在x = 0.5附近的一個根，要求精度ε=10-5。解：通過搜索方法，得有根區(qū)間[0.5,0.6]，且有 φ’(x) ≤ =exp(

13、-0.5)<1迭代公式xk+1=e-xk對迭代初值x0=0.5收斂。,經(jīng)18次迭代后，x18=0.56714，滿足所規(guī)定的精度要求。§2.3 Aitken加速迭代法 設(shè)xk是第k次迭代近似值，由迭代公式得第k+1次迭代值，記作 𝑥 k+1，即 𝑥 k+1=𝜑(xk)由微分中值定理，有 𝑥 ? - &

14、#119909; k+1=𝜑,(𝜃)( 𝑥 ? -xk)≈L ( 𝑥 ? -xk)記 𝑥 k+1=𝜑( 𝑥 k+1)且有 𝑥 ? - x k+1=𝜑,(𝛿)( 𝑥 ? - 𝑥 k+1) ≈L ( 𝑥 ? - w

15、909; k+1),于是 𝑥 ? ? 𝑥 k+1 𝑥 ? ? x k+1 ≈ 𝑥 ? ?xk 𝑥 ? ? 𝑥 k+1 整理后，有如下事后估計式 𝑥 ? ? 𝑥 k+1 ≈ ? 𝑥 k+1? 𝑥 k

16、+1 2 𝑥 k+1?2 𝑥 k+1+ 𝑥 𝑘 由此，得下列Aitken迭代加速公式,校正 𝑥 k+1=𝜑(xk),再校正 𝑥 k+1=𝜑( 𝑥 k+1),改進 xk+1= 𝑥 k+1 - 𝑥 k+1

17、? 𝑥 k+1 2 𝑥 k+1?2 𝑥 k+1+ 𝑥 𝑘,,例2.4 用Aitken方法求解方程 f(x)=x3-x-1=0在x=1.5附近的根。解：以如下迭代公式 xk+1=(xk)3-1為基礎(chǔ)，構(gòu)造Aitken迭代加速公式 𝑥 k+1=(xk)3?1

18、 𝑥 k+1=( 𝑥 k+1)3-1 xk+1 = 𝑥 k+1 - 𝑥 k+1? 𝑥 k+1 2 𝑥 k+1?2 𝑥 k+1+𝑥𝑘 初值x0=1.5,經(jīng)5次迭代，得x5=1.32472,例2.5 證明求方程 𝑥 2 ?

19、𝑥?1=0在 1,2 上有一個實根，用二分法求這個根，要求 𝑥 𝑘 ? 𝑥 ? < 10 ?3 ，若要求 𝑥 𝑘 ? 𝑥 ? < 10 ?6 ，需二分區(qū)間 1,2 多少次？ 1.3253(9),19例2.6 設(shè)方程12?3𝑥+2cos𝑥

20、;=0的迭代格式為 𝑥 𝑘+1 =4+ 2 3 cos 𝑥 𝑘 （1）證明對? 𝑥 0 ∈𝑅，均有 lim 𝑘→∞ 𝑥 𝑘 = 𝑥 ? ；（2）取 𝑥 0 =4，求此迭代格式的近似值，精度為 ε= 10 ?3 ，列出各

21、迭代值。 3.3475(3),§2.4 Newton迭代法1、Newton迭代法的構(gòu)造思路 設(shè)方程f(x)=0的根 𝑥 ? ，xk為方程根的近似值 將函數(shù)f(x)在xk處做一階Taylor展開 用 近似代替函數(shù)

22、f(x) 于是 f(x)=0 → 求解 ，得,由此得Newton迭代格式 Newton迭代法的幾何描述 y

23、 切線法

24、 xk+2 xk+1 xk x,,,例2.7 用Newton法求方程 x = e-x在x = 0.5附近的一個根。解：將x = e-x改為x ex-1=0 令 f(x)= x ex-1 Newton迭代公式為 取x0= 0.5 ，利用上述迭代公式，得 x1= 0.57102

25、，x2= 0.56716 ， x3= 0.56714,例2.8 用Newton法求 115 ，精度𝜀= 10 ?6 解：將此問題轉(zhuǎn)化為下列二次方程 x 2 –115=0 Newton迭代格式為 xk+1 = 1 2 (xk+ 115 xk ) 初值x0= 10 ，4次迭代得所要求的近似值 115 ≈10.72380

26、5,2、Newton迭代法的收斂性定義2.2 設(shè)迭代序列 𝑥 𝑛 收斂于 𝑥 ? ，誤差為 𝜀 𝑘 = 𝑥 𝑘 ?𝑥 ? 如果有 𝜀 𝑘+1

27、20576; 𝑘 𝑝 → 𝛼≠0 𝑘→∞ 稱迭代序列是𝑝階收斂的， 特別地 （1） 𝑝=1，0<𝛼<1 ，線性收斂 （2） 𝑝=2，平方收斂 （3） 𝑝≥1， 𝜀 𝑘+1 𝜀 ⻕

28、6; 𝑝 →0，超𝑝階收斂的,例2.9 設(shè)𝜑 𝑥 在𝑥=𝜑 𝑥 的根 𝑥 ? 附近有連續(xù)的p導(dǎo)數(shù)，且𝜑, 𝑥 ? =𝜑,, 𝑥 ? =……= 𝜑 𝑝?1 𝑥 ? =0

29、 𝜑 𝑝 𝑥 ? ≠0 證明迭代過程 𝑥 𝑘+1 =𝜑 𝑥 𝑘 是p階級收斂的。 例2.10 設(shè) 𝑥 ? 是𝑓 𝑥 =0的一個根，且𝑓, &#

30、119909; ? ≠0,（ 𝑥 ? 為單根）證明Newton迭代法至少是二階收斂的。,3、Newton下山法例2.11 求方程f(x)=x3-x-1=0在x=1.5附近的根x*的近似值。解：設(shè)迭代初值 𝑥 0 =1.5，Newton迭代公式為 𝑥 𝑘+1 = 𝑥 𝑘 ? ү

31、09; 𝑘 3? 𝑥 𝑘 ?1 3 𝑥 𝑘 2?1 迭代結(jié)果為（6位有效數(shù)字） 𝑥 1 =1.34783， 𝑥 2 =1.32520， 𝑥 3 =1.32472如果初值為 𝑥 0 =0.6，則 𝑥 1 =17.9，迭代發(fā)散,對迭代過程附加一項要求（

32、19891; 𝑥 ? =0） 𝑓 𝑥 𝑘 > 𝑓 𝑥 𝑘+1 下山條件具體方法為松弛法，記 𝑥 𝑘+1 = 𝑥 𝑘 ? 𝑓 &

33、#119909; 𝑘 𝑓, 𝑥 𝑘 取 𝑥 𝑘+1 和𝑥 𝑘 的加權(quán)平均作為迭代改進值 𝑥 𝑘+1 ，即 𝑥 𝑘+1 = 1?𝜌 𝑥 𝑘 +

34、𝜌 𝑥 𝑘+1 于是，得Newton下山法迭代公式 𝑥 𝑘+1 = 𝑥 𝑘 ?𝜌 𝑓 𝑥 𝑘 𝑓, 𝑥 𝑘 𝜌下山因子

35、,下山因子𝜌的選取從𝜌=1開始，判斷 𝑓 𝑥 𝑘 > 𝑓 𝑥 𝑘+1 是否成立 成立，則用Newton迭代法進行迭代 不成立 ，則下山因子𝜌依次在下述集合 1 2 ， 1 4 ，?, 1 2 𝑛

36、 ,? 中選取，直至滿足 𝑓 𝑥 𝑘 > 𝑓 𝑥 𝑘+1 。在例2.8中，仍取初值 𝑥 0 =0.6，經(jīng)過試探，找到𝜌= 1 32 ，得到第一步 𝑥 1 =1.140625，比 𝑥 0 更接近于根x*，從而保證迭代過程收斂。,4、有重根情形的Newt

37、on迭代法 設(shè) 𝑥 ? 為𝑓 𝑥 =0的𝑚重根，即有 𝑓 𝑥 = 𝑥? 𝑥 ? 𝑚 𝑔 𝑥 ， 𝑔( 𝑥 ? )≠0， 𝑚≥2 Newton迭代法的迭代函數(shù)

38、 𝜑 𝑥 =𝑥? 𝑓 𝑥 𝑓, 𝑥 𝜑,(𝑥)= 1? 1 𝑚 + 𝑥? 𝑥 ? 2𝑔, 𝑥 𝑚𝑔 𝑥 + ү

39、09;? 𝑥 ? 2 𝑔,, 𝑥 𝑚 2 𝑔 𝑥 1+ 𝑥? 𝑥 ? 𝑔, 𝑥 𝑚𝑔 𝑥 2 𝜑, 𝑥 ?

40、 =1? 1 𝑚 ≠0,𝜑, 𝑥 ? <1此時，Newton迭代法收斂，但僅為線性收斂。方案一 將迭代函數(shù)𝜑 𝑥 改造為 𝜑 𝑥 =𝑥?𝑚 𝑓 𝑥 𝑓, 𝑥

41、 且有𝜑, 𝑥 ? =0 于是下述迭代公式 𝑥 𝑘+1 = 𝑥 𝑘 ?𝑚 𝑓 𝑥 𝑘 𝑓, 𝑥 𝑘 至少具有是二階收斂的。缺點：事先知道 𝑥

42、; ? 的重數(shù)，一般不可能。,方案二 令𝜇 𝑥 = 𝑓 𝑥 𝑓, 𝑥 ，且𝑓 𝑥 = 𝑥? 𝑥 ? 𝑚 𝑔 𝑥 則𝜇 𝑥 = 𝑥? 𝑥

43、 ? 𝑚 𝑔 𝑥 𝑚 𝑥? 𝑥 ? 𝑚?1 𝑔 𝑥 + 𝑥? 𝑥 ? 𝑚 𝑔, 𝑥 = 𝑥? 𝑥 ? &#

44、119892; 𝑥 𝑚𝑔 𝑥 + 𝑥? 𝑥 ? 𝑔, 𝑥 由此可見 𝑥 ? 是𝜇 𝑥 =0的單根 𝑓 𝑥 =0的重根 𝑥 ? ?𝜇 𝑥 =0的單根 𝑥

45、; ? 取迭代函數(shù)𝜑 𝑥 =𝑥? 𝜇 𝑥 𝜇, 𝑥 =𝑥? 𝑓 𝑥 𝑓, 𝑥 𝑓, 𝑥 2 ?𝑓 𝑥 𝑓,, 𝑥,從而構(gòu)造迭代法

46、𝑥 𝑘+1 = 𝑥 𝑘 ? 𝑓 𝑥 𝑘 𝑓, 𝑥 𝑘 𝑓, 𝑥 𝑘 2 ?𝑓 𝑥 𝑘 𝑓,, 𝑥 𝑘

47、例2.12 方程 𝑥 4 ?4 𝑥 2 +4=0的根 𝑥 ? = 2 是二重根。 (1) 𝑥 𝑘+1 = 𝑥 𝑘 ? 𝑥 𝑘 2?2 4 𝑥 𝑘 Newton迭代法 (2) 𝑥 𝑘+1 =

48、𝑥 𝑘 ? 𝑥 𝑘 2?2 2 𝑥 𝑘 方案一 (3) 𝑥 𝑘+1 = 𝑥 𝑘 ? 𝑥 𝑘 𝑥 𝑘 2?2 𝑥 𝑘 2+2 方案二,初值

49、19909; 0 =1.5方法（2）與（3）二階方法，迭代第三步時精度到 10 ?9 ，方法（1）為線性收斂，要到達相同精度需迭代30次。,5、非線性方程組的Newton迭代法 設(shè)有非線性方程組 𝑓 1 𝑥 1 , 𝑥 2 ,?, 𝑥 𝑛 =0 𝑓 2 𝑥 1 , 𝑥

50、2 ,?, 𝑥 𝑛 =0 ? 𝑓 𝑛 𝑥 1 , 𝑥 2 ,?, 𝑥 𝑛 =0 依次將上述𝑛個方程在點 ? 處做一階Taylor展開，得 𝑓 𝑖 𝑥 1 , 𝑥 2 ,?, &

51、#119909; 𝑛 ≈ 𝑓 𝑖 ? + ?,記作 Ү

52、91; 𝑖 𝑋 ≈ 𝑓 𝑖 𝑋 𝑘 + 𝑓 𝑖 , 𝑋 (𝑘) 𝑋? 𝑋 (𝑘) 這里 𝑋= 𝑥 1 , 𝑥 2 ,?, 𝑥 w

53、899; 𝑇 令 𝑓 1 𝑋 𝑘 + 𝑓 1 , 𝑋 (𝑘) 𝑋? 𝑋 (𝑘) =0 𝑓 2 𝑋 𝑘 + 𝑓 2 , 𝑋

54、(𝑘) 𝑋? 𝑋 (𝑘) =0? 𝑓 𝑛 𝑋 𝑘 + 𝑓 𝑛 , 𝑋 (𝑘) 𝑋? 𝑋 (𝑘) =0 由此得非線性方程組的

55、Newton迭代公式,例2.13 用Newton迭代法求解下列方程組 𝑓 1 𝑥 1 , 𝑥 2 = 𝑥 1 2?10 𝑥 1 + 𝑥 2 2+8=0 𝑓 2 𝑥 1 , 𝑥 2 = 𝑥 1 𝑥 2 2+ 𝑥 1 ?10

56、 𝑥 2 +8=0 建立迭代公式。 例2.14 給定函數(shù)𝑓 𝑥 ，設(shè)對一切𝑥，𝑓, 𝑥 存在，而且0<𝑚≤𝑓, 𝑥 ≤𝑀。證明對0<𝜎< 2 𝑀 的任意常數(shù)𝜎，迭代法 𝑥