數值分析(第5版)：數值算法分析與高效算法設計（簡體書）

·強調基本原理、基本理論，夯實基本素質
·注重基本方法和技巧，提高應用能力
·闡述嚴謹，脈絡分明，深入淺出
·反覆錘煉，不斷更新，長銷近30年

本書是為理工科院校各專業普遍開設的“數值分析”課程而編寫的教材.其上篇內容包括插值與逼近、數值積分與數值微分、常微分方程與線性方程組的數值解法、矩陣的特徵值與特徵向量計算等.每章附有習題並在書末給出部分答案.
本書下篇（高效算法設計）以講座形式介紹快速算法、並行算法與加速算法方面的幾個典型案例，力圖普及推廣超級計算方面的基礎知識.全書闡述嚴謹，脈絡分明，深入淺出，便於教學.
本書可作為理工科院校應用數學、力學、物理、計算機等專業的教材，也可供從事科學計算的科技工作者參考。

李慶揚，北京大學數學系教授，博士生導師，從事於數值分析的研究。
王能超，教授、博士生導師，我國並行算法設計的先驅者之一，中華數學的弘揚者和踐行者之一。北京大學計算數學專業、復旦大學微分方程專業研究生畢業，師從谷超豪教授。畢業後分配到華中理工大學(現華中科技大學)，先後在計算機系和數學系任教。承擔的主要課題有:國家"863"高技術項目《智能計算機主題:高性能計算中心的快速算法研究》，國防科工委"九五"基金課題《分佈式並行計算機上體可視化算法研究》等。多年來發表學術論文40餘篇，出版學術專著有《數值算法設備》(華中理工大學出版社)，《同步並行算法設計》(科學出版社)等。自1982年以來共培養碩士生43名，博士生3名，其中38人已獲碩士學位。並編寫出版了工程數學、大學本科與研究生三個檔次的數值分析(計算方法)的全國通用教材，其中《數學分析》(合編)與《數值分析簡明教程》均獲國家教委優秀教材二等獎。從事的研究方向為:並行算法與數學軟件、小波分析與信號處理、演化數學方法等

王能超教授是我國並行算法設計的先驅者之一，他在這方面有許多獨特的重要貢獻，其中z主要的是他巧妙地運用二分技術於並行算法設計……。
王能超教授在並行算法設計中之所以能取得巨大進展，主要是由於他對算法設計的基本原理有深刻的研究……。正是由於這些獨到的論點，使他在並行算法設計的研究中取得巨大的、實質性的進展，推動了這門算法設計學的發展。——程民德（1992年）

王能超教授的這本書，是一本富於哲學思想和科學方法論精神的著作。書中對各種各樣的數值算法提出了幾種富於概括性的設計思想和方法原則。這些思想和原則對從事研究和運用計算方法的科技工作者無疑會有深刻的啟迪和指導作用。例如，書中所講述的“縮減技術”、“校正技術”、“鬆弛技術”和快速算法及並行算法設計等，都是極為重要的方法原則，任何人如能精通並靈活運用這些方法原則，不僅能圓滿地解決實際計算問題，而且還可能有所創新，有所發展。
——徐利治（1988年）

本書於1981年由華中科技大學出版社出版，至今已有37年.本書1988年獲國家教委優秀教材二等獎，在國內為許多高校所選用.
今天，數值計算已進入超級計算的新時代，科技革命迅猛發展的新形勢迫切要求普及推廣高性能計算方面的新知識，鑑於這一認識本書推出第5版.
作為高效算法設計的關鍵技術，二分演化技術具有深邃的文化內涵，其設計思想新奇而玄妙，這方面內容可能尚未為人們所熟悉，筆者深信它處於算法設計學的前沿，因此選取快速算法設計、並行算法設計和加速算法設計方面的幾個典型案例，匯集成講座資料作為本書第10～13章，奉獻給立志於從事高性能計算的讀者參考.
本書中的第10～13章（講座資料）由王能超撰寫，錯誤與不當之處請讀者不吝指正.本書的再版，得到華中科技大學出版社的鼎力支持，在此表示衷心的感謝！

