Universidad de Carabobo

Facultad de Ciencias y Tecnología

Departamento de Computación

Cálculo Computacional

Proyecto 1:

Métodos directos e iterativos para resolver sistemas lineales.

13' 3e 'April' 3e '2005

Introducción

Con la evolución de los descubrimientos matemáticos, fueron creándose cada vez mas áreas de desarrollo y así mismo la sociedad fue exigiendo logros mas altos, tales como: edificios mas seguros, puentes mas resistentes, señales de onda, exploración de recursos energéticos (como el petróleo) entre otras, bajo estas razones se comienzan a implementar los sistemas de ecuaciones lineales para poder resolver todas estas demandas que exigía el mundo moderno. Sin embargo plantearlas no es suficiente, hay que resolverlas, y esto se logra por medio de teorías que provienen del siglo XIX y que ciertamente se les viene a ver su aplicabilidad es en la época moderna. Sin duda alguna, se está frente a la imagen de visionarios, de verdaderos poetas científicos.

Ahora bien, entrando en materia podremos ver mediante los ejemplos anexos en código fuente y las teorías de el método de resolución de cada factorización, que para resolver las ecuaciones lineales, se manipulan son sus coeficientes y de esta manera poder conseguir una solución efectiva al compactar todos estos “valores” que acompañan a las variables en una matriz, que contenga la información necesaria, para resolver el sistema de manera correcta.

Bien se podría representar un sistema lineal de ecuaciones como una matriz Mnxn donde M es la matriz a evaluar y n representa las dimensiones de la misma, se dice que es nxn porque las matrices a factorizar deben ser cuadradas, es decir, tener el mismo número de elementos que de filas, ahondando en el procedimiento, tenemos la ecuación Ax=b, donde A es la matriz, x es un vector de incógnitas que se va a resolver una vez aplicada la factorización y ese resultado se verá expresado en b, que también es un vector, es decir, el resultado de la incógnita X1 será igual al resultado de b1 y así se mantendrá hasta Xn y bn respectivamente.

Los 3 métodos de factorización que resuelven de manera efectiva estos sistemas son los siguientes: Factorización LDLt. Factorización Cholesky y finalmente la factorización LU.

La factorización LU se caracteriza por colocar en la triangular inferior de la matriz simplificada los valores de los multiplicadores dejando de esta manera la “reducción” de la matriz en la triangular superior, y así poder aplicar el método de “Sustitución hacia atrás” y obtener los valores del vector b. La factorización LDLt es eficiente para resolver matrices simétricas, característica suficiente para subrayarla como eficaz de tiempo y efectiva en sus resultados. Finalmente el método de Cholesky, se utiliza para resolver matrices definidas positivas, de manera rápida, en comparación con el resto de las factorizaciones ya que las mismas realizan un número importante de operaciones sin necesidad, ocasionando pérdida importante de tiempo de máquina. De igual manera en este proyecto, se tiene como recurso importante al cálculo del número de condición el cual se logra por medio la matriz inversa.

Como ultima parte del software, tenemos la implementación del algoritmo de Gauss-Seidel, que mediante un método iterativo de pruebas intenta aproximar los valores resultantes al del vector x de la mejor manera posible este método funcionará siempre que se cumplan por lo menos una de las siguientes condiciones:

Al cumplirse cualquiera de las dos inmediatamente el software finaliza su búsqueda arrojando de resultado los números mejor aproximados posibles gracias a este procedimiento. En este proyecto no se utilizó que se cumpliera la condición a debido a que el objetivo es lograr la mejor aproximación posible.

Antecedentes

Desde pocas centurias atrás, los expertos en cálculo, mejor conocidos como matemáticos, se propusieron lograr los alcances científicos más altos que había la conocido la humanidad hasta el momento: por ejemplo las grandes diferencias entre las propiedades de las funciones de variables reales y las de variables complejas, las demostraciones del teorema fundamental del cálculo y del resto de Taylor, por nombrar algunos de los métodos que siguen vigentes, son imprecisos e intuitivos.

