計算方法第一講

1、數(shù)值分析數(shù)值分析趙麗娜趙麗娜v鄧建中，劉之行，西安交通大學出版社，計算方法，鄧建中，劉之行，西安交通大學出版社，計算方法，2001年年v李慶揚，關冶李慶揚，關冶 數(shù)值分析原理，清華大學出版社，數(shù)值分析原理，清華大學出版社，2000年年v李慶揚，易大義，王能超李慶揚，易大義，王能超 現(xiàn)代數(shù)值分析，高教出版現(xiàn)代數(shù)值分析，高教出版社，社，1995年年vMichael T. H. Scientific Computing: An introductory Survey, 清華大學出版社，清華大學出版社，2001vMatlews J. H. Numerical Methods Using Matlab,

2、 電子工業(yè)電子工業(yè)出版社，出版社，2002教材與參考書 數(shù)值分析或計算方法的歷史早于計算機的產(chǎn)生，數(shù)值分析或計算方法的歷史早于計算機的產(chǎn)生，許多（如今仍在使用的）概念與方法由二十許多（如今仍在使用的）概念與方法由二十世紀前的偉人給出世紀前的偉人給出 Newton (1642-1727) Euler(1707-1783) Lagrange(1736-1813) Laplace(1749-1817) Legendre(1752-1833) Hermite(1822-1901) Gauss(1777-1855) Cauchy(1789-1857) Jacobi(1804-1851) Adams(18

3、19-1892) Chebyshev(1821-1894) Laguerre(1834-1886)第一講數(shù)值分析的意義內(nèi)容與方法n 起源：尋找有效的方法獲得數(shù)學問題的近似解。n 數(shù)學問題源于物理，天文，勘測等n 在僅使用紙，筆，大腦，而不是計算機進行計算時，算法效率尤為重要。n 如今，大規(guī)模計算成為可能，更要仔細分析控制截斷誤差1.1 數(shù)值分析的起源與意義v隨著計算機的普及與發(fā)展，計算機性能的大幅提高，海量數(shù)據(jù)的出現(xiàn)，科學計算更為重要v科學計算已成為現(xiàn)代科學技術的研究方法的第三大方法 理論推導，科學試驗，科學計算v其他應用：符號計算、計算幾何、定理的機器證明科學計算的定義v將科學技術問題科學技

4、術問題通過建立數(shù)學模型轉(zhuǎn)換為數(shù)數(shù)學問題學問題；v將數(shù)學問題離散化得到數(shù)值問題數(shù)值問題；v使用數(shù)值計算方法數(shù)值計算方法求出數(shù)值問題的解數(shù)值問題的解；v并把所得的解作為原科技問題的解原科技問題的解。實際問題數(shù)學問題可計算問題數(shù)學建模構(gòu)造算法計算求解計算結(jié)果反饋、修正、應用解決實際問題計算數(shù)學是科學計算的核心v計算數(shù)學-對數(shù)學模型問題研究數(shù)值求解方法，分析方法的性質(zhì) 數(shù)學問題通過數(shù)值計算方法化為可計算問題，然后進行計算求得結(jié)果v按研究內(nèi)容可分為：數(shù)值代數(shù)、數(shù)值逼近、數(shù)值微積分、微分方程數(shù)值解、最優(yōu)化計算、概率統(tǒng)計計算、計算幾何、計算力學等。是否有了計算機，找到數(shù)學公式就可以得到正確的結(jié)果？例例1：1

5、23123123111123611113234121114734560 xxxxxxxxx解為：解為：x1 = x2 = x3 =1如近似為：如近似為：則解為：則解為：1231231230.500.331.80.500.330.251.10.330.250.200.78xxxxxxxxx1236.222,38.25,33.65xxx 1.2 數(shù)值問題與算法v數(shù)值問題是指輸入數(shù)據(jù)（原始數(shù)據(jù)，問題中的已知量）與輸出數(shù)據(jù)（結(jié)果）之間的函數(shù)關系的明確的無歧異的問題v數(shù)學問題未必是數(shù)值問題，但它往往可以用數(shù)值問題來逼近例例2：求常微分方程：求常微分方程22(0)0dyxydxy由題目要求，需給出y=y(

6、x)解析式，該問題不是數(shù)值問題；若輸出y=y(x)在（給定步長h）x=h, x=2h, x=nh處的近似值，則該問題轉(zhuǎn)化為數(shù)值問題。算法及其好壞v計算機的基本運算：四則運算、簡單邏輯運算v計算機的算法可分為串行算法和并行算法v好的算法： 1、面向計算機，易于編程和計算實現(xiàn)； 2、計算復雜性好：計算時間少、占用內(nèi)存少； 3、計算穩(wěn)定性好：能有效控制由于方法近似和舍入 誤差引起的誤差增長，結(jié)果能達到所要求的精度； 4、適用性好。例例3：計算多項式：計算多項式x = a時時p(a)的值。的值。1011( )nnnnp xa xa xaxa 普通方法 時間：n(n+1)/2次乘法；n次加法 秦九韶算法

