數(shù)值分析(計算方法)

1、 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-171數(shù)數(shù) 值值 分分 析析插值、擬合與數(shù)值微積分插值、擬合與數(shù)值微積分主講：劉敬剛劉敬剛 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-172 數(shù)值分析數(shù)值分析(計算方法計算方法) 介紹介紹考慮如下線性方程組 bAx 或者：其中 ,0)det(A由克萊姆法則可知 (1)有唯一的解，而且解為：nnn

2、nnnnbxaxabxaxa1111111(1)nnninninniiiiiaabaaaabaaDADDDx11111111111det),det(,一、引例一、引例 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-173若行列式用按行（列）展開的方法計算 ，(1)(1) !nnn用克萊姆法則求解（1）需做乘除法的次數(shù): 當(dāng)方程組階數(shù)較高時，計算量很大，因此克萊姆法則通常僅有理論上的價值，計算線性方程組的解還要考慮: 首先看一個簡單的例子：1212120 xxxx 121

3、2xx（若是更高階的 方程組呢？）人類的計算能力計算能力是計算工具計算工具和計算方法計算方法效率的乘積，提高計算方法的效率與提高計算機(jī)硬件的效率同樣重要?？茖W(xué)計算科學(xué)計算已用到科學(xué)技術(shù)和社會生活的各個領(lǐng)域中，成為繼實驗實驗和理論研究理論研究之后的第三種研究方法。數(shù)值解法數(shù)值解法 = 算法算法 + 計算機(jī)計算機(jī)。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-174 算算法法設(shè)設(shè)計計 實實際際問問題題 數(shù)數(shù)學(xué)學(xué)模模型型 程程序序設(shè)設(shè)計計 上上機(jī)機(jī)求求解解 應(yīng)應(yīng)用用數(shù)數(shù)學(xué)學(xué)

4、 計計算算數(shù)數(shù)學(xué)學(xué) 二、研究對象和主要內(nèi)容二、研究對象和主要內(nèi)容 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-175n數(shù)值計算方法，是一種研究如何求解數(shù)學(xué)問題數(shù)值近數(shù)值近似解似解的方法，是在計算機(jī)計算機(jī)上使用的解數(shù)學(xué)問題的方法，簡稱計算方法。包括直接方法直接方法和迭代方法迭代方法!n數(shù)值計算方法的計算對象是線性代數(shù)，微積分，常微分方程中的數(shù)學(xué)問題。內(nèi)容包括：求解線性方程組的數(shù)值方法求解線性方程組的數(shù)值方法; ;計算矩陣特征值和特征向量的數(shù)值方法計算矩陣特征值和特征向量

5、的數(shù)值方法; ;非線性方程和非線性方程組的迭代解法非線性方程和非線性方程組的迭代解法; ;插值插值與與擬合擬合; ;數(shù)值微積分?jǐn)?shù)值微積分; ;常微分方程數(shù)值解等問題。常微分方程數(shù)值解等問題。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-176 特特 點點 面面 向向 計計 算算 機(jī)機(jī) 有有 可可 靠靠 的的 理理 論論 分分 析析 有有 較較 好好 的的 計計 算算 復(fù)復(fù) 雜雜 性性 有有 數(shù)數(shù) 值值 實實 驗驗 收收 斂斂 性性 穩(wěn)穩(wěn) 定定 性性 時時 間間 復(fù)復(fù)

6、雜雜 度度 空空 間間 復(fù)復(fù) 雜雜 度度 三、特點三、特點 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-177數(shù)值計算方法既有數(shù)學(xué)類課程中理論上的抽象性和嚴(yán)謹(jǐn)性，又有實用性和實驗性等技術(shù)特征，它是一門理論性理論性和實踐性實踐性都很強(qiáng)的課程。在20世紀(jì)70年代，大多數(shù)學(xué)校僅在數(shù)學(xué)系的計算數(shù)學(xué)專業(yè)計算數(shù)學(xué)專業(yè)和計算機(jī)系計算機(jī)系開設(shè)計算方法這門課程。隨著計算機(jī)技術(shù)的迅速發(fā)展和普及，現(xiàn)在計算方法課程幾乎已成為所有理工科大學(xué)生的一門必修課程理工科大學(xué)生的一門必修課程。n學(xué)習(xí)過程

