Sahlala

Necesidad del pivoteo
Para k

= 1, . . . , n − 1 = k + 1, . . . , n
(k) (k) aik /akk

´ • El algoritmo de eliminacion gaussiana (o ´ ´ el de factorizacion LU) solo puede llevarse a cabo si todos los pivotes son no nulos:

Sistemas de Ecuaciones
para i

mik =

Lineales III
(k+1) aij

para j

= k + 1, . . . , n =
(k) aij

akk = 0.

(k)

−

(k) mik akj

• Pivoteo:Estrategia de pivoteo parcial.
´ • Adaptacion a matrices con estructuras particulares: Matrices banda y tridiagonales. ´ Metodo de Cholesky.
(1) (1)

• Ejemplo. El sistema de ecuaciones siguiente tiene matriz no singular pues su determinante es 1:      x1 2 0 1 1      1 2 3 x2  = 4      0 x3 2 0 1
Sin embargo el algoritmo anterior no puede aplicarse pues a11 ´ m21 = a21 /a11y m31 = a31 /a11 no estan definidos.
(1) (1)

= 0 y, por lo tanto,

521230

-1-

´ DIM – Universidad de Concepcion 521230

-2-

´ DIM – Universidad de Concepcion

Estrategia de pivoteo parcial Necesidad del pivoteo (cont.)
´ • Para poder resolver el sistema, debe intercambiarse la primera ecuacion con cualquiera de las otras de manera de evitar el pivote cero. Por ejemplo, asi:(1) a11

··· 0 ···
.. . .. .

··· ···

··· ···



(1) a12 (2) a22


(1) a1n  (2) a2n  

. . .

 −→



0
. . .

akk

(k)

···
. . .
(k)

´ • En el paso k -esimo se revisa el vector   (k) a  kk   .   .   .  (k) ank y se busca la fila . . . . . . . . .

l en la que aparece la en´ trada mayor en modulo:

    x1 2 0 1 1      1 2 3 x2  =4      x3 0 2 0 1

    x1 4 1 2 3      0 1 1 x2  = 2      0 x3 2 0 1

0

···

0

ank

···

´ ´ • Por otra parte, puede demostrarse que la estabilidad del metodo de eliminacion ´ multiplicadores mij son numeros muy grandes en modulo. ´

            

    (k)  akn   .  .  .  (k) ann

k ≤ l ≤ n : alk
´ • Luego, si l = k , seintercambia esa fila con la k -esima.

(k)

= max

k≤i≤n

aik

(k)

.

´ gaussiana en cuanto a propagacion de errores de redondeo se deteriora si los

´ • Si la matriz es no singular, siempre habra una entrada no nula en ese vector, por lo que as´ se evitan los pivotes nulos. ı
(k) (k)

• Una forma de evitar ambos inconvenientes, pivotes nulos y multiplicadores grandes en
´ modulo,es realizar en cada paso el intercambio de ecuaciones que produzca el pivote ´ mayor posible en modulo. Esto estrategia se denomina pivoteo parcial.

´ • Ademas, despues del intercambio, akk ≥ aik , i = k, . . . , n. Por lo tanto, los ´ multiplicadores no pueden pasar de 1 en modulo:

|mik | = aik / akk ≤ 1,
521230 -3´ DIM – Universidad de Concepcion 521230 -4-

(k)

(k)

i = k, . . ., n.
´ DIM – Universidad de Concepcion

´ Matrices de permutacion
• Si hay intercambios de filas, las matrices triangulares L y U que se obtienen por el
´ ´ metodo de eliminacion gaussiana con estrategia de pivoteo parcial, ya no factorizan ´ a A, sino que factorizan a la matriz que se obtiene despues de aplicar a A todos los intercambios de filas que tuvieron lugar.

´ Factorizacion LU conestrategia de pivoteo parcial
• Teorema. Si A es una matriz no singular, entonces existen matrices no singulares L ´ triangular inferior y U triangular superior y una matriz de permutacion P , tales que LU = P A.

´ ´ • Estas matrices pueden obtenerse mediante el metodo de eliminacion gaussiana con estrategia de pivoteo parcial.

• Los intercambios de filas de una matriz se obtienenmultiplicando a izquierda por una

´ • Se llama matriz de permutacion a toda matriz que se obtenga intercambiado filas de I . ´ Por ejemplo, las siguientes son todas las matrices de permutacion 3 × 3:        0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0        0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0        0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 ´ matriz de permutacion. Por...