Estrategias de pivoteo

Eliminacion de Gauss con pivotes diagonales puede funcionar mal

1. Ejemplo. A =

1 2 1 42 4 3 31 3 4 1

.2. Ejemplo. Resolver el sistema usando calculos con 3 dgitos con redondeo al mascercano: {

3.00 103 x1 + 6.11 x2 = 6.14;7.00 x1 3.00 101 x2 = 4.00 101.

La solucion exacta es x1 = 1.00 101, x2 = 1.00. Calculos con tres dgitos:

= 7.00

3.00 103 = 2.(3) 103 2.33 103;

Apliquemos la operacion R2+ =2.33 103 R1.2.33 103 6.11 = 1.42363 104 1.42 104;

1.42 104 3.00 101 = 1.423 104 1.42 104;2.33 103 6.14 = 1.43062 104 1.43 104;

1.43 104 + 4.00 101 = 1.426 104 1.43 104.Se obtiene el siguiente sistema:{

3.00 103 x1 + 6.11 x2 = 6.14; 1.42 104 x2 = 1.43 104.

Calculamos x2 y x1 (los valores aproximados de x2 y x1):

x2 =1.43 1041.42 104 1.00704 1.01;

6.11 1.01 = 6.1711 6.17;6.14 6.17 = 3.00 102;

x1 =3.00 1023.00 103 = 1.00 10

1.

En vez de la solucion exacta

x1 = 1.00 101, x2 = 1obtuvimos la solucion

x1 = 1.00 101, x2 = 1.01.

Estrategias de pivoteo, pagina 1 de 3

Eliminacion gaussiana con pivoteo parcial(o pivoteo de columna maxima)

3. El mayor elemento de la columna. Consideremos la siguiente modificacion delmetodo de Gauss: en cada paso k, (k {1, . . . ,m 1}) elijamos en calidad de pivote elelemento con ndices (ik, k) tal que

|aik,k| = maxkim

|ai,k|,

es decir el mayor elemento (en el sentido absoluto) de la k-esima columna empezando con(k, k) hasta (m,k).

4. Algoritmo Reduce2.

Entrada: matriz A de tama~no m por n con m L[[imax]], imax = i], {i, Length[L]}];

imax

6. Ejemplo. Resolver el sistema usando calculos con 3 dgitos con redondeo al mascercano. Aplicar la eliminacion gaussiana con el pivoteo parcial.{

3.00 103 x1 + 6.11 x2 = 6.14;7.00 x1 3.00 101 x2 = 4.00 101.

Estrategias de pivoteo, pagina 2 de 3

7. Ejemplo cuando la eliminacion gaussiana con pivoteo parcial funciona mal.{3.00 105 x1 + 6.11 108 x2 = 6.14 108;

7.00 x1 3.00 101 x2 = 4.00 101.

Pivoteo parcial escalado(Pivoteo de escalado de columna)

8. La eleccion del elemento pivoteo en el paso numero k:para todo i {k, . . . ,m} calculamos el valor maximo absoluto:

si = maxkjm

|ai,j|.

Si si = 0 para algun i y el sistema es cuadrada (n = m+ 1), entonces el sistema no tieneuna solucion unica. Supongamos que si > 0 para todo i {k, . . . ,m}. Elijamos el menorentero p con

|ap,k|

sp= max

kim|ai,k|

si.

En otras palabras, sea p el menor de los ndices i en los cuales la expresion|ai,k|

sialcanza

su maximo. Si p 6= k, entonces se intercambian los renglones con ndices p y k.

Pivoteo completo

9. En el k-esimo paso se buscan los ndices p, q {k, . . . ,m} tales que|ap,q| = max

kimkjm

|ai,j|.

En otras palabras, se busca el maximo entre los elementos |ai,j| con k i m y k j m.

Si (p, q) 6= (k, k), entonces se intercambian los renglones y las columnas de tal maneraque el elemento ap,q se pone en la posicion (k, k).

En vez de intercambiar las columnas de manera explcita se usa un vector auxiliar queguarda la permutacion de las columnas.

Ejemplos

10. Obtenga los intercambios de filas que se requieren en el primer paso del metodo deGauss con el pivoteo parcial y con el pivoteo parcial escalado:

x1 5x2 + x3 = 7;10x1 + 20x3 = 6;5x1 x3 = 4.

x1 + x2 x3 = 1;x1 + x2 + 4x3 = 2;2x1 x2 + 2x3 = 3.

Estrategias de pivoteo, pagina 3 de 3