數(shù)值分析講稿

1、數(shù)值方法（A）講稿周 富 照數(shù)值方法（A）講稿（周富照）數(shù)值方法研究的對象：各種數(shù)學(xué)問題求解的數(shù)值計算方法。就是研究用計算機解決數(shù)學(xué)問題的數(shù)值計算方法及其理論。包括方法的穩(wěn)定性、收斂性及誤差分析，還要根據(jù)計算機特點研究計算時間最省的計算方法。實際問題的解決過程：實際問題數(shù)學(xué)問題計算方法上機實現(xiàn)實際問題第一章 緒 論掌握誤差的來源、衡量誤差大小的一些標(biāo)準(zhǔn)、控制誤差的一些原則1.1 誤差的來源與分類 在工程和科學(xué)計算中，估計計算結(jié)果的精確度是很重要的。而影響精確度的是各種誤差。誤差按照它們的來源可分為以下四種：1. 模型誤差數(shù)學(xué)模型一般只能近似的描述實際問題，如勻速運動認(rèn)為速度(近似地)為常數(shù)，勻

2、加速運動認(rèn)為速度為時間t的一次函數(shù)。在動力學(xué)中，若認(rèn)為阻力R是速度 v = x (t) 的一次函數(shù)：R = v，將v的高次項的影響略去，可得線性微分方程模型(見同濟高數(shù))。2. 觀測誤差數(shù)學(xué)模型中包含的某些常數(shù)(時間，長度等)由于受儀器的限制觀測結(jié)果不能絕對準(zhǔn)確。如測量距離時為了減少測量誤差，一般取兩次往返測量的平均值。3. 截斷誤差有些函數(shù)需要用無窮級數(shù)計算，計算時只能取前幾項。如 當(dāng)x充分小時取 sin x x，其誤差 。4. 舍入誤差在計算機上要把一些數(shù)字四舍五入后再計算如：因為我們主要是在已給數(shù)學(xué)模型的基礎(chǔ)上研究計算方法的，所以只考慮后兩種誤差。1.2 誤差概念或誤差的衡量標(biāo)準(zhǔn)絕對誤差

3、（限）、相對誤差（限）和有效數(shù)字 1. 絕對誤差 設(shè)某量準(zhǔn)確值為x，近似值為x*，稱 e = x x*為近似值x*的絕對誤差。簡稱為誤差。 在同一量的不同近似值中，|e (x)|越小，x*的精確度越高。2. 絕對誤差限 由于精確值x實際上是不知道的，故絕對誤差e也不能求出。在實際計算中，可根據(jù)情況事先估計出它的大小范圍。即預(yù)先指定適當(dāng)小的正數(shù)，使得 | e | = | x x* | 稱為近似值x*的絕對誤差限。有時也用 x = x* 表示近似值的精確度或準(zhǔn)確值的范圍。 例如，取的近似值為 a，則 e = a， | e | 0.0003。 3. 相對誤差絕對誤差有時不足以表示近似值的好壞。例如，

4、若有兩個近似數(shù)x1 =100 1（m）， x2 =1000 1(m)其絕對誤差限都是1(m), x1* = 100(m), x2* = 1000(m)，與近似值本身比較，x2*較精確。記 稱er為近似值x*的相對誤差。如以上問題中的x1相對誤差為1，x2為。 相對誤差越小者越精確。相對誤差在誤差分析中更能反映出誤差的特征。它無量綱，與所取單位無關(guān)。4. 相對誤差限 和絕對誤差一樣，er 也不能求出，可預(yù)先指定適當(dāng)小的正數(shù) r，使得 ，或 。 r稱為近似值x*的相對誤差限。5. 有效數(shù)字近似值的準(zhǔn)確程度可用有效數(shù)字來描述。定義 設(shè)x*是的近似值，若x*的絕對誤差限是它的某一位的半個單位，并且從該

5、位到它的第一位非零數(shù)字共有位，則用x*近似是具有位有效數(shù)字。相對誤差與有效數(shù)字位數(shù)有關(guān)。有效數(shù)字位數(shù)越多，相對誤差限越小。例1 設(shè)，0.005 是經(jīng)四舍五入得到的近似數(shù)，分別求出它們的絕對誤差限和相對誤差限。由此可得什么結(jié)論? 解 絕對誤差限：，。 相對誤差限：0.02%，0.02%，10%。例2 下列各近似值的絕對誤差度是，它們有幾位有效數(shù)字。 （4位），（2位），（0位） 1.3 誤差的傳播設(shè) 是可微的,是的近似值, ，則問題是：當(dāng)()很小時，是否很??？ 當(dāng)()很小時，是否很小？ 下列公式很容易從對應(yīng)公式求得：， ，故可取 ， 簡單地說，兩數(shù)之和(差)結(jié)果保留的小數(shù)位數(shù)與位數(shù)較少的加數(shù)相同

6、，兩數(shù)之積(商)保留的數(shù)字位數(shù)與有效數(shù)字較少的因數(shù)相同。但其誤差可能超過末位半個單位，這樣保留的數(shù)除最后一位數(shù)字外都是有效數(shù)字。詳細(xì)分析如下例. 例2 計算 ( 62.33)并分析誤差，設(shè)因數(shù)都是四舍五入所得(計算結(jié)果只保留有效數(shù)字)。解 設(shè)x，y，由 d(xy) = ydx + xdy 得 (xy) = |y|(x) + |x|(y)。 (x，(y， (xy) + 0.0005 = 0.0016 + 所以要四舍五入保留1位小數(shù)(為什么?)： ( 62.33) = 20.1949 。1.4 數(shù)值運算中的一些原則 算法穩(wěn)定性的若干原則一個算法若計算結(jié)果受原始數(shù)據(jù)誤差影響很小，便稱之有較好的數(shù)值穩(wěn)

7、定性。因為在計算機中進行運算會產(chǎn)生舍入誤差。為了減少舍入誤差的影響，設(shè)計算法時應(yīng)遵循以下一些原則：1. 要設(shè)法控制誤差的傳播2. 相近的數(shù)相減的改進措施因為 | x y|太小會使相對誤差擴大。1)若是兩個根式相減，可將分子分母同乘以它的有理化因式。如取四位數(shù)字計算： (只有一位有效數(shù)字) (有四位有效數(shù)字)2)若是兩個三角函數(shù)相減，可和差化積后再計算。如：o o sin 30 oo o。3) 若是超越函數(shù)在兩個相近點的函數(shù)值相減，可用Tailor公式或中值定理： f (x2) f (x1) = f ( ) (x2 x1)， (x1, x2)例 比較三種算法：ln 3.000 001 ln 3

