Fórmula de Lagrange - Histórico de revisão

Ejagnes em 10h47min de 25 de outubro de 2011

2011-10-25T10:47:19Z

← Edição anterior		Edição das 10h47min de 25 de outubro de 2011
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

Caca em 18h44min de 20 de outubro de 2011

2011-10-20T18:44:54Z

← Edição anterior		Edição das 18h44min de 20 de outubro de 2011
Linha 1:		Linha 1:
	== ~~Interpolação polinimial &~~ Polinômios de Lagrange ==		== 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:

Caca em 18h43min de 20 de outubro de 2011

2011-10-20T18:43:59Z

← Edição anterior		Edição das 18h43min de 20 de outubro de 2011
Linha 1:		Linha 1:
	== Polinômios de Lagrange ==		== Interpolação polinimial & 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:

Ejagnes em 16h09min de 14 de outubro de 2011

2011-10-14T16:09:46Z

← Edição anterior		Edição das 16h09min de 14 de outubro de 2011
Linha 178:		Linha 178:
	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>.		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~~]]).		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]]).

	----		----

Ejagnes em 16h07min de 14 de outubro de 2011

2011-10-14T16:07:31Z

Mostrar alterações

Tekkito: Criou página com '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 d...'

2011-09-19T17:36:36Z

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

Página nova

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:

<math>
P(x)=\sum_{i=1}^N Y_i L_i(x)
</math>

onde

<math>
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}
</math>

é claramente 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

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

é fácil verificar que, de fato,<math>\;P(X_i)=Y_i</math>. Assim,<math>\;P(x)</math> pode ser empregado para se estimar o valor de <math>\;Y(x)</math> em pontos <math>\;x</math> não tabulados.

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

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.
Por isto, o algorítmo de Neville é de grande valia na realização desta tarefa.
Se aproximarmos cada intervalo por um valor constante, podemos representar esta aproximação por
<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>
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}\;.
</math>

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

<math>
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}}
</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
<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>
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}
</math>

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

<math>
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]
</math>

onde

<math>
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]\;.
</math>

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

<math>
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)\;.
</math>

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

<math>
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]
</math>

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

<math>
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]
</math>

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

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

e

<math>
D^{(2)}_{k,i}(x)=P_{i,i+1,\cdots,i+k}(x)-P_{i+1,i+2,\cdots,i+k}(x)\;.
</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.

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

----

Voltar para o índice de [[Métodos computacionais]].