Ito Shinji, Nakatsukasa Yuji
1Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 113-8656 Japan.
2Present Address: NEC Corporation, Kanagawa, 211-8666 Japan.
Numer Math (Heidelb). 2018;139(3):633-682. doi: 10.1007/s00211-018-0948-4. Epub 2018 Feb 21.
A common way of finding the poles of a meromorphic function in a domain, where an explicit expression of is unknown but can be evaluated at any given , is to interpolate by a rational function such that at prescribed sample points , and then find the roots of . This is a two-step process and the type of the rational interpolant needs to be specified by the user. Many other algorithms for polefinding and rational interpolation (or least-squares fitting) have been proposed, but their numerical stability has remained largely unexplored. In this work we describe an algorithm with the following three features: (1) it automatically finds an appropriate type for a rational approximant, thereby allowing the user to input just the function , (2) it finds the poles via a generalized eigenvalue problem of matrices constructed directly from the sampled values in a one-step fashion, and (3) it computes rational approximants in a numerically stable manner, in that with small at the sample points, making it the first rational interpolation (or approximation) algorithm with guaranteed numerical stability. Our algorithm executes an implicit change of polynomial basis by the QR factorization, and allows for oversampling combined with least-squares fitting. Through experiments we illustrate the resulting accuracy and stability, which can significantly outperform existing algorithms.
在一个区域中寻找亚纯函数极点的常见方法是，当函数(f)的显式表达式未知但能在任意给定的(z)处求值时，用一个有理函数(r)对(f)进行插值，使得(r)在规定的采样点(z_i)处等于(f(z_i))，然后求(r)的根。这是一个两步过程，有理插值函数的类型需要由用户指定。已经提出了许多其他用于极点查找和有理插值（或最小二乘拟合）的算法，但它们的数值稳定性在很大程度上仍未得到探索。在这项工作中，我们描述了一种具有以下三个特征的算法：（1）它会自动为有理逼近找到合适的类型，从而允许用户仅输入函数(f)；（2）它通过直接从采样值(f(z_i))构建的矩阵的广义特征值问题一步找到极点；（3）它以数值稳定的方式计算有理逼近(r)，即(r(z_i))在采样点处与(f(z_i))的差值很小，这使其成为第一个具有保证数值稳定性的有理插值（或逼近）算法。我们的算法通过QR分解执行多项式基的隐式变换，并允许过采样与最小二乘拟合相结合。通过实验，我们展示了由此产生的精度和稳定性，其性能可显著优于现有算法。
