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

De Física Computacional
Ir para navegação Ir para pesquisar
(Criou página com 'Baseado no fato de que sobre <math>N</math> pontos <math>(X_1,Y_1), (X_2,Y_2), \cdots, (X_N,Y_N)</math> passa um ''único'' polinômio de grau <math>N-1</math>, o '''Polinômio d...')
 
Sem resumo de edição
Linha 1: Linha 1:
== Polinômios de Lagrange ==
Baseado no fato de que sobre <math>N</math> pontos <math>(X_1,Y_1), (X_2,Y_2), \cdots, (X_N,Y_N)</math> passa um ''único'' polinômio de grau <math>N-1</math>, o '''Polinômio de Lagrange''' pode ser usado como fórmula de interpolação ou extrapolação:
Baseado no fato de que sobre <math>N</math> pontos <math>(X_1,Y_1), (X_2,Y_2), \cdots, (X_N,Y_N)</math> passa um ''único'' polinômio de grau <math>N-1</math>, o '''Polinômio de Lagrange''' pode ser usado como fórmula de interpolação ou extrapolação:


Linha 12: Linha 14:
</math>
</math>


é claramente um polinômio de grau <math>\;N-1</math> em <math>\;x</math>.
é um polinômio de grau <math>\;N-1</math> em <math>\;x</math>.
Tendo em vista que <math>L_i(X_j)=\delta_{i,j}\;,</math> onde o delta de Kronecker
Tendo em vista que <math>L_i(X_j)=\delta_{i,j}\;,</math> onde o delta de Kronecker
   
   
Linha 23: Linha 25:




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 <math>\;X</math>, deve ser empregado.
Por exemplo, digamos que temos uma tabela com 100 pontos <math>\;\{(X_i,Y_i)\}</math>. Se desejamos estimar o valor de <math>\;Y</math> no interior da região <math>[X_1,\; X_N]</math>, 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 <math>(X_{i-1},Y_{i-1}),\; (X_i,Y_i),\; (X_{i+1},Y_{i+1})</math> e<math>\;(X_{i+2},Y_{i+2})</math>.




Contudo, devemos notar que, embora a interpolação seja contínua nas interfaces das regiões, a continuidade das derivadas 1<sup>a</sup> e 2<sup>a</sup> não é garantida. Em situações em que estas propriedades importam, outras aproximações devem ser adotadas (veja, por exemplo, [[Spline Cúbico]]).
== Exemplo 1 ==
 
[[Image:lagrangen2.png|right|frame|Fórmula de Lagrange para N=2.]]
 
Para exemplificar a fórmula de Lagrange, consideramos primeiramente uma reta que passa pelos pontos <math>(X_1,Y_1) = (1,9)</math> e <math>(X_2,Y_2) = (2,13)</math>, tendo assim <math>N = 2</math>. Aplicando a fórmula de Lagrange, temos
 
:<math>L_1 = \frac{x-X_2}{X_1-X_2} = \frac{x-2}{1-2} = -(x-2)</math>
e
:<math>L_2 = \frac{x-X_1}{X_2-X_1} = \frac{x-1}{2-1} = (x-1)</math>,
assim, o polinômio de Lagrange que passa pelos pontos desejados é dado por:
:<math>P(x)=\sum_{i=1}^N Y_i L_i(x) = Y_1L_1 + Y_2L_2 = 9(-x+2) + 13(x-1) = 4x + 5 </math>.
 
Note que substituindo na equação acima, <math>P(1) = 9</math> e <math>P(2) = 13</math>.
 
== Exemplo 2 ==
 
[[Image:lagrangen3.png|right|frame|Fórmula de Lagrange para N=3.]]
 
Verificando a fórmula de Lagrange para <math>N = 3</math>. Suponhamos que desejamos encontrar qual é o polinômio que passa pelos pontos  <math>(X_1,Y_1) = (2,4)</math>, <math>(X_2,Y_2) = (3,9)</math> e <math>(X_3,Y_3) = (6,36)</math>. Temos que:
 
:<math>L_1 = \left(\frac{x-X_2}{X_1-X_2}\right) \left(\frac{x-X_3}{X_1-X_3}\right) = \left(\frac{x-3}{2-3}\right) \left(\frac{x-6}{2-6}\right) = \frac{x^2-9x+18}{4}</math>,
 
:<math>L_2 = \left(\frac{x-X_1}{X_2-X_1}\right) \left(\frac{x-X_3}{X_2-X_3}\right) = \left(\frac{x-2}{3-2}\right) \left(\frac{x-6}{3-6}\right) = -\frac{x^2-8x+12}{3}</math>
 
e
 
:<math>L_3 = \left(\frac{x-X_1}{X_3-X_1}\right) \left(\frac{x-X_2}{X_3-X_2}\right) = \left(\frac{x-2}{6-2}\right) \left(\frac{x-3}{6-3}\right) = \frac{x^2-5x+6}{12}</math>,
 
assim
 
 
:<math>P(x)=\sum_{i=1}^N Y_i L_i(x) = Y_1L_1 + Y_2L_2 + Y_3L_3 = 4\frac{x^2-9x+18}{4} - 9\frac{x^2-8x+12}{3} + 36\frac{x^2-5x+6}{12} = x^2 </math>.
 
 
== Exemplo 3 ==
 
Para ilustrar graficamente o método da fórmula de Lagrange, usaremos um exemplo com <math>N=4</math>. Considerando os quatro pontos <math>(X_1,Y_1) = (-1,5)</math>, <math>(X_2,Y_3) = (1,2)</math>, <math>(X_3,Y_3) = (-3,5)</math> e <math>(X_4,Y_4) = (7,4)</math>, as equações <math>L_i</math> ficam
 
:<math>L_1 = -\frac{1}{64}(x^3-11x^2+31x-21)</math>,
 
:<math>L_2 = \frac{1}{24}(x^3-9x^2+11x+21)</math>,
 
:<math>L_3 = -\frac{1}{32}(x^3-7x^2-x+7)</math>
 
e
 
:<math>L_4 = \frac{1}{192}(x^3-3x^2-x+3)</math>.
O gráfico abaixo mostra os quatro pontos <math>(X_i,Y_i)</math>, as curvas <math>L_iY_i</math> e a curva final <math>P(x)</math>. Lembre-se que <math>P(x)</math> é a curva gerada pela soma dos polinômios <math>L_iY_i</math>. Note que a curva <math>L_1Y_1</math> passa pelo ponto <math>(X_1,Y_1)</math>, assim como as demais e a curva <math>P(x)</math> passa por todos os pontos.
 
[[Imagem:lagrange.png|800px]]
 
 
 
== 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 <math>{X_i,Y_i}</math>, devolva um polinômio <math>P(x)</math> 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 <math>L_i(x)</math>) onde cada um deles é construído como um produto de N-1 termos; ao todo <math>N^2</math> cálculos para cada ponto x (isto fica como exercício a partir da fórmula
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.


Para concluir esta este assunto, deve-se notar que a implementação numérica do polinômio de Lagrange é extremamente complicada. Como exercício, deve ser tentada a construção de uma função que calcule <math>\;P(x)</math>, a partir da fórmula acima.
Para deduzirmos esta fórmula de recorrência, começamos  aproximando cada intervalo por um valor constante. Podemos representar esta aproximação por
Por isto, o algorítmo de Neville é de grande valia na realização desta tarefa.
<math>P_1(x)=Y_1,\; P_2(x)=Y_2,\; \cdots\,\; P_N(x)=Y_N</math>.  
Se aproximarmos 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 <math>[X_i,\;X_{i+1}]</math>, denotamos por <math>P_{12}(x),\;P_{23}(x),\; \cdots,\; P_{N-1,N}(x)</math>, onde <math>P_{i,i+1}(x)\;</math>é o polinômio que passa exatamente sobre
<math>P_1(x)=Y_1,\; P_2(x)=Y_2,\; \cdots\,\; P_N(x)=Y_N</math>. Melhorando a descrição, empregando agora uma aproximação linear em cada intervalo <math>[X_i,\;X_{i+1}]</math>, denotamos por <math>P_{12}(x),\;P_{23}(x),\; \cdots,\; P_{N-1,N}(x)</math>, onde <math>P_{i,i+1}(x)\;</math>é o polinômio que passa exatamente sobre
<math>(X_i,Y_i)\;</math>e<math>\;(X_{i+1},Y_{i+1})</math>:
<math>(X_i,Y_i)\;</math>e<math>\;(X_{i+1},Y_{i+1})</math>:


Linha 48: Linha 107:


Isto sugere que há uma relação entre os polinômios de ordem <math>\;n</math> com os de ordem <math>\;n+1</math>.
Isto sugere que há uma relação entre os polinômios de ordem <math>\;n</math> com os de ordem <math>\;n+1</math>.
Para verificar isto, vamos considerar, agora, uma parábola passando extamente sobre
Para verificar isto, vamos considerar, agora, uma parábola passando exatamente sobre
<math>(X_i,Y_i)\;,(X_{i+1},Y_{i+1})</math> e<math>\;(X_{i+2},Y_{i+2})</math>, que denotaremos por,<math>\;P_{i,i+1,i+2}(x)</math>:
<math>(X_i,Y_i)\;,(X_{i+1},Y_{i+1})</math> e<math>\;(X_{i+2},Y_{i+2})</math>, que denotaremos por,<math>\;P_{i,i+1,i+2}(x)</math>:


Linha 108: Linha 167:
D^{(2)}_{k,i}(x)=P_{i,i+1,\cdots,i+k}(x)-P_{i+1,i+2,\cdots,i+k}(x)\;.
D^{(2)}_{k,i}(x)=P_{i,i+1,\cdots,i+k}(x)-P_{i+1,i+2,\cdots,i+k}(x)\;.
</math>
</math>


Ao invés de se gerar <math>\;P(x)</math> a partir da relação de recorrência para <math>P_{i,i+1,\cdots,i+k}(x)</math>, pode-se utilizar as equações acima e obter relações de recorrência para <math>\;D^{(1)} \mbox{ e } D^{(2)}</math>. No final, obtemos <math>\;P(x)</math> a partir destas quantidades. Este desenvolvimento é deixado como exercício.
Ao invés de se gerar <math>\;P(x)</math> a partir da relação de recorrência para <math>P_{i,i+1,\cdots,i+k}(x)</math>, pode-se utilizar as equações acima e obter relações de recorrência para <math>\;D^{(1)} \mbox{ e } D^{(2)}</math>. No final, obtemos <math>\;P(x)</math> 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 <math>\;\{X_i\}</math> serem igualmente espaçados. Portanto, as fórmulas apresentadas aqui podem ser aplicadas em situações bastante gerais.
É importante notar que em nenhum ponto da discussão foi evocada a necessidade dos pontos <math>\;\{X_i\}</math> serem igualmente espaçados. Portanto, as fórmulas apresentadas aqui podem ser aplicadas em situações bastante gerais.
Linha 117: Linha 174:
----
----


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 <math>\;X</math>, deve ser empregado.
Por exemplo, digamos que temos uma tabela com 100 pontos <math>\;\{(X_i,Y_i)\}</math>. Se desejamos estimar o valor de <math>\;Y</math> no interior da região <math>[X_1,\; X_N]</math>, 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 <math>(X_{i-1},Y_{i-1}),\; (X_i,Y_i),\; (X_{i+1},Y_{i+1})</math> e<math>\;(X_{i+2},Y_{i+2})</math>.


Voltar para o índice de [[Métodos computacionais]].
Contudo, devemos notar que, embora a interpolação seja contínua nas interfaces das regiões, a continuidade das derivadas 1<sup>a</sup> e 2<sup>a</sup> não é garantida. Em situações em que estas propriedades importam, outras aproximações devem ser adotadas (veja, por exemplo, [[Spline Cúbico]]).
 
----

Edição das 13h07min de 14 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] é 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).