Fórmula de Lagrange

De Física Computacional
Ir para: navegação, pesquisa

Tabela de conteúdo

Polinômios de Lagrange

Baseado no fato de que sobre N pontos (X_1,Y_1), (X_2,Y_2), \cdots, (X_N,Y_N) passa um único polinômio de grau N − 1, o Polinômio de Lagrange pode ser usado como fórmula de interpolação ou extrapolação:


P(x)=\sum_{i=1}^N Y_i L_i(x)

onde


L_i(x)=\prod_{j=1,j\ne i}^N\frac{x-X_j}{X_i-X_j}=\frac{x-X_1}{X_i-X_1}\cdots\frac{x-X_{i-1}}{X_i-X_{i-1}}
\frac{x-X_{i+1}}{X_i-X_{i+1}}\cdots\frac{x-X_N}{X_i-X_N}

é um polinômio de grau \;N-1 em \;x. Tendo em vista que L_i(X_j)=\delta_{i,j}\;, onde o delta de Kronecker

\delta_{ij} = \left\{\begin{matrix} 
1, & \mbox{se } i=j  \\ 
0, & \mbox{se } i \ne j \end{matrix}\right.

é fácil verificar que, de fato,\;P(X_i)=Y_i. Assim,\;P(x) pode ser empregado para se estimar o valor de \;Y(x) em pontos \;x 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 (X1,Y1) = (1,9) e (X2,Y2) = (2,13), tendo assim N = 2. Aplicando a fórmula de Lagrange, temos

L_1 = \frac{x-X_2}{X_1-X_2} = \frac{x-2}{1-2} = -(x-2)

e

L_2 = \frac{x-X_1}{X_2-X_1} = \frac{x-1}{2-1} = (x-1),

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

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 .

Note que substituindo na equação acima, P(1) = 9 e P(2) = 13.

Exemplo 2

Fórmula de Lagrange para N=3.

Verificando a fórmula de Lagrange para N = 3. Suponhamos que desejamos encontrar qual é o polinômio que passa pelos pontos (X1,Y1) = (2,4), (X2,Y2) = (3,9) e (X3,Y3) = (6,36). Temos que:

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},
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}

e

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},

assim


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 .


Exemplo 3

Para ilustrar graficamente o método da fórmula de Lagrange, usaremos um exemplo com N = 4. Considerando os quatro pontos (X1,Y1) = ( − 1,5), (X2,Y3) = (1,2), (X3,Y3) = ( − 3,5) e (X4,Y4) = (7,4), as equações Li ficam

L_1 = -\frac{1}{64}(x^3-11x^2+31x-21),
L_2 = \frac{1}{24}(x^3-9x^2+11x+21),
L_3 = -\frac{1}{32}(x^3-7x^2-x+7)

e

L_4 = \frac{1}{192}(x^3-3x^2-x+3).

O gráfico abaixo mostra os quatro pontos (Xi,Yi), as curvas LiYi e a curva final P(x). Lembre-se que P(x) é a curva gerada pela soma dos polinômios LiYi. Note que a curva L1Y1 passa pelo ponto (X1,Y1), assim como as demais e a curva P(x) 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 Xi,Yi, devolva um polinômio P(x) 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 Li(x)) onde cada um deles é construído como um produto de N-1 termos; ao todo N2 cálculos para cada ponto x (isto fica como exercício a partir da fórmula geral do P(x)).

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 P_1(x)=Y_1,\; P_2(x)=Y_2,\; \cdots\,\; P_N(x)=Y_N. Melhorando a descrição, empregando agora uma aproximação linear em cada intervalo [X_i,\;X_{i+1}], denotamos por P_{12}(x),\;P_{23}(x),\; \cdots,\; P_{N-1,N}(x), onde P_{i,i+1}(x)\;é o polinômio que passa exatamente sobre (X_i,Y_i)\;e\;(X_{i+1},Y_{i+1}):


