New Recursive Divided-Difference Interpolation Method

Resumo Técnico: Novo Método de Interpolação por Diferenças Divididas Recursivas

Definição do Problema
A interpolação polinomial é uma ferramenta fundamental na análise numérica, contudo, existe um desafio computacional persistente na determinação dos coeficientes de um polinômio de interpolação na base monomial padrão ($P_n(x) = a_n x^n + \dots + a_0$). Embora a forma de Newton do polinômio de interpolação seja computacionalmente eficiente para a construção utilizando diferenças divididas, a conversão desta forma para a base monomial tipicamente requer uma de duas estratégias ineficientes:

1. Expansão Explícita: Expandir algebricamente os polinômios da base de Newton e agrupar termos semelhantes, o que aumenta as operações aritméticas e a complexidade à medida que o grau aumenta.
2. Sistemas de Vandermonde: Resolver um sistema linear $Va = y$, que é conhecido por ser numericamente instável para polinômios de alto grau devido ao crescimento exponencial do número de condição da matriz de Vandermonde.

Algoritmos existentes, como o método de Newton clássico, determinam apenas os coeficientes para a base de Newton e terminam assim que esses coeficientes são encontrados. Eles não utilizam a estrutura recursiva das diferenças divididas para fornecer diretamente os coeficientes monomiais sem expansão algébrica intermediária ou resolução de sistemas lineares.

Metodologia
Os autores propõem um novo algoritmo recursivo que determina coeficientes monomiais diretamente a partir de dados de interpolação, reconstruindo iterativamente a tabela de diferenças divididas. O método opera sob os seguintes princípios:

• Tabela de Diferenças Divididas Recursiva: Os autores definem uma estrutura recursiva onde todos os elementos de uma coluna na tabela de diferenças divididas são retidos, em vez de apenas o primeiro elemento utilizado na interpolação de Newton clássica.
• Identificação de Coeficientes via Invariância: A percepção teórica central é que, quando uma coluna de diferenças divididas computadas recursivamente produz um valor constante em todos os seus elementos (ou seja, $\Delta^{(k)}_1 = \Delta^{(k)}_2 = \dots = \Delta^{(k)}_{n-k+1}$), este valor constante corresponde exatamente ao coeficiente do termo de maior grau ($x^k$) na base monomial.
• Redução Iterativa: Uma vez identificado o coeficiente do termo de maior grau ($a_k$), o algoritmo subtrai a contribuição do termo $a_k x^k$ dos valores de interpolação originais ($y_i$). Isso gera um novo conjunto de diferenças de ordem zero correspondentes a um polinômio de grau $k-1$.
• Reconstrução: Uma nova tabela de diferenças divididas é construída a partir desses valores atualizados e o processo se repete para identificar o próximo coeficiente de maior grau ($a_{k-1}$). Isso continua sequencialmente até o termo constante ($a_0$).

Principais Contribuições

1. Determinação Monomial Direta: O artigo introduz um método para computar coeficientes monomiais sem expandir explicitamente o polinômio de Newton ou resolver um sistema de Vandermonde.
2. Estratégia de Redução Recursiva: Os autores desenvolvem uma estratégia onde o problema de interpolação é transformado em uma sequência de problemas de interpolação de grau inferior, subtraindo a contribuição do termo de maior grau determinado em cada etapa.
3. Justificativa Teórica: O método é sustentado por provas matemáticas rigorosas, incluindo:
   • Lema 3.1: Estabelece a representação do polinômio de interpolação em termos das diferenças divididas recursivas propostas.
   • Teorema 3.2: Prova a condição necessária e suficiente para que uma coluna constante na tabela de diferenças divididas recursivas corresponda ao coeficiente monomial específico.
4. Implementação Algorítmica: Um algoritmo iterativo passo a passo (Algoritmo 3.1) é fornecido, detalhando a reconstrução da tabela e a atualização das diferenças de ordem zero para isolar os coeficientes de $a_n$ até $a_0$.

Resultos
O artigo valida o método proposto através de experimentos numéricos:

• Corretude: Um exemplo numérico utilizando um polinômio cúbico ($y = 2x^3 + 3x^2 + 5x + 7$) demonstra a reconstrução recursiva passo a passo. O algoritmo identificou com sucesso os coeficientes $a_3=2$, $a_2=3$, $a_1=5$ e $a_0=7$ ao observar os valores constantes nas colunas de diferenças divididas após cada etapa de redução.
• Precisão: Os coeficientes reconstruídos coincidiram com os coeficientes exatos do polinômio, confirmando a validade teórica da abordagem.
• Eficiência: O método demonstrou que os coeficientes podem ser determinados diretamente a partir dos dados de interpolação, evitando a expansão algébrica intermediária exigida pelos métodos tradicionais de conversão.

Significância e Alegações
Os autores posicionam este trabalho como uma nova interpretação computacional das diferenças divididas. Eles alegam que o método estabelece um elo recursivo direto entre as diferenças divididas e os coeficientes monomiais, alterando fundamentalmente o papel das diferenças divididas de meramente construir polinômios de Newton para servirem como quantidades intermediárias para a reconstrução de coeficientes monomiais.

O artigo afirma explicitamente que não fornece uma análise comparativa de complexidade computacional ou estabilidade numérica contra métodos existentes (como resolvedores de Vandermonde ou algoritmos de conversão de base) dentro deste estudo. Em vez disso, apresenta o método como uma nova alternativa de esquema computacional recursivo. Os autores observam que pesquisas futuras abordarão a complexidade computacional, a estabilidade numérica e a eficiência do algoritmo em várias distribuições de nós e o compararão com métodos existentes. A principal contribuição é o arcabouço teórico e a demonstração de que coeficientes monomiais podem ser derivados recursivamente através da redução de dados sem álgebra linear auxiliar ou expansão polinomial.