PDF de programación - Programación: Factorización LU

Programaci´on: Factorizaci´on LU

Objetivos. Programar el m´etodo de la factorizaci´on LU y la soluci´on de sistemas de
ecuaciones elementales usando la factorizaci´on LU.

Requisitos. Ciclos for, entradas de matrices y vectores, submatrices y subvectores, ope-
raciones elementales por renglones, soluci´on de sistemas de ecuaciones lineales con matri-
ces triangulares.

1. Problema: Factorizaci´on LU. Escriba una funci´on que construya la factorizaci´on
LU de la matriz dada A.

Entrada: matriz cuadrada A.

Condici´on que debe cumplir la entrada: se supone que la matriz A es estrictamente
invertible, esto es, a la matriz A se puede aplicar la eliminaci´on de Gauss con pivotes
diagonales. No tiene que verificar esta condici´on.

Salida: dos matrices L y U tales que LU = A, L es triangular inferior con unos en
la diagonal principal, U es triangular superior.

Puede usar el siguiente esbozo del algoritmo:

Entrada: matriz cuadrada A.
n := orden de A;
L := matriz identidad de orden n;
U := copia de A;
Para p := 1, ..., n - 1:

Para i := p + 1, ..., n:

mu := U[ , ] / U[
L[ , ] := mu;
U[i, p] := 0;
Para j :=

, ...,

, ];

:

U[ , ] -= mu * U[ , ];

Salida: L y U.

2. Usar operaciones vectoriales (opcional). En lenguajes de programaci´on orientados
a matrices se pueden usar operaciones vectoriales para eliminar el ciclo sobre j. M´as a´un,
utilizando la operaci´on de multiplicaci´on de matrices por vectores se puede eliminar el
ciclo sobre i.

Programaci´on: Factorizaci´on LU, p´agina 1 de 2

3. Guardar L y U en una matriz (opcional). Las entradas no triviales de la matriz
L se pueden guardar en la parte inferior de la matriz U.

4. Complejidad. Calcular el n´umero de operaciones aritm´eticas en el algoritmo anterior.
La respuesta es un polinomio de n.

5. Pruebas con matrices peque˜nas. Componga una matriz triangular inferior L de
orden 3 con elementos diagonales iguales a 1 y una matriz triangular superior U de orden
3 con elementos diagonales no nulos. Calcule su producto A = LU y aplique la funci´on
del ejercicio anterior a la matriz A.

6. Problema SolveWithLU. Escriba una funci´on que resuelva sistemas de ecuaciones
lineales de la forma Ax = b a trav´es de la factorizaci´on LU. Use las funciones SolveUT y
SolveLT (o SolveLT1) de las clases anteriores.

7. Pruebas con matrices peque˜nas. Pruebe la funci´on SolveWithLU con el siguiente

sistema de ecuaciones:  1

 −3

2
1

1
2 −2

2
6
1 −4

−3

 =

 1

−4
7

 .

8. Pruebas con matrices grandes. Haga pruebas de los algoritmos anteriores generan-
do la matriz A y el vector b de manera aleatoria. En estas pruebas se recomienda calcular
la norma del vector Ax − b y el tiempo de ejecuci´on de programas. ¿C´omo se cambia el
tiempo de ejecuci´on al multiplicar n por 10?

Programaci´on: Factorizaci´on LU, p´agina 2 de 2