En esta asignatura hemos cubierto métodos para resolver ecuaciones y sistemas lineales. Ahora abordamos la interpolación de funciones, una técnica fundamental para aproximar funciones desconocidas o costosas de evaluar a partir de un conjunto finito de puntos de datos ($x_i$, $y_i$), donde $y_i=f\left(x_i\right)$.

La interpolación de funciones es un proceso matemático que se utiliza para estimar valores desconocidos dentro del dominio de un conjunto de datos discretos, es decir, cuando solo se tiene información en ciertos puntos específicos. Este proceso es fundamental en diversas áreas de las ciencias aplicadas y la ingeniería, ya que permite construir funciones continuas que pasan exactamente por un conjunto de puntos dados

. Dentro de los métodos de interpolación polinómica, el polinomio de Lagrange es uno de los más utilizados. Este polinomio se construye de manera que para cada uno de los puntos conocidos, se crea un término que es cero en todos los puntos, excepto en el punto correspondiente.

9.1 Concepto de interpolación

Dado un conjunto de n+1 puntos distintos {$\left(x_0,y_0\right)$, $\left(x_1,y_1\right)$, …, $\left(x_n,y_n\right)$} con $x_i\ne x_j$ para i$\ne j$, la interpolación consiste en encontrar una función $P\left(x\right)$ tal que:

$P\left(x_i\right)=y_i$ para todo $i = 0, 1, \dots , n$

y que pertenezca a una familia parametrizada de funciones (polinomios, splines, funciones racionales, etc.).

Teorema de existencia y unicidad (interpolación polinómica): Para n+1 puntos distintos existen un único polinomio $P\left(x\right)$ de grado ≤ n tal que $P\left(x_i\right)=y_i$ para todo i. Este polinomio se denomina polinomio interpolador de Lagrange o de Newton (ambos representan el mismo polinomio, pero expresado de forma diferente).

Error de interpolación (teorema fundamental): Sea $f\in C^{n+1}\left[a,b\right]$ y $x_0,\dots ,x_n\in \left[a,b\right]$ distintos. Entonces para cualquier $x\in \left[a,b\right]$ existe $\xi \in \left(minx,x_0,\dots ,x_n,maxx,x_0,\dots ,x_n\right)$tal que

donde $\omega \left(x\right)=\left(x-x_0\right)\left(x-x_1\right)\dots \left(x-x_n\right)$es el polinomio nodal.

Figura 1

Conjunto de puntos de datos y polinomio interpolador único de grado ≤ n para n+1 puntos.

En ciberseguridad: la interpolación se usa en side-channel attacks (reconstrucción de funciones de leakage mediante polinomios a partir de trazas de potencia/timing), en criptoanálisis polinómico (aproximación de funciones modulares o curvas elípticas), en machine learning para seguridad (interpolación de datos de entrenamiento para detección de anomalías) y en procesamiento forense digital (suavizado/interpolación de señales en imágenes o audio extraídos de dispositivos comprometidos).

Figura 2

Representación del error de interpolación: término de Runge y fenómeno de oscilación en intervalos grandes.

El término de Runge es un ejemplo clásico de un error que ocurre cuando se utiliza un polinomio de grado alto para interpolar una función, particularmente en intervalos grandes. En este caso, el error de interpolación crece significativamente en los extremos del intervalo. Este fenómeno es más notable cuando la función a interpolar tiene un comportamiento oscilante o no es suficientemente suave, como sucede con la famosa función de Runge:

Cuando se interpola esta función usando polinomios de alto grado, el error no solo se mantiene pequeño en el centro del intervalo, sino que aumenta drásticamente cerca de los bordes, produciendo oscilaciones que se conocen como oscilaciones de Runge.

El fenómeno de oscilación ocurre porque los polinomios de grado alto tienden a "sobrefit" los datos, es decir, ajustan los puntos de datos de manera demasiado precisa, lo que genera oscilaciones no deseadas, especialmente en los extremos del intervalo. A medida que el grado del polinomio aumenta, las oscilaciones cerca de los bordes del intervalo también se intensifican, lo que resulta en una mala aproximación, a pesar de que el polinomio pase por todos los puntos de datos. Esta oscilación se puede ver en el gráfico como picos y valles en la curva interpolada en las cercanías de los extremos del intervalo.

