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

Dado n  + 1 puntos de datos

$${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$$

diferencias divididas hacia adelante ${\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 , ${\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}].}$$

ƒx ₀x _n

$${\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 ${\displaystyle f}$
  $${\displaystyle f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}}$$
  para un número en el intervalo abierto determinado por el menor y el mayor de los 's. ${\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 . Resumido, 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 tipo delta de Kronecker , es decir ${\displaystyle \delta _{\xi }}$
  $${\displaystyle \delta _{\xi }(t)={\begin{cases}1&:t=\xi ,\\0&:{\mbox{else}}.\end{cases}}}$$
  Obviamente , por 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 ${\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}}}$$
  La diagonalización de se puede escribir como ${\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

$${\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}}}$$

función identidadfunción potenciaexponentefunción polinómica ${\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).}$$

fórmula de Opitz^{[2] [3]}

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 matricial correspondiente a : Si ${\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 peano

Si y , las diferencias divididas se pueden expresar como ^[4] ${\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}$$

derivadaB-spline ${\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

$${\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 directas es ^[5]

$${\displaystyle [y_{j},y_{j+1},\ldots ,y_{j+k}]={\frac {1}{k!h^{k}}}\Delta ^{(k)}y_{j},}$$

^{[ cita necesaria ]}

$${\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 .