計算方法概論

1、第1章 計算方法概論(giln) 運用(ynyng)數(shù)學(xué)方法解決科學(xué)研究或工程技術(shù)問題，一般按如下途徑進(jìn)行：實際問題模型設(shè)計算法設(shè)計程序設(shè)計上機(jī)計算問題的解 其中算法設(shè)計是計算方法課程的主要內(nèi)容. 結(jié)束1 計算方法又稱數(shù)值分析，是計算數(shù)學(xué)的重要組成部分。共二十七頁 1.1 引言(ynyn)結(jié)束(jish)21.1.1 計算方法的意義 計算方法對于計算速度與增強(qiáng)計算結(jié)果的準(zhǔn)確性來說，與計算機(jī)硬件同等重要。這就導(dǎo)致了計算方法研究領(lǐng)域的空前活躍。1.1.2 計算方法的任務(wù) 計算方法課程研究常見的基本數(shù)學(xué)問題的數(shù)值解法.包含了數(shù)值代數(shù)(線性方程組的解法、非線性方程的解法、矩陣求逆、矩陣特征值計算等)、

2、數(shù)值逼近、數(shù)值微分與數(shù)值積分、常微分方程及偏微分方程的數(shù)值解法等.它的基本理論和研究方法建立在數(shù)學(xué)理論基礎(chǔ)之上，研究對象是數(shù)學(xué)問題，因此它是數(shù)學(xué)的分支之一.共二十七頁 1.2 算法(sun f)與效率結(jié)束(jish)31.2.1 算法 進(jìn)行科學(xué)計算，需要構(gòu)造確定型數(shù)值算法，確定型算法可定義為：從給定的已知量出發(fā)，按指定的運算順序，經(jīng)過有限次的四則運算及邏輯運算，可求出給定問題的數(shù)值解的完整的計算步驟。1.2.2 算法的效率 一個算法所需要四則浮點運算的總次數(shù)定義為它的計算量，單位是flop。由于+，-運算速度很快，可忽略，因此，算法的計算量簡化為該算法所需要的乘法和除法運算的總次數(shù)。計算量越小

3、，計算效率就越高。共二十七頁1.2.3 算法的表述形式 算法的表述形式是多種多樣的. 1 用數(shù)學(xué)公式和文字說明描述，這種方式(fngsh)符合人們的理解習(xí)慣，和算法的推證相銜接，易于學(xué)習(xí)接受，但離上機(jī)應(yīng)用距離較大. 2用框圖描述，這種方式描述計算過程流向清楚，易于(yy)編制程序 ，詳略難以掌握. 4 算法程序，即用計算機(jī)語言描述的算法，它是面對計算機(jī)的算法。我們以后討論的算法，都有現(xiàn)成的程序文本和軟件可資利用. 但從學(xué)習(xí)算法的角度看，這種描述方式并不有利.結(jié)束 3 算法描述語言，它是表述算法的一種通用語言。有特定的表述程序和語句?？梢院苋菀椎剞D(zhuǎn)化為某種計算機(jī)語言，同時也具有一定的可讀性。4共

4、二十七頁 本教材將采用前三種方式(fngsh)表述各種算法.1.2.4 算法的基本(jbn)特點 1 算法常表現(xiàn)為一個無窮過程的截斷： 例1 計算 sin x的值， 根據(jù)sin x 的無窮級數(shù)( 1.1) 這是一個無窮級數(shù)，我們只能在適當(dāng)?shù)牡胤健敖財唷?，使計算量不太大，而精度又能滿足要求. 如計算 sin 0.5，取n=3結(jié)束5共二十七頁 據(jù)泰勒(ti l)余項公式，它的誤差應(yīng)為( 1.2)可見結(jié)果是相當(dāng)精確(jngqu)的.實際上結(jié)果的六位數(shù)字都是正確的. 2 算法常表現(xiàn)為一個連續(xù)過程的離散化 例2 計算積分值.將0，1分為4等分，分別計算4個小曲邊梯形的面積的近似值，然后加起來作為積分的近

