Interpolación de splines

Método matemático

En el campo matemático del análisis numérico , la interpolación spline es una forma de interpolación donde el interpolante es un tipo especial de polinomio por partes llamado spline . Es decir, en lugar de ajustar un solo polinomio de alto grado a todos los valores a la vez, la interpolación spline ajusta polinomios de bajo grado a pequeños subconjuntos de los valores, por ejemplo, ajustando nueve polinomios cúbicos entre cada uno de los pares de diez puntos, en lugar de ajustar un solo polinomio de grado nueve a todos ellos. La interpolación spline a menudo se prefiere a la interpolación polinómica porque el error de interpolación se puede hacer pequeño incluso cuando se utilizan polinomios de bajo grado para la spline. ^[1] La interpolación spline también evita el problema del fenómeno de Runge , en el que puede ocurrir una oscilación entre puntos cuando se interpola utilizando polinomios de alto grado.

Introducción

Interpolación con splines cúbicos entre ocho puntos. Los dibujos técnicos hechos a mano para la construcción naval son un ejemplo histórico de interpolación de splines; los dibujos se construían utilizando reglas flexibles que se doblaban para seguir puntos predefinidos.

En un principio, spline era un término que designaba a las reglas elásticas que se doblaban para pasar por una serie de puntos predefinidos, o nudos . Se utilizaban para hacer dibujos técnicos para la construcción y construcción naval a mano, como se ilustra en la figura.

Queremos modelar tipos similares de curvas utilizando un conjunto de ecuaciones matemáticas. Supongamos que tenemos una secuencia de nudos, a través de . Habrá un polinomio cúbico entre cada par sucesivo de nudos y que se conecta a ambos, donde . Por lo tanto, habrá polinomios, con el primer polinomio comenzando en , y el último polinomio terminando en . ${\displaystyle n+1}$ ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle (x_{n},y_{n})}$ ${\displaystyle q_{i}(x)=y}$ ${\displaystyle (x_{i-1},y_{i-1})}$ ${\displaystyle (x_{i},y_{i})}$ ${\displaystyle i=1,2,\dots ,n}$ ${\displaystyle n}$ ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle (x_{n},y_{n})}$

La curvatura de cualquier curva se define como ${\displaystyle y=y(x)}$

