En las clases anteriores nos centramos en ecuaciones no lineales de una variable. Ahora pasamos a sistemas de ecuaciones lineales, que constituyen uno de los pilares fundamentales de los métodos numéricos y tienen aplicaciones críticas en computación y ciberseguridad.

Presentamos primero la formulación matemática formal, propiedades y teoremas relevantes, y posteriormente las implicaciones directas en ciberseguridad.

Los sistemas de ecuaciones lineales son conjuntos de ecuaciones donde las incógnitas aparecen solo con exponente uno y sin productos entre ellas. Estos sistemas se pueden expresar de manera compacta utilizando matrices.

7.1 Formulación de sistemas de ecuaciones lineales

Un sistema de m ecuaciones lineales con n incógnitas se escribe en forma matricial como:

$Ax = b$

donde

• A ∈ $R^{m\times n}$ es la matriz de coeficientes,
• x ∈ $R^n$ es el vector de incógnitas,
• b ∈ $R^m$ es el vector de términos independientes.

En el caso cuadrado (m = n), el sistema es determinado si det(A) ≠ 0 (matriz invertible), sobredeterminado si m > n, o subdeterminado si m < n. En la práctica numérica nos enfocamos principalmente en sistemas cuadrados no singulares.

Propiedades clave:

• Matriz invertible ⇔ det(A) ≠ 0 ⇔ rango(A) = n ⇔ columnas linealmente independientes ⇔ solución única $x=A^{-1}$ b.
• Número de condición $\kappa \left(A\right)=\left|\left|A\right|\right|·\left|\left|A^{-1}\right|\right|$ (en alguna norma inducida, usualmente 2-norma o ∞-norma): mide sensibilidad a perturbaciones. Si κ(A) grande (mal condicionado), pequeños errores en A o b producen grandes errores en x.

Teorema de existencia y unicidad (sistemas cuadrados): El sistema $Ax = b$ tiene solución única si y solo si A es invertible. En ese caso, $x=A^{-1}$ b.

En ciberseguridad: estos sistemas aparecen en criptoanálisis basado en lattices (e.g., resolución de sistemas lineales modulares o aproximados en ataques BKZ/LLL), criptografía lineal (ataques lineales a cifrados de bloques como AES), reconstrucción de claves en side-channel (regresión lineal sobre múltiples trazas), y en machine learning para seguridad (resolución de mínimos cuadrados en entrenamiento o detección de anomalías).

Figura 1

Representación matricial Ax = b para un sistema de 4 ecuaciones y 4 incógnitas.

Este sistema puede resolverse usando diversos métodos de álgebra lineal, como:

• Método de eliminación de Gauss (o Gauss-Jordan),
• Método de matrices inversas,
• Método de factorización LU,
• O utilizando métodos iterativos si se trata de un sistema grande.

Este formato de Ax = b facilita la aplicación de algoritmos computacionales para resolver sistemas de ecuaciones de manera eficiente.

Figura 2

Ilustración geométrica de solución única, infinitas o ninguna en sistemas 2D y 3D.

Sistemas en 2D (Dos Ecuaciones, Dos Incógnitas)

Para un sistema de 2 ecuaciones lineales con 2 incógnitas (por ejemplo, $ax+by=c$y $dx+ey=f$), la representación geométrica se puede visualizar en el plano cartesiano como dos líneas. Dependiendo de la relación entre estas dos líneas, se puede tener uno de los siguientes casos:

a) Solución Única (Intersección de dos líneas):

• En este caso, las dos líneas se intersectan en un único punto.
• La solución del sistema de ecuaciones es el punto de intersección, que representa los valores de las incógnitas $x$y $y$que satisfacen ambas ecuaciones.
• Geometría: Dos líneas que se cortan en un solo punto.
• Condición: Las dos ecuaciones tienen una pendiente diferente, es decir, $\frac{a}{b}\ne \frac{d}{e}$.

b) Infinitas Soluciones (Líneas coincidentes):

• En este caso, ambas ecuaciones representan la misma línea en el plano, es decir, las dos ecuaciones son dependientes y no proporcionan nueva información.
• La solución del sistema es cualquier punto sobre la línea común, ya que todos esos puntos satisfacen ambas ecuaciones.
• Geometría: Dos líneas coincidentes.
• Condición: Las ecuaciones son proporcionales entre sí, es decir, $\frac{a}{b}=\frac{d }{e}$ y $\frac{c}{b}=\frac{f}{e}$.

c) Ninguna Solución (Líneas paralelas):

• En este caso, las dos ecuaciones representan líneas paralelas que nunca se intersectan, lo que significa que no hay ningún punto que satisfaga ambas ecuaciones.
• Geometría: Dos líneas paralelas.
• Condición: Las ecuaciones son inconsistentes, es decir, las pendientes son iguales pero los términos independientes no lo son (por ejemplo, $\frac{a}{b}=\frac{d}{e}$pero $\frac{c}{b}\ne \frac{f}{e}$).