5、似值(如圖1-1).記被積函數(shù)為 f(x) ，即結(jié)束6共二十七頁011yx圖1-1計算有：I0.697 024，與精確值0.693 147比較，可知結(jié)果(ji gu)不夠精確，如進(jìn)一步細(xì)分區(qū)間，精度可以提高. 3 算法常表現(xiàn)為“迭代”形式.迭代是指某一簡單算法的多次重復(fù)，后一次使用前一次的結(jié)果.這種形式易于在計算程序中實現(xiàn)(shxin)，在程序中表現(xiàn)為“循環(huán)”過程. 例3 多項式求值. 結(jié)束7共二十七頁 用tk表示(biosh)xk，uk表示(1.4)式前k+1項之和.作為初值令： (1.5) 對k=1,2,n，反復(fù)(fnf)執(zhí)行： (1.6) 顯然Pn(x)=un，而(1.6)式是一種簡單算

6、法的多次循環(huán). 令 k=1,2, ,n (1.7)結(jié)束 對此問題還有一種更好的迭代算法.8共二十七頁 顯然(xinrn)Pn(x)=vn . 這兩種算法都是將n次多項式化為n個一次多項式來計算，這種化繁為簡的方法在數(shù)值分析中經(jīng)常(jngchng)使用. 下面估計一下以上兩種算法的計算量： 第一法：執(zhí)行n次(1.6)式，每次2次乘法，一次加法，共計2n次乘法，n次加法； 第二法：執(zhí)行n次(1.7)式，每次1次乘法，一次加法，共計n次乘法， n次加法. 顯然第二種方法運算量小，它是我國宋代數(shù)學(xué)家秦九韶最先提出的，被稱為“秦九韶算法”. 例4 不用開平方計算 (a0)的值. 假定x0是 的一個近似值

7、，x0 0，則 也是 的一個近似值，且x0和 兩個近似值必有一個大于 ，另結(jié)束9共二十七頁一個小于 ，可以設(shè)想它們的平均值應(yīng)為 的更好的平均值，于是設(shè)計(shj)一種算法：10 (k=0,1,2,) (1.8) 如計算(j sun) ，取x0 =2，有 (k=0,1,2,)計算有：x0=2 x1=1.75 x2=1.732 142 9 x3=1.732 050 8 可見此法收斂速度很快，只算三次得到8位精確數(shù)字. 迭代法應(yīng)用時要考慮是否收斂、收斂條件及收斂速度等問題，今后課程將進(jìn)一步討論.結(jié)束共二十七頁 1.4 誤 差 1.4.1 誤差的來源 在運用數(shù)學(xué)方法解決(jiju)實際問題的過程中，每

8、一步都可能帶來誤差. 1 模型誤差 在建立數(shù)學(xué)模型時，往往要忽視很多次要因素(yn s)，把模型“簡單化”，“理想化”，這時模型就與真實背景有了差距，即帶入了誤差. 2 測量誤差 數(shù)學(xué)模型中的已知參數(shù)，多數(shù)是通過測量得到.而測量過程受工具、方法、觀察者的主觀因素、不可預(yù)料的隨機(jī)干擾等影響必然帶入誤差. 3 截斷誤差 數(shù)學(xué)模型常難于直接求解，往往要近似替代，簡化為易于求解的問題，這種簡化帶入誤差稱為方法誤差或截斷誤差. 4 舍入誤差 計算機(jī)只能處理有限數(shù)位的小數(shù)運算，初始參數(shù)或中間結(jié)果都必須進(jìn)行四舍五入運算，這必然產(chǎn)生舍入誤差.結(jié)束11共二十七頁 在數(shù)值分析課程中不分析討論模型誤差；截斷誤差是數(shù)

