sistemas lineales

Clase

1. Resolución de sistemas de ecuaciones lineales:

preliminares
2. Método directo y exacto: Gauss
3. Método directo y exacto (II): descomposición LU
4. Métodos indirectos: Jacobi, Gauss-Seidel

2

Sistemas lineales
PRELIMINARES

Matriz
de coeficientes

Vector de incógnitas

Sistema de ecuaciones lineales

Recordatorio de álgebra lineal…

La primera opción queuno se plantea es
 No es eficiente (demasiadas operaciones)
 Si el determinante de A es próximo a cero, el error de redondeo
puede ser muy grande, y esto es dificil de estimar numéricamente
(
)
Se requieren métodos numéricos alternativos:

La primera opción que uno se plantea es
 No es eficiente (demasiadas operaciones)
 Si el determinante de A es próximo a cero, el error de redondeopuede ser muy grande.
Se requieren métodos numéricos alternativos:
 métodos directos (son exactos (no tienen asociado error de
truncamiento), y son usados cuando la mayoría de los coeficientes de A
son distintos de cero y las matrices no son demasiado grandes). Suelen
ser algoritmos ‘complicados de implementar’

La primera opción que uno se plantea es
 No es eficiente (demasiadasoperaciones)
 Si el determinante de A es próximo a cero, el error de redondeo
puede ser muy grande.
Se requieren métodos numéricos alternativos:
 métodos directos (son exactos (no tienen asociado error de
truncamiento), y son usados cuando la mayoría de los coeficientes de A
son distintos de cero y las matrices no son demasiado grandes). Suelen
ser algoritmos ‘complicados de implementar’
métodos indirectos o iterativos (tienen asociado un error de
truncamiento y se usan preferiblemente para matrices grandes
(n>>1000) cuando los coeficientes de A son la mayoría nulos –
matrices sparse-). Algoritmos sencillos de implementar que requiere
aproximación inicial y que en general no tiene porqué converger
(requieren análisis de convergencia previo).

Ejemplos
Métodos directos
método de eliminación de Gauss (llevar A a triangular)
 método de descomposición LU (A=LU, donde L triangular
U triangular superior)

 método de Cholesky

(LU para matrices simétricas)

Métodos iterativos
 método de Jacobi
 método de Gauss-Seidel
 método SOR

inferior y

METODOS DIRECTOS

método de eliminación de Gauss

LA IDEA
o Primero, mediante operacioneselementales por filas, se
transforma la matriz ampliada en una matriz triangular superior
(equivalente a la matriz de partida) (PASO DE ELIMINACION)
o Segundo, se resuelve dicho sistema obteniendo las incógnitas,
empezando por la n-esima –la última- y acabando con la
primera (PASO DE SUSTITUCION).

(ALGEBRA LINEAL)

REPETIMOS ESTE PROCESO N-1 VECES HASTA LLEGAR A

Finalmente, porsustitución regresiva resolvemos el sistema.

ELIMINACIÓN DE GAUSS: ALGORITMO COMPLETO
Paso de eliminación

Paso de sustitución (cambio de notación au)

método de descomposición LU

LA IDEA
o Primero, a partir de la matriz A se calcula aquella matriz
triangular inferior L y aquella matriz triangular superior U (con
1’s en la diagonal) tal que A=LU (PASO DE DESCOMPOSICION)
o Así, el sistemaAx=b pasa a ser LUx=b. Primero hacemos el
cambio Ux=y, que introducimos y el sistema resulta Ly=b.
Como L es triangular, fácilmente calculamos y. Finalmente,
introducimos este resultado en Ux=y, y como U es triangular,
fácilmente calculamos x. (PASO DE SUSTITUCION).

PASO DE DESCOMPOSICION : L, U \ A=LU

PASO DE SUSTITUCION : Ly=b (cambio de notación yx)

PASO DE SUSTITUCION : Ux=y(cambio de notación yb)

Comentarios práctica (MÉTODOS DIRECTOS)

-Cuidado con la información de entrada en las subrutinas!!
- Subrutina LU: algoritmo se resuelve secuenciamente!!
-Cálculo de determinantes con LU: trivial !!!!!

 det(A)=det(LU)=det(L)det(U)

Matrices estrictamente diagonal dominantes: propiedad suficiente
para Gauss sin pivote y para LU (aunque no necesarias)...