配套代码:
ode_incremental_stability.py(运行py ode_incremental_stability.py,输出 figs/ 下三张图) 交互演示:web/index.html(双击打开,四个数值演示 + 页内自检) · 文章:文章-连续时间稳定不等于离散稳定.md
一句话:用连续时间动力系统的语言,给离散迭代算法做收敛性与稳定性分析。
它不属于单一学科,而是四块理论在一个问题上的交汇:
| 理论板块 | 在这件事里的角色 | 关键文献 |
|---|---|---|
| 随机逼近 / ODE 方法(ODE method, mean-field / fluid limit) | 把随机迭代的极限写成确定性 ODE,并证明"ODE 稳定 ⟹ 算法收敛" | Ljung (1977) Analysis of recursive stochastic algorithms;Kushner & Clark (1978);Benveniste–Métivier–Priouret (1990);Borkar (2008) Stochastic Approximation: A Dynamical Systems Viewpoint |
| 连续化 / 梯度流(continuous-time embedding, gradient flow) | 确定性优化的算法(GD、momentum、Nesterov、mirror descent)的 ODE 建模与速率分析 | Polyak (1964);Su–Boyd–Candès (2014);Wibisono–Wilson–Jordan (2016) Bregman Lagrangian;Shi et al. (2018) 高分辨率 ODE |
| 数值分析:ODE 数值解 + 绝对稳定性 | 离散算法就是某个积分格式;步长能取多大 = 该格式的绝对稳定域 | Dahlquist;Hairer & Wanner;Lax 等价定理(相容 + 稳定 ⟺ 收敛) |
| 动力系统 / 控制:稳定性判据本身 | Hurwitz、Lyapunov 第二方法、LaSalle 不变集、Hartman–Grobman、中心流形 | Khalil Nonlinear Systems;Sastry Nonlinear Systems |
再加一条主线:多时间尺度 / 奇异摄动(Borkar;Konda–Tsitsiklis 1999),用于 actor-critic、GAN、双线性博弈这类"快的变量 + 慢的变量"的算法。
写是都能写,但要让 ODE 的结论合法地迁移回离散算法,需要 Robbins–Monro / Kushner–Clark 定理的条件:
h(x) = E[H(x, ξ)]良定义且 Lipschitz(噪声关于历史是鞅差);- 步长
Ση_k = ∞,Ση_k² < ∞(衰减步长); - ODE
ẋ = h(x)有紧的渐近稳定吸引集。
缺了 (2),随机迭代只会停在平衡点附近一个 O(√η) 的邻域里而不收敛(见 §5)。缺了 (1),"平均场"就没有定义。
给定增量式算法(迭代 / 在线 / 递归都算):
x_{k+1} = x_k + η_k · H(x_k, ξ_k)
Step 1 — 平均场方向场。 取条件期望,把噪声积掉:
h(x) = E[ H(x, ξ) ]
Step 2 — 时间重标定,取连续极限。 令 t = Σ_{i<k} η_i,把 x_k 看作 x(t) 的分片常数/线性插值。当 η → 0:
ẋ = h(x)
重标定是关键:不除以
η,"离散 ↔ 连续"在时间尺度上就对不上,图上会看到两条曲线斜率差一个η。对二阶方法(momentum)要用t = k√η。
Step 3 — 平衡点。 解 h(x*) = 0。这就是算法的收敛目标。
Step 4 — 线性化 → 局部指数稳定。 令 J = Dh(x*):
ẋ = J·(x - x*) ⟹ 局部指数稳定 ⟺ J 是 Hurwitz(所有特征值实部 < 0)
收敛速率由 max Re λ(J) 决定。判定可以纯代数化:Routh–Hurwitz 判据(符号计算)或直接数值求特征值。
Step 5 — Lyapunov 证书(全局 / 非线性)。 找 V(x) ≥ 0, V(x*)=0,使 dV/dt = ⟨∇V, h(x)⟩ < 0。常用模板:
- 凸优化 + 梯度流:
V = f - f*,则dV/dt = -‖∇f‖²; - 线性系统:
V = xᵀPx,P解 Lyapunov 方程JᵀP + PJ = -Q(代码里用scipy.linalg.solve_lyapunov); - 非严格下降时用 LaSalle 不变集原理收尾。
Step 6 — 离散 ↔ 连续桥接(最容易漏的一步)。 线性化后的迭代是
x_{k+1} = (I + η J) x_k ← 这正是一步前向 Euler
所以步长上界来自前向 Euler 的绝对稳定域(复平面上以 −1 为圆心、半径 1 的圆盘):
稳定 ⟺ |1 + η λ_i| < 1 ∀i ⟺ 0 < η < min_i 2·(−Re λ_i)/|λ_i|²
实正特征值的情形: η_max = 2 / λ_max
这一条解释了整件事的核心张力:ODE 的特征值只要落在左半平面就稳定,而离散算法要求 ηλ 落在一个有限圆盘里。 所以"连续时间稳定"是"离散时间稳定"的必要条件,不是充分条件;中间那条缝就是算法不稳定的来源。
Step 7 — 噪声的账。 噪声不移动 h 的零点,所以不改变 ODE 的平衡点,但它决定稳态方差:
- 常数步长
η:渐近协方差∝ η,误差停在O(√η)邻域("噪声地板"); - 衰减步长
Ση=∞, Ση²<∞:几乎必然收敛到点; - 用 Benveniste 的平均化 (averaging) 方法可以把
√η级别的波动也描述出来。
| 算法 | 离散更新 | 连续 ODE | 稳定性 / 步长条件 |
|---|---|---|---|
| Richardson / 二次 GD | x ← x − η(Ax − b) |
ẋ = −A(x − x*) |
λ(A)>0;η < 2/λ_max |
| 梯度下降 | x ← x − η∇f |
ẋ = −∇f |
凸 + L-光滑;η < 2/L |
| Heavy-ball | x ← x − η∇f + β(x−x_{k−1}) |
ẍ + ((1−β)/√η)ẋ + ∇f = 0 |
ODE:β<1 即稳定;离散另需 ηλ_max < 2(1+β) |
| Nesterov | 见 Su–Boyd–Candès | ẍ + (3/t)ẋ + ∇f = 0 |
连续速率 O(1/t²) ↔ 离散 O(1/k²) |
| LMS / SA | θ ← θ + ηφ(y − φᵀθ) |
θ̇ = Σ(θ* − θ), Σ = E[φφᵀ] |
持续激励 Σ ≻ 0 |
| 共识 / 分布式平均 | x ← Wx |
ẋ = −(I−W)x |
图 Laplacian 的谱隙决定速率 |
| Kaczmarz / 增量梯度 | 逐样本投影 | 微分包含 / 切换系统 | 用单调算子语言更自然 |
多时间尺度(actor-critic、GAN、双线性博弈):
θ̇ = h(θ, w) (快)
ε ẇ = g(θ, w) (慢,ε → 0)
先冻结 w 让 θ 收敛到"快流形",再在慢流形上分析约化 ODE。如果两个尺度靠得不够近,线性化会出现纯虚特征值(极限环 / cycling),此时线性稳定性分析失效,需要中心流形或平均化方法。
import sympy as sp
# 1. 求 h(x) = E[H(x, xi)]
# 2. J = h.jacobian(x) 代入 x*
# 3. 用 Routh-Hurwitz 或直接特征值判断 Hurwitz不确定的时候用 Lyapunov 方程数值验证谱条件,比手算特征值鲁棒(尤其非对称矩阵)。
- 实现离散迭代
f(x); - 写出同一个
h,用solve_ivp(RK45)积分 ODE; - 把离散迭代按
t = kη与 ODE 解画在同一张图上 → η→0 必须重合(图 A); - 扫
η(或(η, β)平面),实测发散边界 vs 理论η_max(图 B); - 实测每步增长比
‖e_{k+1}‖/‖e_k‖vs 谱半径ρ(I+ηJ); - 扫
η看稳态 MSD 是否∝ η(图 C1),对比常数步长/衰减步长(图 C2)。
- 连续稳定 ≠ 离散稳定——最重要的一条。一定要把
η_max算出来。 - 时间不重标定会导致 ODE 和离散轨迹看起来"不一致",其实只是时间尺度差了
η或√η。 - 常数步长永远不收敛到点,只到
O(√η)邻域;论文里说"收敛"默认指衰减步长或误差界。 - 非正规矩阵的瞬态增长:
ρ(M) < 1不保证误差单调下降,可能有巨大的瞬时放大(伪谱/数值域才是对的工具)。在两步法(momentum)里尤其常见。 - 非光滑(ReLU、L1、投影、clipping):ODE 变成微分包含
ẋ ∈ H(x),要用 Clarke 广义梯度、单调算子/预解式、Moreau 包络。分裂算法(ADMM、Douglas–Rachford)在这套语言下最自然。 - 两时间尺度不分离 → 纯虚特征值 → 极限环,线性化判据失效。
- 步长上界的来源要说清:它来自积分格式的绝对稳定域,不是来自 ODE。换成隐式/半隐式格式(proximal、后向 Euler)可以得到无条件稳定,代价是每步要解一个子问题。
| 检验项 | 理论值 | 脚本输出 |
|---|---|---|
A:η_max |
2/λ_max = 0.5 |
数值谱半径二分 = 0.50000000,相对误差 0 |
| A:衰减率 | ρ(I−ηA) = 0.975 / 0.925 / 0.875 / 0.8 |
仿真的每步增长比逐位吻合(8 位小数) |
| A:边界两侧 | 0.99η_max 收敛 / 1.01η_max 发散 |
3.1e-18 vs 1.7e+17 |
B:η_max(β) |
2(1+β)/λ_max |
β = 0/0.2/0.5/0.8/0.9 全部吻合,相对误差 ≤ 1.1e-15 |
| B:几何增长率 | ρ = √β = 0.70710678 |
实测 0.70692 / 0.70723 / 0.70713(误差 < 3e-4,有限窗口残差) |
| B:GAP | ODE 阻尼 a = 0.333 > 0 |
离散在第 27 步越过 1e12,爆炸 |
| C:均值误差 | 前向 Euler 全局误差 O(η) |
η = 0.05/0.01/0.002 → 2.37e-2 / 4.63e-3 / 9.22e-4(比值恒定 ≈0.46) |
| C:噪声地板 | 精确稳态协方差 vs 蒙特卡洛 | η = 0.002…0.128 七点全部吻合(最差 0.5%);小 η 对数斜率 1.02 |
| C:首阶渐近 | tr V ≈ ησ²n/2 |
小 η 处与精确解重合;η = 0.128 时精确值高出 2.5 倍(高阶修正) |
附带发现(脚本注释里保留了这段): 稳态协方差方程
ΣV + VΣ = η[Σ·tr(ΣV) + 2ΣVΣ + σ²Σ] 中的 Σ·tr(ΣV) 是一个非正规的秩一项。
用最自然的定点迭代 V ← V − η(...) 求解,它能收敛到正确的不动点(tr V = 0.19966),
却会把 1e-16 的浮点舍入逐步放大,几千步后涨到 1e140。
改成直接在对称矩阵空间组装线性方程组求解后完全稳定 —— 正是上面第 4 条坑的真实实例。
ODE 视角把"算法"拆成一个向量场 + 一个积分格式,于是分析被干净地因式分解:
稳定性 = Hurwitz(h 的 Jacobian) ∩ 格式的绝对稳定域(η)
收敛速率 = 连续时间的谱/能量衰减 × 离散修正因子
稳态误差 = O(η) 的噪声地板 (只取决于 η 和噪声,与格式无关)
这个拆分才是真正的价值:它把"问题本身有多难"和"离散化带来的技术性限制"分开了。 以往的收敛性证明把这两件事搅在一起,导致换一个步长策略、换一个噪声假设就得重证一遍。 分开之后,确定性部分是共用的,只有噪声项需要重做。
① 定量回答"步长能取多大"。
工程上调 learning rate 靠扫参;ODE 分析给解析式。我们的图 B 就是一条可直接使用的设计规则:
η_max = 2(1+β)/λ_max —— 动量 β 把一个"免费"的步长上界线性放大 (1+β) 倍,
这正是加速的来源,代价是进入欠阻尼区开始振荡(复特征值)。
② 把"病态"和"刚性"统一成一张图。
λ_max/λ_min = κ 的病态问题 ⟺ 刚性 ODE。步长被 2/λ_max 卡住,迭代次数被 κ 卡住。
于是只有两条出路,且都变得显然:
- 换变量 → 预条件 / 自然梯度 / 白化(改的是 Riemman 度量,不是算法);
- 换 ODE → 加动量、加高阶项、Nesterov 加速(改的是向量场本身)。
③ 反向生成算法,而不只是分析算法。 这是最有生产力的一条:先写一个你想要的 ODE,再挑一个积分格式,离散化就得到新算法。
- Nesterov 加速 ←
ẍ + (3/t)ẋ + ∇f = 0的一个离散化(Su–Boyd–Candès); - proximal point / ADMM 的无条件稳定 ← 后向 Euler(隐式格式天然 A-稳定);
- mirror descent ← Bregman 散度诱导的黎曼度量下的梯度流;
- Bregman Lagrangian ← 直接在连续时间构造满足变分法的 Lagrangian。 想要保能量的算法,就用辛格式;想要对刚性稳健,就用隐式格式。数值 ODE 一百年的工具箱可以整箱搬过来。
④ 刻画"不收敛但有用"的现象。 GAN 的 cycling、双线性博弈、RL 的策略振荡,在"收敛性"框架下是失败;在动力系统框架下是 极限环 / Hopf 分岔,可以被有意义地刻画(周期轨道、Poincaré–Bendixson、平均化)。 调大 learning rate 导致训练从收敛变震荡,就是一个 Hopf 分岔 —— 这是"训练不稳定"的机制解释, 而不是一句"发散"。
⑤ 把局部结论推到全局 / 给出下界。
Lyapunov 函数就是物理里的能量,dE/dt = −a‖ẋ‖² ≤ 0 一句话给出全局稳定性(我们的例子 B);
反过来,能量恒等式也用来证明速率下界("任何一阶方法都做不到比 O(1/k²) 更快的"这类结论)。
⑥ 让一个领域的技巧可以直接搬到另一个领域。 GD、momentum、Adam、mirror descent、自然梯度、LMS/RLS、Kalman、TD/actor-critic、 共识算法、ADMM、GAN 训练 —— 在 ODE 语言下都是"向量场 + 格式"的不同选择。 学一次分析套路,可以横跨优化、控制、信号处理、强化学习、博弈论。
诚实的边界:
| 情形 | 问题 |
|---|---|
| 需要方差的精细分布(置信区间、中心极限定理、有限样本界) | ODE 只给均值场,要用扩散逼近 / SDE(dX = h dt + √η σ dW)而不只是 ODE |
步长很大(ηλ_max 接近 2) |
ODE 逼近在这一区间恰恰失效,而实际调参常落在这里;此时 ODE 只给"趋势正确、细节失真" |
| 非光滑 + 非凸(ReLU 网络、L1、投影) | 要升级成微分包含 / 单调算子理论,工具门槛明显上升 |
| 非正规性强 | ρ < 1 不保证误差单调下降,必须上伪谱(我们脚本里那个 1e140 的例子就是这个坑) |
| 高维深度网络的全局非凸景观 | λ_max 根本算不出来;ODE 只能给方向性直觉,不能给可验证的保证 |
| 只是想要一个能跑的结果 | 分析成本高于直接实验;但一旦分析完,可复用到一整类算法上 |
一句话取舍:ODE 分析换来的是"可迁移的机制理解 + 解析的设计规则",代价是失去对有限步长、精确方差和全局非凸行为的控制。 它替代的是"盲目扫参试错",不是替代实验。