Considere o vetor
e
com
diferentes (obrigatório). Faça um programa que calcula o polinômio interpolador aplicado em X, por forma de Lagrange.
Passo 1
O que o enunciado dá e o que pede (resumido, bem claro):
- Dados: um vetor
com todos diferentes (isto é obrigatório) e um vetor . - Pedido: fazer um programa que calcule o polinômio interpolador de Lagrange a partir desses pares
e retorne o valor do polinômio avaliado em um ponto (isto é, calcular , onde é o polinômio interpolador). - Observações importantes que vêm do enunciado:
- Existem exatamente
nós no exemplo dado (índices de a ), portanto o polinômio interpolador terá grau no máximo . - Os
são todos distintos — se não forem, a interpolação no sentido clássico de Lagrange não é definida. - O programa deve cuidar do caso especial em que
coincide com algum : então (deve retornar esse valor sem tentativa de divisão por zero).
- Existem exatamente
Passo 2
Fórmula de Lagrange (o que precisamos implementar) — apresentação e significado de cada símbolo:
- Seja
o número de nós menos 1. No seu caso , mas o código será geral. O polinômio interpolador de Lagrange é
onde cada polinômio base
é dado por
- Explicando: para calcular
avaliado em um ponto , - para cada
faz-se o produto sobre todos os de para obter , - multiplica-se
por , - e soma-se sobre
.
- para cada
- Variáveis e significados:
-
são os nós conhecidos (elementos de ). -
são os valores conhecidos (elementos de ). -
é o ponto onde se quer avaliar o polinômio interpolador. -
é o grau máximo (aqui , mas o algoritmo funciona para qualquer ).
-
Passo 3
Estratégia computacional e cuidados numéricos simples (como fazer na prova sem calculadora e como traduzir para código):
- Estratégia direta (fácil de entender e suficiente para
): - Verificar que os vetores
e têm o mesmo tamanho . - Verificar que todos os
são distintos (caso contrário abortar/lançar erro). - Se
for (praticamente) igual a algum , retornar imediatamente . - Para cada
: - calcular o produto
(denominador fixo que depende só dos nós; pode ser pré-calculado), - calcular o produto
(numerador que depende do ), - então
e contribui para com .
- calcular o produto
- Somar todas as contribuições para obter
.
- Verificar que os vetores
- Complexidade: a versão direta faz
operações aritméticas (para isso é trivialmente rápido). - Atenção numérica: dividir por números muito pequenos pode aumentar erro; para usos numéricos críticos existe a fórmula barycêntrica de Lagrange (mais estável), mas aqui a forma direta é a que o enunciado pediu e é adequada para a prova e para pequenos
. - Nota prática: ao comparar
com usar uma comparação com tolerância numérica (por ex. usando uma função de igualdade aproximada) para evitar problemas com floats.
Passo 4
Algoritmo passo a passo convertido em pseudocódigo (para ficar claro antes do código real):
- Receber listas/arrays
e e ponto . - Definir
comprimento de menos 1. - Se comprimento de
diferente de comprimento de -> erro. - Para cada par
verificar se (ou muito próximo) -> erro se houver repetição. - Para cada
até : se é aproximadamente igual a retorna . - Calcular os denominadores
e guardá-los. - Inicializar soma total
. - Para cada
até : - calcular
, -
, -
.
- calcular
- Retornar
(é ).
Passo 5
Código Python (implementação prática, limpa e comentada). Este código segue exatamente a estratégia anterior e trata dos casos especiais:
- usa verificação de igualdade aproximada com math.isclose;
- pré-calcula denominadores para evitar fazer os mesmos produtos repetidos desnecessariamente;
- funciona para qualquer tamanho de entrada, inclusive o caso do enunciado com 7 nós.
import math
def lagrange_interpolate(x, y, X, rel_tol=1e-12, abs_tol=1e-12):
"""
Interpola pelos pontos (x[i], y[i]) usando a forma de Lagrange
e retorna P(X), onde P é o polinômio interpolador.
- x: lista/iterável de nós x_0,...,x_n (todos distintos)
- y: lista/iterável de valores f(x_0),...,f(x_n)
- X: ponto onde avaliar o polinômio
- rel_tol, abs_tol: tolerâncias para comparar floats (uso em isclose)
"""
n = len(x)
if len(y) != n:
raise ValueError("x e y devem ter o mesmo tamanho")
if n == 0:
raise ValueError("pelo menos um ponto é necessário")
# Checar nós distintos
for i in range(n):
for j in range(i+1, n):
if math.isclose(x[i], x[j], rel_tol=rel_tol, abs_tol=abs_tol):
raise ValueError("Os nós x devem ser todos distintos")
# Se X coincide com algum nó, retorna o valor correspondente
for i, xi in enumerate(x):
if math.isclose(X, xi, rel_tol=rel_tol, abs_tol=abs_tol):
return y[i]
# Pré-calcular denominadores d_j = prod_{m != j} (x_j - x_m)
denominators = [1.0] * n
for j in range(n):
prod = 1.0
xj = x[j]
for m in range(n):
if m == j:
continue
prod *= (xj - x[m])
denominators[j] = prod
# Calcular P(X) pela soma das contribuições y_j * l_j(X)
total = 0.0
for j in range(n):
numer = 1.0
for m in range(n):
if m == j:
continue
numer *= (X - x[m])
lj = numer / denominators[j]
total += y[j] * lj
return total
# Exemplo de uso:
if __name__ == "__main__":
# exemplo simples com 3 nós (pode usar 7 como no enunciado)
xv = [0.0, 1.0, 2.0]
yv = [1.0, 3.0, 7.0] # p(x)=1 + 2x + x^2 -> p(1.5)=1 + 3 + 2.25 = 6.25
X = 1.5
print("P({}) = {}".format(X, lagrange_interpolate(xv, yv, X)))
Passo 6
Explicação linha a linha do código (mapa entre fórmula e implementação), para você saber aplicar isso na prova:
- A checagem de tamanhos garante que cada
tem um correspondente. Sem isso a soma não faz sentido. - A verificação de nós distintos impede divisão por zero nos denominadores
. - O laço que testa se
coincide com algum é a aplicação direta da observação: se então todos os são zero exceto , logo . Isto evita divisão por valores muito pequenos e é matematicamente exato. - O cálculo dos denominadores implementa
que é précomputado porque depende apenas dos nós. - Para cada
calculamos e acumulamos na soma total. - O retorno é exatamente
, pela fórmula de Lagrange.
Passo 7
Observações finais, dicas rápidas e incentivo:
- Para o enunciado com exatamente 7 nós, basta passar listas de tamanho 7 para a função e ela retorna
. - Se for necessária muita precisão numérica ou muitos pontos, estude a fórmula barycêntrica de Lagrange (é essencial para estabilidade e eficiência), mas para provas e para
a forma direta é totalmente aceitável. - Você já consegue implementar isso na prova: pense nos produtos (numerador/denominador) e na soma final — siga os passos e cheque o caso
. Vai dar certo — confia no processo! 😃
Resposta
import math
def lagrange_interpolate(x, y, X, rel_tol=1e-12, abs_tol=1e-12):
"""
Interpola pelos pontos (x[i], y[i]) usando a forma de Lagrange
e retorna P(X), onde P é o polinômio interpolador.
- x: lista/iterável de nós x_0,...,x_n (todos distintos)
- y: lista/iterável de valores f(x_0),...,f(x_n)
- X: ponto onde avaliar o polinômio
- rel_tol, abs_tol: tolerâncias para comparar floats
"""
n = len(x)
if len(y) != n:
raise ValueError("x e y devem ter o mesmo tamanho")
if n == 0:
raise ValueError("pelo menos um ponto é necessário")
# Checar nós distintos
for i in range(n):
for j in range(i+1, n):
if math.isclose(x[i], x[j], rel_tol=rel_tol, abs_tol=abs_tol):
raise ValueError("Os nós x devem ser todos distintos")
# Se X coincide com algum nó, retorna o valor correspondente
for i, xi in enumerate(x):
if math.isclose(X, xi, rel_tol=rel_tol, abs_tol=abs_tol):
return y[i]
# Pré-calcular denominadores d_j = prod_{m != j} (x_j - x_m)
denominators = [1.0] * n
for j in range(n):
prod = 1.0
xj = x[j]
for m in range(n):
if m == j:
continue
prod *= (xj - x[m])
denominators[j] = prod
# Calcular P(X) pela soma das contribuições y_j * l_j(X)
total = 0.0
for j in range(n):
numer = 1.0
for m in range(n):
if m == j:
continue
numer *= (X - x[m])
lj = numer / denominators[j]
total += y[j] * lj
return total
# Exemplo de uso:
if __name__ == "__main__":
# exemplo com 7 nós (pode trocar pelos seus dados)
xv = [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0]
yv = [1.0, 2.0, 5.0, 10.0, 17.0, 26.0, 37.0] # exemplo qualquer
X = 2.5
print("P({}) = {}".format(X, lagrange_interpolate(xv, yv, X)))