Factorización triangular.

Supongamos que la matriz de coeficientes A de un sistema lineal Ax=b admite una factorización triangular como la siguiente.

| a₁₁ a₁₂ a₁₃ | | 1 | | u₁₁ u₁₂ u₁₃ |

A= | a₂₁ a₂₂ a₂₃ | = | l₂₁ 1 0 |= | 0 u₂₂ u₂₃ |

| a₃₁ a₃₂ a₃₃ | | l₃₁ l₃₂ 1 | | 0 0 u₃₃ |

Entonces la solución la podemos plantear como

LUx = b

El cual se puede solucionar resolviendo primero Ly=b y luego el sistema Ux=y.

Ejemplo.

Resolver el sistema de ecuaciones

x₁ + 2x₂ + 4x₃ + x₄ = 21

2x₁ + 8x₂ + 6x₃ + 4x₄ = 52

3x₁ + 10x₂ + 8x₃ + 8x₄ = 79

4x₁ + 12x₂ + 10x₃ + 6x₄ = 82

| 1 2 4 1 | | 1 0 0 0 | | 1 2 4 1 |

A = | 2 8 6 4 | = | 2 1 0 0 | * | 0 4 –2 2 |

| 3 10 8 8 | | 3 1 1 0 | | 0 0 –2 3 |

| 4 12 10 6 | | 4 1 2 1 | | 0 0 0 –6 |

Primero resolvemos el sistema de ecuaciones

y₁ = 21

2y₁ + y₂ = 52

3y₁ + y₂ + y₃ + = 79

4y₁ + y₂ + 2y₃ + y₄ = 82

El cual corresponde a un sistema triangular inferior

y₁ = 21

y₂ = 10

y₃ = 6

y₄ = -24

En general

x₁ = b₁/ a_1,1

x_k = (b_k – S_j=1,k-1 a_kj x_j)/a_kk

y posteriormente solucionamos

x₁ + 2x₂ + 4x₃ + x₄ = 21

4x₂ - 2x₃ + 2x₄ = 10

- 2x₃ + 3x₄ = 6

- 6x₄ =-24

utilizando sustitución hacia atrás tenemos

X = [1,2,3,4]^T

Implementación.

Como vimos una matriz factorizada, fácilmente puede ser resuelta utilizando los métodos de sustitución hacia adelante y sustitución hacia atrás. ¿Pero como hacemos la factorización? Comenzaremos por escribir el sistema

| a₁₁ a₁₂ a₁₃ | | 1 | | u₁₁ u₁₂ u₁₃ |

| a₂₁ a₂₂ a₂₃ | = | l₂₁ 1 0 |= | 0 u₂₂ u₂₃ |

| a₃₁ a₃₂ a₃₃ | | l₃₁ l₃₂ 1 | | 0 0 u₃₃ |

A = LU

Si multiplicamos el primer renglón de L por la primera columna de U tenemos

u₁₁ = a₁₁

u₁₂ = a₁₂

u₁₃ = a₁₃

Ahora hacemos lo mismo para el segundo renglón de L con U

l₂₁ u₁₁ = a₂₁ => l₂₁ = a₂₁/u₁₁ = a₂₁/a₁₁

l₂₁ u₁₂ + u₂₂ = a₂₂ => u₂₂ = a₂₂ - l₂₁ u₁₂ = a₂₂ - a₂₁ a₁₂/a₁₁

l₂₁ u₁₃ + u₂₃ = a₂₃ => u₂₃ = a₂₃ - l₂₁ u₁₃ = a₂₃ - a₂₁ a₁₃/a₁₁

Multiplicando el tercer renglón de L por U tenemos:

l₃₁ u₁₁ = a₃₁ => l₃₁ = a₃₁/u₁₁ = a₃₁/a₁₁

l₃₁ u₁₂ + l₃₂ u₂₂ = a₃₂ => l₃₂ = (a₂₂ – l₃₁ u₁₂)/a₂₂

l₃₁ u₁₃ + l₃₂ u₂₃ + u₃₃ = a₃₃ => u₃₃ = a₃₃ – l₃₁ u₁₃ - l₃₂ u₂₃

Podemos notar lo siguiente, en este caso la triangulación la podemos hacer en dos pasos.

Paso I. Dado la matriz A hacemos

a11	a12	a13
a21/a11	a22 - a21 a12/a11	a23 - a21 a13/a11
a31/a11	a32 – a31 a12/a11	a33 – a31 a13/a11

a11	a12	a13
a’21	a’22	a’23
a’31	a’32	a’33

Paso II. Dado A modificada

a11	a12	a13
a’21	a’22	a’23
a’31	a’32/ a’22	a’33 – a’32a’23/a22

a11	a12	a13
a’21	a’’22	a’’23
a’31	a’’32	a’’33

Note que para calcular la matriz triangular superior se podría aplicar, el método de eliminación gaussiana y la matriz diagonal inferior es simplemente los cocientes

a_jk = a_jk/a_kk

Ejemplo:

Hacer la factorización LU de la siguiente matriz.

1	2	4	1
2	8	6	4
3	10	8	8
4	12	10	6

Paso 1.

1	2	4	1
2	4	-2	2
3	4	-4	5
4	4	-6	2

Paso 2.

1	2	4	1
2	4	-2	2
3	1	-2	3
4	1	-4	0

Paso 3.

1	2	4	1
2	4	-2	2
3	1	-2	3
4	1	-2	6

Regresar.