AAA Algorithm

Nakatsukasa, Yuji, Olivier Sète, and Lloyd N. Trefethen. The AAA algorithm for rational approximation. SIAM Journal on Scientific Computing 40.3 (2018). https://doi.org/10.1137/16M1106122

AAA(Adaptive Antoulas-Anderson)算法是一种简单但非常有效的构造有理逼近的方法，它只需要目标函数在任意给定点上的取值即可进行计算。因为选取采样点的位置几乎没有限制，这让这种方法具有很强的灵活性，可以在各种复杂的几何区域上对函数进行近似。另一方面，AAA算法是以一种贪心地方式逐渐构造越来越高阶的有理逼近，这让最终得到的AAA逼近可以接近理论上的最佳有理逼近。由于有理逼近相比于多项式逼近更加强力但相对不稳定，特别是数值上容易出现伪极点-零点对，AAA算法设计了特殊的后处理来剔除可疑的极点-零点对，相比于另一常用的Padé逼近更加稳定。鉴于以上优点，AAA算法在目前是最通用的有理逼近构造算法。

给定一个定义在某一区域的函数，它的一个有理逼近是指形如的一个有理函数，其中和是两个多项式，使得在上有。

AAA算法的基本想法是先在考虑的区域上选取一组采样点，计算出函数在这些点上的取值集合，通过迭代的方式逐渐构造越来越高阶的有理逼近。每次迭代中，AAA算法会选择一个新的采样点加入到当前的支持点集合中，并使用当前的支持点集合来构造一个有理逼近。这个过程会一直持续下去，直到达到预设的最大迭代次数或者逼近误差足够小为止。每次迭代中构造一个如下质心形式的有理逼近：

当选定了支持点集合后，AAA算法通过构造一个Loewner矩阵并进行SVD来求解权重，从而确定上述逼近函数。

算法简介

AAA算法的每次迭代中有两个核心操作：选取新的支撑点和更新插值权重。

选取支撑点 假设在前次迭代后已经确定下来的支持点集合为，则AAA算法在第次迭代时将在剩余的采样点集合中寻找一个新的支撑点来构造更高阶逼近。此处AAA算法使用了简单粗暴的贪心策略，即选择使得当前逼近与目标函数在剩余采样点上误差最大的那个点作为新的支撑点，即

由于形式的逼近函数在支撑点处具有插值性质，即，使用上述策略选取新的支撑点可以保证每次迭代中逼近函数在新的支撑点处的误差为零，直观上来看会使得逼近函数在剩余采样点上的误差得到降低(但在理论上无法保证误差单调下降，因此AAA本质只是一种经验算法)。

更新权重 在选定了新的支撑点后，AAA算法需要更新逼近函数的权重以构造新的逼近函数。在这一步AAA算法以最小化逼近误差的方式确定权重，即

为了保证上面的优化问题有意义，我们要求。下面我们把上述问题转化为最小二乘问题并使用SVD求解。记，，则

记为如下的Loewner矩阵

那么之前的优化问题就等价于

所以就是矩阵的右奇异向量中对应于最小奇异值的那个向量，即中的最后一列向量。实际上，由于是一个瘦高矩阵，对应于最小奇异值的可能并不唯一或接近不唯一，但这并不影响AAA算法的性能，因为在实际计算中我们只需要得到一个满足条件的权重向量即可。

算法的最后一步是检查当前逼近函数在全体采样点集上的误差，如果误差足够小或者已经达到预设的最大迭代次数，则停止迭代并返回当前的逼近函数。

下面是AAA算法的伪代码实现：

AAA Algorithm

Problem: Construct a rational approximation of function on set .

---

Input:

Z = vector of sample points
F = f(Z), vector of date value on sample points

Output: AAA approximant to f

---

For m=1:mmax

Let , find the next support point via

Construct the Loewner matrix

Take the weight as the final right singular vector of by SVD

Construct the rational approximation

Check max error at sample points, break if error is small enough.

End

Return barycentric form rational approximant .

最后，由于舍入误差的存在，AAA算法得到的逼近函数可能会包含一些伪极点-零点对，这些对在数值上非常接近但并不是真正的极点-零点对。为了剔除这些伪极点-零点对，AAA算法设计了一个后处理步骤，即计算最后得到的有理函数的所有极点对应的留数，找到所有留数接近机器精度的极点并剔除支撑点中最接近这些极点的那个点，重新计算权重并构造新的逼近函数。这个后处理步骤可以显著提高AAA算法的数值稳定性，使得最终得到的逼近函数更加可靠。

数值示例

AAA算法可以逼近多种函数，包括性质良好的解析函数，或者具有邻近分支点的解析函数，甚至是区域中包含极点的亚纯函数以及定义在不连通区域上的函数或无界区域上的函数。这里只给出一个值得特别关注的数值例子。

考虑使用AAA算法对函数进行有理逼近，其中是一个正数，随着的增大，需要越来越高阶的有理函数来逼近函数的行为。下图展式了当分别取且采样点集为单位圆上的1000个等距点时AAA算法随着阶数的增加得到的逼近函数的误差下降情况。在所有的这些情形中，AAA算法都能够成功地构造出一个高阶的有理逼近来逼近函数，但从图中可以明显看到当时逼近误差并非随着阶数的增加而单调下降，而是呈现锯齿形振荡下降，AAA算法不能保证每次迭代中逼近误差都会得到降低。

选取为单位圆上的1000个等距点，使用AAA算法对函数进行阶有理逼近在采样点集上的误差，其中。

另外一点值得特别指出的是，对于一个给定的区域，选取来构造有理逼近只能让误差在边界上得到控制，但无法保证在区域内部的误差也得到控制。下图展示了当和时AAA算法得到的逼近函数在单位圆内部的误差分布情况，即使是在的情形中单位圆内部的误差不能得到很好的控制，而在的情形中单位圆内部的误差更加明显。

选取为单位圆上的1000个等距点，使用AAA算法对函数进行阶有理逼近在复平面上的误差分布等高线图，其中颜色从深蓝色(1e-12)到黄色(1e-1)表示误差该等高线上的误差大小。

如果希望在区域内部也得到误差的控制，最自然的方法是将区域内部的点也加入到采样点集中来构造有理逼近。下图展示了使用单位圆盘内部的3000个随机点与单位圆上的1000个等距点的并集来构造有理逼近时得到的逼近误差分布情况，可以看到在这种情况下AAA算法得到的逼近函数在单位圆内部的误差也得到了很好的控制。

选取为单位圆盘内部的3000个随机点与单位圆上的1000个等距点，使用AAA算法对函数进行阶有理逼近的误差分布等高线图，其中颜色从深蓝色(1e-12)到黄色(1e-1)表示误差该等高线上的误差大小。

关于使用AAA算法的更多细节和应用示例，参考Chebfun的AAA示例文档与综述文章Applications of AAA rational approximation。