Sistemas de Ecuaciones Lineales V
´ ´ • Metodos Iterativos: Matrices dispersas. Esquema general. Metodos de Jacobi y de Gauss-Seidel.

521230

-1-

´ DIM – Universidad de Concepcion

Matrices dispersas
´ • Cuando la matriz A del sistema a resolver es dispersa, pero no banda, los metodos ´ (directos) estudiados hasta ahora (eliminacion de Gauss o Cholesky) presentan el defecto denominado llenado (fill-in). ´ • El llenado consiste en que, a medida que el proceso de eliminacion avanza, se van creando elementos no nulos en posiciones de L y U en donde la matriz A tiene ceros.

• Como consecuencia del llenado se tiene, por una parte, el aumento del numero de flop y ´ con ello el aumento del error de redondeo. Por otra parte se tiene …ver más…

6

5

4

3

Luego, si

1 M > 2 , puede ser incorrecto

2

´ detener el proceso cuando solo se tiene

1

0

x

(k+1)

−x

(k)

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

≤ tol.

521230

-9-

´ DIM – Universidad de Concepcion

´ Criterio de detencion (cont.)
´ • El criterio de detencion implica calcular M , lo que en general es dif´cil. El siguiente ı lema indica una manera de estimar M .

• Lema. Para k = 1, 2, . . . se tiene: x(k+1) − x(k) mk := x(k) − x(k−1)
´ Demostracion.

≤ M .

x(k+1) − x(k) mk = x(k) − x(k−1) e(k+1) − e(k) = e(k) − e(k−1)

=

x(k+1) − x − x(k) − x x(k) − x − x(k−1) − x ≤ y∈Rn : y=0

M e(k) − e(k−1) = e(k) − e(k−1)

max

My = M . y

´ ´ • En el criterio de detencion puede utilizarse mk como una estimacion de M . ´ En tal caso, el proceso iterativo se detendra cuando:

mk x(k+1) − x(k) ≤ tol. 1 − mk
521230 - 10 ´ DIM – Universidad de Concepcion

´ Descomposicion de una matriz
• Se considera resolver un sistema Ax = b con aii = 0, para i = 1, . . . , n.
Sea x
(0) t

=

(0) (0) x1 , . . . , xn

arbitrario y escribamos la matriz A en la forma

A = D − E − F, donde D

= diag(A), −E y −F son:    A= 

..

.

D −E

−F    
.. .



• Notemos que tanto D como D − E son matrices invertibles, ya que aii = 0 para i = 1, . . . , n.

521230

- 11 -

´ DIM – Universidad de Concepcion

´ Metodo de Jacobi
´ • El metodo de