《计算机常用算法》求取 ⇩

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