En el siglo XIX, resultará una integración armoniosa de las teorías ingeniosas de los siglos anteriores y de las teorías “mecánicas” o sistemáticas, de las funciones de variable real y de variable compleja. Esto por uno de los flancos matemáticos presentados en este siglo, ahora bien, en el campo del álgebra, el problema central sigue siendo el de la resolución de las ecuaciones de grado mayor o igual a cuatro cuya solución se logró gracias a los arduos trabajos de Gauss, Jordan, Galois, Sylaw, Kronecker, Cayley, Lie y Klein. La importancia concedida al estudio de los problemas lineales es tangible gracias a numerosos trabajos consagrados a los determinantes y a las matrices, en el estudio de las formas algebraicas y, finalmente, en la introducción del concepto de nuevos tipos de álgebra. Adicionalmente, todos estos estudios colaboraron con la difusión del cálculo lineal y al considerable auge del análisis vectorial.

La geometría algebraica, tomará su forma definitiva en el siglo XX y conocerá entonces un desarrollo rápido. La geometría diferencial moderna será obra de los trabajos fundamentales de Monge, Gauss y Riemann .Aunque la topología habla sido presentada antes por Leibniz bajo el nombre de geometría de situación, y a ella están ligados problemas célebres como el de los puentes de Konigsberg, el de los nudos y el de coloreado de un mapa geográfico “Corolario”, esta disciplina no comienza a dibujarse como tal hasta los trabajos de Cayley, Listing y Mobins. Fue Riemann quien fundó verdaderamente esta nueva rama de las matemáticas, a la que consideró como el estudio de las propiedades invariantes bajo el efecto de transformaciones biunívocas continuas. El siguiente desarrollo de la topología fue influenciado por la célebre teoría de conjuntos de Cantor, por los progresos de la teoría de los números reales de Dedekind y de Bolzano, y por el estudio de las funciones de variables reales. Además en la ciencia moderna se utilizan los sistemas de geometría algebraica se utiliza desde las construcciones de las casas hasta el ensamble de circuitos integrados para las mas complejas computadoras

Johann Friedrich Gauss, autor de más de setecientas memorias y libros, quien desarrolló un marcado interés por la geometría en general y, en particular, por la no euclideana, de igual manera, su tendencia se inclinó también por casi todas las ramas de las matemáticas. Siendo una de las creaciones ingeniosas de las mas reconocidos el “método de la eliminación Gaussiana” que fue, el primer método conocido y vigente utilizado en el álgebra, para la solución de ecuaciones algebraicas lineales simultáneas. Este método consiste en eliminar las incógnitas mediante la combinación de las ecuaciones, es decir, un conjunto de n ecuaciones con n incógnitas se reduce a un sistema triangular equivalente (un sistema equivalente es un sistema que tiene iguales valores de la solución), que a su vez se resuelve de manera sencilla mediante el procedimiento conocido como "sustitución inversa". Sin embargo este método tiene tres grandes desventajas que son: los errores de redondeo de los cuales ninguno de los métodos vigentes se salvan, por otro lado los sistemas mal condicionados y finalmente la división entre 0 en algunos casos. Bajo el mismo concepto pero viendo el lado negativo de esta “sustitución inversa” (según Lourdes Sánchez del departamento de sistemas de la Universidad Autónoma Metropolitana de México) el número de ecuaciones simultáneas que puede resolver satisfactoriamente utilizando de 8 a 10 dígitos significativos en las operaciones aritméticas, se limita generalmente a 15 o 20, mientras que los otros métodos soportan mayor número de ecuaciones con errores mas reducidos.

