計算方法講義

西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第1頁!教材：計算方法，計算方法課程組作業：計算方法作業集（A、B）參考書：1、封建湖，車剛明，計算方法典型題分析解集（第二版），西北工業大學出版社，2001.2、封建湖，聶玉峰，王振海，數值分析導教導學導考，西北工業大學出版社，2003.課時數：32西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第2頁!章緒論內容提要

§1.1引言

§1.2誤差的度量與傳播

§1.3數值試驗與算法性能比較西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第3頁!§1.1引言提出實際問題辨析其中的主要矛盾和次要矛盾，并在合理假設的條件下，運用各種數學理論、工具和方法，建立起問題中不同量之間的聯系，即得到數學模型。建立數學模型

模型的適定性:數學模型解的存在性（模型內部沒有蘊含矛盾）、惟一性（模型是完備的)以及對原始數據具有的連續依賴性統稱為模型的適定性.科學與工程計算過程：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第4頁!數值問題舉例

是用一階常微分方程初值問題表示的數學模型，要求無窮多個輸出，因而它不是數值問題。但當我們要求出有限個點處函數值的近似值時，便成為一數值問題。

西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第5頁!算法分類:

分類方法1：若算法包含有一個進程則稱其為串行算法，否則為并行算法。分類方法2：從算法執行所花費的時間角度來講，若算術運算占絕大多數時間則稱其為數值型算法，否則為非數值型算法。本課程介紹數值型串行算法。（其它類型算法參閱數據結構、并行算法等課程。）西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第6頁!例1例2秦九韶算法

西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第7頁!科學與工程計算過程小結提出實際問題建立數學模型提出數值問題設計可靠、高效的算法程序設計、上機實踐計算結果計算結果的可視化

在具體問題的求解過程中，上述步驟形成一個循環。科學計算（數值模擬）已經被公認為與理論分析、實驗分析并列的科學研究三大基本手段之一。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第8頁!本課程的學習方法盡管我們所學算法有限，但許多仍有學多學生會覺得公式多，理論分析復雜。我們提出如下的幾點學習方法，僅供初學者參考。1、以算法的理論分析為基礎，理解記憶公式。2、搞清各章問題的基本提法,算法提出的背景。3、理解每個算法建立的數學背景、數學原理和基本線索，熟練掌握最基本的算法。4、從各種算法的理論分析中學習推理證明方法，提高推理證明能力。5、認真進行數值計算的訓練。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第9頁!一、誤差來源及其分類1)模型誤差（描述誤差）反映實際問題有關量之間的計算公式（數學模型）通常是近似的。2）觀測誤差數學模型中包含的某些參數是通過觀測得到的。

在計算方法中不研究這兩類誤差，總是假定數學模型是正確合理的反映了客觀實際問題。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第10頁!4）舍入誤差

在實現數值方法的過程中，由于計算機表示浮點數采用的是有限字長，因而僅能夠區分有限個信息，準確表示某些數，不能準確表示所有實數，這樣在計算機中表示的原始輸入數據、中間計算數據、以及最終輸出結果必然產生誤差，稱此類誤差為舍入誤差。如利用計算機計算e的近似值en時，實際上得不到en的精確值，只能得到en的近似e*；這樣e*作為e的近似包含有舍入誤差和截斷誤差兩部分：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第11頁!1.絕對誤差絕對誤差定義：準確值減近似值

絕對誤差限：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第12頁!西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第13頁!有效數：當x*

準確到末位，即n=p，則稱x*為有效數。舉例：x=π,x1*=3.141,x2*=3.1423位有效數字，非有效數4位有效數字，有效數西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第14頁!4.誤差度量間的聯系絕對誤差與相對誤差絕對誤差與有效數字相對誤差與有效數字西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第15頁!Remark1、該定理實質上給出了一種求相對誤差限的方法。2、僅從并不能保證x*一定具有n位有效數字。如設其近似值a=0.484，其相對誤差為：我們并不能由此斷定a有兩位有效數字，因為西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第16頁!三、誤差的傳播概念：近似數參加運算后所得之值一般也是近似值，含有誤差，將這一現象稱為誤差傳播。誤差傳播的表現：算法本身可能有截斷誤差；初始數據在計算機內的浮點表示一般有舍入誤差；每次運算一般又會產生新的舍入誤差，并傳播以前各步已經引入的誤差；誤差有正有負，誤差積累的過程一般包含有誤差增長和誤差相消的過程，并非簡單的單調增長；運算次數非常之多，不可能人為地跟蹤每一步運算。

西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第17頁!復習泰勒公式西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第18頁!相對誤差：進而得到如下絕對誤差限和相對誤差限傳播關系：

西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第19頁!二元函數算術運算誤差傳播規律絕對誤差限相對誤差限西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第20頁!一些避免相近數相減示例當|x|>>1時當|x|<<1時西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第21頁!盡可能避免絕對值很小的數做分母，防止出現溢出。當a,b中有近似值時，由若，則可能很大。當a,b都是準確值時，由于很大，會使其它較小的數加不到中而引起嚴重誤差，或者會發生計算機“溢出”，導致計算無法進行下去。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第22頁!算例算法1a0.00000.10×1010.50000.25×10－7算法2a0.25000.75×10－70.50000.25×10－7算法1b0.26000000.40×10－10.49999870.10×10－6算法2b0.25000200.50×10－80.50000000.25×10－7計算結果西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第23頁!方法1計算結果西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第24頁!方法2計算結果西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第25頁!本章知識結構圖西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第26頁!3）z*有5位有效數字，

