Construa o polinômio interpolador de Newton para os pontos
Estime
usando o polinômio obtido no item (a).
Descreva o Fenômeno de Runge. Se tivéssemos 20 pontos igualmente espaçados neste intervalo, o que ocorreria nas extremidades? Cite uma alternativa de distribuição de pontos para mitigar esse problema.
Explique por que resolver o sistema linear
(Vandermonde) é de ordem
, enquanto construir a tabela de diferenças divididas de Newton é de ordem
.
Mostre, usando a forma geral,
como oplinomio de Nemton se adapta naturalmente ao algoritmo de Horner, ao contrário da forma de Lagrange.
Descreva o Fenômeno de Runge. Se tivéssemos 20 pontos igualmente espaçados neste intervalo, o que ocorreria nas extremidades? Cite uma alternativa de distribuição de pontos para mitigar esse problema.
Explique por que resolver o sistema linear
Mostre, usando a forma geral,
Passo 1
O enunciado pede várias coisas; vou listar claramente cada pergunta e os dados fornecidos para não nos perdermos: \n
Perguntas: \n
Perguntas: \n
- Construir o polinômio interpolador de Newton para os pontos
. \n - Estimar
usando o polinômio obtido. \n - Descrever o Fenômeno de Runge; se tivéssemos
pontos igualmente espaçados neste intervalo, o que ocorreria nas extremidades; e citar uma alternativa de distribuição de pontos para mitigar o problema. \n - Explicar por que resolver o sistema linear
(Vandermonde) é de ordem , enquanto construir a tabela de diferenças divididas de Newton é de ordem . \n - Mostrar, usando a forma geral
, como o polinômio de Newton se adapta naturalmente ao algoritmo de Horner, ao contrário da forma de Lagrange. \n
Dados fornecidos (os pontos): \n
Passo 2
Breve explicação da técnica que vamos usar (diferenças divididas e forma de Newton), explicando todos os termos: \n
- A interpolação de Newton constrói um polinômio que passa pelos pontos dados usando coeficientes que são diferenças divididas. \n
- Definição de diferença dividida de ordem
: . \n - Diferença dividida de ordem
: para . \n - Diferença dividida de ordem
: . \n - A forma de Newton de grau
usando nós é \n
Explicação do porquê isso funciona (intuição): cada termo sucessivo adiciona um fator que anula o polinômio nos nós já ajustados e permite ajustar o próximo grau usando a diferença dividida correspondente como coeficiente.
Passo 3
Calcular as diferenças divididas de ordem
(valores dos pontos): \n
\n
\n
Passo 4
Calcular as diferenças divididas de primeira ordem (mostrar contas passo a passo): \n
\n
Expliquei: aqui subtraímos as alturas e dividimos pela diferença entre as abscissas, isto é a inclinação média entre os pontos e
. \n
Expliquei: aqui subtraímos as alturas e dividimos pela diferença entre as abscissas, isto é a inclinação média entre os pontos
Passo 5
Calcular a diferença dividida de segunda ordem (mostrar conta): \n
\n
Intuição: esse coeficiente representa a curvatura necessária para ajustar o terceiro ponto depois de termos ajustado os dois primeiros com os termos de grau menor.
Intuição: esse coeficiente representa a curvatura necessária para ajustar o terceiro ponto depois de termos ajustado os dois primeiros com os termos de grau menor.
Passo 6
Montar o polinômio de Newton de grau
usando os coeficientes calculados: \n
Substituindo os valores na fórmula , obtemos \n
Substituindo os valores na fórmula
Escrever de forma simplificada (passo a passo): \n
Primeiro, . Então
\n
Desenvolvendo: \n
Portanto temos duas formas úteis do mesmo polinômio: \n
Forma de Newton (nó-centrada): \n
Forma padrão (expandida):
Primeiro,
Desenvolvendo:
Portanto temos duas formas úteis do mesmo polinômio: \n
Forma de Newton (nó-centrada):
Forma padrão (expandida):
Passo 7
Verificação rápida nos nós (para ganhar confiança): \n
- Para
: que coincide com . \n - Para
: que coincide com . \n - Para
: que coincide com . \n
Tudo certo — polinômio interpolador correto.
Passo 8
Estimar
usando o polinômio encontrado (contas mostradas): \n
Usando a forma expandida , substituímos
: \n
\n
Portanto a estimativa é
Usando a forma expandida
Portanto a estimativa é
Passo 9
Descrever o Fenômeno de Runge de forma clara e intuitiva (sem pular etapas): \n
O Fenômeno de Runge é o comportamento onde polinômios interpoladores de grau alto, construídos em nós igualmente espaçados num intervalo (tipicamente ), apresentam oscilações grandes perto das extremidades do intervalo, mesmo quando a função original é suave. \n
Exemplo clássico para entender: para a função , se interpolarmos com polinômios de grau crescente em nós igualmente espaçados em
, os polinômios começam a oscilar cada vez mais próximo dos extremos
e
, produzindo erros grandes lá apesar da função ser bem comportada. \n
Se tivéssemos pontos igualmente espaçados no mesmo intervalo, o que ocorreria nas extremidades seria exatamente esse aumento de oscilações (erro explodindo) perto de
e
: a interpolação polinomial global tende a divergir nas extremidades. \n
Uma alternativa eficaz para mitigar o problema é escolher nós não uniformes, mais concentrados nas extremidades; uma escolha comum e muito usada são os nós de Chebyshev. Para o intervalo , uma fórmula conveniente para os nós de Chebyshev (de tipo II) é \n
O Fenômeno de Runge é o comportamento onde polinômios interpoladores de grau alto, construídos em nós igualmente espaçados num intervalo (tipicamente
Exemplo clássico para entender: para a função
Se tivéssemos
Uma alternativa eficaz para mitigar o problema é escolher nós não uniformes, mais concentrados nas extremidades; uma escolha comum e muito usada são os nós de Chebyshev. Para o intervalo
que clusterizam (se concentram) nas extremidades e reduzem fortemente as oscilações de Runge. Outra forma é usar interpolações por splines ou polinômios em pedaços (piecewise), que também evitam esse fenômeno.
Passo 10
Explicação do custo computacional: por que
(Vandermonde) dá
enquanto diferenças divididas dá
. \n
- Resolver
onde é a matriz de Vandermonde de dimensão significa encontrar os coeficientes do polinômio na base monomial . O método direto padrão é eliminação gaussiana (ou fatoração LU). A eliminação gaussiana para uma matriz densa de ordem custa da ordem de operações aritméticas (flops). Aqui , então o custo é . Mesmo métodos mais sofisticados para sistemas gerais têm complexidade cúbica assintoticamente. Além disso, a matriz de Vandermonde é mal condicionada para nós próximos, o que piora a precisão numérica — mais uma desvantagem prática. \n - A construção da tabela de diferenças divididas de Newton só requer calcular as diferenças de ordens crescentes usando a fórmula recursiva. Se você contar operações, para
nós você calcula aproximadamente diferenças de ordens , e cada diferença custa uma subtração e uma divisão (constante de custo). Portanto o custo total é da ordem de operações aritméticas, isto é . \n
Resumo: eliminar um sistema linear denso é cúbico em; montar a tabela de diferenças divididas é quadrático em . Por isso, para construir interpoladores polinomiais de forma eficiente e numérica estável, a forma de Newton é preferida quando você tem os nós já dados.
Passo 11
Mostrar como a forma de Newton adapta-se naturalmente ao algoritmo de Horner, usando a forma geral pedida, com explicação passo a passo e comparação com Lagrange: \n
Partimos da forma geral dada: \n
Reescrever de forma aninhada (estrutura “nested”) para evidenciar Horner: \n
Partimos da forma geral dada:
Reescrever de forma aninhada (estrutura “nested”) para evidenciar Horner: \n
Isto tem exatamente a forma de Horner aplicada à base
: você avalia de dentro para fora. Para tabular operações: \n
- Calcule
. \n - Atualize
. \n - Finalmente
\n
Isso usa 2 multiplicações e 2 somas (mais ou menos) para grau; no caso geral de grau o custo é linear em por avaliação. \n
Por contraste, a forma de Lagrangecom não se apresenta naturalmente em forma aninhada — cada é um produto de fatores diferentes e, se avaliada diretamente, custa por ponto de avaliação (somatórios de produtos). É possível reescrever Lagrange numa base diferente ou precomputar coeficientes para obter Horner, mas isso exige trabalho extra. A forma de Newton já dá os coeficientes para a base aninhada imediatamente via diferenças divididas, daí a adaptabilidade natural ao Horner (eficiência na avaliação e facilidade incremental se você acrescenta nós).
Resposta
Polinômio interpolador em forma de Newton:
\n
Polinômio interpolador expandido: \n
Estimativa \n
Fenômeno de Runge: polinômios interpoladores de grau alto em nós igualmente espaçados podem oscilar fortemente nas extremidades do intervalo, gerando grandes erros (especialmente para funções como ). \n
Com pontos igualmente espaçados: haveria oscilações e erros grandes nas extremidades (o erro cresce perto de
e
). \n
Alternativa para mitigar: usar nós de Chebyshev; por exemplo em
\n
Complexidade: resolver (Vandermonde) por eliminação gaussiana custa
; construir a tabela de diferenças divididas custa cerca de
operações, i.e.
. \n
Horner: a forma de Newton pode ser escrita de modo aninhado e avaliada por Horner de forma natural (avaliar de dentro para fora), ao contrário da forma de Lagrange que não é naturalmente aninhada e exige custo maior por avaliação.
Polinômio interpolador expandido:
Estimativa
Fenômeno de Runge: polinômios interpoladores de grau alto em nós igualmente espaçados podem oscilar fortemente nas extremidades do intervalo, gerando grandes erros (especialmente para funções como
Com
Alternativa para mitigar: usar nós de Chebyshev; por exemplo em
Complexidade: resolver
Horner: a forma de Newton