上篇數值算法分析
第1章緒論(1)
1.1 數值分析研究的對象與特點(1)
1.2 誤差來源與誤差分析的重要性(2)
1.3 誤差的基本概念(4)
1.3.1 誤差與誤差限(4)
1.3.2 相對誤差與相對誤差限(5)
1.3.3 有效數字(6)
1.3.4 數值運算的誤差估計(7)
1.4 數值運算中誤差分析的方法與原則(9)
1.4.1 要避免除數絕對值遠遠小於被除數絕對值的除法(9)
1.4.2 要避免兩相近數相減(10)
1.4.3 要防止大數“吃掉”小數(11)
1.4.4 注意簡化計算步驟，減少運算次數(11)
小結(12)
習題(12)
第2章插值法(14)
2.1 引言(14)
2.2 Lagrange插值(15)
2.2.1 插值多項式的存在唯一性(15)
2.2.2 線性插值與拋物插值(16)
2.2.3 Lagrange插值多項式(18)
2.2.4 插值餘項(19)
2.3 逐次線性插值法(21)
2.4 差商與Newton插值公式(23)
2.4.1 差商及其性質(23)
2.4.2 Newton插值公式(24)
2.5 差分與等距節點插值公式(26)
2.5.1 差分及其性質(26)
2.5.2 等距節點插值公式(28)
2.6Hermite插值(29)
2.7 分段低次插值(32)
2.7.1 多項式插值的問題(32)
2.7.2 分段線性插值(33)
2.7.3 分段三次Hermite插值(34)
2.8 三次樣條插值(36)
2.8.1 三次樣條函數(36)
2.8.2 三轉角方程(37)
2.8.3 三彎矩方程(39)
2.8.4 計算步驟與例題(40)
2.8.5 三次樣條插值的收斂性(41)
小結(42)
習題(43)
第3章函數逼近與計算(45)
3.1 引言與預備知識(45)
3.1.1 問題的提出(45)
3.1.2 Weierstrass定理(46)
3.1.3 連續函數空間C［a,b］(47)
3.2 最佳一致逼近多項式(47)
3.2.1 最佳一致逼近多項式的存在性(47)
3.2.2 Chebyshev定理(48)
3.2.3 最佳一次逼近多項式(50)
3.3 最佳平方逼近(52)
3.3.1 內積空間(52)
3.3.2 函數的最佳平方逼近(54)
3.4 正交多項式(57)
3.4.1 正交化手續(57)
3.4.2 Legendre多項式(57)
3.4.3 Chebyshev多項式(60)
3.4.4 其他常用的正交多項式(62)
3.5 函數按正交多項式展開(63)
3.6 曲線擬合的最小二乘法(65)
3.6.1 一般的最小二乘逼近(65)
3.6.2 用正交函數作最小二乘擬合(69)
3.6.3 多元最小二乘擬合(71)
3.7 Fourier逼近與快速Fourier變換(71)
3.7.1 最佳平方三角逼近與三角插值(71)
3.7.2 快速Fourier變換(74)
小結(77)
習題(77)
第4章數值積分與數值微分(80)
4.1 引言(80)
4.1.1 數值求積的基本思想(80)
4.1.2 代數精度的概念(81)
4.1.3 插值型的求積公式(82)
4.2 Newton-Cotes公式(82)
4.2.1 Cotes係數(82)
4.2.2 偶階求積公式的代數精度(84)
4.2.3 幾種低階求積公式的餘項(85)
4.2.4 复化求積法及其收斂性(86)
4.3 Romberg算法(88)
4.3.1 梯形法的遞推化(88)
4.3.2 Romberg公式(89)
4.3.3 Richardson外推加速法(91)
4.3.4 梯形法的餘項展開式(92)
4.4 Gauss公式(93)
4.4.1 Gauss點(94)
4.4.2 GaussLegendre公式(95)
4.4.3 Gauss公式的餘項(96)
4.4.4 Gauss公式的穩定性(96)
4.4.5 帶權的Gauss公式(97)
4.5 數值微分(99)
4.5.1 中點方法(99)
4.5.2 插值型的求導公式(100)
4.5.3 實用的五點公式(102)
4.5.4 樣條求導(103)
小結(104)
習題(104)
第5章常微分方程數值解法(106)
5.1 引言(106)
5.2 Euler方法(106)
5.2.1 Euler格式(106)
5.2.2 後退的Euler格式(108)
5.2.3 梯形格式(109)
5.2.4 改進的Euler格式(110)
5.2.5 Euler兩步格式(111)
5.3 RungeKutta方法(113)
5.3.1 Taylor級數法(113)
5.3.2 RungeKutta方法的基本思想(114)
5.3.3 二階RungeKutta方法(115)
5.3.4 三階RungeKutta方法(116)
5.3.5 四階RungeKutta方法(118)
5.3.6 變步長的RungeKutta方法(119)
5.4 單步法的收斂性和穩定性(120)
5.4.1 單步法的收斂性(120)
5.4.2 單步法的穩定性(122)
5.5 線性多步法(124)
5.5.1 基於數值積分的構造方法(124)
5.5.2 Adams顯式格式(125)
5.5.3 Adams隱式格式(126)
5.5.4 Adams預測校正系統(127)
5.5.5 基於Taylor展開的構造方法(128)
5.5.6 Milne格式(130)
5.5.7 Hamming格式(131)
5.6 方程組與高階方程的情形(132)
5.6.1 一階方程組(132)
5.6.2 化高階方程組為一階方程組(133)
5.7 邊值問題的數值解法(134)
5.7.1 試射法(135)
5.7.2 差分方程的建立(135)
5.7.3 差分問題的可解性(137)
5.7.4 差分方法的收斂性(138)
小結(140)
習題(140)
第6章方程求根(142)
6.1 根的搜索(142)
6.1.1 逐步搜索法(142)
6.1.2 二分法(142)
6.2 迭代法(144)
6.2.1 迭代過程的收斂性(144)
6.2.2 迭代公式的加工(147)
6.3 Newton法(149)
6.3.1 Newton公式(149)
6.3.2 Newton法的幾何解釋(150)
6.3.3 Newton法的局部收斂性(151)
6.3.4 Newton法應用舉例(152)
6.3.5 Newton下山法(153)
6.4 弦截法與拋物線法(154)
6.4.1 弦截法(155)
6.4.2 拋物線法(156)
6.5 代數方程求根(158)
6.5.1 多項式求值的秦九韶算法(158)
6.5.2 代數方程的Newton法(159)
6.5.3 劈因子法(160)
小結(162)
習題(162)
第7章解線性方程組的直接方法(164)
7.1 引言(164)
7.2 Gauss消去法(164)
7.2.1 消元手續(165)
7.2.2 矩陣的三角分解(168)
7.2.3 計算量(170)
7.3 Gauss主元素消去法(171)
7.3.1 完全主元素消去法(172)
7.3.2 列主元素消去法(173)
7.3.3 GaussJordan消去法(175)
7.4 Gauss消去法的變形(178)
7.4.1 直接三角分解法(178)
7.4.2 平方根法(181)
7.4.3 追趕法(184)
7.5 向量和矩陣的範數(186)
7.6 誤差分析(192)
7.6.1 矩陣的條件數(192)
7.6.2 舍入誤差(197)
小結(198)
習題(198)
第8章解線性方程組的迭代法(202)
8.1 引言(202)
8.2 Jacobi迭代法與GaussSeidel迭代法(204)
8.2.1 Jacobi迭代法(204)
8.2.2 GaussSeidel迭代法(205)
8.3 迭代法的收斂性(206)
8.4 解線性方程組的超鬆弛迭代法(213)
小結(217)
習題(217)
第9章矩陣的特徵值與特徵向量計算(220)
9.1 引言(220)
9.2 冪法及反冪法(222)
9.2.1 冪法(222)
9.2.2 加速方法(225)
9.2.3 反冪法(227)
9.3 Householder方法(230)
9.3.1 引言(230)
9.3.2 用正交相似變換約化矩陣(232)
9.4 QR算法(237)
9.4.1 引言(237)
9.4.2 QR算法(239)
9.4.3 帶原點位移的QR方法(242)
小結(246)
習題(246)
下篇高效算法設計
第10章快速算法設計：快速Walsh變換(248)
10.1 美的Walsh函數(248)
10.1.1 微積分的逼近法(248)
10.1.2 Walsh函數的複雜性(249)
10.1.3 Walsh分析的數學美(250)
10.2 Walsh函數代數化(251)
10.2.1 時基上的二分集(251)
10.2.2 Walsh函數的矩陣表示(252)
10.3 Walsh陣的二分演化(252)
10.3.1 矩陣的對稱性複制(253)
10.3.2 Walsh陣的演化生成(253)
10.3.3 Walsh陣的演化機制(254)
10.3.4 Hadamard陣的演化生成(255)
10.4 快速變換FWT(257)
10.4.1 FWT的設計思想(257)
10.4.2 FWT的演化機制(258)
10.4.3 FWT的計算流程(259)
10.4.4 FWT的算法實現(261)
小結(262)
第11章並行算法設計：遞推計算並行化(263)
11.1 什麼是並行計算(263)
11.1.1 一則寓言故事(263)
11.1.2 同步並行算法的設計策略(264)
11.2 疊加計算(265)
11.2.1 倍增技術(265)
11.2.2 二分手續(267)
11.2.3 數列求和的二分法(268)
11.2.4 多項式求值的二分法(269)
11.2.5 二分算法的效能分析(270)
11.2.6 二分算法的基本特徵(271)
11.3 一階線性遞推(272)
11.3.1 相關鏈的二分手續(272)
11.3.2 算式的建立(273)
11.3.3 二分算法的效能分析(275)
11.4 三對角方程組(275)
11.4.1 相關鏈的二分手續(276)
11.4.2 算式的建立(277)
小結(279)
第12章加速算法設計：重差加速技術(281)
12.1 千古疑案(281)
12.1.1 阿基米德的“窮竭法”(281)
12.1.2 祖沖之“綴術”之謎(281)
12.2 神來之筆(282)
12.2.1 數學史上一篇千古奇文(282)
12.2.2 “一飛沖天”的“劉徽神算”(283)
12.3 奇光異彩(284)
12.3.1 劉徽的新視野(285)
12.3.2 偏差比中傳出好“消息”(286)
12.3.3 只要做一次“俯衝”(286)
12.3.4 差之毫釐，失之千里(287)
12.3.5 “綴術”再剖析(288)
12.3.6 平庸的新紀錄(289)
12.4 萬能引擎(291)
12.4.1 逼近加速的重差公設(292)
12.4.2 重差加速法則(292)
12.4.3重差加速的邏輯推理(293)
第13章總覽(294)
13.1 算法重在設計(294)
13.1.1 算法設計關係到科學計算的成敗(294)
13.1.2 算法設計追求簡單與統一(295)
13.2 直接法的縮減技術(295)
13.2.1 數列求和的累加算法(295)
13.2.2 縮減技術的設計機理(296)
13.2.3 多項式求值的秦九韶算法(297)
13.3 迭代法的校正技術(298)
13.3.1 開方算法(298)
13.3.2 校正技術的設計機理(299)
13.4 迭代優化的超鬆弛技術(300)
13.4.1 超鬆弛技術的設計機理(300)
13.4.2 劉徽的“割圓術”(300)
13.5 遞推加速的二分技術(301)
13.5.1 “結繩記數”的快速算法(301)
13.5.2 二分技術的設計機理(302)
小結(303)
部分習題答案(305)
參考文獻(308)