Implementação do algoritmo de Neville

Aqui é descrito um possível mapeamento para fazer o algoritmo de Neville, são descritas as fórmulas do algoritmo de Neville e seu correspondente mapeamento.

Algoritmo de Neville:

$P_{12}=\frac{1}{x_1-x_2}[(x-x_2)P_{11}-(x-x_1)P_{22}]$

Olhando em termos da matriz:

$A_{12}=P_{12}=\frac{1}{X[1]-X[2]}[(x-X[2])A_{11}-(x-X[1])P_{22}].$

Algoritmo de Neville:

$P_{23}=\frac{1}{x_2-x_3}[(x-x_3)P_{22}-(x-x_2)P_{33}]$

Mapeamento:

$A_{22}=P_{23}=\frac{1}{X[2]-X[3]}[(x-X[3])A_{21}-(x-X[2])A_{31}]$

A. N.:

$P_{34}=\frac{1}{x_3-x_4}[(x-x_4)P_{33}-(x-x_3)P_{44}]$

M.:

$A_{32}=P_{34}=\frac{1}{X[3]-X[4]}[(x-X[4])A_{31}-(x-X[3])A_{41}]$

Já é possível notar que

$A_{ij}=\frac{1}{X[i]-X[k]}[(x-X[k])A_{i,j-1}-(x-X[i])A_{i+1,j-1}],k=j+i-1$

Continuando com o A. N.:

$P_{123}=\frac{1}{x_1-x_3}[(x-x_3)P_{12}-(x-x_1)P_{23}]$

M.:

$A_{13}=P_{123}=\frac{1}{X[1]-X[3]}[(x-X[3])A_{12}-(x-X[1])A_{22}]$

A. N.:

$P_{234}=\frac{1}{x_2-x_4}[(x-x_4)P_{23}-(x-x_3)P_{34}]$

M.:

$A_{23}=P_{234}=\frac{1}{X[2]-X[4]}[(x-X[4])A_{22}-(x-X[3])A_{32}]$

A. N.:

$P_{1234}=\frac{1}{x_1-x_4}[(x-x_4)P_{123}-(x-x_1)P_{234}]$

M.:

$A_{14}=P_{1234}=\frac{1}{X[1]-X[4]}[(x-X[4])A_{13}-(x-X[1])A_{23}]$

Chegando finalmente a relação de recorrencia

$A_{ij}=\frac{1}{X[i]-X[k]}[(x-X[k])A_{i,j-1}-(x-X[i])A_{i+1,j-1}]$

onde

$k=j+i-1$

No final do processo, o polinômio interpolador é dado por

$P(x)=A14.$

A leitura dos pontos é dado pelos valores de X e da primeira coluna da matriz A.

$X,Y\to X[i],A[i][1]$

A ordem do preenchimento é fundamental:

$j=1;i=1,2,3,4$

$j=2;i=1,2,3$

$j=3;i=1,2$

$j=4;i=1$

$j=1...N;i=1...(N-j+1)$