Fórmula de Lagrange: mudanças entre as edições

De Física Computacional
Ir para navegação Ir para pesquisar
Sem resumo de edição
Sem resumo de edição
 
Linha 89: Linha 89:
geral do <math>P(x)</math>).
geral do <math>P(x)</math>).


O Algoritmo de Neville [http://www.physics.utah.edu/~detar/phys6720/handouts/interpolation/interpolation/node4.html] é muito útil na realização desta tarefa.Ao final, veremos que o polinômio interpolador de grau n pode ser reconstruído com polinômios de grau n-1. Este processo gera uma fórmula de recorrência,  que é um recurso  bastante comum em algoritmos computacionais.  
O Algoritmo de Neville [http://www.physics.utah.edu/~detar/phys6720/handouts/interpolation/interpolation/node4.html], [[Implementação do algoritmo de Neville]], é muito útil na realização desta tarefa.Ao final, veremos que o polinômio interpolador de grau n pode ser reconstruído com polinômios de grau n-1. Este processo gera uma fórmula de recorrência,  que é um recurso  bastante comum em algoritmos computacionais.  


Para deduzirmos esta fórmula de recorrência, começamos  aproximando cada intervalo por um valor constante. Podemos representar esta aproximação por
Para deduzirmos esta fórmula de recorrência, começamos  aproximando cada intervalo por um valor constante. Podemos representar esta aproximação por

Edição atual tal como às 07h47min de 25 de outubro de 2011

Polinômios de Lagrange

Baseado no fato de que sobre pontos passa um único polinômio de grau , o Polinômio de Lagrange pode ser usado como fórmula de interpolação ou extrapolação:

onde

é um polinômio de grau em . Tendo em vista que onde o delta de Kronecker

é fácil verificar que, de fato,. Assim, pode ser empregado para se estimar o valor de em pontos não tabulados.



Exemplo 1

Fórmula de Lagrange para N=2.

Para exemplificar a fórmula de Lagrange, consideramos primeiramente uma reta que passa pelos pontos e , tendo assim . Aplicando a fórmula de Lagrange, temos

e

,

assim, o polinômio de Lagrange que passa pelos pontos desejados é dado por:

.

Note que substituindo na equação acima, e .

Exemplo 2

Fórmula de Lagrange para N=3.

Verificando a fórmula de Lagrange para . Suponhamos que desejamos encontrar qual é o polinômio que passa pelos pontos , e . Temos que:

,

e

,

assim


.


Exemplo 3

Para ilustrar graficamente o método da fórmula de Lagrange, usaremos um exemplo com . Considerando os quatro pontos , , e , as equações ficam

,
,

e

.

O gráfico abaixo mostra os quatro pontos , as curvas e a curva final . Lembre-se que é a curva gerada pela soma dos polinômios . Note que a curva passa pelo ponto , assim como as demais e a curva passa por todos os pontos.

Lagrange.png


Numericamente

Na prática, a implementação numérica do polinômio de Lagrange é complicada. Computacionalmente não é possível fazer um programa geral para interpolação de ordem arbitrária, isto é fazer um programa que, com os N pontos de entrada , devolva um polinômio interpolador de grau N. Isto envolve computação simbólica (do tipo utilizada em programas proprietários como o Mathematica, Maple, ou livres como Maxima). Por outro lado a implementação numérica do método na força bruta envolve um duplo laço de ordem N: devem ser somados N termos (os ) onde cada um deles é construído como um produto de N-1 termos; ao todo cálculos para cada ponto x (isto fica como exercício a partir da fórmula geral do ).

O Algoritmo de Neville [1], Implementação do algoritmo de Neville, é muito útil na realização desta tarefa.Ao final, veremos que o polinômio interpolador de grau n pode ser reconstruído com polinômios de grau n-1. Este processo gera uma fórmula de recorrência, que é um recurso bastante comum em algoritmos computacionais.

Para deduzirmos esta fórmula de recorrência, começamos aproximando cada intervalo por um valor constante. Podemos representar esta aproximação por . Melhorando a descrição, empregando agora uma aproximação linear em cada intervalo , denotamos por , onde é o polinômio que passa exatamente sobre e:

Vemos que pode ser escrito como:

Isto sugere que há uma relação entre os polinômios de ordem com os de ordem . Para verificar isto, vamos considerar, agora, uma parábola passando exatamente sobre e, que denotaremos por,:

Fatorando e somando e subtraindo , obtemos:

onde

Note que o último termo desta expressão corresponde àquele que foi subtraído após seu termo de sinal contrário ter sido somado à expressão que levou a na equação para. Rearranjando os termos acima, encontramos:

Substituindo este resultado na equação para, obtemos finalmente:

Assim, notamos que, de fato, há uma relação de recorrência bastante simples entre os polinômios que envolvem e pontos, cuja forma geral é dada por:

Por ser muito mais simples de se implementar numericamente do que a expressão original para , é esta relação de recorrência que é, de fato, utilizada em cálculos numéricos. Os erros cometidos podem ser estimados calculando-se as diferenças entre as diferentes ordens do polinômio:

e

Ao invés de se gerar a partir da relação de recorrência para , pode-se utilizar as equações acima e obter relações de recorrência para . No final, obtemos a partir destas quantidades. Este desenvolvimento é deixado como exercício.

É importante notar que em nenhum ponto da discussão foi evocada a necessidade dos pontos serem igualmente espaçados. Portanto, as fórmulas apresentadas aqui podem ser aplicadas em situações bastante gerais.


Como discutido na seção Interpolação e extrapolação, é desaconselhável o uso de polinômios de grau elevado. Por isto, apenas um pequeno subconjunto dos valores tabulados, nas vizinhanças do ponto de interesse , deve ser empregado. Por exemplo, digamos que temos uma tabela com 100 pontos . Se desejamos estimar o valor de no interior da região , ao invés de construir um polinômio de grau 99, podemos, por exemplo, dividir o espaço em 25 sub-regiões e usar polinômios cúbicos em cada uma delas, utilizando apenas e.

Contudo, devemos notar que, embora a interpolação seja contínua nas interfaces das regiões, a continuidade das derivadas 1a e 2a não é garantida. Em situações em que estas propriedades importam, outras aproximações devem ser adotadas (veja, por exemplo, Spline cúbico).