Recursive algorithms for computing Birkhoff interpolation polynomials

Résumé Technique : Algorithmes Récursifs pour le Calcul des Polynômes d'Interpolation de Birkhoff

Énoncé du Problème
Le document traite du problème d'interpolation de Birkhoff, une généralisation du problème classique d'interpolation de Hermite. Contrairement à l'interpolation de Hermite, où les conditions de dérivées en chaque nœud sont contiguës, l'interpolation de Birkhoff n'impose aucune exigence de continuité sur les dérivées. Ce manque de structure rend le problème plus complexe ; spécifiquement, l'ensemble des polynômes satisfaisant les conditions homogènes ne forme pas un idéal, et il n'existe pas de critère unifié pour la régularité du problème ou de méthode directe pour spécifier la forme du polynôme d'interpolation. Bien que les méthodes existantes comme l'élimination de Gauss puissent résoudre ces problèmes, elles entraînent souvent des coûts de calcul et des exigences de stockage élevés. De plus, des approches récentes (par exemple, RHBPIA) ont traité des cas spécifiques mais peuvent produire des bases d'interpolation de degré plus élevé que nécessaire.

Méthodologie
Les auteurs proposent deux algorithmes récursifs, l'Algorithme 1 et l'Algorithme 2, basés sur la théorie du complément de Schur et de l'identité de Sylvester. Ces algorithmes généralisent l'Algorithme d'Interpolation Polynomiale Récursive Généralisée (GRPIA), conçu à l'origine pour l'interpolation de Hermite.

1. Cadre Théorique :

   • Le document définit une « base d'interpolation proprement forte », une séquence de polynômes où les $i$ premiers polynômes forment une base propre pour les $i$ premières conditions d'interpolation.
   • En utilisant le complément de Schur, les auteurs dérivent des formules récursives pour calculer une base de type Newton et le polynôme d'interpolation correspondant. Le polynôme d'interpolation $p_{k-1}(x)$ pour les $k$ premières conditions est exprimé comme un complément de Schur d'une matrice impliquant les polynômes de la base et les valeurs d'interpolation.
   • L'approche utilise l'identité de Sylvester pour mettre à jour récursivement les polynômes auxiliaires ($g_{j,k-1}(x)$), évitant ainsi de recalculer l'ensemble du système à chaque étape.

2. Algorithme 1 :

   • Portée : Conçu pour les problèmes de Birkhoff où les conditions sont composées de fonctionnelles d'évaluation et d'opérateurs différentiels monomiaux (par exemple, $\delta_{x_\beta} \circ D_x^\alpha$).
   • Mécanisme : Il construit de manière itérative une base de type Newton. À chaque étape $k$, il vérifie une condition de jugement : $g^{(\alpha_k)}_{k-2, k-1}(x_{\beta_k}) \neq 0$. Cela garantit la non-singularité de la matrice de Vandermonde associée.
   • Ajustement : Si la condition de jugement échoue, l'algorithme augmente le degré de la base monomiale sous-jacente (en multipliant par $x$) et recalcule jusqu'à ce que la condition soit remplie.
   • Optimisation : L'algorithme incarne implicitement l'élimination de Gauss mais restreint les calculs aux $k$ premières conditions lors du calcul de la $k$-ième base, évitant ainsi l'accès à la partie triangulaire inférieure complète de la matrice.

3. Algorithme 2 :

   • Portée : Étend l'Algorithme 1 pour gérer des conditions plus générales où l'opérateur différentiel est un polynôme différentiel (une combinaison linéaire de dérivées) plutôt qu'un simple monôme.
   • Mécanisme : Il introduit une stratégie de réordonnancement. Si la condition de jugement échoue pour la condition actuelle $L_k$, l'algorithme vérifie les conditions suivantes ($L_{k+s}$). Si une condition ultérieure produit une valeur non nulle, il échange les positions de $L_k$ et $L_{k+s}$ pour garantir que la base reste proprement forte.
   • Réduction de Degré : Cette capacité de réordonnancement permet à l'Algorithme 2 de potentiellement produire des polynômes d'interpolation de degré plus faible que l'Algorithme 1, qui suit strictement l'ordre initial.

Contributions Clés

• Généralisation de GRPIA : Ce travail étend les techniques d'interpolation récursive de Hermite à la classe plus large des problèmes d'interpolation de Birkhoff.
• Construction de Base Proprement Forte : Le document fournit une méthode constructive pour générer une « base d'interpolation proprement forte » et une base de type Newton, garantissant que le problème est bien posé à chaque étape récursive.
• Condition de Jugement : Une contribution centrale est l'incorporation d'une condition de jugement pour vérifier dynamiquement la non-singularité de la matrice de Vandermonde pendant le processus récursif.
• Approche à Deux Algorithmes :
  • L'Algorithme 1 offre une solution récursive pour les opérateurs différentiels monomiaux avec une surcharge de calcul réduite.
  • L'Algorithme 2 gère les conditions de polynômes différentiels généraux et inclut un mécanisme de réordonnancement des conditions pour obtenir des solutions de degré inférieur.

Résultats et Performance
Le document valide les algorithmes par des exemples numériques (Exemples 1–4) et les compare à l'élimination de Gauss traditionnelle et à l'algorithme RHBPIA.

• Efficacité de Calcul : L'approche récursive réduit considérablement le coût de calcul et l'espace de stockage. En traitant les conditions de manière incrémentielle et en ne conservant pas tous les polynômes auxiliaires, la méthode évite les opérations matricielles complètes requises par l'élimination de Gauss.
• Réduction de Degré : Dans l'Exemple 1, la méthode proposée produit un polynôme d'interpolation de degré minimal (degré 3), tandis que la méthode RHBPIA de la référence [16] a produit un polynôme de degré 6 pour le même problème.
• Flexibilité : L'Exemple 2 démontre que l'Algorithme 2 peut réordonner les conditions pour trouver une solution de degré inférieur (degré 3) par rapport à l'Algorithme 1, qui pourrait autrement nécessiter l'augmentation du degré de la base pour satisfaire la condition de jugement.

Signification et Revendications
Les auteurs affirment que leur approche récursive offre une alternative plus efficace à l'élimination de Gauss traditionnelle pour l'interpolation de Birkhoff. En exploitant le complément de Schur et l'identité de Sylvester, la méthode réduit à la fois la complexité de calcul et les exigences de mémoire. De plus, l'introduction d'une condition de jugement garantit le caractère bien posé du problème à chaque étape. Le document positionne l'Algorithme 2 comme une avancée significative par rapport aux méthodes existantes (spécifiquement RHBPIA) en gérant les conditions de polynômes différentiels généraux et en fournissant un mécanisme pour minimiser le degré du polynôme résultant grâce au réordonnancement des conditions. Ce travail contribue à un cadre théorique unifié pour la construction de bases d'interpolation dans des contextes d'interpolation non idéaux.