post original: https://metodosnumericosgera.wordpress.com/2017/03/15/gauss-seidel-y-jacobi/
Tanto el método Gauss-Seidel y Jacobi, son algoritmos que resuelven sistemas de ecuaciones mayores o iguales a segundo grado.
Tanto el método Gauss-Seidel y Jacobi, son algoritmos que resuelven sistemas de ecuaciones mayores o iguales a segundo grado.
Al igual que los métodos anteriores de Gauss y Gauss-Jordan (ya que resuelven sistemas ecuaciones) necesitan un sistema de ecuaciones para su funcionamiento. Es decir, tener la misma cantidad de funciones que de incógnitas. No obstante, para que los métodos lleguen a una solución, dichas funciones no deben ser múltiplos entre sí, en otras palabras, no deben ser paralelas, de tal manera que las funciones se intersectan para que exista una solución para las incógnitas.
También es importante considerar que para ambos métodos, las ecuaciones del sistema de ecuaciones inicial necesitan estar acomodadas de manera que los coeficientes más grandes estén en la diagonal.
Esto significa que si comenzaramos con el siguiente sistema de ecuaciones:

Lo primero que tendríamos que hacer es reacomodarlo de la siguiente manera:

Los dos métodos son prácticamente iguales, en código fuente solo es cuestion de cambiar una cuantas líneas ya que utilizan el mismo principio y los mismos pasos para encontrar la solución. La unica diferencias es, como se muestra en la siguiente imagen, es la manera en que converge los valores de la incógnita. En Gauss-Seidel, dado los valores semillas para las incógnitas, el método evalúa x1 y con ella evalúa x2 los cuales son utilizadas para la siguiente incógnita, y así sucesivamente para las demás en la misma iteración. En cambio, Jacobi evalúa las incógnitas con y el valor nuevo lo guarda para la iteración siguiente.

Diagramas de flujo
Gauss-Seidel

Jacobi

Es un método iterativo porque utiliza la medición del error para detener las iteraciones en vez de realizar un proceso con un número de pasos definidos por el grado del sistema de ecuaciones.
Codigo Fuente en C++
Gauss-Seidel
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include #include using namespace std; double EPSILON = 0.00001; // error iterativo como tolerancia int x=0; int a=x; // copy of x int y=0; int b=y; // copy of y int z=0; int c=z; // copy of z // augmented matrix int rowA[]={2,-1,1,7}; // 2x -y +1 = 7 int rowB[]={1,2,-1,6}; // x +2y -z = 6 int rowC[]={1,1,1,12}; // x + y + z = 12 double anteriorX=-999999; // pseudo minus infinity double anteriorY=-999999; // pseudo minus infinity double anteriorZ=-999999; // pseudo minus infinity int times=0; void gaussSeidel(){ while(true){ times++; x=(rowA[3]-(rowA[1]*b)-(rowA[2]*c))/rowA[0]; y=(rowB[3]-(rowB[0]*x)-(rowB[2]*c))/rowB[1]; // we use previously obtained value of x z=(rowC[3]-(rowC[0]*x)-(rowC[1]*y))/rowC[2]; // we use previously obtained values of x and y a=x; b=y; c=z; cout << "x: " << x << ", anteriorX: " << anteriorX << endl; cout << "y: " << y << ", anteriorY: " << anteriorY << endl; cout << "z: " << z << ", anteriorZ: " << anteriorZ << endl << endl; if(abs((x-anteriorX)/x)<=EPSILON && abs((y-anteriorY)/y)<=EPSILON && abs((z-anteriorZ)/z)<=EPSILON){ break; } anteriorX=x; anteriorY=y; anteriorZ=z; } } int main(){ gaussSeidel(); cout << "FINAL ANSWER..." << endl; cout << "x: "<< x << endl; cout << "y: " << y <<endl; cout << "z: " << z << endl; cout << "it took " << times << " times to terminate"; return 0; } |
Jacobi
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <iostream> #include <cmath> using namespace std; double EPSILON = 0.00001; // error iterativo como tolerancia double x=0; double a=x; // copy of x double y=0; double b=y; // copy of y double z=0; double c=z; // copy of z // augmented matrix int rowA[]={2,-1,1,7}; // 2x -y +1 = 7 int rowB[]={1,2,-1,6}; // x +2y -z = 6 int rowC[]={1,1,1,12}; // x + y + z = 12 double anteriorX=-999999; // pseudo minus infinity double anteriorY=-999999; // pseudo minus infinity double anteriorZ=-999999; // pseudo minus infinity int times=0; void gaussSeidel(){ while(true){ times++; if(times>2){ x=(rowA[3]-(rowA[1]*anteriorY)-(rowA[2]*anteriorZ))/rowA[0]; y=(rowB[3]-(rowB[0]*anteriorX)-(rowB[2]*anteriorZ))/rowB[1]; z=(rowC[3]-(rowC[0]*anteriorX)-(rowC[1]*anteriorY))/rowC[2]; }else{ x=(rowA[3]-(rowA[1]*b)-(rowA[2]*c))/rowA[0]; y=(rowB[3]-(rowB[0]*a)-(rowB[2]*c))/rowB[1]; z=(rowC[3]-(rowC[0]*a)-(rowC[1]*b))/rowC[2]; } a=x; b=y; c=z; cout << "x: " << x << ", anteriorX: " << anteriorX << endl; cout << "y: " << y << ", anteriorY: " << anteriorY << endl; cout << "z: " << z << ", anteriorZ: " << anteriorZ << endl << endl; if(abs((x-anteriorX)/x)<=EPSILON && abs((y-anteriorY)/y)<=EPSILON && abs((z-anteriorZ)/z)<=EPSILON){ break; } anteriorX=x; anteriorY=y; anteriorZ=z; } } int main(){ gaussSeidel(); cout << "FINAL ANSWER..." << endl; cout << "x: "<< x << endl; cout << "y: " << y <<endl; cout << "z: " << z << endl; cout << "it took " << times << " times to terminate"; return 0; } |
Criterio de convergencia
La convergencia del método depende de algo llamado diagonal dominante, de acuerdo a esta pagina. Los valores de la diagonal deben ser mayores o iguales a la suma de los demás elementos de la fila. Es una condición que asegura la convergencia más no indica que obligatoriamente debe cumplir esa condición para que converja
Estos métodos pueden utilizar algo conocido como relajación, el cual, es una modificación al método de Gauss-Seidel donde para cada incógnita evaluada, se modifica con un promedio con peso obtenido con los resultados anteriores y con los resultados de la iteración presente. Esto, con el motivo de mejorar la convergencia del método. La fórmula para relajar es la siguiente, donde lambda, es un valor entre 0 y 2 previamente asignada. Para acelerar aún más la convergencia, se recomienda usar valores para lamba en un intervalo (1,2], esto se le llama sobrerrelajación.