${\displaystyle \kappa ={\frac {y''}{(1+y'^{2})^{3/2}}},}$

donde y son las derivadas primera y segunda de con respecto a . Para hacer que la spline adopte una forma que minimice la flexión (bajo la restricción de pasar por todos los nudos), definiremos que y sean continuos en todas partes, incluidos los nudos. Cada polinomio sucesivo debe tener valores iguales (que son iguales al valor y del punto de datos correspondiente), derivadas y segundas derivadas en sus nudos de unión, es decir que ${\displaystyle y'}$ ${\displaystyle y''}$ ${\displaystyle y(x)}$ ${\displaystyle x}$ ${\displaystyle y'}$ ${\displaystyle y''}$

${\displaystyle {\begin{cases}q_{i}(x_{i})=q_{i+1}(x_{i})=y_{i}\\q'_{i}(x_{i})=q'_{i+1}(x_{i})\\q''_{i}(x_{i})=q''_{i+1}(x_{i})\end{cases}}\qquad 1\leq i\leq n-1.}$

Esto solo se puede lograr si se utilizan polinomios de grado 3 (polinomios cúbicos) o superior. El enfoque clásico es utilizar polinomios de exactamente grado 3 ( splines cúbicos ).

Además de las tres condiciones anteriores, un ' spline cúbico natural ' tiene la condición de que . ${\displaystyle q''_{1}(x_{0})=q''_{n}(x_{n})=0}$

Además de las tres condiciones principales anteriores, un ' spline cúbico fijado ' tiene las condiciones de que y donde es la derivada de la función interpolada. ${\displaystyle q'_{1}(x_{0})=f'(x_{0})}$ ${\displaystyle q'_{n}(x_{n})=f'(x_{n})}$ ${\displaystyle f'(x)}$

Además de las tres condiciones principales anteriores, un ' spline sin nudo ' tiene las condiciones de que y . ^[2] ${\displaystyle q'''_{1}(x_{1})=q'''_{2}(x_{1})}$ ${\displaystyle q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})}$

Algoritmo para encontrar el spline cúbico interpolador

Queremos encontrar cada polinomio dados los puntos que pasan por . Para ello, consideraremos solo una única parte de la curva, , que interpolará de a . Esta parte tendrá pendientes y en sus puntos finales. O, más precisamente, ${\displaystyle q_{i}(x)}$ ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle (x_{n},y_{n})}$ ${\displaystyle q(x)}$ ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (x_{2},y_{2})}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$

${\displaystyle q(x_{1})=y_{1},}$

${\displaystyle q(x_{2})=y_{2},}$

${\displaystyle q'(x_{1})=k_{1},}$

${\displaystyle q'(x_{2})=k_{2}.}$

La ecuación completa se puede escribir en forma simétrica ${\displaystyle q(x)}$

dónde

Pero ¿qué son y ? Para derivar estos valores críticos, debemos considerar que ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$

${\displaystyle q'={\frac {dq}{dx}}={\frac {dq}{dt}}{\frac {dt}{dx}}={\frac {dq}{dt}}{\frac {1}{x_{2}-x_{1}}}.}$

De lo cual se deduce que

Fijando t = 0 y t = 1 respectivamente en las ecuaciones ( 5 ) y ( 6 ), se obtiene de ( 2 ) que efectivamente las primeras derivadas q′ ( x ₁ ) = k ₁ y q′ ( x ₂ ) = k ₂ , y también las segundas derivadas

Si ahora ( x _i , y _i ), i = 0, 1, ..., n son n + 1 puntos, y

donde i = 1, 2, ..., n , y son n polinomios de tercer grado que interpolan y en el intervalo x _{i −1} ≤ x ≤ x _i para i = 1, ..., n tales que q′ _i ( x _i ) = q′ _{i +1} ( x _i ) para i = 1, ..., n  − 1, entonces los n polinomios juntos definen una función diferenciable en el intervalo x ₀ ≤ x ≤ x _n , y ${\displaystyle t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}}$

para i = 1, ..., n , donde

Si la secuencia k ₀ , k ₁ , ..., k _n es tal que, además, q′′ _i ( x _i ) = q′′ _{i +1} ( x _i ) se cumple para i = 1, ..., n  − 1, entonces la función resultante tendrá incluso una segunda derivada continua.

De ( 7 ), ( 8 ), ( 10 ) y ( 11 ) se deduce que este es el caso si y sólo si

para i = 1, ..., n  − 1. Las relaciones ( 15 ) son n − 1 ecuaciones lineales para los n + 1 valores k ₀ , k ₁ , ..., k _n .

Para las reglas elásticas que son el modelo para la interpolación de splines, se tiene que a la izquierda del "nudo" más a la izquierda y a la derecha del "nudo" más a la derecha la regla se puede mover libremente y, por lo tanto, tomará la forma de una línea recta con q′′ = 0. Como q′′ debe ser una función continua de x , los "splines naturales" además de las n − 1 ecuaciones lineales ( 15 ) deben tener

${\displaystyle q''_{1}(x_{0})=2{\frac {3(y_{1}-y_{0})-(k_{1}+2k_{0})(x_{1}-x_{0})}{{(x_{1}-x_{0})}^{2}}}=0,}$

${\displaystyle q''_{n}(x_{n})=-2{\frac {3(y_{n}-y_{n-1})-(2k_{n}+k_{n-1})(x_{n}-x_{n-1})}{{(x_{n}-x_{n-1})}^{2}}}=0,}$

es decir que

Finalmente, ( 15 ) junto con ( 16 ) y ( 17 ) constituyen n + 1 ecuaciones lineales que definen de forma única los n + 1 parámetros k ₀ , k ₁ , ..., k _n .

Existen otras condiciones finales, la "spline fija", que especifica la pendiente en los extremos de la spline, y la popular "spline sin nudos", que requiere que la tercera derivada también sea continua en los puntos x ₁ y x _{n −1} . Para la spline sin nudos, las ecuaciones adicionales se leerán así:

${\displaystyle q'''_{1}(x_{1})=q'''_{2}(x_{1})\Rightarrow {\frac {1}{\Delta x_{1}^{2}}}k_{0}+\left({\frac {1}{\Delta x_{1}^{2}}}-{\frac {1}{\Delta x_{2}^{2}}}\right)k_{1}-{\frac {1}{\Delta x_{2}^{2}}}k_{2}=2\left({\frac {\Delta y_{1}}{\Delta x_{1}^{3}}}-{\frac {\Delta y_{2}}{\Delta x_{2}^{3}}}\right),}$

${\displaystyle q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})\Rightarrow {\frac {1}{\Delta x_{n-1}^{2}}}k_{n-2}+\left({\frac {1}{\Delta x_{n-1}^{2}}}-{\frac {1}{\Delta x_{n}^{2}}}\right)k_{n-1}-{\frac {1}{\Delta x_{n}^{2}}}k_{n}=2\left({\frac {\Delta y_{n-1}}{\Delta x_{n-1}^{3}}}-{\frac {\Delta y_{n}}{\Delta x_{n}^{3}}}\right),}$

dónde . ${\displaystyle \Delta x_{i}=x_{i}-x_{i-1},\ \Delta y_{i}=y_{i}-y_{i-1}}$

Ejemplo

Interpolación con splines cúbicos "naturales" entre tres puntos

En el caso de tres puntos, los valores para se encuentran resolviendo el sistema de ecuaciones lineales tridiagonales. ${\displaystyle k_{0},k_{1},k_{2}}$

${\displaystyle {\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}}{\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}}$

