2025-11-10T02:44:47.045098

Error analysis of Abate--Whitt methods for Inverse Laplace Transforms and a new algorithm for queuing theory applications

Deniskin, Poloni
We study the accuracy of a class of methods to compute the Inverse Laplace Transform, the so-called \emph{Abate--Whitt methods} [Abate, Whitt 2006], which are based on a linear combination of evaluations of $\widehat{f}$ in a few points. We provide error bounds which relate the accuracy of a method to the rational approximation of the exponential function. We specialize our analysis to applications in queuing theory, a field in which Abate--Whitt methods are often used; in particular, we study phase-type distributions and Markov-modulated fluid models (or \emph{fluid queues}). We use a recently developed algorithm for rational approximation, the AAA algorithm [Nakatsukasa, Sète, Trefethen 2018], to produce a new family of methods, which we call TAME. The parameters of these methods are constructed depending on a function-specific domain $Ω$; we provide a quasi-optimal choice for certain families of functions. We discuss numerical issues related to floating-point computation, and we validate our results through numerical experiments which show that the new methods require significantly fewer function evaluations to achieve an accuracy that is comparable (or better) to that of the classical methods.
academic

Error analysis of Abate--Whitt methods for Inverse Laplace Transforms and a new algorithm for queuing theory applications

基本信息

  • 论文ID: 2510.14799
  • 标题: Error analysis of Abate--Whitt methods for Inverse Laplace Transforms and a new algorithm for queuing theory applications
  • 作者: Nikita Deniskin (Scuola Normale Superiore), Federico Poloni (Università di Pisa)
  • 分类: math.NA cs.NA (数值分析)
  • 发表时间: 2024年10月16日提交至arXiv
  • 论文链接: https://arxiv.org/abs/2510.14799

摘要

本文研究了计算拉普拉斯逆变换的Abate-Whitt方法的精度问题。这类方法基于在少数几个点对函数f^\hat{f}的线性组合评估。作者提供了将方法精度与指数函数有理逼近相关联的误差界限，并将分析专门应用于排队论中的相位型分布和马尔科夫调制流体模型。通过使用AAA算法，作者提出了名为TAME的新方法族，在保持或提高精度的同时显著减少了函数评估次数。

研究背景与动机

问题定义

拉普拉斯逆变换(ILT)是一个重要但具有挑战性的数值问题。给定函数ff的拉普拉斯变换f^(s)=∫0∞e−stf(t)dt\hat{f}(s) = \int_0^{\infty} e^{-st}f(t)dt，需要从f^\hat{f}在几个点的评估中重构f(t)f(t)的值。

问题重要性

  1. 病态性质: 与傅里叶变换不同，拉普拉斯逆变换是一个病态问题，f^\hat{f}中的小误差可能导致f(t)f(t)中的大误差
  2. 实际应用: 在排队论、概率论和工程中有广泛应用，特别是在相位型分布和流体队列分析中
  3. 计算效率: 现有方法通常需要大量函数评估才能达到满意的精度

现有方法局限性

  • Euler方法: 在垂直线上使用等间距节点，但收敛较慢
  • Talbot方法: 通过变形积分轮廓改善性能，但在某些情况下数值不稳定
  • Gaver-Stehfest方法: 基于Post-Widder公式，容易产生数值抵消
  • CME方法: 虽然稳定，但收敛速度慢，需要更多函数评估

核心贡献

  1. 理论分析: 建立了Abate-Whitt方法精度与指数函数有理逼近之间的严格数学关系
  2. 误差界限: 为SE类、ME类和LS类函数提供了定量误差界限
  3. TAME算法: 基于AAA算法提出了新的参数选择策略，显著提高了效率
  4. 应用特化: 针对排队论中的相位型分布和流体队列模型提供了专门的分析
  5. 数值稳定性: 深入讨论了浮点运算中的数值问题并提供解决方案

方法详解

任务定义

给定拉普拉斯变换f^(s)\hat{f}(s)，Abate-Whitt方法通过以下公式近似f(t)f(t)：

fN(t)=∑n=1Nwntf^(βnt)f_N(t) = \sum_{n=1}^N \frac{w_n}{t} \hat{f}\left(\frac{\beta_n}{t}\right)

其中(wn,βn)n=1N(w_n, \beta_n)_{n=1}^N是权重和节点参数。

核心理论框架

有理逼近联系

作者建立了关键的理论联系：Abate-Whitt方法的有理逼近子为 ρ^N(−z)=∑n=1Nwnβn−z\hat{\rho}_N(-z) = \sum_{n=1}^N \frac{w_n}{\beta_n - z}

方法的精度直接依赖于ρ^N(−z)\hat{\rho}_N(-z)对eze^z的逼近质量。

函数类别

论文重点研究三类"驯服"函数：

  1. SE类(指数和): f(t)=∑m=1Mcmeαmtf(t) = \sum_{m=1}^M c_m e^{\alpha_m t}
  2. ME类(矩阵指数): f(t)=v∗exp⁡(tQ)uf(t) = v^* \exp(tQ)u
  3. LS类(拉普拉斯-斯蒂尔切斯): f(t)=∫e−xtdμ(x)f(t) = \int e^{-xt}d\mu(x)

TAME算法设计

AAA算法修改

作者对AAA算法进行了关键修改：

  1. 度数调整: 确保有理函数度数为(N−1,N)(N-1,N)而非(K−1,K−1)(K-1,K-1)
  2. 共轭对: 保证非实权重和节点成对出现
  3. 数值稳定性: 在二进制64位精度下运行主循环，仅在特征值问题中使用高精度