8、= ln (3.000 001 / 3) 0.000 001 / 3.000 000 5。用計算器計算結(jié)果分別為: 3.333 3107，3.333 299 444107，3.333 332 778107 (把計算結(jié)果乘以10 7才能顯示10位)。更精確的解為3.333 332 777 777 9107。3. 兩數(shù)相加要防止較小的數(shù)加不到較大的數(shù)中連加時，要把絕對值較小的數(shù)放到前面先加。如：在4位有效數(shù)字的計算機上計算 0.3 + 0.3 + 0.4 + 1234，1234 + 0.4 + 0.3 + 0.3 結(jié)果不同。4. 減少運算次數(shù)這樣可以減少誤差積累。如計算多項式可用秦九韶算法： 例

9、2 x3 3 x2 + 4 x 5 = (2 x 3) x + 4) x 5。5. 避免除數(shù)絕對值太小因為 d (x/y) = (ydx xdy) / y2，| y | 太小會使絕對誤差擴大。6. 編程時避免用等式條件 例題下列各題右端算法精度較高：1. ， |x| 1，和差化積。2.3.，N充分大。4.，|x| 1，用Tailor公式。記住 (1+x)a, ex, ln(1+x), sin x, cos x, tan x, cot x 的Tailor公式：，。 5計算，取，利用下列等式計算，哪一個得到的結(jié)果最好？6序列滿足遞推關(guān)系）若（三位有效數(shù)字），計算到誤差有多大？這個計算過程穩(wěn)定嗎？

10、7 給定 ，試用四位數(shù)學(xué)用表求的近似值。 甲方法：， 乙方法：，而，問題那一個方案較正確？分析：記 ，其中 ，三角函數(shù)表給出了四位數(shù)字，它準(zhǔn)確到小數(shù)后第三位，而第四位是經(jīng)過“四舍五入”得到的，即有，乙比甲好，實際答案。第二章 插值與逼近2.1 引 言1、插值問題：在實踐中經(jīng)常遇到這樣的函數(shù)，它太復(fù)雜或僅僅是一些測量數(shù)據(jù)，就需要用較簡單函數(shù)近似表示: 。 已知y = C a，b 在n+1個互異節(jié)點a = x0 x1 xn = b處的函數(shù)值=，i = 0, 1, , n。為某一函數(shù)類，求滿足: (xi) = yi （1）稱這個問題為插值問題，為的插值函數(shù)，為被插值函數(shù)，x 0, x 1, , x

11、n 為插值結(jié)點，（1）式為插值條件。2、解決問題包含的內(nèi)容（1）確定（有限維空間只要確定一組基）；（2）討論滿足（1）式的是否存在？是否唯一及如何求？（3）討論截斷誤差 的表達(dá)式與估計。常用插值函數(shù)類有: 多項式，三角函數(shù)，有理函數(shù)等。對應(yīng)插值法分別稱為代數(shù)多項式插值，三角多項式插值，有理函數(shù)插值。下面主要討論代數(shù)多項式插值。2.2 代數(shù)插值問題1、代數(shù)插值問題設(shè)表示所有次數(shù)不超過的多項式的集合。其它條件如上，求滿足, i = 0, 1, , n （1）2、存在唯一性：定理 滿足條件（1）式的代數(shù)插值多項式存在且唯一。，有 （2）求求一組數(shù)，將（2）式代入（1）式： （3）的存在唯一性方程組（

12、3）的解的，的存在唯一性（3）的系數(shù)矩陣的行列式為n+1階Vandermonde行列式由于結(jié)點互異，所以 Vn 0，故方程組（3）存在唯一解(a 0，a 1，a n )。3、插值多項式的求法: Lagrange插值多項式下面我們用另一種方法確定多項式。令 ，k = 0, 1, , n （6）則lk (x)滿足條件 k=0, 1, , n （7）記 （8）則有 ，i = 0, 1, , n.所以 稱上式為Lagrange插值多項式, 稱lk(x)為以、為結(jié)點的Lagrange插值基函數(shù)。 注：（1）n=1時，線性插值公式， ，或 （2）n=2時，二次插值（或拋物線插值）公式：4、插值余項設(shè)為 f

13、 (x) 的n次Lagrange插值多項式，其余項為R n (x) = f (x) 定理 設(shè) f C n+1 a, b，則對任意 x (a, b) ，存在 (a, b) ，使得 （4）其中 。證 當(dāng)x = xi 時定理成立。下設(shè) x xi，作 （可根據(jù)不同層次進行取舍） （5）則 C n +1 a, b，且，即在a, b上有 n + 2個零點 t =。應(yīng)用Rolle中值定理，在(a, b)內(nèi)至少存在n + 1個點 0 , 1 , , n, 使得：F ( i) = 0，i = 0, 1, 2, , n。如此反復(fù)應(yīng)用Rolle中值定理，可知在(a, b)內(nèi)至少存在一點使得因為，所以有由此可得定理的

14、結(jié)論。 幾點說明：(1) 插值多項式本身只與插值結(jié)點及f (x)在這些點上的函數(shù)值有關(guān)，而與函數(shù)f (x)并沒有關(guān)系。但余項R n (x) 卻與f (x)聯(lián)系很緊。具體估計時f (n+1)()可取 |f (n+1)(x)| 在區(qū)間上的最大值：|Rn(x)| M |n+1 (x)| / (n+1)!，M = max x a, b |f (n+1) (x)|。有些函數(shù)的 |f (n+1)(x)| 隨 n 增長很快，最好采用分段低次插值。 (2) 若f (x)為次數(shù) deg (f ) n 的多項式，那么以n + 1個點為結(jié)點的插值多項式就一定是其本身。因此時 f (n +1) ( ) 0，故R n

15、(x) = 0。還進一步推出一些結(jié)果，見書后習(xí)題。(3) 當(dāng)點x位于x 0 , x 1 , x n 的中部時， | n+1 (x) | 比較小，精度較高。位于兩端時，精度較低。若點x位于 x 0 , x 1 , x n 的外部，一般稱為外插，精度更低。見下圖所示。 4 (x)= (x2 0.09) (x2 0.01) 6 (x)= (x2 0.25) (x2 0.09) (x2 0.01)圖5-1圖5-2例1 sin 15o，sin 16o，求 o解 故 o = 0.2622.例2 x和y的觀察數(shù)據(jù)如下表，試求Lagrange插值多項式x012 y 123解 這說明的次數(shù)可以小于n 。例3 已

