Física Computacional - FSC-5705

só um divisor

Método de Neville

Qual é o melhor ajuste a ser realizado a fim de obter uma boa interpolação utilizando o método de Lagrange? Uma possível resposta seria ver quão mal é o nosso ajuste. Para isso, é possível calcular o erro cometido na aproximação utilizando a formula

\[ f(x) - P_n(x) = \dfrac{ f^{(n+1)}( \xi (x)) }{(n+1)!}\prod_{i=0}^{n}(x-x_i) \nonumber \]

O problema em se aplicar esta formula é que é necessário conhecer qual é o grau do polinômio que ajusta os dados e isso só é possível de conhecer depois de todos os cálculos serem realizados. Por outo lado, o polinômio que melhor "fita" um conjunto de dado se encontra incrementado a ordem dos polinômios de Lagrange utilizados.

Dessa forma vemos que se faz necessário o cálculo de diversos polinômios a fim de saber qual é aquele que melhor se ajusta a nossas necessidades. Nesse sentido o método do Neville proporciona uma técnica interativa que permite utilizar os polinômios já calculados no cálculo dos novos polinômios.

Antes de passarmos a definir o que é o método de Neville vamos estabeler uma notação que será utilizada mais adiante. Suponhamos que temos os pontos: $x_0=1.0$, $x_1=2.0$, $x_2=3.0$, $x_3=4.0$, $x_4=6.0$ e $f(x) = e^x$, chamaremos de $P_{1,2,4}(x)$ ao polinômio de Lagrange que passa pelos pontos $x_1=2.0$, $x_2=3.0$ e $x_4=6.0$, isto é \[ P_{1,2,4}(x) = \dfrac{\left( x - 3 \right)\left( x - 6\right)}{\left(2-3 \right)\left( 2-6 \right)}e^2 + \dfrac{\left( x - 2\right)\left( x - 6\right)}{\left( 3-2 \right)\left( 3-6 \right)}e^3 + \dfrac{\left( x - 2\right)\left( x - 3\right)}{\left( 6-2\right)\left( 6-3 \right)}e^4 \nonumber \] observado este detalhe vamos ao método.

Suponhamos $f(x)$ está definida nos pontos $x_0,\, x_1,\, x_2,\, \ldots, \, x_k$, e que $x_i$ e $x_j$ são dois números distintos daquele conjunto, o teorema de Neville no diz que

\[ P_{0,1,3,\ldots,k}(x) = \dfrac{\left(x - x_j\right)\;P_{0,1,\ldots, j-1, j+1,\cdots,k}\;\; - \;\;\left(x - x_i\right)\;P_{0,1,\ldots, i-1, i+1,\ldots,k}}{\left(x_i - x_j\right)} \nonumber \]

onde $P_{0,1,3,\ldots,k}(x)$ é o polinômio de Lagrange de grau $k$-ésimo que interpola $f$ nos $k+1$ pontos $x_0,\,x_1,\, x_2,\, \ldots, \, x_k$

Como exemplo consideremos os dados da tabela:

   x       f(x)   
1.0 0.7651977
1.3 0.6200860
1.6 0.4554022
1.9 0.2818186
2.2 0.1103623

Interpolemos o valor $x=1.5$, utilizadando diversos polinômios:

$\displaystyle{ \begin{array}{ccc} P_{0,1}(r) & = & \frac{(r-x_0)P_1 - (r-x_1)P_0}{(x_1 - x_0)} \\ \end{array} }$

Aqui observamos que $P_i = f(x_i)$, dessa forma: \[ \begin{aligned} P_{0,1}(1.5) = & \dfrac{(1.5-x_0)P_1 - (1.5-x_1)P_0}{(x_1 - x_0)}\nonumber\\ = & \dfrac{(1.5-x_0)f(x_1) - (1.5-x_1)f(x_0)}{(x_1 - x_0)}\\ = & \dfrac{(1.5-1.0)(0.6200860) - (1.5-1.3)(0.7651977)}{(1.5 - 1.3)}\\ = & 0.7651977 \end{aligned} \]

