Interpolação polinomial

Fórum sobre técnicas matemáticas úteis na preparação olímpica

Interpolação polinomial

Mensagempor ampat em Sábado Fev 27, 2010 9:03 am

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. :wink:

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, x e y; a função y=\varphi(x) não é conhecida mas, procedendo a uma série de medições, estabeleceu-se que a função y=\varphi(x) toma os valores y_{1},y_{2},..., y_{n} quando a variável (suposta independente) x assume os valores x_{1},x_{2}..., x_{n}, 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 y=\varphi(x), sobre a qual apenas conhecemos o valor para n+1 pontos diferentes x_{1},x_{2}..., x_{n} pertencentes a um certo intervalo [a,b]:

\varphi(x_{0}) = y_{0}, ... , \varphi(x_{n}) =y_{n} ;

Propomo-nos, então, a encontrar um polinómio P(x) de grau menor ou igual a n que exprima duma maneira aproximada a relação funcional entre x e y, ou seja, a função \varphi.

É muito natural escolher o polinómio de forma a que tome nos pontos x_{1},x_{2}..., x_{n} os mesmo valores que a função \varphi. Neste caso, estamos perante um problema de 'interpolação' que pode ser formulado na maneira seguinte: encontrar para uma função y=\varphi(x) um polinómio P(x) de grau <=n que tome nos pontos x_{1},x_{2}..., x_{n} os mesmos valores que a função \varphi.

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 n da forma

P(x)=C_{0}(x-x_{1})(x-x_{2})...(x-x_{n}) +\ C_{1}(x-x_{0})(x-x_{2})..(x-x_{n})+\ C_{n}(x-x_{0})(x-x_{1})...(x-x_{n-1})

e determinar os coeficientes C_{0},...\ , C_{n} , de tal forma que sejam verificadas as condições

P(x_{0})=y_{0},\ P(x_{1})=y_{1},\ ...\ ,\ P(x_{n})=y_{n} ,

Façamos então x=x_{i} para i=0,\ ...\ ,n na fórmula do polinómio, sucessivamente; então, em virtude das igualdades P(x_{i})=x_{i}, obtemos o valor de cada coeficiente C_{i} do polinómio através da fórmula seguinte:

C_{0}= \frac{y_{0} }{ (x_{0}-x_{1})(x_{0}-x_{2})...(x_{0}-x_{n}) }\\

C_{1}= \frac{y_{1} }{(x_{1}-x_{0})(x_{1}-x_{2})...(x_{1}-x_{n}) }\\

\ \ \ \ \ \ ..................................\\

C_{n}= \frac{y_{n} }{(x_{n}-x_{0})(x_{n}-x_{1})...(x_{n}-x_{n-1})}\\

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

P(x)= \frac{(x-x_{1})(x-x_{2})...(x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})...(x_{0}-x_{n}) }y_{0}\ +\ \frac{ (x-x_{0})(x-x_{2})..(x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})...(x_{1}-x_{n}) }y_{1}\ +\ ...\ +\ \frac{(x-x_{0})(x-x_{1})...(x-x_{n-1}) }{(x_{n}-x_{0})(x_{n}-x_{1})...(x_{n}-x_{n-1}) }y_{n}
=\sum_{i=0}^{n}{l_{i,n}(x)y_i}

Existe ainda um resultado, que nao vou demonstrar, que diz o seguinte: se \varphi (x) tem uma derivada de ordem (n+1) no segmento[a,b], o erro R(x) cometido substituindo a função \varphi (x) pelo polinómio P(x) verifica a desigualdade:


| R(x)|<| (x-x_{0})(x-x_{1})...(x-x_{n}) | \cdot  \frac{ max|\varphi^{(n+1)} (x)|}{ (n+1)!} (fórmula bastante semelhante à do resto de Lagrange de ordem n 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 x corresponde um único valor da variável y.
Para além disso, vê-se imediatamente que, se nos dados experimentais existirem duas 'entradas', a 'entrada' nº 1 e a 'entrada' nº 2 com o mesmo valor de x, x_{1}=x=x_{2}, temos de analisar dois casos: se as ordenadas correspondentes, y_{1} e y_{2} 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, y_{1}=y_{2}, 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, x e y, que se pensa estarem ligadas por uma relação funcional:

y_{0}=\ 4 para x_{0}=0
y_{1}=\ 6 para x_{1}=1
y_{2}=10 para x_{2}=2


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:

P(x)=C_{0}(x-x_{1})(x-x_{2})\ +\ C_{1}(x-x_{0})(x-x_{2}) \ + \ C_{2}(x-x_{0})(x-x_{1})

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

C_{0}= \frac{y_{0} }{ (x_{0}-x_{1})(x_{0}-x_{2})} =\ 2
C_{1}= \frac{y_{1} }{ (x_{1}-x_{0})(x_{1}-x_{2})} = -6
C_{2}= \frac{y_{2} }{ (x_{2}-x_{0})(x_{2}-x_{1})} =\ 5

Portanto, o nosso polinómio é:

P(x)=2(x-1)(x-2)\ -\ 6(x-0)(x-2) \ + \ 5(x-0)(x-1) = x^2 \ +\ x\ +\ 4



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, y=f(x) a função que pretendemos aproximar por um polinómio P(x) de grau <=n.
Esta função toma nos pontos x_{1},\ x_{2},\ ...\ , x_{n} os valores y_{1},y_{2},\ ...\ , y_{n} respectivamente.
O polinómio P(x), sendo de grau <=n-1, é da forma

P(x)=C_{1}+C_{2}x+ C_{3}x^2 + ...+ C_{n}x^{n-1},

e satisfaz ainda P(x_{i})=y_{i} para i=1,\ ...\ ,n.

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

\begin{bmatrix}
1       & x_{1}  & x_{1}^2 & \cdots  & x_{1}^{n-1}\\ 
1       & x_{2}  & x_{2}^2 & \cdots  & x_{2}^{n-1}\\ 
\vdots  & \vdots & \vdots  & \ddots  & \vdots\\ 
1       & x_{n}  & x_{n}^2 & \cdots  & x_{n}^{n-1}
\end{bmatrix} \begin{bmatrix}
C_{1}\\ 
C_{2}\\ 
\vdots \\
C_{n} 
\end{bmatrix} = \begin{bmatrix}
y_{1}\\ 
y_{2}\\ 
\vdots \\
y_{n} 
\end{bmatrix}

A matriz dos coeficientes deste sistema é uma matriz de Vandermonde V. O sistema tem solução única sse a matriz dos coeficientes fôr não singular
(\ det(V)\neq 0), 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 <=n-1, apenas o polinómio nulo se anula em todos os pontos x_{i} (i=0,...,n). De facto, se um polinómio se anula em todos esses pontos, pode ser factorizado na forma

P(x)= (x-x_{1})(x-x_{2})...(x-x_{n}) Q(x),

onde Q(x) é outro polinómio, pelo que P ou é identicamente nulo (se Q(x)\equiv 0), ou é de grau >=n (se Q(x)\neq0).
última vez editado por ampat s Quinta Jan 20, 2011 5:55 pm, editado 8 vezes no total
ampat
bottom-Quark!
bottom-Quark!
 
Mensagens: 68
Registado: Sábado Dez 13, 2008 10:50 am
Localização: IST, Lisboa / Oeiras

Re: Interpolação polinomial

Mensagempor jap em Sábado Fev 27, 2010 10:01 am

Obrigado, André! :friends:

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

Bt the way, alguém sabe como é que uma calculadora de bolsa calcula as funções trigonométricas? :roll:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Interpolação polinomial

Mensagempor ampat em Sábado Fev 27, 2010 3:36 pm

jap Escreveu: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? :?:
ampat
bottom-Quark!
bottom-Quark!
 
Mensagens: 68
Registado: Sábado Dez 13, 2008 10:50 am
Localização: IST, Lisboa / Oeiras

Re: Interpolação polinomial

Mensagempor Bruno Oliveira em Sábado Fev 27, 2010 7:55 pm

Excelente post!!

Está muito interessante :hands:

O pessoal de MEFT faz as coisas a direito :P 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 :shock: ) 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 :D .