7、001,1,2,( )kkknbabaabknp ab時間：n次乘法；n次加法例：計算多項式：例：計算多項式：需需10次乘法次乘法4次加法。次加法。4次乘法次乘法4次加法。這是多項式計算的次加法。這是多項式計算的秦九韶秦九韶算算法法。3次乘法次乘法5次加法。次加法。4320.06250.4251.2151.9122.1296xxxx(0.06250.425)1.215)1.912)2.1296xxxx22(0.50.6)0.50.7 (0.50.6)0.80.9xxx例例4 解代數(shù)方程解代數(shù)方程 ：11 11221121 1222221 122nnnnnnnnnna xa xa xba xa

8、xa xba xa xa xb/,1,2,kkxDDkn直接法：用直接法：用Cramer法則解，法則解， 若若det(A)不為0，1.3 數(shù)值計算的基本方法論v有限近似無限：有限維空間代替無限維空間；有限和代替積分或無限級數(shù)；差商近似導數(shù)；v代數(shù)方程組近似微分方程組；v高階方程低階化v非線性問題線性化v復雜函數(shù)用簡單函數(shù)來代替（多項式泰勒展開）v一般矩陣簡單化原則：復雜問題Q1 簡單問題Q2Q2與Q1的解在一定意義下相同。直接方法（適用于可有限步內(nèi)直接計算得到解的問題）截斷近似：利用一些展開式截取其若干項來近似迭代法線性化：非線性問題局部線性化化整為零：將整體問題分割為若干小部分處理外推法：利

9、用已算出的結(jié)果適當組合得到更精確 的結(jié)果35721sin3!5!7!(21)!nnxxxxxxRn例例5：計算：計算sinx，x 0， /423 0 x 例例6：求解函數(shù)方程：求解函數(shù)方程f (x)=0.例例7：求解函數(shù)方程：求解函數(shù)方程例例9：求解常微分方程：求解常微分方程0( , ) , , ( )yf x yxa by ay 1(,)nnnnyyhf xy例例8：計算定積分：計算定積分( )bafx dx一個具體的例子：一個具體的例子：迭代格式為：迭代格式為：2,0,1(0)1xyyxyy 1(2/)nnnnnyyh yxy精確解：精確解：( )12y xxxn0.10.20.30.40

10、.51yn1.11.19181.27741.35811.43511.7848yn1.09591.18111.26621.34341.41641.7379Y(xn)1.09541.18321.26491.34161.41421.7320例：求方程例：求方程 根，如根，如z10系數(shù)系數(shù) 210略有誤差，為略有誤差，為 210.000000119，則根則根20變?yōu)樽優(yōu)?0.847，19和和18變?yōu)樽優(yōu)?9.502 1.94i .例：求解微分方程例：求解微分方程(1)(2)(20)0zzz0, (0)(0)1,0(0)1,(0)1,(1),22xxxyyyyyexyyyyeexy 解為：，則解為：v某

11、些問題的計算中，由于數(shù)據(jù)的微小變化引某些問題的計算中，由于數(shù)據(jù)的微小變化引起解的劇烈變化，稱這類問題為起解的劇烈變化，稱這類問題為病態(tài)問題病態(tài)問題和和壞條件問題壞條件問題。對于這類問題的計算，一定要。對于這類問題的計算，一定要采用采用高精度計算高精度計算。但對于非病態(tài)的良態(tài)問題，如算法不當，由于但對于非病態(tài)的良態(tài)問題，如算法不當，由于計算機的近似性，有時也可能得到不可靠的計算機的近似性，有時也可能得到不可靠的結(jié)果。結(jié)果。例：如在尾數(shù)為例：如在尾數(shù)為4位的計算機上計算位的計算機上計算其真正值為其真正值為0.05572809，但計算結(jié)果為：，但計算結(jié)果為： 0.0560，但，但如果先進行有理化在計

12、算，結(jié)果為：如果先進行有理化在計算，結(jié)果為：0.05574，顯然，顯然，后一種計算精度高。后一種計算精度高。例：如在尾數(shù)為例：如在尾數(shù)為4位的計算機上計算位的計算機上計算精確值為精確值為34.5612，計算時如先加前兩項，再加后一，計算時如先加前兩項，再加后一項，結(jié)果為項，結(jié)果為34.57，如先加后兩項，再加前一項，結(jié)，如先加后兩項，再加前一項，結(jié)果為果為34.56，顯然，后一種算法更好。，顯然，后一種算法更好。98021010 (0.3197) 10 (0.2456) 10 (0.1352)例：如在尾數(shù)為例：如在尾數(shù)為4位的計算機上計算位的計算機上計算按兩種不同遞推計算，結(jié)果為：按兩種不同遞