Agora vamos calcular com 3 pontos \[ P_{0,1,2}(r) = \dfrac{(r-x_0)P_{1,2} - (r-x_2)P_{0,1}}{(x_2 - x_0)}\nonumber \] onde \[ \begin{aligned} P_{1,2}(r) =& \dfrac{(r-x_1)P_2 - (r-x_2)P_1}{(x_2 - x_1)}\\ P_{1,2}(1.5) =& \dfrac{(1.5 - 1.3)(0.4554022) - (1.5 - 1.6)(0.6200860)}{(1.6 - 1.3)}\\ =& 0.5102968\nonumber \end{aligned} \] de forma \[ \begin{aligned} P_{0,1,2}(r) =& \dfrac{(r-x_0)P_{1,2} - (r-x_2)P_{0,1}}{(x_2 - x_0)}\\ P_{0,1,2}(1.5) =& \dfrac{(1.5 - 1.3)(0.5102968) - (1.5 - 1.6)(0.7651977)}{1.6 - 1.0}\\ & 0.595263767\nonumber \end{aligned} \] O valor exato é $0,5118277$ (função Bessel de primeiro nível de ordem zero).

Exemplo 2

Dado o conjunto de elementos

   x       f(x)   
1.0 0.7651977
1.3 0.6200860
1.6 0.4554022
1.9 0.2818186
2.2 0.1103623
2.5 -0.04383838

utilizando o método de Neville interpole o valor x=1.5 tal que a tolerância seja menor do que $1\times 10^{-2}$

Solução

A nossa interpolação vai incluir mais e mais polinômios de Lagrange (isso implica, mais e mais pontos) até encontrarmos um resultado que diverga do prévio em $1\times 10^{-4}$

A ideia é usar pouco a pouco os dados que foram fornecidos. O primeiro a calcular são os polinômios de Lagrange de ordem $0$ que concorda com os pontos $x_0$, $x_1$, $x_2$, $x_3$ e $x_4$. Um polinômio de ordem zero é um número pelo, assim a única interpolação que concorde com cada um dos $6$ número é o próprio número:

$\displaystyle{ \begin{array}{rcl} P_{0}(r) & = & f(x_0) \\ P_{1}(r) & = & f(x_1) \\ P_{2}(r) & = & f(x_2) \\ P_{3}(r) & = & f(x_3) \\ P_{4}(r) & = & f(x_4) \\ P_{5}(r) & = & f(x_5) \\ \end{array} }$

Note que o índice utilizado com o polinômio não indica a ordem e sem com que numero da data ele coincide, a ordem é $n-1$ sendo $n$ a quantidades de números na qual o polinômio de interpolação coincide com os dados.

Utilizado o dois ponto contíguos podemos realizar interpolações lineares: $x_0$ e $x_1$, ou $x_1$ e $x_2$, ou $x_2$ e $x_3$, $x_3$ e $x_4$. Façamos o cálculo da interpolação linear:

$\displaystyle{ \begin{array}{rcl} P_{0,1}(r) & = & \frac{(r-x_0)P_1(r) - (r-x_1)P_0(r)}{(x_1 - x_0)}\\ P_{1,2}(r) & = & \frac{(r-x_1)P_2(r) - (r-x_2)P_1(r)}{(x_2 - x_1)}\\ P_{2,3}(r) & = & \frac{(r-x_2)P_3(r) - (r-x_3)P_2(r)}{(x_3 - x_2)}\\ P_{3,4}(r) & = & \frac{(r-x_3)P_4(r) - (r-x_4)P_3(r)}{(x_4 - x_3)}\\ P_{4,5}(r) & = & \frac{(r-x_4)P_5(r) - (r-x_5)P_4(r)}{(x_5 - x_4)}\\ P_{5,6}(r) & = & \frac{(r-x_5)P_6(r) - (r-x_6)P_5(r)}{(x_5 - x_4)}\\ \end{array} }$

O passo a seguir requer o cálculo do polinômio de II grau, usando 3 pontos:

$\displaystyle{ \begin{array}{rcl} P_{0,1,2}(r) & = & \frac{(r-x_0)P_{1,2}(r) - (r-x_2)P_{0,1}(r)}{(x_2 - x_0)}\\ P_{1,2,3}(r) & = & \frac{(r-x_1)P_{2,3}(r) - (r-x_3)P_{1,2}(r)}{(x_3 - x_1)}\\ P_{2,3,4}(r) & = & \frac{(r-x_2)P_{3,4}(r) - (r-x_4)P_{2,3}(r)}{(x_4 - x_2)}\\ P_{3,4,5}(r) & = & \frac{(r-x_3)P_{4,5}(r) - (r-x_5)P_{3,4}(r)}{(x_5 - x_3)}\\ P_{4,5,6}(r) & = & \frac{(r-x_4)P_{5,6}(r) - (r-x_6)P_{4,5}(r)}{(x_6 - x_4)}\\ \end{array} }$

