En la clase anterior exploramos métodos cerrados (de acotamiento) para encontrar raíces de ecuaciones no lineales $f\left(x\right) = 0$. Ahora pasamos a los métodos abiertos (open methods), que no requieren intervalos que acoten la raíz y suelen converger más rápido cuando se inicia cerca de la solución, aunque pueden divergir si la aproximación inicial es mala o la función tiene propiedades desfavorables.

En esta clase nos centramos en tres métodos abiertos clásicos: el de punto fijo, Newton-Raphson y secante. Presentamos primero la formulación matemática formal, teoremas de convergencia y orden, y luego las aplicaciones en ciberseguridad, como en criptoanálisis polinómico (e.g., ataques Coppersmith para RSA) o recuperación de claves parciales.

5.1 Métodos abiertos

Los métodos abiertos son una clase de técnicas numéricas que se utilizan para encontrar las raíces de una ecuación. A diferencia de los métodos cerrados, que requieren un intervalo en el que se sabe que existe una raíz, los métodos abiertos parten de una aproximación inicial $x₀$ (o dos, en el caso del método de la secante) y generan sucesivas aproximaciones $xₖ$ para acercarse a la solución. La idea es aplicar una fórmula iterativa, como $xₖ₊₁ = g\left(xₖ\right)$, donde $g\left(x\right)$ es una función que se deriva de la ecuación original y se utiliza para obtener el siguiente valor de la iteración a partir del anterior.

Una característica clave de los métodos abiertos es que no necesitan que la raíz esté dentro de un intervalo específico, lo que los hace más flexibles que los métodos cerrados. Sin embargo, su principal desventaja es que no siempre garantizan que las iteraciones converjan a la solución. La convergencia depende de la función elegida y de la elección de la aproximación inicial. Además, estos métodos no ofrecen una "acotación" de la solución, es decir, no aseguran que los valores de las iteraciones se mantendrán dentro de un rango cercano a la solución verdadera, lo que puede llevar a resultados erróneos si no se seleccionan correctamente.

La velocidad de convergencia de los métodos abiertos es una propiedad importante y está relacionada con el orden de convergencia. El orden de convergencia se refiere a la rapidez con que las iteraciones se acercan a la solución exacta. Los métodos que tienen un mayor orden de convergencia son más eficientes porque requieren menos iteraciones para alcanzar una precisión dada. Algunos métodos populares, como el método de Newton-Raphson o el método de la secante, se incluyen en esta categoría, siendo el primero de ellos particularmente conocido por su alta velocidad de convergencia, que es cuadrática, siempre y cuando se elija una buena aproximación inicial.

5.1.1 Método del punto fijo

El método del punto fijo transforma f(x) = 0 en x = g(x), donde g(x) es una función continua tal que si α es raíz de f entonces α = g(α) (punto fijo de g).

La iteración es:

Teorema de convergencia

Suponga que g es continua en un intervalo cerrado I que contiene α, y que g es contractiva en I, es decir, existe L < 1 tal que |g'(x)| ≤ L para todo x en I (o Lipschitz con constante L < 1). Entonces:

• Existe un único punto fijo α en I.
• Para cualquier x₀ en I, la secuencia {x_k} converge a α.
• La convergencia es lineal: |x_{k+1} - α| ≤ L |x_k - α|.

Si g ∈ C¹ cerca de α y |g'(α)| < 1, entonces existe un vecindario donde la iteración converge linealmente con tasa |g'(α)|. Si |g'(α)| > 1 diverge; si =1, convergencia más lenta o no garantizada.

Orden de convergencia Lineal (orden 1) si g'(α) ≠ 0; superlineal o más alto si g'(α) = 0 y derivadas superiores controladas.

5.1.2 Método de Newton–Raphson

Definimos el Método de Newton-Raphson: derivado de la aproximación lineal (tangente) de f cerca de

Teorema de convergencia

