Lista 10 · Interpolação polinomial¶

Acompanha o capítulo 10. Estimar entre os pontos de uma tabela: reta, Lagrange e Newton. E nunca fora dela.

Como esta lista funciona

Abra o caderno no Colab, escreva a sua solução no lugar do # TODO e rode a célula de teste logo abaixo. Ela mesma diz o que passou e o que falhou — você não precisa esperar correção de ninguém.

O código de cada exercício também está aqui embaixo, caso você prefira colar num editor local. Os testes comparam números com tolerância.

Exercícios marcados com ✏️ são à mão, no papel, com 4 casas decimais — como na parte em papel das avaliações.

Exercício 01¶

✏️ À mão. A tabela tem os pontos \((1, 2)\), \((2, 3)\) e \((4, 1)\).

a) Calcule \(L_0(3)\), \(L_1(3)\) e \(L_2(3)\) e o valor do polinômio de Lagrange em \(x = 3\).

b) Monte a tabela de diferenças divididas e escreva o polinômio de Newton.

c) Calcule o polinômio de Newton em \(x = 3\). Deu o mesmo que em (a)? Por quê?

Exercício 02¶

Escreva interp_linear(xs, ys, x), que acha os dois pontos vizinhos de x na tabela (com xs em ordem crescente) e devolve a interpolação linear entre eles. Se x estiver fora da tabela, devolva None (não extrapole!).

interp_linear([0, 10, 20], [5, 25, 30], 15)    # -> 27.5
interp_linear([0, 10, 20], [5, 25, 30], 25)    # -> None

def interp_linear(xs, ys, x):
    """Interpolação linear entre os dois pontos da tabela (xs crescente) em volta de x."""
    # TODO: ache o i com xs[i] <= x <= xs[i + 1] e devolva a reta entre os dois;
    # se nenhum servir, return None
    pass


# --- testes (não altere) ---
assert abs(interp_linear([0, 10, 20], [5, 25, 30], 15) - 27.5) < 1e-12
assert abs(interp_linear([0, 10, 20], [5, 25, 30], 10) - 25) < 1e-12, "no próprio ponto"
assert abs(interp_linear([50, 100, 200, 400], [4.48, 6.40, 9.17, 13.20], 300) - 11.185) < 1e-9
assert interp_linear([0, 10, 20], [5, 25, 30], 25) is None, "fora da tabela: None"
print("Exercício 02: todos os testes passaram!")

Exercício 03¶

Escreva lagrange(xs, ys, x), o polinômio interpolador de Lagrange em x:

\[ p(x) = \sum_i y_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}. \]

def lagrange(xs, ys, x):
    """Polinômio interpolador de Lagrange em x."""
    n = len(xs)
    soma = 0.0
    # TODO: para cada i, calcule o produto L (começando em 1) e some ys[i] * L
    return soma


# --- testes (não altere) ---
assert abs(lagrange([1, 2, 4], [2, 3, 1], 3) - 8 / 3) < 1e-12
assert abs(lagrange([1, 2, 4], [2, 3, 1], 4) - 1) < 1e-12, "passa pelos pontos"
assert abs(lagrange([50, 100, 200, 400, 1000], [4.48, 6.40, 9.17, 13.20, 21.61], 300) - 11.232046783625734) < 1e-9
print("Exercício 03: todos os testes passaram!")

Exercício 04¶

Escreva diferencas_divididas(xs, ys), que devolve a lista dos coeficientes \(c_0, c_1, \ldots\) do polinômio de Newton. Use o jeito do capítulo: comece com uma cópia de ys e, para cada ordem, de baixo para cima, troque cada valor pela diferença dividida com o de cima.

diferencas_divididas([1, 2, 4], [2, 3, 1])    # -> [2, 1.0, -0.666...]

def diferencas_divididas(xs, ys):
    """Coeficientes do polinômio de Newton (a primeira linha da tabela)."""
    n = len(xs)
    coef = list(ys)
    # TODO: for ordem in range(1, n): for i in range(n - 1, ordem - 1, -1):
    # coef[i] = (coef[i] - coef[i - 1]) / (xs[i] - xs[i - ordem])
    return coef


