Compare e contraste o Polinômio Interpolador de Lagrange e o Polinômio Interpolador de Newton. Quais são as vantagens de cada um?

Passo 1

O que o enunciado pede: comparar e contrastar o Polinômio Interpolador de Lagrange e o Polinômio Interpolador de Newton, explicitando as vantagens de cada um. \n
Informações dadas (implícitas no enunciado): \n
  • Temos um conjunto de nós distintos \{x_0,x_1,\dots,x_n\} e valores associados \{y_0,y_1,\dots,y_n\}, com y_i=f(x_i). \n
  • Procuramos o polinômio P de grau \le n tal que P(x_i)=y_i para todo i. \n
  • Não há restrição extra (por exemplo, formato dos nós ou método imposto). \n

Passo 2

Introdução e fórmula do interpolador de Lagrange. \n
Definição: o polinômio interpolador de Lagrange é escrito como combinação linear das funções base de Lagrange L_i(x). A fórmula é
P(x)=\sum_{i=0}^n y_i\,L_i(x)
onde cada função base é
L_i(x)=\prod_{\substack{j=0 \\\ j\neq i}}^{n}\frac{x-x_j}{x_i-x_j}.
Explicação didática do que isso significa: \n
  • Cada L_i(x) é construído para valer 1 em x=x_i e 0 em x=x_j para j\neq i. Assim, quando avaliamos P em x_k só sobra y_k\cdot L_k(x_k)=y_k. \n
  • A expressão \prod_{j\ne i}\frac{x-x_j}{x_i-x_j} é um produto de termos simples; o denominador é uma constante (depende apenas dos nós) e o numerador é polinomial em x. \n
    Exemplo pequeno (para fixar a ideia): com dois pontos (x_0,y_0) e (x_1,y_1) (caso n=1),
L_0(x)=\frac{x-x_1}{x_0-x_1},\qquad L_1(x)=\frac{x-x_0}{x_1-x_0},
e
P(x)=y_0\frac{x-x_1}{x_0-x_1}+y_1\frac{x-x_0}{x_1-x_0},
que é a forma clássica da reta que passa por dois pontos.

Passo 3

Vantagens práticas e limitações do formulário direto de Lagrange. \n
Vantagens iniciais: \n
  • Fórmula explícita e simétrica: você vê diretamente como cada y_i contribui. Isso é ótimo para provas teóricas e para demonstrar unicidade do interpolador. \n
  • Não precisa construir uma tabela intermediária (como na forma de Newton); basta os nós e os valores. \n
    Limitações do método direto: \n
  • Construção direta das L_i exige calcular \prod_{j\ne i}(x_i-x_j) e, para cada x avaliado, recomputar produtos, o que custa \mathcal{O}(n^2) operações para construir e \mathcal{O}(n^2) para avaliar se feito ingenuamente. \n
  • Se você adicionar um novo nó, em princípio precisa recomputar tudo (custoso). \n
  • Numericamente, a forma direta pode ser instável e ineficiente para avaliação repetida. \n

Passo 4

Barycentric Lagrange: a versão prática e estável de Lagrange. \n
Melhoria prática que todo mundo usa: a forma baricêntrica transforma a Lagrange em uma expressão que avalia P(x) com custo \mathcal{O}(n) por ponto e com boa estabilidade numérica. Primeiro definimos pesos
w_i=\frac{1}{\displaystyle\prod_{\substack{j=0\\\ j\neq i}}^{n}(x_i-x_j)}.
Então, para x que não coincide com nenhum nó,
P(x)=\frac{\displaystyle\sum_{i=0}^n \frac{w_i\,y_i}{x-x_i}}{\displaystyle\sum_{i=0}^n \frac{w_i}{x-x_i}}.
E se x=x_k para algum k então P(x_k)=y_k (tratamento direto). \n
Por que isso é vantajoso: \n
  • Os w_i dependem só dos nós; calculam-se uma vez ( \mathcal{O}(n^2)) e depois cada avaliação de P(x) fica em \mathcal{O}(n). \n
  • A forma baricêntrica é muito mais estável numericamente do que a fórmula de Lagrange direta. \n

Passo 5

Introdução e fórmula do interpolador de Newton. \n
Definição: o polinômio interpolador de Newton usa uma base triangular (base de Newton) com termos progressivos. A forma é
P(x)=a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n\prod_{j=0}^{n-1}(x-x_j).
Aqui os coeficientes a_k são as diferenças divididas (divided differences). Definição das diferenças divididas: \n
f[x_i]=y_i,
f[x_i,x_{i+1}]=\frac{f[x_{i+1}]-f[x_i]}{x_{i+1}-x_i},
e em geral
f[x_i,\dots,x_{i+k}]=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}.
Então a_k=f[x_0,\dots,x_k]. \n
Como se calcula: constrói-se uma tabela triangular (semelhante a um triângulo de Pascal de diferenças), custo total \mathcal{O}(n^2) para preencher a tabela.

Passo 6