16、知函數(shù)的觀測數(shù)據(jù)為x1234 y 0-5-63（1）試求拉格朗日插值多項式；（2）分別用線性插值和二次插值求解：（1）（a）求插值基函數(shù) ， =（b）求(2) 線性插值：（如何取點？?。?，二次插值：（如何取點？?。┮陨辖Y(jié)果說明什么？2.3 分段線性插值1是f(x)在a,b上的拉格朗日插值函數(shù)，當(dāng)插值節(jié)點無限加密時，在a,b趨于f(x)嗎？2分段線性插值 已知y = f (x) C a , b 在n+1個互異節(jié)點a = x0 x1 xn = b處的函數(shù)值yi = f (xi ), i = 0, 1, , n. 試求,，使 （1）， i = 0, 1, , n. （2）在，i = 0, 1, ,

17、 n-1上是一次多項式這樣的稱為f(x)在a,b上以a = x0 x1 xn = b為節(jié)點的分段線性插值多項式。注 （）這樣的使存在唯一的：只將上的一次插值多項式拼接起來即可。，i = 0, 1, , n-1（）記，i = 0, 1, , n-1，定理 若f(x)在a,b上連續(xù)，則，。2.4 Newton插值公式 差商與Newton插值多項式Lagrange公式優(yōu)點：對稱，很容易寫出。缺點：增加結(jié)點要重新計算。若寫成 (1)則可以逐次計算出： a0 = f (x0), , 每增加一個結(jié)點只需增加一項，前面的項不變。下面利用差商概念導(dǎo)出Newton差商插值多項式，就能很快確定系數(shù)。 1. 差商設(shè)

18、函數(shù)y = f (x)在xi , xj 上有定義，稱 為 f (x)在xi , xj 上的一階差商。稱 為 f (x)的二階差商.已知 k 階差商 f xi , xi+1, xi+k，f x i +1, x i+2 , x i+k+1 ，定義 k + 1 階差商為 并規(guī)定零階差商為函數(shù)本身：f xi = f (xi)2.5 埃米爾特（Hermite）插值1、問題：已知y = f (x) C a , b 在n+1個互異節(jié)點a = x0 x1 xn = b處的函數(shù)值yi = f (xi )和導(dǎo)數(shù)值, i = 0, 1, , n。求 ，使 ， i = 0, 1, , n （1）2、Hermite插值

19、多項式的求法 令 ， （2）其中是不超過次的多項式。顯然 由 ，得，由多項式插值：代入（2）式得+。2.6 三次樣條插值多項式插值問題：結(jié)點增加，次數(shù)升高，計算量增大，波動增大。圖5-3為的圖象(實線)及將1, 1分成10等分所作Lagrange插值多項式P10 (x)的圖象(虛線)。P10 (x)只中部較好的靠近f (x)，越往兩端震動越大(叫Ronge現(xiàn)象)。改進方法：分段低次插值。若還要求結(jié)點處要光滑，就是樣條插值函數(shù)。1三次樣條函數(shù) 設(shè)給定區(qū)間 a, b 上n + 1個點：a = x0 x1 xn = b。若 s (x) 滿足：(1) 在每個子區(qū)間xk1, xk (k = 1, 2,

20、, n)上， s (x)為不超過三次的多項式；(2) 在a，b上有二階連續(xù)可導(dǎo)則稱s (x) 是a，b上以 x1, x2, , xn1 為內(nèi)部結(jié)點的三次樣條函數(shù)。a，b區(qū)間上以為節(jié)點的所有三次樣條函數(shù)的全體記為。2三次樣條插值問題 求 使，滿足上式的s (x)稱為的（在a，b上以為節(jié)點）三次樣條插值函數(shù)。3三次樣條插值函數(shù)的求法（之前簡單分析三次樣條插值函數(shù)的存在性和唯一性問題）（1）三彎矩方程組方法（1）令(= 0, 1, , n)，設(shè)x , ，則s (x)為過兩點，的線性函數(shù)。設(shè)，則 （1）對上式積分兩次，得 (2) (3)根據(jù)插值條件：，得 ，由此解得 代入(2)式得 (4)由此得x ,

21、 時有： (5)當(dāng)x , 時， (6)根據(jù)三次樣條插值函數(shù)的定義應(yīng)有：，由此得： (7)令 , 代入(7)式得三彎矩方程，或 (8)此方程組有 n + 1個未知量，但只有 n 1個方程，還需根據(jù)實際問題補充兩個條件(端點條件)。 已知兩端點x0及xn處的導(dǎo)數(shù)和：，。由式(5)，(6) 也即 (9)其中 將(8)與(9)兩個方程組聯(lián)立，得 (10) 函數(shù) y = f (x) 在端點曲率為已知常數(shù)：，=。代入方程組(8)即可。M0 = Mn = 0 時稱所得的樣條為自然樣條，表示兩端點為簡支的情況。 函數(shù) y = f (x) 以 b a = xn x 0為周期： y0 = yn , s(x 0)

22、= s(x n)， s(x 0) = s(x n)，由于 hn+1 = h1，Mn = M 0，yn = y0，利用(5)式和(6)式可得 。于是 由此得 (11)其中 由(8)式和(11)式得 (12)可用推廣的追趕法求解。（2）三轉(zhuǎn)角方程組方法設(shè)，由，利用Hermite插值公式有+， （1）由上式得類似得 由（）有 （） （2）考慮邊界條件（1），即，已知，代入（2）式得 （3）（用什么方法求解？）解方程組（3）得 ，代入（1）式得。這樣求的方法稱為三轉(zhuǎn)角方程組方法。若考慮邊界條件（2），已知，得 (4)其中 ，結(jié)合（2）式和（4）式得 （5）解方程組（3）得 ，代入（1）式得。至于周期性