9、值分析課程的主要討論對象，它往往是計算中誤差的主要部分，在講到各種算法時，通過數(shù)學(xué)方法可推導(dǎo)出截斷誤差限的公式(如(1.2)式)；舍入誤差的產(chǎn)生往往帶有很大的隨機(jī)性，討論比較困難，在問題本身呈病態(tài)或算法穩(wěn)定性不好時，它可能成為計算中誤差的主要部分；至于測量誤差，我們(w men)把它作為初始的舍入誤差看待. 誤差(wch)分析是一門比較艱深的專門學(xué)科.在數(shù)值分析中主要討論截斷誤差及舍入誤差.但一個訓(xùn)練有素的計算工作者，當(dāng)發(fā)現(xiàn)計算結(jié)果與實際不符時，應(yīng)當(dāng)能診斷出誤差的來源，并采取相應(yīng)的措施加以改進(jìn)，直至建議對模型進(jìn)行修改.結(jié)束12共二十七頁 1.4.2 誤差的基本概念 1 誤差與誤差限 定義1.1

10、 設(shè)x*是準(zhǔn)確值，x是它的一個(y )近似值，稱e=x-x*為近似值x的絕對誤差，簡稱誤差. 誤差是有量綱的量，量綱同x，它可正可負(fù). 誤差一般無法準(zhǔn)確計算，只能(zh nn)根據(jù)測量或計算情況估計出它的絕對值的一個上限，這個上界稱為近似值x的誤差限，記為 x-x*，其意義是：x-x*x+在工程中常記為： x*= x.如 l=10.2.mm，R=1500100 2 相對誤差與相對誤差限 誤差不能完全刻畫近似值的精度.如測量百米跑道產(chǎn)生10cm的誤差與測量一個課桌長度產(chǎn)生1cm的誤差，我們不能簡單地認(rèn)為后者更精確，還應(yīng)考慮被測值的大小.下面給出定義：結(jié)束13共二十七頁 定義1.2 誤差與精確值的

11、比值 稱為(chn wi)x的相對誤差，記作er. 相對誤差是無量綱的量，常用百分比表示，它也可正可負(fù).相對誤差也常不能準(zhǔn)確計算(j sun)，而是用相對誤差限來估計. 相對誤差限： 實際上由于x*不知道，用上式無法確定r ，常用x代x*作分母，此時：結(jié)束14共二十七頁 以后我們就用 表示(biosh)相對誤差限. 例5 在剛才測量(cling)的例子中，若測得跑道長為1000.1m，課桌長為1201cm ，則顯然后者比前者相對誤差大. 1.4.3 有效數(shù)字 定義1.3結(jié)束15共二十七頁 定義(dngy)1.4結(jié)束(jish)16共二十七頁 如：=3.14159265 則3.14和3.1416

12、分別(fnbi)有3位和5位有效數(shù)字.而3.143相對于也只能有3位有效數(shù)字 如a=0.034537，則近似(jn s)數(shù)0.0345有3位有效數(shù)字又如近似數(shù)c=30.4和d=30.40分別有3位和4位有效數(shù)字 如計算機(jī)上得到方程x3-x-1=0的一個正根為1.32472，保留4位有效數(shù)字的結(jié)果為1.325，保留5位有效數(shù)字的結(jié)果為1.3247.相對誤差與有效數(shù)位的關(guān)系十分密切.定性地講，相對誤差越小，有效數(shù)位越多，反之亦正確.定量地講，有如下兩個定理. 定理1.1 設(shè)近似值x=0.a1a2an10m有n位有效數(shù)字，則其相對誤差限 此定理的證明不難，可作為習(xí)題完成.結(jié)束17共二十七頁 定理1.

