cálculo numérico - venus.ceride.gov.ar

Cálculo NuméricoTrabajo Práctico N° 3

“Métodos iterativos para sistemas de ecuaciones lineales”

Alejandro Debus – DNI 36273716Año 2014

1. Ejercicio 7

Este ejercicio consiste en resolver un sistema de ecuaciones lineales con todos los métodositerativos dados en clase (Jacobi, Gauss-Seidel, SOR, Gradiente Conjugado). Luego se debencomparar los resultados obtenidos con el método directo de eliminación de Gauss.Las entradas para la matriz de coeficientes del sistema lineal son:

con i=1,.....n con n=250, 500 y 1000.Las entradas del vector de términos independientes es bi=π

Como vector de aproximación inicial utilizaremos un vector X=0Para generar la matriz de coeficientes con el vector de términos independientes se implementó el Algoritmo N° 1: Generar matriz.

Aplicación de los métodos para N=250

(N es el orden la matriz). Con el Algoritmo N° 1: Generar Matriz, generamos una matriz de orden250. Este algoritmo genera la matriz A respetando las condiciones de entrada de los coeficientesdadas en el enunciado del ejercicio, el vector b de términos independientes y el vector deaproximación inicial X=0. El máximo número de iteraciones que vamos a usar para resolver elsistema de ecuaciones para todos los métodos es 250, el cual es igual al orden de la matriz.

Aplicación del método de Jacobi

Con el Algoritmo N° 2: Método de Jacobi, resolvemos el sistema.En 39 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demora enobtener la solución es de 7.332 segundos. [Observación: Con los lazos del código en formavectorizada el tiempo en que se obtuvo la solución es 0.251 segundos, muy inferior al obtenido conlos lazos escritos de forma no vectorizada].El residuo resultante de la última iteración es 0.0000082.

1

La Figura N° 1 muestra la tasa de convergencia para el método de Jacobi en función del númerode iteraciones.

Figura N° 1: Tasa de convergencia del método de Jacobi

Aplicación del método de Gauss-Seidel

Con el Algoritmo N° 3: Método de Gauss-Seidel resolvemos el sistema.En 9 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demora enobtener la solución es de 1.683 segundos. [Observación: Con los lazos del código en formavectorizada el tiempo en que se obtuvo la solución es 0.077 segundos, muy inferior al obtenido conlos lazos escritos de forma no vectorizada].El residuo resultante de la última iteración es 0.0000064 La Figura N° 2 muestra la tasa de convergencia de este método en función del número deiteraciones que se realizaron para encontrar la solución teniendo en cuenta la tolerancia dada.

Figura N° 2: Tasa de convergencia del método de Jacobi

2

Aplicación del método SOR

Para realizar la resolución del sistema mediante el método de Sobrerrelajación Sucesiva se debeseleccionar un ω apropiado. El teorema de Kahan (Teorema 7.24 - p 449 - Análisis Numérico, 7 ed -Burden, Richard) enuncia que si aii ≠ 0 para cada i=1, 2, …., n, entonces ρ(Tω)≥|ω-1|. Ello significaque el método SOR converge si y solo si 0 < ω < 2.Siguiendo el teorema de Kahan vamos a seleccionar valores de ω experimentales.Para ω=0.5 obtuvimos 22 iteraciones en un tiempo reloj de 4.271 segundos. El último elemento delvector residual es 0.0000096 . [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 0.182 segundos].Para ω=1 obtuvimos 9 iteraciones en un tiempo reloj de 1.732 segundos. El último elemento delvector residual es 0.0000064. [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 0.084 segundos].Para ω=1.5 obtuvimos 27 iteraciones en un tiempo reloj de 5.129 segundos. El último elementodel vector residual es 0.0000077. [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 0.22 segundos].Por tanto, el ω óptimo tiene que estar entre 0.5 y 1. Realizando pruebas en Scilab llegamos a que elvalor óptimo de ω es 0.93. Para este valor de ω obtuvimos 8 iteraciones en un tiempo reloj de1.525 segundos. El último elemento del vector residual es 0.0000094. [Observación: Con laimplementación del código con sus lazos vectorizados, el tiempo que se tardó fue 0.073 segundos].

La Figura N° 3 muestra la tasa de convergencia en función del número de iteraciones que seprecisaron para llegar a la convergencia deseada teniendo en cuenta la tolerancia dada.

Figura N° 3: Tasa de convergencia del método SOR

3