Sistemas en 3D (Tres Ecuaciones, Tres Incógnitas)

Para un sistema de 3 ecuaciones lineales con 3 incógnitas (por ejemplo, $ax+by+cz=d$, $ex+fy+gz=h$, y $ix+jy+kz=l$), la representación geométrica se extiende al espacio tridimensional. En este caso, las soluciones se representan como planos en 3D, y el comportamiento del sistema dependerá de cómo se relacionen estos planos entre sí.

a) Solución Única (Intersección de tres planos en un punto):

• En este caso, los tres planos se intersectan en un único punto en el espacio 3D.
• La solución del sistema es el punto de intersección de los tres planos, que representa los valores de $x$, $y$, y $z$que satisfacen todas las ecuaciones.
• Geometría: Tres planos que se intersectan en un solo punto.
• Condición: Las tres ecuaciones son independientes, y los planos no son paralelos ni coincidentes.

b) Infinitas Soluciones (Planos coincidentes o paralelos):

• Si dos o más planos son coincidentes o paralelos, el sistema tendrá infinitas soluciones, ya que cualquier punto sobre la intersección de los planos será una solución.
• Dependiendo del caso, las soluciones pueden estar restringidas a una línea o una superficie en el espacio.
• Geometría: Planos coincidentes o paralelos.
• Condición: Las ecuaciones son dependientes, y los planos no tienen una intersección única, sino que se solapan en una línea o se paralelizan.

c) Ninguna Solución (Planos paralelos o no coincidentes):

• Si los tres planos son paralelos pero no coincidentes, no existe ninguna solución, ya que los planos no se intersectan en ningún punto.
• Geometría: Planos paralelos y no coincidentes.
• Condición: Las ecuaciones son inconsistentes; los planos son paralelos pero tienen diferentes términos independientes.

7.1.1 Métodos directos

Los métodos directos encuentran la solución exacta (en aritmética exacta) en un número finito de operaciones aritméticas, sin iteraciones ni aproximaciones sucesivas. Incluyen eliminación de Gauss, factorización LU, Cholesky (para matrices simétricas definidas positivas), QR, etc.

Ventajas matemáticas:

• Precisión teórica alta si no hay errores de redondeo.
• Costo computacional predecible: O(n³) para Gauss/LU en sistemas densos n×n.

Desventajas: sensibles a errores de redondeo en matrices mal condicionadas; no escalan bien para matrices muy grandes o dispersas (donde se prefieren métodos iterativos).

7.1.2 Eliminación de Gauss

La eliminación de Gauss transforma A en una matriz triangular superior U mediante operaciones elementales de fila (intercambio, multiplicación por escalar ≠0, suma de múltiplo de una fila a otra).

Proceso:

1. Para k = 1 a n-1:

• Pivote: $a_{kk}$ (si =0, intercambiar filas para pivote ≠0 → pivoteo parcial).
• Eliminadores: $l_{ik}=a_{ik}/a_{kk}$ para $i = k+1 a n$.
• Actualizar: $fila i\leftarrow filai-l_{ik}·fila k$ (para i > k, columnas j ≥ k).

Resultado: Ax = b → Ux = c, donde U es triangular superior.

Luego, sustitución hacia atrás (back-substitution): $x_n=c_n/u_{nn}{x}_k=\left(c_k-{\sum }_{j=k+1}^n{u}_{kj}{x}_j\right)/u_{kk}parak=n-1$ downto 1.

Complejidad: O(n³/3) operaciones flotantes.

Estabilidad: con pivoteo parcial, numéricamente estable en la mayoría de los casos (aunque no siempre óptimo).

Figura 3

Pasos de eliminación de Gauss sin pivoteo: transformación a triangular superior.

7.1.3 Factorización LU

Formulación matemática formal

La factorización LU descompone A = L U, donde:

• L es triangular inferior con 1's en la diagonal (unitaria),
• U es triangular superior.

Si no se requiere pivoteo: $A=LU\Rightarrow Ax=b\iff L\left(Ux\right)=b\iff Ly=b$(sustitución hacia adelante), luego $Ux = y$ (hacia atrás).

Con pivoteo parcial: $A = P L U$, donde $P$ es matriz de permutación. Entonces $PAx = Pb \iff L U x = P b$.

Algoritmo de factorización LU con pivoteo parcial (Doolittle o Crout):

• Inicializar L con 1's en diagonal, U vacía.
• Para cada columna k:
• Buscar pivote máximo en fila $\ge k \to$ intercambiar filas (registrar en P).
• Calcular multiplicadores $l_{ik}=a_{ik}^{\left(k\right)}/a_{kk}^{\left(k\right)}$ (para $i > k$).
• Actualizar submatriz restante.