Cálculo dos polinômios de III grau, usando 4 pontos:

$\displaystyle{ \begin{array}{rcl} P_{0,1,2,3}(r) & = & \frac{(r-x_0)P_{1,2,3}(r) - (r-x_3)P_{0,1,2}(r)}{(x_3 - x_0)}\\ P_{1,2,3,4}(r) & = & \frac{(r-x_1)P_{2,3,4}(r) - (r-x_4)P_{1,2,3}(r)}{(x_4 - x_1)}\\ P_{2,3,4,5}(r) & = & \frac{(r-x_2)P_{3,4,5}(r) - (r-x_5)P_{2,3,4}(r)}{(x_5 - x_2)}\\ P_{3,4,5,6}(r) & = & \frac{(r-x_3)P_{4,5,6}(r) - (r-x_6)P_{3,4,5}(r)}{(x_6 - x_3)}\\ \end{array} }$

Cálculo dos polinômios de IV grau, usando 5 pontos:

$\displaystyle{ \begin{array}{rcl} P_{0,1,2,3,4}(r) & = & \frac{(r-x_0)P_{1,2,3,4}(r) - (r-x_4)P_{0,1,2,3}(r)}{(x_4 - x_0)}\\ P_{1,2,3,4,5}(r) & = & \frac{(r-x_1)P_{2,3,4,5}(r) - (r-x_5)P_{1,2,3,4}(r)}{(x_5 - x_1)}\\ P_{2,3,4,5,6}(r) & = & \frac{(r-x_2)P_{3,4,5,6}(r) - (r-x_6)P_{2,3,4,5}(r)}{(x_6 - x_2)}\\ \end{array} }$

Cálculo dos polinômios de V grau, usando 6 pontos:

$\displaystyle{ \begin{array}{rcl} P_{0,1,2,3,4,5}(r) & = & \frac{(r-x_0)P_{1,2,3,4,5}(r) - (r-x_5)P_{0,1,2,3,4}(r)}{(x_5 - x_0)}\\ P_{1,2,3,4,5,6}(r) & = & \frac{(r-x_1)P_{2,3,4,5,6}(r) - (r-x_6)P_{1,2,3,4,5}(r)}{(x_6 - x_1)}\\ \end{array} }$

Cálculo dos polinômios de VI grau, usando 7 pontos:

$\displaystyle{ \begin{array}{rcl} P_{0,1,2,3,4,5,6}(r) & = & \frac{(r-x_0)P_{1,2,3,4,5,6}(r) - (r-x_6)P_{0,1,2,3,4,5}(r)}{(x_6 - x_0)}\\ \end{array} }$

O resultado desses cálculos está apresentado na tabela com o seguinte formato:

$\displaystyle{ \begin{array}{ccccccc} x_0 & P_{0} & & & & &\\ x_1 & P_{1} & P_{0,1} & & & &\\ x_2 & P_{2} & P_{1,2} & P_{0,1,2} & & &\\ x_3 & P_{3} & P_{2,3} & P_{1,2,3} & P_{0,1,2,3} & &\\ x_4 & P_{4} & P_{3,4} & P_{2,3,4} & P_{1,2,3,4} & P_{0,1,2,3,4} & \\ x_5 & P_{5} & P_{4,5} & P_{3,4,5} & P_{2,3,4,5} & P_{1,2,3,4,5} & P_{0,1,2,3,4,5} \\ \end{array} }$

Que resulta em:

$\displaystyle{ \begin{array}{ccccccc} 1.0 & 0.7651977 & & & & & \\ 1.3 & 0.6200860 & 0.5233449 & & & & \\ 1.6 & 0.4554022 & 0.5102968 & 0.5124715 & & &\\ 1.9 & 0.2818186 & 0.5132634 & 0.5112857 & 0.5118127 & &\\ 2.2 & 0.1103623 & 0.5104270 & 0.5137361 & 0.5118302 & 0.5118200 &\\ 2.5 & -0.0483838 & 0.4807699 & 0.5301984 & 0.519070 & 0.5118430 & 0.5118277 \\ \end{array} }$