Aplicación del método de Gradiente Conjugado

Con el Algoritmo N° 4: Gradiente Conjugado resolvemos el sistema generado.En 237 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demoraen obtener la solución es de 0.436 segundos. [Observaciones: Con el arreglo realizado en elAlgoritmo N° 4 el tiempo que se demoró en obtener la solución fue de 0.173 segundos.]El residuo resultante de la última iteración es 0.0000091. La Figura N° 4 muestra la tasa de convergencia de este método en función del número deiteraciones que se realizaron para encontrar la solución teniendo en cuenta la tolerancia dada.

Figura N° 4: Tasa de convergencia del método del gradiente conjugado

Aplicación del método directo de eliminación de Gauss

Aplicando este método se obtiene la solución al sistema sin haber tenido que realizar pivoteo, ya que no hubo “error” de división por cero.El tiempo reloj que demoró en resolver el sistema es 19.589 segundos.OBSERVACIONES: En la corrección del trabajo se propone realizar los lazos del código de formavectorizada. Con esta forma, el tiempo que se demoró en resolver el sistema es 0.910 segundos.Esto demuestra una gran diferencia con el código no vectorizado, lo que hace ver la eficiencia quese logra con esta forma de escribir el código.

CONCLUSIÓN

En esta conclusión no se tienen en cuenta los algoritmos con sus lazos vectorizados, si no los quefueron escritos en la forma tradicional.Para una matriz generada de orden 250, hemos buscado la solución del sistema por diferentesmétodos iterativos y realizamos la comparación con el método directo de eliminación de Gauss.

4

Método de JacobiCon una simple observación y comparación de los resultados obtenidos se puede ver que el métodode Jacobi es un método poco conveniente para buscar la solución al sistema, ya que necesita variasiteraciones (39) para aproximarse a la solución, teniendo en cuenta la tolerancia dada (1e-5). Eltiempo reloj que emplea también es mucho mayor, frente a los que tardan otros métodos. Jacobitardó 7.332 segundos y Gauss-Seidel demora 1.683 en aproximarse a la solución. Si es un métodomucho mas eficiente que el método directo de eliminación gaussiana que tarda 19.589 en llegar a lasolución del sistema.Método de Gauss-Seidel y método SOREstos métodos tuvieron un desempeño superior al método de Jacobi. A Gauss Seidel le costó 9iteraciones aproximarse a la solución, teniendo en cuenta la tolerancia dada, y lo hizo en un tiemporeloj de 1.683 segundos. SOR tuvo un desempeño apenas mejor que Gauss-Seidel; realizó 8iteraciones en un tiempo de 1.525 segundos. SOR tiene la desventaja que para converger en estacantidad de iteraciones se tuvo que encontrar un w óptimo entre los valores de 0 y 2. A partir deestas conclusiones, obviamente son métodos más eficientes que el método directo de eliminación deGauss.Método de Gradiente ConjugadoEste método fue el más rápido en tiempo reloj, pero le llevó una cantidad mayor de iteraciones(237) aproximarse a la solución, con respecto a otros métodos.

Con estas observaciones realizadas podríamos afirmar que el método iterativo del gradienteconjugado es el más eficiente de todos. Pero si miramos el número de condición de la matriz sepuede ver que:

k ( A)=|(λmax)||(λmin)|

donde λmax y λmin son los autovalores extremos de la matriz.

Para calcular los autovalores de la matriz utilizamos el Algoritmo N° 8 y luego con las funcionesmax y min de Scilab determinamos los valores λmax y λmin.

k ( A)=822.705361.8096754

=454.6148773

Se puede ver claramente que el número de condición de la matriz es mucho mayor a 1, lo que hacela matriz muy susceptible a un pequeño cambio. Por tanto, no es demasiado conveniente utilizar el método de Gradiente Conjugado.

En la Figura N° 5 se puede ver la gráfica que muestra la tasa de convergencia en función delnúmero de iteraciones de los métodos iterativos, como otra manera de ver las observacionesrealizadas en la conclusión, lo que claramente en número de iteraciones SOR es inferior.

5

Figura N° 5: Tasa de convergencia de métodos iterativos




Con el Algoritmo N° 2: Método de Jacobi, resolvemos el sistema.En 39 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demora enobtener la solución es de 29.149 segundos. [Observación: Con los lazos del código en formavectorizada el tiempo en que se obtuvo la solución es 0.882 segundos, muy inferior al obtenido conlos lazos escritos de forma no vectorizada].El residuo resultante de la última iteración es 0.0000083.

