Sistemas lineales: eliminación de Gauss, LU, Jacobi y Gauss-Seidel

Resolver un circuito por nudos, calcular las fuerzas en una estructura o simular el calor en una pieza con elementos finitos acaba siempre en lo mismo: un sistema lineal

A\mathbf{x} = \mathbf{b}

, a veces con millones de incógnitas. La regla de Cramer es inútil a esa escala. Los métodos numéricos se dividen en directos, que dan la solución en un número fijo de pasos, e iterativos, que la aproximan cada vez mejor.

Lo que vas a aprender

La eliminación de Gauss y por qué hace falta pivotar.
La factorización LU y cuándo compensa.
Cuánto cuesta cada método en número de operaciones.
Qué es el número de condición y por qué algunos sistemas son “peligrosos”.
Los métodos iterativos de Jacobi y Gauss-Seidel y cuándo convergen.

Fundamentos teóricos

Eliminación de Gauss

Eliminación: con operaciones de fila se hacen ceros bajo la diagonal hasta obtener un sistema triangular superior $U\mathbf{x} = \mathbf{c}$ .
Sustitución regresiva: se despeja $x_n$ de la última ecuación, luego $x_{n-1}$ , y así hasta $x_1$ .

El multiplicador para hacer cero el elemento

a_{ik}

usando la fila

k

m_{ik} = a_{ik}/a_{kk}

. El elemento

a_{kk}

es el pivote.

Pivoteo parcial

Si un pivote es 0, el método se para; si es muy pequeño, los errores de redondeo se disparan. El pivoteo parcial intercambia filas para usar como pivote el elemento de mayor valor absoluto de la columna. Es lo que hacen todos los programas.

Factorización LU

La eliminación de Gauss equivale a escribir

A = L\,U

con

L

triangular inferior (con unos en la diagonal y los multiplicadores debajo) y

U

triangular superior. Con pivoteo,

PA = LU

. Para resolver

A\mathbf{x} = \mathbf{b}

: primero

L\mathbf{y} = \mathbf{b}

(sustitución progresiva) y después

U\mathbf{x} = \mathbf{y}

(regresiva). La ventaja: si hay que resolver con muchos

\mathbf{b}

distintos, la factorización se hace una sola vez. Si

A

es simétrica y definida positiva, se usa Cholesky:

A = LL^T

, con la mitad de operaciones.

Coste

Operación	Multiplicaciones (aprox.)
Factorización LU / eliminación	$\frac{n^3}{3}$
Sustituciones con LU ya hecha	$n^2$
Regla de Cramer con determinantes por cofactores	$\sim n!$

Para

n = 1000

, LU necesita unos

3\cdot10^8

productos (una fracción de segundo). Cramer por cofactores necesitaría más operaciones que átomos hay en el universo.

Número de condición

\kappa(A) = \|A\|\,\|A^{-1}\|

Mide cuánto se amplifica un error relativo en los datos:

\frac{\|\Delta\mathbf{x}\|}{\|\mathbf{x}\|} \le \kappa(A)\,\frac{\|\Delta\mathbf{b}\|}{\|\mathbf{b}\|}

Con

\kappa \approx 10^k

se pierden unas

k

cifras significativas. Un sistema con

\kappa

grande se llama mal condicionado: ningún algoritmo lo arregla, porque el problema mismo es sensible.

Métodos iterativos

Se descompone

A = D + L + U

(diagonal, parte estrictamente inferior y superior) y se itera. Jacobi: cada incógnita se despeja de su ecuación usando los valores de la iteración anterior:

x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j\ne i} a_{ij}\,x_j^{(k)}\right)

Gauss-Seidel: igual, pero usa los valores ya actualizados en la misma iteración. Suele converger el doble de rápido y necesita menos memoria. Convergencia: si

A

es estrictamente diagonalmente dominante por filas, es decir,

|a_{ii}| > \sum_{j \ne i}|a_{ij}|

en cada fila, los dos métodos convergen desde cualquier punto. Gauss-Seidel también converge si

A

es simétrica definida positiva.

¿Directo o iterativo?

	Directos (LU)	Iterativos
Matrices	Densas, tamaño moderado	Grandes y dispersas (casi todo ceros)
Resultado	Exacto salvo redondeo	Aproximado, se para al llegar a la tolerancia
Memoria	Puede rellenar los ceros	Solo guarda los elementos no nulos

Ejemplos resueltos

Ejemplo 1 · Eliminación de Gauss

\begin{cases} 2x + y - z = 8 \\ -3x - y + 2z = -11 \\ -2x + y + 2z = -3 \end{cases}

Con

m_{21} = -1{,}5

m_{31} = -1

: la fila 2 pasa a

0{,}5y + 0{,}5z = 1

y la fila 3, a

2y + z = 5

.Con

m_{32} = 4

: la fila 3 pasa a

-z = 1

.Sustitución regresiva:

z = -1

y = 3

