[Link] Estimaciones de error y refinamiento iterativo — Cap.

XVIII

CAPITULO XVIII. ESTIMACIONES DE ERROR

Y REFINAMIENTO ITERATIVO

1. ESTIMACIONES DE ERROR
Parece razonable intuitivamente que si x̃ es una aproximación a la solución x de
A x = b y el vector residual r = b − A x̃ tiene la propiedad de que ||r|| es pequeño,
entonces ||x − x̃|| será también peque˜no. Aún cuando éste es frecuentemente el caso,
ciertos sistemas especiales, que aparecen bastante en la práctica, no tienen esta propiedad.
Ejemplo 1.
El sistema lineal A x = b dado por
µ ¶µ ¶ µ ¶
1 2 x1 3
= ,
1.0001 2 x2 3.0001

tiene la solución única x = (1, 1)t . La aproximación a esta solución x̃ = (3, 0)t tiene
vector residual
µ ¶ µ ¶ µ ¶ µ ¶
3 1 2 3 0
r = b − A x̃ = − = ,
3.0001 1.0001 2 0 −0.0002

ası́ que ||r||∞ = 0.0002.

Aunque la norma del vector residual es pequeña, la aproximación x̃ = (3, 0)t es
obviamente bastante pobre; en realidad, ||x − x̃||∞ = 2.
Esta dificultad se puede explicar muy simplemente si se observa que la solución del
sistema representa la intersección de las rectas

l1 : x1 + 2 x2 = 3 y l2 : 1.0001 x1 + 2 x2 = 3.0001 .

El punto (3, 0) se encuentra en l1 y las rectas son casi paralelas. Esto implica que (3, 0)
se encuentra también cerca de l2 , aún cuando difiere significativamente del punto de
intersección (1, 1). Si las rectas no hubieran sido casi paralelas, se espererı́a que un vector
residual peque˜no implicara una aproximación precisa.
En general, no podemos depender de la geometrı́a del sistema para obtener una
indicación de cúando pueden presentarse problemas. Sin embargo, podemos extraer esta
información considerando las normas de la matriz A y de su inversa.
Definición. El número de condición K(A) de la matriz no singular A relativo a la
norma || · || se define como
K(A) = ||A|| ||A−1 || .

Teorema XVIII.1
Si x̃ es una aproximación a la solución de A x = b y A es una matriz no singular,
entonces para cualquier norma natural,
||r||
||x − x̃|| ≤ ||r|| ||A−1 || = K(A) (XV III.1)
||A||

249
[Link] Estimaciones de error y refinamiento iterativo — Cap. XVIII

y
||x − x̃|| ||r|| ||r||
≤ ||A−1 || ||A|| = K(A) , (XV III.2)
||x|| ||b|| ||b||
siempre que x 6= 0 y b 6= 0, donde r es el vector residual de x̃ con respecto al sistema
A x = b.
Demostración: como r = b − A x̃ = A x − A x̃ y A no es singular:

||x − x̃|| = ||A−1 r|| ≤ ||A−1 || ||r|| .

Además, como b = A x, ||b|| ≤ ||A|| ||x||; ası́ que

||x − x̃|| ||r||

≤ ||A−1 || ||A|| .
||x|| ||b||

c.q.d.
Las desigualdades (XV III.1) y (XV III.2) implican que las cantidades ||A−1 || y
K(A) = ||A|| ||A−1 || pueden ser usadas para dar una indicación de la conexión entre
el vector residual y la precisión de la aproximación. En general, el error relativo ||x −
x̃||/||x|| es de mayor interés y por la desigualdad (XV III.2) este error está acotado por
el producto del número de condición K(A) = ||A|| ||A−1 || con el residual relativo para
esta aproximación ||r||/||b||. Para esta aproximación puede usarse cualquier norma que
sea conveniente, el único requisito es que se use consistentemente desde el principio hasta
el final.
Ya que para cualquier matriz no singular A

1 = ||I|| = ||A · A−1 || ≤ ||A|| ||A−1 || = K(A) ,

se espera que la matriz A tenga un buen comportamiento (llamada formalmente una

matriz bien condicionada) si K(A) está cerca de uno y un comportamiento defectuoso
(llamada una matriz mal condicionada) cuando K(A) sea significativamente mayor
que uno. El comportamiento en esta situación se refiere a la relativa seguridad de que
un vector residual peque˜no implique correspondientemente una solución aproximada
precisa.
Ejemplo 2.
La matriz del sistema considerado en el ejemplo 1 es
µ ¶
1 2
A= ,
1.0001 2

