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
é dada por
onde
Explicando: cada
é um polinômio que vale
em
e
em todos os outros
. Para montar
nessa forma você precisa conhecer todas as frações
no denominador e construir produtos até grau
. Se você já tinha
com
para pontos
e quer incluir novos pontos, não existe uma fórmula simples que reutilize os
antigos sem refazer (em boa parte) os produtos: tipicamente é preciso recomputar muitas bases
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
é
Aqui cada coeficiente
é uma diferença dividida:
Diferença dividida é definida recursivamente por
e em geral
Ponto crucial: as diferenças divididas podem ser organizadas em uma tabela triangular. Quando se adiciona um novo ponto
, basta calcular as novas diferenças divididas envolvendo esse ponto, usando as diferenças já computadas anteriormente — e depois adicionar apenas um novo termo
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
e
.
Calcule as diferenças divididas:
Logo o interpolador de grau
na forma de Newton é
Agora adicionamos um terceiro ponto
. Para atualizar, calculamos apenas as diferenças que envolvem
:
Com isso o novo polinômio é
Repare que só calculamos duas novas quantidades (a diferença
e
) 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
pontos, ao acrescentar o -ésimo ponto precisa calcular aproximadamente novas diferenças divididas (principalmente na nova coluna da tabela) — custo da ordem de operações aritméticas para obter o novo coeficiente (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
ou recomputar os coeficientes do polinômio inteiro a partir dos pontos; isso envolve produtos e somas que, na implementação direta, custam da ordem de para recompor tudo (ou ao menos custos significativamente maiores que os 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 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.