Refinamiento Iterativo

Sea $\tilde{x}$ una aproximación de la solución $x$ del sistema $Ax=b$, con la propiedad de que la norma del vector residual $r=b-A\tilde{x}$ es pequeña, entonces es intuitivo pensar que la norma de $\Vert x-\tilde{x}\Vert$ también lo será. Esto no es necesariamente así.

Teorema: Supongamos que $\tilde{x}$ es una aproximación a la solución del sistema $Ax=b$, siendo $A$ una no singular y que $r$ es el vector residual

1. $\Vert x-\tilde{x}\Vert \le \Vert r\Vert \Vert A^{-1}\Vert$
2. $\frac{\Vert x-\tilde{x}\Vert }{\Vert x\Vert }\le \Vert A\Vert \Vert A^{-1}\Vert \frac{\Vert r\Vert }{\Vert b\Vert }$

Número de Condición $K$

Llamamos $K(A)$ al número de condición de la matriz $A$, se puede calcular como $K(A)=\Vert A\Vert \Vert A^{-1}\Vert$. El número de condición de una matriz es siempre mayor a $1$.

Se dice que una matriz está mal condicionada, si su número de condición es significativamente mayor que $1$.

Para aproximar el número de condición de una matriz, debo encontrar a la solución del sistema en el vector residual

$$Ay=(b-A\tilde{x})⟹x=\tilde{x}+\tilde{y}$$

Puedo utilizar la fórmula de error residual para aritmética de $t$ cifras significativas.

$$\Vert r\Vert \approx 10^{-t}\Vert A\Vert \Vert \tilde{x}\Vert$$

Luego, podemos aproximar el número de condición como:

$$K(A)\approx 10^t\frac{\Vert \tilde{y}\Vert }{\Vert \tilde{x}\Vert }$$

Refinamiento Iterativo

El refinamiento iterativo consiste en, a cada iteración de un método iterativo, sumarle la solución del sistema para el vector residual.

1. Encontramos la aproximación ${\tilde{x}}^{(1)}$, para $Ax=b$
2. Encontramos la aproximación ${\tilde{y}}^{(1)}$, para $Ay=r$, siendo $r=b-A{\tilde{x}}^{(1)}$
3. Luego encontramos la siguiente aproximación ${\tilde{x}}^{(2)}={\tilde{x}}^{(1)}+{\tilde{y}}^{(1)}$
4. Repetir este algoritmo hasta llegar a la cota de error deseada