x = 2

Ejemplo 2 · Factorización LU

A = \begin{pmatrix} 4 & 3 \\ 6 & 3 \end{pmatrix}

. Multiplicador

m_{21} = 6/4 = 1{,}5

L = \begin{pmatrix} 1 & 0 \\ 1{,}5 & 1 \end{pmatrix}

U = \begin{pmatrix} 4 & 3 \\ 0 & -1{,}5 \end{pmatrix}

. Comprobación:

LU = A

.Para

\mathbf{b} = (10, 12)

L\mathbf{y} = \mathbf{b}

\mathbf{y} = (10, -3)

, y

U\mathbf{x} = \mathbf{y}

x_2 = 2

x_1 = 1

Ejemplo 3 · Por qué pivotar

\begin{cases} 0{,}0001x + y = 1 \\ x + y = 2 \end{cases}

, cuya solución es

x \approx 1{,}0001

y \approx 0{,}9999

.Sin pivotar, con 3 cifras significativas:

m = 10\,000

, la segunda fila queda

-10\,000y = -10\,000

(el 1 y el 2 se pierden al redondear),

y = 1

x = \frac{1 - 1}{0{,}0001} = 0

. Totalmente falso.Intercambiando filas primero,

m = 0{,}0001

y se obtiene

y = 1

x = 1

, correcto con 3 cifras.

Ejemplo 4 · Jacobi y Gauss-Seidel

\begin{cases} 4x - y = 3 \\ -x + 4y = 3 \end{cases}

(solución

x = y = 1

). Es diagonalmente dominante.

$k$	Jacobi $(x, y)$	Gauss-Seidel $(x, y)$
0	(0, 0)	(0, 0)
1	(0,75; 0,75)	(0,75; 0,9375)
2	(0,9375; 0,9375)	(0,984; 0,996)
3	(0,984; 0,984)	(0,999; 1,000)

Jacobi divide el error por 4 en cada paso; Gauss-Seidel, por 16.

Ejemplo 5 · Un sistema mal condicionado

\begin{cases} x + y = 2 \\ x + 1{,}0001y = 2{,}0001 \end{cases}

tiene solución

(1, 1)

.Si el 2,0001 se mide como 2,0002 (un error del 0,005 %), la solución pasa a

(0, 2)

. Las dos rectas son casi paralelas:

\kappa \approx 4\cdot10^4

Errores frecuentes

Calcular $A^{-1}$ para resolver $A\mathbf{x} = \mathbf{b}$ . Cuesta el triple que LU y es menos preciso. Se factoriza y se sustituye.
No pivotar. Un pivote pequeño destruye la precisión aunque no sea exactamente 0.
Aplicar Jacobi a una matriz que no converge. Reordena las ecuaciones para que la diagonal domine antes de iterar.
Confundir determinante pequeño con mal condicionamiento. $10^{-10} I$ tiene determinante diminuto y $\kappa = 1$ : está perfectamente condicionada.

Preguntas frecuentes

¿Qué hace la barra invertida de MATLAB?

A\b analiza la matriz y elige: Cholesky si es simétrica definida positiva, LU con pivoteo parcial si es cuadrada general, QR si es rectangular (mínimos cuadrados). Para matrices dispersas grandes se usan métodos iterativos como el gradiente conjugado o GMRES.

¿Por qué los simuladores de circuitos acaban en un sistema lineal?

El análisis por nudos da

G\mathbf{v} = \mathbf{i}

. Con componentes no lineales, cada paso de Newton-Raphson linealiza el circuito y resuelve un sistema así. Por eso SPICE pasa la mayor parte del tiempo factorizando matrices dispersas.

Temas relacionados

Calculadora de matrices

Determinante, inversa y operaciones con matrices.

Sistemas de ecuaciones 2×2

Sustitución, igualación y reducción.

Mallas y nudos

Los sistemas lineales de los circuitos.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Sistemas lineales: eliminación de Gauss, LU, Jacobi y Gauss-Seidel

Lo que vas a aprender

Fundamentos teóricos

Eliminación de Gauss

Pivoteo parcial

Factorización LU

Coste

Número de condición

Métodos iterativos

¿Directo o iterativo?

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados

Calculadora de matrices

Sistemas de ecuaciones 2×2

Mallas y nudos

​Lo que vas a aprender

​Fundamentos teóricos

​Eliminación de Gauss

​Pivoteo parcial

​Factorización LU

​Coste

​Número de condición

​Métodos iterativos

​¿Directo o iterativo?

​Ejemplos resueltos

​Errores frecuentes

​Preguntas frecuentes

​Temas relacionados

Calculadora de matrices

Sistemas de ecuaciones 2×2

Mallas y nudos

Lo que vas a aprender

Fundamentos teóricos

Eliminación de Gauss

Pivoteo parcial

Factorización LU

Coste

Número de condición

Métodos iterativos

¿Directo o iterativo?

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados