Interpolação polinomial

[ampat]

Não sei bem se isto é muito útil para alguma coisa na Física (Física Experimental?), mas acho que não se perde nada em colocar este tópico aqui. Talvez não esteja tudo 100% matematicamente correcto, mas acho que se percebe.

Bem, comecemos.

O que é a interpolação polinomial ?

Suponhamos que, ao estudar um certo fenómeno (movimento de uma sistema mecânico, experiências ópticas, etc.), se verificou (ou se pensa) existir uma dependência funcional entre duas grandezas, e ; a função não é conhecida mas, procedendo a uma série de medições, estabeleceu-se que a função toma os valores quando a variável (suposta independente) assume os valores , rspectivamente.

Procura-se então, após esta fase experimental, uma relação funcional o mais simples possível (um polinómio, por exemplo) que se ajuste aos dados experimentais obtidos. Duma forma mais geral, o problema em questão pode-se colocar nos seguintes termos:

Suponha-se a existência de uma função , sobre a qual apenas conhecemos o valor para n+1 pontos diferentes pertencentes a um certo intervalo :



Propomo-nos, então, a encontrar um polinómio de grau menor ou igual a que exprima duma maneira aproximada a relação funcional entre e , ou seja, a função .

É muito natural escolher o polinómio de forma a que tome nos pontos os mesmo valores que a função . Neste caso, estamos perante um problema de 'interpolação' que pode ser formulado na maneira seguinte: encontrar para uma função um polinómio de grau que tome nos pontos os mesmos valores que a função .

Para resolver este problema, existem vários métodos, uns mais precisos que outros. Devemos, porém, ter sempre presente que há um preço a pagar por uma maior precisão na aproximação obtida, a saber, o tempo de cálculo requerido para a resolução do problema.
Neste pequeno texto introdutório, apenas vou introduzir de forma rápida um método de ataque ao problema conhecido como 'Fórmula de interpolação de Lagrange'. Se tiver um tempinho, mais tarde escrevo sobre as outras fórmulas que existem.


Fórmula de interpolação de Lagrange

Este método consiste, essencialmente, em considerar um polinómio de grau da forma



e determinar os coeficientes , de tal forma que sejam verificadas as condições



Façamos então para na fórmula do polinómio, sucessivamente; então, em virtude das igualdades , obtemos o valor de cada coeficiente do polinómio através da fórmula seguinte:



Substituindo estes coeficientes na fórmula do polinómio, obtemos a chamada Fórmula de interpolação de Lagrange:



Existe ainda um resultado, que nao vou demonstrar, que diz o seguinte: se tem uma derivada de ordem no segmento, o erro cometido substituindo a função pelo polinómio verifica a desigualdade:


(fórmula bastante semelhante à do resto de Lagrange de ordem da fórmula de Taylor)

Note-se que, neste método, a relação entre as duas grandezas tem de ser funcional, ou seja, a cada valor da variável corresponde um único valor da variável .
Para além disso, vê-se imediatamente que, se nos dados experimentais existirem duas 'entradas', a 'entrada' nº e a 'entrada' nº com o mesmo valor de , , temos de analisar dois casos: se as ordenadas correspondentes, e forem diferentes a relação entre x e y não é funcional, pelo que a fórmula de Lagrange deixa de ser aplicável; caso as ordenadas sejam iguais, , apenas temos dados repetidos e a eliminação de uma das entradas dos dados experimentais permite continuar o processo de interpolação.

Exemplo:

Enunciado

Uma experiência forneceu os seguintes resultados para duas grandezas físicas, e , que se pensa estarem ligadas por uma relação funcional:

para
para
para


Exprimir esta relação duma maneira aproximada, através de um polinómio do segundo grau.

Resolução:

O polinómio procurado tem a forma seguinte:



Aplicando a fórmula para o cálculo dos coeficientes, obtemos:





Portanto, o nosso polinómio é:





Matriz de Vandermonde

Este método baseia-se em cálculo matricial, mas é pouco eficiente computacionalmente, porque não dá uma fórmula explicita para o polinómio interpolador.

Seja, então, a função que pretendemos aproximar por um polinómio de grau .
Esta função toma nos pontos os valores respectivamente.
O polinómio , sendo de grau , é da forma



e satisfaz ainda para .

Temos, por isso, de resolver um sistema de equações a incognitas (os coeficientes do polinómio). Este sistema pode ser representado matricialmente na forma



A matriz dos coeficientes deste sistema é uma matriz de Vandermonde . O sistema tem solução única sse a matriz dos coeficientes fôr não singular
(), ou seja, sse o sistema homogéneo tiver como solução apenas o polinómio identicamente nulo . Isto equivale a afirmar que, de entre todos os polinómios de grau , apenas o polinómio nulo se anula em todos os pontos . De facto, se um polinómio se anula em todos esses pontos, pode ser factorizado na forma



