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

Technische Samenvatting: Stabiele Evaluatie van Afgeleiden voor Barycentrische en Doorlopende Breukvoorstellingen

Probleemstelling
Rationale functiebenadering heeft opnieuw belangstelling gekregen door algoritmen zoals AAA en de gulzige Thiele continued fraction (TCF) selectie, die interpolanten produceren op $n$ knopen die in $O(n)$ tijd stabiel geëvalueerd kunnen worden. Er bestaat echter een aanzienlijke kloof in de betrouwbare berekening van afgeleiden voor deze voorstellingen.

• Barycentrische Voorstelling: Hoewel Schneider en Werner $O(n)$ formules voor afgeleiden hebben verstrekt, is de generieke formule numeriek instabiel nabij interpolatieknopen door aftrekkingsannulering (subtractive cancellation). De alternatieve formule voor knopen is weliswaar stabiel, maar verschilt fundamenteel en vereist conditionele logica.
• TCF Voorstelling: Een bestaande $O(n)$ iteratieve formule voor de eerste afgeleide (gebaseerd op forward-mode automatische differentiatie) mist een formele onderzoek naar de numerieke stabiliteit, en er is geen generalisatie naar hogere orde afgeleiden vastgesteld.

Methodologie
De auteurs stellen nieuwe algoritmen voor om afgeleiden voor beide voorstellingen te evalueren, waarbij zowel de numerieke stabiliteit als de computationele efficiëntie behouden blijven.

1. Barycentrische Voorstelling:

   • Analyse van Instabiliteit: De auteurs tonen aan dat de standaardformule $r'(z) = [N'(z) - r(z)D'(z)]/D(z)$ lijdt onder dominante aftrekkingsannulering wanneer $z$ dicht bij een knoop $z_j$ ligt.
   • Dubbel-sommatie Oplossing: Zij leiden een dubbel-sommatieformule (Vergelijking 8) af die deze annulering elimineert. Hoewel stabiel, heeft deze aanpak een $O(n^2)$ complexiteit.
   • Stabiel $O(n)$ Algoritme: Om de lineaire complexiteit te behouden, introduceren de auteurs een aangepaste aanpak. Door $\tilde{N}(z) = \epsilon N(z)$ en $\tilde{D}(z) = \epsilon D(z)$ te definiëren waarbij $\epsilon = z - z_j$ (waarbij $z_j$ de dichtstbijzijnde knoop is), leiden zij een stabiele recursierelatie (Vergelijking 13) af voor afgeleiden van alle orden. Deze methode vermijdt de annulering door te werken met de geschaalde teller en noemer.
   • Algoritme 1: De voorgestelde methode identificeert de dichtstbijzijnde knoop in $O(n)$ tijd en past de aangepaste recursie toe om afgeleiden tot orde $\mu$ te berekenen.

2. Thiele Continued Fraction (TCF) Voorstelling:

   • Stabiliteitsbewijs: De auteurs bewijzen (Theorema 1) dat de alternatieve iteratie voor het evalueren van TCF's (gebruikmakend van teller/noemer paren) dezelfde numerieke stabiliteit heeft als de standaard tail-ordered evaluatie.
   • Hogere-orde Afgeleiden: Zij breiden het bestaande eerste-afgeleide algoritme uit naar willekeurige orden met behulp van forward-mode automatische differentiatie. Zij leiden recursierelaties (Vergelijking 21) af voor de afgeleiden van de teller- en noemerpolynomen ($p_k$ en $q_k$).
   • Algoritme 2: Dit algoritme berekent de functiewaarde en de afgeleiden tot orde $\mu$ in $O(n)$ tijd. Het bevat een praktische beveiliging tegen numerieke onderloop (underflow) door tussenliggende waarden te herschalen.

Belangrijkste Resultaten
De auteurs hebben deze algoritmen geïmplementeerd in de RationalFunctionApproximation.jl package en getest op diverse functies (entire, oscillerend, meromorf en functies met vertakkingspunten) over het interval $[-1, 1]$ en de eenheidscirkel.

• Barycentrische Stabiliteit: Numerieke experimenten bevestigen dat de nieuwe formule fouten bereikt die consistent zijn met extended-precision rekenkunde (Double64). In tegen plaats vertoont de oorspronkelijke Schneider–Werner generieke formule (Vergelijking 2) catastrofale fouten (tot $10^1$) nabij knopen, terwijl de nieuwe formule fouten nabij de machine-epsilon ($10^{-13}$ tot $10^{-11}$) behoudt.
• TCF Stabiliteit: Het TCF-afgeleidealgoritme produceert fouten in double precisie die bijna identiek zijn aan die in extended precision, wat de praktische stabiliteit bevestigt.
• Orde van Afgeleiden: De methoden berekenen succesvol eerste en tweede afgeleiden. De foutmarges liggen over het algemeen binnen een orde van grootte van de stabiele barycentrische resultaten.
• Beperkingen: Voor sterk geparametriseerde functies met kleine parameters ($\epsilon \le 10^{-6}$) levert geen van beide voorstellingen consistent nauwkeurige globale afgeleiden. De auteurs schrijven dit toe aan de inherente slecht geconditioneerde aard van het differentiëren van rationale benaderingen en de mog'elijke aanwezigheid van polen met kleine residuen nabij het domein, in plaats van instabiliteit in de afgeleideformules zelf.

Betekenis en Claims
Het artikel beweert de eerste numeriek stabiele methoden te presenteren voor het evalueren van afgeleiden in de barycentrische voorstelling, inclusief een $O(n)$ algoritme voor afgeleiden van alle orden. Voor de TCF-voorstelling biedt het werk de eerste generalisatie van het afgeleidealgoritme naar hogere orden en bevestigt dat de bestaande eerste-afgeleideformule praktisch stabiel is.

De auteurs zijn bescheiden in hun claims en merken op dat, hoewel zij geen formele bewijzen van stabiliteit hebben, de numerieke experimenten op eerste en tweede afgeleiden over diverse domeinen de robuustheid van de voorgestelde methoden bevestigen. Zij benadrukken dat de nauwkeurigheid van rationale afgeleidebenaderingen fundamenteel beperkt wordt door de conditionering van het probleem, wat vaak resulteert in een lagere nauwkeurigheid dan de functiebenadering zelf. Het werk biedt een praktische oplossing voor stabiele afgeleide-evaluatie in rationale benaderingsworkflows, waarmee een kritieke flessenhals wordt aangepakt in toepassingen die gevoeligheidsanalyse of optimalisatie vereisen.