目 录 1
第1章算法及其基本设计方法 1
1.1算法的基本概念 1
1.1.1算法的一般特征 1
1.1.2数值型算法的特点 3
1.2算法描述语言 5
11.7.1托伯利兹矩阵快速求逆的特兰持算法 31 7
1.3算法的基本设计方法 7
1.3.1列举法 8
1.3.2归纳法 9
1.3.3递推 10
1.3.4递归 11
1.3.5减半递推 12
1.3.6 回溯法 14
1.3.7数字模拟法 15
1.3.8数值法 17
习题 17
第2章算法分析 19
2.1误差与运算误差分析 19
2.1.1误差的来源 19
2.1.2绝对误差与相对误差 20
2.1.3有效数字与对称舍入 21
2.1.4运算误差分析 23
2.2算法的稳定性 28
2.2.1算法稳定性的基本概念 28
2.2.2三项递推关系的稳定性分析 31
2.3算法的复杂度与最优性 41
2.3.1算法的时间复杂度 41
2.3.2算法的空间复杂度 45
2.3.3算法的最优性 46
2.4算法的自适应 48
2.5.1NP问题的概念 49
2.5NP问题简介 49
2.5.2近似算法与分析 51
习题 57
第3章多项式 59
3.1多项式的基本概念 59
3.2多项式的欧几里得算法 62
3.3多项式的中国剩余定理 65
3.4多项式的快速求值 69
3.4.1 多项式求值的秦九韶方法 69
3.4.2具有系数预处理的多项式求值 71
3.5切比雪夫正交多项式 76
3.5.1正交多项式的概念 76
3.5.2切比雪夫正交多项式 77
3.5.3切比雪夫正交多项式在近似计算中的应用 80
习题 83
第4章矩阵与线性代数方程组 84
4.1线性代数方程组的直接解法 84
4.1.1高斯消去法 84
4.1.2选主元 86
4.1.3约当消去法 87
4.2三对角线线性代数方程组 88
4.2.1三对角矩阵的压缩 89
4.2.2追赶法 89
4.3一般带型线性代数方程组 91
4.3.1带型矩阵的压缩 92
4.3.2列选主元高斯消去法 93
4.4.1简单迭代法 95
4.4线性代数方程组的迭代解法 95
4.4.2赛德尔迭代法 99
4.4.3松弛法 101
4.5共轭梯度法 101
4.5.1对称正定矩阵、向量的正交与共轭变换 102
4.5.2梯度法的基本思想 103
4.5.3共轭梯度法 104
4.6矩阵相乘的快速算法 106
4.6.1维诺格拉德方法 107
4.6.2斯特拉森方法 108
4.7矩阵分解 110
4.7.1矩阵的三角分解 110
4.7.2矩阵的QR分解 115
4.8矩阵求逆 121
4.8.1高斯-约当法 122
4.8.2全主元矩阵求逆 125
习题 127
第5章矩阵特征值的计算 129
5.1计算绝对值最大的特征值的乘幂法 129
5.2求对称矩阵特征值的雅可比方法 132
5.3 QR方法求实矩阵的全部特征值与多项式方程的全部根 137
5.3.1 QR方法的基本思想 137
5.3.2化一般矩阵为上H矩阵 138
5.3.3 QR方法求实矩阵的全部特征值 140
5.3.4 QR方法求多项式方程的根 146
习题 147
6.1非线性方程求根的基本过程 149
第6章非线性方程与方程组 149
6.2简单迭代法 152
6.2.1简单迭代法的迭代过程 152
6.2.2迭代过程的误差与收敛性 153
6.2.3埃特金迭代格式 155
6.3牛顿法与插值法 158
6.3.1牛顿迭代法 158
6.3.2插值法 161
6.4有记忆的单点迭代法 163
6.5对控制迭代过程的讨论 165
6.6应用举例——非线性电路分析 167
6.7非线性方程组 168
6.7.1牛顿法 168
6.7.2拟牛顿法 170
习题 172
第7章插值与逼近 175
7.1插值与逼近的基本概念 175
7.2拉格朗日插值法 177
7.2.1插值问题的提法 177
7.2.2拉格朗日插值多项式 178
7.2.3拉格朗日插值多项式的余项 180
7.2.4插值的逼近性质 181
7.3埃特金逐步插值法 183
7.4埃尔米特插值法 186
7.5样条插值法 187
7.5.1样条函数 187
7.5.2三次样条插值函数的构造 187
7.6离散点连成光滑曲线的阿克玛方法 191
7.7最佳均方逼近 196
7.8最佳一致逼近 198
7.8.1最佳一致逼近多项式 198
7.8.2里米兹算法 200
7.9曲线拟合的最小二乘法 202
7.9.1线性拟合 203
7.9.2一般多项式拟合 205
7.9.3利用正交多项式作最小二乘拟合 207
习题 211
第8章数值微分与数值积分 214
8.1数值微分 214
8.2插值求积公式 215
8.3变步长梯形求积法 218
8.4龙贝格求积法 219
8.5高斯求积法 222
8.5.1代数精度的概念 222
8.5.2高斯求积公式 223
8.6自适应梯形求积法 225
8.7高振荡函数的求积法 227
8.7.1问题的提出 227
8.7.2分部积分法 228
8.7.3利用样条函数计算高振荡积分 230
习题 232
第9章常微分方程初值问题的数值解法 234
9.1数值解法的基本思想与途径 234
9.2欧拉方法 237
9.2.1基本公式 237
9.2.2欧拉公式的几何解释 237
9.2.4改进的欧拉公式 239
9.2.3欧拉方法的误差分析 239
9.3龙格-库塔法 240
9.3.1问题的提出 240
9.3.2龙格-库塔法 241
9.3.3步长的自动选择 244
9.3.4求解一阶微分方程组的龙格-库塔法 245
9.3.5求解高阶微分方程的龙格-库塔法 246
9.4阿当姆斯预报-校正公式 247
9.5哈明方法 250
9.6常微分方程数值解法的相容性、收敛性与稳定性 252
9.6.1相容性 252
9.6.2 收敛性 254
9.6.3稳定性 254
9.7求解刚性方程的吉尔方法 255
习题 263
10.1连分式 265
10.1.1连分式的基本概念 265
第10章连分式及其计算法 265
10.1.2连分式的主要性质 267
10.2函数连分式 270
10.2.1函数连分式的基本概念 270
10.2.2函数连分式的主要性质 271
10.2.3函数连分式的计算 272
10.3变换级数为连分式 272
10.4连分式插值法 274
10.4.1连分式插值的基本概念 274
10.4.2连分式插值函数的构造 274
10.4.3连分式逐步插值 277
10.5非线性方程的连分式解法 278
10.6利用连分式计算一维积分 281
10.7常微分方程初值问题的连分式解法 284
习题 286
第11章数字信号处理中的快速算法 287
11.1数字信号处理 287
11.2快速傅里叶变换 288
11.2.1离散傅里叶变换 288
11.2.2单位根的性质 290
11.2.3快速傅里叶变换（FFT） 291
11.3循环卷积与线性卷积 295
11.3.1循环卷积 295
11.3.2利用FFT计算循环卷积 295
11.3.3线性卷积 297
11.4多项式的快速乘法 298
11.4.1多项式相乘与卷积的关系 298
11.4.2多项式相乘的快速算法 299
11.5短序列卷积的快速算法 301
11.5.1维诺格拉德短序列卷积算法 302
11.5.2短序列线性卷积快速算法的设计 303
11.5.3短序列循环卷积快速算法的设计 306
11.6滤波算法 310
11.6.1逐段卷积 311
11.6.2短序列滤波段快速算法的设计 314
11.6.3滤波段的递归算法 316
11.7解托伯利兹系统的快速算法 317
11.7.2解托伯利兹型线性代数方程组的列文松算法 323
11.8.1 沃什函数 326
11.8快速沃什变换 326
11.8.2快速沃什变换（FWT） 328
习题 330
第12章非数值问题的常用算法 332
12.1数据结构 332
12.1.1线性表 332
12.1.2栈和队列 333
12.1.3二叉树 333
12.2寻找最大项和次大项 335
12.3有序表的对分查找和分块查找 338
12.3.1对分查找法 338
12.3.2分块查找 339
12.4.1二叉排序树及其构造 341
12.4树表的查找 341
12.4.2二叉排序树的查找 342
12.4.3平衡二叉排序树 343
12.5字符串匹配的KMP算法 348
12.5.1字符串匹配的简单算法 348
12.5.2有限自动机 349
12.5.3 KMP算法 350
12.6冒泡排序与快速排序 354
12.6.1 冒泡排序 354
12.6.2快速排序 355
12.7希尔排序 358
12.8堆排序 360
习题 363
参考书目 364
附录短序列循环卷积算法 365