计算机常用算法PDF电子书下载

前言页 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