Construa o polinômio interpolador de Newton para os pontos
(-1,4), \quad(0,2), \quad(1,6)
Estime f(0.5) 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 T a=y (Vandermonde) é de ordem O\left(n^{3}\right), enquanto construir a tabela de diferenças divididas de Newton é de ordem O\left(n^{2}\right).
Mostre, usando a forma geral,
P_{2}(x)=c_{0}+c_{1}\left(x-x_{0}\right)+c_{2}\left(x-x_{0}\right)\left(x-x_{1}\right)
como oplinomio de Nemton se adapta naturalmente ao algoritmo de Horner, ao contrário da forma de Lagrange.

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
  1. Construir o polinômio interpolador de Newton para os pontos (-1,4),\,(0,2),\,(1,6). \n
  2. Estimar f(0,5) usando o polinômio obtido. \n
  3. Descrever o Fenômeno de Runge; se tivéssemos 20 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
  4. Explicar por que resolver o sistema linear T a = y (Vandermonde) é de ordem O\big(n^{3}\big), enquanto construir a tabela de diferenças divididas de Newton é de ordem O\big(n^{2}\big). \n
  5. Mostrar, usando a forma geral \displaystyle P_{2}(x)=c_{0}+c_{1}\big(x-x_{0}\big)+c_{2}\big(x-x_{0}\big)\big(x-x_{1}\big), 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
    \displaystyle x_{0}=-1,\; y_{0}=4;\quad x_{1}=0,\; y_{1}=2;\quad x_{2}=1,\; y_{2}=6.

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 0: \displaystyle f[x_{i}]=y_{i}. \n
  • Diferença dividida de ordem 1: \displaystyle f[x_{i},x_{j}]=\frac{f[x_{j}]-f[x_{i}]}{x_{j}-x_{i}} para j>i. \n
  • Diferença dividida de ordem k: \displaystyle 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}}. \n
  • A forma de Newton de grau 2 usando nós x_{0},x_{1},x_{2} é \n
\displaystyle P_{2}(x)=f[x_{0}]+f[x_{0},x_{1}]\big(x-x_{0}\big)+f[x_{0},x_{1},x_{2}]\big(x-x_{0}\big)\big(x-x_{1}\big).
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 0 (valores dos pontos): \n
\displaystyle f[x_{0}] = y_{0} = 4. \n
\displaystyle f[x_{1}] = y_{1} = 2. \n
\displaystyle f[x_{2}] = y_{2} = 6.

Passo 4

Calcular as diferenças divididas de primeira ordem (mostrar contas passo a passo): \n
\displaystyle f[x_{0},x_{1}] = \frac{f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}} = \frac{2-4}{0-(-1)} = \frac{-2}{1} = -2. \n
Expliquei: aqui subtraímos as alturas e dividimos pela diferença entre as abscissas, isto é a inclinação média entre os pontos x_{0} e x_{1}. \n
\displaystyle f[x_{1},x_{2}] = \frac{f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}} = \frac{6-2}{1-0} = \frac{4}{1} = 4.

Passo 5

Calcular a diferença dividida de segunda ordem (mostrar conta): \n
\displaystyle f[x_{0},x_{1},x_{2}] = \frac{f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}} = \frac{4 - (-2)}{1-(-1)} = \frac{6}{2} = 3. \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.

Passo 6

Montar o polinômio de Newton de grau 2 usando os coeficientes calculados: \n
Substituindo os valores na fórmula \displaystyle P_{2}(x)=f[x_{0}]+f[x_{0},x_{1}]\big(x-x_{0}\big)+f[x_{0},x_{1},x_{2}]\big(x-x_{0}\big)\big(x-x_{1}\big), obtemos \n
\displaystyle P_{2}(x)=4 + (-2)\big(x-(-1)\big) + 3\big(x-(-1)\big)\big(x-0\big).
Escrever de forma simplificada (passo a passo): \n
Primeiro, \big(x-(-1)\big)=x+1. Então \displaystyle P_{2}(x)=4 -2(x+1) + 3(x+1)x. \n
Desenvolvendo: \displaystyle 4 -2x -2 + 3x^{2}+3x = 3x^{2} + (-2x+3x) + (4-2) = 3x^{2} + x + 2. \n
Portanto temos duas formas úteis do mesmo polinômio: \n
Forma de Newton (nó-centrada): \displaystyle P_{2}(x)=4 -2(x+1) + 3(x+1)x. \n
Forma padrão (expandida): \displaystyle P_{2}(x)=3x^{2} + x + 2.

Passo 7

Verificação rápida nos nós (para ganhar confiança): \n
  • Para x=-1: \displaystyle P_{2}(-1)=3\cdot(-1)^{2}+(-1)+2 = 3-1+2=4 que coincide com y_{0}. \n
  • Para x=0: \displaystyle P_{2}(0)=2 que coincide com y_{1}. \n
  • Para x=1: \displaystyle P_{2}(1)=3+1+2=6 que coincide com y_{2}. \n
    Tudo certo — polinômio interpolador correto.