Vantagens práticas do formulário de Newton. \n
  • Avaliação eficiente: usando multiplicação aninhada (alguma versão de Horner para a base de Newton) o valor de P(x) pode ser calculado em \mathcal{O}(n) operações. \n
  • Atualização incremental: se for adicionada uma nova observação (x_{n+1},y_{n+1}) ao final dos nós, basta calcular as novas diferenças divididas envolvendo o novo nó (custando \mathcal{O}(n)) e acrescentar um novo termo ao polinômio. Não é preciso recomputar tudo. Isso é uma grande vantagem quando os dados chegam sequencialmente. \n
  • Interpretação dos coeficientes: os coeficientes a_k (diferenças divididas) têm relação com derivadas quando os nós se aproximam; isso é útil em análise e em formas de extrapolação ou ajuste local. \n

Passo 7

Comparação direta: construção, avaliação, atualização e estabilidade. \n
Construção: \n
  • Lagrange (direto): escreve-se imediatamente L_i e soma-se; custo \mathcal{O}(n^2) para construir explicitamente as bases. \n
  • Newton: constrói-se tabela de diferenças divididas com custo \mathcal{O}(n^2). \n
    Avaliação de P(x): \n
  • Lagrange direto: avaliar pela soma das L_i(x) é \mathcal{O}(n^2) (produto por base). \n
  • Lagrange baricêntrica: após calcular os pesos, avaliação é \mathcal{O}(n) e com boa estabilidade numérica. \n
  • Newton: avaliação por multiplicação aninhada também é \mathcal{O}(n). \n
    Atualização (adicionar nó): \n
  • Lagrange: adicionar nó típico exige recalcular bases (custo alto). \n
  • Newton: se o novo nó for acrescentado como x_{n+1} “ao final”, só é preciso calcular as novas diferenças divididas envolvendo x_{n+1} (custo \mathcal{O}(n)). \n
    Estabilidade numérica: \n
  • Forma direta de Lagrange pode ser numericamente sensível; forma baricêntrica corrige muito disso. \n
  • Newton em geral é estável para avaliação se implementado com cuidado; porém tanto Newton quanto Lagrange sofrem do problema fundamental: polinômios de alto grau com nós mal escolhidos geram grande erro (Fenômeno de Runge). \n

Passo 8

Erro de interpolação e influência dos nós (ideia importante para a prova). \n
Fato teórico que vale para ambas as formas (já que representam o mesmo polinômio): se f tem derivada de ordem n+1 contínua, então para cada x existe \xi (dependente de x) tal que
f(x)-P(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{j=0}^{n}(x-x_j).
Interpretação: o erro depende de \prod_{j=0}^n(x-x_j) e de f^{(n+1)}. Isso explica por que a escolha dos nós (por exemplo nós de Chebyshev versus nós igualmente espaçados) é crucial para controlar o erro; não é culpa da forma (Lagrange ou Newton), mas da escolha dos nós e do grau. \n

Passo 9

Resumo prático e dicas de uso (como escolher em prova ou trabalho numérico). \n
  • Se você precisa de uma fórmula explícita rápida para derivar propriedades teóricas do interpolador (por exemplo, provar unicidade, manipular símbolos), a forma de Lagrange é muito intuitiva. \n
  • Para implementação numérica: use Lagrange baricêntrica ou Newton; ambos permitem avaliações rápidas ( \mathcal{O}(n)). \n
  • Se os dados são recebidos sequencialmente e você precisa atualizar o polinômio frequentemente acrescentando nós ao final, escolha Newton: atualização barata ( \mathcal{O}(n)). \n
  • Se quiser reusar a mesma malha de nós para vários vetores de valores y diferentes (mesmos x_i, valores y_i mudam), a forma baricêntrica é vantajosa porque os pesos w_i permanecem fixos. \n
  • Para estabilidade e precisão numérica ao avaliar em muitos pontos, prefira Lagrange baricêntrica ou Newton com cuidado numérico; evite a forma explícita de Lagrange para avaliações repetidas em ponto flutuante sem estabilização. \n

Passo 10

Um pequeno checklist prático para a prova (resuma mentalmente e use durante o exame). \n
  • Quer a fórmula direta e simétrica para usar em demonstrações? Lagrange. \n
  • Vai implementar e avaliar muitas vezes com os mesmos nós? Lagrange baricêntrica (calcule w_i uma vez). \n
  • Vai acrescentar pontos aos poucos e atualizar o polinômio? Newton. \n
  • Cuidado com nós equidistantes e grau alto: considere usar nós de Chebyshev ou dividir o domínio (splines) para evitar erro grande. \n

Resposta

Lagrange: fórmula explícita e simétrica; boa para provas teóricas e para ver diretamente como cada y_i contribui; com a forma baricêntrica permite avaliações eficientes ( \mathcal{O}(n)) e estáveis após computar pesos; desvantagem da forma direta é custo/instabilidade na avaliação e necessidade de recomputar tudo ao adicionar nós. \n
Newton: construção via diferenças divididas e base aninhada; permite avaliação eficiente ( \mathcal{O}(n)) e atualização incremental barata ( \mathcal{O}(n)) quando se adiciona um nó ao final; muito prática para implementações quando os dados chegam sequencialmente; dependência da ordenação dos nós pode influenciar comportamento numérico.

Exercícios relacionados