Recursive algorithms for computing Birkhoff interpolation polynomials

Sintesi Tecnica: Algoritmi Ricorsivi per il Calcolo dei Polinomi di Interpolazione di Birkhoff

Enunciato del Problema
Il documento affronta il problema dell'interpolazione di Birkhoff, una generalizzazione del classico problema di interpolazione di Hermite. A differenza dell'interpolazione di Hermite, dove le condizioni derivate in ogni nodo sono contigue, l'interpolazione di Birkhoff non impone tali requisiti di continuità sulle derivate. Questa mancanza di struttura rende il problema più complesso; specificamente, l'insieme dei polinomi che soddisfano le condizioni omogenee non forma un ideale, e non esiste un criterio unificato per la regolarità del problema o un metodo diretto per specificare la forma del polinomio di interpolazione. Sebbene i metodi esistenti, come l'eliminazione gaussiana, possano risolvere questi problemi, essi spesso comportano elevati costi computazionali e requisiti di memoria. Inoltre, approcci ricorsivi recenti (ad esempio, RHBPIA) hanno affrontato casi specifici ma possono generare basi di interpolazione di grado superiore al necessario.

Metodologia
Gli autori propongono due algoritmi ricorsivi, l'Algoritmo 1 e l'Algoritmo 2, basati sulla teoria del complemento di Schur e dell'identità di Sylvester. Questi algoritmi generalizzano l'Algoritmo di Interpolazione Polinomiale Ricorsiva Generalizzata (GRPIA), originariamente progettato per l'interpolazione di Hermite.

1. Quadro Teorico:

   • Il documento definisce una "base di interpolazione fortemente propria", ovvero una sequenza di polinomi in cui i primi $i$ polinomi formano una base propria per le prime $i$ condizioni di interpolazione.
   • Utilizzando il complemento di Schur, gli autori derivano formule ricorsive per calcolare una base di tipo Newton e il corrispondente polinomio di interpolazione. Il polinomio di interpolazione $p_{k-1}(x)$ per le prime $k$ condizioni è espresso come un complemento di Schur di una matrice che coinvolge i polinomi della base e i valori di interpolazione.
   • L'approccio utilizza l'identità di Sylvester per aggiornare ricorsivamente i polinomi ausiliari ($g_{j,k-1}(x)$), evitando la necessità di ricalcolare l'intero sistema ad ogni passaggio.

2. Algoritmo 1:

   • Ambito: Progettato per problemi di Birkhoff in cui le condizioni sono composte da funzionali di valutazione e operatori differenziali monomiali (ad esempio, $\delta_{x_\beta} \circ D_x^\alpha$).
   • Meccanismo: Costruisce iterativamente una base di tipo Newton. Ad ogni passaggio $k$, verifica una condizione di giudizio: $g^{(\alpha_k)}_{k-2, k-1}(x_{\beta_k}) \neq 0$. Ciò garantisce la non singolarità della matrice di Vandermonde associata.
   • Regolazione: Se la condizione di giudizio fallisce, l'algoritmo aumenta il grado della base monomiale sottostante (moltiplicando per $x$) e ricalcola finché la condizione non viene soddisfatta.
   • Ottimizzazione: L'algoritmo incarna implicitamente l'eliminazione gaussiana ma restringe i calcoli alle prime $k$ condizioni durante il calcolo dell'ennesima base, evitando l'accesso alla parte inferiore triangolare completa della matrice.

3. Algoritmo 2:

   • Ambito: Estende l'Algoritmo 1 per gestire condizioni più generali in cui l'operatore differenziale è un polinomio differenziale (una combinazione lineare di derivate) anziché un singolo monomio.
   • Meccanismo: Introduce una strategia di riordinamento. Se la condizione di giudizio fallisce per l'attuale condizione $L_k$, l'algoritmo controlla le condizioni successive ($L_{k+s}$). Se una condizione successiva produce un valore non nullo, l'algoritmo scambia le posizioni di $L_k$ e $L_{k+s}$ per garantire che la base rimanga fortemente propria.
   • Riduzione del Grado: Questa capacità di riordinamento permette all'Algoritmo 2 di produrre potenzialmente polinomi di interpolazione di grado inferiore rispetto all'Algoritmo 1, che segue rigorosamente l'ordinamento iniziale.

Contributi Chiave

• Generalizzazione di GRPIA: Il lavoro estende le tecniche di interpolazione ricorsiva dall'interpolazione di Hermite alla classe più ampia dei problemi di interpolazione di Birkhoff.
• Costruzione di una Base Fortemente Propria: Il documento fornisce un metodo costruttivo per generare una "base di interpolazione fortemente propria" e una base di tipo Newton, garantendo che il problema sia ben posto ad ogni passaggio ricorsivo.
• Condizione di Giudizio: Un contributo centrale è l'incorporazione di una condizione di giudizio per verificare dinamicamente la non singolarità della matrice di Vandermonde durante il processo ricorsivo.
• Approccio a Due Algoritmi:
  • L'Algoritmo 1 offre una soluzione ricorsiva per operatori differenziali monomiali con un carico computazionale ridotto.
  • L'Algoritmo 2 gestisce condizioni di polinomi differenziali generali e include un meccanismo per riordinare le condizioni al fine di ottenere soluzioni di grado inferiore.

Risultati e Prestazioni
Il documento valida gli algoritmi attraverso esempi numerici (Esempi 1–4) e li confronta con l'eliminazione gaussiana tradizionale e l'algoritmo RHBPIA.

• Efficienza Computazionale: L'approccio ricorsivo riduce significativamente il costo computazionale e lo spazio di archiviazione. Elaborando le condizioni incrementalmente e non mantenendo tutti i polinomi ausiliari, il metodo evita le operazioni su matrice complete richieste dall'eliminazione gaussiana.
• Riduzione del Grado: Nell'Esempio 1, il metodo proposto produce un polinomio di interpolazione di grado minimo (grado 3), mentre il metodo RHBPIA del riferimento [16] ha prodotto un polinomio di grado 6 per lo stesso problema.
• Flessibilità: L'Esempio 2 dimostra che l'Algoritmo 2 può riordinare le condizioni per trovare una soluzione di grado inferiore (grado 3) rispetto all'Algoritmo 1, che altrimenti potrebbe richiedere l'aumento del grado della base per soddisfare la condizione di giudizio.

Significatività e Rivendicazioni
Gli autori affermano che il loro approccio ricorsivo offre un'alternativa più efficiente all'eliminazione gaussiana tradizionale per l'interpolazione di Birkhoff. Sfruttando il complemento di Schur e l'identità di Sylvester, il metodo riduce sia la complessità computazionale che i requisiti di memoria. Inoltre, l'introduzione di una condizione di giudizio assicura la correttezza del problema ad ogni passaggio. Il documento pone l'Algoritmo 2 come un avanzamento significativo rispetto ai metodi esistenti (specificamente RHBPIA) grazie alla gestione di condizioni di polinomi differenziali generali e alla fornitura di un meccanismo per minimizzare il grado del polinomio di interpolazione risultante attraverso il riordinamento delle condizioni. Il lavoro contribuisce a un quadro teorico unificato per la costruzione di basi di interpolazione in contesti di interpolazione non ideali.