onde é outro polinómio, pelo que ou é identicamente nulo (se ), ou é de grau (se ).

[jap]

Obrigado, André!

E agora lanço o desafio aos quarkianos de implementarem o algoritmo da interpolação de lagrange num pequenino programa Python.

Bt the way, alguém sabe como é que uma calculadora de bolsa calcula as funções trigonométricas?

[ampat]

Bt the way, alguém sabe como é que uma calculadora de bolsa calcula as funções trigonométricas?

Com uma aproximação por um polinómio de Taylor?

[Bruno Oliveira]

Excelente post!!

Está muito interessante

O pessoal de MEFT faz as coisas a direito Não é como em Civil onde as cadeiras de Programação têm como objectivo, peço agora desculpa pelo calão, lixar os alunos em vez de lhes ensinarem métodos numéricos engraçados(onde é que já se viu gente a acabar um exame final com -2 V ) Grande parte do que sei de programação deve-se ao Python, às minhas explorações do Excel para resolver problemas computacionais de mêcanica e ao Quark! Parabéns pelo post .

Bruno

[ampat]

Excelente post!!

Está muito interessante

O pessoal de MEFT faz as coisas a direito Não é como em Civil onde as cadeiras de Programação têm como objectivo, peço agora desculpa pelo calão, lixar os alunos em vez de lhes ensinarem métodos numéricos engraçados(onde é que já se viu gente a acabar um exame final com -2 V ) Grande parte do que sei de programação deve-se ao Python, às minhas explorações do Excel para resolver problemas computacionais de mêcanica e ao Quark! Parabéns pelo post .

Bruno

Definitivamente muito bom o que escreveste Bruno. Por acaso, nunca vi ninguém a acabar um exame com -2
Sim, realmente até pode ser verdade, mas nós também não aprendemos assim tantos métodos numéricos. Em Programação, apenas nos ensinaram os métodos de Runge Kutta e o de Euler-Cromer.
Este método de interpolação foi uma pequena curiosidade que vi em livros de Cálculo/AL. Acho que só para o ano é que damos métodos numérico-matemáticos a sério na cadeira de Matemática Computacional.

Vou tentar ainda colocar o método de Newton para completar o post. Penso que existem mais dois métodos, pelo menos, mas o grau de pormenor desses métodos começa a entrar em demasia no pormenor matemático indesejável para post.

[jap]

Bt the way, alguém sabe como é que uma calculadora de bolsa calcula as funções trigonométricas?

Com uma aproximação por um polinómio de Taylor?

[Bruno Oliveira]

Excelente post!!

Está muito interessante

O pessoal de MEFT faz as coisas a direito Não é como em Civil onde as cadeiras de Programação têm como objectivo, peço agora desculpa pelo calão, lixar os alunos em vez de lhes ensinarem métodos numéricos engraçados(onde é que já se viu gente a acabar um exame final com -2 V ) Grande parte do que sei de programação deve-se ao Python, às minhas explorações do Excel para resolver problemas computacionais de mêcanica e ao Quark! Parabéns pelo post .

Bruno

Definitivamente muito bom o que escreveste Bruno. Por acaso, nunca vi ninguém a acabar um exame com -2
Sim, realmente até pode ser verdade, mas nós também não aprendemos assim tantos métodos numéricos. Em Programação, apenas nos ensinaram os métodos de Runge Kutta e o de Euler-Cromer.
Este método de interpolação foi uma pequena curiosidade que vi em livros de Cálculo/AL. Acho que só para o ano é que damos métodos numérico-matemáticos a sério na cadeira de Matemática Computacional.

Vou tentar ainda colocar o método de Newton para completar o post. Penso que existem mais dois métodos, pelo menos, mas o grau de pormenor desses métodos começa a entrar em demasia no pormenor matemático indesejável para post.

Pois, nós na nossa cadeira, simplesmente não demos métodos numéricos, pelo menos não aplicados a problemas físicos práticos... O algoritmo mais avançado de que falámos, foi o Mergesort que podendo ser útil de vez em quando não tem nada de especial...

A cadeira de MC deve ser bastante interessante, pelo menos tem ar disso... Por outro lado, outra coisa que acho muito interessante é resolver os problemas do livro "Mecânica vectorial para Engenheiros", Beer, F.P., recorrendo a programação; tem problemas especialmente feitos para isso. Aí nesses problemas, testa-se bastante a capacidade de racíocinio algoritmico, mais do que se possa pensar... E envolve sempre uma ligação directa com Engª o que é um ponto a favor dessa mesma abordagem para aprender em simultâneo desenvolvimento de algoritmos/Mecânica, imho

