目錄
目錄
前言
第1章 引論 1
1 1 計算機中算術運算的基本概念 3
1 1 1 位與整形 3
1 1 2 計算機中浮點數系統簡介 3
1 2 誤差與誤差分析 6
1 2 1 誤差及其來源 6
1 2 2 近似數的誤差與有效數字 8
1 3 誤差傳播 13
1 3 1 初始誤差傳播分析 13
1 3 2 浮點誤差及其傳播 16
1 4 控制誤差傳播的有效方法 18
1 4 1 避免兩個相近的數相減 18
1 4 2 避免”大數”吃掉小數的現象 20
1 4 3 設計快速算法 21
1 4 4 注意控制誤差的積累 22
1 5 多項式求值的秦九韶算法舍入誤差分析 24
習題1 26
第2章 線性方程組的直接法28
2 1 引言 28
2 2 向量和矩陣範數 30
2 2 1 向量範數 30
2 2 2 矩陣範數 32
2 3 Gauss消去法 38
2 3 1 Gauss消去法 38
2 3 2 選主元的Gauss消去法 40
2 4 矩陣的三角分解法 42
2 4 1 Doolittle分解法 42
2 4 2 Cholesky分解法 47
2 4 3 三對角方程組的追趕法 50
2 5 誤差分析 51
2 5 1 右端項的擾動 51
2 5 2 係數矩陣的擾動 52
第2章 評注 58
習題2 58
上機實驗題 60
第3章 線性方程組的迭代法61
3 1 引言 61
3 2 一般迭代格式及其收斂性 62
3 3 幾種第1迭代算法 67
3 3 1 Jacobi迭代法 67
3 3 2 Gauss-Seidel迭代法 69
3 3 3 逐次超鬆弛迭代法(SOR迭代法) 71
3 4 幾種第1迭代法的收斂性 74
第3章 評注 80
習題3 81
上機實驗題 82
第4章 非線性方程求解的迭代法 84
4 1 引言 84
4 2 搜索法 85
4 2 1 逐步搜索法 85
4 2 2 二分法 86
4 2 3 騎牆法 88
4 3 迭代法及其收斂性 90
4 3 1 不動點迭代法 90
4 3 2 不動點迭代的收斂性 93
4 3 3 局部收斂性與收斂階 96
4 3 4 Newton迭代法 98
4 3 5 割線法 102
4 3 6 迭代法加速收斂技術 103
4 4 非線性方程組的Newton法 107
第4章 評注 110
習題4 111
上機實驗題 112
第5章 多項式插值 113
5 1 引言 113
5 2 Lagrange插值115
5 2 1 Lagrange插值多項式 116
5 2 2 Lagrange插值余項與誤差估計 118
5 3 Newton插值 122
5 3 1 逐步插值多項式的生成 122
5 3 2 差商及其計算 124
5 3 3 Newton插值多項式 126
5 4 Hermite插值 127
5 5 分段低次插值 132
5 5 1 Runge現象 132
5 5 2 分段線性插值 133
5 6 三次樣條函數 135
5 6 1 三次樣條函數 135
5 6 2 三次樣條插值的構造方法 136
第5章 評注 142
習題5 142
上機實驗題 144
第6章 多項式擬合與*佳逼近 146
6 1 引言 146
6 2 *小二乘擬合 146
6 2 1 擬合*線 146
6 2 2 *小二乘多項式擬合 149
6 2 3 加權*小二乘擬合 155
6 3 離散Fourier變換(DFT)與快速Fourier變換(FFT) 159
6 4 *佳平方逼近與正交多項式 164
6 4 1 *佳逼近 164
6 4 2 正交多項式 167
6 4 3 幾種常見的正交多項式 169
6 4 4 正交多項式在*佳逼近中的應用 175
第6章 評注 182
習題6 183
上機實驗題 185
第7章 數值積分與數值微分 186
7 1 引言 186
7 2 Newton-Cotes 公式 187
7 2 1 基本求積公式 187
7 2 2 代數精度 191
7 2 3 Newton-Cotes積分的收斂性與穩定性 192
7 2 4 複合梯形積分 193
7 2 5 複合Simpson求積公式 198
7 3 Richardson外推法與Romberg求積 199
7 3 1 鬆弛技術與Richardson外推法 199
7 3 2 割圓術與圓周率計算 201
7 3 3 圓周率計算的Richardson外推法 202
7 3 4 Romberg求積法 204
7 4 Gauss型積分 207
7 5 數值微分 213
7 5 1 一階導數的計算 214
7 5 2 二階導數的計算 216
7 5 3 從數值微分加速看Richardson外推法 216
第7章 評注 221
習題7 221
上機實驗題 223
第8章 常微分方程數值解 224
8 1 引言 224
8 2 Euler方法及其改進方法 226
8 2 1 Euler方法 226
8 2 2 Euler方法的誤差分析 228
8 2 3 後退Euler方法與梯形方法 229
8 2 4 改進的Euler方法 231
8 3 Runge-Kutta方法 233
8 3 1 一般Runge-Kutta方法 233
8 3 2 二階Runge-Kutta方法 235
8 3 3 三階和四階 Runge-Kutta方法 236
8 3 4 變步長Runge-Kutta 方法 240
8 4 單步法的收斂性與穩定性 241
8 4 1 相容性 241
8 4 2 收斂性 243
8 4 3 穩定性 245
8 5 線性多步法 248
8 5 1 線性多步法的一般公式 248
8 5 2 Adams顯式與隱式方法 250
8 5 3 Adams預測-校正格式 253
8 6 多步法的收斂性與穩定性 254
8 6 1 相容性 254
8 6 2 收斂性 255
8 6 3 穩定性 258
第8章 評注 260
習題8 261
上機實驗題 263
參考文獻 264
精彩書摘
第1章 引論
科學與工程實踐中的許多問題,通常都需要通過數值計算或近似計算來解決 ”數值計算方法”的主要內容就是研究如何利用計算工具(如算盤、算尺、計算器或計算機等),來高效地求出數學問題數值近似解的方法
“數值計算方法”也稱為”計算方法”、”數值分析”或”數值數學”等 我國自古以來就在計算方面成就突出,為世界古代數學的發展做出了卓越貢獻 其中著名的《九章 算術》《孫子算經》《楊輝算法》《算經十書》等都閃耀著我國古代數學先賢在計算丨算術)方面的卓越智慧,而上述書中記載的廣為人知的孫子定理、勾股定理、楊輝三角(也稱為賈憲三角)、劉徽與祖沖之的圓周率計算等研究成果都處於當時世界的領先水平 在現代通信領域,孫子定理(國外一般稱為中國剩餘定理(Chineseremaindertheorem))是基本定理之一 南北朝數學家祖沖之於公元5世紀對圓周率的計算結果,直到公元15世紀才在西方出現類似的結果,這項傑出的數學成就在千年的漫長歲月中一直處於第1第1地位 我國南宋時期數學家秦九韶提出的計算多項式值的方法所需要的運算量被現代數學證明是一種*優算法(即算術運算量達到理論下界),而成書於兩千多年前秦漢時期的《九章 算術》中記載的”方程術”本質就是近代求解線性方程組的Gauss(高斯)消去法
隨著以微積分為基礎的近、現代數學理論的興起,現代計算機的高度普及以及計算機科學與技術的迅速發展,諸如航空航天、數值天氣預報、核武器試驗的仿真模擬、天體演化、生命的進化過程等許多具有海量特徵的數據處理問題都有可能通過數值計算方法得到很好的解決 數值計算方法的內容也發生了很大的變化,大量優秀的數值計算方法不斷湧現,例如,Newton(牛頓)切線法、Gauss消去法、數值積分公式、*小二乘數據擬合、微分方程的Runge-Kntta(龍格-庫塔)法與Adams(亞當斯)方法、Richardson(理查森)加速技術、有限差分法、有限元法、FFT(快速Fourier(傅里葉)變換)、線性規劃問題的單純形法、MonteCarlo(蒙特卡羅)法、擬Newton法、預條件共軛梯度法、譜方法、多重網格法、區域分裂法、小波變換、邊界元法、模擬退火、遺傳算法以及正則化技術等 以MonteCarlo法之Metropolis(梅特羅波利斯)算法、線性規劃之單純性法、迭代算法之Krylov(克雷洛夫)子空間法、矩陣系列分解法、Fortran優化編譯、特徵值問題的QR算法、快速搜索算法、快速傅里葉變換(FFT)、整數相關問題檢測法(不定方程整數解判斷)、快速多極(multipole)算法等為代表的先進的計算方法極大地推動了現代
科學與技術的進步與發展
自計算機誕生以來,數值計算便與計算機科學緊密結合,並行計算、分布式計算等新理論和新方法不斷出現,數值計算的內涵不斷豐富,計算物理、計算化學、計算生物學、計算地質學等學科分支快速湧現,以數值計算為基礎的計算數學也成為當代數學領域*具活力的交叉學科之一 目前,以數值計算作為主要內容的科學計算,已經成為與科學理論研究和科學實驗具有平行地位的推動現代科學發展的三大主要手段之一,這三種手段之間聯繫緊密、相互促進、相互*立、缺一不可
當人們希望利用計算機更加快速地解決實際問題時,*先需要建立符合實際的數學模型,針對模型還必須設計出符合計算機特性的高效、高精度、數值穩定的數值計算方法,只有這樣才能保證在計算機上計算出可信、有價值的數值結果來 用計算機解決科學計算問題的基本流程如圖1 1所示
從圖1 1可以看出,數值計算方法是聯繫數學科學與計算機科學的橋樑與紐帶,它既有科學理論的嚴謹性和抽象性,同時又可以將之看成數學模型在計算機上實現的一種”工具”,從而具有實驗性和實踐性的技術特徵 因此,數值計算方法屬_xFFFF_理論性和實踐性都很強的學科領域
數值計算的理論與方法的發展既與數學理論的發展與進步密切相關,又與計算機科學的發展相輔相成、相互促進 隨著計算機科學與技術的不斷進步與發展,數值計算方法的內容不斷發展、逐漸豐富,許多新的計算理念、新理論與新方法不斷湧現 例如,受實際問題需求的驅動,計算機需要實時求解的問題規模急劇增加,從而催生出諸如”天河系列”等具有高性能與高效能的分布式超級並行計算機系統,在此情形下數值算法的設計不僅需要考慮高並行度,還需要根據超級計算機的特點研究數據間的極小通信以及低存儲的理論與方法,這些又催生了特定計算平臺下數值計算方法等新的學科內容
我們知道,在現代數學理論的框架下,從實際問題中抽象而建立的數學模型,主要通過微分方程、優化、線性與非線性系統、統計等來描述 本書將針對上述數學問題,介紹相關的數值算法的設計思想與算法性能分析等內容 在算法設計環節 重點從高效與高精度等方面進行考慮,而算法性能分析則主要分析算法的數值穩定性 另外,對於迭代算法還必須考察其收斂性 其中高效主要指算法具有
算術運算和存儲的低複雜度,對於並行計算機系統,還要考慮使得計算過程中各個CPU或GPU之間的通信時間*少 算法的精度問題主要是由計算機系統中的有限字長引起的,同一個數學模型,算法的不同有可能導致不同的數值精度,相互之間的精度有時會相差甚遠,會出現所謂的”數學上等價而計算結果不等效”的問題 另一方面,計算機在計算過程中存在舍入誤差,如果使用不合適的算法,會導致計算結果極度不穩定 因此,針對不同的問題,設計合適的數值算法就成為數值計算方法課程中非常重要的內容
本書需要高等數學、線性代數、常微分方程、優化以及一門計算機語言等預備知識 為便於大多數讀者