Luego de muchos estudios posteriores se logran resumir los métodos de factorización básicamente en 3, uno de ellos es la factorización LDLt que fue hipotéticamente propuesto de igual manera por: Johann Carl Friedrich Gauss; en segundo lugar tenemos el método factorización LU propuesto por Doolittle de quien no se conoce a fondo su biografía, al menos no se pudo conseguir, y de último pero no menos interesante tenemos la factorización conocida como “Cholesky” y lleva este nombre por su creador el Mayor Andre-Louis Cholesky quien nació el 15 de Octubre de 1875 en Montguyon, Francia, comenzó su carrera militar a la edad de 20 años en un instituto politécnico, luego ingresó en el comando de artillería, años mas tarde trabajó para el servicio geográfica de Francia, específicamente en “Geodesy”, donde contribuyó para resolver el enigma de pertenencia de la isla de Creta que fue ocupada por tropas internacionales, durante momentos de guerra. De igual manera su aporte se ve actualmente gracias a sus muchísimos avances matemáticos y algorítmicos, el mas relevante fue el método de Factorización Cholesky que según el mismo dijo “Ayudaría muchísimo a la humanidad si fuera publicado algún día” de esto, se encargó el comandante Benoit ya que fallece por su país el 31 de Octubre de 1918 y este escrito fue publicado en 1924 en la revista “Bulletin geodesique” desde la página 67-77. †

† Información publicada en el website [3] por Richard W. Cottle, traducido por el autor.

Desarrollo

Bases teóricas

Método de Factorización LU

La forma más sencilla de explicar el método LU es ilustrando el método de Gauss básico a través de un ejemplo, como es el caso de la matriz dada a continuación y aplicando el procedimiento a un sistema de cuatro ecuaciones con cuatro incógnitas:

En el primer paso, multiplicamos la primera ecuación por 12/6= 2 y la restamos a la segunda, después multiplicamos la primera ecuación por 3/6 = 1/2 y la restamos a la tercera y finalmente multiplicamos la primera ecuación por -6/6=-1 y la restamos a la cuarta. Los números 2, ½ y -1 son los multiplicadores del primer paso del proceso de eliminación. El número 6 es el elemento pivote de este primer paso y la primera fila, que no sufre modificación alguna, se denomina fila pivote. El sistema en estos momentos tiene el siguiente aspecto:

En el siguiente paso del proceso, la segunda fila se emplea como fila pivote y -4 como elemento pivote aplicamos del nuevo el proceso: multiplicamos la segunda fila por -12/-4=3 y la restamos de la tercera y después multiplicamos la segunda fila por 2/(-4)=-1/2 y la restamos a la cuarta. Los multiplicadores son en esta ocasión 3 y -1/2 y el sistema de ecuaciones se reduce a:

El último paso consiste en multiplicar la tercera ecuación por 4/2=2 y restarla a la cuarta. El sistema resultante resulta ser:

El sistema resultante es triangular superior y equivalente al sistema original (las soluciones de ambos sistemas coinciden). Sin embargo, este sistema es fácilmente resoluble aplicando el algoritmo de sustitución regresiva. La solución del sistema de ecuaciones resulta ser:

Si colocamos los multiplicadores utilizados al transformar el sistema en una matriz triangular inferior unitaria (L) ocupando cada uno de ellos la posición del cero que contribuyó a producir, obtenemos la siguiente matriz:

Por otra parte, la matriz triangular superior (U) formada por los coeficientes resultantes tras aplicar el algoritmo de Gauss (2), es:

Estas dos matrices nos dan la factorización LU de la matriz inicial de coeficientes, A, expresada por la ecuación (1):

Factorización Cholesky

El método de Cholesky es aplicado para factoriza matrices definidas positivas donde el sistema Ax=b se puede escribir como L(Ltx)=b donde L es una matriz triangular inferior y Lt su transpuesta; se sustituye Ltx=y y se resuelve el sistema triangular inferior Ly=b mediante una sustitución hacia delante obteniendo y, luego se resuelve el sistema triangular superior Ltx=y mediante el proceso de sustitución hacia atrás. Este método tiene la particularidad de que cada elemento pivote se obtiene al calcular la raíz cuadrada de lii, donde lii es el elemento diagonal de L que se encuentra en el renglón i, columna i.

Factorización LDLt

Con la factorización LDLt, una matriz puede ser factorizada como el producto de tres matrices; una matriz L, o triangular inferior unitaria, una matriz D, o diagonal y una matriz Lt, es decir, la matriz triangular inferior transpuesta.