# --- testes (não altere) ---
c = diferencas_divididas([1, 2, 4], [2, 3, 1])
assert abs(c[0] - 2) < 1e-12 and abs(c[1] - 1) < 1e-12 and abs(c[2] + 2 / 3) < 1e-12, f"veio {c}"
c = diferencas_divididas([0, 1, 2, 3], [1, 2, 5, 10])
assert abs(c[3]) < 1e-12, "x**2 + 1: a diferença de terceira ordem é zero"
print("Exercício 04: todos os testes passaram!")

Exercício 05¶

Escreva avalia_newton(xs, coef, x), que calcula o polinômio de Newton em x a partir dos coeficientes do ex04:

\[ p(x) = c_0 + c_1(x - x_0) + c_2(x - x_0)(x - x_1) + \cdots \]

Guarde o produto \((x - x_0)(x - x_1)\cdots\) numa variável e vá multiplicando um fator por vez.

def avalia_newton(xs, coef, x):
    """p(x) = c0 + c1 (x - x0) + c2 (x - x0)(x - x1) + ..."""
    p = coef[0]
    produto = 1.0
    # TODO: para k de 1 em diante: multiplique o produto por (x - xs[k - 1]) e some coef[k] * produto
    return p


# --- testes (não altere) ---
assert abs(avalia_newton([1, 2, 4], [2, 1, -2 / 3], 3) - 8 / 3) < 1e-12
assert abs(avalia_newton([0, 1, 2, 3], [1, 1, 1, 0], 5) - 26) < 1e-12, "x**2 + 1 em 5"
print("Exercício 05: todos os testes passaram!")

Exercício 06¶

Computação — a curva de gama de um monitor. O nível digital de um pixel (0 a 255) não é proporcional ao brilho da tela: um pixel em 128 brilha bem menos que a metade de um em 255. O fabricante mede a luminância relativa em alguns níveis:

nível	0	64	128	192	255
luminância	0	0,0478	0,2195	0,5356	1,0

Escreva luminancia(nivel), que interpola a tabela com a lagrange (já escrita).

Depois de passar, compare com a fórmula de gama \((\text{nível}/255)^{2{,}2}\) em 100 e em 30. Onde o polinômio erra mais? Por quê?

def lagrange(xs, ys, x):
    """Polinômio interpolador de Lagrange em x. JÁ ESCRITA."""
    n = len(xs)
    soma = 0.0
    for i in range(n):
        L = 1.0
        for j in range(n):
            if j != i:
                L = L * (x - xs[j]) / (xs[i] - xs[j])
        soma = soma + ys[i] * L
    return soma


def luminancia(nivel):
    """Luminância relativa (0 a 1) de um nível digital (0 a 255), pela tabela."""
    # TODO: as duas listas da tabela e uma chamada da lagrange
    pass


# --- testes (não altere) ---
assert abs(luminancia(128) - 0.2195) < 1e-12, "passa pelo ponto da tabela"
assert abs(luminancia(100) - 0.1276384358517434) < 1e-9
print("Exercício 06: todos os testes passaram!")

Exercício 07¶

Saúde — interpolação inversa. Com a tabela de altura das meninas do capítulo (idade 0, 6, 12, 24 e 36 meses; altura 49,1; 65,7; 74,0; 86,4 e 95,1 cm), a pergunta agora é ao contrário: em que idade a menina típica atinge uma certa altura?

Basta trocar os papéis: interpolar a idade como função da altura. Escreva idade_para_altura(altura_cm) com a lagrange (já escrita).

idade_para_altura(80)    # -> ≈ 17.3 meses

Isso sempre funciona? O que aconteceria com uma tabela em que \(y\) sobe e depois desce?

def lagrange(xs, ys, x):
    """Polinômio interpolador de Lagrange em x. JÁ ESCRITA."""
    n = len(xs)
    soma = 0.0
    for i in range(n):
        L = 1.0
        for j in range(n):
            if j != i:
                L = L * (x - xs[j]) / (xs[i] - xs[j])
        soma = soma + ys[i] * L
    return soma


def idade_para_altura(altura_cm):
    """Idade (meses) em que a menina típica atinge a altura dada: interpolação inversa."""
    idade = [0, 6, 12, 24, 36]
    altura = [49.1, 65.7, 74.0, 86.4, 95.1]
    # TODO: uma chamada da lagrange, com os papéis trocados
    pass


# --- testes (não altere) ---
assert abs(idade_para_altura(74.0) - 12) < 1e-9, "na tabela: 74 cm aos 12 meses"
assert abs(idade_para_altura(80) - 17.268903160032263) < 1e-9
print("Exercício 07: todos os testes passaram!")