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

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