前言页 1
第1章 算法及其基本设计方法 1
1.1 算法的基本概念 1
1.1.1 算法的一般特征 1
1.1.2 数值型算法的特点 3
1.2 算法描述语言 5
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.1 算法的时间复杂度 41
2.3 算法的复杂度与最优性 41
2.3.2 算法的空间复杂度 45
2.3.3 算法的最优性 46
2.4 算法的自适应 48
2.5 NP问题简介 49
2.5.1 NP问题的概念 49
2.5.2 近似算法与分析 51
习题 57
第3章 多项式 59
3.1 多项式的基本概念 59
3.2 多项式的欧几里得算法 62
3.3 多项式的中国剩余定理 65
3.4.1 多项式求值的秦九韶方法 69
3.4 多项式的快速求值 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.2 追赶法 89
4.2.1 三对角矩阵的压缩 89
4.3 一般带型线性代数方程组 91
4.3.1 带型矩阵的压缩 92
4.3.2 列选主元高斯消去法 93
4.4 线性代数方程组的迭代解法 95
4.4.1 简单迭代法 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.1 QR方法的基本思想 137
5.3 QR方法求实矩阵的全部特征值与多项式方程的全部根 137
5.3.2 化一般矩阵为上H矩阵 138
5.3.3 QR方法求实矩阵的全部特征值 140
5.3.4 QR方法求多项式方程的根 146
习题 147
第6章 非线性方程与方程组 149
6.1 非线性方程求根的基本过程 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 牛顿法 169
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.1 问题的提出 227
8.7 高振荡函数的求积法 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.3 欧拉方法的误差分析 239
9.2.4 改进的欧拉公式 239
9.3.1 问题的提出 240
9.3 龙格-库塔法 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.1 多项式相乘与卷积的关系 298
11.4 多项式的快速乘法 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.1 托伯利兹矩阵快速求逆的特兰持算法 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 树表的查找 341
12.4.1 二叉排序树及其构造 341