13、2 設(shè)近似值x=0.a1a2an10m的相對誤差(xin du w ch)限不大于 ，則它至少有n位有效數(shù)字. 證 x |(a1+1）10m-1由定義(dngy)1.3知x有n位有效數(shù)字. 例6 計算sin 1.2，問要取幾位有效數(shù)字才能保證相對誤差限不大于0.01%. 解 sin1.2=0.93，故a1=9,m=0 解關(guān)于n的不等式 10-n1810-5=1.810-4.結(jié)束18共二十七頁 所以取n=4，即可滿足要求. 對有效數(shù)字的觀察(gunch)比估計相對誤差容易得多，故監(jiān)視有效數(shù)字是否損失，?？砂l(fā)現(xiàn)相對誤差的突然擴(kuò)大. 例6 計算(j sun) ，視已知數(shù)為精確值，用4位浮點數(shù)計算.

14、解 原式=0.131810-2-0.131610-2=0.210-5 . 結(jié)果只剩一位有效數(shù)字，有效數(shù)字大量損失，造成相對誤差的擴(kuò)大.若通分后再計算： 原式=就得到4位有效數(shù)字的結(jié)果.下文將會提到相近數(shù)字相減會擴(kuò)大相對誤差.結(jié)束19共二十七頁 1.5 設(shè)計(shj)算法時應(yīng)注意的原則 1.5.1數(shù)值運算時誤差的傳播當(dāng)參與(cny)運算的數(shù)值帶有誤差時，結(jié)果也必然帶有誤差，問題是結(jié)果的誤差與原始誤差相比是否擴(kuò)大. 1)對函數(shù)f(x)的計算:設(shè)x是x*的近似值，則結(jié)果誤差用泰勒展式分析忽略第二項高階無窮小之后，可得函數(shù)f(x)的誤差限估計式結(jié)束20共二十七頁 2)對多元(du yun)函數(shù)f(x1

15、*,x2*,xn*)=A*,設(shè)x1,x2,xn是x1*,x2*,xn*的近似值，則A=f(x1,x2,xn)是結(jié)果的近似值。其中(qzhng)結(jié)束略去高階項后21共二十七頁 3）四則運算中誤差(wch)的傳播 按（1.10）易得:其中(1.11)取等號,是因為作為多元函數(shù),加減法的一次函數(shù)，泰勒展開(zhn ki)沒有二次余項。結(jié)束例7：若電壓V=220 5V，電阻R=300 10 ，求電流I并計算其誤差限及相對誤差限。解：22共二十七頁所以(suy)結(jié)束(jish)1.5.2 算法中應(yīng)避免的問題1）避免相近數(shù)相減 由公式(1.11)23共二十七頁當(dāng)x1和x2十分相近(xin jn)時， x1

16、-x2接近零，結(jié)束(jish)將很大，所以和從直觀上看，相近數(shù)相減會造成有效數(shù)位的減少，本章例6就是一個例子.有時，通過改變算法可以避免相近數(shù)相減.大很多，即相對誤差將顯著擴(kuò)大.將比例8: 解方程x 2-18 x +1=0，假定用4位浮點計算.解: 用公式解法可見第二個根只有兩位有效數(shù)字,精度較差.若第二個根改為用韋達(dá)定理計算可得較好結(jié)果。24共二十七頁結(jié)束(jish)如等等,都可以(ky)得到比直接計算好的結(jié)果。可改為如可改為若則這時將比擴(kuò)大很多。3)防止小數(shù)被大數(shù)“吃掉” 在大量數(shù)據(jù)的累加運算中，由于加法必須進(jìn)行對位，有可能出現(xiàn)小數(shù)被大數(shù)“吃掉”. 252)避免除法中除數(shù)的數(shù)量級遠(yuǎn)小于被除

17、數(shù) 由公式(1.13)共二十七頁結(jié)束(jish)如用六位浮點數(shù)計算某市的工業(yè)總產(chǎn)值，原始數(shù)據(jù)是各企業(yè)的工業(yè)產(chǎn)值，當(dāng)加法進(jìn)行到一定程度，部分和超過100億元 （0.11011），再加產(chǎn)值不足10萬元的小企業(yè)產(chǎn)值，將再也加不進(jìn)去.而這部分企業(yè)可能(knng)為數(shù)不少，合計產(chǎn)值相當(dāng)大.這種情況應(yīng)將小數(shù)先分別加成大數(shù)，然后相加，結(jié)果才比較正確.這個例子告訴我們，在計算機(jī)數(shù)系中，加法的交換律和結(jié)合律可能不成立，這是在大規(guī)模數(shù)據(jù)處理時應(yīng)注意的問題.264)注意運算步驟的簡化減少算術(shù)運算的次數(shù)以減少誤差的積累效應(yīng)：時參加運算的數(shù)字精度應(yīng)盡量保持一致，否則那些較高精度的量的精度沒有太大意義。共二十七頁內(nèi)容摘要第1章 計算方法概論。計算方法對于計算速度與增強(qiáng)(zngqing)計算結(jié)果的準(zhǔn)確性來說，與