Numerical analysis

第0章 基础. 1

0.1 多项式计算 1

0.2 二进制数 4

0.2.1 十进制到二进制的转换 5

0.2.2 二进制到十进制的转换 5

0.3 实数的浮点表示 7

0.3.1 浮点格式 7

0.3.2 机器表示 10

0.3.3 浮点数的加法 12

0.4 有效数字的损失 15

0.5 微积分回顾 18

第1章 解方程 22

1.1 对分法 22

1.1.1 根隔离法 22

1.1.2 算法的精度和速度 26

1.2 不动点迭代 28

1.2.1 函数的不动点 28

1.2.2 不动点迭代的几何原理 31

1.2.3 不动点迭代的线性收敛性 32

1.2.4 停止准则 37

.1.3 精度的界限 40

1.3.1 前向误差和后向误差 41

1.3.2 wilkinson 多项式 44

1.3.3 求根的灵敏度 45

1.4 newton 法 49

1.4.1 newton 法的二次收敛性 50

1.4.2 newton 法的线性收敛性 53

1.5 不用导数求根 58

1.5.1 割线法及其变形 58

1.5.2 brent 方法 62

第2章 方程组 67

2.1 高斯消去法 67

2.1.1 基本的高斯消去法 68

2.1.2 运算计数 70

2.2 lu 分解 75

2.2.1 高斯消去法的矩阵形式 75

2.2.2 利用lu 分解的回代过程 78

2.2.3 lu 分解的复杂性 80

2.3 误差的来源 83

2.3.1 误差放大及条件数 83

2.3.2 摆动 89

2.4 pa=lu 分解 92

2.4.1 部分选主元 92

2.4.2 置换矩阵 94

2.4.3 pa=lu 分解 96

2.5 迭代方法 101

2.5.1 jacobi 方法 101

2.5.2 gauss-seidel 方法和sor 104

2.5.3 迭代方法的收敛性 107

2.5.4 稀疏矩阵计算 108

2.6 共轭梯度法 115

2.6.1 正定矩阵 115

2.6.2 共轭梯度法 116

2.7 非线性方程组系统 .120

2.7.1 多变量newton 方法 120

2.7.2 broyden 方法 124

第3章 插值 128

3.1 数据和插值函数 128

3.1.1 lagrange 插值 129

3.1.2 newton 均差 131

3.1.3 经过n 个点的d 次多项式有多少个 135

3.1.4 插值编码 136

3.1.5 用近似多项式表示函数 138

3.2 插值误差 142

3.2.1 插值误差公式 142

3.2.2 newton 形式和误差公式的证明 144

3.2.3 runge 现象 146

3.3 chebyshev 插值 149

3.3.1 chebyshev 定理 149

3.3.2 chebyshev 多项式 151

3.3.3 区间的改变 153

3.4 三次样条 157

3.4.1 样条的性质 158

3.4.2 端点条件 165

3.5 bezier 曲线 170

第4章 最小二乘 179

4.1 最小二乘和正规方程 179

4.1.1 不相容方程组 179

4.1.2 数据拟合模型 184

4.1.3 最小二乘的条件作用 188

4.2 模型综述 192

4.2.1 周期数据 192

4.2.2 数据线性化 195

4.3 qr 分解 202

4.3.1 gram-schmidt 正交化和最小二乘 202

4.3.2 householder 反射 208

4.4 非线性最小二乘 214

4.4.1 gauss-newton方法 214

4.4.2 带非线性系数的模型 217

第5章 数值微分和数值积分 224

5.1 数值微分 224

5.1.1 有限差分公式 224

5.1.2 舍入误差 228

5.1.3 外推 230

5.1.4 符号微分法和符号积分法 232

5.2 数值积分的newton-cotes公式 235

5.2.1 梯形法则 236

5.2.2 simpson 法则 237

5.2.3 复合newton-cotes公式 240

5.2.4 开newton-cotes方法 242

5.3 romberg 积分 245

5.4 自适应求积 249

5.5 gauss 求积 253

第6章 常微分方程 261

6.1 初值问题 261

6.1.1 euler 方法 263

6.1.2 解的存在性、唯一性和连续性 268

6.1.3 一阶线性方程 271

6.2 初值问题解法分析 .273

6.2.1 局部截断误差和整体截断误差 273

6.2.2 显式梯形方法 277

