研究生课程 · 高等数值分析
高等数值分析
本科数值分析教"怎么算"，高等数值分析回答"为什么这样算、什么时候会坏"：SVD 揭示矩阵的几何本质，FFT 把 O(n²) 变 O(n log n)，条件数预言一切线性代数算法的命运上限。
1 函数逼近与 Chebyshev 多项式
概念最佳一致逼近与最小偏差
两种"最佳"：一致逼近（min max|f−p|，切比雪夫）vs 平方逼近（min ∫|f−p|²，最小二乘/勒让德）。
Chebyshev 多项式 Tₙ(x) = cos(n·arccos x)：|Tₙ| ≤ 1 且在 [−1,1] 上等幅振荡 n+1 次——"偏差最均匀"。
等波纹定理（Chebyshev 交替）：p* 是最佳一致逼近 ⇔ 误差函数在 n+2 个点达到 ±max‖·‖∞ 交替。
插值节点取 Chebysvev 点 cos((2k+1)π/(2n+2)) 使 ω(x) = Π(x−xᵢ) 最小——本科"龙格现象"实验室的正解。
Chebyshev 多项式 Tₙ(x) = cos(n·arccos x)：|Tₙ| ≤ 1 且在 [−1,1] 上等幅振荡 n+1 次——"偏差最均匀"。
等波纹定理（Chebyshev 交替）：p* 是最佳一致逼近 ⇔ 误差函数在 n+2 个点达到 ±max‖·‖∞ 交替。
插值节点取 Chebysvev 点 cos((2k+1)π/(2n+2)) 使 ω(x) = Π(x−xᵢ) 最小——本科"龙格现象"实验室的正解。
2 SVD 与低秩近似
定理A = UΣVᵀ——矩阵的"骨架透视"
任意 A ∈ R^{m×n} 可分解 A = UΣVᵀ = Σᵢ σᵢuᵢvᵢᵀ（σ₁ ≥ σ₂ ≥ … ≥ 0）。
Eckart-Young 定理：最好的秩 k 近似就是 截断 SVD：Aₖ = Σ₁ᵏ σᵢuᵢvᵢᵀ，且 ‖A − Aₖ‖₂ = σₖ₊₁、F 范数意义下也最优。
应用：主成分分析（PCA）、图像压缩、推荐系统（Netflix Prize 的主力）、数据去噪、潜在语义分析。
Eckart-Young 定理：最好的秩 k 近似就是 截断 SVD：Aₖ = Σ₁ᵏ σᵢuᵢvᵢᵀ，且 ‖A − Aₖ‖₂ = σₖ₊₁、F 范数意义下也最优。
应用：主成分分析（PCA）、图像压缩、推荐系统（Netflix Prize 的主力）、数据去噪、潜在语义分析。
随堂检测SVD
3 特征值算法（幂法与 QR）
概念从单根到全谱
幂法：vₖ₊₁ = Avₖ/‖Avₖ‖ → λ₁ 的特征向量（|λ₁|>|λ₂|）；收敛率 |λ₂/λ₁|。反幂法+位移 = 求指定点附近特征值（特征值精修）。
QR 算法：Aₖ = QₖRₖ，Aₖ₊₁ = RₖQₖ。相似变换不断迭代，Aₖ → 上三角（特征值在对角线上）。加位移（Wilkinson）后收敛极快——LAPACK 求全部特征值的工业标准，复杂度 O(n³)。
与 SVD 的关系：对 AᵀA 用幂法即得右奇异向量（上方实验室的原理）。
QR 算法：Aₖ = QₖRₖ，Aₖ₊₁ = RₖQₖ。相似变换不断迭代，Aₖ → 上三角（特征值在对角线上）。加位移（Wilkinson）后收敛极快——LAPACK 求全部特征值的工业标准，复杂度 O(n³)。
与 SVD 的关系：对 AᵀA 用幂法即得右奇异向量（上方实验室的原理）。
4 FFT 与谱分析
定理DFT 与蝶形加速
DFT：Xₖ = Σⱼ xⱼe^{−2πijk/N}，直接算 O(N²)。FFT（Cooley-Tukey）：按奇偶拆分，T(N) = 2T(N/2) + O(N) ⇒ O(N log N)。
N = 10⁶：O(N²) ≈ 10¹² 次不可行，FFT ≈ 2×10⁷ 次瞬间完成——"改变世界的算法"之一。
谱定理（采样）：时域有限长的信号频谱是 sinc 型；采样定理：采样率 > 2×最高频率可完全恢复（Nyquist）。
N = 10⁶：O(N²) ≈ 10¹² 次不可行，FFT ≈ 2×10⁷ 次瞬间完成——"改变世界的算法"之一。
谱定理（采样）：时域有限长的信号频谱是 sinc 型；采样定理：采样率 > 2×最高频率可完全恢复（Nyquist）。
5 偏微分方程数值解
概念差分格式、收敛与稳定性
五点差分（泊松方程 −∇²u = f）：(4uᵢⱼ − uᵢ₋₁ⱼ − uᵢ₊₁ⱼ − uᵢⱼ₋₁ − uᵢⱼ₊₁)/h² = fᵢⱼ，离散误差 O(h²)。
得到大型稀疏对称正定方程组：直接法 O(n⁶) 不可行 ⇒ 迭代法（Jacobi / Gauss-Seidel / SOR / 共轭梯度）。
抛物方程（热传导）显式格式稳定性：CFL 条件 μ = Δt/Δx² ≤ ½，否则数值振荡爆炸（与本科 ODE 稳定性一脉相承）。
得到大型稀疏对称正定方程组：直接法 O(n⁶) 不可行 ⇒ 迭代法（Jacobi / Gauss-Seidel / SOR / 共轭梯度）。
抛物方程（热传导）显式格式稳定性：CFL 条件 μ = Δt/Δx² ≤ ½，否则数值振荡爆炸（与本科 ODE 稳定性一脉相承）。
6 数值稳定性与条件数
定理误差放大器
条件数：κ(A) = ‖A‖·‖A⁻¹‖（≥1）。解线性方程组的误差下界：
‖Δx‖/‖x‖ ≤ κ(A)·(‖Δb‖/‖b‖ + ‖ΔA‖/‖A‖)
κ ~ 10ᵏ 意味着输入的相对误差可能被放大 10ᵏ 倍——病态问题与算法无关，数据本身就危险。
稳定性 vs 条件数：问题是"病态"（κ 大）还是算法"不稳定"（把好的问题算坏）要分开。向后稳定算法（列主元高斯）的误差 ≈ 问题条件数决定的下界。
‖Δx‖/‖x‖ ≤ κ(A)·(‖Δb‖/‖b‖ + ‖ΔA‖/‖A‖)
κ ~ 10ᵏ 意味着输入的相对误差可能被放大 10ᵏ 倍——病态问题与算法无关，数据本身就危险。
稳定性 vs 条件数：问题是"病态"（κ 大）还是算法"不稳定"（把好的问题算坏）要分开。向后稳定算法（列主元高斯）的误差 ≈ 问题条件数决定的下界。