La Figura N° 6 muestra la tasa de convergencia para el método de Jacobi en función del númerode iteraciones.

6

Figura N° 6: Tasa de convergencia para el método de Jacobi


Con el Algoritmo N° 3: Método de Gauss-Seidel, resolvemos el sistema.En 9 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demora enobtener la solución es de 6.614 segundos. [Observación: Con los lazos del código en formavectorizada el tiempo en que se obtuvo la solución es 0.223 segundos, muy inferior al obtenido conlos lazos escritos de forma no vectorizada].El residuo resultante de la última iteración es 0.0000066.

La Figura N° 7 muestra la tasa de convergencia para el método de Gauss-Seidel en función delnúmero de iteraciones.

Figura N° 7: Tasa de convergencia del método de Gauss-Seidel

7


Con el Algoritmo N° 5: Método SOR, resolvemos el sistema.Siguiendo el teorema de Kahan, ya visto en páginas anteriores, vamos a seleccionar valores de ωexperimentales.Para ω=0.5 obtuvimos 22 iteraciones en un tiempo reloj de 16.821 segundos. El último elementodel vector residual es 0.0000096 . [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 0.557 segundos].Para ω=1 obtuvimos 9 iteraciones en un tiempo reloj de 6.685 segundos. El último elemento delvector residual es 0.0000066. [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 0.234 segundos].Para ω=1.5 obtuvimos 27 iteraciones en un tiempo reloj de 20.109 segundos. El último elementodel vector residual es 0.0000083. [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 0.683 segundos].Por tanto, el ω óptimo tiene que estar entre 0.5 y 1. Realizando pruebas en Scilab llegamos a que elvalor óptimo de ω es 0.93. Para este valor de ω obtuvimos 8 iteraciones en un tiempo reloj de5.927 segundos. El último elemento del vector residual es 0.0000094. [Observación: Con laimplementación del código con sus lazos vectorizados, el tiempo que se tardó fue 0.203 segundos].

La Figura N° 8 muestra la tasa de convergencia para este método en función del número de iteraciones.

Figura N° 8: Tasa de convergencia para el método SOR


Con el Algoritmo N° 4: Gradiente Conjugado resolvemos el sistema generado.En 324 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demoraen obtener la solución es de 2.541 segundos. [Observaciones: Con el arreglo realizado en elAlgoritmo N° 4 el tiempo que se demoró en obtener la solución fue de 0.705 segundos.]

8

El residuo resultante de la última iteración es 0.0000092

La Figura N° 9 muestra la tasa de convergencia de este método en función del número deiteraciones que se realizaron para encontrar la solución teniendo en cuenta la tolerancia dada.

Figura N° 9: Tasa de convergencia del método de gradiente conjugado


Aplicando este método se obtiene la solución al sistema sin haber tenido que realizar pivoteo, ya que no hubo “error” de división por cero.El tiempo reloj que demoró en resolver el sistema es 164.352 segundos. [ Observaciones: En la corrección del trabajo se propone realizar los lazos del código de forma vectorizada. Con esta forma, el tiempo que se demoró en resolver el sistema es 6.272 segundos. Esto demuestra una gran diferencia con el código no vectorizado, lo que hace ver la eficiencia que se logra con esta forma de escribir el código.]

CONCLUSIÓN

En esta conclusión no se tienen en cuenta los algoritmos con sus lazos vectorizados, si no los quefueron escritos en la forma tradicional.Para una matriz generada de orden 500, hemos buscado la solución del sistema por diferentesmétodos iterativos y realizamos la comparación con el método directo de eliminación de Gauss.El comportamiento de los algoritmos es similar al caso de la matriz de orden 250. En todos losmétodos aumentó el tiempo reloj para hallar las aproximaciones a la solución. De manera análoga,el número de iteraciones en el método de Gradiente Conjugado. El método directo de eliminaciónde Gauss aumenta de manera considerada el tiempo empleado para encontrar las soluciones delsistema, lo que permite ver que los métodos directos quedan “obsoletos” en matrices de que sean de

9

un orden demasiado grande, como en estos casos.






Con el Algoritmo N° 2: Método de Jacobi, resolvemos el sistema.En 39 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demora enobtener la solución es de 116.788 segundos. [Observación: Con los lazos del código en formavectorizada el tiempo en que se obtuvo la solución es 2.938 segundos, muy inferior al obtenido conlos lazos escritos de forma no vectorizada].El residuo resultante de la última iteración es 0.0000084.La Figura N° 11 muestra la tasa de convergencia para el método de Jacobi en función del númerode iteraciones.

