西北工業(yè)大學計算方法課件第一章緒論nwpu.ppt

《西北工業(yè)大學計算方法課件第一章緒論nwpu.ppt》由會員分享，可在線閱讀，更多相關《西北工業(yè)大學計算方法課件第一章緒論nwpu.ppt（53頁珍藏版）》請在裝配圖網上搜索。

計算方法講義 教材 計算方法 計算方法課程組 作業(yè) 計算方法作業(yè)集 A B 參考書 1 封建湖 車剛明 計算方法典型題分析解集 第二版 西北工業(yè)大學出版社 2001 2 封建湖 聶玉峰 王振海 數值分析導教導學導考 西北工業(yè)大學出版社 2003 課時數 32 第一章緒論 內容提要 1 1引言 1 2誤差的度量與傳播 1 3數值試驗與算法性能比較 1 1引言 提出實際問題辨析其中的主要矛盾和次要矛盾 并在合理假設的條件下 運用各種數學理論 工具和方法 建立起問題中不同量之間的聯系 即得到數學模型 建立數學模型模型的適定性 數學模型解的存在性 模型內部沒有蘊含矛盾 惟一性 模型是完備的 以及對原始數據具有的連續(xù)依賴性統(tǒng)稱為模型的適定性 科學與工程計算過程 提出數值問題數值問題是指有限個輸入數據 問題的自變量 原始數據 與有限個輸出數據 待求解數據 之間函數關系的一個明確無歧義的描述 這正是數值分析所研究的對象 數值問題舉例 是用一階常微分方程初值問題表示的數學模型 要求無窮多個輸出 因而它不是數值問題 但當我們要求出有限個點處函數值的近似值時 便成為一數值問題 設計高效可靠的算法計算方法的任務之一就是提供求得數值問題近似解的方法 算法 算法 指把對數學問題的解法歸結為只有加 減 乘 除等基本運算 并確定運算次序的完整而準確的描述 算法分類 分類方法1 若算法包含有一個進程則稱其為串行算法 否則為并行算法 分類方法2 從算法執(zhí)行所花費的時間角度來講 若算術運算占絕大多數時間則稱其為數值型算法 否則為非數值型算法 本課程介紹數值型串行算法 其它類型算法參閱數據結構 并行算法等課程 算法的可靠性 算法的可靠性包括算法的收斂性 穩(wěn)定性 誤差估計等幾個方面 這些是數值分析研究的第二個任務 一個算法在保證可靠的大前提下再評價其優(yōu)劣才是有價值的 算法的優(yōu)劣評價 可靠算法的優(yōu)劣 應該考慮其時間復雜度 計算機運行時間 空間復雜度 占據計算機存儲空間的多少 以及邏輯復雜度 影響程序開發(fā)的周期以及維護 這是數值分析研究的第三個任務 例1 例2秦九韶算法 算法應用狀態(tài) 計算方法研究對象以及解決問題方法的廣泛適用性 著名流行軟件如Maple Matlab Mathematica等已將其絕大多數內容設計成函數 簡單調用之后便可以得到運行結果 但由于實際問題的具體特征 復雜性 以及算法自身的適用范圍決定了應用中必須選擇 設計適合于自己特定問題的算法 因而掌握數值方法的思想和內容是至關重要的 科學與工程計算過程小結 提出實際問題建立數學模型提出數值問題設計可靠 高效的算法程序設計 上機實踐計算結果計算結果的可視化在具體問題的求解過程中 上述步驟形成一個循環(huán) 科學計算 數值模擬 已經被公認為與理論分析 實驗分析并列的科學研究三大基本手段之一 鑒于實際問題的復雜性 通常將其具體地分解為一系列子問題進行研究 本課程主要涉及如下幾個方面問題的求解算法 函數的插值和曲線擬合數值積分和數值微分線性方程組求解 非線性方程 組 求解代數特征值問題常微分方程數值解法 本課程主要內容 本課程的學習方法 盡管我們所學算法有限 但許多仍有學多學生會覺得公式多 理論分析復雜 我們提出如下的幾點學習方法 僅供初學者參考 1 以算法的理論分析為基礎 理解記憶公式 2 搞清各章問題的基本提法 算法提出的背景 3 理解每個算法建立的數學背景 數學原理和基本線索 熟練掌握最基本的算法 4 從各種算法的理論分析中學習推理證明方法 提高推理證明能力 5 認真進行數值計算的訓練 1 2誤差的度量與傳播 內容提要 一 誤差的來源二 誤差的度量三 誤差的傳播 一 誤差來源及其分類 1 模型誤差 描述誤差 反映實際問題有關量之間的計算公式 數學模型 通常是近似的 2 觀測誤差數學模型中包含的某些參數是通過觀測得到的 在計算方法中不研究這兩類誤差 總是假定數學模型是正確合理的反映了客觀實際問題 3 截斷誤差 方法誤差 數值方法精確解與待求解模型的理論分析解之間的差異 這是由于我們需要將無窮過程截斷為有限過程 而使得算法必須在有限步內執(zhí)行結束而導致的 例如 4 舍入誤差在實現數值方法的過程中 由于計算機表示浮點數采用的是有限字長 因而僅能夠區(qū)分有限個信息 準確表示某些數 不能準確表示所有實數 這樣在計算機中表示的原始輸入數據 中間計算數據 以及最終輸出結果必然產生誤差 稱此類誤差為舍入誤差 如利用計算機計算e的近似值en時 實際上得不到en的精確值 只能得到en的近似e 這樣e 作為e的近似包含有舍入誤差和截斷誤差兩部分 二 誤差的度量 絕對誤差相對誤差有效數字各種度量之間的關系 1 絕對誤差 絕對誤差定義 準確值減近似值 絕對誤差限 2 相對誤差 Remark 絕對誤差限雖然能夠刻劃對同一真值不同近似的好壞 但它不能刻劃對不同真值近似程度的好壞 3 有效數字 為了規(guī)定一種近似數的表示法 使得用它表示的近似數自身就直接指示出其誤差的大小 為此需要引出有效數字和有效數的概念 有效數 當x 準確到末位 即n p 則稱x 為有效數 舉例 x x1 3 141 x2 3 142 3位有效數字 非有效數 4位有效數字 有效數 Remark1 有效數的誤差限是末位數單位的一半 可見有效數本身就體現了誤差界 Remark2 對真值進行四舍五入得到有效數 Remark3 準確數字有無窮多位有效數字 Remark4 從實驗儀器所讀的近似數 最后一為是估計位 不是有效數 估計最后一位是為了確保對最后一位進行四舍五入得到有效數 例從最小刻度為厘米的標尺讀得的數據123 4cm是為了得到有效數123 cm 讀得數據156 7cm是為了得到有效數157 cm 4 誤差度量間的聯系 絕對誤差與相對誤差 絕對誤差與有效數字 相對誤差與有效數字 定理證明 證畢 Remark1 該定理實質上給出了一種求相對誤差限的方法 2 僅從并不能保證x 一定具有n位有效數字 如設其近似值a 0 484 其相對誤差為 我們并不能由此斷定a有兩位有效數字 因為 例題 解 三 誤差的傳播 概念 近似數參加運算后所得之值一般也是近似值 含有誤差 將這一現象稱為誤差傳播 誤差傳播的表現 算法本身可能有截斷誤差 初始數據在計算機內的浮點表示一般有舍入誤差 每次運算一般又會產生新的舍入誤差 并傳播以前各步已經引入的誤差 誤差有正有負 誤差積累的過程一般包含有誤差增長和誤差相消的過程 并非簡單的單調增長 運算次數非常之多 不可能人為地跟蹤每一步運算 初值誤差傳播 假設每一步都是準確計算 即不考慮截斷誤差和由運算進一步引入的舍入誤差 僅介紹初始數據的誤差傳播規(guī)律 研究方法 泰勒 Taylor 方法n元函數 復習泰勒公式 泰勒公式分析初值誤差傳播 相對誤差 進而得到如下絕對誤差限和相對誤差限傳播關系 對于一元函數 有如下初值誤差傳播近似計算公式 二元函數算術運算誤差傳播規(guī)律 絕對誤差限 相對誤差限 盡量避免相近的數相減例x 52 127x 52 129四位有效數字y 52 123y 52 121四位有效數字A x y 0 004A x y 0 008零位有效數字結論 避免相近數相減 1 3數值試驗與算法性能比較 一些避免相近數相減示例當 x 1時 當 x 1時 兩種算法的相對誤差圖比較 盡可能避免絕對值很小的數做分母 防止出現溢出 當a b中有近似值時 由 若 則可能很大 當a b都是準確值時 由于很大 會使其它較小的數加不到中而引起嚴重誤差 或者會發(fā)生計算機 溢出 導致計算無法進行下去 算例用不同位數的浮點數系統(tǒng)求解如下線性方程組 算法1 順序消去法 分別保留4位和7位小數進行計算 算法2 將第1個和第2個方程交換次序后 使用消去法分別保留4位和7位小數進行計算 準確解 計算結果 選用數值穩(wěn)定性好的算法 定義 一個算法 如果在運算過程中舍入誤差在一定條件下能夠得到控制 或者舍入誤差的增長不影響產生可靠的結果 則稱該算法是數值穩(wěn)定的 否則稱其為數值不穩(wěn)定 例 計算如下積分近似值的兩種方案比較 方法1 方法1計算結果 方法一結果分析 方法一分析 計算結果表明 舍入誤差的傳播近似依5的冪次進行增長 因而是一種不穩(wěn)定的方法 方法二 由此分析知 該方法是穩(wěn)定的 關于初值的近似可由下面式子得到 方法2計算結果 總之 除了算法的正確性之外 在算法設計中至少還應 1盡量避免兩個相近的近似數相減 2合理安排量級相差很大的數之間的運算次序 防止大數 吃掉 小數 3盡可能避免絕對值很小的數做分母 4防止出現溢出 5簡化計算步驟以減少運算次數 6選用數值穩(wěn)定性好的算法 本章知識結構圖 本章典型例題 例1 指出如下有效數的有效數字位數并計算絕對誤差限和相對誤差限 解 1 x 有2位有效數字 絕對誤差限為 相對誤差限為 2 y 有3位有效數字 絕對誤差限為 相對誤差限為 3 z 有5位有效數字 絕對誤差限為 相對誤差限為 解 由題意知 近似數x 的絕對誤差限 相對誤差限 例2 已知試求的相對誤差限 注意 此處正好有 解 例3 已知桌子長寬近似值 并且已知 求近似面積的絕對誤差限和相對誤差限 例4 下列公式如何變形才能使數值計算得到比較精確的結果