Factorizacion
Páginas: 5 (1029 palabras)
Publicado: 8 de noviembre de 2010
1 M´todos Num´ricos e e Segundo Cuatrimestre 2010 Departamento de Computaci´n o FCEyN - Universidad de Buenos Aires Pr´ctica 2 a
Eliminaci´n Gaussiana. Factorizaci´n LU o o
1. Triangular la matriz de Hilbert de orden 4. Usando operaciones con fracciones en forma exacta en (a) y usando aritm´tica de punto decimal flotante con tres d´ e ıgitos con redondeo en (b): 1 1/2 1/3 1/4 1, 000 0,500 0, 333 0, 250 1/2 1/3 1/4 1/5 , (b) H = 0, 500 0, 333 0, 250 0, 200 (a) H = 1/3 1/4 1/5 1/6 0, 333 0, 250 0, 200 0, 167 1/4 1/5 1/6 1/7 0, 250 0, 200 0, 167 0, 143 (a) Analizar por qu´ se obtienen diferentes resultados. e 2. Describir un algoritmo que calcule un vector no nulo z ∈ Rn tal que U z = 0, donde U ∈ Rn×n es una matriz triangular superior con un,n = 0 y u1,1. . . un−1,n−1 ̸= 0 3. Resolver por eliminaci´n Gaussiana sin o donde 1 2 1 4 A= 1 8 1 16 intercambio de filas o columnas el sistema lineal Ax = b 3 4 2 10 9 16 , B= 44 27 64 81 256 190
Dar la factorizaci´n LU de A y calcular det(A). o 4. Calcular la factorizaci´n LU y resolver usando aritm´tica de punto decimal flotante de tres o e d´ ıgitos con redondeo ( )( ) ( )0, 003 0, 217 x1 0, 437 = 0, 277 0, 138 x2 0, 553 5. Usando n´meros de 2 d´ u ıgitos de base ( ) 7 6 la factorizaci´n LU de o 9 8 2 −1 de A = 1 6. Calcular la inversa A 4 10 con aritm´tica de punto flotante con redondeo, calcular e
1 2 2 3 de las dos maneras siguientes: 1 2
(a) Resolviendo el sistema matricial AX = I por pivoteo parcial. (b) Calculando la factorizaci´n LU de A yaplicando la identidad A−1 = U −1 L−1 . o 7. Sean A1 , ..., Ak ∈ Rn×n tales que la factorizaci´n LU de Ah es Lh U para h = 1, ..., k, donde Lh o ∑ tiene unos en la diagonal y U es la misma para toda Ah . Sea A = k Ah . Probar: h=1 (a) A tiene factorizaci´n LU . o (b) Para 1 ≤ j < i ≤ n, el multiplicador mij de la triangulaci´n gaussiana de A es el promedio o de los multiplicadores de la posici´n (i, j)en las triangulaciones de las Ah . Es decir, mij = o 1 ∑k h h o o h=1 mij , con mij el multiplicador de la posici´n (i, j) en la triangulaci´n de Ah . k 8. Probar que si A ∈ Rn×n tiene todas sus (sub)matrices principales no singulares (es decir, toda submatriz que consiste de las primeras i filas y columnas de A), entonces A tiene factorizaci´n o LU sin pivoteo. Adem´s esa factorizaci´n es unica. ao ´
2 9. Supongamos que una matriz A ∈ Rn×n tiene una factorizaci´n A = LU y que L y U son o conocidas. Dar un algoritmo que calcule el elemento (i, j) de A−1 en aproximadamente (n − j)2 + (n − i)2 flops. (Un flop es una operaci´n de punto flotante). o 10. Sea A ∈ Rn×n inversible tal que A = T S donde T ∈ Rn×n es triangular inferior y S ∈ Rn×n es triangular superior. Probar: (a) T y S soninversibles, usando propiedades de determinantes. (b) A tiene factorizaci´n LU (con unos en la diagonal de L). o 11. Hallar la factorizaci´n o 0 0 0 0 a 0 0 b c 0 0 d e f 0 q g h i j de permutaci´n). o LU 0 0 n r (L con unos en la diagonal) de la matriz 0 k l m sabiendo que es inversible. (Sugerencia: intercalar matrices o p s t
12. Sea A ∈ Rn×n y sea A(k) la matriz que seobtiene a partir de A por el m´todo de eliminaci´n e o Gaussiana cuando las primeras k columnas ya han sido trianguladas. Usando propiedades de los determinantes, probar que A es no singular si y s´lo si A(k) es no singular. o 13. Con las mismas notaciones que en el ejercicio anterior, sea A(k) = (aij )1≤i,j≤n y sea ak := max1≤i,j≤n |aij |. Si se aplica el m´todo de eliminaci´n Gaussiana conpivoteo parcial, e o probar que: (a) ak ≤ 2k a0 , k = 1, . . . , n − 1 para A arbitraria. (b) ak ≤ (k + 1)a0 , k = 1, . . . , n − 1 para matrices de Hessenberg. (Una matriz A es de Hessenberg si todos sus coeficientes debajo de la primer subdiagonal son nulos, es decir, si aij = 0 para todo (i, j) tal que i ≥ j + 2). (c) a = max1≤k≤n−1 ak ≤ 2a0 para matrices tridiagonales. 14. Una matriz A de Rn×n se...
Eliminaci´n Gaussiana. Factorizaci´n LU o o
1. Triangular la matriz de Hilbert de orden 4. Usando operaciones con fracciones en forma exacta en (a) y usando aritm´tica de punto decimal flotante con tres d´ e ıgitos con redondeo en (b): 1 1/2 1/3 1/4 1, 000 0,500 0, 333 0, 250 1/2 1/3 1/4 1/5 , (b) H = 0, 500 0, 333 0, 250 0, 200 (a) H = 1/3 1/4 1/5 1/6 0, 333 0, 250 0, 200 0, 167 1/4 1/5 1/6 1/7 0, 250 0, 200 0, 167 0, 143 (a) Analizar por qu´ se obtienen diferentes resultados. e 2. Describir un algoritmo que calcule un vector no nulo z ∈ Rn tal que U z = 0, donde U ∈ Rn×n es una matriz triangular superior con un,n = 0 y u1,1. . . un−1,n−1 ̸= 0 3. Resolver por eliminaci´n Gaussiana sin o donde 1 2 1 4 A= 1 8 1 16 intercambio de filas o columnas el sistema lineal Ax = b 3 4 2 10 9 16 , B= 44 27 64 81 256 190
Dar la factorizaci´n LU de A y calcular det(A). o 4. Calcular la factorizaci´n LU y resolver usando aritm´tica de punto decimal flotante de tres o e d´ ıgitos con redondeo ( )( ) ( )0, 003 0, 217 x1 0, 437 = 0, 277 0, 138 x2 0, 553 5. Usando n´meros de 2 d´ u ıgitos de base ( ) 7 6 la factorizaci´n LU de o 9 8 2 −1 de A = 1 6. Calcular la inversa A 4 10 con aritm´tica de punto flotante con redondeo, calcular e
1 2 2 3 de las dos maneras siguientes: 1 2
(a) Resolviendo el sistema matricial AX = I por pivoteo parcial. (b) Calculando la factorizaci´n LU de A yaplicando la identidad A−1 = U −1 L−1 . o 7. Sean A1 , ..., Ak ∈ Rn×n tales que la factorizaci´n LU de Ah es Lh U para h = 1, ..., k, donde Lh o ∑ tiene unos en la diagonal y U es la misma para toda Ah . Sea A = k Ah . Probar: h=1 (a) A tiene factorizaci´n LU . o (b) Para 1 ≤ j < i ≤ n, el multiplicador mij de la triangulaci´n gaussiana de A es el promedio o de los multiplicadores de la posici´n (i, j)en las triangulaciones de las Ah . Es decir, mij = o 1 ∑k h h o o h=1 mij , con mij el multiplicador de la posici´n (i, j) en la triangulaci´n de Ah . k 8. Probar que si A ∈ Rn×n tiene todas sus (sub)matrices principales no singulares (es decir, toda submatriz que consiste de las primeras i filas y columnas de A), entonces A tiene factorizaci´n o LU sin pivoteo. Adem´s esa factorizaci´n es unica. ao ´
2 9. Supongamos que una matriz A ∈ Rn×n tiene una factorizaci´n A = LU y que L y U son o conocidas. Dar un algoritmo que calcule el elemento (i, j) de A−1 en aproximadamente (n − j)2 + (n − i)2 flops. (Un flop es una operaci´n de punto flotante). o 10. Sea A ∈ Rn×n inversible tal que A = T S donde T ∈ Rn×n es triangular inferior y S ∈ Rn×n es triangular superior. Probar: (a) T y S soninversibles, usando propiedades de determinantes. (b) A tiene factorizaci´n LU (con unos en la diagonal de L). o 11. Hallar la factorizaci´n o 0 0 0 0 a 0 0 b c 0 0 d e f 0 q g h i j de permutaci´n). o LU 0 0 n r (L con unos en la diagonal) de la matriz 0 k l m sabiendo que es inversible. (Sugerencia: intercalar matrices o p s t
12. Sea A ∈ Rn×n y sea A(k) la matriz que seobtiene a partir de A por el m´todo de eliminaci´n e o Gaussiana cuando las primeras k columnas ya han sido trianguladas. Usando propiedades de los determinantes, probar que A es no singular si y s´lo si A(k) es no singular. o 13. Con las mismas notaciones que en el ejercicio anterior, sea A(k) = (aij )1≤i,j≤n y sea ak := max1≤i,j≤n |aij |. Si se aplica el m´todo de eliminaci´n Gaussiana conpivoteo parcial, e o probar que: (a) ak ≤ 2k a0 , k = 1, . . . , n − 1 para A arbitraria. (b) ak ≤ (k + 1)a0 , k = 1, . . . , n − 1 para matrices de Hessenberg. (Una matriz A es de Hessenberg si todos sus coeficientes debajo de la primer subdiagonal son nulos, es decir, si aij = 0 para todo (i, j) tal que i ≥ j + 2). (c) a = max1≤k≤n−1 ak ≤ 2a0 para matrices tridiagonales. 14. Una matriz A de Rn×n se...
Leer documento completo
Regístrate para leer el documento completo.