10

Figura N° 11: Tasa de convergencia para el método de Jacobi


Con el Algoritmo N° 3: Método de Gauss-Seidel, resolvemos el sistema.En 9 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demora enobtener la solución es de 26.421 segundos. [Observación: Con los lazos del código en formavectorizada el tiempo en que se obtuvo la solución es 0.726 segundos, muy inferior al obtenido conlos lazos escritos de forma no vectorizada].El residuo resultante de la última iteración es 0.0000067.

La Figura N° 12 muestra la tasa de convergencia para el método de Gauss-Seidel en función delnúmero de iteraciones.

Figura N° 12: Tasa de convergencia del método de Gauss-Seidel

11


Con el Algoritmo N° 5: Método SOR, resolvemos el sistema.Siguiendo el teorema de Kahan, ya visto en páginas anteriores, vamos a seleccionar valores de ωexperimentales.Para ω=0.5 obtuvimos 22 iteraciones en un tiempo reloj de 65.36 segundos. El último elementodel vector residual es 0.0000096 . [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 1.833 segundos].Para ω=1 obtuvimos 9 iteraciones en un tiempo reloj de 26.88 segundos. El último elemento delvector residual es 0.0000067. [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 0.749 segundos].Para ω=1.5 obtuvimos 27 iteraciones en un tiempo reloj de 82.182 segundos. El último elementodel vector residual es 0.0000085. [Observación: Con la implementación del código con sus lazosvectorizados, el tiempo que se tardó fue 2.237 segundos].Por tanto, el ω óptimo tiene que estar entre 0.5 y 1. Realizando pruebas en Scilab llegamos a que elvalor óptimo de ω es 0.93. Para este valor de ω obtuvimos 8 iteraciones en un tiempo reloj de24.288 segundos. El último elemento del vector residual es 0.0000094. [Observación: Con laimplementación del código con sus lazos vectorizados, el tiempo que se tardó fue 0.674 segundos].

La Figura N° 13 muestra la tasa de convergencia para este método en función del número de iteraciones.

Figura N° 13: Tasa de convergencia para el método SOR

12


Con el Algoritmo N° 4: Gradiente Conjugado resolvemos el sistema generado.En 437 iteraciones el método cumple con la tolerancia dada de 1e-5. El tiempo reloj que demoraen obtener la solución es de 12.82 segundos. [Observaciones: Con el arreglo realizado en elAlgoritmo N° 4 el tiempo que se demoró en obtener la solución fue de 3.214 segundos.]El residuo resultante de la última iteración es 0.0000093.La Figura N° 14 muestra la tasa de convergencia de este método en función del número deiteraciones que se realizaron para encontrar la solución teniendo en cuenta la tolerancia dada.

Figura N° 14: Tasa de convergencia para el método del gradiente conjugado


Aplicando este método se obtiene la solución al sistema sin haber tenido que realizar pivoteo, yaque no hubo “error” de división por cero.El tiempo reloj que demoró en resolver el sistema es 1264.661 segundos. [ Observaciones: En lacorrección del trabajo se propone realizar los lazos del código de forma vectorizada. Con estaforma, el tiempo que se demoró en resolver el sistema es 44.871 segundos. Esto demuestra unagran diferencia con el código no vectorizado, lo que hace ver la eficiencia que se logra con estaforma de escribir el código.]

CONCLUSIÓN

En esta conclusión no se tienen en cuenta los algoritmos con sus lazos vectorizados, si no los quefueron escritos en la forma tradicional.

13

Para una matriz generada de orden 1000, hemos buscado la solución del sistema por diferentesmétodos iterativos y realizamos la comparación con el método directo de eliminación de Gauss.En este caso sucede lo mismo que para las matrices generadas de orden 250 y 500 y la relaciónentre estas. Aumenta el tiempo reloj que emplea cada método y la cantidad de iteraciones en elmétodo de gradiente conjugado. Cuando se utiliza el método directo de eliminación de Gauss, una vez mas se observa que el tiemporeloj que emplea este método es demasiado grande (1264.661 segundos = 21.07 minutos). Una vez,llegamos a la conclusión de que los métodos iterativos que hemos visto son más veloces que elmétodo directo por eliminación Gaussiana, y esto aumenta conforme al orden de la matriz.



