1、 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-171數數 值值 分分 析析插值、擬合與數值微積分插值、擬合與數值微積分主講：劉敬剛劉敬剛 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-172 數值分析數值分析(計算方法計算方法) 介紹介紹考慮如下線性方程組 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）需做乘除法的次數: 當方程組階數較高時，計算量很大，因此克萊姆法則通常僅有理論上的價值，計算線性方程組的解還要考慮: 首先看一個簡單的例子：1212120 xxxx 121

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

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

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

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

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

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

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

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

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

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

13、的規模逐次減1，最終當規模為1時即可直接得出所求的和值，而這樣設計出來的算法就是累加求和算法（2）。可見，上述累加求和算法的設計思想是將多項求和（1）化歸為兩項求和（2）的重復，最終加工成一項和式（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 利用縮減技術可得如下算法：算法流程圖考慮問題1 Numerica

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

15、hina Elec. P.U.2022-3-1717注意到 v是個小量，設t也是個小量，則可從上式中略去vt ，即令校正量t滿足如下方程(近似近似)設解t*有某個預報值預報值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進一步視 t1為新的預報值，重復實施上述手續，求出新的校正值 t2

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

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

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

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

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

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

22、hina Elec. P.U.2022-3-17252 誤差和有效數字(1) (1) 誤差誤差 定義定義 設 是準確值， 是 的一個近似值，記 ，稱 為近似值 的絕對誤差絕對誤差，簡稱誤差。 axaxeeax若已知 的一個上界為 ，即 ，則稱 為近似值 的絕對誤差界絕對誤差界，簡稱誤差界（越小表示近似程度越高）。 eea注注: : 用絕對誤差來刻畫近似數的精確程度不能反映它在原數中所占的比例。 例例 , ，可是 與真值 相差一個數量級。 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 函數計算的誤差估計 121,nnkkknzf x xxxzfabbaa對

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

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

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

27、在計算中通常都是使用相對誤差相對誤差來控制精度！由于計算機的有限精度而造成的誤差稱為舍入誤差舍入誤差！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-3-1730（2） 截斷誤差和舍入誤差截斷誤差和舍入誤差考慮計算一元可微函數f(x)在x0處導數的近似方法：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通過實驗發現，隨著h減小，通過（1）計算的導數近似值與真值的誤差是先減小后增大先減小后增大，這種現象是什么原因造成的呢？其原因就在于計算機是有限精度的，隨著h的減小，舍入誤差逐漸被放大，并且最終成為引起誤差的主導因素！（要求上機體會舍入誤差的影響）要學好數值分析課程一定要真正理解舍

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

30、同則尾數相加，相加后若尾數大于1則階碼進位；若階碼不等，則以相對大的階碼為標準，將階碼小的浮點數進行移位，直到階碼一致，再按階碼相同時的規則進行相加！例1 假設計算機只能存放三位十進制數字，設 在該計算機上進行如下運算 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 數值計算的一些基本原則數值計算的一些基本原則（1）由