域选择策略

根据函数类型选择适当的逼近域Ω\Omega：

  • 流体队列: Ω=B(−r,r)\Omega = B(-r,r)，其中r=λtr = \lambda t
  • ME类: Ω\Omega应包含W(tQ)W(tQ)(数值域)
  • LS类: Ω=[−L,0]\Omega = [-L,0]

实验设置

实验设计

作者设计了五个实验来验证TAME方法：

实验A: 流体队列模型(d+=5,d−=10d_+ = 5, d_- = 10，均匀化率λ=1\lambda = 1) 实验B: 不同时间点的性能比较 实验C: 连续时间马尔科夫链(d=15d = 15) 实验D: 非光滑信号(三角波和方波) 实验E: 欧式看涨期权定价

对比方法

  • Euler方法
  • Gaver-Stehfest方法
  • Talbot方法
  • CME方法
  • Zakian方法

评价指标

主要使用L∞L_{\infty}误差：∥f(t)−fN(t)∥∞\|f(t) - f_N(t)\|_{\infty}

实验结果

主要结果

实验A核心发现

  • TAME效率: 仅需3-4个函数评估即可达到与经典方法相当或更好的精度
  • 数值稳定性: TAME方法不会因为增加N′N'而出现数值不稳定，而经典方法在达到最小误差后误差会增长
  • 最优性能:
    • CDF: TAME在N′=4N'=4时误差为3.3×10−143.3 \times 10^{-14}
    • PDF: TAME在N′=3N'=3时误差为8.0×10−148.0 \times 10^{-14}
方法CDF最小误差对应NPDF最小误差对应N
Euler4.0×10−124.0 \times 10^{-12}352.0×10−112.0 \times 10^{-11}31
Talbot1.2×10−141.2 \times 10^{-14}181.2×10−131.2 \times 10^{-13}20
Zakian4.3×10−144.3 \times 10^{-14}43.8×10−133.8 \times 10^{-13}4
TAME3.3×10−143.3 \times 10^{-14}48.0×10−148.0 \times 10^{-14}3

实验B域选择验证

证实了理论预测：当r<tr < t时TAME方法精度下降，当r≥tr \geq t时保持高精度。

消融实验

通过不同Ω\Omega域的比较，验证了域选择策略的有效性。使用Theorem 5.2-5.4的界限构造的TAME方法都表现出色。

理论验证

实验验证了理论误差界限和矩估计的准确性，证明了有理逼近理论与实际性能的一致性。

相关工作

Abate-Whitt框架发展

  • Abate & Whitt (2006): 统一框架建立
  • 经典方法: Euler, Talbot, Gaver-Stehfest等方法的发展
  • CME方法: Telek等人基于矩优化的方法

有理逼近理论

  • AAA算法: Nakatsukasa等人的突破性工作
  • Padé逼近: Zakian方法的理论基础
  • 数值稳定性: 浮点运算中的精度问题

结论与讨论

主要结论

  1. 理论突破: 首次建立了Abate-Whitt方法精度与有理逼近质量的严格数学关系
  2. 实用算法: TAME方法在保持精度的同时显著减少计算量
  3. 数值稳定: 解决了经典方法的数值不稳定问题
  4. 专门化应用: 为排队论应用提供了优化的参数选择策略

局限性

  1. 函数类限制: 方法主要适用于"驯服"函数类(SE, ME, LS)
  2. 域依赖性: 需要先验知识来选择合适的逼近域Ω\Omega
  3. 非光滑函数: 对于不连续函数(如方波)，CME方法可能表现更好
  4. 理论常数: Crouzeix-Palencia定理中的常数1+21+\sqrt{2}可能不够紧

未来方向

  1. 扩展函数类: 将理论扩展到更广泛的函数类
  2. 自适应域选择: 开发自动选择最优Ω\Omega的算法
  3. 权重优化: 进一步优化权重选择以避免过度增长
  4. 并行算法: 开发并行版本以处理大规模问题

深度评价

优点

  1. 理论深度: 建立了严格的数学理论框架，填补了重要理论空白
  2. 实用价值: TAME方法在实际应用中表现出色，特别是在排队论中
  3. 数值洞察: 深入分析了浮点运算的影响，提供了实用的数值稳定性解决方案
  4. 全面实验: 涵盖了理论函数类内外的多种测试案例

不足

  1. 适用范围: 虽然覆盖了重要的函数类，但仍限制在特定类别
  2. 参数调优: 需要一定的专业知识来选择合适的域和参数
  3. 比较公平性: 某些实验中不同方法的参数设置可能不够公平

影响力

  1. 学术贡献: 为拉普拉斯逆变换数值方法提供了新的理论视角
  2. 实际应用: 在排队论、金融数学等领域有直接应用价值
  3. 方法论: AAA算法的创新应用为其他数值问题提供了启发

适用场景

  • 排队论中的相位型分布分析
  • 马尔科夫调制流体模型
  • 需要高精度拉普拉斯逆变换的工程应用
  • 函数评估成本高昂的场景

参考文献

本文引用了49篇重要文献，涵盖了拉普拉斯变换理论、数值方法、矩阵分析和排队论等多个领域的经典和前沿工作。特别值得注意的是对Abate & Whitt原始工作、AAA算法和相关数值方法的全面引用。

总体评价: 这是一篇高质量的数值分析论文，成功地将理论分析与实际应用相结合。TAME方法不仅在理论上有坚实基础，在实际性能上也表现出色。论文的贡献对于拉普拉斯逆变换的数值计算和排队论应用都具有重要价值。