23、邊界條件類似可得結(jié)論。例1 已知插值條件：，與邊界條件：，求在1，3上的三次樣條插值函數(shù)。解：（1）， 三轉(zhuǎn)角方程組： 結(jié)合：，有（2）代入（1）式得 例2 給出四個樣點(1, 1)，(2, 3)，(4, 4)，(5, 2)，求其各個子區(qū)間上的樣條插值函數(shù)s(x)，并求f (3)。設(shè)已知 y0= 2，y3= 3。解 求Mk 的方程組為：列表計算,如下，其中Dk = (yk yk 1) / hk-1：khk= xk+1 xk x kykDk 0112 (=y0)012/31232 3 21/32441/2 5 3152 2 64 3 (=y3)代入方程組得 解得 代入(3)，化簡得 而 f (3

24、) s (3) = (533 4 32 + 199 。例3 已知數(shù)據(jù)表x1245y1342及邊界條件。求其各個子區(qū)間上的樣條插值函數(shù)。解：（1）n=3，；，（2）三彎矩方程組為（3）代入(3)，化簡得 。例4 已知插值條件：，與邊界條件：。求在1,3上的三次樣條插值函數(shù)。解 求的方程組為：列表計算，如下，其中Dk = (yk yk 1) / hk-1：khk= xk+1 xkx kykDk0111(=y0)611/21232-1821/213-1-430 31(=y2)代入方程組得 解得 ，代入(3)，化簡得 2.7 最佳平方逼近與正交多項式一、幾個概念1：上所有連續(xù)函數(shù)組成的集合2上的權(quán)函數(shù)

25、：（1），；（2）存在，（3）且非負(fù)，若，則=0，3上的內(nèi)積：若，是上的權(quán)函數(shù)，則稱為關(guān)于在上的內(nèi)積。4若與的內(nèi)積為零： 則稱f與g關(guān)于在a,b上正交。5若滿足則稱為正交函數(shù)族。6，若當(dāng)且僅當(dāng)，時， 則稱線性無關(guān)。7一般逼近問題 已知，求使其中表示在空間中與的距離。稱為最佳逼近元素。若取 ，則上問題稱為最佳一致逼近問題；若取，則上問題稱為最佳平方逼近問題。二、最佳平方逼近問題1、最佳平方逼近問題解的存在唯一性設(shè)，且線性無關(guān)。， （1）求求一組數(shù)，記 （2）， （3）記 ，方程組（3）化為 （4）因線性無關(guān)，所以。定理 設(shè)如上定義，則對，存在唯一的使2、求最佳逼近元素的步驟：（1）令，求， 。（

26、2）求解方程組（4）得：（3）將代入（1）式即得。問題：（a）方程組（4）是否有解？如何求解？用什么方法求解？(b) 與有關(guān)，是否可選取使盡可能簡單？2.8 正交多項式系1、定義 （1）Legendre多項式系 在-1,1上， ，（2）Chebyshev多項式系-1,1上，2性質(zhì)（1）（正交性）Legendre多項式系是-1,1上以的正交多項式系Chebyshev多項式系是-1,1上以的正交多項式系證： （2）（奇偶性），（3）（遞推公式），證： （4）（）在-1,1上有個相異的實零點。例1 設(shè)（2+x），x-1,1，求它在上的最佳平方逼近多項式。解：取，例2 設(shè)，求它在上的最佳平方逼近多項式

27、。 解： ， ， ， ，解方程組 ， 2.9 曲線擬合的最小二乘法1、問題 已知一組數(shù)據(jù)，求使 （1）求滿足（1）式的的方法稱為最小二乘法（曲線的最小二乘擬合），稱為最小二乘擬合曲線。2、求解取 ，線性無關(guān)。， （2）記 求求一組數(shù)；求求的最小值點。由多元函數(shù)求最值的方法，令， （3）記 ，（2）式 （4）因為，線性無關(guān)，可以證明，從而（4）有唯一解，解記為 ?？梢宰C明總結(jié)求的步驟： （1）先確定，；（實際情況如何確定？） （2）計算 ， （3）解方程組（用什么方法求解？）得解 ； （4） 得 例1 已知 012312579421試求它的最小二乘擬合曲線（。解：（1）取直角坐標(biāo)系，描點，由圖可

28、知，這些點位于一條雙曲線附近。取 ，即，； （2） ，=1.842857, =1.310408，=16， (3) 解方程組得解，問題：能否找到這樣一組基使方程組（4）的系數(shù)矩陣為簡單形式？可找到這樣的使=（最小二乘的）多項式擬合若取，則總結(jié)求（最小二乘多項式擬合曲線）的步驟： （1）計算 ， （3）解方程組（用什么方法求解？）（稱為正規(guī)方程）得解 ； （4） 得 若記 ，則 ，正規(guī)方程組 例1 用一次函數(shù) y = a + b x 擬合右表所列數(shù)據(jù)123035解 這里 ，.(正規(guī)方程組：)解得 b = 5/2，a = 7/3。所求擬合曲線為 y = 2.5 x。例2 求一個經(jīng)驗函數(shù) (x)=ae

29、bx 使它能與下表所列數(shù)據(jù)相擬合：xk12345678yk解 對經(jīng)驗公式兩邊取對數(shù)： ln (x) = ln a + bx。令A(yù)= ln a，B=b，u= ln (x)，則擬合曲線方程可化為：u=A+Bx。故只需對x和ln y的函數(shù)表用例1中的方法先求出A，B，再求a，b。其余請同學(xué)們自己完成。例3 已知三次樣條函數(shù)在上的表達(dá)式為，且，求在及上的表達(dá)式。答案：例4 已知三次樣條函數(shù)在上的表達(dá)式為，且，求在及上的表達(dá)式。答案：設(shè)在，及上的表達(dá)式分別記為，和；又設(shè)，由，得，。其余同理。例5 設(shè)是以互異的為節(jié)點的Lagrange插值基函數(shù)，證明 簡答：（1）記 ，的Lagrange插值函數(shù)為，因，所

30、以由插值余項公式，即（2） 。例6 已知在，上，求。簡答： ， ， ，。例7 已知插值條件：，與邊界條件：。求在1,3上的三次樣條插值函數(shù)。簡答：（1）， ，； （2）三轉(zhuǎn)角方程組 ，結(jié)合 ，得； （3）由公式+ +，算得。第四章 數(shù)值積分1 理論：若在上連續(xù)，且 。則2 實際問題：下列情況如何計算？ （1）的計算相當(dāng)復(fù)雜時； （2）不是初等函數(shù)時； （3）不知的解析式，而只知在若干點上的值。3 機械求積法取：用形如 其中 只與有關(guān)，而與無關(guān)。這類方法稱為機械求積法；：求積節(jié)點；：求積系數(shù)4.1 NewtonCotes求積法1NewtonCotes求積公式 設(shè)：，作在上拉格朗日插值多項式，記，

31、 （1）因為用近似，所以可用近似，于是得 ， （2）（2）式稱為階NewtonCotes共識，稱C i(n) (i = 0, 1, , n)為Cotes求積系數(shù)。注： 滿足 （可簡單證明），； 當(dāng)時，得梯形公式：當(dāng)n=2時得拋物線(Sympson)公式：當(dāng)n=3時， 例 用n=15階 Newton-Cotes求積公式計算()計算結(jié)果n123452NewtonCotes求積公式的誤差 截斷誤差， 代數(shù)精度定義 若某個求積公式對于任意次數(shù)不高于m的多項式準(zhǔn)確成立，而存在一次數(shù)為 m + 1的多項式使之不準(zhǔn)確成立，則稱這一求積公式的代數(shù)精確度為m。定理 設(shè)f (x)在區(qū)間a, b上具有連續(xù)的二階導(dǎo)數(shù)

32、，則梯形求積公式的誤差為 設(shè) f (x) C 4 a, b，則拋物線公式的誤差為： n階NewtonCotes求積公式至少有次代數(shù)精度。 當(dāng)為偶數(shù)時，n階NewtonCotes求積公式至少有次代數(shù)精度。證 這里n = 1，在區(qū)間a, b上2 (x)=(x a)(x b)不變號，f (x)連續(xù)，由積分第二中值定理，存在 (a, b)使得 因為NewtonCotes求積公式的余項為： 若deg (f ) n，則 f (n+1) ( ) = 0，故n階NewtonCotes求積公式對于任何次數(shù)不高于n的多項式是精確的。 設(shè)為一次數(shù)為n+1的多項式，則（常數(shù)），所以 =0例 分別求梯形公式和拋物線公式

33、的代數(shù)精度（分別為1和3）。（注意求的步驟和方法）3NewtonCotes求積公式的數(shù)值穩(wěn)定性與收斂性 當(dāng)不大時，數(shù)值穩(wěn)定； 當(dāng)較大時，數(shù)值不穩(wěn)定； 當(dāng)（或）時，不收斂于。證： 設(shè)的實際計算值為，的近似值為，(b-a)， (b-a)， ，因，所以結(jié)論成立。4.2 復(fù)化求積公式為提高精度，使用高階求積公式，這樣存在的問題：（1）很大時，計算很復(fù)雜；（2）很大時，不一致收斂于，從而不收斂于；（3）很大時，數(shù)值不穩(wěn)定。1復(fù)化梯形公式將a, b n等分， ，在每個子區(qū)間上應(yīng)用梯形公式， （1） 得復(fù)化梯形公式：， （2） 復(fù)化梯形公式的截斷誤差： ， （3）（3）式的證明：由梯形公式的截斷誤差易知 ，

34、 （4）由連續(xù)函數(shù)界值定理知, (a, b) 使得： 代入（4）即得（3）式。實際估計取 2復(fù)化拋物線公式類似復(fù)化梯形公式，把區(qū)間a, b分成n個相等的子區(qū)間xi, xi+1(i = 0, 1, , n 1)，每個子區(qū)間上應(yīng)用拋物線公式， （5） 復(fù)化拋物線公式：， （6） 復(fù)化拋物線公式的截斷誤差： ， （7）實際估計取 同理可推出復(fù)化Cotes公式。 例1 若用復(fù)化梯形公式和復(fù)化拋物線公式計算積分，問積分區(qū)間要等分多少才能保證有5位有效數(shù)字?解 由余項公式因為 f (x) = f (x) = = e x, b a = 1故 或 由 | R | 10 4/2，得 n (e10 4/6)1/2

35、 =68 (梯形公式)，或 n (e104/1440)1/4 =2.1(拋物線公式，因區(qū)間是2n，實際上還要乘以2，故6等分即可)。由此可知，使用拋物線公式比使用梯形公式可大大提高計算效率。例 分別用復(fù)化梯形公式和復(fù)化拋物線公式計算，使精確到解：（1）取，81689， （2）取，例2 將0, 1區(qū)間分成8等分，分別用復(fù)化梯形公式和復(fù)化拋物線公式計算：解 將分點及函數(shù)值列表如下i012345678xi011/(1+xi2)10.5 ，I ，I (1/24)1+0.5+2(0.9412+0.8+0.64)+4注：；復(fù)化梯形公式和復(fù)化Simpson公式都是數(shù)值穩(wěn)定的。3 變步長公式 實際計算時因為難

36、以事先估計步長，往往借助于計算機自動選擇步長。下面介紹變步長拋物線公式（拋物線法的遞推化）。 第一步 將區(qū)間a, b分成2等分， 計算 第二步 將區(qū)間a, b分成4等分， 計算(xi = a + ih, h = (b a)/4，i = 0, 1, 2, 3, 4)： 若，則停止計算；否則繼續(xù)將每個小區(qū)間2等分，計算，若， 則以作為所求積分近似值。否則繼續(xù)將區(qū)間分半進行計算。注： （1）當(dāng)在a,b上變化很小時，有 ； （8）（2）當(dāng)在a,b上變化很小時，有 。 （9）（3）當(dāng)和無法估計時，如何估計的誤差？事后估計方法：用做為估計，即|（或）（或）。 由（8）和（9）式可以認(rèn)為 比的效果好，比的效

37、果好。實際上可以推出， ，（Romberg求積法）（5），與的關(guān)系：，：， ， ， 。4.3 Romberg 求積法一、Richardson外推法設(shè)常量，用的函數(shù)來近似它，設(shè)已知+， （1）其中與無關(guān)，單調(diào)遞增，取，+， （2） （3）有+， （4），（），與無關(guān)，一般地，可歸納做出， （5）以上這種方法稱為Richardson外推法。二、Romberg求積法將Richardson外推法應(yīng)用于復(fù)合梯形公式可得收斂性很好的數(shù)值求積法Romberg求積法。記 （6），當(dāng)在a,b上滿足一定條件時，有+， （7）其中與無關(guān)，（6）式中用代，+， （8） （9）有+， （10）類似從（9）式出發(fā)，+，

38、（11）一般地，可歸納做出， （12）由上式，可推得一種新的求積法，其步驟：(1) 取，由（6）式計算 再取，遞推計算如下兩步（）， （）對，計算 （3）對給定的誤差，若有 ，即可停機，取，否則k+1代k轉(zhuǎn)向（）。上述方法是逐次平分區(qū)間，是用復(fù)合梯形公式，在配合Richardson外推法，這種方法稱為Romberg求積法。實際計算時如表：， 0123誤差注（1）是復(fù)合梯形序列，是復(fù)合Simpson序列，是復(fù)合Cotes序列，他們與，統(tǒng)稱為Romberg序列。（2）由于當(dāng)較大時，再做組合意義不大，通常算到即可。（3），例 用Romberg 求積法計算，使誤差不超過。解：將計算結(jié)果列表如下k010

39、.939793323 ，例 已知，求。 解：，4.4 Gauss型求積法前面提出的新的求積公式目的主要是改善截斷誤差。這節(jié)將討論是否可以提高代數(shù)精度？在求積區(qū)間上節(jié)點數(shù)不變情況下是否可以通過選擇節(jié)點，以提高求積公式的代數(shù)精度？一、Gauss型求積公式 1. 定義 設(shè)節(jié)點，求積公式， （1）其中 ，若（1）式至少有次代數(shù)精度，則稱它為Gauss型求積公式，稱為Gauss點，稱為Gauss求積系數(shù)。2. Gauss點的性質(zhì)定理 是Gauss點的充要條件：對次數(shù)不超過的任意多項式，與在上正交其中。證明：是Gauss點，任取次數(shù)不超過的多項式，是不高于的多項式，于是。若上式對任意次數(shù)不超過的多項式成立

40、，考慮次數(shù)不超過的多項式，記，次數(shù)不超過，=，而 ，即說明是Gauss點。3. Gauss-Legendre求積公式，是-1,1上以為權(quán)的正交多項式系。 設(shè)在-1,1上零點為，則是求積公式 （4）的Gauss點。例 （1）取的零點為節(jié)點，作求積公式令它對嚴(yán)格成立，得，從而得零階Gauss-Legendre求積公式 （2）取的零點為節(jié)點作求積公式令它對精確成立：于是一階Gauss-Legendre求積公式它有3次代數(shù)精度。二 Gauss型求積公式的截斷誤差、代數(shù)精度、數(shù)值穩(wěn)定性和收斂性1. -,；2 . 代數(shù)精度為；Gauss型求積公式是數(shù)值穩(wěn)定的 證明：先證，再證 設(shè)的實際計算值為，記，。證畢

41、 4. Gauss型求積公式是收斂的。例1 證明中矩形求積公式是高斯型求積公式 。 設(shè)充分光滑，試確定其余項。證明：因為 當(dāng)時，左邊=右邊； 當(dāng)時，左邊=右邊； 當(dāng)時，左邊=右邊，所以上求積公式有1次代數(shù)精度，是高斯型求積公式。=。 例2 確定，使下面求積公式的代數(shù)精度盡可能高并求其代數(shù)精度 。解：當(dāng)時，左邊=，右邊=； 當(dāng)時，左邊=0，右邊=；當(dāng)時，左邊=，右邊=令 上面左邊=右邊得當(dāng)時，左邊=右邊；當(dāng)時，左邊=右邊=，所以代數(shù)精度為3次。 例3 確定，使下面求積公式的代數(shù)精度盡可能高并求其代數(shù)精度 解：當(dāng)時，左邊=右邊； 當(dāng)時，左邊=0，右邊=；當(dāng)時，左邊=，右邊=；令 上面左邊=右邊得第

42、五章 常微分方程數(shù)值解法 5.1 引 言回顧：微分方程的分類？能求解哪些微分方程？是否所有微分方程都能求解？不能求解的微分方程怎么辦？ 以如下初值問題為例來介紹微分方程的數(shù)值解法。討論初值問題 （1）有解的條件：設(shè) f (x, y)在區(qū)域 R ：a x b, y 上連續(xù)，對y滿足Lipschitz條件：其中，L 為正常數(shù)。設(shè)精確解為。所謂數(shù)值解法就是求在一列點a = x0 x1 x2 x n = b上的近似值，。通常取 xi = a + ih , h=(b a) / n 。 Euler法和改進的Euler法 Euler 法1、Euler公式 因 ，對 所以 ，將 y (xi)用差商近似： ，

43、再用yi近似代替y (xi)，由此得Euler公式(h = xi+1 xi): （2）注：Euler法的幾何意義是 用過點的一條折線近似代替過點的積分曲線。例1 用Euler法求初值問題: 解 （1） Euler公式：，這里，=（2） 算得 y1 = y(0.1) = 0, y2 = y(0.2) = 0.01, y3 = y(0.3) = 0.029, 2、Euler法的截斷誤差 局部截斷誤差和整體截斷誤差（1）局部截斷誤差假設(shè)在計算時用到的是精確值即時產(chǎn)生的誤差記 ，將在處泰勒展開 （3）稱為局部截斷誤差。（2）整體截斷誤差= =+ 反復(fù)利用可得3、Euler方法的數(shù)值穩(wěn)定性 僅就 （4）

44、討論之。 記是（的）實際計算解， 假設(shè)用某個數(shù)值方法求解常微分方程，對給定，產(chǎn)生誤差，若這個誤差在計算后面的，中所引起的誤差按絕對值均不增大，則稱這個數(shù)值方法對和復(fù)常數(shù)是絕對穩(wěn)定的。絕對穩(wěn)定區(qū)域。考慮Euler方法 若 ，誤差就不增大，這時Euler方法絕對穩(wěn)定。Euler方法的絕對穩(wěn)定域為：。 改進的Euler法 因 ，對 所以 ，將用差商近似：再用yi近似代替y (xi)，由此得向后的Euler公式(h = xi+1 xi): （5）其幾何意義為過(xi , yi)作射線與過(xi+1 , y(xi+1)點處曲線的切線平行。結(jié)合（2）和（5）式，得梯形公式: （6）例2 用梯形法解例1。解

45、 公式：yi+1 = yi + 0.05 (xi yi + xi+1 yi+1), 或 yi+1yixi + 0.005)/1.05, 解得 y1 = y(0.1) = (0+0+0.005)/1.05 = 0.004762, y2 = y0.1+0.005)/1.05 = 0.01859, 余見下表.xiEuler法向后Euler法改進的Euler法預(yù)測-校正法k1k20000000910Euler預(yù)測校正法梯形公式是隱式的，求yi+1必須解一個方程。一般我們采用迭代法求解：用Euler公式求出初始近似 yi+1(0)，然后用梯形公式進行校正： 直到滿足 | yi+1(k+1) yi+1(k

46、) | ， 取yi+1= yi+1(k+1) ，再轉(zhuǎn)到下一步計算。只要f (x, y)對y滿足Lipschitz條件，當(dāng)h足夠小時迭代序列收斂。實際應(yīng)用梯形公式公式時，只需進行一次迭代就可以了，由此得梯形公式法的另一形式，或叫Euler預(yù)測校正法。 （7）寫為下面的形式更便于上機計算： （8）例3 用Euler預(yù)測-校正法解例1(y = x y, y(0) = 0)。解 x1 ：k1=00=0，k2，y1；x2：k1，k2， y2(0.095+； 5.3 RungeKutta 法 RungeKutta法1、由微分中值定理 ， （1）Euler公式與上式比較：Euler法是用點的斜率近似代替得出

47、的。上式與Euler預(yù)測校正法比較：Euler預(yù)測校正法是用、上的斜率的平均值近似代替得出的。啟示：當(dāng)取斜率的點數(shù)確定時，可對點的位置和平均權(quán)引進待定參數(shù)，然后選擇參數(shù)已取得較高的局部截斷誤差的階數(shù)。這就是RungeKutta方法的精髓所在?？紤]： （2）選擇參數(shù)，使 （3）的階盡可能高，其中設(shè)有適當(dāng)?shù)墓饣?。因?y (x) = f (x, y (x), y (x) = f x + f y y (x) = f x + f y f , 所以 （4） （5）將上兩式代入（3）式得 （6）令 （7）代入（6）式 如取，得，代入（2）式即得預(yù)估-校正公式； 如取，得，代入（2）式即得 （8）稱之為中

48、點公式。二級二階R-K公式。 是否可選擇使（對）的階更高？可以證明這是不可能的。 類似地可以推導(dǎo)三級、四級以至一般的m-級R-K公式 ， ， ， ， 可推兩個主要公式1、四級四階經(jīng)典R-K公式 (8)2、四級四階Gill公式四階RongeKutta公式不太復(fù)雜，精確度也夠高。高于四階的公式計算量大，精確度也并不一定提高，有時還會降低。 RK法的絕對穩(wěn)定區(qū)域以四級四階經(jīng)典RungeKutta方法為例針對討論，得=于是 =相應(yīng)的誤差方程=由此得絕對穩(wěn)定區(qū)域5.4 單步法的收斂性計算公式訪法的收斂性：對，有 定理 若（1）（2）在上滿足，（3）則 （1）；（2）當(dāng)時，方法是收斂的。5.5 解橢圓型方

49、程的差分法設(shè)有Poisson方程第一邊值問題：Laplace算子 區(qū)域的離散化， ，步長；節(jié)點；相鄰節(jié)點；內(nèi)部節(jié)點；邊界節(jié)點； 微分方程的離散化 （3） （4）引入網(wǎng)絡(luò)差分算子+ （5） （6）稱為微分方程（1）的五點差分格式，他的解稱為差分解。注 （1）正方形網(wǎng)格，（6）式變?yōu)?（7） （2）用（6）逼近（1）的截斷誤差 有 稱差分方程（6）與微分方程（1）是相容的。 邊界條件的處理1、矩形區(qū)域（矩形網(wǎng)絡(luò)），2、一般區(qū)域 （1）直接轉(zhuǎn)移：若邊界點S正好在上，則 若邊界點P不在上，可在上取與P最靠近的網(wǎng)格上的點R，用代： （2）線性插值 邊界點P也可取B、C兩點或R、Q兩點的線性插值作為。 設(shè)