Bruno
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Interpolação polinomial

Mensagempor ampat em Sábado Fev 27, 2010 8:02 pm

Bruno Oliveira Escreveu:Excelente post!!

Está muito interessante :hands:

O pessoal de MEFT faz as coisas a direito :P 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 :shock: ) 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 :D .

Bruno


Definitivamente muito bom o que escreveste Bruno. Por acaso, nunca vi ninguém a acabar um exame com -2 :lol:
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.
última vez editado por ampat s Sábado Fev 27, 2010 8:23 pm, editado 2 vezes no total
ampat
bottom-Quark!
bottom-Quark!
 
Mensagens: 68
Registado: Sábado Dez 13, 2008 10:50 am
Localização: IST, Lisboa / Oeiras

Re: Interpolação polinomial

Mensagempor jap em Sábado Fev 27, 2010 8:19 pm

ampat Escreveu:
jap Escreveu: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? :?:
:no
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Interpolação polinomial

Mensagempor Bruno Oliveira em Sábado Fev 27, 2010 9:28 pm

ampat Escreveu:
Bruno Oliveira Escreveu:Excelente post!!

Está muito interessante :hands:

O pessoal de MEFT faz as coisas a direito :P 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 :shock: ) 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 :D .

Bruno


Definitivamente muito bom o que escreveste Bruno. Por acaso, nunca vi ninguém a acabar um exame com -2 :lol:
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... :roll: 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... :lol: 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... :wink: 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? :roll:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Interpolação polinomial

Mensagempor ampat em Sábado Fev 27, 2010 10:13 pm

Bruno Oliveira Escreveu: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 n 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 n se torna bastante pequeno.
ampat
bottom-Quark!
bottom-Quark!
 
Mensagens: 68
Registado: Sábado Dez 13, 2008 10:50 am
Localização: IST, Lisboa / Oeiras

Re: Interpolação polinomial

Mensagempor Bruno Oliveira em Sábado Fev 27, 2010 10:21 pm

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 :roll:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Interpolação polinomial

Mensagempor jap em Sábado Fev 27, 2010 11:37 pm

Bruno Oliveira Escreveu: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 :roll:


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 \sin(x) com uma precisão de 8 casas decimais? :roll:

Experimentem com interpolação de Lagrange... :confident:

PS: O cálculo com séries de Taylor seria muito ineficiente... :mock:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Interpolação polinomial

Mensagempor Bruno Oliveira em Sábado Fev 27, 2010 11:59 pm

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

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 \displaystyle sin(x) com precisão de 8 d.p. amanhã :D De facto o uso da interpolação parece promissor :wink:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Interpolação polinomial

Mensagempor jap em Domingo Fev 28, 2010 12:16 am

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... :roll:

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! :hands:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Interpolação polinomial

Mensagempor RicardoCampos em Domingo Fev 28, 2010 4:04 pm

Pois, eu na realidade também pensava que era com o polinómio de Taylor... Muito melhor assim :D
\emph{Ricardo Campos}\in \delta \bigcap q\overline{q}
O Matemático-Físico de 2008
Avatar do utilizador
RicardoCampos
top-Quark!
top-Quark!
 
Mensagens: 1280
Registado: Sexta Jun 01, 2007 3:49 pm
Localização: Figueira da Foz/Coimbra/DMUC/DFUC, Paris... E agora Zurique!

Re: Interpolação polinomial

Mensagempor jap em Domingo Mar 07, 2010 11:22 pm

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... :lol:
Podem confirmar! :wink:

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
   
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra


Voltar para Técnicas matemáticas

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 2 visitantes