que tiene ||A||∞ = 3.0001. Esta norma no se considera grande, sin embargo
µ ¶
−1 −10000 10000
A = ,
5000.5 −5000

250
[Link] Estimaciones de error y refinamiento iterativo — Cap. XVIII

y ||A−1 ||∞ = 20000 y para la norma infinita K(A) = 20000×3.0001 = 60002. El tama˜no
del número de condición para este ejemplo seguramente nos detendrı́a al tomar decisiones
apresuradas acerca de la precisión, basadas en el residual de la aproximación.
Mientras que, en teorı́a, el número de condición de una matriz depende totalmente
de las normas de la matriz y de su inversa, en la práctica, el cálculo de la inversa está
sujeto a errores de redondeo y es dependiente de la exactitud con la que se estén haciendo
los cálculos. Si hacemos la suposición de que la solución aproximada al sistema lineal
A x = b se determina usando aritmética de t dı́gitos y eliminación Gaussiana, se puede
demostrar que el vector residual r para la aproximación x̃ tiene la propiedad

||r|| ≈ 10−t ||A|| ||x̃|| . (XV III.3)

De esta ecuación aproximada, se puede obtener una estimación del número de condición
efectivo para la aritmética de t dı́gitos, sin la necesidad de invertir la matriz A. [La
aproximación en la ecuación (XV III.3) supone que todas las operaciones aritméticas en
la técnica de eliminación Gaussiana se efectúan usando aritmética de t dı́gitos, pero que
las operaciones que se necesitan para determinar el residual se hacen en doble precisión,
es decir, 2t dı́gitos, para eliminar la pérdida de precisión involucrada en la sustracción de
números casi iguales que ocurre en los cálculos del residual].
La aproximación del número de condición K(A) a t dı́gitos viene de considerar el
sistema lineal A y = r. La solución de este sistema puede aproximarse fácilmente ya que
los multiplicadores para el método de eliminación Gaussiana han sido ya calculados y
supuestamente retenidos. De hecho ỹ, la solución aproximada de A y = r, satisface que

ỹ ≈ A−1 r = A−1 (b − A x̃) = A−1 b − A−1 A x̃ = x − x̃ ; (XV III.4)

ası́ que ỹ es una estimación del error cometido al aproximar la solución del sistema original.
Consecuentemente la ecuación (XV III.3) puede usarse para deducir que

||ỹ|| ≈ ||x − x̃|| = ||A−1 r|| ≤

≤ ||A−1 || ||r|| ≈ ||A−1 || (10−t ||A|| ||x̃||) = 10−t ||x̃|| K(A) .

Esto proporciona una aproximación para el número de condición involucrado en la solución

del sistema A x = b usando eliminación Gaussiana y el tipo de aritmética de t dı́gitos
descrito anteriormente:
||ỹ||
K(A) ≈ 10t . (XV III.5)
||x̃||

Ejemplo 3.
El sistema lineal A x = b dado por
    
3.3330 15920 −10.333 x1 15913
 2.2220 16.71 9.612   x2  =  28.544  ,
1.5611 5.1791 1.6852 x3 8.4254

251
[Link] Estimaciones de error y refinamiento iterativo — Cap. XVIII

tiene la solución exacta x = (1, 1, 1)t .

Usando eliminación Gaussiana y aritmética de redondeo de 5 dı́gitos llegamos suce-
sivamente a las matrices ampliadas
 
3.3330 15920 −10.333 | 15913
 0 −10596 16.501 | −10580 
0 −7451.4 6.525 | −7444.9

y  
3.3330 15920 −10.333 | 15913
 0 −10596 16.501 | −10580  .
0 0 −5.079 | −4.7
La solución aproximada a este sistema es

x̃ = (1.2001, 0.99991, 0.92538)t .

El vector residual correspondiente a x̃ calculado con doble precisión (y luego redondeado

a cinco dı́gitos) es

r = b − A x̃ =
     
15913 3.3330 15920 −10.333 1.2001
=  28.544  −  2.2220 16.71 9.612   0.99991  =
8.4254 1.5611 5.1791 1.6852 0.92538
 
−0.0051818
=  0.27413  ;
−0.18616

ası́ que
||r||∞ = 0.27413 .

La estimación del número de condición dada en la discusión anterior se obtiene

resolviendo primero el sistema A y = r:
     
3.3330 15920 −10.333 y1 −0.0051818
 2.2220 16.71 9.612   y2  =  0.27413  ,
