这篇笔记在做什么
这不是逐页摘要，也不是把 889 页讲义压缩成一个“目录翻译”。
这篇笔记只做四件事：
- 说明这份讲义到底在训练什么能力。
- 把 12 章内容整理成几条可复用的主线。
- 提炼每章最值得记住的算法、对象和方法关系。
- 给出一条适合自学和复习的阅读路线。
严格说，这份 PDF 带有很强的课程讲义气质，组织方式更接近“工具箱展开 + 例子穿插”；也正因为这样，它很适合用来搭建“科学计算工具箱”的全局视角。
书籍定位
| 项目 | 内容 |
|---|---|
| 资料名称 | Numerical Methods for Computational Science and Engineering |
| 课程来源 | ETH Zurich, Numerical Methods for CSE |
| 主讲人 | Prof. Ralf Hiptmair |
| 其他贡献者 | Prof. P. Arbenz, Dr. V. Gradinaru |
| 版本信息 | Autumn Term 2025, lecture document |
| 资料形态 | 课程讲义，约 889 页 |
| 目标读者 | 计算科学、计算机科学、工程方向本科高年级/研究生 |
| 先修要求 | 线性代数、微积分、基础编程 |
| 明确侧重点 | 算法思想、计算代价、稳定实现、数值实验 |
| 明确弱化内容 | 纯理论证明、HPC 细节、硬件级优化 |
这份讲义的定位非常明确：
它一方面梳理数值分析的基本对象，另一方面把重点放在真实计算问题中的问题识别、算法选择、代价估算、误差判断与可靠实现上。
因此，它从一开始就把重点放在三件事上：
- 算法本身
- 实现方式
- 数值结果解释
先给结论：这份讲义真正的组织方式
如果只用一句话概括，这份讲义的真正结构是：
线性代数基础设施 -> 数据表示与逼近 -> 非线性迭代 -> 大规模迭代线性代数 -> 常微分方程时间推进
它不是一本“从第 1 章顺理成章推到第 12 章”的教材。
更准确地说，它是一组彼此有依赖关系的工具模块：
- 有些模块负责表示对象，比如矩阵、基函数、插值多项式、样条、傅里叶基。
- 有些模块负责求解方程，比如 LU、QR、SVD、Newton、CG。
- 有些模块负责控制误差，比如稳定性分析、条件数、Chebyshev 节点、自适应步长、预条件。
- 有些模块负责把问题规模做大也还能算，比如稀疏矩阵、Krylov 子空间、FFT。
全书真正持续起作用的是一组判断标准，它们和具体算法一起构成这本书的核心骨架：
- 这个问题应该表示成什么数学对象？
- 该用直接法还是迭代法？
- 误差来自建模、离散还是舍入？
- 算法复杂度是多少？
- 算法在浮点环境下是否稳定？
一页式知识树
Numerical Methods for Computational Science and Engineering
├── 0. 导论与准备
│ ├── 课程目标、主题依赖、相关应用
│ ├── C++ 基础、模板、lambda、Eigen 使用前提
│ └── 复数、三角函数、线代与分析预备知识
├── 1. 矩阵与向量计算基础
│ ├── 矩阵类别、存储格式、BLAS
│ ├── 复杂度估算
│ └── 机器数、舍入、消去、稳定性
├── 2. 线性方程组直接法
│ ├── Gaussian elimination
│ ├── LU 分解与 pivoting
│ ├── 稀疏矩阵与结构利用
│ └── 无主元稳定消去的特殊情形
├── 3. 线性最小二乘
│ ├── normal equations
│ ├── QR 分解
│ ├── SVD
│ ├── PCA / 低秩逼近
│ └── total / constrained least squares
├── 4. 滤波与频域方法
│ ├── 卷积
│ ├── DFT / FFT
│ ├── 正弦余弦变换
│ └── Toeplitz 与 Levinson
├── 5. 插值与数据拟合
│ ├── 多项式插值
│ ├── 形状保持插值
│ ├── 样条
│ ├── Bezier / spline curves
│ └── 三角插值与最小二乘拟合
├── 6. 函数逼近
│ ├── 全局多项式逼近
│ ├── Chebyshev 节点与误差
│ ├── L2 / L∞ 最佳逼近
│ └── 分片多项式逼近
├── 7. 数值积分
│ ├── Newton-Cotes / 多项式求积
│ ├── Gauss quadrature
│ ├── composite quadrature
│ └── adaptive quadrature
├── 8. 非线性方程与非线性最小二乘
│ ├── fixed-point iteration
│ ├── bisection / Newton / secant
│ ├── Newton in R^n
│ ├── quasi-Newton
│ └── Gauss-Newton / Levenberg-Marquardt
├── 9. 特征值与特征向量
│ ├── power / inverse iteration
│ ├── subspace iteration
│ ├── Ritz projection
│ └── Krylov eigensolvers
├── 10. 线性方程组的 Krylov 方法
│ ├── steepest descent
│ ├── conjugate gradient
│ ├── preconditioning
│ └── residual-based methods
├── 11. ODE 初值问题单步法
│ ├── Euler / midpoint
│ ├── general one-step methods
│ ├── explicit Runge-Kutta
│ └── adaptive stepsize control
└── 12. 刚性 ODE
├── model problem analysis
├── stiffness
├── implicit Runge-Kutta
├── semi-implicit methods
└── splitting methods
全书最核心的六条主线
1. 线性代数主线
这是全书最硬的地基。
第 1 章告诉你如何在计算机里表示矩阵和向量，第 2 章讲线性方程组直接法，第 3 章讲最小二乘，第 9 章讲特征值，第 10 章讲 Krylov 方法。它们共同说明一件事：
科学计算里大量问题，最终都要落到矩阵问题上。
所以这条主线同时覆盖：
- 如何表示矩阵；
- 如何估计运算代价；
- 如何利用结构；
- 如何处理病态与舍入误差；
- 如何从小规模直接法过渡到大规模迭代法。
2. 逼近与表示主线
第 5、6、7 章可以连起来回答一个问题：
当函数太复杂、数据太稀疏、积分太难精确算时，应该用什么更简单的对象去替代原问题？
这条线的逻辑是：
- 第 5 章先做“通过已知点重建函数”；
- 第 6 章再做“允许误差的函数逼近”；
- 第 7 章进一步做“用有限个采样点近似积分”。
换句话说，这一组章节是在训练“有限信息近似连续对象”的能力。
3. 频域与结构主线
第 4 章初看会显得有些跳跃，但放回全书结构里就会发现它和前后内容联系很紧。
卷积、DFT、FFT、Toeplitz 矩阵这些内容，本质上都在说明：
有些代价较高的线性运算，在合适表示下可以显著降低计算成本。
这是“利用结构降复杂度”的典型范式。
它和第 1 章的复杂度分析、第 10 章的 Krylov 方法一样，都属于“怎样把计算做得更快”的问题；这里主要依靠的是变换与结构，和迭代路线形成互补。
4. 非线性迭代主线
第 8 章开始，问题从 $Ax=b$ 变成了 $F(x)=0$ 或
$$ \min_x \|F(x)\|_2^2. $$这一章的重要性非常高，因为它把前面线性代数里的工具重新拿回来做局部线性化：
- Newton 法依赖 Jacobian 和线性方程求解；
- Gauss-Newton 把非线性最小二乘局部变成线性最小二乘；
- Levenberg-Marquardt 则在收敛性与稳定性之间做折中。
因此第 8 章和前面的第 2、3 章联系非常紧密，可以看作线性方程组与最小二乘方法在非线性场景下的延伸。
5. 大规模问题主线
第 9、10 章是从“能不能解”转向“规模大到不能用直接法时怎么办”。
这里最关键的思想是 Krylov 子空间：
$$ \mathcal{K}_m(A,r_0)=\operatorname{span}\{r_0,Ar_0,A^2r_0,\dots,A^{m-1}r_0\}. $$这条线处理的问题包括：
- 大规模特征值问题；
- 大规模稀疏线性系统；
- 为什么预条件能显著改善收敛；
- 为什么共轭梯度法对对称正定系统特别重要。
如果你以后做 PDE、反问题、计算电磁学、机器学习中的大规模优化，这部分几乎绕不过去。
6. 时间推进与刚性主线
第 11、12 章把视角切到常微分方程初值问题：
$$ y'(t)=f(t,y(t)). $$这里更值得关注的是两个真正计算上的问题：
- 怎么设计一步一步推进时间的数值格式？
- 为什么有些问题显式方法会失控或者被迫使用极小步长？
于是第 11 章给出 Euler、Runge-Kutta、自适应步长； 第 12 章进一步解释 stiffness，并转向 implicit RK、semi-implicit、splitting 等更稳定的方法。
章节依赖关系怎么理解
如果把全书改从依赖图视角来看，大概是下面这个关系：
Ch.1 矩阵/复杂度/浮点
-> Ch.2 线性方程组直接法
-> Ch.3 线性最小二乘
-> Ch.4 FFT / Toeplitz
-> Ch.9 特征值
-> Ch.10 Krylov 线性求解
Ch.2 线性方程组
-> Ch.8 Newton / quasi-Newton 中的线性化求解
-> Ch.10 大规模线性迭代
Ch.3 最小二乘
-> Ch.8.7 非线性最小二乘
Ch.5 插值
-> Ch.6 函数逼近
-> Ch.7 数值积分
Ch.6 逼近
-> Ch.7 高质量求积规则
Ch.11 单步法
-> Ch.12 刚性 ODE
其中最重要的三条依赖是：
- Ch.1 是底层公共基础设施。
- Ch.2 + Ch.3 是非线性算法的线性内核。
- Ch.11 是 Ch.12 的前置语法。
每一章最值得记住的内容
Ch.0 导论与工具
这一章真正值得抓的是它明确给出的课程方法论：
- 数值方法是一组面向目标的问题求解工具；
- 实现语言强调 C++ 和 Eigen；
- 课程非常重视数值实验；
- 不追求统一大理论，追求“知道何时该拿什么工具”。
这一章还提前补了模板、lambda、向量类、复数等 C++ 内容，说明讲义默认你不仅要“懂方法”，还要“能编码”。
Ch.1 Computing with Matrices and Vectors
这是计算基础设施章。
最值得记住的是四个关键词：
- 矩阵类别与存储；
- BLAS 级操作；
- 复杂度估算；
- 浮点误差与稳定性。
这一章建立了后面所有章节共同的语言：数据结构、操作代价、机器数模型、舍入误差、消去误差、稳定性。
如果这一章没吃透，后面很多“为什么这个算法比那个更可靠”就会变成死记硬背。
Ch.2 Direct Methods for Linear Systems
这一章的中心对象就是
$$ Ax=b. $$真正要掌握的是下面这条完整链路；高斯消元的操作步骤只是其中一个局部环节：
- 线性系统的存在唯一性；
- 条件数与敏感性；
- Gaussian elimination；
- LU 分解；
- pivoting；
- 稀疏矩阵与结构利用。
它教你的核心能力是：对求解器保持结构感，知道结构、代价和稳定性之间如何交换。
Ch.3 Direct Methods for Linear Least Squares
这一章是全书中应用面最广的一章之一。
核心问题变成：
$$ \min_x \|Ax-b\|_2. $$这章最重要的层级关系是：
- normal equations 是最直接但数值上不总是最优的想法；
- QR 分解是更稳健的主力方法；
- SVD 是最强大也最昂贵的通用工具。
而且这章没有停在“求最小二乘解”，还继续走到：
- Moore-Penrose 伪逆；
- 最佳低秩逼近；
- PCA；
- total least squares；
- constrained least squares。
所以第 3 章把“拟合、降维、约束优化”连成了一条线。
Ch.4 Filtering Algorithms
这一章把向量看成离散信号，把矩阵看成滤波器或卷积算子。
真正主线是：
- 卷积是特殊线性映射；
- circulant / Toeplitz 结构让变换法可用；
- DFT 把卷积转成乘法；
- FFT 让这一过程变得高效。
如果用一句话概括，就是：
频域方法的力量，来自“换基以后问题变简单”。
这也是后面很多快速算法共同的思想模板。
Ch.5 Data Interpolation and Data Fitting in 1D
这一章解决的是“数据点之间的空白怎么补”。
它从抽象插值条件
$$ f(t_i)=y_i $$出发，逐步讲到：
- 全局多项式插值；
- Newton 形式与差商；
- 形状保持插值；
- 三次 Hermite；
- cubic spline；
- Bezier 与 spline curve；
- 三角插值；
- 最小二乘拟合。
它最有价值的地方在于让你意识到：
- 插值不是只有 Lagrange 多项式；
- 保形、局部性、可控性往往比“精确穿点”更重要；
- 曲线设计和数值分析的很多工具本质上是同一件事。
Ch.6 Approximation of Functions in 1D
这章是“允许误差”的版本。
它不再要求函数必须穿过所有点，而是追求一个“更简单但足够好”的近似函数。重点包括：
- 全局多项式逼近；
- Chebyshev 插值与误差；
- $L^2$ 最佳逼近；
- 一致最佳逼近；
- 三角多项式逼近；
- 分片多项式逼近。
这章背后的核心问题是：
什么样的近似空间适合这个函数？什么样的误差度量才有意义？
如果你做 surrogate model、reduced model、谱方法、函数学习，这一章非常关键。
Ch.7 Numerical Quadrature
这章把逼近思想进一步推向积分计算：
$$ \int_a^b f(x)\,dx \approx \sum_{i=0}^n w_i f(x_i). $$这一章需要把注意力放在求积规则的设计逻辑上：
- 选哪些节点；
- 设哪些权重；
- 对多大次数的多项式精确；
- 误差如何估计；
- 什么时候该自适应细分。
Gauss quadrature 是这一章的高光，因为它展示了“在相同采样数下做到更高精度”的思想。
Ch.8 Iterative Methods for Non-Linear Systems
这里问题转向
$$ F(x)=0 $$以及非线性最小二乘。
章节内部的升级路线非常清楚：
- 固定点迭代先给最基本的迭代框架；
- 二分法给鲁棒保守路线；
- 标量 Newton 法展示局部高阶收敛；
- $R^n$ 上的 Newton 法把 Jacobian 和线性系统引进来；
- quasi-Newton 讨论如何减少代价；
- Gauss-Newton 和 Levenberg-Marquardt 把非线性拟合接回第 3 章。
这一章最值得记住的是：非线性算法的效率，往往来自高质量局部线性模型。
Ch.9 Computation of Eigenvalues and Eigenvectors
这一章处理
$$ Ax=\lambda x. $$主线从理论简介出发，走向：
- power method；
- inverse iteration；
- preconditioned inverse iteration；
- subspace iteration；
- Ritz projection；
- Krylov eigensolvers。
它传递的核心思想是：特征值问题通常不需要整个谱，只需要感兴趣的那一部分。
因此，“迭代逼近主特征对”比“完全分解”更符合实际大规模计算需求。
Ch.10 Krylov Methods for Linear Systems
这章是大规模线性求解的核心。
对于对称正定系统，它把求解问题转成能量几何和二次型最小化问题，再自然过渡到：
- steepest descent；
- conjugate gradient；
- preconditioning；
- 其他最小残量/短递推方法。
这章最值得反复体会的是：
Krylov 方法一方面表现为迭代公式，另一方面也可以理解为不断把矩阵信息压缩到越来越合适的低维子空间里。
而预条件的本质，则是在进入迭代前先把几何形状“改造得更好”。
Ch.11 Numerical Integration - Single Step Methods
这一章开始正式进入常微分方程时间推进。
逻辑顺序非常标准但也非常重要：
- 先讲 ODE 初值问题与模型；
- 再从显式 Euler、隐式 Euler、隐式 midpoint 入手；
- 再抽象成 general one-step methods；
- 再进入 explicit Runge-Kutta；
- 最后讨论 adaptive stepsize control。
这一章真正训练的是：
- 局部截断误差怎么影响全局误差；
- 稳定性与精度如何平衡；
- 自适应步长为什么是现代积分器的核心能力。
Ch.12 Single-Step Methods for Stiff IVPs
这是第 11 章的升级版，也是很多工程计算里最实际的一章之一。
它要解决的问题是：
某些 ODE 的真实解变化并不快，但显式方法为了稳定却被迫使用极小步长，这时怎么办？
因此它先做 model problem analysis，再引出 stiffness，然后转向：
- implicit Euler；
- collocation；
- implicit Runge-Kutta；
- semi-implicit methods；
- splitting methods。
如果你只记住一个词，那就是 stability region； 如果你只记住一个判断，那就是 “小步长不一定是因为精度要求，而可能是因为稳定性要求”。
这份讲义里反复出现的 10 个关键词
1. 条件数
它衡量问题本身对扰动的敏感程度。条件差，哪怕算法没写错，结果也可能很脆弱。
2. 稳定性
它衡量算法是否会把舍入误差和输入误差放大。条件数是问题属性，稳定性是算法属性，这个区分必须牢牢记住。
3. 正交性
QR、SVD、Ritz、CG 等很多方法之所以可靠，核心都离不开正交性。
4. 稀疏性与结构
Toeplitz、banded、sparse、circulant 都不是“细节”，它们决定了复杂度能不能从不可接受降到可接受。
5. 基与变换
多项式基、傅里叶基、样条基、Krylov 基，都是“换一套表示后问题更容易处理”。
6. 最小二乘
它不仅是拟合工具，也是很多非线性算法、降维方法和统计模型的核心骨架。
7. 迭代
从 fixed-point、Newton 到 CG、RK，自顶向下看，全书几乎一直在讨论“如何把一次难题拆成很多次简单更新”。
8. 预条件
这是大规模数值线性代数最重要的工程思想之一，本质是先改问题的几何结构，再做迭代。
9. 自适应
自适应求积和自适应步长控制都在说明：计算资源应该投到最难的那部分区域。
10. 刚性
刚性提醒我们：数值方法的主要障碍并不总是逼近精度，很多时候是稳定性约束。
如果按能力建设来读，推荐四条路线
路线 A：数据拟合 / 机器学习基础
推荐顺序：
- Ch.1 复杂度、浮点、稳定性
- Ch.3 最小二乘、QR、SVD、PCA
- Ch.5 插值与拟合
- Ch.6 函数逼近
- Ch.7 数值积分
- Ch.8.7 非线性最小二乘
这条路适合想把“数值分析基础”接到拟合、降维、参数估计上的读者。
路线 B：PDE / 科学计算求解器基础
推荐顺序：
- Ch.1
- Ch.2
- Ch.9
- Ch.10
- Ch.11
- Ch.12
这条路线适合想做有限元、计算电磁学、流体、反问题、迭代求解器的人。
路线 C：信号处理 / 频域方法
推荐顺序：
- Ch.1
- Ch.4
- Ch.5.6 三角插值
- Ch.6.5 三角多项式逼近
- Ch.7 数值积分中的频域视角
这条线适合把矩阵观点和信号处理联系起来。
路线 D：完整数值分析入门
推荐顺序：
- Ch.1
- Ch.2
- Ch.3
- Ch.5
- Ch.6
- Ch.7
- Ch.8
- Ch.11
- Ch.12
这条路线最均衡，也最适合把整份讲义当作年度基础训练计划来消化。
最后总结：这份讲义最值得学走的是什么
如果只看目录，这份讲义像 12 门小课的拼盘。
但如果抓住方法论，它真正要训练的是下面这套能力：
- 把实际问题翻译成矩阵、函数、积分、特征值、ODE 等标准计算对象。
- 知道直接法、迭代法、变换法、逼近法分别适合什么规模和结构。
- 在“精度、稳定性、复杂度、实现难度”之间做现实权衡。
- 把数值方法写成可靠代码，并用实验解释结果。
所以这份讲义的价值，既来自各章内容本身，也来自它把“科学计算到底在做什么”这件事组织得足够清楚：
我们不断用更便宜、更稳定、更适合机器的对象，去近似和替代原始数学问题。
这就是整份讲义的共同母题。