Anderson 加速

先分清线性模型与实际残差 ​

对仿射映射$g(x)=Ax+b$，令${\overline{x}}_k=\sum a_j{x}_{k-p+j}$。由$\sum a_j=1$得到

所以式(1)精确最小化的是历史仿射空间中${\overline{x}}_k$的残差；真正接受的无阻尼候选还多应用了一次$g$。非线性映射一般连第一个等号也不成立，旧残差能完全抵消时，新残差仍可能变大。

这也是与GMRES比较时必须保留的细节。GMRES理路GMRES 方法GMRES · Generalized minimal residual method在 Krylov 仿射空间中逐步最小化线性系统的二范数残差，并权衡 Arnoldi 正交化、存储和重启代价。在Krylov空间中最小化线性系统残差；Walker–Ni的精确关系要求仿射$g$、$I-A$非奇异、相同初值、二范数、无阻尼、未截断的全部历史，并在所比较的第$k>0$轮满足$r_{k-1}^{\mathrm{G}\mathrm{M}\mathrm{R}\mathrm{E}\mathrm{S}}\ne 0$及$\Vert r_{j-1}^{\mathrm{G}\mathrm{M}\mathrm{R}\mathrm{E}\mathrm{S}}{\Vert }_2>\Vert r_j^{\mathrm{G}\mathrm{M}\mathrm{R}\mathrm{E}\mathrm{S}}{\Vert }_2$（$0<j<k$）。这允许第$k$轮本身停滞，也允许$k=1$时前述严格下降条件为空。满足这些条件时，对应的是${\overline{x}}_k=x_k^{\mathrm{G}\mathrm{M}\mathrm{R}\mathrm{E}\mathrm{S}}$和$x_{k+1}^{\mathrm{A}\mathrm{A}}=g(x_k^{\mathrm{G}\mathrm{M}\mathrm{R}\mathrm{E}\mathrm{S}})$，不是把同下标两点直接画等号。有限窗口、阻尼、保护拒绝或非线性映射都需要重新分析，不能无条件写成算法等价。

保护为什么能单独证明收敛 ​

由Banach不动点定理理路Banach 不动点定理Banach fixed-point theorem · Contraction mapping theorem完备空间中的统一压缩给出唯一不动点；用几何尾和证明收敛，并把后验误差与残差转成停止证书。，式(3)在闭子集这个完备空间上给出唯一不动点$x^{\ast }$。对任意$x\in D$，三角不等式给

从而

若加速步被接受，式(4)直接控制新残差。若回退，则

因此令$c=max(q,\eta )<1$，包括第一步Picard在内，每个已接受状态都满足

这份证明允许任意候选生成器，因为安全性来自真实残差检查和可靠回退。Anderson的作用是产生有机会通过检查的高质量候选；保护定理本身不承诺比原Picard每轮更快。

两个坐标的负权重可以合法且有效 ​

在$D=[0,1{]}^2$上取

映射保持$D$。矩阵的最大绝对行和为$3/4$，按诱导矩阵范数理路矩阵范数与诱导算子范数Matrix norm · Induced matrix norm · Operator norm of a matrix用诱导范数和常用可计算矩阵范数度量线性映射的放大能力，并区分算子范数、Frobenius 范数与谱半径。得到式(3)在无穷范数下可取$q=3/4$。直接解方程得$x^{\ast }=(1,1)$。

从$x_0=(0,0)$做一次Picard：$x_1=(1/4,3/4)$，残差为

使用这两个历史点，写$a_0=t,a_1=1-t$。最小化$\Vert r_1+t(r_0-r_1){\Vert }_2^2$，对$t$求导给

式(2)给$y=(53/82,81/82)\in D$，真实残差为$(57/328,3/328)$。它相对当前无穷范数残差的比例是

故$\eta =3/5$接受。负权重本身不构成失败，是否属于域和是否真有进展要分别核验。此时式(6)给点误差上界$57/82$，真实无穷范数误差为$29/82$；证书允许保守。

旧残差归零，新候选仍应拒绝 ​

在$D=[0,1]$定义

两段在$1/2$相接，映射保持$D$，且为$q=9/10$的压缩映射。唯一不动点为$5/9$。

从$x_0=0$到$x_1=1/10$，旧残差为$1/10,9/100$。两历史LS可以用$a_0=-9,a_1=10$完全抵消残差；候选却是

实际$r(1)=3/5-1=-2/5$。对$\eta =3/5$，允许阈值只有$27/500$，远小于$2/5$，所以应拒绝，并回退到$g(1/10)=19/100$。在旧点都处于第一段时拟合到的缓慢斜率，不能外推穿过分界后仍当成真实映射。

秩亏、边界与错误停机 ​

若所有保留残差相同，式(1)对很多系数给出同样值，甚至所有系数都是最优解。只要明确选解仍可执行；为了求一组权重而除以零或求奇异正规方程的逆则会失败。

$D$必须在求值前检查。负权重可能把概率向量变成负分量，或把正定矩阵组合成不定矩阵；映射若只在原域有定义，应直接拒绝，不先试算再寄望得到数字。$q=1$也不够：例如$g(x)=-x$是非扩张映射，Picard的非零点永远交替，式(6)分母失效。更一般的非扩张AA理论需要不同保护机制，不能把这里的$q<1$删掉。

可实现的最小二乘接口 ​

消去最新点系数，把式(1)写成

求得$\theta$后，前$p$个$a$取其分量，最后一个取$1-\sum {\theta }_j$。这里约定在式(10)多解时选最小二范数的$\theta$；这是一个确定的选解规则，不宣称得到最小范数的整个$a$。

实际用QR或SVD理路用 QR 与 SVD 求最小二乘Least squares via QR · Least squares via SVD · Numerical least squares以 QR 作为满列秩最小二乘的默认计算路线，并用 SVD 处理秩亏、欠定和最小范数解。求解，避免把$E^{\mathsf{T}}E$的逆当作默认实现。SVD可显露秩亏；按阈值截断小奇异值会改变原LS问题，应记录阈值，不过只要随后通过真实保护，式(7)仍成立。求解器报告失败时回退同样保留证明。

对$d\times p$矩阵，从头做稠密薄SVD通常需$O(dpmin(d,p))$算术操作，另需$O(dp)$形成矩阵和候选；$p\ge 1$。保存窗口需$O(d(m+1))$空间。若维护适当QR更新可以更便宜，但需另管秩变化和删列。不能把“只加一个点”理解为整轮常数时间。

查询账与预算 ​

已缓存$g(x_k)$后，接受候选通常需一次额外$g(y_k)$，该值可作为下一轮缓存。候选被拒且已求过值时，还需求$g(g(x_k))$以得到回退新点的残差，最多两次新映射求值；候选越域则跳过第一次。函数内部工作空间、域检查和LS成本另计。

为了认证$\Vert x_k-x^{\ast }\Vert \le \epsilon$，实际停止可直接检查$\Vert r(x_k)\Vert \le (1-q)\epsilon$。若初始残差尚未达标，式(7)给充分轮数

初值已通过时零步返回。这个轮数还须换成实际映射求值账，才能与原Picard公平比较。