絕對誤差限為：

相對誤差限為：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第27頁!解:例3:已知桌子長寬近似值，并且已知，求近似面積的絕對誤差限和相對誤差限。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第28頁!提出數值問題數值問題是指有限個輸入數據（問題的自變量、原始數據）與有限個輸出數據（待求解數據）之間函數關系的一個明確無歧義的描述。這正是數值分析所研究的對象。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第29頁!設計高效可靠的算法計算方法的任務之一就是提供求得數值問題近似解的方法—算法。

算法：指把對數學問題的解法歸結為只有加、減、乘、除等基本運算，并確定運算次序的完整而準確的描述。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第30頁!

算法的可靠性：算法的可靠性包括算法的收斂性、穩定性、誤差估計等幾個方面。這些是數值分析研究的第二個任務。一個算法在保證可靠的大前提下再評價其優劣才是有價值的。算法的優劣評價：可靠算法的優劣，應該考慮其時間復雜度（計算機運行時間）、空間復雜度（占據計算機存儲空間的多少）以及邏輯復雜度（影響程序開發的周期以及維護）。這是數值分析研究的第三個任務。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第31頁!算法應用狀態

計算方法研究對象以及解決問題方法的廣泛適用性，著名流行軟件如Maple、Matlab、Mathematica等已將其絕大多數內容設計成函數，簡單調用之后便可以得到運行結果。但由于實際問題的具體特征、復雜性，以及算法自身的適用范圍決定了應用中必須選擇、設計適合于自己特定問題的算法，因而掌握數值方法的思想和內容是至關重要的。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第32頁!

鑒于實際問題的復雜性，通常將其具體地分解為一系列子問題進行研究，本課程主要涉及如下幾個方面問題的求解算法：函數的插值和曲線擬合數值積分和數值微分線性方程組求解、非線性方程（組）求解代數特征值問題常微分方程數值解法

本課程主要內容西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第33頁!§1.2誤差的度量與傳播

內容提要：一、誤差的來源二、誤差的度量三、誤差的傳播西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第34頁!3）截斷誤差（方法誤差）數值方法精確解與待求解模型的理論分析解之間的差異。這是由于我們需要將無窮過程截斷為有限過程，而使得算法必須在有限步內執行結束而導致的。例如：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第35頁!二、誤差的度量絕對誤差相對誤差有效數字各種度量之間的關系西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第36頁!2.相對誤差Remark:絕對誤差限雖然能夠刻劃對同一真值不同近似的好壞，但它不能刻劃對不同真值近似程度的好壞。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第37頁!3.有效數字

為了規定一種近似數的表示法，使得用它表示的近似數自身就直接指示出其誤差的大小。為此需要引出有效數字和有效數的概念。

西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第38頁!Remark1:有效數的誤差限是末位數單位的一半，可見有效數本身就體現了誤差界。Remark2:對真值進行四舍五入得到有效數。Remark3:準確數字有無窮多位有效數字。Remark4:從實驗儀器所讀的近似數（最后一為是估計位）不是有效數，估計最后一位是為了確保對最后一位進行四舍五入得到有效數。例從最小刻度為厘米的標尺讀得的數據123.4cm是為了得到有效數123.cm,讀得數據156.7cm是為了得到有效數157.cm。西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第39頁!定理證明證畢西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第40頁!例題解：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第41頁!初值誤差傳播：假設每一步都是準確計算，即不考慮截斷誤差和由運算進一步引入的舍入誤差，僅介紹初始數據的誤差傳播規律。研究方法：泰勒（Taylor）方法n元函數西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第42頁!泰勒公式分析初值誤差傳播西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第43頁!

對于一元函數，有如下初值誤差傳播近似計算公式：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第44頁!盡量避免相近的數相減

例x=52.127x*=52.129四位有效數字

y=52.123y*=52.121四位有效數字

A=x-y=0.004A*=x*-y*=0.008

零位有效數字結論：避免相近數相減§1.3數值試驗與算法性能比較西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第45頁!兩種算法的相對誤差圖比較西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第46頁!算例

用不同位數的浮點數系統求解如下線性方程組

算法1：順序消去法，分別保留4位和7位小數進行計算；算法2：將第1個和第2個方程交換次序后，使用消去法分別保留4位和7位小數進行計算；準確解：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第47頁!選用數值穩定性好的算法。定義：一個算法,如果在運算過程中舍入誤差在一定條件下能夠得到控制,或者舍入誤差的增長不影響產生可靠的結果,則稱該算法是數值穩定的,否則稱其為數值不穩定.例：計算如下積分近似值的兩種方案比較方法1：西北工業大學計算方法課件章緒論nwpu共53頁，您現在瀏覽的是第48頁!方法一結果分析方法一分析：計算結果表明,舍入誤差的傳播近似依5的冪次進行增長,