7、中應(yīng)該注意以下幾個方面：認(rèn)清算法的計算對象；掌握基本的計算方法及其原理；用C+語言編制程序，在計算機(jī)上對算法進(jìn)行驗證；對于算法要勤思考多比較！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-178參考書目：參考書目：1 鐘爾杰.數(shù)值分析.高等教育出版社,2004.2 顏慶津.數(shù)值分析.修訂版.北京航空航天大學(xué)出版社,2000.3 李慶揚(yáng). 數(shù)值分析.清華大學(xué)出版社,2001.4 白峰杉.數(shù)值計算引論.高等教育出版社,2004.5 王能超.計算方法.北京: 高等教育出版社

8、, 2005. Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1791、算法設(shè)計技術(shù)2、誤差3、數(shù)值計算中需要注意的一些問題4、算法的穩(wěn)定性5、病態(tài)問題內(nèi)容內(nèi)容: :數(shù)值分析的基本概念 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1710 1.1 算法設(shè)計技術(shù)算法設(shè)計技術(shù) 古希臘哲學(xué)家Zeno(芝諾)在兩千多年前提出過一個駭人聽聞的命題：一個人

9、不管跑得多快，也追不上爬在他前面的一只烏龜。這就是著名的Zeno悖論。Zeno在論證這個命題時采取了如下形式的邏輯推理：設(shè)人與龜同時同向起跑，如果龜不動，那么人經(jīng)過某段時間便能追上它；但實際上在這段時間內(nèi)龜又爬了一段路程，從而人又得重新追趕，如下圖所示，這樣每追趕一次所歸結(jié)的是同樣類型的追趕問題，因而這種追趕過程“永遠(yuǎn)”不會終結(jié)。 引例引例 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1711耐人尋味的是，盡管Zeno悖論的論斷極其荒謬，但從算法設(shè)計思想的角度來看它卻

10、是極為精辟的。Zeno悖論將人龜追趕問題表達(dá)為一連串追趕步的逐步逼近過程。設(shè)人與龜?shù)乃俣确謩e為與，記表示逼近過程的第步人與龜?shù)拈g距，另以表示相應(yīng)的時間，相鄰兩步的時間差。Zeno悖論將人龜追趕問題分解為一追一趕兩個過程：1kkStVkkSv t 追的過程：追的過程：先令龜不動，計算人追上龜所費的時間趕的過程：趕的過程：再令人不動，計算龜在這段時間內(nèi)爬行的路程tkSk-1SkVvtk-1vV 圖示: 人龜追趕過程 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1712若以

11、人和龜之間的距離 定義問題的規(guī)模規(guī)模大小，則上述過程將問題規(guī)模壓縮了 倍：kSvV1kkvSSV由于龜?shù)乃俣冗h(yuǎn)遠(yuǎn)小于人的速度，故 很小，因此按上述步驟很快問題的規(guī)模 就可以忽略不計，從而得到人追上龜所花時間 ，Zeno的解釋可用如下過程表示：vVkSkt01,1,2,kkvSS SSkVZeno算法可見，Zeno算法的設(shè)計思想是，將人龜追趕計算化歸為簡單的行程計算的重復(fù)，它的設(shè)計方法是逐步壓縮計算模型的規(guī)模，這種“化大為小”的設(shè)計策略稱為規(guī)?？s減技術(shù)規(guī)?？s減技術(shù)，簡稱縮減技術(shù)縮減技術(shù)。 算法的設(shè)計精髓：“簡單簡單”的重復(fù)生成復(fù)雜！的重復(fù)生成復(fù)雜！ Numerical Analysis J. G

12、. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1713則計算結(jié)果即為所求的和值： （3）數(shù)列求和問題： （1）01nSaaa001,1,2,kkkbabbaknnSb1 直接法的縮減技術(shù)直接法的縮減技術(shù)若用bk表示前k項的部分和，則有 （2） Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1714這樣，如果定義和式的項數(shù)為數(shù)列求和問題的規(guī)模規(guī)模，則所求和值為（1）的退化情形。因之，只要令和式

