Recursive algorithms for computing Birkhoff interpolation polynomials

Resumo Técnico: Algoritmos Recursivos para Computação de Polinômios de Interpolação de Birkhoff

Enunciado do Problema
O artigo aborda o problema da interpolação de Birkhoff, uma generalização do clássico problema de interpolação de Hermite. Diferente da interpolação de Hermite, onde as condições de derivada em cada nó são contíguas, a interpolação de Birkhoff não impõe tais requisitos de continuidade nas derivadas. Essa falta de estrutura torna o problema mais complexo; especificamente, o conjunto de polinômios que satisfazem condições homogêneas não forma um ideal, e não há um critério unificado para a regularidade do problema ou um método direto para especificar a forma do polinômio de interpolação. Embora métodos existentes, como a eliminação gaussiana, possam resolver esses problemas, eles frequentemente incorrem em altos custos computacionais e requisitos de armazenamento. Além disso, abordagens recursivas recentes (por exemplo, RHBPIA) trataram de casos específicos, mas podem gerar bases de interpolação de grau superior ao necessário.

Metodologia
Os autores propõem dois algoritmos recursivos, Algoritmo 1 e Algoritmo 2, baseados na teoria do complemento de Schur e da identidade de Sylvester. Esses algoritmos generalizam o Algoritmo de Interpolação Polinomial Recursiva Generalizada (GRPIA), originalmente projetado para a interpolação de Hermite.

1. Estrutura Teórica:

   • O artigo define uma "base de interpolação fortemente própria", uma sequência de polinômios onde os primeiros $i$ polinômios formam uma base própria para as primeiras $i$ condições de interpolação.
   • Utilizando o complemento de Schur, os autores derivam fórmulas recursivas para computar uma base do tipo Newton e o correspondente polinômio de interpolação. O polinômio de interpolação $p_{k-1}(x)$ para as primeiras $k$ condições é expresso como um complemento de Schur de uma matriz envolvendo os polinômios da base e os valores de interpolação.
   • A abordagem utiliza a identidade de Sylvester para atualizar polinômios auxiliares ($g_{j,k-1}(x)$) recursivamente, evitando a necessidade de recomputar todo o sistema a cada etapa.

2. Algoritmo 1:

   • Escopo: Projetado para problemas de Birkhoff cujas condições são compostas por funcionais de avaliação e operadores diferenciais monomiais (ex: $\delta_{x_\beta} \circ D_x^\alpha$).
   • Mecanismo: Ele constrói iterativamente uma base do tipo Newton. Em cada etapa $k$, verifica uma condição de julgamento: $g^{(\alpha_k)}_{k-2, k-1}(x_{\beta_k}) \neq 0$. Isso garante a não singularidade da matriz de Vandermonde associada.
   • Ajuste: Se a condição de julgamento falhar, o algoritmo aumenta o grau da base monomial subjacente (multiplicando por $x$) e recomputa até que a condição seja atendida.
   • Otimização: O algoritmo incorpora implicitamente a eliminação gaussiana, mas restringe os cálculos às primeiras $k$ condições ao computar a $k$-ésima base, evitando o acesso à parte inferior triangular completa da matriz.

3. Algoritmo 2:

   • Escopo: Estende o Algoritmo 1 para lidar com condições mais gerais onde o operador diferencial é um polinômio diferencial (uma combinação linear de derivadas) em vez de um único monômio.
   • Mecanismo: Introduz uma estratégia de reordenação. Se a condição de julgamento falhar para a condição atual $L_k$, o algoritmo verifica as condições subsequentes ($L_{k+s}$). Se uma condição posterior resultar em um valor não nulo, o algoritmo troca as posições de $L_k$ e $L_{k+s}$ para garantir que a base permaneça fortemente própria.
   • Redução de Grau: Essa capacidade de reordenação permite que o Algoritmo 2 produza, potencialmente, polinômios de interpolação de grau menor do que o Algoritmo 1, que segue estritamente a ordem inicial.

Principais Contribuições

• Generalização do GRPIA: O trabalho estende as técnicas de interpolação recursiva de Hermite para a classe mais ampla de problemas de interpolação de Birkhoff.
• Construção de Base Fortemente Própria: O artigo fornece um método construtivo para gerar uma "base de interpolação fortemente própria" e uma base do tipo Newton, garantindo que o problema seja bem posto em cada etapa recursiva.
• Condição de Julgamento: Uma contribuição central é a incorporação de uma condição de julgamento para verificar a não singularidade da matriz de Vandermonde dinamicamente durante o processo recursivo.
• Abordagem de Dois Algoritmos:
  • O Algoritmo 1 oferece uma solução recursiva para operadores diferenciais monomiais com custo computacional reduzido.
  • O Algoritmo 2 lida com condições gerais de polinômios diferenciais e inclui um mecanismo para reordenar as condições a fim de alcançar soluções de grau menor.

Resultos e Desempenho
O artigo valida os algoritmos através de exemplos numéricos (Exemplos 1–4) e os compara com a eliminação gaussiana tradicional e o algoritmo RHBPIA.

• Eficiência Computacional: A abordagem recursiva reduz significativamente o custo computacional e o espaço de armazenamento. Ao processar as condições incrementalmente e não reter todos os polinômios auxiliares, o método evita as operações de matriz completas exigidas pela eliminação gaussiana.
• Redução de Grau: No Exemplo 1, o método proposto produz um polinômio de interpolação de grau mínimo (grau 3), enquanto o método RHBPIA da referência [16] produziu um polinômio de grau 6 para o mesmo problema.
• Flexibilidade: O Exemplo 2 demonstra que o Algoritmo 2 pode reordenar as condições para encontrar uma solução de grau menor (grau 3) comparado ao Algoritmo 1, que de outra forma poderia exigir o aumento do grau da base para satisfazer a condição de julgamento.

Significância e Alegações
Os autores alegam que sua abordagem recursiva oferece uma alternativa mais eficiente à eliminação gaussiana tradicional para a interpolação de Birkhoff. Ao utilizar o complemento de Schur e a identidade de Sylvester, o método reduz tanto a complexidade computacional quanto os requisitos de memória. Além disso, a introdução de uma condição de julgamento garante a natureza bem posta do problema em cada etapa. O artigo posiciona o Algoritmo 2 como um avanço significativo sobre os métodos existentes (especificamente o RHBPIA) ao lidar com condições gerais de polinômios diferenciais e fornecer um mecanismo para minimizar o grau do polinômio de interpolação resultante através da reordenação de condições. O trabalho contribui com um arcabouço teórico unificado para a construção de bases de interpolação em configurações de interpolação não ideais.