14

CONCLUSIÓN GENERAL

En este ejercicio se estudiaron los métodos iterativos para resolución de sistemas lineales y loscomparamos con el método directo de eliminación de Gauss. Cuando se realiza esta comparación sepuede observar que para los 3 casos del orden de la matriz generada (250, 500 y 1000), los métodositerativos resultaron “ganadores” en velocidad con respecto al método directo. Algo es importanteaclarar con respecto a esto es que, los tiempos que se precisen para hallar las soluciones dependende la velocidad del procesador, arquitectura (32 o 64 bits) para la precisión y un sistema operativoque aproveche la arquitectura de tal procesador.Dentro de los métodos iterativos pudimos ver que algunos llegaban a la aproximación de la soluciónen un número pequeño de iteraciones, pero en algunos casos tardaban un tiempo reloj considerablefrente al método del gradiente conjugado. Sin embargo, en el método de gradiente conjugado vimosque el número de condición era muy grande y a consecuencia de esto, necesitaba un número deiteraciones muy grande para aproximarse a la solución. Todos los métodos lograron la convergencia, teniendo en cuenta la tolerancia dada (1e-5), por loque se obtuvo el vector solución en todos los casos. Esto se aprecia mejor al observar las gráficasrealizadas en la aplicación de cada método. Esta convergencia está asegurada en las condiciones quese tienen que dar para que tal cosa suceda: > Que la matriz sea diagonalmente dominante, para los métodos de Jacobi, Gauss-Seidel ySobrerrelajaciones Sucesivas (SOR).

> Simétrica y definida positiva, para los métodos de Gauss-Seidel, SOR, y GradienteConjugado. En el caso de los método de Gauss-Seidel, Jacobi y SOR la convergencia se encuentra asegurada, yaque la matriz es diagonalmente dominante, y por lo tanto no es necesario que esta sea simétrica, quede hecho no lo es, y por este motivo no se puede asegurar la convergencia del método de GradienteConjugado mediante estos dos teoremas enunciados. Sin embargo, como hemos visto en eldesarrollo del ejercicio el método de Gradiente Conjugado converge para la matriz dada (en ordenn=250, 500 y 1000). Incluso se ha experimentado lo que sucedía con matrices de orden pequeño. Segeneró una matriz de orden 8 con el Algoritmo N° 1: Generar Matriz. Luego se resolvió elsistema para una tolerancia de 1e-5, con un vector de aproximación inicial X=0 y mediante elmétodo de Gradiente Conjugado se halló la solución en 24 iteraciones. Finalmente, se comparó elresultado obtenido con el vector solución hallado mediante el método directo de eliminaciónGaussiana y se pudo observar que la solución obtenida con el método de Gradiente Conjugado eraefectiva. También se pudo observar que la matriz no era simétrica ni definida positiva, ya queningún autovalor era menor a 1.

15

2. Ejercicio 8

Este ejercicio consiste en resolver dos sistemas de ecuaciones lineales mediante el método iterativode Gauss-Seidel y el método directo de eliminación de Gauss.Los sistemas son iguales, con la diferencia de que tienen intercambiadas las filas 2 y 3.

Los sistemas dados son:

3 x+ y+z=5 3 x+ y+z=5x+3 y−z=3 3 x+ y−5 z=−13 x+ y−5 z=−1 x+3 y−z=3

Sistema A Sistema B

Al sistema de la izquierda lo llamaremos A y al de la derecha, B. Las matrices aumentadas de los sistemas dados quedan de la siguiente manera:

La matriz aumentada de A queda: La matriz aumentada de B queda:

[3 1 1 51 3 −1 33 1 −5 −1] [3 1 1 5

3 1 −5 −11 3 −1 3 ]

Resolución mediante el método iterativo de Gauss-Seidel

Gauss-Seidel es un método iterativo que se utiliza para resolver sistemas de ecuaciones lineales.Tiene la desventaja que no posee convergencia global, dependiendo de si cumple con ciertaspropiedades o no. En algunos sistemas, con un simple intercambio de renglones se puede obtenerconvergencia hacia la solución de sistema, ya que de esta manera cumple con las propiedades deconvergencia de Gauss-Seidel. Si alguna de las siguientes dos condiciones se cumple, entonces éstemétodo converge.

> Si la matriz es estrictamente diagonal dominante, entonces el método converge.> Si la matriz es simétrica y definida positiva, entonces el método también converge.

