Universidad Tecnica Federico Santa MarıaDepartamento de Matematica

Tarea 3 MAT270

2do Semestre 2014

Sistemas de Ecuaciones Lineales, metodos iterativos

Profesor: Sergio RojasAyudante: Nicolas Medina Poblete

Fecha de entrega: Viernes 12 de Septiembre de 2014.

Nombre: Camilo Figueroa Olivera.

Rol: 201011518-6

1. Considerar el siguiente sistema: 10 −2 53 4 07 8 −17

xyz

=

4−26

a) ¿Que metodos son convergentes y por que?

b) Resolver el sistema por el o los metodos convergentes, para un error absoluto de a lo mas un 10%.Considere un vector semilla de (0, 0, 0)T

Solucion:

a) Primeramente se debe probar que la matriz A es diagonal dominante, esto quiere decir que el valorabsoluto del elemento de la diagonal de esa fila es estrictamente mayor que la suma de los valoresabsolutos del resto de elementos de esa fila:

|10| > | − 2|+ 5|

|4| > |3|+ |0|

| − 17| > |7|+ |8|

∴ La matriz A es diagonal dominante

Para el metodo de Jacobi basta con determinar si la matriz A es diagonal dominante o tambien si suradio espectral ρ es menor a 1:

ρ(Mj) < 1

con Mj = D−1(−L− U)

Para el metodo de Gauss-Seidel tambien basta con determinar si la matriz A es diagonal dominante o siA es simetrica y definida positiva.

Por lo tanto ambos metodos convergen y pueden resolver.

b) Metodo Jacobi: Se tiene que:

A =

10 −2 53 4 07 8 −17

b =

4−26

LATEX 1

Universidad Tecnica Federico Santa MarıaDepartamento de Matematica

Se tiene que A = (L+D + U)

(L+D + U)x = b

Dx = (−L− U)x+ b

x = D−1(−L− U)︸ ︷︷ ︸Mj

x+D−1 · b︸ ︷︷ ︸B

Xk+1 = MjXk + B

Luego:

L =

0 0 0

3 0 0

7 8 0

U =

0 −2 5

0 0 0

0 0 0

D =

10 0 0

0 4 0

0 0 −17

D−1 =

110 0 0

0 14 0

0 0 − 117

(−L− U) =

0 2 −5

−3 0 0

−7 −8 0

D−1(−L− U) =

0 1

5 −12

−34 0 0

717

817 0

= Mj

Como se tiene el vector semilla (0, 0, 0)T se puede calcular x1:

x1 = Mj · x0 + B B = D−1 · b x0 =

000

x1 = D−1 · b =

110 0 0

0 14 0

0 0 − 117

4−26

=

25

−12

− 617

Ahora es posible calcular el numero mınimo k de iteraciones para la cual es seguro obtener latolerancia requerida mediante:

(tol) =∥Mj∥k

1− ∥Mj∥∥x0 − x1∥

Se tiene que:

(tol) = 0, 1 ∥Mj∥ =15

17∥x0 − x1∥ = 0, 5

∴ k ≈ 29, 9 → k = 30

Ahora se debe comprobar que:

(tol) ≥ ∥Mj∥1− ∥Mj∥

∥xk+1 − xk∥

Por lo que se debe iterar hasta encontrar el error entre las iteraciones que satisfaga la ecuacionanterior mediante la siguiente relacion:

LATEX 2

Universidad Tecnica Federico Santa MarıaDepartamento de Matematica

Xk+1 = Mj · Xk + B

Luego las iteraciones quedan:k=0

X1 =

0,4−0,5

−0,352941

k=1

X2 =

0,476471−0,8

−0,423529

k=2

X3 =

0,451765−0,857353−0,533218

k=3

X4 =

0,495138−0,838824−0,570381

k=4

X5 =

0,517426−0,871354−0,543801

k=5

X6 =

0,49763−0,888069−0,549932

k=6

X7 =

0,497352−0,873222−0,56595

k=7

X8 =

0,50833−0,873014−0,559077

Se tiene que el error entre la iteracion 7 es de 0,0823 por lo que se cumple la igualdad, por lo tantola solucion adecuada para el problema es:

X8 =

0,50833−0,873014−0,559077

LATEX 3

Universidad Tecnica Federico Santa MarıaDepartamento de Matematica

Metodo Gauss-Seidel:Para este metodo se debe hacer el siguiente despeje:

Ax = b

(L+D + U)x = b

(L+D)x = −Ux+ b

x = (L+D)−1(−U)︸ ︷︷ ︸Mgs

x+ (L+D)−1︸ ︷︷ ︸B

·b

Xk+1 = MjXk + B

Luego:

(L+D) =

10 0 03 4 07 8 −17

Como la matriz (L+D) esta escalonada, mediante pivoteo se buscara la inversa:

10 0 0 1 0 0

3 4 0 0 1 0

7 8 -17 0 0 1

→

1 0 0 1

10 0 0

3 4 0 0 1 0

7 8 -17 0 0 1

→

1 0 0 1

10 0 0

0 4 0 - 310 1 0

7 8 -17 0 0 1

1 0 0 110 0 0

0 1 0 - 340

14 0

7 8 -17 0 0 1

→

1 0 0 1

10 0 0

0 1 0 - 340

14 0

0 8 -17 - 710 0 1

→

1 0 0 1

10 0 0

0 1 0 - 340

14 0

0 0 -17 - 110 -2 1

→

1 0 0 1

10 0 0

0 1 0 - 340

14 0

0 0 1 1170

217 - 1

17

∴ (L+D)−1 =

110 0 0

− 340

14 0

1170

217 − 1

17

Luego como se tiene el vector semilla (0, 0, 0)T se puede calcular x1:

x1 = Mgs · x0 + B B = (L+D)−1 · b x0 =

000

x1 = B = (L+D)−1 · b

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

110 0 0

− 340

14 0

1170

217 − 1

17

0 2 −50 0 00 0 0

LATEX 4

Universidad Tecnica Federico Santa MarıaDepartamento de Matematica

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

0 1

5 − 12

0 − 320

38

0 185 − 1

34

= Mgs

(L+D)−1b =

110 0 0

− 340

14 0

1170

217 − 1

17

4−26

=

25

−45

− 4885

= x1

De la misma manera que para el metodo jacobi, es posible calcular el numero mınimo k de iteracionespara la cual es seguro obtener la tolerancia requerida:

(tol) =∥Mj∥k

1− ∥Mj∥∥x0 − x1∥

Con:

(tol) = 0, 1 ∥Mgs∥ =7

10∥x0 − x1∥ = 0, 8

∴ k ≈ 9, 2 → k = 10

Al igual que para el otro metodo se debe comprobar que:

(tol) ≥ ∥Mgs∥1− ∥Mgs∥

∥xk+1 − xk∥

Por lo que se debe iterar hasta encontrar el error entre las iteraciones que satisfaga la ecuacionanterior mediante la siguiente relacion:

Xk+1 = Mgs · Xk + B

Luego las iteraciones quedan:k=0

X1 =

0,4−0,5

−0,352941

k=1

X2 =

0,522353−0,891765−0,557509

k=2

X3 =

0,500402−0,875301−0,5588

Se tiene que el error entre la iteracion 2 es de 0,051218 por lo que se cumple la igualdad, por lo tantola solucion adecuada para el problema es:

X3 =

0,500402−0,875301−0,5588

LATEX 5