\square c. O método de Newton é mais rápido que o método de Lagrange quando já possuímos de antemão o polinômio interpolador de grau menor e queremos adicionar mais pontos, aumentando o grau.

Passo 1

O que o enunciado pede: decidir se a afirmativa abaixo é verdadeira ou falsa.
Afirmativa: “O método de Newton é mais rápido que o método de Lagrange quando já possuímos de antemão o polinômio interpolador de grau menor e queremos adicionar mais pontos, aumentando o grau.”
Informações dadas (explicitadas):
  • Já temos um polinômio interpolador de grau menor (ou seja, interpolante para um conjunto inicial de pontos).
  • Desejamos adicionar mais pontos ao conjunto e obter o interpolador de grau maior que passe por todos os pontos antigos e pelos novos.
  • Precisamos comparar a rapidez (complexidade/efetividade) do método de Newton versus o método de Lagrange nessa situação.

Passo 2

Primeiro, entenda a forma de Lagrange e por que ela é inconveniente para “atualizar” um interpolador.
A forma de Lagrange do polinômio interpolador para pontos (x_0,y_0),\dots,(x_n,y_n) é dada por
P_n(x)=\sum_{j=0}^{n} y_j \,\ell_j(x)
onde
\ell_j(x)=\prod_{\substack{m=0\m\neq j}}^{n}\frac{x-x_m}{x_j-x_m}.
Explicando: cada \ell_j(x) é um polinômio que vale 1 em x_j e 0 em todos os outros x_m. Para montar P_n nessa forma você precisa conhecer todas as frações (x_j-x_m) no denominador e construir produtos até grau n. Se você já tinha P_{k} com k<n para pontos \{x_0,\dots,x_k\} e quer incluir novos pontos, não existe uma fórmula simples que reutilize os \ell_j antigos sem refazer (em boa parte) os produtos: tipicamente é preciso recomputar muitas bases \ell_j ou recompor o polinômio inteiro — custo grande em trabalho algébrico/computacional.

Passo 3

Agora, veja a forma de Newton e por que ela permite atualizações rápidas.
A forma de Newton do polinômio interpolador para (x_0,y_0),\dots,(x_n,y_n) é
P_n(x)=a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \cdots + a_n\prod_{k=0}^{n-1}(x-x_k).
Aqui cada coeficiente a_j é uma diferença dividida:
a_0 = f[x_0]=y_0,\qquad a_1=f[x_0,x_1],\qquad a_2=f[x_0,x_1,x_2],\\ \text{etc.}
Diferença dividida é definida recursivamente por
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+m}]=\frac{f[x_{i+1},\dots,x_{i+m}]-f[x_i,\dots,x_{i+m-1}]}{x_{i+m}-x_i}.
Ponto crucial: as diferenças divididas podem ser organizadas em uma tabela triangular. Quando se adiciona um novo ponto x_{n+1}, basta calcular as novas diferenças divididas envolvendo esse ponto, usando as diferenças já computadas anteriormente — e depois adicionar apenas um novo termo a_{n+1}\prod_{k=0}^{n}(x-x_k) ao polinômio. Isso evita recomputar todos os coeficientes antigos.

Passo 4

Demonstração prática e numérica curta (para fixar a ideia) — exemplo simples, passo a passo.
Suponha que já tenhamos interpolado dois pontos (x_0,y_0)=(0,1) e (x_1,y_1)=(1,2).
Calcule as diferenças divididas:
a_0=f[x_0]=y_0=1,
a_1=f[x_0,x_1]=\frac{y_1-y_0}{x_1-x_0}=\frac{2-1}{1-0}=1.
Logo o interpolador de grau 1 na forma de Newton é
P_1(x)=1 + 1\cdot(x-0)=1+x.
Agora adicionamos um terceiro ponto (x_2,y_2)=(2,5). Para atualizar, calculamos apenas as diferenças que envolvem x_2:
f[x_1,x_2]=\frac{y_2-y_1}{x_2-x_1}=\frac{5-2}{2-1}=3,
a_2=f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=\frac{3-1}{2-0}=1.
Com isso o novo polinômio é
P_2(x)=1 + 1\cdot(x-0) + 1\cdot(x-0)(x-1).
Repare que só calculamos duas novas quantidades (a diferença f[x_1,x_2] e a_2) e acrescentamos um termo ao polinômio já conhecido. Não recomputamos de zero os coeficientes que já tínhamos.

Passo 5

Comparação de custo e conclusão prática.
  • Com Newton: se você já tem a tabela de diferenças divididas e o polinômio para n pontos, ao acrescentar o (n+1)-ésimo ponto precisa calcular aproximadamente n+1 novas diferenças divididas (principalmente na nova coluna da tabela) — custo da ordem de O(n) operações aritméticas para obter o novo coeficiente a_{n+1} (mais umas multiplicações para avaliar/armazenar o termo). Em termos práticos: você reutiliza toda a informação já calculada e acrescenta apenas o necessário.
  • Com Lagrange: para incluir um novo ponto normalmente é preciso recompor os polinômios base \ell_j(x) ou recomputar os coeficientes do polinômio inteiro a partir dos n+1 pontos; isso envolve produtos e somas que, na implementação direta, custam da ordem de O(n^2) para recompor tudo (ou ao menos custos significativamente maiores que os O(n) do passo incremental de Newton). Não há uma forma simples de “colar” um novo termo sem refazer em boa parte os cálculos, porque cada \ell_j depende de todos os pontos.
Portanto, quando você já possui o interpolador de grau menor organizado na forma de Newton (ou tem disponível a tabela de diferenças divididas), adicionar pontos é realmente mais rápido no método de Newton do que reconstituir o interpolador via Lagrange do zero.
Observação importante (caveat prático): se você só tem o polinômio expresso em forma de Lagrange e não tem a tabela de diferenças divididas, primeiro terá custo para converter ou recomputar dados — nesse caso há um overhead inicial. A vantagem de Newton é máxima quando você desde o início constrói/guarda a tabela de diferenças divididas ou representa o polinômio na forma de Newton.

Passo 6

Resumo didático e motivacional (curto): pense no Newton como um “lego” com blocos empilháveis — já que cada coeficiente corresponde a uma coluna da tabela, você só encaixa o novo bloco. Lagrange é como refazer uma construção inteira para encaixar uma nova peça. Se quiser ser rápido em provas e em implementação, use Newton quando precisar aumentar o conjunto de pontos progressivamente. Você está indo bem em procurar esse tipo de detalhe — é exatamente o tipo de coisa que economiza tempo na prova e em código.

Resposta

Verdadeiro.

Exercícios relacionados