50、，取或邊界點的方程與內(nèi)點的方程構(gòu)成一個方程組。其方程個數(shù)與未知量的個數(shù)相等常用矩形域D：A是不可約對角占優(yōu)，且是大型稀疏帶狀矩陣。采用迭代法求解。例2 用標(biāo)準(zhǔn)4階Ronge-Kutta法解初值問題 解 這里, x0 = 0, y0 = 1, h = 0.2. 利用標(biāo)準(zhǔn)4階Ronge-Kutta公式有計算結(jié)果如下表. ixiyik1k2k3k400111234517 (3) 常微分方程組和二階常微分方程初值問題的RongeKutta公式設(shè)有微分方程組初值問題 (9)其求解公式為: (10)以上公式寫為向量形式與單個方程的公式形式上完全相同, 證明也相仿. 其幾何意義可理解為參數(shù)方程表示的曲線.對

51、二階方程 (11)設(shè) x= y, 則 .y = f (t, x, y). 在(10)式中取 g (t, x, y) y, 得 (12)5.6 Adams 法 RongeKutta法優(yōu)點: 是單步法, 由前一步的 yi 值就可以推得后一步的yi+1 值. 缺點: 當(dāng) f 較復(fù)雜時計算量較大. 未利用前面幾步算得的 y 值.我們知道, 初值問題 y = f (x, y), y (x0) = y0等價于積分方程 過前幾步算得的(xi , yi)作 f (x, y (x)的插值多項式pn(x), 設(shè)余項為R n(x), 則 f (x, y) = pn(x) + R n(x) 舍去余項后得到線性多步法公

52、式: (1) 5.6.1 Adams 顯式取q +1個結(jié)點 xi , xi1 , , xiq ,并作Newton后差插值多項式, 則 (2)其中 x = xi + sh , fi = f (xi , yi). 將(2)式代入(1)式, 得 (3)這里, . (3)式即為Adams顯式.由此得Rq = h q+2 y(q+2) () q . (x iq, x i) (4) m是多項式積分, 列表如后. 通常將(3)中的 m f 用各點已知函數(shù)表示, 如 q=2, 3 時有公式 (5) (6)Adams法系數(shù) m 、m 表m01234 m11/25/123/8251/720m11/21/121/2

53、419/7205.6.2 Adams隱式 顯式公式作插值多項式時未包括xi+1, 精確度較差. 若取q +1個結(jié)點 xi+1 , xi , , xiq+1 ,并作Newton后差插值多項式, 則 (7)其中 x = xi+1 + sh .將(7)式代入(1)式, 得 (8)這里, , m = 0, 1, 2, q. (8)式即為Adams隱式.類似于Adams顯式的余項求法, 可得Adams隱式的余項為: Rq = h q+2 y(q+2) q+1, (xiq+1, xi+1) (9) m 的計算結(jié)果如節(jié)表.將 mfi 用各點已知函數(shù)表示, q = 2, 3 時有公式: (10) (11)5.

54、6.3 Adams預(yù)測校正公式通常將Adams隱式和顯式聯(lián)立使用, 可得Adams預(yù)測校正公式. 以q = 3為例: (12)用pi與ci依次表示第i步y(tǒng)i的預(yù)測值與校正值, 精確值仍記為yi , 由誤差估計式(4), (9)可得 相減得 從而有 由此得 由此給出預(yù)測校正法(12)的另外一種模式(簡稱為PMCM模式):(13)開始時可取 pi = ci = 0 , 以后每步按上式計算. 因為Adams法是多步法, 不能自動開始, 前幾個值依賴于其它方法, 例如我們可以:(1)用RongeKutta法求出開始值.(2)使用 y (x) 的Tailor展開式.5.7 二階線性常微分方程邊值問題在解

55、數(shù)學(xué)物理問題時經(jīng)常遇到各種邊值問題. 這里我們只介紹二階線性常微分方程邊值問題 (1)其中 p (x), q (x), f (x)為區(qū)間a, b上足夠光滑的已知函數(shù)且q (x) 0, , 為已知常數(shù).將區(qū)間 a, b 分成n等分, 將各結(jié)點導(dǎo)數(shù)用差商表示, 可化為差分方程組. 設(shè)y , y 的誤差均為O (h 2). 設(shè) pi = p (xi), qi = q (xi), fi = f (x i), 代入方程(1)得: 兩邊乘以h 2, 整理得 (2)即 (3)例 用差分法解邊值問題 解 這里，h = 0.1, x i i, p = 0, q = 1, f (x) = x, i = 0, 1,

56、 , 10. 代入(3)式得ixi差分解yi精確解yi123456789解得結(jié)果見右表.最后一列為精確解 2 sh x / sh1x.關(guān)于差分方程的收斂性有如下的收斂定理 設(shè) 2 pi h 2, qi 0, i = 1, 2, , n 1, 則二階差分方程(2)有唯一解, 且當(dāng)h 0時收斂于微分方程(1)的準(zhǔn)確解.第六章 非線性方程求根 掌握非線性方程求根的每一種方法的基本思想、理論依據(jù)和基本步驟6.0 引 言1、問題 設(shè)，則至少存在，使得，如何求？我們都會解一元一次方程和一元二次方程，三次以上方程就不會解了。事實上，三次和四次方程的求根公式很復(fù)雜，五次以上代數(shù)方程一般無求根公式，超越方程也只

57、能求近似解。2、求近似解的步驟(1) 判定根的存在性，根據(jù)連續(xù)函數(shù)介值定理 f C a, b, f (a) f (b) 0 (a, b)，使得 f ( ) = 0(2) 確定根的分布區(qū)間: 可列函數(shù)表或求導(dǎo)數(shù)確定單調(diào)區(qū)間。(3) 根的精確化縮小區(qū)間。3、常見的求近似解的方法：二分法、牛頓法、弦割法和拋物線法等 6.1 二分法基本思想：對有根區(qū)間不斷進行二分；理論依據(jù)：區(qū)間套定理和收斂序列的性質(zhì)； 二分法的思想：逐漸二分有根區(qū)間，得一系列有根區(qū)間 ，用某個區(qū)間的中點 作為根的近似值。二分法的理論依據(jù)：得三個序列 ，有，且 二分法的算法（自己完成）：輸入，計算；判別，是輸出，否判別，是，否判別，是

58、輸出，停機；否轉(zhuǎn)（2）結(jié)束例1 用二分法求方程 x 2 2 = 0的根。解 設(shè)f (x) = x 2 2，因f (1) = 1 0, 故在（1, 2）內(nèi)有根。取 x1， 得 f (1.5) = 1.25 0。 取 x2，得 f (1.25) = 0.43 0。令 ，利用介值定理可證至少有一根，再利用反證法證只有唯一根（即）。2) ，由條件（2）知，設(shè)，同理可得，由數(shù)學(xué)歸納法得對，由（3）式得xk。由Lipschitz條件 ；將 代入上式得。 如何構(gòu)造等價方程？（不同的構(gòu)造會得到不同的收斂性） 把方程 f (x) = 0改寫為x = g (x)可以有多種方案。例1 x3 x 1 = 0 在附近有