con

${\displaystyle a_{11}={\frac {2}{x_{1}-x_{0}}},}$

${\displaystyle a_{12}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{21}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{22}=2\left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right),}$

${\displaystyle a_{23}={\frac {1}{x_{2}-x_{1}}},}$

${\displaystyle a_{32}={\frac {1}{x_{2}-x_{1}}},}$

${\displaystyle a_{33}={\frac {2}{x_{2}-x_{1}}},}$

${\displaystyle b_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},}$

${\displaystyle b_{2}=3\left({\frac {y_{1}-y_{0}}{{(x_{1}-x_{0})}^{2}}}+{\frac {y_{2}-y_{1}}{{(x_{2}-x_{1})}^{2}}}\right),}$

${\displaystyle b_{3}=3{\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}.}$

Por los tres puntos

${\displaystyle (-1,0.5),\ (0,0),\ (3,3),}$

Uno consigue eso

${\displaystyle k_{0}=-0.6875,\ k_{1}=-0.1250,\ k_{2}=1.5625,}$

y de ( 10 ) y ( 11 ) que

${\displaystyle a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875,}$

${\displaystyle b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750,}$

${\displaystyle a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750,}$

${\displaystyle b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875.}$

En la figura, se muestra la función spline que consta de dos polinomios cúbicos y está dada por ( 9 ). ${\displaystyle q_{1}(x)}$ ${\displaystyle q_{2}(x)}$

Véase también

• Estrías de Akima
• Interpolación circular
• Spline cúbico de Hermite
• Spline centrípeta Catmull-Rom
• Interpolación de splines discreta
• Interpolación cúbica monótona
• B-spline racional no uniforme
• Interpolación multivariante
• Interpolación polinómica
• Spline suavizante
• Ondícula spline
• Estría de placa delgada
• Spline poliarmónico

Referencias

1. Hall, Charles A.; Meyer, Weston W. (1976). "Límites de error óptimos para la interpolación de spline cúbico". Journal of Approximation Theory . 16 (2): 105–122. doi : 10.1016/0021-9045(76)90040-X .
2. Burden, Richard; Faires, Douglas (2015). Análisis numérico (10.ª ed.). Cengage Learning. págs. 142–157. ISBN 9781305253667.

Lectura adicional

• Schoenberg, Isaac J. (1946). "Contribuciones al problema de aproximación de datos equidistantes mediante funciones analíticas: Parte A. Sobre el problema de suavizado o graduación. Una primera clase de fórmulas de aproximación analítica". Quarterly of Applied Mathematics . 4 (2): 45–99. doi : 10.1090/qam/15914 .
• Schoenberg, Isaac J. (1946). "Contribuciones al problema de aproximación de datos equidistantes mediante funciones analíticas: Parte B. Sobre el problema de la interpolación osculatoria. Una segunda clase de fórmulas de aproximación analítica". Quarterly of Applied Mathematics . 4 (2): 112–141. doi : 10.1090/qam/16705 .

Enlaces externos

• Herramienta de cálculo y visualización en línea de interpolación de splines cúbicos (con código fuente en JavaScript)
• "Interpolación de splines", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Splines cúbicos dinámicos con JSXGraph
• Conferencias sobre la teoría y la práctica de la interpolación spline
• Artículo que explica paso a paso cómo se realiza la interpolación de splines cúbicos, pero sólo para nudos equidistantes.
• Recetas numéricas en C, Ir al Capítulo 3 Sección 3-3
• Una nota sobre splines cúbicos
• Información sobre la interpolación de splines (incluido el código en Fortran 77)
• TinySpline: biblioteca C de código abierto para splines que implementa la interpolación de splines cúbicos
• SciPy Spline Interpolation: un paquete de Python que implementa la interpolación
• Interpolación cúbica: biblioteca C# de código abierto para interpolación de splines cúbicos