Passo 8

Estimar \displaystyle f(0,5) usando o polinômio encontrado (contas mostradas): \n
Usando a forma expandida \displaystyle P_{2}(x)=3x^{2}+x+2, substituímos x=0,5: \n
\displaystyle P_{2}(0,5)=3\cdot(0,5)^{2} + 0,5 + 2 = 3\cdot 0,25 + 0,5 + 2 = 0,75 + 0,5 + 2 = 3,25. \n
Portanto a estimativa é \displaystyle f(0,5)=3,25.

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 [-1,1]), 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 \displaystyle f(x)=\frac{1}{1+25x^{2}}, se interpolarmos com polinômios de grau crescente em nós igualmente espaçados em [-1,1], os polinômios começam a oscilar cada vez mais próximo dos extremos -1 e 1, produzindo erros grandes lá apesar da função ser bem comportada. \n
Se tivéssemos 20 pontos igualmente espaçados no mesmo intervalo, o que ocorreria nas extremidades seria exatamente esse aumento de oscilações (erro explodindo) perto de -1 e 1: 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 [-1,1], uma fórmula conveniente para os nós de Chebyshev (de tipo II) é \n
\displaystyle x_{k}=\cos\!\left(\frac{2k+1}{2(n+1)}\pi\right),\qquad k=0,1,\dots,n,
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 T a = y (Vandermonde) dá O(n^{3}) enquanto diferenças divididas dá O(n^{2}). \n
  • Resolver T a = y onde T é a matriz de Vandermonde de dimensão (n+1)\times(n+1) significa encontrar os coeficientes a do polinômio na base monomial \{1,x,\dots,x^{n}\}. O método direto padrão é eliminação gaussiana (ou fatoração LU). A eliminação gaussiana para uma matriz densa de ordem m custa da ordem de \frac{2}{3}m^{3} operações aritméticas (flops). Aqui m=n+1, então o custo é O(n^{3}). 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+1 nós você calcula aproximadamente \sum_{k=1}^{n} (n+1-k) = \frac{n(n+1)}{2} diferenças de ordens \ge 1, e cada diferença custa uma subtração e uma divisão (constante de custo). Portanto o custo total é da ordem de n^{2} operações aritméticas, isto é O(n^{2}). \n
    Resumo: eliminar um sistema linear denso é cúbico em n; montar a tabela de diferenças divididas é quadrático em n. 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: \displaystyle P_{2}(x)=c_{0}+c_{1}\big(x-x_{0}\big)+c_{2}\big(x-x_{0}\big)\big(x-x_{1}\big). \n
Reescrever de forma aninhada (estrutura “nested”) para evidenciar Horner: \n
\displaystyle P_{2}(x)=c_{0} + \big(x-x_{0}\big)\Big(c_{1} + c_{2}\big(x-x_{1}\big)\Big).
Isto tem exatamente a forma de Horner aplicada à base \{1,(x-x_{0}),(x-x_{0})(x-x_{1}),\dots\}: você avalia de dentro para fora. Para tabular operações: \n
  1. Calcule t\leftarrow c_{2}. \n
  2. Atualize t\leftarrow t\cdot\big(x-x_{1}\big) + c_{1}. \n
  3. Finalmente P_{2}(x)\leftarrow c_{0} + \big(x-x_{0}\big)\cdot t. \n
    Isso usa 2 multiplicações e 2 somas (mais ou menos) para grau 2; no caso geral de grau n o custo é linear em n por avaliação. \n
    Por contraste, a forma de Lagrange \displaystyle P(x)=\sum_{j=0}^{n} y_{j} \ell_{j}(x) com \ell_{j}(x)=\prod_{m\ne j}\frac{x-x_{m}}{x_{j}-x_{m}} não se apresenta naturalmente em forma aninhada — cada \ell_{j}(x) é um produto de n fatores diferentes e, se avaliada diretamente, custa O(n^{2}) 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: \displaystyle P_{2}(x)=4 -2(x+1) + 3(x+1)x. \n
Polinômio interpolador expandido: \displaystyle P_{2}(x)=3x^{2}+x+2. \n
Estimativa \displaystyle f(0,5)=3,25. \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 \displaystyle \frac{1}{1+25x^{2}}). \n
Com 20 pontos igualmente espaçados: haveria oscilações e erros grandes nas extremidades (o erro cresce perto de -1 e 1). \n
Alternativa para mitigar: usar nós de Chebyshev; por exemplo em [-1,1] \displaystyle x_{k}=\cos\!\left(\frac{2k+1}{2(n+1)}\pi\right),\;k=0,\dots,n. \n
Complexidade: resolver T a=y (Vandermonde) por eliminação gaussiana custa O(n^{3}); construir a tabela de diferenças divididas custa cerca de \frac{n(n+1)}{2} operações, i.e. O(n^{2}). \n
Horner: a forma de Newton \displaystyle P_{n}(x)=c_{0}+c_{1}(x-x_{0})+c_{2}(x-x_{0})(x-x_{1})+\cdots 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.

Exercícios relacionados