《计算机常用算法 第2版》求取 ⇩

目 录1

第1章算法及其基本设计方法1

1.1算法的基本概念1

1.1.1算法的一般特征1

1.1.2数值型算法的特点3

1.2算法描述语言5

11.7.1托伯利兹矩阵快速求逆的特兰持算法 317

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