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

Sintesi Tecnica: Valutazione Stabile delle Derivate per Rappresentazioni Baricentriche e di Frazioni Continue

Definizione del Problema
L'approssimazione di funzioni razionali ha visto un rinnovato interesse grazie ad algoritmi come AAA e la selezione greedy della frazione continua di Thiele (TCF), che producono interpolanti su $n$ nodi valutabili in modo stabile in tempo $O(n)$. Tuttavia, esiste una lacuna significativa nella computazione affidabile delle derivate per queste rappresentazioni.

• Rappresentazione Baricentrica: Sebbene Schneider e Werner abbiano fornito formule $O(n)$ per le derivate, la formula generica è numericamente instabile vicino ai nodi di interpolazione a causa della cancellazione sottrattiva. La formula alternativa per i nodi è stabile ma distinta, richiedendo una logica condizionale.
• Rappresentazione TCF: Una formula iterativa esistente $O(n)$ per la prima derivata (basata sulla differenziazione automatica in modalità forward) mancava di un'indagine formale sulla sua stabilità numerica, e non era stata stabilita alcuna generalizzazione alle derivate di ordine superiore.

Metodologia
Gli autori propongono nuovi algoritmi per valutare le derivate per entrambe le rappresentazioni, mantenendo la stabilità numerica e l'efficienza computazionale.

1. Rappresentazione Baricentrica:

   • Analisi dell'Instabilità: Gli autori dimostrano che la formula standard $r'(z) = [N'(z) - r(z)D'(z)]/D(z)$ soffre di una dominante cancellazione sottrattiva quando $z$ è vicino a un nodo $z_j$.
   • Soluzione a Doppia Somma: Derivano una formula di doppia sommatoria (Equazione 8) che elimina questa cancellazione. Sebbene stabile, questo approccio ha una complessità $O(n^2)$.
   • Algoritmo $O(n)$ Stabile: Per mantenere la complessità lineare, gli autori introducono un approccio modificato. Definendo $\tilde{N}(z) = \epsilon N(z)$ e $\tilde{D}(z) = \epsilon D(z)$ dove $\epsilon = z - z_j$ (con $z_j$ il nodo più vicino), derivano una relazione di ricorrenza stabile (Equazione 13) per le derivate di tutti gli ordini. Questo metodo evita la cancellazione lavorando con il numeratore e il denominatore scalati.
   • Algoritmo 1: Il metodo proposto identifica il nodo più vicino in tempo $O(n)$ e applica la ricorrenza modificata per calcolare le derivate fino all'ordine $\mu$.

2. Rappresentazione di Frazione Continua di Thiele (TCF):

   • Prova di Stabilità: Gli autori dimostrano (Teorema 1) che l'iterazione alternativa per la valutazione delle TCF (utilizzando coppie numeratore/denominatore) ha la stessa stabilità numerica della valutazione standard ordinata per code (tail-ordered).
   • Derivate di Ordine Superiore: Estendono l'esistente algoritmo della prima derivata ad ordini arbitrari utilizzando la differenziazione automatica in modalità forward. Derivano relazioni di ricorrenza (Equazione 21) per le derivate dei polinomi numeratore e denominatore ($p_k$ e $q_k$).
   • Algoritmo 2: Questo algoritmo calcola il valore della funzione e le sue derivate fino all'ordine $\mu$ in tempo $O(n)$. Include una salvaguardia pratica contro l'underflow numerico tramite il riscalamento dei valori intermedi.

Risultati Chiave
Gli autori hanno implementato questi algoritmi nel pacchetto RationalFunctionApproximation.jl e li hanno testati su varie funzioni (intere, oscillanti, meromorfe e con punti di ramificazione) sull'intervallo $[-1, 1]$ e sul cerchio unitario.

• Stabilità Baricentrica: Gli esperimenti numerici confermano che la nuova formula raggiunge errori coerenti con l'aritmetica a precisione estesa (Double64). Al contrario, l'originale formula generica di Schneider–Werner (Equazione 2) mostra errori catastrofici (fino a $10^1$) vicino ai nodi, mentre la nuova formula mantiene errori vicini alla macchina epsilon ($10^{-13}$ a $10^{-11}$).
• Stabilità TCF: L'algoritmo delle derivate TCF produce errori in doppia precisione quasi identici a quelli in precisione estesa, confermando la sua stabilità pratica.
• Ordine delle Derivate: I metodi calcolano con successo la prima e la seconda derivata. Gli ordini di grandezza degli errori sono generalmente entro un ordine di grandezza rispetto ai risultati stabili barentrici.
• Limitazioni: Per funzioni altamente parametrizzate con parametri piccoli ($\epsilon \le 10^{-6}$), nessuna delle due rappresentazioni fornisce costantemente derivate globali accurate. Gli autori attribuiscono ciò all'intrinseca cattività del differenziamento delle approssimazioni razionali e alla potenziale presenza di poli con residui piccoli vicino al dominio, piuttosto che all'instabilità delle formule delle derivate stesse.

Significatività e Rivendicazioni
Il documento sostiene di presentare i primi metodi numericamente stabili per valutare le derivate nella rappresentazione baricentrica, incluso un algoritmo $O(n)$ per le derivate di tutti gli ordini. Per la rappresentazione TCF, il lavoro fornisce la prima generalizzazione dell'algoritmo delle derivate ad ordini superiori e conferma che l'esistente formula della prima derivata è stabile in pratica.

Gli autori sono modesti nelle loro rivendicazioni, osservando che, sebbene manchino di prove formali di stabilità, gli esperimenti numerici su prime e seconde derivate attraverso vari domini confermano la robustezza dei metodi proposti. Essi sottolineano che l'accuratezza delle approssimazioni delle derivate razionali è fondamentalmente limitata dal condizionamento del problema, producendo spesso un'accuratezza inferiore rispetto all'approssimazione della funzione stessa. Il lavoro fornisce una soluzione pratica per la valutazione stabile delle derivate nei flussi di lavoro di approssimazione razionale, affrontando un collo di bottiglia critico in applicazioni che richiedono analisi di sensibilità o ottimizzazione.