《《數(shù)值分析》》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)值分析》》PPT課件.ppt（47頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、數(shù) 值 分 析 理 學(xué) 院 劉 秀 娟 第 1 章 緒 論 1.1 數(shù)值分析的研究對象 數(shù)值分析是近代數(shù)學(xué)的一個重要分支，它是研究 各種數(shù)學(xué)問題的 數(shù)值解法 ，包括方法的構(gòu)造和求 解過程的理論分析。 在電子計算機成為數(shù)值計算的主要工具之后，則 要求研究適合于計算機使用的數(shù)值計算方法，為 了更好地說明數(shù)值分析的研究對象，我們考察用 計算機解決科學(xué)計算問題時經(jīng)歷的幾個過程： 提問：數(shù)值分析是做什么用的？ 提問：數(shù)值分析是做什么用的？ 選擇數(shù)值 計算方法 程序設(shè)計 上機計算 求出結(jié)果 構(gòu)造數(shù) 學(xué)模型 實 際 問 題 任務(wù)：數(shù)值分析的任務(wù)是提供在計算 機上實際可行的，有可靠理論分析、 計算復(fù)雜性好的各
2、種數(shù)值計算方法。 特點：數(shù)值分析是與計算機及其它科 學(xué)有密切關(guān)系的數(shù)學(xué)課程，因此它即 具有純數(shù)學(xué)的高度抽象性與嚴密科學(xué) 性的特點，同時又具有應(yīng)用廣泛性與 數(shù)值試驗的高度技術(shù)性，除此之外， 它還有以下幾個基本特點： 1、采用“構(gòu)造性”方法； 2、采用“離散化”方法； 3、采用“遞推化”方法； 4、采用“近似代替”方法等等。 研究內(nèi)容 線性方程組的數(shù)值解 矩陣特征值與特征向量計算 非線性方程的數(shù)值解 數(shù)值逼近 數(shù)值積分 常微、偏微的數(shù)值解 研究方法 理論分析 算法分析 誤差分析 收斂性分析 收斂速度 1.2 誤差 知識與算法知識 1.2.1 誤差的來源與分類 在工程技術(shù)的計算中，估計計算結(jié) 果的精
3、確度是十分重要的工作，而影響 精確度的是各種各樣的誤差。誤差的來 源是復(fù)雜的，但主要有以下四種： 從實際問題中抽象出數(shù)學(xué)模型 模型誤差 ( Modeling Error ) 通過測量得到模型中參數(shù)的值 觀測誤差 ( Measurement Error ) 求近似解 方法誤差 (截斷誤差 ( Truncation Error ) ) 機器字長有限 舍入誤差 ( Roundoff Error ) 模型誤差 處理實際問題時，要建立數(shù)學(xué)模型，通常模型只 是近似的。由此產(chǎn)生的 數(shù)學(xué)模型解 與 實際問題的 解 之間的誤差叫 模型誤差 。 例如 是實際問題的解，而若數(shù)學(xué)模型的解是 由此產(chǎn)生的誤差叫作模型誤差
4、。 865 6 s i n , 0 1 0y x x x 65 6 , 0 1 0 ,y x x 觀測誤差 數(shù)學(xué)模型中包含某些變量，如時間、長度、電壓 等，它們一般是通過觀測來獲得。由于觀測得到 的數(shù)據(jù)與實際數(shù)據(jù)之間有誤差，這種誤差叫 觀測 誤差。 截斷誤差 求解數(shù)學(xué)模型所用的數(shù)值計算方法，如果是一種 近似的方法，只能得到模型的近似解，由此產(chǎn)生 的誤差稱為 截斷誤差 或 方法誤差。 舍入誤差 由于計算機的字長有限，參加運算的數(shù)據(jù)及其 運算結(jié)果在計算機中存放會產(chǎn)生誤差。這種誤 差叫 舍入誤差 或 計算誤差 。 例如 在 16 位微機上計算，單精度實數(shù)存放僅有 7 位有效數(shù)字。在其上運算，會有 1
5、 3 0.333 333 3, (1.000 002)2 1.000 004 0, 后者的準確結(jié)果是 4 1012。 dxe x 10 2 近似計算:例 大家一起猜？ dxe 2x10 1 1 / e 解法之一 ： 將 作 Taylor展開后再積分 2xe 9 1 !4 1 7 1 !3 1 5 1 !2 1 3 1 1 ) !4!3!2 1( 1 0 864 21 0 dx xxx xdxe 2x S4 R4 ( Remainder ) ,10 4 Sdxe 2x取 則 11 1 !5 1 9 1 !4 1 4R 稱為 截斷誤差 ( Truncation Error ). 005091!41
6、4 .R 這里 74300240103330142110 13114 .S 0010200050 . | 舍入誤差 ( Roundoff Error ) | 0 0 600 0 100 0 5010 2 .dxe -x 的總體誤差計算 = 0.747 由截去部分 ( excluded terms ) 引起 由留下部分 ( included terms ) 引起 1.2.2 絕對誤差、相對誤差與有效數(shù)字 (Error and Significant Digits ) 定義 絕對誤差 (absolute error) e x x 10 006074302 .dxe x例如： 其中 x 為精確值，
7、x* 為 x 的近似值。 |e|的上 界記為 , 稱為 絕對誤差限 (accuracy),工程上常記 為 x = x* 注 :理論上講 ,e 是唯一確定的 , 可能取正 , 也可能取負 . 不唯一 ， 當然 越小越具有參考價值。 提問：絕對誤差限的大小能否完全地 表示近似值的好壞？ 例如： 有兩個量 問： 誰的近似程度要好一些？ 51 0 0 0,110 yx 思考 定義 近似值 x* 的 相對誤差 (relative error) . r e x xe xx .|r x 定義 近似值 x* 的 相對誤差上限 (界 ) (relative accuracy) .r ee x 由于精確值 x 未
8、知 , 實際上總把 作為 x*的 相對誤差，并且仍記為 er , 即 ex 注 :相對誤差一般用百分比表示 . 例 1 用最小刻度為毫米的卡尺測量直桿甲和直桿 乙，分別讀出長度為 a=312mm 和 b=24mm， 問： (a)， (b)， r(a)， r(b)各是多少？兩直桿的 實際長度 x 和 y 在什么范圍內(nèi)？ 解： mmymm mmxmm b b b a a a mmba r r 5.245.23 ,5.3125.311 %,08.2 24 5.0)( )( %,16.0 312 5.0)( )( ,5.0)()( 例 2 設(shè) a=-2.18 ， b=2.1200 是分別由準確值 x和
9、 y 經(jīng)過四舍五入而得到的近似值， 問： (a)， (b)， r(a)， r(b) 各是多少？ 解： %00 24.0 12 00.2 00 00 5.0)( )( %,23.0 18.2 00 5.0)( )( 0500 0.0)(,00 5.0)( b b b a a a ba r r 有效數(shù)字 ( significant digits) 四舍五入帶來的絕對誤差限 凡是由準確值 x 經(jīng)四舍五入而得到近似值 x*，其絕對誤差 限等于該近似值 末位 的半個單位。 定義 有效數(shù)字 設(shè) x* 是數(shù) x 的近似值，如果 x* 的絕對誤差限是它的 某一位的半個單位，并且從該位到它的第一位非零數(shù)字共 有
10、 n 位，則稱用 x* 近似 x 時，具有 n 位有效數(shù)字 。 用科學(xué)計數(shù)法，記 （其中 ） , 0 1 a mnaa.ax 100 21* *| | 0 5 1 0 mnx x . 若 (即 an 的截取按四舍五入規(guī)則 )， 則 x* 至少有 n 位有效數(shù)字，且精確到 10m n. 有效數(shù)字的確定方法 有效數(shù)字的位數(shù) n = 近似數(shù)科學(xué)記數(shù)法的冪指 數(shù) 絕對誤差限科學(xué)記數(shù)法的冪指數(shù) . 當差為負整數(shù)時 ，表示沒有效數(shù)字 ! 把誤差限 表示為 0.5 10mn, 當指數(shù) m n 是最小的整數(shù) 時 , 有效數(shù)字的位數(shù)精確地是 n. 例 3 下列近似值的絕對誤差限都是 0.005， 問：各個近似值
11、有幾位有效數(shù)字？ 41086.0,0 3 1 2.0,38.1 cba 注 : 1、同一個準確值的不同近似值，有效數(shù)字 越多，其絕對誤差和 相對誤差都越小 . 2、準確值的有效數(shù)字可看做有無限多位 . 3位： 1， 3， 8 1位： 3 0位 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 1 4 1 6. ; * .例 問： 有幾位有效數(shù)字？請證明你的結(jié)論。 * 注： 1、 由準確值經(jīng)過四舍五入得到的近似值，從它的末位 數(shù)字到第一位非零數(shù)字都是有效數(shù)字。 2、 0.2300有 4位有效數(shù)字，而 0.23只有 2位有效數(shù)字。 12300有 5位有效數(shù)字，如果寫成 0.1
12、23105，則表示只有 3位有效數(shù)字。 數(shù)字末尾的 0不可隨意省去！ 證明 ： 。， a n d 位精確到小數(shù)點后第位有效數(shù)字有 45 105.0105.0 103 1 4 1 6.0 514 1 1.2.3 函數(shù)求值的誤差估計 問題一 ：對于函數(shù) y = f (x)，若用 x* 取代 x， 將對 y 產(chǎn)生什么影響？ 分析 ： e(y) = f (x) f (x*) e(x) = x x * = f ( )(x x *) x* 與 x 非常接近時，可認為 f ( ) f (x*) ，則有： |e(y)| | f (x*)|e(x)| (1) (2) 即： x*產(chǎn)生的誤差經(jīng)過 f 作用后被放大
13、/縮小了 | f (x*)| 倍。故稱 | f (x*)|為 放大因子 ( amplification factor ) 或 絕對條件數(shù) ( absolute condition number ). )( *)()( xxfy ()| ( ) | ( * )r eyey fx ()| ( ) | *r exex x ( ) ( * ) * * * ( * ) * * ( * ) () ( * ) r f x f x x x x x x f x x x f x ex fx 相對誤差條件數(shù) ( relative condition number) f 的條件數(shù)在某一點是 小 大 ，則稱 f 在該點
14、是 好條件的 ( well-conditioned ) 壞條件的 ( ill-conditioned )。 )4()( ! )( )( )3()( ! )( )( ,0)()()()( )( )( )()1( k k k k kk a k af y ae k af ye af，afafaf 則有如果有 問題二 ：對于 n 元函數(shù) 將對 u 產(chǎn)生什么影響？ ，xaxxxfu iin 的近似值是),( 21 ，xa ii代替用 ） 6（ )( ),( )( ） 5（ )( ),( )( 1 21 1 21 i n i i n i n i i n a x aaaf u ae x aaaf ue 問題
15、三：四則運算結(jié)果的誤差估計 設(shè) a,b 分別是準確值 x,y 的近似值，則 0, )()( .3 )()()( .2 )()()( 1. 2 b b abba b a abbaab baba 設(shè) a,b 分別是準確值 x,y 的近似值，則 )()( 7. )()()( 6. )()( )( 5. )()( )( 4. ba b a baab ba ba ba ba ba ba rrr rrr r r 例 4 設(shè)有三個近似數(shù) a=2.31,b=1.93,c=2.24 它們都有三位有效數(shù)字，試計算 p=a+bc， 并問： p的計算結(jié)果能有幾位有效數(shù)字？ 例 5 )()( pp r 和 ? ),()
16、871.0,30.1( .0005.0871.0,005.030.1, c o s ),( 有幾位有效數(shù)字 能則的近似值作為如果用 設(shè) u，yxffu yx x y yxf (p) 0.02585 2位 f(x,y) 0.49543 0.39% (u) 0.00220.005 p 6.6332 )(pr 1.2.4 算法及其計算復(fù)雜性 定義 算法 就是規(guī)定了怎樣從輸入數(shù)據(jù)計算出數(shù) 值問題解的一個有限的基本運算序列 . 定義 算法的計算復(fù)雜性 是指在達到給定精度時 , 該算法所需的計算量和所占的內(nèi)存空間 . 前者叫 時間復(fù)雜性 ，后者叫 空間復(fù)雜性 . 例子 計算下面多項式的值。輸入數(shù)據(jù)為 ai
17、和 x， 輸出數(shù)據(jù)為 p(x) 的值。 i n i i xaxp 0 )( 算法一 算法二 （秦九韶法） 00 01 ( 1 , 2 , , ), () k kk n kn sa s a x p x s s s 1 0 ( 1 , 2 , , 1 , 0), () nn k k k k n n Ta T x T a p x T i n i i xaxp 0 )( 12 1 2 1 0 1 2 1 1 2 1 0 2 3 0 1 2 1 0 () = ( ) = ( ) nn nn nn nn nn nn p x a x a x a x a x a a x a x a x a x a a x a
18、 x a x x a x a 1 3 2 1 0 = = ( ( ( ( ) ) ) )nna x a x a x a x a x a 秦九韶法原理 Tn=an Tn-1= xTn+an-1 T 0= xT1+a0 T1= xT2+a1 算法比較 算法一 所需乘法次數(shù)為 n(n+1)/2,加法次數(shù)為 n。 算法二 所需乘法次數(shù)為 n，加法次數(shù)也為 n。 兩種算法所占內(nèi)存空間基本相同。 算法二是 1247年我國數(shù)學(xué)家秦九韶首次提出的。 注意：簡化計算步驟，減小運算次數(shù) . 算法一 逐個相乘要用 254次乘法。 算法二 14次乘法。 例子 計算 的值 。 255x 思考 1 2 864321684
19、22 5 5 xxxxxxxxx 算法比較 1. 避免相近二數(shù)相減 例： a1 = 0.12345， a2 = 0.12346，各有 5位有效數(shù)字。 而 a2 a1 = 0.00001，只剩下 1位有效數(shù)字。 幾種經(jīng)驗性避免方法： ;xx xx ;1lnlnln xxx 當 | x | 1 時： ;2s i n2c os1 2 xx .612111 2xxxe x 設(shè)計算法時應(yīng)遵循的一些原則 2. 避免小分母 : 分母小會造成浮點溢出 ( over flow ) 3. 避免大數(shù) 吃 小數(shù) 例： 用單精度計算 的根。 010)110( 992 xx 精確解為 110 291 x,x 算法 1:
20、利用求根公式 a acbbx 2 42 在計算機內(nèi)， 109存為 0.11010， 1存為 0.1101。 做加法時， 兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即 1 的指數(shù)部分須變?yōu)?1010，則： 1 = 0.0000000001 1010，取 單精度時就成為： 109+1=0.100000001010+0.00000000 1010=0.10000000 1010 大數(shù) 吃 小數(shù) 02 4,102 4 2 2 9 2 1 a acbbx a acbbx 算法 2:先解出 再利用 9 2 1 102 4)( a acbbs i g nbx 11010 9 9 1 221 xa cx
21、a cxx 注： 求和時 從小到大 相加，可使和的誤差減小。 例： 按從小到大、以及從大到小的順序分別計算 1 + 2 + 3 + + 40 + 10 9 4. 先化簡再計算，減少步驟，避免誤差積累。 一般來說，計算機處理下列運算的速度為 e x p , 5. 選用穩(wěn)定的算法 ,控制舍入誤差的傳播。 誤差傳播與積累 .2101 1 0 ,n,dxexeI xnn 例： 計算 11.nnI n I 公式一： 1 1 11 11 0 0 0 0 11 d d 1 d .n x n x n x n xnx e x x e n x e x x e x e e e 注意此公式 精確 成立 , 因為 1
22、0 0 11 d 1 0 63 21 20 56 xI e x . ee 記為 *0,I 80 0 0 0 5 10 . E I I . 則初始誤差 11 01 00 1 1 1 1d d , ( 1 ) 1 nn nnx e x I x e x Ie e e n n 3 9 1 41 4 2 3151 9 5 9 4 2 494141 2 2 7 6 4 8 07131 6 3 2 8 9 6 0 00121 0 3 0 5 9 2 0 00111 0 8 8 1 2 8 0 00101 . 3 6 7 8 7 9 4 4011 1415 * 13 * 14 * 12 * 13 * 11 *
23、 12 * 10 * 11 * 9 * 10 * 0 * 1 .II .II .II .II .II .II .II ? ? ? ! ! ! What happened ?! 考察第 n步的誤差 nE |)1()1(| * 11* nnnnn nInIIIE |! 01 En|En n 11 11 ( 1 ) n n n nI n I I In 公式 方法：先估計一個 IN ,再反推要求的 In ( n N )。 (unstable algorithm), 我們有責(zé)任改變。 造成這種情況的是 不穩(wěn)定的算法 迅速積累 , 可見初始的小擾動 8 0 1050| .E 誤差呈遞增 . 考察反推一步的
24、誤差： |1)1(1)1(1| *1 NNNN ENININE 以此類推，對 n N 有： 1| | | | . ( 1 ) . ( 1 ) nNEEN N n 誤差逐步遞減 , 這樣的算法稱為 穩(wěn)定的算法 (stable algorithm). 在我們今后的討論中 , 誤差 將不可回避 , 算法的 穩(wěn)定性 會是一個非常重要的話題。 11 , ( 1 ) 1NIe N N NN INNeI 1 1 )1( 1 2 1*可取 當 N 時， *| | 0 N N NE I I 632120560)1( 1 1 367879440)1( 2 1 0838771150)1( 11 1 07735173
25、20)1( 12 1 0717792140)1( 13 1 0668702200)1( 14 1 0638169180)1( 15 1 0427462330 16 1 16 1 2 1 * 1 * 0 * 2 * 1 * 11 * 10 * 12 * 11 * 13 * 12 * 14 * 13 * 15 * 14 * 15 .II .II .II .II .II .II .II . e I 取 We just got lucky? 作 業(yè) 題 書： P12 習(xí)題一 1、 2、 3、 4、 5、 6、 7、 8、 12 練 習(xí) 題 1、 下列各近似值均有四位有效數(shù)字，試指出它們 的絕對誤差限和
26、相對誤差限。 2、 下列近似值的絕對誤差限都是 0.0005，試指出 它們有幾位有效數(shù)字。 3、 在四位十進制的限制下，試選擇精確度最高 的算法，計算下式的值。 200.1,341.12,0 1 3 4 7.0 cba 0 0 0 3 2.0,0 4 2.0,0 0 0 3 1.1 cba 90605040101 3 4 0 2 u 4、 設(shè) ， 在四位十進制的限制下，試 使用一個具有數(shù)值穩(wěn)定性的算法，計算 的近似值。 dxxxy n n 1 0 41 )8,1,0( ny n 答案： 1、 0.000005,0.03712%;0.005,0.04052%;0.0005,0.04167%. 2、 4、 2、 0 3、 134200 4、 )1( 4 1,14 11 nnnn ynynyy 數(shù)學(xué)符號 x0, x1, , xn, y0, y1, , ym, xi 1 i k=0,1, , n 1. 0 x,1x, , nx (x, y) pnm(x, y)
《數(shù)值分析》》PPT課件.ppt
