數(shù)值分析華電PPT

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

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

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

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

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

6、性 穩(wěn)穩(wěn) 定定 性性 時時 間間 復復 雜雜 度度 空空 間間 復復 雜雜 度度 數(shù)值分析數(shù)值分析(計算方法計算方法)課程介紹課程介紹特點特點 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-87n學好本門課程需要做到：認清算法的計算對象；掌握基本的計算方法及其原理；編制程序，在計算機上對算法進行驗證；對于算法要多思考多比較！ 數(shù)值分析數(shù)值分析(計算方法計算方法)課程介紹課程介紹數(shù)值計算方法既有數(shù)學類課程中理論上的抽象性和嚴謹性，又有實用性和實驗性等技術特征，它是一門理論

7、性理論性和實踐性實踐性都很強的課程。在20世紀70年代，大多數(shù)學校僅在數(shù)學系的計算數(shù)學專業(yè)計算數(shù)學專業(yè)和計算機系計算機系開設計算方法這門課程。隨著計算機技術的迅速發(fā)展和普及，現(xiàn)在計算方法課程幾乎已成為所有理工科大學生的一門必修課程理工科大學生的一門必修課程。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-88參考書目：參考書目：1 谷根代等，數(shù)值分析與應用，科學出版社，20112 鐘爾杰.數(shù)值分析.高等教育出版社,2004.3 顏慶津.數(shù)值分析.修訂版.北京航空航天大學

8、出版社,2000.4 李慶揚. 數(shù)值分析.清華大學出版社,2001.5 白峰杉.數(shù)值計算引論.高等教育出版社,2004.6 王能超.計算方法.北京: 高等教育出版社, 2005. Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-89第一章 緒論1、算法設計技術2、誤差3、數(shù)值計算中需要注意的一些問題4、算法的穩(wěn)定性5、病態(tài)問題內容內容: : Numerical Analysis J. G. Liu School of Math. & Phys. North Chi

9、na Elec. P.U.2022-5-810 1.1 算法設計技術算法設計技術 古希臘哲學家Zeno(芝諾)在兩千多年前提出過一個駭人聽聞的命題：一個人不管跑得多快，也追不上爬在他前面的一只烏龜。這就是著名的Zeno悖論。Zeno在論證這個命題時采取了如下形式的邏輯推理：設人與龜同時同向起跑，如果龜不動，那么人經(jīng)過某段時間便能追上它；但實際上在這段時間內龜又爬了一段路程，從而人又得重新追趕，如下圖所示，這樣每追趕一次所歸結的是同樣類型的追趕問題，因而這種追趕過程“永遠”不會終結。 引例引例 Numerical Analysis J. G. Liu School of Math. &

10、Phys. North China Elec. P.U.2022-5-811耐人尋味的是，盡管Zeno悖論的論斷極其荒謬，但從算法設計思想的角度來看它卻是極為精辟的。Zeno悖論將人龜追趕問題表達為一連串追趕步的逐步逼近過程。設人與龜?shù)乃俣确謩e為V與v，記Sk表示逼近過程的第k步人與龜?shù)拈g距，另以tk表示相應的時間，相鄰兩步的時間差tk 。Zeno悖論將人龜追趕問題分解為一追一趕兩個過程：1kkStVkkSv t 追的過程：追的過程：先令龜不動，計算人追上龜所費的時間趕的過程：趕的過程：再令人不動，計算龜在這段時間內爬行的路程tkSk-1SkVvtk-1vV 圖示: 人龜追趕過程 Numeri

11、cal Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-812若以人和龜之間的距離 定義問題的規(guī)模規(guī)模大小，則上述過程將問題規(guī)模壓縮了 倍：kSvV1kkvSSV由于龜?shù)乃俣冗h遠小于人的速度，故 很小，因此按上述步驟很快問題的規(guī)模 就可以忽略不計，從而得到人追上龜所花時間 ，Zeno的解釋可用如下過程表示：vVkSkt01,1,2,kkvSS SSkVZeno算法可見，Zeno算法的設計思想是: “化大為小,化繁為簡”，即將人龜追趕計算化為簡單的行程計算的重復。算法的設計精髓：“簡單簡單”的

12、重復生成復雜！的重復生成復雜！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-813則計算結果即為所求的和值： （3）數(shù)列求和問題： （1）01nSaaa001,1,2,kkkbabbaknnSb1 直接法的縮減技術直接法的縮減技術若用bk表示前k項的部分和，則有 （2） Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-814這樣，如果定義和式的項

13、數(shù)為數(shù)列求和問題的規(guī)模規(guī)模，則所求和值為（1）的退化情形。因之，只要令和式的規(guī)模逐次減1，最終當規(guī)模為1時即可直接得出所求的和值，而這樣設計出來的算法就是累加求和算法（2）?？梢?，上述累加求和算法的設計思想是將多項求和（1）化歸為兩項求和（2）的重復，最終加工成一項和式（3）（(1)的退化情形）,從而得出和值。 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-815考慮10110( ) nnnnnn kkkP xa xa xaxaa x00va(1,2,)k 1kkkvx

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

