Diferencias divididas

Algoritmo para calcular coeficientes polinomiales.

En matemáticas , diferencias divididas es un algoritmo , históricamente utilizado para calcular tablas de logaritmos y funciones trigonométricas . ^{[ cita necesaria ]} El motor diferencial de Charles Babbage , una de las primeras calculadoras mecánicas , fue diseñado para utilizar este algoritmo en su funcionamiento. ^[1]

Las diferencias divididas son un proceso de división recursivo . Dada una secuencia de puntos de datos , el método calcula los coeficientes del polinomio de interpolación de estos puntos en forma de Newton . ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$

Definición

Dados n  + 1 puntos de datos donde se supone que son distintos por pares, las diferencias divididas hacia adelante se definen como: $${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$$ ${\displaystyle x_{k}}$ $${\displaystyle {\begin{aligned}{\mathopen {[}}y_{k}]&:=y_{k},&&k\in \{0,\ldots ,n\}\\{\mathopen {[}}y_{k},\ldots ,y_{k+j}]&:={\frac {[y_{k+1},\ldots ,y_{k+j}]-[y_{k},\ldots ,y_{k+j-1}]}{x_{k+j}-x_{k}}},&&k\in \{0,\ldots ,n-j\},\ j\in \{1,\ldots ,n\}.\end{aligned}}}$$

Para hacer más claro el proceso recursivo de cálculo, las diferencias divididas se pueden poner en forma tabular, donde las columnas corresponden al valor de j anterior, y cada entrada en la tabla se calcula a partir de la diferencia de las entradas a su inmediata inferior izquierda y a su parte superior izquierda inmediata, dividido por una diferencia de los valores de x correspondientes : $${\displaystyle {\begin{matrix}x_{0}&y_{0}=[y_{0}]&&&\\&&[y_{0},y_{1}]&&\\x_{1}&y_{1}=[y_{1}]&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&y_{2}=[y_{2}]&&[y_{1},y_{2},y_{3}]&\\&&[y_{2},y_{3}]&&\\x_{3}&y_{3}=[y_{3}]&&&\\\end{matrix}}}$$

Notación

Tenga en cuenta que la diferencia dividida depende de los valores y , pero la notación oculta la dependencia de los valores de x . Si los puntos de datos están dados por una función f , a veces se escribe la diferencia dividida en la notación. Otras notaciones para la diferencia dividida de la función ƒ en los nodos x ₀ , ...,  x _n son: ${\displaystyle [y_{k},\ldots ,y_{k+j}]}$ ${\displaystyle x_{k},\ldots ,x_{k+j}}$ ${\displaystyle y_{k},\ldots ,y_{k+j}}$ $${\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{n})=(x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n}))}$$ $${\displaystyle f[x_{k},\ldots ,x_{k+j}]\ {\stackrel {\text{def}}{=}}\ [f(x_{k}),\ldots ,f(x_{k+j})]=[y_{k},\ldots ,y_{k+j}].}$$ $${\displaystyle f[x_{k},\ldots ,x_{k+j}]={\mathopen {[}}x_{0},\ldots ,x_{n}]f={\mathopen {[}}x_{0},\ldots ,x_{n};f]=D[x_{0},\ldots ,x_{n}]f.}$$

Ejemplo

Diferencias divididas para y los primeros valores de : ${\displaystyle k=0}$ ${\displaystyle j}$ $${\displaystyle {\begin{aligned}{\mathopen {[}}y_{0}]&=y_{0}\\{\mathopen {[}}y_{0},y_{1}]&={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\{\mathopen {[}}y_{0},y_{1},y_{2}]&={\frac {{\mathopen {[}}y_{1},y_{2}]-{\mathopen {[}}y_{0},y_{1}]}{x_{2}-x_{0}}}={\frac {{\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}-{\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}}{x_{2}-x_{0}}}={\frac {y_{2}-y_{1}}{(x_{2}-x_{1})(x_{2}-x_{0})}}-{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})(x_{2}-x_{0})}}\\{\mathopen {[}}y_{0},y_{1},y_{2},y_{3}]&={\frac {{\mathopen {[}}y_{1},y_{2},y_{3}]-{\mathopen {[}}y_{0},y_{1},y_{2}]}{x_{3}-x_{0}}}\end{aligned}}}$$