Complejidad: O(n³/3), mismo que Gauss-Jordan, pero más eficiente en almacenamiento y reutilización (factorizar una vez, resolver múltiples $b$).

Teorema de existencia: Toda matriz cuadrada no singular admite factorización LU con pivoteo parcial (sin crecimiento excesivo de elementos si se usa pivoteo).

Figura 4

Factorización LU sin pivoteo: L (multiplicadores debajo diagonal) y U (triangular superior).

Dado un sistema de ecuaciones lineales $Ax=b$, el objetivo es descomponer la matriz $A$en el producto de una matriz triangular inferior $L$y una matriz triangular superior $U$, es decir:

$A=LU$

Sin embargo, para mejorar la estabilidad numérica, se realiza un proceso de pivoteo parcial, lo que implica intercambiar filas de la matriz $A$durante el proceso de eliminación para garantizar que los pivotes sean lo más grandes posible, lo que minimiza el error numérico.

En la Clase 7 estudiamos métodos directos para resolver sistemas lineales $Ax = b$ (eliminación de Gauss, factorización LU). Ahora exploramos los métodos iterativos, ideales para matrices grandes, dispersas o mal condicionadas donde los métodos directos son costosos o inestables numéricamente.

Presentamos primero la formulación matemática formal, algoritmos, teoremas de convergencia y criterios, y posteriormente las aplicaciones en ciberseguridad.

Los métodos iterativos son herramientas esenciales para resolver sistemas de ecuaciones lineales, particularmente en situaciones donde se enfrentan sistemas grandes que no son prácticos de resolver mediante métodos directos como la eliminación de Gauss o la descomposición LU. Estos métodos no proporcionan una solución exacta de inmediato, sino que se aproximan a la solución mediante sucesivas iteraciones. El Método de Jacobi, por ejemplo, se basa en descomponer cada ecuación del sistema en términos de las incógnitas que aún no han sido actualizadas. Esto implica que en cada iteración, se usan los valores de las incógnitas obtenidas en la iteración anterior para calcular los nuevos valores. Este proceso se repite de forma sucesiva hasta que las diferencias entre los valores de las incógnitas en dos iteraciones consecutivas son mínimas, indicando que se ha alcanzado una solución aproximada suficientemente precisa.

El Método de Gauss-Seidel es una variante que mejora el proceso iterativo de Jacobi. A diferencia de este último, en Gauss-Seidel se utilizan los valores más recientes de las incógnitas dentro de la misma iteración, lo que puede resultar en una convergencia más rápida, ya que se aprovecha la información actualizada de inmediato. Este método es generalmente más eficiente, pero aún depende de las características del sistema de ecuaciones para su efectividad. Ambos métodos, aunque muy útiles, requieren un análisis cuidadoso de la convergencia para garantizar que las soluciones obtenidas sean válidas. Existen ciertos criterios matemáticos que permiten determinar si un sistema de ecuaciones lineales se comportará de manera convergente bajo estos métodos iterativos. La convergencia se refiere a la capacidad del proceso iterativo para acercarse cada vez más a la solución exacta, y si estos criterios no se cumplen, los métodos podrían no converger o hacerlo muy lentamente, lo que puede llevar a resultados inexactos.

8.1 Métodos iterativos

Los métodos iterativos generan una secuencia {$x^{\left(k\right)}$} que converge a la solución $x^{*}=A^{-1}b$ (asumiendo A invertible). Se basan en una división (splitting) de $A = M - N$, donde M es fácil de invertir (e.g., diagonal o triangular), y la iteración es:

$M{x}^{\left(k+1\right)}=N{x}^{\left(k\right)}+b$ o equivalentemente $x^{\left(k+1\right)}=M^{-1}N{x}^{\left(k\right)}+M^{-1}b=G{x}^{\left(k\right)}+c$

donde $G=M^{-1}$ N es la matriz de iteración y $c=M^{-1}b$.

Teorema fundamental de convergencia (para cualquier método iterativo $x^\left\{\right(k+1\left)\right\} = G x^\left\{\right(k\left)\right\} + c)$: La iteración converge a la solución única$x^{*}$ para cualquier inicial $x^{\left(0\right)}$ si y solo si el radio espectral ρ(G) < 1, es decir, todas las autofunciones de G tienen módulo <1.

Además, si ρ(G) < 1, el error $e^{\left(k\right)}=x^{\left(k\right)}-x^{*}$ satisface $‖e^{\left(k\right)}‖\le C\rho {\left(G\right)}^k‖e^{\left(0\right)}‖$ para alguna constante C > 0 y norma subordinada. La tasa asintótica de convergencia es -log₁₀(ρ(G)) dígitos por iteración (cuanto menor ρ(G), más rápido).