1.5611 5.1791 1.6852 y3 −0.18616

lo cual implica que ỹ = (−0.20008, 8.9989 × 10−5 , 0.074607)t . Usando la estimación dada
por la ecuación (XV III.5):

||ỹ||∞ 105 (0.20008)

K(A) ≈ 105 = = 16672 .
||x̃||∞ 1.2001

Las cotas de error dadas en el Teorema XVIII.1 para estos valores son

||r||∞ (16672)(0.27413)
||x − x̃||∞ ≤ K(A) = = 0.28683
||A||∞ 15934

252
[Link] Estimaciones de error y refinamiento iterativo — Cap. XVIII

y
||x − x̃||∞ ||r||∞ (16672)(0.27413)
≤ K(A) = = 0.28721 .
||x||∞ ||b||∞ 15913

Para determinar el número de condición exacto de A, necesitamos construir primero

−1
A . Usando aritmética de redondeo de 5 dı́gitos para los cálculos se obtiene la aproxi-
mación:
 
−1.1701 × 10−4 −1.4983 × 10−1 8.5416 × 10−1
A−1 =  6.2782 × 10−5 1.2124 × 10−4 −3.0662 × 10−4  .
−5
−8.6631 × 10 1.3846 × 10−1 −1.9689 × 10−1

El Teorema XIII.13 puede usarse para demostrar que ||A−1 ||∞ = 1.0041 y ||A||∞ = 15934.
Como consecuencia la matriz A mal condicionada tiene

K(A) = (1.0041) (15934) = 15999 .

La aproximación que habı́amos obtenido antes está bastante cerca de este K(A) y ha
requerido un esfuerzo computacional considerablemente menor.
Como la solución real x = (1, 1, 1)t de este sistema es conocida, podemos calcular
ambos
||x − x̃||∞ = 0.2001

y
||x − x̃||∞
= 0.2001 .
||x||∞
Las cotas de error dadas en el Teorema XVIII.1 para estos valores son

||r||∞ (15999)(0.27413)
||x − x̃||∞ ≤ K(A) = = 0.27525
||A||∞ 15934
y
||x − x̃||∞ ||r||∞ (15999)(0.27413)
≤ K(A) = = 0.27561 .
||x||∞ ||b||∞ 15913

2. REFINAMIENTO ITERATIVO
En la ecuación (XV III.4) usamos la estimación ỹ ≈ x − x̃, en la que ỹ es la solución
aproximada al sistema A y = r. Serı́a razonable sospechar, a partir de este resultado,
que x̃ + ỹ fuese una mejor aproximación a la solución del sistema lineal A x = b que la
aproximación inicial x̃.
El método que usa esta suposición se llama refinamiento iterativo, o mejora iter-
ativa y consiste en llevar a cabo iteraciones sobre el sistema cuyo lado derecho es el vector
residual para las aproximaciones sucesivas, hasta que se obtiene una precisión satisfacto-
ria. El procedimiento se usa generalmente sólo en los sistemas en que se sospecha que la
matriz involucrada es mal condicionada, debido a que esta técnica no mejora mucho la
aproximación para un sistema bien condicionado.

253
[Link] Estimaciones de error y refinamiento iterativo — Cap. XVIII

Algoritmo de refinamiento iterativo.