Para la resolución de ambos sistemas utilizaremos al vector (0 0 0 0)' como vector de aproximacióninicial. Realizaremos la prueba para 3, 5 y 10 iteraciones y con una tolerancia de 1e-3. A partir deestos datos iniciales analizaremos la convergencia hacia la solución buscada.

Para el sistema A se obtuvo: Para el sistema B se obtuvo: >>Con 3 iteraciones >>Con 3 iteraciones

Vector Solución: Vector Solución:0.9555556 169.96296

1.037037 - 2395.3333 0.9807407 - 7019.037

Vector Residual: Vector Residual: 2.1532634 20.311464

0.8777075 377.89057 0.1613659 7020.291

16

>>Con 5 iteraciones >>Con 5 iteraciones

Vector Solución: Vector Solución: 1.002963 58310.144

0.9975309 - 826980.81 1.001284 - 2422635.3

Vector Residual: Vector Residual:2.1532634 20.311464

0.8777075 377.89057 0.1613659 7020.291 0.0585138 130415.61 0.0107577 2422724.3

>>Con 10 iteraciones >>Con 10 iteraciones

Vector Solución: Vector Solución:1.0000018 10^11 *1.29005641.0000013 10^11*-18.2964991.0000013 10^11*-53.59944

Vector Residual: Vector Residual:2.1532634 20.311464 0.8777075 377.89057 0.1613659 7020.291 0.0585138 130415.61 0.0107577 2422724.3 0.0039009 45006828. 0.0007172 8.361D+08 0.0002601 1.553D+10 0.0000478 2.885D+11 0.0000173 5.360D+12

Se puede observar que la resolución del sistema A converge a una solución determinada a medidaque se incrementa el número de iteraciones. Esta solución parece converger a los valores x=1 y=1 z=1.

Analíticamente esto se puede probar ya que existe un teorema que enuncia que si la matriz esestrictamente diagonal convergente, entonces converge.

El sistema B, que posee un intercambio entre las filas 2 y 3 se puede observar que a medida que sese incrementa el número de iteraciones, el vector solución se aleja de la solución. En este caso, lascomponentes del vector residual cada vez son mayores.

Resolución mediante el método directo de eliminación de Gauss

El método de eliminación de Gauss consiste en resolver un sistema de ecuaciones aplicandooperaciones elementales para la simplificación del sistema y luego la sustitución hacia atrás paraencontrar las soluciones, ya vistas en el Trabajo Práctico N° 2: Métodos directos para sistemas deecuaciones lineales.

17

Para el sistema AAplicando el método de eliminación de Gauss se obtuvo la solución :

x= 1 y=1 z=1

Para el sistema BPara el sistema de ecuaciones B, al aplicar el método de eliminación de Gauss ocurre el “error” dedivisión por cero. La causa de esto es que en la simplificación del sistema, un elemento pivote (a22)se hace cero. Esto hace que no se pueda seguir aplicando operaciones elementales mediante estemétodo. Por tanto, no se pueden encontrar las soluciones.

Para que se puedan encontrar las soluciones del sistema B, se debería realizar un intercambio defilas, para que no ocurra el “error” de división por cero con un elemento pivote. Realizando unintercambio entre las filas 2 y 3, el sistema exactamente igual al sistema A, del cual ya vimos queposee una única solución igual a x=1 y=1 z=1. De manera análoga, un intercambio entre las filas 1y 3 también arroja como resultado la solución ya mostrada. Este intercambio realizado es de maneraexperimental. Por eso vamos a utilizar el Algoritmo N° 7, el cual devuelve el vector solución X y lamatriz de pivotes P que muestra el intercambio entre las filas. Las soluciones obtenidas son:

P= [1 0 00 0 10 1 0] y X= [1 1 1]

La matriz P muestra un intercambio entre las filas 2 y 3, tal como habíamos vistoexperimentalmente.

18

Algoritmos utilizados

Los siguientes algoritmos fueron realizados con el software matemático Scilab 5.5.0

Algoritmo N° 1: Generar Matriz

Entrada: Recibe el orden de la matriz a generar.Salida: Devuelve la matriz generada. El vector de términos ind. y el vector de de aprox. inicial.function [A,b,x0]=generaMatriz(n) for i=1:n for j=1:n if i==j then A(i,j)=2*i; else if or([j==(i+2) j==(i-2)]) A(i,j)=0.5*i; A(j,i)=0.5*i; else if or([j==(i+4) j==(i-4)]) A(i,j)=0.25*i; A(j,i)=0.25*i; else A(i,j)=0; end end end end b(i)=%pi;