8.1.1 Método de Jacobi

División: A = D + (L + U), donde D diagonal, L estrictamente triangular inferior, U estrictamente superior. Entonces M = D, N = -(L + U).

Iteración$:D{x}^{\left(k+1\right)}=-\left(L+U\right)x^{\left(k\right)}+b$ o componente a componente:

Matriz de iteración: $G_J=-D^{-1}\left(L+U\right)=I-D^{-1}A$.

Teorema de convergencia

El método de Jacobi converge para cualquier $x^{\left(0\right)}$ si $\rho \left(G_J\right)<1$. Condición suficiente (no necesaria): A estrictamente diagonalmente dominante por filas: $\forall i:\left|a_{ii}\right|>{\sum }_{j\ne i}\left|a_{ij}\right|$ En este caso, ‖G_J‖∞ < 1 (usando norma ∞), lo que implica $\rho \left(G_J\right)\le ‖G_J‖\infty <1$.

Orden de convergencia: lineal (orden 1), tasa ρ(G_J).

Figura 5

Descomposición A = D + L + U para Jacobi y matriz de iteración G_J.

8.1.2 Método de Gauss–Seidel

División: A = (D + L) + U, donde D + L triangular inferior. Entonces M = D + L, N = -U.

Iteración: $\left(D+L\right)x^{\left(k+1\right)}=-U{x}^{\left(k\right)}+b$ o componente a componente (actualización inmediata):

Matriz de iteración: $G_{GS}=-{\left(D+L\right)}^{-1}U$.

Teorema de convergencia

El método converge para cualquier $x^{\left(0\right)}$ si $\rho \left(G_{GS}\right)<1$. Condiciones suficientes:

1. A estrictamente diagonalmente dominante (por filas o columnas).
2. A simétrica y definida positiva (entonces converge, y Gauss-Seidel es más rápido que Jacobi).

Gauss-Seidel converge más rápido que Jacobi cuando converge ($\rho (G_{GS}$) ≤ $\rho {\left(G_J\right)}^2$ en muchos casos, e.g., matrices simétricas positivas definidas).

Figura 6

Actualización secuencial en Gauss-Seidel: usa valores nuevos inmediatamente.

La figura muestra el proceso de actualización secuencial en el método de Gauss-Seidel, en el cual los nuevos valores de la solución se utilizan inmediatamente para calcular las siguientes iteraciones. A diferencia del método de Jacobi, donde todos los valores de la iteración anterior se emplean para calcular los nuevos valores en paralelo, en Gauss-Seidel se actualiza el valor de cada componente de la solución de manera secuencial, es decir, tan pronto como se calcula un nuevo valor ( $x_i^{\left(k+1\right)}$ ), este se utiliza de inmediato para actualizar el siguiente valor ( $x_j^{\left(k+1\right)}$ ). Esto significa que, durante una misma iteración, los componentes de la solución se van actualizando uno a uno, lo que puede acelerar la convergencia del método en comparación con el método de Jacobi, ya que cada actualización puede aprovechar los nuevos valores que ya se han calculado.

Figura 7

Comparación de error vs iteraciones: Gauss-Seidel más rápido que Jacobi.

8.1.3 Criterios de convergencia en sistemas

Criterios prácticos de parada:

• Residuo pequeño: $‖r^{\left(k\right)}‖=‖A{x}^{\left(k\right)}-b‖<\epsilon$ (norma ∞ o 2 usual).
• Cambio relativo: $‖x^{\left(k+1\right)}-x^{\left(k\right)}‖/‖x^{\left(k+1\right)}‖<\epsilon$.
• Máximo de iteraciones (para evitar bucles infinitos si no converge).

Criterios teóricos para convergencia garantizada:

1. ρ(G) < 1 (necesario y suficiente).
2. ‖G‖ < 1 en alguna norma subordinada (suficiente).
• Para Jacobi: si A estrictamente diagonalmente dominante → ‖G_J‖_∞ < 1.
• Para Gauss-Seidel: lo mismo, más simétrica positiva definida.
3. Diagonal dominance estricta o irreducible (suficiente para ambos métodos).

Teorema general: Si ρ(G) < 1, converge para cualquier inicial; si ρ(G) ≥ 1, diverge o converge condicionalmente.

Figura 8

Matriz estrictamente diagonalmente dominante y su impacto en ρ(G).

Una matriz ( $A$ ) es estrictamente diagonalmente dominante si, para cada fila ($i$), el valor absoluto del elemento en la diagonal es mayor que la suma de los valores absolutos de los elementos fuera de la diagonal en esa misma fila, es decir,

$\left|a_{ii}\right|>{\sum }_{j\ne i}\left|a_{ij}\right|$