59、根，把它寫成不同等價形式，判斷各迭代公式的收斂性并迭代求解(保留6位有效數(shù)字，下文同，不再聲明)。 x = x3 1； 。解 設(shè)g1 (x) = x3 1，g1 (x) = 3 x2，| g1 (1.3) | = 3.4 1。故迭代序列xk+1 = xk3 1發(fā)散。 設(shè)。故迭代序列收斂。用它進行迭代，得結(jié)果如下表。因此，x 。k012345678xk例 用簡單迭代法求在2，3上的根。為求在2，3上的根，可構(gòu)造三個同解方程（1），（2），（3）得三個迭代： 一個收斂快；一個收斂慢；一個發(fā)散。 （1），（2），（3）取，結(jié)果如下表0222112-53-1254-19530055 迭代法的局部收斂性

60、若 ，使 對都收斂，則稱上迭代是局部收斂的。定理2 若在根的某個鄰域內(nèi)有連續(xù)導(dǎo)數(shù)，且，則上迭代有局部收斂性。 收斂階定義 設(shè)某迭代有局部收斂性，記ek = s xk 0, k = 0, 1, , 如果存在正實數(shù)r和c使成立，則稱該迭代是r階收斂的。r=1時又稱有線性收斂速度；r=2稱平方收斂。例 xk k，ekk 有線性收斂速度(每算一步小數(shù)點后有效數(shù)字每次增加1位)。 yk 3 k 有三階收斂速度(小數(shù)點后有效數(shù)字成三倍增加)。定理3 設(shè)I = a, b， ，s = g (s) I，g (k) (s) = 0, k = 1, 2, m 1, g (m) (s) 0，則對任何x0 I (x0