Programación y Métodos Numéricos.
Héctor Andrés Granada Díaz
Universidad Nacional de Colombia - Sede Manizales
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 1 / 12
Contenido
1 Introducción
2 Construcción de métodos iterativos
Método de Jacobi
3 Resultados de convergencia
4 Método SOR
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 2 / 12
Contenido
1 Introducción
2 Construcción de métodos iterativos
Método de Jacobi
Método de Gauss - Seidel
3 Resultados de convergencia
4 Método SOR
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 2 / 12
Contenido
1 Introducción
2 Construcción de métodos iterativos
Método de Jacobi
Método de Gauss - Seidel
3 Resultados de convergencia
4 Método SOR
Criterios de convergencia
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 2 / 12
Introducción
Dada una matriz invertible de tamaño n n y un vector b 2 Rn la única
solución del sistema Ax = b es x = A 1 b, Buscaremos métodos
aproximados para la resolución del sistema que se basan esencialmente en
el producto matriz-vector. Un método iterativo obtiene una solución
aproximada de Ax = b construyendo una sucesión de vectores:
x 1, x 2, x 3, , xk
desde un vector inicial arbitrario x 0 .
Método iterativo convergente:
lim x k = x
k !∞
Vector error en cada iteración:
ek = x xk
Vector residuo en cada iteración:
rk = b Ax k
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 3 / 12
En consecuencia
lim x k = x () lim e k = 0 () lim rk = 0
k !∞ k !∞ k !∞
Los métodos iterativos más usados son los que construyen la solución de la
forma:
x k +1 = Tx k + c donde T 2 MR (n) y c 2 Rn
a partir de un x 0 2 Rn arbitrario.
Método consistente
1
x = Tx + c () c = (I T )A b
Teorema:
Un método se dice convergente si cumple
1 Que es consistente
2 ρ (T ) < 1
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 4 / 12
Construcción de metodos iterativos
Consideremos la descomposición
A=M N, con M regular
M es regular si es cuadrada y tiene inversa. El sistema Ax = b se puede
escribir de la forma
1 1
Mx = Nx + b, es decir x = M Nx + M b
Evidentemente,
1 1 1
T =M N y c=M b = (I T )A b
Lo que sugiere estudiar el método iterativo
x k +1 = Tx k + c
por lo que el método así construido es consistente con el sistema y para
que el método sea convergente es su…ciente que para alguna norma se
cumpla kT k < 1.
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 5 / 12
Teorema
Todo método iterativo convergente es de la forma
x k +1 = M 1
Nx k + M 1
b
con A = M N y M regular.
Velocidad media de convergencia en k iteraciones
1
k
R (T k ) = log10 T k
Velocidad asíntotica de convergencia
1
v= log10
ρ (T )
Cota de error:
kT k
xk x xk xk 1
1 kT k
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 6 / 12
Método de Jacobi
x k +1 = Jx k + c
0 a 12 a 1 (n 1 ) a 1n
0 a 11 a a 11
B a 21 a 2 (n11 1 ) a 2n
B a 22 0 a 22 a 22
B .. .. .. .. ..
J = D (L + U ) = B
1
B . . . . .
B a (n 1 )1 a (n 1 )2 a (n 1 )n
@ a (n 1 )(n 1 ) a (n 1 )(n 1 ) 0 a (n 1 )(n 1 )
a n1 a n2 a n (n 1 )
a nn a nn a nn 0
Siendo A regular, en caso en que aii = 0 se permutan las …las previamente.
1
c=D b
O bien en componentes
!
n
1
xik +1 =
aii ∑ aij xjk + bi ; i = 1, 2, ,n
j 6 =i
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 7 / 12
Método de Jacobi
x k +1 = (D L) 1
Ux k + (D L) 1
b = Gx k + c
Siendo A regular, en caso en que aii = 0 se permutan las …las previamente.
O bien en componentes
!
i 1 n
1
xik +1
=
aii ∑ aij xj
k +1
∑ aij xj + bi ; i = 1, 2, , n
k
j =1 j =i +1
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 8 / 12
Resultados de convergencia
Matrices estrictamente diagonal dominantes:
n
jaii j > ∑ jaij j para i = 1, 2, ,n
j =1 ; j 6 =i
Teorema:
Para estas matrices se cumple que el método de Gauss seidel y el de
Jacobi son convergentes y ρ(G ) K y ρ(J ) K , siendo
( )
n
jaij j
K = max ∑ ja j < 1
j =1,j 6=i ii
Matrices simétricas de…nidas positivas:
A simétrica y todos sus autovalores son estrictamente positivos.
Teorema
Si A es simétrica de…nida positiva y aii > 0, 8i, entonces, el método de
Gauss - Seidel converge
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 9 / 12
Convergencia de matrices tridiagonales
Matriz tridiagonal
Teorema
Para matrices tridiagonales, se tiene que ρ(G ) = ρ(J )2 y por tanto ambos
convergen o divergen, en el caso de ser convergente el de Gauss - Seidel
converge asintoticamente más rápido que el de Jacobi.
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 10 / 12
Método se SOR
El método de relajación se consigue haciendo
1 1 w
M= D L y N= D +U con w 6= 0
w w
La matriz de iteración es
1
1 1 1 w
Gw = M N= D L D +U
w w
con w = 1 es el caso de Gauss - Seidel.
En componentes se puede expresar de la forma
!
i 1 n
w
xik +1 =
aii
bi ∑ aij xjk +1 ∑ aij xjk + (1 w )xik ; i = 1, 2, ,n
j =1 j =i +1
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 11 / 12
Criterios de Convergencia del método SOR
Teorema (Kahan)
Si aii 6= 0 para todo i, entonces, ρ(Gw ) jw 1j
Teorema
Elmétodo puede converger si 0 < w < 2.
Teorema
Si A es estrictamente diagonal dominante entonces el método de SOR
converge.
Teorema (Ostrowski - Reich)
Si A es simétrica de…nida positiva con aii > 0 y 0 < w < 2, entonces, el
método SOR converge
Teorema
Si A es simétrica de…nida positiva y tridiagonal, entonces los métodos de
Jacobi, Gauss - Seidel y SOR convergen y el valor óptimo para el
parámetro w es:
2 2
wop = p = p
1 + 1 ρ (J )2 1 + 1 ρ (G )2
Héctor Granada (Universidad Nacional de Colombia
DEPARTAMENTO
- Sede Manizales)
DE MATEMATICAS Y ESTADISTICA 12 / 12