Assim vemos que é necessário calcular o polinômio anterior antes calcular o polinômio atual.

Nos não podemos aplicar a formula de erro para o caso da aproximação de Lagrange. Assim, consideraremos como toleráveis a resposta que verifique $\xi > | P_i - P_j |$. Então em nosso exemplo vemos que $|P_{12345} - P_{1234}| = 0.0000077$, valor este que é menor do que $1\times 10^{-4}$.

Algoritmo de Neville

Primeiro vamos definir uma notação que facilite fazer referencia aos polinômios utilizados, definimos $Q_{ij}$ para $0 \le j \le i $ como a representação do polinômio de grau $j$ que passa pelos $(j+1)$ pontos $x_{i-j}, \, x_{i-j+1}, \, \cdots , x_i$, isto é

$\displaystyle{ Q_{i,j} = P_{i-j, i-j+1, i-j+1, \ldots , i-1, i} }$

assim, o exemplo anterior se expressa

$\displaystyle{ \begin{array}{ccccccc} x_0 & P_{0} = Q_{0,0} & & & & &\\ x_1 & P_{1} = Q_{1,0} & P_{0,1} = Q_{1,1} & & & &\\ x_2 & P_{2} = Q_{2,0} & P_{1,2} = Q_{2,1} & P_{0,1,2} = Q_{2,2} & & &\\ x_3 & P_{3} = Q_{3,0} & P_{2,3} = Q_{3,1} & P_{1,2,3} = Q_{3,2} & P_{0,1,2,3} = Q_{3,3} & &\\ x_4 & P_{4} = Q_{4,0} & P_{3,4} = Q_{4,1} & P_{2,3,4} = Q_{4,2} & P_{1,2,3,4} = Q_{4,3} & P_{0,1,2,3,4} = Q_{4,4} & \\ x_5 & P_{5} = Q_{5,0} & P_{4,5} = Q_{5,1} & P_{3,4,5} = Q_{5,2} & P_{2,3,4,5} = Q_{5,3} & P_{1,2,3,4,5} = Q_{5,4} & P_{0,1,2,3,4,5} = Q_{5,5}\\ \end{array} }$

Algoritmo:

Com essa nova notação em mão podemos escrever o algoritmo de Neville assim:

Entrada: tabela de dados $(x_k, f(x_k))$ e ponto a interpolar, $x$
Saída: tabela com $Q$ para $P(x) = Q_{n,n}$
Passo 1: $Q_{i,0} \leftarrow f(x_i)$
Passo2: Para $i = 1, 2, \ldots , n$
Para $j = 1, 2, \ldots , i$
faça $Q_{i,j} \leftarrow \dfrac{(x-x_{i-j})Q_{i,j-1} - (x-x_{i})Q_{i-1,j-1}}{x_i - x_{i-j}}$
Paso 3: Saída (Q)
Pare

O algoritmo para quando \[ \left| Q_{i,i} - Q_{i-1,i-1} \right| < \epsilon \]

Tarefa

$\displaystyle{ \begin{array}{ccccccc} x_0 & P_{0} = Q_{0,0} & & & & &\\ x_1 & P_{1} = Q_{1,0} & P_{0,1} = Q_{1,1} & & & &\\ x_2 & P_{2} = Q_{2,0} & P_{1,2} = Q_{2,1} & P_{0,1,2} = Q_{2,2} & & &\\ x_3 & P_{3} = Q_{3,0} & P_{2,3} = Q_{3,1} & P_{1,2,3} = Q_{3,2} & P_{0,1,2,3} = Q_{3,3} & &\\ x_4 & P_{4} = Q_{4,0} & P_{3,4} = Q_{4,1} & P_{2,3,4} = Q_{4,2} & P_{1,2,3,4} = Q_{4,3} & P_{0,1,2,3,4} = Q_{4,4} & \\ x_5 & P_{5} = Q_{5,0} & P_{4,5} = Q_{5,1} & P_{3,4,5} = Q_{5,2} & P_{2,3,4,5} = Q_{5,3} & P_{1,2,3,4,5} = Q_{5,4} & P_{0,1,2,3,4,5} = Q_{5,5}\\ \end{array} }$

para os dados em tabela.dat, e para $x = 2.0$.