==================================================
Para aproximar la solución al sistema lineal A x = b cuando se sospecha que A sea mal
condicionada.
Entrada: número de incógnitas y de ecuaciones n; las componentes de la matriz A = (aij )
donde 1 ≤ i, j ≤ n; las componentes bi , con 1 ≤ i ≤ n, del término no homogéneo b; la
tolerancia TOL; el número máximo de iteraciones N0 .
Salida: solución aproximada xx = (xx1 , xx2 , . . . , xxn ) ó mensaje de que el número de
iteraciones fue excedido.
Paso 0: Resolver el sistema A x = b para x1 , x2 , . . . , xn por eliminación Gaus-
siana guardando los multiplicadores mji , j = i + 1, i + 2, . . . , n, i =
1, 2, . . . , n − 1 y haciendo notar los intercambios de filas.
Paso 1: Tomar k = 1.
Paso 2: Mientras que k ≤ N0 seguir los pasos 3–8.
Paso 3: Para i = 1, 2, . . . , n (calcular r, realizando los cálculos con doble
precisión aritmética), tomar
P
n
ri = bi − (aij xj ).
j=1
Paso 4: Resolver el sistema lineal A y = r usando eliminación Gaussiana en
el mismo orden que en el paso 0.
Paso 5: Para i = 1, 2, . . . , n tomar
xxi = xi + yi .
Paso 6: Si ||x − xx|| < T OL entonces SALIDA (xx1 , xx2 , . . . , xxn );
(procedimiento completado satisfactoriamente) PARAR.
Paso 7: Tomar k = k + 1.
Paso 8: Para i = 1, 2, . . . , n tomar xi = xxi .
Paso 9: SALIDA (número máximo de iteraciones excedido);
(procedimiento completado sin éxito) PARAR.
==================================================
Si se está usando aritmética de t dı́gitos, un procedimiento recomendable para parar
(k)
en el paso 6 consiste en iterar hasta que |yi | ≤ 10−t para cada i = 1, 2, . . . , n.
Debe enfatizarse que la técnica de refinamiento iterativo no da resultados satisfacto-
rios para todos los sistemas que contienen matrices mal condicionadas. En particular, si
K(A) ≥ 10t , es probable que el procedimiento falle y que la única alternativa sea el uso
de mayor precisión en los cálculos.
Ejemplo 4.
En el ejemplo 3 encontramos que la aproximación al problema que habı́amos estado
considerando, usando aritmética de cinco dı́gitos y la eliminación Gaussiana, era

x̃(1) = (1.2001, 0.99991, 0.92538)t

y que la solución a A y(1) = r(1) era

ỹ(1) = (−0.20008, 8.9989 × 10−5 , 0.074607)t .

254
[Link] Estimaciones de error y refinamiento iterativo — Cap. XVIII

Usando el paso 5 del algoritmo, tenemos que

x̃(2) = x̃(1) + ỹ(1) = (1.0000, 1.0000, 0.99999)t

y el error real en esta aproximación es

||x − x̃(2) ||∞ = 1.0 × 10−5 .

Usando la técnica de paro sugerida para el algoritmo, calculamos r(2) = b − A x̃(2) , y

resolvemos el sistema A y(2) = r(2) , obteniéndose

ỹ(2) = (−2.7003 × 10−8 , 1.2973 × 10−8 , 9.9817 × 10−6 )t .

Puesto que ||ỹ(2) ||∞ ≤ 10−5 , concluı́mos que

x̃(3) = x̃(2) + ỹ(2) = (1.0000, 1.0000, 1.0000)t

es suficientemente preciso. De hecho es claramente correcto.

255
[Link] Estimaciones de error y refinamiento iterativo — Cap. XVIII

EJERCICIOS.

1. Resolver los siguientes sistemas lineales usando eliminación Gaussiana y re-

finamiento iterativo (con aritmética a dos dı́gitos para el problema a) y a
tres dı́gitos para b) y c)). Calcular K(A).
a) 3.9 x1 + 1.6 x2 = 5.5 ,
6.8 x1 + 2.9 x2 = 9.7 .

b) 4.56 x1 + 2.18 x2 = 6.74 ,

2.79 x1 + 1.38 x2 = 4.13 .

1 1 11
c) x1 + 2x2 + 3 x3 = 6 ,
10 5 65
5 x1 + 3 x2 + 2 x3 = 6 ,
100 235
3 x1 + 25 x2 + 20 x3 = 3 .

2. Calcular los números de condición de las siguientes matrices, relativos a

|| · ||∞ . µ ¶
1 2
a) ,
1.0001 2
µ ¶
3.9 1.6
b) ,
6.8 2.9
µ ¶
4.56 2.18
c) ,
2.79 1.38
µ ¶
1.003 58.09
d) .
5.550 321.8

3. El sistema lineal
µ ¶ µ ¶ µ ¶
1. 2. x1 3.
=
1.0001 2. x2 3.0001
tiene solución (1, 1)t . Cambiar la matriz A por
µ ¶
1. 2.
0.9999 2.
y considerar el sistema lineal
µ ¶ µ ¶ µ ¶
1. 2. x1 3.
= .
0.9999 2. x2 3.0001
Calcular la nueva solución x̃ usando aritmética de cinco dı́gitos.
4. El sistema lineal
µ ¶ µ ¶ µ ¶
1. 2. x1 3.
=
1.00001 2. x2 3.00001
tiene solución (1, 1)t . Encontrar la solución del sistema lineal perturbado
µ ¶ µ ¶ µ ¶
1. 2. x1 3.00001
= ,
1.000011 2. x2 3.00003
usando aritmética de siete dı́gitos.

256