Fórmula de interpolación de Newton: Diferencia entre la fórmula hacia delante y la fórmula hacia atrás

Question

Me enseñaron que se debe utilizar la fórmula de avance cuando se calcula el valor de un punto cercano a $x_0$ y el de atrás cuando se calcula cerca de $x_n$ . Sin embargo, el polinomio de interpolación es único, por lo que el valor debería ser el mismo. Entonces, ¿hay alguna diferencia entre los dos, o mi profesor está equivocado?

Aquí están los fórmulas :

1. Interpolación diferencial Gregory-Newton o Newton Forward $$P(x_{0}+hs)=f_{0}+s\Delta f_{0}+\frac{s(s-1)}{2!}\Delta^{2}f_{0}+\cdots+\frac{s(s-1)(s-2)...(s-n+1)}{n!}\Delta^{n}f_{0}$$ donde $$s=\frac{(x-x_{0})}{h}; \qquad f_0=f(x_0); \qquad \Delta^k f_i=\sum_{j=0}^k{(-1)^j \frac{k!}{j!(k-j)!}f_{i+k-j}}$$
2. Interpolación por diferencia hacia atrás Gregory-Newton o Newton $$P(x_{n}+hs)=f_{n}+s\nabla f_{n}+\frac{s(s+1)}{2!}\nabla^{2}f_{n}+\cdots+\frac{s(s+1)(s+2)...(s+n-1)}{n!}\nabla^{n}f_{n}$$ donde $$s=\frac{(x-x_{n})}{h}; \qquad f_n=f(x_n); \qquad \nabla^k f_i=\sum_{j=0}^k{(-1)^j \frac{k!}{j!(k-j)!}f_{i-j}}$$

Ejemplo: Para interpolar en los puntos $x_0=-3,-2.9,-2.8,...,2.9,3=x_n$ con $f(x)=e^x$ usando MATLAB tenemos

>> x = -3:0.1:3; y = exp(x);
>> frwrdiffdata = frwrdiff(x, y, 0.1, -3:0.5:3);
>> bckwrdiffdata = bkwrdiff(x, y, 0.1, -3:0.5:3);
>> mostAccurateData = exp(-3:0.5:3)';
>> [abs(frwrdiffdata-mostAccurateData)./mostAccurateData ... 
abs(bckwrdiffdata-mostAccurateData)./mostAccurateData]

ans =

   1.0e-03 *

                   0   0.672871398134864
   0.000000000000169   0.001123487151044
   0.000000000000205   0.000000247108705
                   0   0.000000006452206
   0.000000000000302   0.000000000010412
   0.000000000000366   0.000000000005491
   0.000000000000222   0.000000000001776
   0.000000000000135                   0
   0.000000000000327   0.000000000000327
   0.000000000093342                   0
   0.000000006938894                   0
   0.000003364235903                   0
   0.000053772150047                   0

donde la primera columna es el error relativo de la diferencia hacia delante de Newton y la segunda columna es el error relativo de la diferencia hacia atrás de Newton para los puntos de muestra $x=-3,-2.5,-2,...,2.5,3$ . Como se ve en la tabla anterior y en la siguiente figura, el error relativo de la primera columna aumenta a medida que $x\to x_n$ y el error relativo de la segunda columna disminuye como $x\to x_n$ .

Las funciones de MATLAB frwrdiff y bkwrdiff utilizados arriba son

function polyvals = frwrdiff(x, y, h, p) % Newton Forward Difference function
n = length(x);
ps = length(p);
polyvals = zeros(ps, 1);
dd = zeros(n,n);
dd(:, 1) = y(:);
for i = 2: n % divided diference table
    for j = 2: i
        dd(i,j) = (dd(i, j-1) - dd(i-1, j-1));
    end
end
a = diag(dd); %y_0, delta_0, ..., delta_n
for k = 1: ps
    s = (p(k) - x(1))/h; %(x - x_0) / h
    t = s;
    polyvals(k) = a(1) + s*a(2); %y_0 + s * delta_0
    for i = 1: n-2
       t = t * (s - i);
       polyvals(k) = polyvals(k) + t*a(i+2)/factorial(i+1);
    end
end

y

function polyvals = bkwrdiff(x, y, h, p) % Newton Backward Difference function
n = length(x);
ps = length(p);
polyvals = zeros(ps, 1);
dd = zeros(n,n);
dd(:, 1) = y(:);
for i = 2: n % divided diference table
    for j = 2: i
        dd(i,j) = (dd(i, j-1) - dd(i-1, j-1));
    end
end
a = dd(n,:); %y_n, nabla_0, ..., nabla_n
for k = 1: ps
    s = (p(k) - x(n))/h; %(x - x_n) / h
    t = s;
    polyvals(k) = a(1) + s*a(2); %y_0 + s * nabla_0
    for i = 1: n-2
       t = t * (s + i);
       polyvals(k) = polyvals(k) + t*a(i+2)/factorial(i+1);
    end
end

Nota: Los resultados parecen diferentes cuando al principio obtenemos los polinomios y luego sustituimos los puntos $x=-3,-2.5,-2,...,2.5,3$ a los polinomios:

ans =

   1.0e+02 *

   0.000000132146955   1.528566476043447
   0.000000000047960   0.000683674054800
   0.000000000000000   0.000000095605754
   0.000000000000000   0.000000000002139
   0.000000000000000   0.000000000000000
   0.000000000000000   0.000000000000000
   0.000000000000000                   0
   0.000000000000000                   0
   0.000000000000000   0.000000000000000
   0.000000000000331   0.000000000000000
   0.000000004277456   0.000000000000000
   0.000006632407337   0.000000000000896
   0.001154767626752   0.000000000785245

Los resultados anteriores se han obtenido modificando las dos funciones de matlab ya mencionadas en esta pregunta.

Answer 1

Suponiendo teóricamente que los cálculos se realicen en una aritmética infinita entonces los polinomios son los mismos por lo que dan la misma respuesta .

Pero ¡como el ordenador y la aritmética aplicada son finitos entonces al calcular los polinomios no resultan ser iguales (al menos no en todos los casos). y ten en cuenta que cuantas más operaciones aritméticas haces más pierdes precisión!

por lo que si la entrada x está más cerca de $x_i$ (uno de los datos que ya tenemos); a continuación, elegir $x_i$ como $x_0$ da una mayor precisión si utilizamos la fórmula de las diferencias hacia delante en nuestro sistema aritmético finito (o en el caso de las diferencias hacia atrás, eligiendo $x_i$ como $x_n$ ) (o incluso en el caso de las diferencias centradas elegir $x_i$ como los datos del medio)

desde

Por ejemplo, en el caso de $x_i$ como $x_0$ utilizando la fórmula de las diferencias hacia adelante ; el $f(x_0)$ es un solo término (sin aritmética adicional para perder precisión como otros términos) y como estamos asumiendo que si x está cerca de $x_i$ entonces $f(x)$ también está cerca de $f(x_i)$ . para que obtengamos el menor error posible en el cálculo $f(x)$ (que también es el caso de las diferencias centradas y de las diferencias de fondo).

Notas adicionales:

Si utilizamos la fórmula de las diferencias divididas de Newton, entonces la indexación de los datos no importa realmente. así que para aumentar la precisión simplemente volvemos a indexar los datos de la forma más precisa y encontramos el polinomio.

PERO si utilizamos la suposición de que $x_{i+1} - x_{i} = h$ (donde h es el tamaño del paso).

entonces no podemos reindexar los datos como deseamos y los datos deben ser crecientes o decrecientes .así que para obtener más precisión y poder elegir el término único ( $f(x_{0})$ o $f(x_{n})$ o ...) para que sean los datos más cercanos; tenemos que cambiar la fórmula del polinomio para satisfacer nuestras necesidades.

Answer 2

Interpolación polinomial para un conjunto de valores de $\{x_k, f(x_k)\}_{k = 1}^n$ es único. Usted puede obtener la prueba en cualquier texto estándar utilizando Vandermond determinante.

Cuando queremos encontrar el valor de la función de $f(x)$ en algún momento dado de la $x$, por interpolación, un error término usado para venir. $f(x) = L_n(x) + R_n(x)$ donde $L_n(x)$ es el valor de la interpolación polinómica en $x$ $R_n(x)$ es el valor del término de error en $x$. Nuestro objetivo fundamental es disminuir el error tanto como sea posible.

Vamos a utilizar hacia adelante y hacia atrás de interpolación en diferentes lugares como sea necesario.

Answer 3

Supongamos que $x_0,x_1,x_2,\dots,x_n$ son los puntos nodales dados. Entonces el método de diferencias hacia delante de Newton es mejor para los puntos que están más cerca de $x_0$ mientras que el método de diferencias hacia atrás de Newton es mejor para los puntos que están más cerca de $x_n$ .

Pero ambos métodos se utilizan para encontrar el valor de una función en un punto determinado.