15、l of Math. & Phys. North China Elec. P.U.2022-5-817注意到 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-5-818進一步視

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

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

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

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

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

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

22、 North China Elec. P.U.2022-5-8252 誤差和有效數(shù)字(1) (1) 誤差誤差 定義定義 設 是準確值， 是 的一個近似值，記 ，稱 為近似值 的絕對誤差絕對誤差，簡稱誤差。 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-5-826稱 為近似值 的相對誤差相對誤差, xaxxeer記reaaaxaeer 的一個上界 ,稱為近似值 的相對誤界相對誤界 reara上例中 ，易見近似程度并不高！8 . 0001. 0001. 00002. 0aaxer也可以記為 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-827(2) (2) 誤差估計誤差估計 n 函數(shù)計算的誤差估計 121,nnkkknzf x xxxzfab

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

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

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

27、下界m處比較稠密，而在接近其上界M處比較稀疏！因此，在計算中通常都是使用相對誤差相對誤差來控制精度！由于計算機的有限精度而造成的誤差稱為舍入誤差舍入誤差！ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-830則稱近似數(shù)a具有n位有效數(shù)字位有效數(shù)字。若a的絕對誤差滿足： 120.10mntad ddd 1102m nxa設x的近似值a可表示為規(guī)格化浮點數(shù)形式 121,090td ddd 其中都是中的整數(shù)，且，定理定理 設 ，120.10mnad dd 1510nread反

28、之若近似數(shù)a的相對誤差滿足 15101nread則a至少有n位有效數(shù)字。若a是有n位有效數(shù)字的近似數(shù)，則它的相對誤差滿足 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-831例例1 要使的 近似值a的相對誤差限不超過相對誤差限不超過0.1，a應取幾位有效數(shù)字？ 30例例2 已知 的近似數(shù)a相對誤差限為相對誤差限為0.5，試問a至少有幾位有效數(shù)字?20參考答案：3參考答案：2 3115: 1010 ,30,5 3nreaddn解 由及對于 115: 0.00510 ,20

29、,4,1 2nreaddn解 由及對于 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-832（2） 截斷誤差和舍入誤差截斷誤差和舍入誤差考慮計算一元可微函數(shù)f(x)在x0處導數(shù)的近似方法：000000()()(),(1)()()(),(2)2f xhf xfxhf xhf xhfxh因此近似方法（1）的誤差為20000()()()()()(4)2f xhf xfxfxhO hh考慮方法（1）：由泰勒展開，可得230000()()()()()(3)2fxf xhf xfx

30、hhO h從而有201()()(5)2fxThO h截斷誤差 Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-833通過實驗發(fā)現(xiàn)，隨著h減小，通過（1）計算的導數(shù)近似值與真值的誤差是先減小后增大先減小后增大，這種現(xiàn)象是什么原因造成的呢？（演示）其原因就在于計算機是有限精度的，隨著h的減小，舍入誤差逐漸被放大，并且最終成為引起誤差的主導因素！（要求上機體會舍入誤差的影響）要學好數(shù)值分析課程一定要真正理解舍入誤差，特別是舍入誤差在算法中的傳播傳播和對最終結果的影響！同理可以討

31、論近似方法（2）的截斷誤差，以及隨著h的減小，其誤差的變化情況！返回那么是不是那么是不是h越小，計算誤差就越小呢？越小，計算誤差就越小呢？ Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-83402468101214161820-3-2.5-2-1.5-1-0.500.5 向 前中 心300( ),1,()30.1,0.01,f xxxfxh算例： Numerical Analysis J. G. Liu School of Math. & Phys. North

32、 China Elec. P.U.2022-5-835 1.3 數(shù)值計算中需要注意的問題數(shù)值計算中需要注意的問題1 浮點數(shù)的加法浮點數(shù)的加法112.;stdd dd 21 2.stcc cc 設兩個浮點數(shù)相加：兩個浮點數(shù)相加：首先比較它們的階碼，若階碼相同則尾數(shù)相加，相加后若尾數(shù)大于1則階碼進位；若階碼不等，則以相對大的階碼為標準，將階碼小的浮點數(shù)進行移位，直到階碼一致，再按階碼相同時的規(guī)則進行相加！例1 假設計算機只能存放三位十進制數(shù)字，設 在該計算機上進行如下運算 001. 0,00. 1,01. 1321xxx（1）計算 與十個 之和，即 ，采用以下兩種計算方法 1x3x331xxx Numerical Analysis J. G. Liu School of Math. & Phys. North China Elec. P.U.2022-5-8361） ， ，則 即為所求， 10 xa )10, 1(31ixaaii10a計算得 （錯）01. 110a 2） （正確） 02. 101. 001. 1)(331xxx（2） （錯） 32311001. 100. 1001. 001. 1 xxx（3） （錯） 02. 000. 102. 12221 xx （正確） 2212122211001. 201. 201