13、推計算，結(jié)果為：11011,0,1,2,71(1)/nxnnnnnIex e dx nInIIIn 第一種算法第一種算法第二種算法第二種算法真正值真正值I00.63210.63200.6321I10.36800.36790.3679I60.04000.12690.1268I70.72000.11240.1124由此可見，舍入誤差對計算有影響，影響小的算法稱由此可見，舍入誤差對計算有影響，影響小的算法稱為為數(shù)值穩(wěn)定數(shù)值穩(wěn)定的算法。的算法。有些算法具有遞推性，稱之為有些算法具有遞推性，稱之為迭代法或逐次逼近法迭代法或逐次逼近法。再計算一些復雜的函數(shù)的值，有時我們用一些簡單的再計算一些復雜的函數(shù)的值

14、，有時我們用一些簡單的函數(shù)（如多項式、有理函數(shù)等）來近似之，這稱為函數(shù)（如多項式、有理函數(shù)等）來近似之，這稱為函數(shù)逼近函數(shù)逼近。有時要求逼近函數(shù)與被逼近函數(shù)之間在。有時要求逼近函數(shù)與被逼近函數(shù)之間在某些點函數(shù)值及若干階導數(shù)值相等，這種逼近稱為某些點函數(shù)值及若干階導數(shù)值相等，這種逼近稱為插值插值；有時要求在逼近區(qū)間上的最大誤差取極小，；有時要求在逼近區(qū)間上的最大誤差取極小，這稱為這稱為最佳一致逼近最佳一致逼近；或在某些點的誤差值平方和；或在某些點的誤差值平方和取極小，這稱為取極小，這稱為最佳平方逼近最佳平方逼近。2 誤差及有關概念誤差及有關概念2.1誤差的來源誤差的來源真實值與我們所獲得的值之間

15、的差異就是真實值與我們所獲得的值之間的差異就是誤差誤差。對實際問題的研究需要建立數(shù)學模型，這帶來對實際問題的研究需要建立數(shù)學模型，這帶來模型模型誤差誤差。求解數(shù)學問題時需要若干參量和初始值，這些數(shù)據(jù)求解數(shù)學問題時需要若干參量和初始值，這些數(shù)據(jù)往往通過對實際問題的觀測得到，由于觀測引起往往通過對實際問題的觀測得到，由于觀測引起的誤差稱為的誤差稱為觀測誤差觀測誤差（數(shù)據(jù)誤差、模型參量誤數(shù)據(jù)誤差、模型參量誤差差）。求解數(shù)學問題時，由于算法而引起的誤差）。求解數(shù)學問題時，由于算法而引起的誤差稱為稱為方法誤差方法誤差（截斷誤差截斷誤差）。計算機計算時只能）。計算機計算時只能對有限位數(shù)進行計算，超過的進行

16、舍入，由此引對有限位數(shù)進行計算，超過的進行舍入，由此引起的誤差稱為起的誤差稱為舍入誤差舍入誤差（計算誤差計算誤差）。）。實際問題數(shù)學問題可計算問題數(shù)學建模構(gòu)造算法計算求解計算結(jié)果（模型誤差）（方法誤差）（舍入誤差、輸入數(shù)據(jù)誤差）2.2 絕對誤差與相對誤差絕對誤差與相對誤差設設x為真正值，為真正值， 為近似值，稱：為近似值，稱： 為近似值的為近似值的絕對誤差絕對誤差（簡稱（簡稱誤差誤差）通常我們要求絕對誤差不能超過某個值通常我們要求絕對誤差不能超過某個值 ， 稱稱為為絕對誤差限絕對誤差限或或誤差限誤差限。x ( )( )xE xxx ( ),xxxxxx設設x為真正值，為真正值， 為近似值，稱：

17、為近似值，稱：為為 的相對誤差。的相對誤差。如果存在如果存在 r，使得使得，稱之為，稱之為 相對誤差限。相對誤差限。在實際計算中，相對誤差限很小時，也?。涸趯嶋H計算中，相對誤差限很小時，也取：x ( )( )/()/xxxxxx x ( )( )/()/rxxxxxx x ( )( )/()/xxxxxx 2.3有效位數(shù)與有效數(shù)字有效位數(shù)與有效數(shù)字如果如果 的誤差限為的誤差限為0.510-n，即即則稱其準確到小數(shù)后第則稱其準確到小數(shù)后第n位，并稱位，并稱 的第一的第一個非零數(shù)字到第個非零數(shù)字到第n位的全部數(shù)字為位的全部數(shù)字為 的有的有效數(shù)字。效數(shù)字。x x x 1102nxx例如，若 x= =

