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\rightarrow 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)$