• Author / Uploaded
• ALuis Angel

Citation preview

Métodos directos para la resolución de sistemas lineales 1

Factorización LU

De…nición 1.1 Se dice que una matriz A admite una factorización LU si dicha matriz puede escribirse como el producto de una matriz triangular inferior, L, cuyos elementos en la diagonal sean iguales a la unidad y una matriz triangular superior U: Es decir A = LU De…nición 1.2 Se dice que una matriz A admite una factorización LU indirecta si existe una matriz de permutación P tal que la matriz P A admita una factorización LU . Es decir, P A = LU Teorema 1.1 Toda matriz A no singular admite una factorización de la forma P A = LU: Observación 1.1 Se denomina matriz de permutación a toda matriz cuadrada tal que cada …la y cada columna de la matriz tiene un y sólo un elemento distinto de cero y éste toma además el valor 1. Observación 1.2 Toda matriz de permutación es no singular y además se veri…ca: P 1 = P t Observación 1.3 Toda matriz A no singular admite una factorización LU indirecta (pero no necesariamente una factorización LU).

1.1

Algoritmo para la factorización

LU es básicamente una forma modi…cada de la eliminación gaussiana. Transformamos la matriz A en una triangular superior U anulando los elementos debajo de la diagonal. Es decir E1 E2 ::: En A = U donde E1 ; E2 ; :::; En son matrices elementales, que representan los distintos pasos de la eliminación. Luego recordando que la inversa de una matriz elemental, es otra matriz elemental: A = (E1 E2 ::: En ) 1

1

U =L U

con L=En 1 En 11 ::: E1 1 matriz triangular inferior. Para 2matrices 3 3, 3 esto 2 es: 3 2 3 a11 a12 a13 1 0 0 u11 u12 u13 A = 4 a21 a22 a23 5 = 4 l21 1 0 5 4 0 u21 u23 5 a31 a32 a33 l31 l32 1 0 0 u33

1.2

Cálculo de factorizacion LU con MATLAB

>> [L, U]=lu(A) Si la matriz A admite una factorización LU , la función lu devuelve en L la matriz triangular inferior y en U la matriz triangular superior. >> [L, U, P]=lu(A) Si la matriz A admite una factorización LU indirecta, la función lu devuelve en L la matriz triangular inferior, en U la matriz triangular superior y en P la matriz de permutación.

2

Factorización de Cholesky

De…nición 2.1 Una matriz A nxn simétrica se de…ne de…nida positiva si se veri…ca que xt Ax > 0 8x 2 0 8x 6= 0). Teorema 2.1 Una matriz A nxn simétrica, es de…nida positiva si y solo si todos sus autovalores son reales y positivos. ( i 2 < y i > 0; 8i = 1; ::; n:).

2

2.1

Cálculo de factorización de Cholesky con Matlab

>> [U]=chol(A) Si la matriz A admite una factorización de Cholesky, la función chol devuelve en U la matriz triangular superior Rt :

3 3.1

Aplicaciones Resolviendo sistemas lineales

Dada la ecuación matricial Ax = b Los pasos para resolver el sistema lineal usando la factorización Ax = L(U x) = Ly = b son los siguientes: Primero, resolvemos Ly = b Segundo, resolvemos U x = y y obtenemos x. Es decir que resolvemos dos sistemas triangulares. Este método es computacionalmente e…ciente. Observar que la factorización es independiente del vector b: En el caso A admita una factorización de la forma P A = LU; entonces para resolver el sistema lineal Ax = b;calculamos primeramente: P Ax = P b:

3.2

Cálculo de la inversa de una matriz

La factorización L.U puede ser usada para calcular la matriz inversa de A. Algunos algoritmos que invierten matrices usan este método. Es decir, A 1 = (LU ) 1 = U 1 L 1 :También si A es una matriz de nxn y sabiendo que A:A 1 = I si se resuelven n sistemas Avi = ei con ei = (0; :::; 1; 0; :::0), un 1 en el lugar "i-ésimo", usando la factorización LU se obtiene la matriz inversa cuyas columnas son los vectores vi :

3.3

Cálculo del determinante de una matriz

Las matrices L y U pueden ser usadas para calcular el determinante de la matriz A: det(A) = det(L)det(U ): 3

