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

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