18、3.1415926535，1416. 3x則x準確到小數(shù)后4位，具有5位有效數(shù)字。 顯然，近似值的絕對誤差越小，其準確到小數(shù)后的位數(shù)越多。 注意，若 x= 0.200001，,2000. 0, 2 . 021xx則1x作為 x 的近似只有1位有效數(shù)字，而2x作為 x 的近似具有4位有效數(shù)字。具有 k 位有效數(shù)字，則易知)0(10. 0121aaaaxmk)1(121102110. 01021| )(|kmknaaaax若這說明近似值的相對誤差越小，其有效數(shù)字越多。2.4 數(shù)據(jù)誤差的影響數(shù)據(jù)誤差的影響2.4 數(shù)據(jù)誤差的影響數(shù)據(jù)誤差的影響對兩個數(shù)對兩個數(shù)x1和和x2，簡單計算可得：簡單計算可得：1

19、2121212121212()()()()()()xxxxxxxxxxxxxx 1221121212()()()()()()x xxxxxx xxx112122221212(/)()/()(/)()()xxxxxxxxxxx 11()( ),()( )22xxxxx可見，當可見，當x1和和x2同號時，同號時，反之，當反之，當x1和和x2異號時，尤其異號時，尤其12211212()()()()()()xxxxxxxx 1212210,()()( )xxxxxx這表明，大小接近的異號數(shù)相加或大小這表明，大小接近的異號數(shù)相加或大小接近的同號數(shù)相減，會嚴重損失有效接近的同號數(shù)相減，會嚴重損失有效數(shù)字！

20、數(shù)字！乘數(shù)絕對值很大，或除數(shù)接近零時，可乘數(shù)絕對值很大，或除數(shù)接近零時，可能會嚴重擴大絕對誤差，減少精度！能會嚴重擴大絕對誤差，減少精度！開方會減少相對誤差，提高精度。開方會減少相對誤差，提高精度。一般地，設數(shù)學問題的解為一般地，設數(shù)學問題的解為 ,近似解為：近似解為：則絕對誤差為：則絕對誤差為：相對誤差為：相對誤差為：12( ,)nyx xx12( ,)nyx xx 1212121( )( ,)( ,)( ,)( )nnnniiiyyyx xxx xxx xxxx niiinnixxxxxxxxxyyy12121)(),(),()()( 和和 起對誤差的放大和縮小作用，其絕對值分別稱起對誤差

21、的放大和縮小作用，其絕對值分別稱為所求解的數(shù)學問題的絕對誤差下的條件數(shù)為所求解的數(shù)學問題的絕對誤差下的條件數(shù)和相對誤差下的條件數(shù)。條件數(shù)很大時稱該和相對誤差下的條件數(shù)。條件數(shù)很大時稱該問題為問題為病態(tài)問題病態(tài)問題或或壞條件問題壞條件問題，它是問題固，它是問題固有的屬性，與算法無關。但由于這類問題數(shù)有的屬性，與算法無關。但由于這類問題數(shù)據(jù)的微小變化會引起解的劇烈變化，對于這據(jù)的微小變化會引起解的劇烈變化，對于這類問題的計算，一般要采用類問題的計算，一般要采用高精度計算高精度計算，或，或改變問題的提法，降低條件數(shù)。改變問題的提法，降低條件數(shù)。12(,)nix xxxinnixxxxxxxx),()

22、,(21212.5舍入誤差的影響舍入誤差的影響在計算機中，用浮點法表示的數(shù)（稱為浮點數(shù)）在計算機中，用浮點法表示的數(shù)（稱為浮點數(shù)）的尾數(shù)，位數(shù)是固定的，稱為字長。設計算機的尾數(shù)，位數(shù)是固定的，稱為字長。設計算機字長為字長為t，任意數(shù)任意數(shù)x十進制是按舍入原則表為浮十進制是按舍入原則表為浮點數(shù)點數(shù)則相對誤差的絕對值則相對誤差的絕對值)1()1(110211021|)(|ttax)0(10.0)(121aaaaxflmt記記稱稱 為計算機的相對精度。我們有：為計算機的相對精度。我們有：( )( )( )(1)fl xxxfl xxx 12121121221212312124()()(1)()()(1)()()(1)(/)(/)(1)fl xxxxfl xxxxfl x xx xfl xxxx則對于多數(shù)相加則對于多數(shù)相加相對誤差相對誤差 123121312