9.1.1 Interpolación polinómica

La interpolación polinómica busca el polinomio $P_n\left(x\right)$ de grado ≤ n que pasa exactamente por los n+1 puntos dados.

Ventajas matemáticas:

• Unicidad garantizada.
• Error controlado si se conoce $f^{\left(n+1\right)}$.
• Fácil evaluación en puntos nuevos.

Desventajas:

• Fenómeno de Runge: para nodos equidistantes y n grande, oscilaciones grandes cerca de los extremos (polinomios de alto grado son inestables).
• Sensibilidad a errores en los datos (mal condicionado para nodos equidistantes).

Nodos de Chebyshev (para minimizar error máximo$): x\_k = cos├( \left\{\right(2k+1\left)\pi \right\}\left\{2\right(n+1\left)\right\} ┤), \hspace{1em}k=0,\dots ,n$ reducen significativamente el fenómeno de Runge.

En ciberseguridad: interpolación polinómica de bajo grado se usa en ataques a implementaciones de curvas elípticas (aproximación de la función de punto en curva), y en side-channel para modelar leakage como polinomio de grado bajo (e.g., Hamming weight model).

Figura 3

Fenómeno de Runge: interpolación polinómica de grado alto con nodos equidistantes vs nodos de Chebyshev.

9.1.2 Polinomio de Lagrange

Formulación matemática formal

El polinomio de Lagrange es:

donde los polinomios base de Lagrange son:

$l_i\left(x\right)={\prod }_{j=0,j\ne i}^n\frac{x-x_j}{x_i-x_j}$

Propiedades:

• $l_i\left(x_k\right)={\delta }_{ik}$ (1 si i=k, 0 en otro caso) → interpolación exacta.
• Grado de cada $l_{i}esn\to P_n$tiene grado ≤ n.
• Forma explícita, no requiere resolución de sistemas lineales.

Complejidad: O(n²) para evaluar en un punto nuevo (suma de productos).

Estabilidad numérica: mal condicionado para n grande (número de condición crece exponencialmente con n en nodos equidistantes).

En ciberseguridad: forma de Lagrange útil para evaluar rápidamente funciones interpoladas en ataques de timing o power (e.g., aproximar tiempo de ejecución como función de clave parcial).

Figura 4

Polinomios base de Lagrange $l_i\left(x\right)$ para $n=3$ (cuatro puntos).

La figura muestra los polinomios base de Lagrange ( $l_i\left(x\right)$ ) para ($n = 3$ ), es decir, para un conjunto de 4 puntos. Los polinomios base de Lagrange son utilizados en la interpolación polinómica para construir el polinomio interpolador. Para ( $n = 3$ ), hay 4 puntos de datos, y cada uno de estos puntos está asociado con un polinomio base ( $l_i\left(x\right)$) que tiene la propiedad de que ( $l_i\left(x_j\right)=1$ ) cuando ($i = j$) y ( $l_i\left(x_j\right)=0$ ) para ( $i \ne j$). Esto significa que cada ( $l_i\left(x\right)$) toma el valor 1 en el punto ( $x_i$ ) y 0 en los demás puntos.

En la figura, probablemente se muestran las curvas de los 4 polinomios base ( $l_0\left(x\right)$ ), ( $l_1\left(x\right)$), ($l_2\left(x\right)$) y ( $l_3\left(x\right)$ ), cada uno de los cuales es un polinomio de grado 3 (ya que hay 4 puntos en total). Estas curvas se intersectan en los puntos de interpolación, y cada uno de ellos tiene su máximo en su respectivo nodo ( $x_i$), donde toma el valor 1, mientras que se acercan a cero en los otros nodos.

Cada polinomio base ( $l_i\left(x\right)$ ) contribuye a la construcción del polinomio interpolador, de manera que el polinomio total se puede escribir como una suma ponderada de estos polinomios base:

$P\left(x\right)={\sum }_{i=0}^3{y}_i{l}_i\left(x\right)$

donde ($y_i$) son los valores de la función en los puntos ( $x_i$ ). En la figura, se puede observar cómo cada polinomio base es responsable de "activar" el valor ( $y_i$ ) correspondiente en su respectivo punto ( $x_i$ ), mientras que los demás puntos son anulados (por eso los polinomios base toman valor 0 en esos puntos).

Figura 5

Construcción del polinomio de Lagrange: suma ponderada de bases.

9.1.3 Polinomio de Newton

Formulación matemática formal

El polinomio de Newton usa diferencias divididas y se escribe en forma anidada (Horner-like):

$P_n\left(x\right)=a_0+a_1\left(x-x_0\right)+a_2\left(x-x_0\right)\left(x-x_1\right)+\dots +a_n\left(x-x_0\right)\dots \left(x-x_{n-1}\right)$

donde los coeficientes $a_k$ son las diferencias divididas:

• $a_0=f\left[x_0\right]=y_0$
• $a_1=f\left[x_0,x_1\right]=\frac{y_1-y_0}{x_1-x_0}$
• $a_2=f\left[x_0,x_1,x_2\right]=\frac{f\left[x_1,x_2\right]-f\left[x_0,x_1\right]}{x_2-x_0}$
• En general: $f\left[x_0,\dots ,x_k\right]=\frac{f\left[x_1,\dots ,x_k\right]-f\left[x_0,\dots ,x_{k-1}\right]}{x_k-x_0}$

Ventajas:

• Forma anidada → evaluación O(n).
• Fácil añadir puntos nuevos (diferencias divididas adicionales).
• Estabilidad numérica mejor que Lagrange para evaluación secuencial.

Teorema: El polinomio de Newton coincide con el de Lagrange (mismo polinomio único).

En la clase anterior vimos la interpolación, donde una función pasa exactamente por todos los puntos dados. Ahora exploramos la aproximación (o ajuste de curvas), que busca la mejor representación posible cuando los datos contienen ruido, errores de medición o no se espera un ajuste perfecto.

La aproximación y el ajuste de curvas son técnicas utilizadas para encontrar una función que se acerque a un conjunto de datos, pero a diferencia de la interpolación, que busca una función que pase exactamente por todos los puntos, la aproximación busca una función que minimice el error global, es decir, que se acerque lo más posible a todos los puntos sin necesariamente pasar por cada uno de ellos. Mientras que la interpolación es útil cuando se desea una representación exacta de los datos, la aproximación es más adecuada cuando se trabaja con datos ruidosos o cuando se desea una solución más general que no dependa estrictamente de cada punto individual. Un método comúnmente utilizado para la aproximación de curvas es el método de mínimos cuadrados, que tiene como objetivo encontrar la mejor aproximación en el sentido de minimizar la suma de los cuadrados de las diferencias entre los valores observados y los valores predichos por la función ajustada. Este método se utiliza ampliamente en regresión y es particularmente eficaz cuando los datos presentan ruido o incertidumbre, ya que proporciona un compromiso entre los datos y una función general. El método de mínimos cuadrados se puede aplicar tanto a ajustes lineales como no lineales, dependiendo de la naturaleza de los datos y de la función que se quiera ajustar.

10.1 Diferencia entre interpolación y aproximación

Interpolación: Dada un conjunto finito de puntos {$(x\_i, y\_i)\}\_\{i=0\}^n$, se busca una función P(x) tal que $P\left(x_i\right)=y_i$ exactamente para todo i (error cero en los nodos). El polinomio interpolador único de grado ≤ n existe por el teorema de unicidad. El error en puntos intermedios está dado por el teorema de interpolación:

para algún ξ entre min($x,x_i$) y max($x,x_i$).

