El Sol

Parte 4. M´todos iterativos para la
e
resoluci´n de sistemas de ecuaciones
o
lineales
Gustavo Montero

Escuela T´cnica Superior de Ingenieros Industriales
e
Universidad de Las Palmas de Gran Canaria
Curso 2006-2007

Generalidades de los m´todos iterativos
e
Metodo de Jacobi
M´todo de Gauss-Seidel
e
M´todo de Relajaci´n Sucesiva
e
o
Convergencia de los m´todos
e
ResumenGeneralidades de los m´todos iterativos
e
Metodo de Jacobi
M´todo de Gauss-Seidel
e
M´todo de Relajaci´n Sucesiva
e
o
Convergencia de los m´todos
e
Resumen

Introducci´n
o
Ventaja frente a los m´todos directos
e
Son menos sensibles a los errores de blackondeo y esto se aprecia en sistemas de orden elevado donde los errores de
blackondeo de los m´todos directos son considerablese

Definici´n de m´todo iterativo
o
e
Un m´todo iterativo construye una sucesi´n de vectores xm tal que
e
o
lim

m→∞

xm = x

siendo x la soluci´n del sistema Ax = b .
o

Construcci´n de un m´todo iterativo
o
e
Se parte de una aproximaci´n inicial x0 y luego se calcula
o
xm+1 = F (xm ),

m = 0 , 1, . . .

donde F se toma de forma lineal: F (x ) = B x + c
xm+1 = B xm + c ,m = 0 , 1, . . .

La matriz B se denomina matriz de iteraci´n y de sus propiedades va a depender la convergencia del m´todo.
o
e

Definici´n de convergencia
o
Definici´n de convergencia
o
Un m´todo se dice que es convergente si:
e
lim

m→∞

xm = x = A

−1

b

Teorema del Punto Fijo
Aplicando el Teorema del Punto Fijo,
||F (x ) − F (x )|| ≤ L||x − x ||
es decir,
||Bx −Bx || ≤ L||x − x ||
Luego si v = x − x

=
⇒

||Bv || ≤ L||v ||

Teorema general para la convergencia de los m´todos
e
iterativos
Un m´todo iterativo del tipo anterior es convergente si y s´lo si se cumplen simult´neamente las siguientes
e
o
a
condiciones,
c = ( I − B )A − 1 b
ρ( B ) < 1

Construcci´n de m´todos iterativos
o
e
Sea A = M − N , con M invertible
Teorema decaracterizaci´n de m´todos iterativos
o
e
Si se toma,
B
c

=

M

=

M

−1
−1

N
b

el m´todo considerado cumple la primera condici´n anterior.
e
o
Pero adem´s se debe cumplir la segunda condici´n,
a
o
ρ( M

−1

N) < 1

||M

o tambi´n
e

−1

N || < 1

Teorema de construcci´n de los m´todos iterativos
o
e
Todo m´todo del tipo estudiado verifica las condicionesdel teorema anterior con M − N = A y M invertible.
e
El m´todo resulta,
e
xm+1 = M

−1

Nxm + M

−1

b

es decir,
Mxm+1 = Nxm + b
Por tanto, conviene elegir M tal que sea f´cilmente invertible (diagonal o triangular).
a
El n´mero de operaciones de los m´todos iterativos es O (n2 ) × no iter
u
e

Generalidades de los m´todos iterativos
e
Metodo de Jacobi
M´todo deGauss-Seidel
e
M´todo de Relajaci´n Sucesiva
e
o
Convergencia de los m´todos
e
Resumen

Algoritmo de Jacobi
Matriz de iteraci´n de Jacobi
o
Descomposici´n suma de una matriz
o

La matriz de iteraci´n de Jacobi resulta,
o
Sea A = D − L − U , con

0

0
B −a21
B
B −a31
L=B
B
.
B
.
@
.
−an1

Algoritmo

···
0
−a32
.
.
.
−an2

a
0 − 12
0
aa
11
B
B
a21 B 011B
B
B −D = B 0
.
a
B
.
a22 B a
B
B − 31 @ − . 32
B
a33
a33
0
B
B
.
.
B
. ···
.0
·B·
·
B
.
.
an0
an 1 · ·
·@·
·
·
2
−
−
0
·
0
ann · ·
ann
.
.
..
.
.
.
.
.
···
−ann−1
0
0

a13
−
0 a · · · · · ·0
11
a22 a23· · ·
0
−
···
. a22 .
.
.
..
.
.0
···.
0
···
ann
1.
0. .
.
.0
.
C an 3 B 0
C−
B··
·
Ca
B
nn
C; U = B .
C
B.
CB.
A
@ ···
0

1
a
1 1n
−
a11 C
Ca2n C
C
C
−
C
Ca;
Ca22 C
A 3n C
C
−
a33 C
C
C
.
C
.
−a12 C −a13
C
.
0 A −a23
0
.
..
.
.
.
···
···
···
···

El m´todo de Jacobi consiste en elegir M = D y N = L + U , resultando en forma matricial,
e
Dxm+1 = (L + U )xm + b
es decir,

aii (xm+1 )i = −

n
X
j =1
j =i

aij (xm )j + bi ;

i = 1 , 2, . . . , n

···...