Prof. será que as calculadoras não podem usar uma interpolação a partir de uma tabela de valores fixos (tal como nas tabelas antigas que tinham os valores para vários ângulos editados em forma de livros), e aproximando-se de um dado ângulo, com uma margem de erro que seja apenas notória numa casa decimal que seja desprezável para efeitos práticos?

[ampat]

Prof. será que as calculadoras não podem usar uma interpolação a partir de uma tabela de valores fixos (tal como nas tabelas antigas que tinham os valores para vários ângulos editados em forma de livros), e aproximando-se de um dado ângulo, com uma margem de erro que seja apenas notória numa casa decimal que seja desprezável para efeitos práticos?

Pois é... Eu nem pensei nisso porque me parecia muito mais eficiente calcular através do polinómio de Taylor. Mas, realmente, olhando para a desigualdade a que obedece o resto de ordem da interpolação para as funções contínuas, vê-se imediatamente que, se tivermos suficientes valores tabelados destas funções, o resto de ordem se torna bastante pequeno.

[Bruno Oliveira]

Sim, acho que neste caso, o das calculadoras de bolso, pode ser isto que se aplica, dado que, creio eu, basta ter tabelados os valores mais conhecidos, do género, 0º, 30º, 45º, 60º, 90º,180º, 270º e 360º. Tendo esta gama de valores tabelada, e eventualmente alguns valores intermédios, deve ser relativamente simples realizar uma interpolação para chegar a qualquer valor dado como input pelo utilizador

[jap]

Sim, acho que neste caso, o das calculadoras de bolso, pode ser isto que se aplica, dado que, creio eu, basta ter tabelados os valores mais conhecidos, do género, 0º, 30º, 45º, 60º, 90º,180º, 270º e 360º. Tendo esta gama de valores tabelada, e eventualmente alguns valores intermédios, deve ser relativamente simples realizar uma interpolação para chegar a qualquer valor dado como input pelo utilizador

Sim e basta apenas aramzenar em memória alguns valores do sin entre 0 e 90º para se conseguir, por interpolação, calcular com boa precisão as funções trigonométricas.

Sabem quantos valores do seno é que é preciso armazenar na memória não volátil de uma calculadora para calcular o ) com uma precisão de 8 casas decimais?

Experimentem com interpolação de Lagrange...

PS: O cálculo com séries de Taylor seria muito ineficiente...

[Bruno Oliveira]

Podemos confirmar os valores obtidos pela interpolação com os valores obtidos a partir de uma CASIO "truncados" até à 8ª casa decimal?

ETA: Ainda não tive tempo de programar nada...mas como estive de volta do EXCEL a tarde toda, pode ser que tente calcular o polinómio que nos dá valores de com precisão de 8 d.p. amanhã De facto o uso da interpolação parece promissor

[jap]

Se fizeres um programa para a interpolação podes usar a função sin para calcular esses valores e comparar com o resultado da interpolação. On então usa a tua CASIO. Na realidade, é provável que uma calculadora não use interpolação mas sim o algoritmo CORDIC... Depende da calculadora...

PS: Se tiverem curiosidade espreitem na wikipedia o algoritmo CORDIC que calcula as funções trigonométricas só com operações muito simples, adições, subtracções e shifts de bits: espectacular!

[RicardoCampos]

Pois, eu na realidade também pensava que era com o polinómio de Taylor... Muito melhor assim

[jap]

Just for fun...

A minha implementação pitónica do algoritmo da interpolação de Lagrange mostra que memorizando apenas 8 valores da função sin entre 0 e pi/2, se consegue calcular o sin de qualquer ângulo com a precisão de 7 casas decimais...
Podem confirmar!

Código: Seleccionar Todos

#!/usr/bin/env python
"""
Lagrange interpolation
"""

from math import *


def table(f,a,b,n):
    "Sets up a table of n equidistant points of (x,f(x)) in [a,b]"
    h = (b-a)/float(n-1)
    x = a
    t = []
    for i in range(n):
        t.append((x,f(x)))
        x += h
    return t

def lagpoly(t,x):
    s = 0
    n = len(t)
    for i in range(n):
        term = t[i][1]
        for j in range(n):
            if j != i:
                term *= (x-t[j][0])/(t[i][0]-t[j][0])
        s += term
    return s


if __name__ == "__main__":

    f = sin
    t = table(f,0,pi/2,8)
    x = 0
    difmax = 0
    while x <= pi/2:
        print x,sin(x),lagpoly(t,x)
        difmax = max(difmax,abs(sin(x)-lagpoly(t,x)))
        x += 0.01
    print "maximum error is",difmax