13、的規(guī)模逐次減1，最終當(dāng)規(guī)模為1時即可直接得出所求的和值，而這樣設(shè)計出來的算法就是累加求和算法（2）?？梢姡鲜隼奂忧蠛退惴ǖ脑O(shè)計思想是將多項求和（1）化歸為兩項求和（2）的重復(fù)，最終加工成一項和式（3）（(1)的退化情形）,從而得出和值。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1715考慮10110( ) nnnnnn kkkP xa xa xaxaa x00va(1,2,)k 1kkkvx va 利用縮減技術(shù)可得如下算法：算法流程圖考慮問題1 Numerica

14、l Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-17162 迭代法的校正技術(shù)迭代法的校正技術(shù)易得人追上龜所花的時間是有些問題的“大事化小”過程似乎無法了結(jié)。Zeno悖論強(qiáng)調(diào)人“永遠(yuǎn)”趕不上龜正是為了突出這層含義。這是一類無限逼近的過程，適于用所謂預(yù)報校正技術(shù)預(yù)報校正技術(shù)來處理。 設(shè)人龜起初相距 ，兩者的速度分別為 和 ，SVv則有方程VtvtS（1）*StVv Numerical Analysis J. G. Liu School of Math. & Phys. North C

15、hina Elec. P.U.2022-3-1717注意到 v是個小量，設(shè)t也是個小量，則可從上式中略去vt ，即令校正量t滿足如下方程(近似近似)設(shè)解t*有某個預(yù)報值預(yù)報值t0，希望提供校正量t，使校正值校正值t1= = t0+ t 能更好的滿足所給方程（1），即使得00V ttv ttS00V ttvtS求解上述方程即可定出校正值 01SvttV Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1718進(jìn)一步視 t1為新的預(yù)報值，重復(fù)實施上述手續(xù)，求出新的校正值 t2

16、，再由 t2定 t3 ，如此反復(fù)可生成一系列近似值 t1,t2,t3,這就規(guī)定了一個迭代過程， 1,0,1,2,kkSvttkV(2)Zeno悖論所描述的逼近過程正是這種迭代過程，當(dāng)k時，tk t* （ 考慮問題2 ）。大家知道，任何形式的重復(fù)都可看成是“時間”的量度。Zeno在刻畫人龜追趕問題中設(shè)置了兩個“時鐘”：一個是日常的鐘，另外Zeno又將迭代次數(shù)視為另一種時鐘，不妨稱之為Zeno鐘鐘。Zeno公式（2）表明，當(dāng)Zeno鐘趨于時人才能追上龜，Zeno正是據(jù)此斷言人永遠(yuǎn)追不上龜。 Numerical Analysis J. G. Liu School of Math. & Phy

17、s. North China Elec. P.U.2022-3-1719給定 ，求開方值 的問題就是要求解方程 0a a20 xa設(shè)給定某個預(yù)報值 ，希望借助于某種簡單方法確定校正量 ，使校正值0 xx10 xxx能夠比較準(zhǔn)確地滿足方程（1），即使 成立，20 xxa設(shè)校正量 是個小量，舍去上式中的高階小量 ，令 ，從中定出 ，繼而可得校正值：x2x2002xxxa x（1）10012axxx利用校正技術(shù)，設(shè)計求解 （ ）的算法。0a a近似近似 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec.

18、 P.U.2022-3-172011,0,1,2,2kkkaxxkx反復(fù)實施這種預(yù)報校正手續(xù)，即可導(dǎo)出開方公式開方公式 ：從某個初值 出發(fā)，利用上式反復(fù)迭代，即可獲得滿足精度要求的開方值 。 00 x a校正技術(shù)的基本思想：刪繁就簡刪繁就簡，逐步求精逐步求精 ！考慮問題3 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1721其中 ，3 算法優(yōu)化的松弛技術(shù)算法優(yōu)化的松弛技術(shù)10VvSttVvVvVv對于給定的預(yù)報值 ，校正值為01SvttV0t據(jù)此有 ，兩端同除以 ，有

19、10VtvtSV v由于 為人龜追趕問題的精確解，*StVv10*(1)ttt再考察Zeno算法：可見，精確解等于任給預(yù)報值同它的校正值的加權(quán)平均加權(quán)平均：vVv Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1722即通過適當(dāng)選取權(quán)系數(shù) 來調(diào)整校正量 ，以加工得到更高精度的 ，這種基于校正量的調(diào)整與松動的方法通常稱為松弛技術(shù)松弛技術(shù)。 可以看到，這里任意一對迭代值經(jīng)過上述手續(xù)松弛即可得到問題的精確解。這種加工效果是奇妙的。在實際計算中常?？梢垣@得目標(biāo)值 F * 的兩個