Suponga f ∈ C² en un vecindario de α (raíz simple, f(α)=0, f'(α) ≠ 0). Entonces existe δ > 0 tal que si |x₀ - α| < δ, la secuencia converge a α.

Orden de convergencia Cuadrático (orden 2): si f'(α) ≠ 0 y f ∈ C², entonces:

$\underset{k\to \infty }{\lim }\frac{\left|x_{k+1}-\alpha \right|}{{\left|x_k-\alpha \right|}^2}=\left|\frac{f^{\text{'}\text{'}}\left(\alpha \right)}{2f^{\text{'}}\left(\alpha \right)}\right|$

Derivación vía expansión de Taylor:

$x_{k+1}-\alpha =x_k-\alpha -\frac{f\left(x_k\right)}{f^{\text{'}}\left(x_k\right)}=\left(x_k-\alpha \right)-\frac{f^{\text{'}}\left(\alpha \right)\left(x_k-\alpha \right)+\frac{1}{2}{f}^{\text{'}\text{'}}\left({\xi }_k\right){\left(x_k-\alpha \right)}^2+O\left({\left(x_k-\alpha \right)}^3\right)}{f^{\text{'}}\left(x_k\right)}\approx \left(x_k-\alpha \right)-\left(x_k-\alpha \right)-\frac{f^{\text{'}\text{'}}\left(\alpha \right)}{2f^{\text{'}}\left(\alpha \right)}{\left(x_k-\alpha \right)}^2+O\left({\left(x_k-\alpha \right)}^3\right)\Rightarrow erro{r}_{k+1}\approx C{\left(erro{r}_k\right)}^2,conC=-f^{\text{'}\text{'}}\left(\alpha \right)/\left(2f^{\text{'}}\left(\alpha \right)\right)$

Fundamental en ataques Coppersmith: encontrar raíces pequeñas de polinomios modulares (e.g., RSA con MSB/LSB conocidos o mensajes pequeños). Newton refina aproximaciones iniciales de raíces modulares. También en optimización de ataques side-channel (ajuste de parámetros) o entrenamiento de ML para detección (gradiente descendente es Newton-like).

5.1.3 Método de la secante

Aproximación de la derivada por diferencia finita:

Requiere dos iniciales x₀, x₁.

Teorema de convergencia

Suponga f ∈ C² cerca de α (raíz simple, f'(α) ≠ 0). Si x₀, x₁ suficientemente cercanos a α, converge a α.

Orden de convergencia Superlineal con orden $\phi = (1 + \surd 5)/2 \approx 1.618$ (razón áurea): $\underset{k\to \infty }{\lim }\frac{\left|x_{k+1}-\alpha \right|}{{\left|x_k-\alpha \right|}^{\varphi }}={\left|\frac{f^{\text{'}\text{'}}\left(\alpha \right)}{2f^{\text{'}}\left(\alpha \right)}\right|}^{1/\varphi }$

Derivación vía error: $erro{r}_{k+1}\approx Cerro{r}_{k}erro{r}_{k-1}$, llevando a la ecuación característica r² - r - 1 = 0, raíces φ y 1-φ (tomamos la positiva).

El método de la secante es un método iterativo utilizado para encontrar las raíces de una función no lineal, y es una alternativa al método de Newton-Raphson. En este método, en lugar de utilizar la derivada de la función para aproximar la tangente en cada iteración, se utiliza una cuerda (o secante) que conecta dos puntos cercanos en el gráfico de la función para aproximar la tangente en el punto de interés.

Consideremos que estamos resolviendo la ecuación $f\left(x\right)=0$ utilizando el método de la secante, con una función $f\left(x\right)$y dos valores iniciales $x_0$y $x_1$. Supongamos que la raíz real es $\alpha$, y en las iteraciones sucesivas calculamos los valores aproximados $x_0,x_1,x_2,\dots$.

• En la primera iteración, el error es $\mid x_1-\alpha \mid$.
• En la segunda iteración, el error es $\mid x_2-\alpha \mid$.
• En la tercera iteración, el error es $\mid x_3-\alpha \mid$.

La tasa de reducción del error en cada iteración debería ser proporcional a un factor cercano a $1/\phi$, lo que significa que el error se reduce aproximadamente por un factor de 1.618 en cada paso.

Si calculamos el ratio de los errores en dos iteraciones consecutivas $\mid x_n-\alpha \mid$y $\mid x_{n+1}-\alpha \mid$, el valor de este ratio debe converger a $\phi$. Es decir:

Este valor indica que la reducción del error en cada iteración sigue una tasa de convergencia superlineal, con un orden de convergencia de aproximadamente 1.618.

En las clases anteriores hemos estudiado métodos cerrados (bisección, falsa posición) y abiertos (punto fijo, Newton-Raphson, secante) para resolver $f\left(x\right) = 0$. Ahora analizamos su comportamiento cuantitativo: si convergen, con qué velocidad y cómo compararlos. Este análisis es esencial para seleccionar el método adecuado en aplicaciones de ciberseguridad, donde la eficiencia computacional y la robustez frente a errores numéricos pueden marcar la diferencia entre un ataque exitoso y uno fallido.

Presentamos primero los conceptos matemáticos formales, teoremas y definiciones, y después las implicaciones en ciberseguridad.

6.1 Concepto de convergencia

Una secuencia ${x_{n}n=0}^{\infty }$ converge a α (raíz de f(x) = 0) si $\lim n\to \infty \left|x_n-\alpha \right|=0$.

En métodos iterativos $x_{n+1}=g\left(x_n\right)$ (punto fijo) o variantes, la convergencia depende de la aproximación inicial $x_0$, propiedades de g y la naturaleza de la raíz (simple o múltiple).

Convergencia local: existe δ > 0 tal que si |x_0 - α| < δ, entonces {x_n} → α.

Convergencia global: converge para cualquier x_0 en un dominio amplio (raro en métodos abiertos).

En ciberseguridad: convergencia local es común (e.g., Newton en Coppersmith requiere buena inicial cerca de la raíz pequeña); convergencia global es deseable en búsquedas exhaustivas o ataques side-channel.

a) Características de la convergencia:

• La función $g\left(x\right)$debe cumplir con ciertas condiciones para garantizar la convergencia, como que $\mid g^{\text{'}}\left(x\right)\mid <1$en la vecindad de la raíz $\alpha$. Esto significa que la pendiente de la función en ese punto es menor que 1, lo que asegura que el valor iterado se acerque más a la raíz en cada paso.
• A medida que se realizan más iteraciones, los puntos $x_n$se aproximan progresivamente al valor de la raíz $\alpha$.

b) Características de la divergencia:

• La divergencia generalmente ocurre cuando la función $g\left(x\right)$no satisface los criterios de convergencia, como cuando $\mid g^{\text{'}}\left(x\right)\mid \ge 1$cerca de la raíz. Si la pendiente de la función es mayor o igual a 1, los valores iterados pueden alejarse de la raíz en lugar de acercarse a ella.

6.1.1 Criterios de convergencia

Criterio práctico de parada (en implementación):

• $\left|x_{n+1}-x_n\right|<\epsilon$ (cambio absoluto pequeño).
• $\left|f\left(x_{n+1}\right)\right|<\epsilon$ (residuo pequeño).
• $\left|x_{n+1}-x_n\right|/\left|x_{n+1}\right|<\epsilon$ (error relativo).
• Número máximo de iteraciones alcanzado (para evitar bucles infinitos).

Teorema de convergencia para punto fijo

Sea g ∈ C¹ en intervalo I que contiene α = g(α). Si |g'(α)| < 1, entonces existe vecindario donde la iteración converge linealmente con tasa |g'(α)|. Si |g'(α)| > 1, diverge; si =1, convergencia sublineal o no garantizada.

Para Newton-Raphson: si f ∈ C², f(α)=0, f'(α) ≠ 0 (raíz simple), converge localmente cuadráticamente.

Para secante: si f ∈ C², f'(α) ≠ 0, converge localmente con orden (1 + √5)/2 ≈ 1.618.

Para bisección: converge siempre si f continua y f(a)f(b) < 0; tasa lineal con constante 1/2 (error ≤ (b-a)/2^n).

Para falsa posición: converge si f continua y cambio de signo, pero tasa variable (lineal en peor caso, superlineal si función convexa).

En ciberseguridad: criterios estrictos evitan falsos positivos en detección (e.g., residuo < 10^{-12} en correlación CPA); convergencia garantizada (bisección) es clave en búsquedas seguras de claves parciales.

6.1.2 Orden de convergencia

Definición formal: Una secuencia $x_n$ converge a α con orden p ≥ 1 si existe constante λ > 0 tal que $\underset{n\to \infty }{\lim }\frac{\left|x_{n+1}-\alpha \right|}{{\left|x_n-\alpha \right|}^p}$.

• $p = 1$: convergencia lineal (tasa constante <1).
• $p = 2$: cuadrática (error se cuadra cada iteración).
• $p \approx 1.618$: superlineal (secante, razón áurea).

Teorema para Newton-Raphson (raíz simple): Si $f\in C^2$ cerca de $\alpha$, $f^{\text{'}}\left(\alpha \right)\ne 0$, entonces orden $p=2y\underset{n\to \infty }{\lim }\frac{\left|x_{n+1}-\alpha \right|}{{\left|x_n-\alpha \right|}^2}=\left|\frac{f^{\text{'}\text{'}}\left(\alpha \right)}{2f^{\text{'}}\left(\alpha \right)}\right|$.

Para secante: Orden p = (1 + √5)/2 ≈ 1.618 (raíz positiva de r² - r - 1 = 0), constante asintótica involucra f''/f'.

Para punto fijo: p = 1 si |g'(α)| < 1 ≠ 0; p > 1 si g'(α) = 0 y derivadas superiores nulas hasta cierto orden.

Para bisección: p = 1, tasa 1/2 (error se reduce a la mitad cada iteración).

Para falsa posición: p = 1 en peor caso (estancamiento en un lado), pero puede ser superlineal en casos favorables.

En ciberseguridad: métodos de orden alto (Newton p=2) son preferidos en criptoanálisis (Coppersmith, lattices) por su rapidez; bisección (p=1 garantizado) en búsquedas seguras donde no se tolera divergencia.

Donde:

• $e_n=\mid x_n-\alpha \mid$es el error en la $n$-ésima iteración,
• $p$es el orden de convergencia,
• $C$es una constante.

En términos sencillos:

• Convergencia lineal significa que el error disminuye de manera proporcional a un factor constante en cada iteración.
• Convergencia cuadrática significa que el error disminuye exponencialmente, con el error reduciéndose de manera cuadrática en cada iteración.
• Convergencia superlineal es más rápida que la lineal, pero más lenta que la cuadrática.

Comportamiento de los Métodos Comparados:

Método de Bisección (Convergencia Lineal):

El método de bisección es un método muy confiable que siempre converge hacia la raíz de una función, pero su convergencia es lineal, lo que significa que el error disminuye de manera proporcional en cada iteración.

• Comportamiento en el gráfico:
• El error absoluto en la bisección disminuye de forma constante en cada iteración.
• El gráfico mostrará una pendiente suave y lenta, con una reducción gradual del error en cada paso.
• La curva de la bisección será una línea recta inclinada, que refleja la reducción constante del intervalo en cada paso, lo que reduce el error en una cantidad proporcional con cada iteración.

Método de Newton-Raphson (Convergencia Cuadrática):

El método de Newton-Raphson tiene una convergencia cuadrática, lo que significa que el error disminuye de forma exponencial en cada iteración. Esto se traduce en que, si la aproximación inicial está cerca de la raíz, la solución se encuentra muy rápidamente.

• Comportamiento en el gráfico:
• La curva de error absoluto será muy pronunciada en las primeras iteraciones, ya que el error disminuye muy rápidamente en cada paso.
• Al principio, la reducción del error es muy grande, pero conforme el valor de la raíz se aproxima más y más, la disminución del error se vuelve más lenta.
• El gráfico tendrá una pendiente empinada al inicio, que luego se va aplanando conforme las iteraciones avanzan y el error se reduce a niveles más pequeños.
• La convergencia cuadrática es lo que hace que el método de Newton-Raphson sea extremadamente eficiente cuando la aproximación inicial está cerca de la raíz.

Método de Secante (Convergencia Superlineal):

El método de secante tiene una convergencia superlineal, lo que significa que su tasa de convergencia es más rápida que la convergencia lineal de la bisección, pero no tan rápida como la convergencia cuadrática de Newton-Raphson.

• Comportamiento en el gráfico:
• La curva de error absoluto para el método de secante será más empinada que la de la bisección, pero no tan empinada como la de Newton-Raphson.
• El error se reduce más rápidamente que en la bisección, pero no alcanza la misma rapidez de convergencia que el método de Newton-Raphson.
• La curva mostrará una reducción acelerada del error en las primeras iteraciones, pero la tasa de disminución del error se estabiliza de manera más gradual en comparación con Newton-Raphson.

6.1.3 Comparación entre métodos

En general: métodos cerrados → robustez; abiertos → velocidad (cuando convergen). Elección: usar cerrado para inicializar, abierto para refinar.

En ciberseguridad: Newton/secante en ataques eficientes (criptoanálisis polinómico, lattices); bisección en validaciones seguras donde divergencia no es aceptable.