x0(i)=0; endendfunction

Algoritmo N° 2: Método de Jacobi

A] Con los lazos internos sin vectorizarEntrada: Recibe una matriz A, el vector de términos independientes, el vector de aproximacióninicial, la máxima cantidad de iteraciones (para que el algoritmo no termine en bucle infinito), y unatolerancia dada.Salida: Devuelve el vector solución x, la cantidad de iteraciones necesarias para llegar a la solucióny el vector residual r_h.function [x, it, r_h]=metodoJacobi(A, b, x0, maxit, tol) [n,m]=size(A); if n~=m then error("La matriz no es cuadrada."); end x = x0; for k=1:maxit for i=1:n aux1=0; for j=1:i-1 aux1=aux1+A(i,j)*x(j); end aux2=0; for j=i+1:n aux2=aux2+A(i,j)*x(j); end y(i)=(b(i)-aux1-aux2)/A(i,i);

19

end r_h(k) = norm(y-x); x=y; it = k; if (r_h(k)<tol) then return; end endendfunction

B] Con los lazos internos vectorizados

function [x, it, r_h]=metodoJacobi(A, b, x0, maxit, tol) [n,m]=size(A); if n~=m then error("La matriz no es cuadrada.") end for c=1:maxit for i=1 : n k=[1:i-1,i+1:n]; x(i)=(-A(i,k)*x0(k)+b(i))/A(i,i); end r_h(c)=norm(x-x0) it=c; if r_h(c)<tol then return; end x0=x; endendfunction

Algoritmo N° 3: Método de Gauss-Seidel

A] Con lazos internos sin vectorizarEntrada: Recibe una matriz A, el vector de términos independientes, el vector de aproximacióninicial, la máxima cantidad de iteraciones (para que el algoritmo no termine en bucle infinito), y unatolerancia dada.Salida: Devuelve el vector solución x, la cantidad de iteraciones necesarias para llegar a la solucióny el vector residual r_h.function [x, it, r_h]=metodoGaussSeidel(A, b, x0, maxit, tol) [n,m]=size(A); if n~=m then error("La matriz no es cuadrada.") end x = x0; for k=1:maxit for i=1:n aux1 = 0; for j=1:i-1 aux1=aux1 +A(i,j)*y(j); end aux2=0; for j=i+1:n aux2=aux2+A(i,j)*x(j); end y(i)=(b(i)-aux1-aux2)/A(i,i);

20

end r_h(k) = norm(y-x); x=y; it=k; if (r_h(k)<tol) then return; end endendfunction


function [x, it, r_h]=metodoGaussSeidel(A, b, x0, maxit, tol) [n,m]=size(A); if n~=m then error("La matriz no es cuadrada.") end for c= 1:maxit for i=1:n k1=[1:i-1]; k2=[i+1:n]; x(i)=(-A(i,k2)*x0(k2)-A(i,k1)*x(k1)+b(i))/A(i,i); end r_h(c)=norm(x-x0); it=c; if r_h(c)<tol then return; end x0=x; endendfunction

Algoritmo N° 4: Método SOR

A] Con los lazos internos sin vectorizarEntrada: Recibe una matriz A, el vector de términos independientes, el vector de aproximacióninicial, la máxima cantidad de iteraciones (para que el algoritmo no termine en bucle infinito), unatolerancia dada y w que es un parámetro que debe ser 0<w<2.Salida: Devuelve el vector solución x, la cantidad de iteraciones necesarias para llegar a la solucióny el vector residual r_h.function [x, it, r_h]=metodoSOR(A, b, x0, maxit, tol, w) [n,m]=size(A); if n~=m then error("La matriz no es cuadrada."); end x=x0; for k=1:maxit for i=1:n aux1=0; for j=1:i-1 aux1=aux1+A(i,j)*y(j); end aux2=0; for j=i+1:n aux2=aux2+A(i,j)*x(j);

21

end y(i)=(1-w)*x(i)+(w)*(b(i)-aux1-aux2)/A(i,i); end r_h(k)=norm(y-x); x=y; it=k; if (r_h(k)<tol) then return end endendfunction