20、相伴的近似值 F0 與 F1 ，將它們加工成更高精度的結(jié)果的方法之一就是取兩者的某種加權(quán)平均作為改進(jìn)值： 010101FFFFFF10FFF Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1723有一種情況特別引人注目：若所提供的一對近似值 與 有優(yōu)劣之分，譬如 優(yōu)而 劣，這時就采用如下松弛方式： 0F1F1F0F101,0FFF即在松弛過程中張揚(yáng) 的優(yōu)勢而抑制 的劣勢，這種設(shè)計策略稱作外推松弛技術(shù)，簡稱超松弛超松弛。 1F0F總之，超松弛的設(shè)計機(jī)理是優(yōu)劣互補(bǔ)，化粗為精

21、優(yōu)劣互補(bǔ)，化粗為精。松弛技術(shù)的關(guān)鍵在于松弛因子的選取松弛因子的選取，而這往往是相當(dāng)困難的。 返回 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1724 1.2 誤差誤差 1 誤差的分類誤差的分類 模模型型誤誤差差 觀觀測測誤誤差差 截截斷斷誤誤差差 舍舍入入誤誤差差 數(shù)數(shù)值值分分析析進(jìn)進(jìn)行行誤誤差差分分析析的的對對象象 按按來來源源分分類類 Numerical Analysis J. G. Liu School of Math. & Phys. North C

22、hina Elec. P.U.2022-3-17252 誤差和有效數(shù)字(1) (1) 誤差誤差 定義定義 設(shè) 是準(zhǔn)確值， 是 的一個近似值，記 ，稱 為近似值 的絕對誤差絕對誤差，簡稱誤差。 axaxeeax若已知 的一個上界為 ，即 ，則稱 為近似值 的絕對誤差界絕對誤差界，簡稱誤差界（越小表示近似程度越高）。 eea注注: : 用絕對誤差來刻畫近似數(shù)的精確程度不能反映它在原數(shù)中所占的比例。 例例 , ，可是 與真值 相差一個數(shù)量級。 001. 0,0002. 0ax001. 0axeax Numerical Analysis J. G. Liu School of Math. &

23、Phys. North China Elec. P.U.2022-3-1726稱 為近似值 的相對誤差相對誤差, xaxxeer記reaaaxaeer 的一個上界 ,稱為近似值 的相對誤界相對誤界 reara上例中 ，易見近似程度并不高！8 . 0001. 0001. 00002. 0aaxer也可以記為 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1727(2) (2) 誤差估計誤差估計 n 函數(shù)計算的誤差估計 121,nnkkknzf x xxxzfabbaa對

24、元函數(shù)，設(shè)準(zhǔn)確值為 和 的近似值分別為 、 ，則 ,( ) |( )| ( )yf xxyabbfaa對一元函數(shù)設(shè)準(zhǔn)確值 和 的近似值分別為 、 ，則 n 算數(shù)運算的誤差估計121212211222121221aaaaaaaaaaaa aaaaa Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1728解解 絕對誤差限是0.01的半個單位，且 ， 有三位有效數(shù)字，分別是1，3，8； 有一位有效數(shù)字，為3； 沒有有效數(shù)字。 (3) 有效數(shù)字有效數(shù)字定義定義 設(shè) 是數(shù) 的近似

25、值，如果 的絕對誤差限是它的某一位的半個單位某一位的半個單位，且從該位到 的第一位非零數(shù)字非零數(shù)字共有 位，則稱 作為 的近似有 位有效數(shù)字。 axaanaxn例例 設(shè)近似值 ，其絕對誤差限都是0.005，求各個近似值各有幾位有效數(shù)字？41086. 03,0312. 02,38. 11aaa2a000086. 03 a1a3a同一真值的不同近似值，有效數(shù)字越多有效數(shù)字越多，它的絕對誤差和相對誤差都越小。 用單精度浮點型變量進(jìn)行計算的結(jié)果有七位有效數(shù)字，雙精度浮點型變量有16位有效數(shù)字注注： Numerical Analysis J. G. Liu School of Math. & P