P_{i,i+1}(x)=\frac{x-X_{i+1}}{X_i-X_{i+1}}Y_i+\frac{x-X_i}{X_{i+1}-X_i}Y_{i+1}\;.

Vemos que P_{i, i+1}(x)\;pode ser escrito como:


P_{i,i+1}(x)=\frac{(x-X_{i+1})P_i(x)-(x-X_i)P_{i+1}(x)}{X_i-X_{i+1}}

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


P_{i,i+1,i+2}(x)=\frac{x-X_{i+1}}{X_i-X_{i+1}}\frac{x-X_{i+2}}{X_i    -X_{i+2}}Y_i
             +\frac{x-X_i}{X_{i+1}-X_i}\frac{x-X_{i+2}}{X_{i+1}-X_{i+2}}Y_{i+1}
             +\frac{x-X_i}{X_{i+2}-X_i}\frac{x-X_{i+1}}{X_{i+2}-X_{i+1}}Y_{i+2}

Fatorando \;1/(X_i-X_{i+2}) e somando e subtraindo \frac{x-X_i}{X_{i+1}-X_i}(x-X_{i+2})Y_{i+1}, obtemos:


P_{i,i+1,i+2}(x) =\frac{1}{X_i-X_{i+2}}\left[(x-X_{i+2})P_{i,i+1}(x)
-F(x)\right]

onde


F(x)=(x-X_i)\left[\frac{x-X_{i+1}}{X_{i+2}-X_{i+1}}Y_{i+2}
-\frac{X_i-X_{i+2}}{X_{i+1}-X_i}\frac{x-X_{i+2}}{X_{i+1}-X_{i+2}}Y_{i+1} 
+\frac{x-X_{i+2}}{X_{i+1}-X_i}Y_{i+1}\right]\;.

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\;P_{i,i+1}(x) na equação para\;P_{i,i+1,i+2}(x). Rearranjando os termos acima, encontramos:


F(x)=(x-X_i)\left[\frac{x-X_{i+2}}{X_{i+1}-X_{i+2}}Y_{i+1}+\frac{x-X_{i+1}}{X_{i+2}-X_{i+1}}Y_{i+2}\right]
=(x-X_i)P_{i+1,i+2}(x)\;.

Substituindo este resultado na equação para\;P_{i,i+1,i+2}(x), obtemos finalmente:


P_{i,i+1,i+2}(x) =\frac{1}{X_i-X_{i+2}}\left[(x-X_{i+2})P_{i,i+1}(x)
-(x-X_i)P_{i+1,i+2}(x)\right]

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


P_{i,i+1,\cdots,i+k}(x) =\frac{1}{X_i-X_{i+k}}\left[(x-X_{i+k})P_{i,i+1,\cdots,i+k-1}(x)
-(x-X_i)P_{i+1,i+2,\cdots,i+k}(x)\right]

Por ser muito mais simples de se implementar numericamente do que a expressão original para \;P(x), é 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:


D^{(1)}_{k,i}(x)=P_{i,i+1,\cdots,i+k}(x)-P_{i,i+1,\cdots,i+k-1}(x)

e


D^{(2)}_{k,i}(x)=P_{i,i+1,\cdots,i+k}(x)-P_{i+1,i+2,\cdots,i+k}(x)\;.

Ao invés de se gerar \;P(x) a partir da relação de recorrência para P_{i,i+1,\cdots,i+k}(x), pode-se utilizar as equações acima e obter relações de recorrência para \;D^{(1)} \mbox{ e } D^{(2)}. No final, obtemos \;P(x) 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 \;\{X_i\} 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 \;X, deve ser empregado. Por exemplo, digamos que temos uma tabela com 100 pontos \;\{(X_i,Y_i)\}. Se desejamos estimar o valor de \;Y no interior da região [X_1,\; X_N], 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 (X_{i-1},Y_{i-1}),\; (X_i,Y_i),\; (X_{i+1},Y_{i+1}) e\;(X_{i+2},Y_{i+2}).

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).


Ferramentas pessoais
Espaços nominais
Variantes
Ações
Navegação
Ferramentas