Diferencias divididas

Algoritmo para calcular coeficientes polinómicos

En matemáticas , las diferencias divididas son un algoritmo , históricamente utilizado para calcular tablas de logaritmos y funciones trigonométricas . ^{[ cita requerida ]} La máquina diferencial de Charles Babbage , una de las primeras calculadoras mecánicas , fue diseñada 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 la 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 pares distintos, 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 de tabla, 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 inmediata superior izquierda, dividida por una diferencia de los valores 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

Nótese que la diferencia dividida depende de los valores y , pero la notación oculta la dependencia de los valores 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}}}$$
• Regla 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 polinomial 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 sostiene

• ${\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 de diferencias divididas con respecto al mismo conjunto de nodos x forman un anillo conmutativo .
• Como es una matriz triangular, sus valores propios son obviamente . ${\displaystyle T_{f}(x)}$ ${\displaystyle f(x_{0}),\dots ,f(x_{n})}$
• Sea una función de tipo delta de Kronecker , es decir Obviamente , por lo tanto es una función propia de la multiplicación de funciones puntuales. Es decir 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 . Denote 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, puede 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 corresponde a una serie de potencias . Puede calcular el esquema de diferencia dividida para 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 expandida

$${\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 de Peano

Si y , las diferencias divididas se pueden expresar como ^[4] donde es la derivada -ésima 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})}}}$$

Esta 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 para las diferencias divididas, todas llamadas así en honor a Giuseppe Peano . ${\displaystyle B_{n-1}}$

Diferencias hacia adelante y hacia atrás

Cuando los puntos de datos se distribuyen de forma equidistante, obtenemos el caso especial denominado diferencias hacia delante . Son más fáciles de calcular que las diferencias divididas más generales.

Dados n +1 puntos de datos con 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 las diferencias divididas y las diferencias hacia adelante es ^[5] mientras que para las diferencias hacia atrás: ^{[ cita requerida ]} $${\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}.}$$

Véase también

• Cociente de diferencia
• El algoritmo de Neville
• Interpolación polinómica
• Teorema del valor medio para diferencias divididas
• Integral de Nörlund-Rice
• Triángulo de Pascal

Referencias

1. Isaacson, Walter (2014). Los innovadores . Simon & Schuster. pág. 20. ISBN 978-1-4767-0869-0.
2. de Boor, Carl , Divided Differences , Surv. App. Theory 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 las matemáticas y la lógica: Actas de la Conferencia internacional en honor de Giuseppe Peano con motivo del 150 aniversario de su nacimiento y del centenario del Formulario Mathematico Torino (Italia) 2-3 de octubre de 2008. Springer Science & Business Media. pág. 40. ISBN 978-88-470-1836-5.
5. Burden, Richard L.; Faires, J. Douglas (2011). Análisis numérico (novena edición). Cengage Learning. pág. 129. ISBN 9780538733519.

• Louis Melville Milne-Thomson (2000) [1933]. El cálculo de diferencias finitas . American Mathematical Soc. Capítulo 1: Diferencias divididas. ISBN 978-0-8218-2107-7.
• Myron B. Allen; Eli L. Isaacson (1998). Análisis numérico para la ciencia aplicada . John Wiley & Sons. Apéndice A. ISBN 978-1-118-03027-1.
• Ron Goldman (2002). Algoritmos piramidales: un enfoque de programación dinámica para curvas y superficies para modelado geométrico . Morgan Kaufmann. Capítulo 4: Interpolación de Newton y triángulos diferenciales. ISBN 978-0-08-051547-2.

Enlaces externos

• Una implementación en Haskell .