Pruebas y Resultados
Consideremos los siguiente sistemas de ecuaciones de 3 incógnitas:
(A)
2x + z = 1 2x + 3y + z = 4 -3x + y - 2z = -3
(B)
-2x + 3y + 2z = 2 3x + z = 16 x - 4y = 11
(C)
3x + y - 2z = -10 2x - 3y + z = -4 x + 2y - 3z = -16
Las respuestas para cada uno de estos casos son:
Caso | Método | Respuesta | Iteraciones |
A | Gauss-Seidel | x = -2, y = 1, z = 5 | 38 |
A | Jacobi | x = -2, y = 1, z = 5 | 76 |
B | Gauss-Seidel | x = 3, y = -2, z = 7 | 10 |
B | Jacobi | x = 3, y = -2, z = 7 | 30 |
C | Gauss-Seidel | x = 1, y = 5, z = 9 | 17 |
C | Jacobi | x = 1, y = 5, z = 9 | 41 |
Como podemos observar, la velocidad de convergencia de Gauss-Seidel es aproximadamente 2 veces más rápida que la de Jacobi.
Casos de falla
Primeramente, si el sistema no tiene solución, el método nunca va a converger; además, si alguna variable es cero, se generaría un error de división entre cero. El programa no tiene ninguna manera de saber si fallo, al menos que se presente una división entre cero, ya que el método seguirá iterando indefinidamente dado que los valores se siguen alejando a la solución. Además, si no cumple con la propiedad de diagonal dominante (descrita anteriormente) el método difícilmente, si es que lo hace, va a converger.
Conclusiones
Estos métodos son muy deficientes en comparación a los otros métodos de los que se han visto para resolver sistemas de ecuaciones. Primeramente, este método tiene dos problemas: o simplemente no converge o lo hace muy lento. Esto se debe a que es un método iterativo, que, a comparación de los otros que no lo son y trabajan con matrices, realizan un número de procesos ya definidos por su cantidad de incógnitas donde es seguro que converge, si es que tiene solución, y es más sencillo monitorear su proceso y observar cual es el error en caso de que falle.
No hay comentarios:
Publicar un comentario