método de jacobi PDF

Preview

Summary

jacobi...

Description

Método de Jacobi I. Sánchez Molinar

E. Venegas Contreras

E.G. Mejía Espinoza

Estudiante M.C.M Av. Miguel de Cervantes Saavedra 120, Complejo Industrial Chihuahua, 31136 6141914826

Estudiante M.C.M Av. Miguel de Cervantes Saavedra 120, Complejo Industrial Chihuahua, 31136 6144672933

Estudiante MCyTA Av. Miguel de Cervantes Saavedra 120, Complejo Industrial Chihuahua, 31136. 6141914826

[email protected]. mx

[email protected]

[email protected]

RESUMEN

El algoritmo toma su nombre del matemático alemán Carl Gustav Jakob Jacobi.

El método de Jacobi usa una serie de iteraciones con el objetivo de aproximar la solución de un sistema de ecuaciones. La convergencia del sistema tiene una forma fácil de asegurarse, que la matriz principal sea diagonalmente dominante. Es decir que el elemento de la diagonal principal sea mayor en valor absoluto que la suma de los elementos del mismo renglón y demás columnas. Si no es así, no se puede asegurar la convergencia del método. Lo cual representa una desventaja.

El método de Jacobi consiste en usar fórmulas como iteración de punto fijo.

Los sistemas que resuelven es del tipo Ax = b y mediante el trabajo con las matrices se puede llegar a la siguiente ecuación, la cual se usa para la programación del método.

x(k+1 )=D

(− 1)

b+D

(− 1)

( L+U ) x k

La base del método consiste en construir una sucesión convergente definida iterativamente. El límite de esta sucesión es precisamente la solución del sistema. A efectos prácticos si el algoritmo se detiene después de un número finito de pasos se llega a una aproximación al valor de x de la solución del sistema. [1] 1.

La matriz no debe tener elementos nulos.

2.

La matriz tiene que ser dominante. Esto quiere decir que los elementos en la diagonal, deben de contener el mayor coeficiente de la ecuación.

.

n

Los requisitos para la programación son: operaciones con vectores (operaciones lineales y el producto punto), matrices triangulares, solución de sistemas con matrices triangulares, ciclo while, la matemática del método de Jacobi.

|aij|> ∑ |aij|

para ij

J=1

{

}

a11 a12 a13  a2 1 a22 a23 a3 1 a32 a33

Existe una función que resuelve de manera directa ecuaciones de este tipo, introduciendo la matriz A y el vector b, y un valor inicial de x [x0,kerA]=linsolve(A,b [,x0]), resuelve ecuaciones de este tipo. Existe también una función que nos puede dar las dos matrices triangulares requeridas para el método, introduciendo A [L,U]= lu(A)

Palabras clave Jacobi, métodos de iteración, métodos numéricos, ecuaciones, convergencia.

|a11 |

>

|a12 |+|a13|

|a 22|

>

|a 21|+|a23|

|a33 |

>

|a31 |+|a32|

INTRODUCCIÓN Un método iterativo trata de resolver un problema matemático (como una ecuación o un sistema de ecuaciones) mediante aproximaciones sucesivas a la solución, empezando desde una estimación inicial. Esta aproximación contrasta con los métodos directos, que tratan de resolver el problema de una sola vez (como resolver un sistema de ecuaciones Ax=b encontrando la inversa de la matriz A). Los métodos iterativos son útiles para resolver problemas que involucran un número grande de variables (a veces del orden de millones), donde los métodos directos tendrían un coste prohibitivo incluso con la potencia del mejor computador disponible.

El método de Jacobi es un método iterativo, usado para resolver sistemas de ecuaciones lineales del tipo Ax = b .

3.

El sistema de ecuaciones debe de ser cuadrado, es decir, el número de ecuaciones es igual al número de incógnitas.