6.2.3 taylor 方法 280

6.3 常微分方程组 282

6.3.1 高阶方程 284

6.3.2 计算机模拟：摆 285

6.3.3 计算机模拟: 轨道力学 289

6.4 runge-kutta 方法及其应用 294

6.4.1 runge-kutta 族 294

6.4.2 计算机模拟：hodgkin-huxley 神经元 297

6.4.3 计算机模拟: lorenz方程 299

6.5 变步长方法 305

6.5.1 嵌入runge-kutta对 305

6.5.2 4/5 阶方法 .307

6.6 隐式方法和刚性方程 312

6.7 多步方法 316

6.7.1 生成多步方法 316

6.7.2 显式多步方法 319

6.7.3 隐式多步方法 322

第7章 边值问题 328

7.1 打靶法 328

7.1.1 边值问题的解 328

7.1.2 打靶法的实现 332

7.2 有限差分方法 .. 337

7.2.1 线性边值问题 337

7.2.2 非线性边值问题 340

7.3 配置法与有限元法 345

7.3.1 配置法 346

7.3.2 有限元和galerkin方法 348

第8章 偏微分方程 355

8.1 抛物型偏微分方程 355

8.1.1 前向差分方法 356

8.1.2 前向差分方法的稳定性分析 360

8.1.3 后向差分方法 362

8.1.4 crank-nicolson方法 364

8.2 双曲型方程 370

8.2.1 波动方程 370

8.2.2 cfl 条件 373

8.3 椭圆型方程 376

8.3.1 椭圆型方程的有限差分方法 377

8.3.2 椭圆型方程的有限元方法 385

第9章 随机数及其应用 397

9.1 随机数 397

9.1.1 伪随机数 398

9.1.2 指数随机数和正态随机数 403

9.2 蒙特卡罗模拟 405

9.2.1 蒙特卡罗估计的幂定律 406

9.2.2 拟随机数 407

9.3 离散布朗运动和连续布朗运动 412

9.3.1 随机游动 412

9.3.2 连续布朗运动 414

9.4 随机微分方程 417

9.4.1 将噪声引入微分方程 417

9.4.2 随机微分方程的数值方法 420

第10章 三角插值和快速fourier变换 431

10.1 fourier 变换 431

10.1.1 复算术 432

10.1.2 离散fourier变换 434

10.1.3 快速fourier变换 436

10.2 三角插值 439

10.2.1 dft 插值定理 439

10.2.2 三角函数的有效求值 443

10.3 fft 和信号处理 447

10.3.1 正交性和插值 447

10.3.2 用三角函数进行最小二乘拟合 449

10.3.3 声音、噪声和过滤 453

第11章 压缩 459

11.1 离散余弦变换 459

11.1.1 一维离散余弦变换 460

11.1.2 dct 和最小二乘逼近 462

11.2 二维dct 和图像压缩 465

11.2.1 二维dct 465

11.2.2 图像压缩 469

11.2.3 量化 471

11.3 hu?man 编码 478

11.3.1 信息论和编码 479

11.3.2 jpeg 格式的hu?man 编码 481

11.4 改进的dct 和音频压缩 485

11.4.1 mdct 485

11.4.2 位的量化 491

第12章 特征值和奇异值 497

12.1 幂迭代方法 497

12.1.1 幂迭代 498

12.1.2 幂迭代的收敛性 500

12.1.3 逆幂迭代 501

12.1.4 rayleigh 商迭代 503

12.2 qr 算法 505

12.2.1 同时迭代 505

12.2.2 实schur 形式和qr算法 509

12.2.3 上hessenberg形式 511

12.3 奇异值分解 519

12.3.1 一般情况下求svd 522

12.3.2 特殊情形：对称矩阵 523

12.4 svd 的应用 525

12.4.1 svd 的性质 525

12.4.2 降维 526

12.4.3 压缩 528

12.4.4 计算svd 529

第13章 最优化 533

13.1 没有导数的无约束最优化 534

13.1.1 黄金分割探索 534

13.1.2 连续抛物线插值法 537

13.1.3 nelder-mead搜索 540

13.2 带导数的无约束最优化 543

13.2.1 牛顿法 543

13.2.2 最速下降法 545

13.2.3 共轭梯度法 546

附录a 矩阵代数 551

附录b matlab 简介 556

参考文献 563

习题选解(图灵网站下载)...