Stable evaluation of derivatives for barycentric and continued fraction representations of rational functions

기술 요약: 바리센트릭(Barycentric) 및 연속 분수(Continued Fraction) 표현법을 위한 안정적인 미분법 평가

문제 정의
AAA 알고리즘이나 탐욕적 틸레 연속 분수(Thiele continued fraction, TCF) 선택법과 같은 알고리즘으로 인해 유리 함수 근사(Rational function approximation)에 대한 관심이 다시 높아지고 있으며, 이들은 $n$개의 노드에 대해 $O(n)$ 시간 내에 안정적으로 평가할 수 있는 보간물을 생성한다. 그러나 이러한 표현법의 미분을 신뢰성 있게 계산하는 데에는 상당한 격차가 존재한다.

• 바리센트릭 표현법: 슈나이더(Schneider)와 베르너(Werner)가 $O(n)$ 공식으로 미분을 제공했으나, 일반적인 공식은 보간 노드 근처에서 감산 캔슬레이션(subtractive cancellation)으로 인해 수치적으로 불안정하다. 대안적인 노드용 공식은 안정적이지만 별도의 조건부 로직을 필요로 한다.
• TCF 표현법: 순방향 모드 자동 미분(forward-mode automatic differentiation)에 기반한 기존의 1계 미분 $O(n)$ 반복 공식은 수치적 안정성에 대한 정식 조사가 부족했으며, 고차 미분으로의 일반화도 확립되지 않았다.

방법론
저자들은 수치적 안정성과 계산 효율성을 유지하면서 두 표현법의 미분을 평가하기 위한 새로운 알고리즘을 제안한다.

1. 바리센트릭 표현법:

   • 불안정성 분석: 저자들은 표준 공식 $r'(z) = [N'(z) - r(z)D'(z)]/D(z)$가 $z$가 노드 $z_j$에 가까울 때 지배적인 감산 캔슬레이션을 겪는다는 것을 입증한다.
   • 이중 합산 솔루션: 이들은 이 캔슬레이션을 제거하는 이중 합산 공식(식 8)을 유도한다. 이 방식은 안정적이지만 $O(n^2)$의 복잡도를 가진다.
   • 안정적인 $O(n)$ 알고리즘: 선형 복잡도를 유지하기 위해, 저자들은 수정된 접근 방식을 도입한다. $\epsilon = z - z_j$ (여기서 $z_j$는 가장 가까운 노드)에 대해 $\tilde{N}(z) = \epsilon N(z)$ 및 $\tilde{D}(z) = \epsilon D(z)$를 정의함으로써, 모든 차수의 미분에 대한 안정적인 재귀 관계(식 13)를 유도한다. 이 방법은 스케일링된 분자와 분모를 다룸으로써 캔슬레이션을 피한다.
   • 알고리즘 1: 제안된 방법은 $O(n)$ 시간 내에 가장 가까운 노드를 식별하고, 수정된 재귀 관계를 적용하여 차수 $\mu$까지의 미분을 계산한다.

2. 틸레 연속 분수(TCF) 표현법:

   • 안정성 증명: 저자들은 분자/분모 쌍을 사용하는 TCF 평가의 대안적 반복(iteration)이 표준 테일 순서 평가(tail-ordered evaluation)와 동일한 수치적 안정성을 가짐을 증명한다(정리 1).
   • 고차 미분: 기존의 1계 미분 알고리즘을 순방향 모드 자동 미분을 사용하여 임의의 차수로 확장한다. 이들은 분자 및 분모 다항식($p_k$ 및 $q_k$)의 미분에 대한 재귀 관계(식 21)를 유도한다.
   • 알고리즘 2: 이 알고리즘은 $O(n)$ 시간 내에 함수값과 그 미분들을 차수 $\mu$까지 계산한다. 여기에는 중간 값을 재스케일링하여 수치적 언더플로우를 방지하는 실용적인 안전 장치가 포함된다.

주요 결과
저자들은 이러한 알고리즘을 RationalFunctionApproximation.jl 패키지에 구현하였으며, $[-1, 1]$ 구간과 단위 원상에서 다양한 함수(전함수, 진동 함수, 메로모르픽 함수, 분기점이 있는 함수)를 대상으로 테스트하였다.

• 바리센트릭 안정성: 수치 실험 결과, 새로운 공식이 확장 정밀도 산술(Double64)과 일치하는 오차를 달성함을 확인하였다. 반면, 기존의 슈나이더-베르너 일반 공식(식 2)은 노드 근처에서 심각한 오차(최대 $10^1$)를 보이는 반면, 새 공식은 머신 엡실론($10^{-13}$에서 $10^{-11}$) 근처의 오차를 유지한다.
• TCF 안정성: TCF 미분 알고리즘은 확장 정밀도에서의 오차와 거의 동일한 배정밀도 오차를 생성하여, 실질적인 안정성을 확인하였다.
• 미분의 차수: 이 방법들은 1계 및 2계 미분을 성공적으로 계산한다. 오차 크기는 일반적으로 안정적인 바리센트릭 결과와 10배 이내의 차이를 보인다.
• 한계점: 작은 파라미터($\epsilon \le 10^{-6}$)를 가진 고도로 매개변수화된 함수의 경우, 두 표현법 모두 일관된 정확한 전역 미분을 제공하지 못한다. 저자들은 이를 미분 공식 자체의 불안정성이 아니라, 유리 근사의 미분 과정에서 발생하는 본질적인 악조건(ill-conditioning)과 도메인 근처에 잔차가 작은 극(pole)이 존재할 가능성 때문이라고 설명한다.

의의 및 주장
본 논문은 모든 차수의 미분을 위한 $O(n)$ 알고리즘을 포함하여, 바리센트릭 표현법에서 미분을 평가하는 최초의 수치적으로 안정적인 방법을 제시한다고 주장한다. TCF 표현법의 경우, 미분 알고리즘을 고차로 확장한 최초의 일반화를 제공하며, 기존의 1계 미분 공식이 실제로 안정적임을 확인하였다.

저자들은 수치 실험을 통해 제안된 방법의 견고함을 확인하였으나, 안정성에 대한 엄밀한 수학적 증명이 부족하다는 점을 언급하며 겸허한 태도를 보인다. 그들은 유리 근사의 미분 정확도가 문제의 조건화(conditioning)에 의해 근본적으로 제한되며, 종종 함수 근사 자체보다 낮은 정확도를 보인다는 점을 강조한다. 이 연구는 민감도 분석이나 최적화가 필요한 응용 분야에서 중요한 병목 현상인 안정적인 미분 평가를 위한 실용적인 해결책을 제공한다.