function [x, it, r_h]=metodoSOR(A, b, x0, maxit, tol, w) [n,m]=size(A); if n~=m then error("La matriz no es cuadrada.") end for c=1:maxit for i=1:n k1=[1:i-1]; k2=[i+1:n]; x(i)=(1-w).*x0(i)+(w/A(i,i))*(-A(i,k2)*x0(k2)-A(i,k1)*x(k1)+b(i)); end it=c r_h(c)=norm(x-x0) if r_h(c)<tol then return; end x0=x; endendfunction

Algoritmo N° 5: Método del Gradiente Conjugado

Entrada: Recibe una matriz A, el vector de términos independientes, el vector de aproximacióninicial, la máxima cantidad de iteraciones (para que el algoritmo no termine en bucle infinito), y unatolerancia dada.Salida: Devuelve el vector solución x, la cantidad de iteraciones necesarias para llegar a la solucióny el vector residual r_h.function [x, it, r_h]=metodoGradienteConjugado(A, b, x0, maxit, tol) [n,m]=size(A); if n~=m then error("La matriz no es cuadrada.") end it=1; rk = b - A * x0; v = rk; while(it<=maxit) if rk == zeros(n,1) then break; end t1=rk' * rk; t2=A * v;

22

t = t1/ (v'* t2); x = x0 + t * v; rh = rk - t * t2; r_h(it) = norm(rh,%inf) if r_h(it)<tol then break; end s1= rh' * rh; s2= rk' * rk; s = s1 / s2; v = rh + s * v; rk = rh; x0 = x; it=it+1; end it=it-1;endfunction

Algoritmo N° 6: Método directo de eliminación Gauss

A] Con los lazos internos sin vectorizarEntrada: Recibe una matriz aumentada A (Matriz cuadrada y vector de términos independientes).Salida: Devuelve el vector solución de A.function X=eliminaciongauss(A) //Eliminacion gaussiana n=size(A,"r") for i=1:n-1 for j=i+1:n m=A(j,i)/A(i,i) A(j,i)=0 for k=i+1:n+1 A(j,k)=A(j,k)-m*A(i,k) end end end if A(n,n)==0 then error("No hay solucion unica.") end //Retrosustitucion X(n)=A(n,n+1)/A(n,n) for i=n-1:-1:1 // con paso -1 s=A(i,n+1) for j=i+1:n s=s-A(i,j)*X(j) end X(i)=s/A(i,i) endendfunction


function X=eliminacionGauss(A, b) n=size(A,"r"); // Eliminacióm de Gauss for i=1:n-1 for k=i+1:n m=A(k,i)/A(i,i);

23

A(k,i+1:n)=A(k,i+1:n)-m*A(i,i+1:n); b(k)=b(k)-m*b(i); end A(i+1:n,i)=0; end // Retrosustitucion X=zeros(n,1); for i=n:-1:1 // Con paso -1 X(i)=(b(i)-A(i,i+1:n)*X(i+1:n))/A(i,i); endendfunction

Algoritmo N° 7: Método directo de eliminación Gauss con pivoteo

Entrada: Recibe una matriz cuadrada A y el vector de términos independientes.Salida: Devuelve el vector solución de A y una matriz P con el pivoteo realizadofunction [x,P]=GaussConPivoteo(A,b) M=[A,b]; [t1,t2]=size(M); i=1; while(i<=t1) P(i,i)=1; i=i+1; end for k=1:1:(t1-1) for i=(k+1):1:(t1) if(M(k,k)==0) t=k+1; while (t<=t1) if(M(t,k)<>0) then aux=M(t,:); M(t,:)=M(k,:); M(k,:)=aux; aux=P(t,:); P(t,:)=P(k,:); P(k,:)=aux; end t=t+1; end end m=M(i,k)/M(k,k); M(i,k)=0; for j=(k+1):1:t2 M(i,j)=M(i,j)-m*M(k,j); end end end if(M(t1,t1)==0) then error(“No existe solución única”). else x(t1)=M(t1,t2)/M(t1,t1); for i = (t1-1):-1:1 s=M(i,t2); for j=(i+1):1:t1 s=s-M(i,j)*x(j); end x(i)=s/M(i,i); end

24

endendfunction

Algoritmo N° 8: Calcular los eigenvalores de una matriz

Entrada: Recibe una matriz cuadrada ASalida: Devuelve un vector V con los valores propios (eigenvalores) de A.function V=eigenvalores(A) V=spec(A);endfunction

25

cálculo numérico - venus.ceride.gov.ar

Documents