METODO DE GAUSS CON PIVOTEO
PARCIAL Y ELIMINACION HACIA ATRAS
ANALISIS DE COMPLEJIDAD
COMPUTACIONAL
La complejidad computacional de la
eliminación gaussiana simple es Θ(n3), es decir, T(n) = Θ(n3).
El cálculo de esta complejidad, supone que la matriz ingresada permite computar
el algoritmo sin necesidad de realizar pivoteo, es decir, intercambios de
filas, ni tampoco tiene en cuenta la complejidad del llamado a la función de
retrosustitución. Además determina una cota asintótica ajustada, puesto que
para éste método no existe ni mejor ni peor caso, dada la anterior condición;
sin embargo, si se tuviese en cuenta las operaciones adicionadas por la
ejecución del bucle interno de pivoteo y la función de retrosustitución a los
sumo tendríamos un pequeño aumento en la complejidad, que podríamos obviar,
puesto que los términos adicionales serian de orden dos y nuestro análisis es
asintótico. Una manera rápida de entender la complejidad de este algoritmo,
consistiría en centrar nuestro interés sobre la instrucción dentro del cuerpo
del bucle más interno, ya que es la porción de código que mas se ejecuta, dicha
instrucción conllevaría un cantidad de operaciones igual a :
Donde los dos términos (N-q) surgen del paso por el bucle más interior y el
intermedio, y los límites de la sumatoria están dados por los límites del bucle
for más externo.
EJEMPLO DE USO:
Se tiene la matriz A, y el
vector B
Paso 1: Volver matriz
aumentada
Paso 2: eliminación
columnas
Paso 3: Retrosustitucion
METODO DE GAUSS-JORDAN CON
PIVOTEO PARCIAL
PSEUDOCODIGO
DEL ALGORITMO DE GAUS-JORDAN CON PIVOTEO PARCIAL
ANALISIS DE COMPLEJIDAD COMPUTACIONAL
Al igual que la eliminación gaussiana, el método de Gauss-Jordan tiene una
complejidad Θ(n3). La razon de esto es que
Gauss-Jordan se basa en la eliminación gaussiana, solo que para cada
eliminación se eliminan tanto los elementos por debajo como aquellos que se
encuentran sobre el pivote, de forma que al final lo que resta es normalizar la
matriz aumentada, este ultimo procedimiento seguramente suma un termino lineal
a la complejidad, que, por ende, puede ser obviado para el calculo de la
complejidad.
METODO DE FACTORIZACION LU
ANALISIS DE COMPLEJIDAD
COMPUTACIONAL
El método de factorización LU, es una extensión o mas bien una
generalización del método de eliminación gaussiana, puesto que usando el mismo
proceso, obtiene una factorización que resulta mucho mas aplicable a diferentes
sistemas de ecuaciones lineales. De lo anterior se deduce que la complejidad de
la factorización LU sea, al igual que la de la del método de Gauss, Θ(n3) puesto que requiere la misma cantidad de
operaciones, con la leve diferencia de que luego del calculo de los
multiplicadores, estos se deben almacenar; además de que se debe efectuar una
sustitución hacia delante y otra hacia atrás para resolver los sistemas de
ecuaciones complementarios necesarios para llegar a la solución, esto ultimo
suma dos términos lineales al calculo de la complejidad computacional, los
cuales pueden ser despreciados debido a la naturaleza asintótica de la búsqueda
de la complejidad.
No hay comentarios:
Publicar un comentario