Así obtendríamos el sistema L(DLtx)=b, donde DLtx=y, teniendo esto, se busca y resolviendo el sistema Ly=b mediante un procedimiento llamado sustitución hacia delante, una vez hecho esto, se sustituye Ltx en el sistema DLtx=y por z y así resolver el nuevo sistema diagonal Dz=y cuya incógnita es z, y finalmente resolver el sistema triangular superior Ltx=z mediante un proceso de sustitución hacia atrás.

Este método puede ser utilizado para resolver matrices simétricas si estas pueden ser resueltas con una eliminación gaussiana sin intercambio de renglones.

Número de condición

Se le llama número de condición al procedimiento en el cual multiplicas la norma infinito de la matriz inversa por la norma infinito de la matriz, esto dará como resultado un número real que es principalmente usado para el resolver el problema de las matrices mal condicionadas, problema que además afecta a muchos de los métodos de factorización.

Método de Jacobi

El método de Jacobi consiste en una secuencia de transformaciones ortogonales. Cada transformación la denominaremos una rotación de Jacobi; y realmente corresponde a una rotación cuyo objeto es eliminar un elemento de la matriz. Así vamos rotando sucesivamente la matriz hasta que el error es lo suficientemente pequeño para ser considerada diagonal.
Un concepto fundamental en este método es que, al rotar la matriz para eliminar un elemento que ya valga cero, modificamos muchos elementos situados en la fila y la columna del elemento rotado, que podían valer cero y hasta haber sido rotados con anterioridad. Sin embargo, cada vez que rotamos un elemento, todos los elementos que insertamos son función de la cantidad que eliminamos ponderada por una función trigonométrica, por lo que el valor absoluto de los elementos distintos de la diagonal se irá reduciendo hasta que podamos considerar que son cero.

La composición de las rotaciones nos va a generar los autovectores, mientras que los elementos de la diagonal principal van a corresponder a los autovalores.

Método de Gauss-Seidel

El método de eliminación para resolver ecuaciones simultáneas suministra soluciones suficientemente precisas hasta para 15 o 20 ecuaciones. El número exacto depende de las ecuaciones de que se trate, del número de dígitos que se conservan en el resultado de las operaciones aritméticas, y del procedimiento de redondeo. Utilizando ecuaciones de error, el número de ecuaciones que se pueden manejar se puede incrementar considerablemente a más de 15 o 20, pero este método también es impráctico cuando se presentan, por ejemplo, cientos de ecuaciones que se deben resolver simultáneamente. El método de inversión de matrices tiene limitaciones similares cuando se trabaja con números muy grandes de ecuaciones simultáneas.

Sin embargo, existen varias técnicas que se pueden utilizar, para resolver grandes números de ecuaciones simultáneas. Una de las técnicas más útiles es el método de Gauss-Seidel. Ninguno de los procedimientos alternos es totalmente satisfactorio, y el método de Gauss-Seidel tiene la desventaja de que no siempre converge a una solución o de que a veces converge muy lentamente. Sin embargo, este método convergirá siempre a una solución cuando la magnitud del coeficiente de una incógnita diferente en cada ecuación del conjunto, sea suficientemente dominante con respecto a las magnitudes de los otros coeficientes de esa ecuación.
Es difícil definir el margen mínimo por el que ese coeficiente debe dominar a los otros para asegurar la convergencia y es aún más difícil predecir la velocidad de la convergencia para alguna combinación de valores de los coeficientes cuando esa convergencia existe. No obstante, cuando el valor absoluto del coeficiente dominante para una incógnita diferente para cada ecuación es mayor que la suma de los valores absolutos de los otros coeficientes de esa ecuación, la convergencia está asegurada. Ese conjunto de ecuaciones simultáneas lineales se conoce como sistema diagonal.
Un sistema diagonal es condición suficiente para asegurar la convergencia pero no es condición necesaria. Afortunadamente, las ecuaciones simultáneas lineales que se derivan de muchos problemas de ingeniería, son del tipo en el cual existen siempre coeficientes dominantes.
La secuencia de pasos que constituyen el método de Gauss-Seidel es la siguiente:

Refiriéndonos al paso 5, mientras menor sea la magnitud del
seleccionado, mayor será la precisión de la solución. Sin embargo, la magnitud del epsilon no especifica el error que puede existir en los valores obtenidos para las incógnitas, ya que ésta es una función de la velocidad de convergencia. Mientras mayor sea la velocidad de convergencia, mayor será la precisión obtenida en los valores de las incógnitas para un
dado.

Metodología

Los datos adjuntos a este trabajo electrónico, no son mas que los códigos en los cuales se sustenta este informe escrito, cada código fuente fue desarrollado bajo el lenguaje “C/C++” en su modo “ANSI” (American National Standards Institute) para conservar el estándar para los diversos sistemas operativos. Para poder realizar este proyecto hubo que seguir una serie de pasos que fueron los siguientes:

• Para LU: make -f Makefile_lu

• Para Cholesky: make -f Makefile_cholesky

• Para LDLt: make -f Makefile_ldlt

Formato de entrada

Con la idea de hacer un programa de acceso “simple”, se crea un archivo denominado especificaciones.in de fácil utilización, consiste unicamente en 3 líneas, que llevarán en su haber los 3 datos importantes para realizar este proyecto efectivamente, la primera consistirá en el formato de carga de la matriz (CRS o Matrix Market) ya que los mismos son formatos por excelencia para este tipo de software, entonces, en la primera línea debe ser especificado con un 0 si se desea utilizar el formato Matrix Market o un 1 si es el de CRS ,luego en la línea siguiente se da la posibilidad de hacer el método de factorización con conteo de sumas/restas y multiplicaciones/divisiones o sin conteo el procedimiento de factorización a realizar, de igual manera sería con un 1 si se quiere y un 0 sino, finalmente tenemos el número de tolerancia permitido por el usuario.

El segundo archivo corresponde al nombre de “Matriz.ent” y su formato estará definido por el que se haya seleccionado en “especificaciones.in”.

Implementación

Antes de mostrar las gráficas basadas en tiempo se mostrarán las especificaciones técnicas del computador donde fue probado este proyecto

• Especificaciones del computador:

CPU: Intel Pentium 4 1.8 Ghz.

Tarjeta Madre: MSI

Memoria RAM: 224 Megabytes (32 Megabytes compartidos para video)

D.D: 40 Gigas

• Especificaciones del sistema operativo:

Se trabajó bajo Knoppix 3.6, que contiene:

• Linux-Kernel 2.4.x

• KDE V3.0.3 como entorno gráfico estandar con KOffice y el navegador web Konqueror.

• Varios lenguajes de programación, herramientas de desarrollo y librerías para desarrolladores.

• Aplicaciones adicionales no utilizadas para las pruebas.

Ya que el mismo, está basado en sistema Linux y es de fácil ejecución sin necesidad de crearle particiones al disco duro. Fue probado en la aplicación conocida como “cónsola”

PRUEBAS Y RESULTADOS

		Metodo LU
Nombre	Dimensión	-O1	-O2	-O3
BCSSTK04.MTX	132	0``` 77808	0``` 71974	0``` 82099
BCSSTK06.MTX	420	1``` 92392	1``` 4834	2``` 4294064582
BCSSTK10.MTX	1086	14``` 4294467209	13``` 4294887608	13``` 512501
BCSSTK02.MTX	66	0``` 27653	0``` 26415	0``` 32907
BCSSTK03.MTX	2003	76``` 429467775541	74``` 4294872984	75``` 814355
BCSSTK11.MTX	112	0``` 76645	0``` 65334	1``` 4294042287

		Metodo LDL^t
Nombre	Dimensión	-O1	-O2	-O3
BCSSTK04.MTX	132	0``` 69086	0``` 63668	0``` 66951
BCSSTK06.MTX	420	1``` 4294812706	1``` 4294827897	1``` 4294809909
BCSSTK10.MTX	1086	27``` 48655	27``` 78583	27``` 429472202
BCSSTK02.MTX	66	0``` 31409	0``` 26083	0``` 26118
BCSSTK03.MTX	2003	106``` 491251	105``` 4294282709	107``` 4294707549
BCSSTK11.MTX	112	0``` 61377	0``` 65364	0``` 47015

		Metodo Cholesky
