Métodos directos e iterativos para resolver sistemas lineales

Computación. Cálculo computacional. Métodos de factorización. Geometría algebraica. Sustitución inversa. Cholesky. Número de condición. Método de Jacobi. Gauss-Seidel

  • Enviado por: Daniel Rosquete
  • Idioma: castellano
  • País: Venezuela Venezuela
  • 14 páginas

publicidad
cursos destacados
Programación Android 04 Ciclo de vida de una actividad
Programación Android 04 Ciclo de vida de una actividad
Este curso trata sobre cómo el sistema operativo avisa del cambio de estado a las actividades en el sistema...
Ver más información

Cómo incluir info HTML en otro HTML
Cómo incluir info HTML en otro HTML
En este vídeo vamos a ver cómo incorporar dentro de un documento HTML información desde otro...
Ver más información

publicidad

'Métodos directos e iterativos para resolver sistemas lineales'
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:

  • El número de iteraciones dado fue alcanzado.

  • El nivel de tolerancia introducido por el usuario fue alcanzado.

  • 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:

    'Métodos directos e iterativos para resolver sistemas lineales'

    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:

    'Métodos directos e iterativos para resolver sistemas lineales'


    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:

    'Métodos directos e iterativos para resolver sistemas lineales'

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

    'Métodos directos e iterativos para resolver sistemas lineales'

    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:

    'Métodos directos e iterativos para resolver sistemas lineales'


    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:

    'Métodos directos e iterativos para resolver sistemas lineales'

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

    'Métodos directos e iterativos para resolver sistemas lineales'

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

    'Métodos directos e iterativos para resolver sistemas lineales'

    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:

  • Asignar un valor inicial a cada incógnita que aparezca en el conjunto. Si es posible hacer una hipótesis razonable de éstos valores, hacerla. Si no, se pueden asignar valores seleccionados arbitrariamente. Los valores iniciales utilizados no afectarán la convergencia como tal, pero afectarán el número de iteraciones requeridas para dicha convergencia.

  • Partiendo de la primera ecuación, determinar un nuevo valor para la incógnita que tiene el coeficiente más grande en esa ecuación, utilizando para las otras incógnitas los valores supuestos.

  • Pasar a la segunda ecuación y determinar en ella el valor de la incógnita que tiene el coeficiente más grande en esa ecuación, utilizando el valor calculado para la incógnita del paso 2 y los valores supuestos para las incógnitas restantes.

  • Continuar con las ecuaciones restantes, determinando siempre el valor calculado de la incógnita que tiene el coeficiente más grande en cada ecuación particular, y utilizando siempre los últimos valores calculados para las otras incógnitas de la ecuación. (Durante la primera iteración, se deben utilizar los valores supuestos para las incógnitas hasta que se obtenga un valor calculado). Cuando la ecuación final ha sido resuelta, proporcionando un valor para la única incógnita, se dice que se ha completado una iteración.

  • Continuar iterando hasta que el valor de cada incógnita, determinado en una iteración particular, difiera del valor obtenido en la iteración previa, en una cantidad menor que cierto 'Métodos directos e iterativos para resolver sistemas lineales'
    seleccionado arbitrariamente. El procedimiento queda entonces completo.

  • Refiriéndonos al paso 5, mientras menor sea la magnitud del 'Métodos directos e iterativos para resolver sistemas lineales'
    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 'Métodos directos e iterativos para resolver sistemas lineales'
    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:

  • En esta etapa se tradujeron los algoritmos de factorización proporcionados en clase (LU, LDLt, Choleski) al lenguaje “C/C++”, como se describió anteriormente y se corrigieron algunos errores de índices que había en el soporte en papel, luego, en esta misma etapa fueron pensados y programados los procedimientos correspondientes a la Carga de datos, generador del vector X aleatorio, creación del vector B, que será el que nos arrojará la solución a partir del vector X creado anteriormente, además fueron realizados los procedimientos de sustituciones respectivas a cada factorización, y numerosos procedimientos adicionales correspondientes a esta primera etapa del proyecto.

  • Este paso puede ser llamado “la etapa de las pruebas” ya que acá se realizaron diversos ensayos con matrices tomadas del libro [1] † y se verificó que los resultados estuvieran correctos, colocando de manera correcta el orden de ejecución de las funciones y procedimientos en el segmento conocido como “Main”, de igual manera se corrigieron errores que aparecieron en las pruebas.

  • “Etapa de modularidad”, en este paso se tomó el código trabajado hasta el momento, bajo un mismo archivo y fueron fragmentados en tres partes, que consisten en: Carga.c, Metdir.c, Vector.c e Metiter.c, cada uno de los anteriores es dependiente de sus respectivos “Headers” que tienen el mismo nombre del archivo con extensión“.c” que es donde se desarrolla cada procedimiento individualmente, pero en el caso de las cabeceras es de terminación “.h”, de igual manera existen archivos .cpp que son los que se ejecutarán para cada método iterativo.

  • Se crearon cinco archivos “Makefile”, cada uno por un archivo de ejecución, para poderlo ejecutar, se debe seguir de acuerdo a la nemotecnia por los nombres de cada archivo por ejemplo lo siguiente:

    • 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)