26、hys. North China Elec. P.U.2022-3-17293 浮點數(shù)浮點數(shù)（1）浮點數(shù)）浮點數(shù)“數(shù)”在計算機(jī)中是以二進(jìn)制表示的，一個非零二進(jìn)制數(shù)的一般描述形式為：12.2std dd其中di（i=1,2,t）為0或1，稱為尾數(shù)尾數(shù)，且d10；2為基數(shù)基數(shù)，s稱為階碼階碼且滿足L s U，這說明計算機(jī)只能表示有限個數(shù)且是有限精度有限個數(shù)且是有限精度，這個實數(shù)的子集稱為浮點數(shù)，記作F。不難驗證對于F中任意不為零的數(shù) f，有,mfM其中m=2L-1，M=2U(1-2-t)，因此計算機(jī)上的計算會有溢出現(xiàn)象：上溢和下溢！浮點數(shù)在接近其下界m處比較稠密，而在接近其上界M處比較稀疏！因此，

27、在計算中通常都是使用相對誤差相對誤差來控制精度！由于計算機(jī)的有限精度而造成的誤差稱為舍入誤差舍入誤差！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1730（2） 截斷誤差和舍入誤差截斷誤差和舍入誤差考慮計算一元可微函數(shù)f(x)在x0處導(dǎo)數(shù)的近似方法：000000()()(),(1)()()(),(2)2f xhf xfxhf xhf xhfxh因此近似方法（1）的誤差為20000()()()()()(4)2f xhf xfxfxhO hh考慮方法（1）：由泰勒展開，

28、可得230000()()()()()(3)2fxf xhf xfxhhO h從而有201()()(5)2fxThO h截斷誤差考慮問題4 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1731通過實驗發(fā)現(xiàn)，隨著h減小，通過（1）計算的導(dǎo)數(shù)近似值與真值的誤差是先減小后增大先減小后增大，這種現(xiàn)象是什么原因造成的呢？其原因就在于計算機(jī)是有限精度的，隨著h的減小，舍入誤差逐漸被放大，并且最終成為引起誤差的主導(dǎo)因素?。ㄒ笊蠙C(jī)體會舍入誤差的影響）要學(xué)好數(shù)值分析課程一定要真正理解舍

29、入誤差，特別是舍入誤差在算法中的傳播傳播和對最終結(jié)果的影響！同理可以討論近似方法（2）的截斷誤差，以及隨著h的減小，其誤差的變化情況！返回那么是不是那么是不是h越小，計算誤差就越小呢？越小，計算誤差就越小呢？考慮問題5 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1732 1.3 數(shù)值計算中需要注意的問題數(shù)值計算中需要注意的問題1 浮點數(shù)的加法浮點數(shù)的加法112.;stdd dd 21 2.stcc cc 設(shè)兩個浮點數(shù)相加：兩個浮點數(shù)相加：首先比較它們的階碼，若階碼相

30、同則尾數(shù)相加，相加后若尾數(shù)大于1則階碼進(jìn)位；若階碼不等，則以相對大的階碼為標(biāo)準(zhǔn)，將階碼小的浮點數(shù)進(jìn)行移位，直到階碼一致，再按階碼相同時的規(guī)則進(jìn)行相加！例1 假設(shè)計算機(jī)只能存放三位十進(jìn)制數(shù)字，設(shè) 在該計算機(jī)上進(jìn)行如下運算 001. 0,00. 1,01. 1321xxx（1）計算 與十個 之和，即 ，采用以下兩種計算方法 1x3x331xxx Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-17331） ， ，則 即為所求， 10 xa )10, 1(31ixaaii10a

31、計算得 （錯）01. 110a 2） （正確） 02. 101. 001. 1)(331xxx（2） （錯） 32311001. 100. 1001. 001. 1 xxx（3） （錯） 02. 000. 102. 12221 xx （正確） 2212122211001. 201. 201. 0)(xxxxxx Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1734例2 計算 127x -只需要做12次乘法 643216842127xxxxxxxx2 2 數(shù)值計算的一些基本原則數(shù)值計算的一些基本原則（1）由