Nombre	Dimensión	-O1	-O2	-O3
BCSSTK04.MTX	132	1``` 1294034229	0``` 66262	0``` 66272
BCSSTK06.MTX	420	0``` 709691	0``` 711548	1``` 4294677028
BCSSTK10.MTX	1086	7``` 66480	7``` 45499	7``` 495613
BCSSTK02.MTX	66	0``` 16834	0``` 16672	0``` 14749
BCSSTK03.MTX	2003	36``` 4294954630	36``` 4294926390	36``` 42948556003
BCSSTK11.MTX	112	0``` 45399	0``` 46849	0``` 042324

	Método LU
Nombre	Error Relativo
BCSSTK04.MTX	9,45201893961721E-16
BCSSTK06.MTX	3,77438084564096E-15
BCSSTK10.MTX	3,05280803691548E-16
BCSSTK02.MTX	1,16375579101169E-16
BCSSTK03.MTX	4,19067285067489E-15
BCSSTK11.MTX	1,44560289664733E-15

	Método LDLT
Nombre	Error Relativo
BCSSTK04.MTX	1,20545077624852E+03
BCSSTK06.MTX	1,18253919876944E+04
BCSSTK10.MTX	2,77102434471308E+04
BCSSTK02.MTX	1,16375579101169E-16
BCSSTK03.MTX	3,68765080910084E+04
BCSSTK11.MTX	4,48547735142637E+04

	Método Cholesky
Nombre	Error Relativo
BCSSTK04.MTX	1,20545077624453E+03
BCSSTK06.MTX	1,18253919876438E+04
BCSSTK10.MTX	2,77102434471455E+04
BCSSTK02.MTX	2,32751158202338E-16
BCSSTK03.MTX	3,68765080900200E+04
BCSSTK11.MTX	4,48547735142736E+04

Número de condición
Nombre	Número
BCSSTK04.MTX	16064,979846
BCSSTK06.MTX	9804,911670
BCSSTK10.MTX	1955,010887
BCSSTK02.MTX	8,752170
BCSSTK03.MTX	111010391,221347
BCSSTK11.MTX	1901390,916600

Gráfica de convergencia de Gauss-Seidel y Jacobi

Conclusión

Este informe teórico está basado en la idea de hacer notar las diferencias entre los métodos Iterativos y Directos y la importancia que tienen cada uno en nuestras vidas sin darnos cuentas la mayoría de las veces.-

Por esta razón, se tomaron muestras matriciales cortesía de la página “Matrix Market” para realizar pruebas y poder llegar a conclusiones concisas y reales, gracias a estas tablas y resultados arrojados por el código fuente que se diseñó específicamente para la demostración de estos métodos, podemos notar que tanto LU como Cholesky tienen un número de sumas/restas muy parecido al de multiplicaciones/divisiones el que es distinto de estos métodos es el LDLt cuyas multiplicaciones/divisiones son considerablemente menores al número de sumas/restas.

La grafica de convergencia entre los métodos iterativos de Jacobi y Gauss-Seidel demuestra que pese a que el método de Jacobi tiene buenos planteamientos no se encuentra optimizado a diferencia del método de Gauss-Seidel, cuya convergencia es mucho mas rápida que el anterior.

Bibliografía y referencias

• http://luda.azc.uam.mx/curso2/tema3/sistem02.html#elim

• BURDEN, Richard L., FAIRES, J. Douglas: Numerical Analysis. Sixth edition.

• http://www.netlib.org/na-digest-html/90/v90n07.html#4

• http://www.uv.es/~diaz/mn/node29.html

• http://luda.azc.uam.mx/curso2/tema3/sistema04.html

• http://html.rincondelvago.com/ historia-de-las-matematicas_el-siglo-xviii.html

9

.

(2)

(1)