El método de Jacobi y Gauss-Seidel, son muy parecidos, a continuación, se enuncian algunas diferencias. Jacobi: para cada iteración, el método utiliza los valores previamente estimados de las variables. En caso de ser la iteración inicial, las variables tienen valores default, o bien, el usuario define dichos valores. Gauss-Seidel: lo que hace este método es reemplazar las variables que fueron calculadas en la iteración anterior por las de la iteración actual al instante. De esta manera, se reduce el número de iteraciones. En cuanto a eficiencia computacional, el método de Gauss-Seidel necesita menos memoria para aplicar el método, sin embargo, hay

que obtener la solución del sistema completo, pues no se puede obtener cualquier incógnita por separado, mientras que el método de Jacobi si permite esta acción, aunque requiere más memoria.

Podemos observar que x aún existe a la derecha de la ecuación, por lo cual necesitaremos una propuesta de

x 0 ( semilla) .

Por otra parte, si la matriz A es definida positiva, se sabe que el método de Gauss-Seidel converge, pero el método de Jacobi necesita, además, que 2D-A sea también definida positiva, pues si no es así, no se asegura nada.

METODOLOGÍA DESARROLLO

Y

PROCESOS

DE

Si los elementos diagonales de A son todos distintos de cero, podemos escribir: 1.

Ax = b

2.

A=D −L−U

PROGRAMACIÓN DEL MÉTODO

Sustituyendo A, 2 en 1.

( D−L−U ) x=b

( D− (L+U )) x=b Dx−(L+U )¿ x= b Dx=b+ ( L+U ) x Despejando x −1 −1 x=D b+ D ( L+U ) x

Donde D es la matriz diagonal que contiene los elementos diagonales de A, [2]

(

) )

0 ⋯ 0 0 −a21 ⋱ ⋮ ⋮ L= ⋮ ⋱ 0 ⋮ −an 1 ⋯ −a n, n−1 0

