GuíaSistemas linealesmedio

Sistemas lineales: error, residuo y condición

Métodos directos frente a iterativos para Ax=b, la diferencia entre error y residuo, el criterio de parada por residuo y por qué el número de condición decide si es fiable.

Directos frente a iterativos

Resolver Ax=bAx=b se puede hacer con métodos directos (Cramer, Gauss-Jordan), que llegan a la solución en un número finito de operaciones, o con métodos iterativos, que generan aproximaciones cada vez mejores. Para matrices grandes, dispersas o mal condicionadas, los iterativos suelen ser más eficientes y permiten parar al alcanzar la precisión deseada.

Error, residuo y parada

El error compara la aproximación con la solución exacta x*; el residuo mide cuánto falla la ecuación. El error no se conoce, así que se para por el residuo.

e(k)=x∗−x(k),r(k)=b−Ax(k),r(k)=Ae(k)e^{(k)}=x^*-x^{(k)},\qquad r^{(k)}=b-Ax^{(k)},\qquad r^{(k)}=Ae^{(k)}
EjemploMatriz mal condicionada

El sistema con A=(2626.0001)A=\bigl(\begin{smallmatrix}2 & 6\\ 2 & 6.0001\end{smallmatrix}\bigr) y b=(8, 8.0001)Tb=(8,\,8.0001)^T tiene solución x=(1,1)Tx=(1,1)^T. Una perturbación mínima cambia drásticamente la solución.

  1. Restando 0.0001 en la segunda fila, la solución pasa a:

    x~=[4, 0]t(muy distinta de [1,1]t)\tilde x=[4,\ 0]^{t}\quad\text{(muy distinta de } [1,1]^t)

Se explica por el enorme número de condición:

K(A)≈4.0001⋅105\mathcal{K}(A)\approx 4.0001\cdot 10^{5}

El esquema iterativo estacionario

Los métodos iterativos parten de una partición A=M−NA=M-N con MM fácil de invertir (diagonal, triangular…). Se transforma Ax=bAx=b en un punto fijo equivalente:

Mx(k+1)=Nx(k)+b ⟺ x(k+1)=Hx(k)+q,H=M−1N, q=M−1bMx^{(k+1)}=Nx^{(k)}+b\ \Longleftrightarrow\ x^{(k+1)}=Hx^{(k)}+q,\qquad H=M^{-1}N,\ q=M^{-1}b

H es la matriz de iteración. El método es estacionario si H es constante en todo el proceso. Distintas elecciones de M dan Jacobi, Gauss-Seidel y SOR.