Así, la tabla correspondiente a estos términos hasta dos columnas tiene la siguiente forma: $${\displaystyle {\begin{matrix}x_{0}&y_{0}&&\\&&{y_{1}-y_{0} \over x_{1}-x_{0}}&\\x_{1}&y_{1}&&{{y_{2}-y_{1} \over x_{2}-x_{1}}-{y_{1}-y_{0} \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{y_{2}-y_{1} \over x_{2}-x_{1}}&\\x_{2}&y_{2}&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&y_{n}&&\\\end{matrix}}}$$

Propiedades

• Linealidad $${\displaystyle {\begin{aligned}(f+g)[x_{0},\dots ,x_{n}]&=f[x_{0},\dots ,x_{n}]+g[x_{0},\dots ,x_{n}]\\(\lambda \cdot f)[x_{0},\dots ,x_{n}]&=\lambda \cdot f[x_{0},\dots ,x_{n}]\end{aligned}}}$$
• gobierno de Leibniz $${\displaystyle (f\cdot g)[x_{0},\dots ,x_{n}]=f[x_{0}]\cdot g[x_{0},\dots ,x_{n}]+f[x_{0},x_{1}]\cdot g[x_{1},\dots ,x_{n}]+\dots +f[x_{0},\dots ,x_{n}]\cdot g[x_{n}]=\sum _{r=0}^{n}f[x_{0},\ldots ,x_{r}]\cdot g[x_{r},\ldots ,x_{n}]}$$
• Las diferencias divididas son simétricas: si es una permutación, entonces ${\displaystyle \sigma :\{0,\dots ,n\}\to \{0,\dots ,n\}}$ $${\displaystyle f[x_{0},\dots ,x_{n}]=f[x_{\sigma (0)},\dots ,x_{\sigma (n)}]}$$
• Interpolación polinomial en la forma de Newton : si es una función polinómica de grado y es la diferencia dividida, entonces ${\displaystyle P}$ ${\displaystyle \leq n}$ ${\displaystyle p[x_{0},\dots ,x_{n}]}$ $${\displaystyle P_{n-1}(x)=p[x_{0}]+p[x_{0},x_{1}](x-x_{0})+p[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\cdots +p[x_{0},\ldots ,x_{n}](x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}$$
• Si es una función polinómica de grado , entonces ${\displaystyle p}$ ${\displaystyle <n}$ $${\displaystyle p[x_{0},\dots ,x_{n}]=0.}$$
• Teorema del valor medio para diferencias divididas : si es n veces diferenciable, entonces para un número en el intervalo abierto determinado por el menor y el mayor de los . ${\displaystyle f}$ $${\displaystyle f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}}$$ ${\displaystyle \xi }$ ${\displaystyle x_{k}}$

forma matricial

El esquema de diferencias divididas se puede poner en una matriz triangular superior : $${\displaystyle T_{f}(x_{0},\dots ,x_{n})={\begin{pmatrix}f[x_{0}]&f[x_{0},x_{1}]&f[x_{0},x_{1},x_{2}]&\ldots &f[x_{0},\dots ,x_{n}]\\0&f[x_{1}]&f[x_{1},x_{2}]&\ldots &f[x_{1},\dots ,x_{n}]\\0&0&f[x_{2}]&\ldots &f[x_{2},\dots ,x_{n}]\\\vdots &\vdots &&\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}.}$$

Entonces se mantiene

• ${\displaystyle T_{f+g}(x)=T_{f}(x)+T_{g}(x)}$
• ${\displaystyle T_{\lambda f}(x)=\lambda T_{f}(x)}$si es un escalar ${\displaystyle \lambda }$
• ${\displaystyle T_{f\cdot g}(x)=T_{f}(x)\cdot T_{g}(x)}$
  Esto se desprende de la regla de Leibniz. Significa que la multiplicación de tales matrices es conmutativa . En resumen, las matrices de esquemas en diferencias divididas con respecto al mismo conjunto de nodos x forman un anillo conmutativo .
• Como es una matriz triangular, sus valores propios obviamente son . ${\displaystyle T_{f}(x)}$ ${\displaystyle f(x_{0}),\dots ,f(x_{n})}$
• Sea una función similar al delta de Kronecker , es decir, obviamente , por lo tanto, es una función propia de la multiplicación de funciones puntuales. Eso es de alguna manera una " matriz propia " de : . Sin embargo, todas las columnas de son múltiplos entre sí, el rango de la matriz de es 1. Por lo tanto, puede componer la matriz de todos los vectores propios de a partir de la -ésima columna de cada uno . Denota la matriz de vectores propios con . Ejemplo La diagonalización de se puede escribir como ${\displaystyle \delta _{\xi }}$ $${\displaystyle \delta _{\xi }(t)={\begin{cases}1&:t=\xi ,\\0&:{\mbox{else}}.\end{cases}}}$$ ${\displaystyle f\cdot \delta _{\xi }=f(\xi )\cdot \delta _{\xi }}$ ${\displaystyle \delta _{\xi }}$ ${\displaystyle T_{\delta _{x_{i}}}(x)}$ ${\displaystyle T_{f}(x)}$ ${\displaystyle T_{f}(x)\cdot T_{\delta _{x_{i}}}(x)=f(x_{i})\cdot T_{\delta _{x_{i}}}(x)}$ ${\displaystyle T_{\delta _{x_{i}}}(x)}$ ${\displaystyle T_{\delta _{x_{i}}}(x)}$ ${\displaystyle T_{f}(x)}$ ${\displaystyle i}$ ${\displaystyle T_{\delta _{x_{i}}}(x)}$ ${\displaystyle U(x)}$ $${\displaystyle U(x_{0},x_{1},x_{2},x_{3})={\begin{pmatrix}1&{\frac {1}{(x_{1}-x_{0})}}&{\frac {1}{(x_{2}-x_{0})(x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{0})(x_{3}-x_{1})(x_{3}-x_{2})}}\\0&1&{\frac {1}{(x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{1})(x_{3}-x_{2})}}\\0&0&1&{\frac {1}{(x_{3}-x_{2})}}\\0&0&0&1\end{pmatrix}}}$$ ${\displaystyle T_{f}(x)}$ $${\displaystyle U(x)\cdot \operatorname {diag} (f(x_{0}),\dots ,f(x_{n}))=T_{f}(x)\cdot U(x).}$$

Polinomios y series de potencias.

La matriz contiene el esquema de diferencias divididas para la función identidad con respecto a los nodos , por lo tanto contiene las diferencias divididas para la función potencia con exponente . En consecuencia, puedes obtener las diferencias divididas para una función polinómica aplicando a la matriz : Si y entonces Esto se conoce como fórmula de Opitz . ^{[2] [3]} $${\displaystyle J={\begin{pmatrix}x_{0}&1&0&0&\cdots &0\\0&x_{1}&1&0&\cdots &0\\0&0&x_{2}&1&&0\\\vdots &\vdots &&\ddots &\ddots &\\0&0&0&0&\;\ddots &1\\0&0&0&0&&x_{n}\end{pmatrix}}}$$ ${\displaystyle x_{0},\dots ,x_{n}}$ ${\displaystyle J^{m}}$ ${\displaystyle m}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle J}$ $${\displaystyle p(\xi )=a_{0}+a_{1}\cdot \xi +\dots +a_{m}\cdot \xi ^{m}}$$ $${\displaystyle p(J)=a_{0}+a_{1}\cdot J+\dots +a_{m}\cdot J^{m}}$$ $${\displaystyle T_{p}(x)=p(J).}$$

Ahora considere aumentar el grado de hasta el infinito, es decir, convertir el polinomio de Taylor en una serie de Taylor . Sea una función que corresponda a una serie de potencias . Puede calcular el esquema de diferencias divididas aplicando la serie de matrices correspondiente a : Si y entonces ${\displaystyle p}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle J}$ $${\displaystyle f(\xi )=\sum _{k=0}^{\infty }a_{k}\xi ^{k}}$$ $${\displaystyle f(J)=\sum _{k=0}^{\infty }a_{k}J^{k}}$$ $${\displaystyle T_{f}(x)=f(J).}$$

Caracterizaciones alternativas

forma ampliada

$${\displaystyle {\begin{aligned}f[x_{0}]&=f(x_{0})\\f[x_{0},x_{1}]&={\frac {f(x_{0})}{(x_{0}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})}}\\f[x_{0},x_{1},x_{2}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})}}\\f[x_{0},x_{1},x_{2},x_{3}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})\cdot (x_{0}-x_{3})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})\cdot (x_{1}-x_{3})}}+\\&\quad \quad {\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})\cdot (x_{2}-x_{3})}}+{\frac {f(x_{3})}{(x_{3}-x_{0})\cdot (x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\f[x_{0},\dots ,x_{n}]&=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}\end{aligned}}}$$

Con la ayuda de la función polinómica esto se puede escribir como ${\displaystyle \omega (\xi )=(\xi -x_{0})\cdots (\xi -x_{n})}$ $${\displaystyle f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\omega '(x_{j})}}.}$$

forma peano

Si y , las diferencias divididas se pueden expresar como ^[4] donde es la -ésima derivada de la función y es un cierto B-spline de grado para los puntos de datos , dado por la fórmula ${\displaystyle x_{0}<x_{1}<\cdots <x_{n}}$ ${\displaystyle n\geq 1}$ $${\displaystyle f[x_{0},\ldots ,x_{n}]={\frac {1}{(n-1)!}}\int _{x_{0}}^{x_{n}}f^{(n)}(t)\;B_{n-1}(t)\,dt}$$ ${\displaystyle f^{(n)}}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle B_{n-1}}$ ${\displaystyle n-1}$ ${\displaystyle x_{0},\dots ,x_{n}}$ $${\displaystyle B_{n-1}(t)=\sum _{k=0}^{n}{\frac {(\max(0,x_{k}-t))^{n-1}}{\omega '(x_{k})}}}$$

Esto es una consecuencia del teorema del núcleo de Peano ; se llama forma de Peano de las diferencias divididas y es el núcleo de Peano de las diferencias divididas, todas con el nombre de Giuseppe Peano . ${\displaystyle B_{n-1}}$

Diferencias hacia adelante y hacia atrás

Cuando los puntos de datos están distribuidos equidistantemente obtenemos el caso especial llamado diferencias directas . Son más fáciles de calcular que las diferencias divididas más generales.

Dados n +1 puntos de datos con las diferencias hacia adelante se definen como, mientras que las diferencias hacia atrás se definen como: Por lo tanto, la tabla de diferencias hacia adelante se escribe como: mientras que la tabla de diferencias hacia atrás se escribe como: $${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$$ $${\displaystyle x_{k}=x_{0}+kh,\ {\text{ for }}\ k=0,\ldots ,n{\text{ and fixed }}h>0}$$ $${\displaystyle {\begin{aligned}\Delta ^{(0)}y_{k}&:=y_{k},\qquad k=0,\ldots ,n\\\Delta ^{(j)}y_{k}&:=\Delta ^{(j-1)}y_{k+1}-\Delta ^{(j-1)}y_{k},\qquad k=0,\ldots ,n-j,\ j=1,\dots ,n.\end{aligned}}}$$ $${\displaystyle {\begin{aligned}\nabla ^{(0)}y_{k}&:=y_{k},\qquad k=0,\ldots ,n\\\nabla ^{(j)}y_{k}&:=\nabla ^{(j-1)}y_{k}-\nabla ^{(j-1)}y_{k-1},\qquad k=0,\ldots ,n-j,\ j=1,\dots ,n.\end{aligned}}}$$ $${\displaystyle {\begin{matrix}y_{0}&&&\\&\Delta y_{0}&&\\y_{1}&&\Delta ^{2}y_{0}&\\&\Delta y_{1}&&\Delta ^{3}y_{0}\\y_{2}&&\Delta ^{2}y_{1}&\\&\Delta y_{2}&&\\y_{3}&&&\\\end{matrix}}}$$ $${\displaystyle {\begin{matrix}y_{0}&&&\\&\nabla y_{1}&&\\y_{1}&&\nabla ^{2}y_{2}&\\&\nabla y_{2}&&\nabla ^{3}y_{3}\\y_{2}&&\nabla ^{2}y_{3}&\\&\nabla y_{3}&&\\y_{3}&&&\\\end{matrix}}}$$

La relación entre diferencias divididas y diferencias hacia adelante es ^[5] mientras que para las diferencias hacia atrás: ^{[ cita necesaria ]} $${\displaystyle [y_{j},y_{j+1},\ldots ,y_{j+k}]={\frac {1}{k!h^{k}}}\Delta ^{(k)}y_{j},}$$ $${\displaystyle [{y}_{j},y_{j-1},\ldots ,{y}_{j-k}]={\frac {1}{k!h^{k}}}\nabla ^{(k)}y_{j}.}$$

Ver también

• cociente de diferencias
• algoritmo de neville
• Interpolación polinomial
• Teorema del valor medio para diferencias divididas
• Nörlund-Arroz integral
• el triangulo de pascal

Referencias

1. Isaacson, Walter (2014). Los innovadores . Simón y Schuster. pag. 20.ISBN​ 978-1-4767-0869-0.
2. de Boor, Carl , Diferencias divididas , Surv. Aprox. Teoría 1 (2005), 46–69, [1]
3. Opitz, G. Steigungsmatrizen , Z. Angew. Matemáticas. Mec. (1964), 44, T52-T54
4. Skof, Fulvia (30 de abril de 2011). Giuseppe Peano entre Matemáticas y Lógica: Actas de la Conferencia Internacional en honor a Giuseppe Peano en el 150 aniversario de su nacimiento y centenario del Formulario Mathematico Torino (Italia) 2-3 de octubre de 2008. Springer Science & Business Media. pag. 40.ISBN​ 978-88-470-1836-5.
5. Carga, Richard L.; Ferias, J. Douglas (2011). Análisis numérico (9ª ed.). Aprendizaje Cengage. pag. 129.ISBN​ 9780538733519.

• Louis Melville Milne-Thomson (2000) [1933]. El cálculo de diferencias finitas . Sociedad Matemática Estadounidense. Capítulo 1: Diferencias divididas. ISBN 978-0-8218-2107-7.
• Myron B. Allen; Eli L. Isaacson (1998). Análisis numérico para ciencias aplicadas . John Wiley e hijos. Apéndice A. ISBN 978-1-118-03027-1.
• Ron Goldman (2002). Algoritmos piramidales: un enfoque de programación dinámica de curvas y superficies para modelado geométrico . Morgan Kaufman. Capítulo 4: Interpolación de Newton y triángulos en diferencia. ISBN 978-0-08-051547-2.

Enlaces externos

• Una implementación en Haskell .