Recordando que el determinante de una matriz triangular es simplemente el producto de los elementos de la diagonal, y que en este caso en particular, L es una matriz triangular donde los elementos de la diagonal son todos unos, entonces: det(L) = 1;y por lo tanto: det(A) = det(U ) = u11 u22 :::: unn : Si la factorización de A es P 1 LU con P matriz de permutación, por ser el determinante de una matriz de permutación 1 o 1 según sea el número de permutaciones de …las en la descomposición, entonces el det(A) = ( 1)u11 u22 :::: unn :

4

Ejemplos 2

3 2 3 2 1 3 1 1 3 5 y el vector b = 4 0 5 1. Dada la matriz A = 4 4 2 5 5 2 a) Factorizar la matriz A como LU Realizamos operaciones elementales para llevar a la matriz A a una matriz triangular 2 superior U. 3 2 3 2 1 3 2 1 3 f ila2 (2) f ila1 4 1 3 5! 0 3 3 5 A=4 4 f ila3 ( 1) f ila1 2 5 5 0 6 8 2 3 2 1 3 4 3 3 5=U ! f ila3 ( 2) f ila2 0 0 0 2 2 3 2 3 2 1 3 1 0 0 3 3 5yL=4 2 1 0 5 Entonces U = 4 0 0 0 2 1 2 1 b) Usando la factorización hallar el determinante de A det(A) = det(LU ) = det(L) det(U ) = (1) (2 ( 3) 2) = 12 c) Resolver el sistema Ax = b usando la factorización LU . Primero resolvemos el sistema triangular Ly = b: Es decir: 2 3 2 3 2 3 1 0 0 y1 1 4 2 1 0 5 : 4 y2 5 = 4 0 5 1 2 1 y3 2

4

y obtenemos como solución 2

3 1 2 1 2. Factorizar la matriz A = 4 3 6 2 5 1 1 4 Hacemos operaciones elementales para reducir A a una matriz triangular superior: 2 3 2 3 1 2 1 1 2 1 f ila2 (3) f ila1 4 0 0 5 5 A=4 3 6 2 5! f ila3 ( 1) f ila1 1 1 4 0 3 3

la cual no es una matriz triangular superiror, entonces, podemos hacer intercambio de …las para que si lo sea. Y obtenemos: 2 3 1 2 1 3 5 U =4 0 3 0 0 5 De esta manera, P A = …las 2 y 3 : 2 1 4 P = 0 0

LU donde P es la matriz de permutación de las 3 0 0 0 1 5 1 0

2

L=4

3 1 0 0 1 1 0 5 3 0 1

3. Factorizar A usando la factorización de Cholesky, analizando previamente si2A es de…nida positiva. 3 81 9 0 A = 4 9 2 2 5, autovalores{0.3219, 2.4579, 20.2202} 0 2 20 Son todos reales y positivos, entonces A es de…nida positiva y se puede factorizar Cholesky. Realizamos operaciones elementales para reducir a la matriz a una matriz triangular 2 superior: 3 2 3 1 1 0 1 1 0 A = 4 1 2 2 5 ! f ila2 ( 1)f ila1 4 0 1 2 5 0 2 20 2 0 2 20 3 1 1 0 ! f ila3 (2)f ila2 4 0 1 2 5 0 0 16 entonces resulta 5

2

1 4 1 A= 0 2 1 0 4 1 1 = 2 0 2 1 0 4 1 1 = 2 0 2 1 0 4 1 1 = 0 2

5

3 2 1 0 1 5 4 2 2 1 = LU = 2 3 202 0 3 2 0 1 0 0 1 5 4 5 4 0 0 1 0 0 1 3 2 0 0 163 2 0 0 1 0 0 1 5 4 5 4 0 0 1 0 0 13 2 0 0 4 3 0 0 1 1 0 5 4 0 0 1 2 5 4 0 0 4

32 0 0 1 5 4 1 0 0 2 1 3 0 1 0 1 2 5= 0 31 2 0 0 1 5 4 1 0 0 0 4 0

3 1 0 1 2 5 = LDLt = 0 16 3 1 0 1 2 5= 0 1

Ejercicios

Dados las siguientes sistemas de ecuaciones Ax = b, factorizar la matriz y resolver usando la factorización. 3 9

1. A = 2

1 2. A = 4 2 1 2 0 4 1 3. A = 1 4. A =

1 5

;

3 1 1 5; 2 3 1 4 2 1 5; 3 3

1 3 1

4 2 2 10

1 3

b=

;

2

3 0 b=4 1 5 1 2 3 0 b=4 1 5 1 b=

1 4

(factorizar Cholesky)

6