Aproximación (curve fitting): Cuando los datos $y_i$ contienen ruido (e.g., errores de medición, variabilidad aleatoria), no se busca pasar exactamente por todos los puntos, sino minimizar una medida global del error. El objetivo es encontrar una función g(x) (de una familia parametrizada, e.g., polinomios de grado bajo, exponenciales) que represente la tendencia general o el comportamiento subyacente.

Diferencia clave:

Interpolación → error cero en puntos dados; útil para datos precisos sin ruido.

Aproximación → minimiza error global (e.g., suma de cuadrados de residuos); útil para datos ruidosos o sobreajuste a evitar.

Teorema de aproximación (Weierstrass): Cualquier función continua en un intervalo cerrado puede aproximarse uniformemente por polinomios de grado arbitrariamente alto (pero en práctica, grado alto causa inestabilidad numérica).

Figura

Diferencia gráfica entre interpolación exacta (pasa por todos los puntos) y aproximación por mejor ajuste (best fit, minimiza error global).

10.1.1 Método de mínimos cuadrados

Dado un conjunto de m puntos {$(x\_i, y\_i)\}\_\{i=1\}^m$ ($m > n+1$ usualmente) y una familia de funciones lineales en parámetros:

$y\approx f\left(x;\beta \right)={\beta }_0{\phi }_0\left(x\right)+{\beta }_1{\phi }_1\left(x\right)+\dots +{\beta }_n{\phi }_n\left(x\right)$

donde {${\phi }_j\left(x\right)$} es una base (e.g., 1, x, x², … para polinomios; o exponenciales, logaritmos, etc. para no lineal).

El método de mínimos cuadrados encuentra el vector de parámetros ${\beta }^{*}$ que minimiza la suma de cuadrados de residuos (SSR o SSE):

$S\left(\beta \right)={\sum }_{i=1}^m{r}_i^2={\sum }_{i=1}^m{\left[y_i-f\left(x_i;\beta \right)\right]}^2$

Teorema fundamental (condición necesaria):

Si S(β) es diferenciable, el mínimo satisface las ecuaciones normales:

$\partial S/\partial {\beta }_j=0 para j=0,\dots ,n$

$\Rightarrow -2{\sum }_{i=1}^m\left[y_i-f\left(x_i;\beta \right)\right]\partial f/\partial {\beta }_j\left(x_i\right)=0$

Para ajuste lineal en parámetros (f lineal en $\beta$), esto da un sistema lineal:

$A^{T}A\beta =A^T$ y

donde A es la matriz de diseño ($A_{ij}={\phi }_j\left(x_i\right)$), y el vector $y={\left[y_1,\dots ,y_m\right]}^T$.

Solución: $\beta ={\left(A^{T}A\right)}^{-1}{A}^T$ y (si $A^{T}A$ invertible).

Error residual: $SSE=\sum {\left(y_i-\widehat{y_i}\right)}^2;R^2=1-SSE/SST$ ($SST =$ suma total de cuadrados respecto a la media).

Figura 7

Partición de varianza: TSS = RSS + ESS en regresión lineal.

La figura ilustra la partición de la varianza en el contexto de la regresión lineal y muestra cómo la varianza total de los datos (denotada como ( $\text{TSS}$ )) se descompone en dos componentes: la varianza explicada por el modelo (denotada como ( $\text{ESS}$ )) y la varianza no explicada, o residuos, (denotada como ( $\text{RSS}$ )).

TSS (Total Sum of Squares): Es la suma total de los cuadrados de las diferencias entre los valores observados y el valor medio de la variable dependiente ( y ). Representa la varianza total en los datos, o cuán dispersos están los puntos de datos en relación con la media. Se calcula como:

$\text{TSS}={\sum }_{i=1}^n{\left(y_i-\stackrel{-}{y}\right)}^2$

donde ( $y_i$) son los valores observados y ( $\stackrel{-}{y}$ ) es la media de ( y ).

RSS (Residual Sum of Squares): Es la suma de los cuadrados de las diferencias entre los valores observados y los valores predichos por el modelo de regresión. Representa la varianza que no es explicada por el modelo, es decir, la parte del error residual que no puede ser capturada por la línea de regresión. Se calcula como:

$\text{RSS}={\sum }_{i=1}^n{\left(y_i-\widehat{y_i}\right)}^2$

donde ( $\widehat{y_i}$ ) son los valores predichos por el modelo.

ESS (Explained Sum of Squares): Es la suma de los cuadrados de las diferencias entre los valores predichos por el modelo y la media de los valores observados. Representa la varianza que el modelo ha explicado o capturado. Se calcula como:

$\text{ESS}={\sum }_{i=1}^n{\left(\widehat{y_i}-\stackrel{-}{y}\right)}^2$

En la figura, estos tres componentes se muestran de manera que ( $\text{TSS}$ ) se descompone en ( $\text{ESS}$ ) y ( $\text{RSS}$ ). La relación es:

$\text{TSS}=\text{ESS}+\text{RSS}$

Esto muestra cómo la varianza total en los datos se reparte entre la parte explicada por el modelo y la parte no explicada (los errores residuales). El objetivo de la regresión lineal es maximizar ( $\text{ESS}$ ) y minimizar (RSS), logrando así un buen ajuste del modelo a los datos.

10.1.2 Ajuste lineal

Caso más simple: ajuste lineal (grado 1):

$y\approx {\beta }_0+{\beta }_{1}x$

Matriz de diseño A (m × 2):

$\begin{array}{cc}1& x_1\\ 1& x_2\\ ⋮& ⋮\\ 1& x_m\end{array}$

Ecuaciones normales:

$A^{T}A\beta =A^T$ y

$\begin{array}{cccc}m& \sum x_i& \sum x_i& \sum x_i^2\end{array}\begin{array}{c}{\beta }_0{\beta }_1\end{array}=\begin{array}{c}\sum y_i\sum x_i{y}_i\end{array}$

Solución explícita:

${\beta }_1=\frac{m\sum x_i{y}_i-\left(\sum x_i\right)\left(\sum y_i\right)}{m\sum x_i^2-{\left(\sum x_i\right)}^2}$

${\beta }_0=\stackrel{-}{y}-{\beta }_1\stackrel{-}{x}$

Teorema de Gauss-Markov (para errores independientes, media cero, varianza constante): el estimador de mínimos cuadrados es el mejor lineal insesgado (BLUE).

Figura 8

Ejemplo de regresión lineal con datos ruidosos: pendiente y ordenada calculadas.

10.1.3 Ajuste no lineal

Cuando el modelo es no lineal en parámetros:

$y \approx f(x; \beta )$, con β no lineal (e.g., $y\approx {\beta }_0{e}^{{\beta }_{1}x}$, $y\approx {\beta }_0+{\beta }_{1}sin\left({\beta }_{2}x+{\beta }_3\right)$, etc.).

No hay solución cerrada; se minimiza $S\left(\beta \right)=\sum {\left[y_i-f\left(x_i;\beta \right)\right]}^2$ mediante métodos numéricos iterativos (gradiente descendente, Levenberg-Marquardt, Gauss-Newton).

Gauss-Newton: aproximación lineal local de f alrededor de ${\beta }^{\left(k\right)}$:

$f\left(x;\beta \right)\approx f\left(x;{\beta }^{\left(k\right)}\right)+J\left({\beta }^{\left(k\right)}\right)\left(\beta -{\beta }^{\left(k\right)}\right)$

donde J es la matriz Jacobiana ($\partial f/\partial {\beta }_j$evaluada en ${\beta }^{\left(k\right)}$).

Iteración: ${\beta }^{\left(k+1\right)}={\beta }^{\left(k\right)}+{\left(J^{T}J\right)}^{-1}{J}^T{r}^{\left(k\right)}$, donde $r^\left\{\right(k\left)\right\} = y - f({\beta }^{\left(k\right)}$).

Levenberg-Marquardt: modifica Gauss-Newton añadiendo término de amortiguación: ($J^T J + \lambda I)^\{-1\}$ para estabilidad.

Convergencia: localmente cuadrática si Jacobiana tiene rango completo y buena inicial.