Function Approximation on Squares | ALL YOU NEED IS LOVE

Townsend, A. (2014). Computing with functions in two dimensions (Doctoral dissertation, University of Oxford).

考虑定义在正方形区域上的连续函数。Townsend 的基本思想不是直接构造完整的二维张量积多项式，而是将逼近为少量可分离函数之和：

其中：是只依赖于的一维函数；是只依赖于的一维函数；是标量；是数值秩。每个和都使用自适应 Chebyshev 插值表示。因此，二维函数的逼近问题被转化为若干一维函数的逼近问题。矩阵化地，可以将这一表示写为，其中和是由一维函数组成的拟矩阵，。

Continuous Gaussian elimination

Townsend 使用带完全主元选取的连续 Gauss 消元构造上述低秩表示。

令初始余量为。在第步，从当前余量中选择绝对值最大的点：

以为主元位置，构造秩一修正项

于是

并更新余量。

对应的第个分离项可以写成

其中，。

这一过程是矩阵 Gauss 消元的连续对应物，也与 adaptive cross approximation 和 pseudoskeleton approximation 密切相关。

连续 Gauss 消元的一个重要性质是：经过步后，逼近函数与原函数在所选取的条直线上完全一致：

即对于，

因此，每次主元操作都增加一条被精确匹配的横向切片和一条纵向切片。

这一性质还意味着：

若关于是次多项式，则至多经过步即可精确恢复；
若关于是次多项式，则至多经过步即可精确恢复；
对于双变量次数为的多项式，至多经过步即可精确恢复。

第一阶段：寻找候选主元

连续区域上的绝对最大值通常无法直接计算，因此 Chebfun2 首先在二维 Chebyshev 张量积网格上离散地寻找主元。

算法依次使用嵌套网格：，，，…依此类推。在这些网格上分别允许最多为，，，…步矩阵 Gauss 消元。若当前采样矩阵能够在相对机器精度下由允许的低秩矩阵逼近，则保留得到的主元位置，并进入第二阶段；否则继续加密二维 Chebyshev 网格。

这一阶段的目的主要是确定：

函数的大致数值秩；
候选主元位置；
需要保留的横向和纵向切片。

若函数的数值秩为，Townsend 给出的第一阶段复杂度估计为。这一复杂度通常只依赖于数值秩，而不直接依赖于最终一维多项式次数。

第二阶段：解析主元行与主元列

低秩并不意味着函数在每个坐标方向上都容易解析。例如，的秩为，但在方向仍需要较高次数的 Chebyshev 多项式。

因此，在找到候选主元后，算法必须继续检查所有主元行和主元列是否已被充分解析。

设第一阶段确定了个主元，则第二阶段只在由这些主元行和主元列构成的 skeleton 上采样，而不再对整个二维张量积网格采样。也就是说，只计算：

条固定的纵向切片；
条固定的横向切片。

每条切片都在一维 Chebyshev 点上采样，并通过离散 Chebyshev 变换转换为 Chebyshev 系数。若高阶系数尚未衰减到相对机器精度，则将一维网格从、、等继续加密。

由于这些 Chebyshev 网格是嵌套的，加密过程中可以保持第一阶段选取的主元位置不变。

最终得到

这里和分别是解析主元列和主元行所需的多项式次数。

第二阶段最多需要约个函数采样值，并需要次运算完成 skeleton 上的消元过程。

算法结束后，函数被表示为

将系数矩阵记为

则二维 Chebyshev 系数矩阵具有低秩分解

因此，算法不需要显式存储一个大小为的稠密二维系数矩阵，而只需存储约个参数。

当时，这显著少于完整张量积表示所需的个参数。

收敛性分析

Townsend 首先从最佳低秩逼近的角度分析解析函数。对每个固定的，定义一维切片。假设这些切片都能一致地解析延拓到同一个 Bernstein 椭圆，其中，并且在该复区域内满足统一有界性，则存在秩至多为的函数，使得

因此最佳秩逼近误差按几何衰减。证明的核心是对方向作 Chebyshev 展开：

截断前项得到

它天然是至多秩的函数，因为每一项都是与的乘积。解析性保证 Chebyshev 系数随几何衰减，因此低秩误差也随几何衰减。同样地，函数的奇异值满足

所以解析函数的函数奇异值也具有几何衰减。这里仅要求函数在至少一个变量方向上具有统一解析延拓。交换和后可以得到完全相同的结论。

若误差满足，为了达到相对误差，大致需要

因此，对于解析延拓区域固定的函数，达到机器精度所需的数值秩通常只随精度要求的对数增长。但常数取决于函数在复平面中最近奇异点的位置。奇异点越靠近实区间，越接近，实际所需秩就越高。

Remark. 需要区分两个层面的结论：Theorem 3.2 证明了解析函数存在几何收敛的秩逼近，并给出了最佳低秩误差及奇异值的界。这一结论本身并不自动说明 Gauss 消元一定达到同样的误差常数。

Townsend 通过数值实验观察到，带完全主元选取的 Gauss 消元通常能够产生接近函数 SVD 的近最优低秩逼近，但论文没有给出一般条件下的完整近最优性或数值稳定性理论。

论文的 Theorem 4.6 在更强的复解析延拓条件下证明：由 Gauss 消元构造的秩一级数一致、绝对并且几何地收敛到原函数。该证明利用两个事实：

第步余量由于交叉插值性质而具有至少个零点；
余量可以解析延拓到实区间附近的复邻域。

通过将这些零点组成的多项式因子从余量中分离出来，并使用最大模原理，可以得到余量的几何衰减。因此，论文中存在两种不同的解析性结论：

较弱的统一 Bernstein 椭圆解析性保证最佳低秩逼近和奇异值几何衰减；
更强的复邻域解析性保证 Gauss 消元本身构造的级数几何收敛。

算法优势

传统张量积方法会在个二维 Chebyshev 点上采样，并构造

这种方法的采样量和存储量均为。

Townsend 方法利用数值低秩结构，只采样少量主元行和主元列，采样量约为。当时，可以显著减少函数采样次数、存储量、二维变换的成本、以及后续积分、微分和求值的计算量。进一步地，低秩表示将二维操作分解为若干一维操作。例如，

类似地：

偏微分只需要对或分别求导；
点值计算只需要计算个一维 Chebyshev 展开；
二维 Chebyshev 系数可以通过组一维离散 Chebyshev 变换得到；
二维积分可以化为个一维 Clenshaw–Curtis 积分。

这正是 Townsend 方法的主要计算优势：低秩分解先将两个变量解耦，随后复用成熟的一维 Chebyshev 算法。

Conclusion

Townsend 对正方形区域上解析函数的逼近可以概括为：使用自适应完全主元 Gauss 消元，从函数中选取少量横向与纵向切片，并将每条切片表示为一维 Chebyshev 展开，从而构造一个达到近机器精度的可分离低秩逼近。

对于具有统一复解析延拓的函数：

最佳秩逼近误差几何衰减；
函数奇异值几何衰减；
达到精度所需的秩通常为；
存储量由完整张量积表示的降为；
二维积分、微分、求值和系数变换可转化为少量一维 Chebyshev 运算。

需要注意的是，论文证明了最佳低秩逼近的几何收敛，并在更强解析性条件下证明了 Gauss 消元级数的几何收敛；但对于实际离散主元选取算法，完整的数值稳定性理论在论文中仍未建立。