(

0 U= ⋮ ⋮ 0

y

La ecuación Ax = b , o transforma entonces

y, si existe entonces

−1

D

−a12 0 −a1 n ⋱ ⋱ ⋮ ⋱ ⋱ −a n−1, n ⋯ ⋯ 0

( D−L−U ) x=b

se

−1 Dx= ( L+U ) x +D b (es decir, aii ≠ 0 para todoi ¿

,

x=D−1 b+D −1 ( L+U ) x Donde se obtiene la expresión matricial del método iterativo de Jacobi:

x k+1=D −1 b+ D −1( L+U ) x k Donde k+1 es la iteración actual, y k la anterior.

1 11 0 00 33 3 011 −1 D (L+U )= 0 1 0 ¿ 10 −1 = ¿ 1 0− 1 3 3 3 ¿−2−1 0 1 1 1 ¿− − 0 00 2 4 4

(

)

() ( ) ( ) ( ) ( )( )

Matriz de resultados

EJEMPLO Y RESULTADOS EJEMPLO PRACTICO DEL METODO DE JACOBI Sistema de ecuaciones.

x k+1 y k +1 z k+ 1

1 1 0 1 3 3 3 = ¿ 1 + ¿ 1 0− 1 3 3 7 ¿ 1 1 4 ¿− − 0 2 4

1 1 1 x k x k+1= 3 + 3 y k + 3 z k ¿ 1 1 y k = y k+1=1+ x k − z k 3 3 ¿ 1 1 7 z k z k+1= − x k − y k 4 2 4

3 x− y−z=1 −x+3 y + z =3 2 x + y + 4 z=7 Matriz de la forma Ax = b pasa a ser de la forma Algunas iteraciones A= D – L– U

x 0=0

;

Formula de la iteración.

x

k+1

−1 −1 =D b+ D ( L+U ) x b

y 0=0 ;

Entonces:

¿ 300 ¿030 ¿004 ¿ ( D )=¿

;

¿ 000 ¿1 0 0 ¿−2−1 0 ¿ ( L )=¿

;

¿ 01 1 ¿ 0 0− 1 ¿000 ¿ ( U ) =¿

Se realizan las siguientes operaciones para obtener la matriz de incógnitas

3 ¿

( )( ) ( )

1 00 3 1 1 1 −1 1 D b= 0 0 ¿ 3 = ¿ 7 3 ¿ ¿7 4 1 00 4

z 0=0

1 1 1 x 1= + (0)+ (0) = 3 3 3

1 3

1 1 y 1=1+ (0)− ( 0)=1 3 3 7 1 1 7 z 1= − ( 0 )− ( 0 ) = 4 4 4 2

;

()

1 1 1 7 x 2= + (1 )+ =1.25 3 3 3 4 y 2=1+

() ( )

1 1 1 7 =0.527777 − 3 3 3 4

()

7 1 z 2= − 1 1 − (1 )=1.3333333 4 2 3 4

1 1 1 x 3= + (0.527777 )+ ( 1.33333 )=0.9537037 3 3 3 1 1 y 3=1+ (1.25 ) − ( 1.33333 )=0.972222 3 3

7 1 z 3= − 1 ( 1.25 )− (0.527777 ) =0.99930 2 4 4

A partir de esta iteración todos los resultados tiende a aproximarse a 1, pero es hasta la iteración k=18 donde los 3 resultados de las respectivas incógnitas toman el valor de 1.

CONCLUSIONES El método de Jacobi es útil para resolver sistemas de ecuaciones lineales en el que una matriz inversa es muy complicada de resolver, debido a que resuelve una matriz inversa diagonal. La matriz coeficiente (A) se descompone en 3 matrices; diagonal inversa (D1 ), triangular superior (U) y triangular inferior (L). Para encontrar la primera aproximación se requiere de un semillero, que es introducida por el usuario o que por default es un vector 0 (xk) y se realiza el cálculo según el método de jacobi. El límite de las iteraciones es precisamente la solución del sistema, el cual, que como se relaciona con el método del punto fijo, éste puede parar con una estimación de error en dos iteraciones consecuentes y comparándola con un error máximo que el usuario puede o no introducir, y, tener una mejor aproximación lo cual conlleva un mayor número de iteraciones. [4] Para que el método sea efectivo debe converger, lo cual lo hace si la matriz A es estrictamente diagonal dominante, aunque puede converger, aunque no se satisfaga esta condición. otra condición del método es que no se puede realizar si la matriz diagonal tiene algún coeficiente nulo. Este método es muy similar al Gauss-Seidel con la diferencia más significativa en el que al calcular xi(k+1) se requieren todos los

elementos de xi(k) por lo que no es posible sobrescribir xi(k) con xi(k+1) por lo que aumenta la cantidad de almacenamiento de dos vectores, para realizar la siguiente iteración (y realiza mayores iteraciones). [5] Con el enunciado anterior afirmamos que la convergencia ocurre más rápido con el método de gauss-seidel pero casos muy especiales ocurre lo contrario, y en términos de eficiencia computacional esto puede ser beneficioso porque es perfectamente diseñado para una computación paralela porque cada iteración utiliza nuevas variables, al contrario que gauss-seidel. [3] El método de jacobi no se puede utilizar si la matriz tiene algún coeficiente nulo en la diagonal.

REFERENCIAS [1] Ezquerro Fernández, J. A. (10, 15, 2020). Iniciación a los métodos numéricos. Obtenido de: https://dialnet.unirioja.es/descarga/libro/489813.pdf [2] Orduño Ahumada (J.P), Vargas Victoria (L.). (10, 15, 2020). Métodos Numéricos: Portafolio. Obtenido de: https://metodosjl.wordpress.com/ [3] King H. Yang (2018) Stepping Through Finite Element Analysis Obtenido de: https://doi.org/10.1016/B978-0-12-809831-8.00007-6 [4] Método de Jacobi. En wikipedia. (10, 19, 2020) Obtenido de https://es.wikipedia.org/wiki/M%C3%A9todo_de_Jacobi [5] Camins OpenCourseWare (10, 19, 2020) Obtenido de: https://portal.camins.upc.edu/materials_guia/250133/2011/iterativos_ v1.pdf...