Recursive algorithms for computing Birkhoff interpolation polynomials

Technische Samenvatting: Recursieve Algoritmen voor het Berekenen van Birkhoff-interpolatiepolynomen

Probleemstelling
Het artikel behandelt het Birkhoff-interpolatieprobleem, een generalisatie van het klassieke Hermite-interpolatieprobleem. In tegenstelling tot Hermite-interpolatie, waarbij de afgeleidecondities bij elk knooppunt aaneengesloten zijn, legt Birkhoff-interpolatie geen dergelijke continuiteitseisen op. Dit gebrek aan structuur maakt het probleem complexer; specifiek vormt de verzameling polynomen die aan homogene condities voldoen geen ideaal, en is er geen verenigd criterium voor de regulariteit van het probleem of een directe methk voor het specificeren van de vorm van het interpolatiepolynoom. Hoewel bestaande methoden zoals Gaussische eliminatie deze problemen kunnen oplossen, brengen zij vaak hoge computationele kosten en opslagvereisten met zich mee. Bovendien hebben recente recursieve benaderingen (bijv. RHBPIA) specifieke gevallen aangepakt, maar kunnen zij hogere graad interpolatiebases opleveren dan noodzakelijk is.

Methodologie
De auteurs stellen twee recursieve algoritmen voor, Algoritme 1 en Algoritme 2, gebaseerd op de theorie van de Schur-complement en de Sylvester-identiteit. Deze algoritmen generaliseren het Generalized Recursive Polynomial Interpolation Algorithm (GRPIA), dat oorspronkelijk is ontworpen voor Hermite-interpolatie.

1. Theoretisch Kader:

   • Het artikel definieert een "sterk passende interpolatiebasis" (strongly proper interpolation basis), een sequentie van polynomen waarbij de eerste $i$ polynomen een passende basis vormen voor de eerste $i$ interpolatiecondities.
   • Met behulp van de Schur-complement leiden de auteurs recursieve formules af om een Newton-type basis en het bijbehorende interpolatiepolynoom te berekenen. Het interpolatiepolynoom $p_{k-1}(x)$ voor de eerste $k$ condities wordt uitgedrukt als een Schur-complement van een matrix die de basispolynomen en de interpolatiewaarden bevat.
   • De aanpak maakt gebruik van de Sylvester-identiteit om hulp-polynomen ($g_{j,k-1}(x)$) recursief bij te werken, waardoor het niet nodig is om bij elke stap de volledige systeem opnieuw te berekenen.

2. Algoritme 1:

   • Reikwijdte: Ontworpen voor Birkhoff-problemen waarbij de condities zijn samengesteld uit evaluatiefunctionalen en monomiale differentiële operatoren (bijv. $\delta_{x_\beta} \circ D_x^\alpha$).
   • Mechanisme: Het construeert iteratief een Newton-type basis. Bij elke stap $k$ wordt een oordeelsconditie gecontroleerd: $g^{(\alpha_k)}_{k-2, k-1}(x_{\beta_k}) \neq 0$. Dit waarborgt de niet-singulariteit van de bijbehorende Vandermonde-matrix.
   • Aanpassing: Indien de oordeelsconditie faalt, verhoogt het algoritme de graad van de onderliggende monomiale basis (door vermenigvuldiging met $x$) en berekent het opnieuw totdat aan de conditie is voldaan.
   • Optimalisatie: Het algoritme belichaamt impliciet Gaussische eliminatie, maar beperkt de berekeningen tot de eerste $k$ condities bij het berekenen van de $k$-de basis, waardoor toegang tot het volledige onderste driehoekige deel van de matrix wordt vermeden.

3. Algoritme 2:

   • Reikwijdte: Breidt Algoritme 1 uit om algemenere condities aan te kunnen waarbij de differentiële operator een differentieel polynoom is (een lineaire combinatie van afgeleiden) in plaats van een enkel monoom.
   • Mechanisme: Het introduceert een herordeningstrategie. Als de oordeelsconditie faalt voor de huidige conditie $L_k$, controleert het algoritme opeenvolgende condities ($L_{k+s}$). Als een latere conditie een niet-nul waarde oplevert, wisselt het de posities van $L_k$ en $L_{k+s}$ om te garanderen dat de basis sterk passend blijft.
   • Graadvermindering: Deze herordeningmogelijkheid stelt Algoritme 2 in staat om potentieel lagere graad interpolatiepolynomen te produceren dan Algoritme 1, dat de initiële ordening strikt volgt.

Belangrijkste Bijdragen

• Generalisatie van GRPIA: Het werk breidt recursieve interpolatietechnieken uit van Hermite naar de bredere klasse van Birkhoff-interpolatieproblemen.
• Constructie van een Sterk Passende Basis: Het artikel biedt een constructieve methode om een "sterk passende interpolatiebasis" en een Newton-type basis te genereren, wat garandeert dat het probleem bij elke recursieve stap goed gesteld is.
• Oordeelsconditie: Een kernbijdrage is de incorporatie van een oordeelsconditie om de niet-singulariteit van de Vandermonde-matrix dynamisch te verifiëren tijdens het recursieve proces.
• Twee-Algoritme Aanpak:
  • Algoritme 1 biedt een recursieve oplossing voor monomiale differentiële operatoren met een verminderde computationele overhead.
  • Algoritme 2 behandelt algemene differentieel-polynomiale condities en bevat een mechanisme om condities te herordenen om oplossingen met een lagere graad te verkrijgen.

Resultaten en Prestaties
Het artikel valideert de algoritmen via numerieke voorbeelden (Voorbeelden 1–4) en vergelijkt deze met traditionele Gaussische eliminatie en het RHBPIA-algoritme.

• Computationele Efficiëntie: De recursieve aanpak vermindert de computationele kosten en de opslagruimte aanzienlijk. Door condities incrementeel te verwerken en niet alle hulp-polynomen te bewaren, vermijdt de methode de volledige matrixoperaties die vereist zijn voor Gaussische eliminatie.
• Graadvermindering: In Voorbeeld 1 levert de voorgestelde methode een interpolatiepolynoom met minimale graad (graad 3), terwijl de RHBPIA-methode uit referentie [16] voor hetzelfde probleem een polynoom van graad 6 produceerde.
• Flexibiliteit: Voorbeeld 2 demonstreert dat Algoritme 2 condities kan herordenen om een oplossing met een lagere graad te vinden (graad 3) vergeleken met Algoritme 1, dat anders de graad van de basis zou moeten verhogen om aan de oordeelsconditie te voldoen.

Betekenis en Claims
De auteurs beweren dat hun recursieve aanpak een efficiënter alternatief biedt voor traditionele Gaussische eliminatie voor Birkhoff-interpolatie. Door gebruik te maken van de Schur-complement en de Sylvester-identiteit, vermindert de methode zowel de computationele complexiteit als de geheugenvereisten. Bovendien zorgt de introductie van een oordeelsconditie voor de welgesteldeheid van het probleem bij elke stap. Het artikel positioneert Algoritme 2 als een significante vooruitgang ten opzichte van bestaande methoden (met name RHBPIA) door algemene differentieel-polynomiale condities te behandelen en een mechanisme te bieden om de graad van het resulterende polynoom te minimaliseren door middel van herordening van condities. Het werk draagt bij aan een verenigd theoretisch kader voor de constructie van interpolatiebases in niet-ideale interpolatiesituaties.