práctica 4-5 métodos directos e iterativos para sistemas de ecuaciones lineales
Post on 23-Jan-2016
226 Views
Preview:
TRANSCRIPT
Práctica 4-5Práctica 4-5
Métodos Directos e Métodos Directos e Iterativos para Sistemas de Iterativos para Sistemas de
Ecuaciones LinealesEcuaciones Lineales
Sistemas de Ecuaciones Sistemas de Ecuaciones LinealesLineales
La Ecuación del CalorLa Ecuación del Calor
Métodos directosMétodos directosMétodo de Eliminación de Gauss Método de Eliminación de Gauss
Métodos iterativosMétodos iterativosMétodo de JacobiMétodo de Jacobi
Método de Gauss-SeidelMétodo de Gauss-Seidel
Método de SobrerrelajaciónMétodo de Sobrerrelajación
Ecuación del CalorEcuación del Calor
Modelo Modelo matemáticomatemático
Matriz asociadaMatriz asociada
)/2T(TT
)/2T(TT
)/2T(TT
)/2T(TT
1n+1-nn
423
312
201
)/2T(TT
)/2T(TT
)/2T(TT
)/2T(TT
1n+1-nn
423
312
201
21-
1-
21-
1-21-
1-2
21-
1-
21-
1-21-
1-2
T0 T1 T2 . . . Tn Tn+1T0 T1 T2 . . . Tn Tn+1
Teorema de Rouché-Teorema de Rouché-FrobeniusFrobeniusTeorema de Rouché-Teorema de Rouché-FrobeniusFrobenius
El sistema AEl sistema Amnmnx = b es x = b es compatiblecompatible si y sólo si si y sólo si
rango(A) = rango(A|b)rango(A) = rango(A|b)
Un sistema compatible es Un sistema compatible es determinadodeterminado sii sii
rango(A) = nrango(A) = n
Un sistema compatible Un sistema compatible indeterminadoindeterminado tiene tiene
n – rango(A) n – rango(A) variables libresvariables libres
SoluciónSolución x xcc = x = xpp + núcleo(A) + núcleo(A)
Eliminación de GaussEliminación de GaussOperaciones elementalesOperaciones elementalesEliminación de GaussEliminación de GaussOperaciones elementalesOperaciones elementales
Eliminar fila Eliminar fila ii tomando la fila tomando la fila k k como pivote como pivote llikik = a = aik ik / a/ akk kk , a, aijij = a = aijij l likik * a * akjkj
A(i,:) = A(i,:) - L(i,k)*A(k,:);A(i,:) = A(i,:) - L(i,k)*A(k,:);
Escalar fila Escalar fila ii dividiéndola por el pivote dividiéndola por el pivote aaiiii
aaijij = a = aij ij / a/ aiiii
A(i,:) = A(i,:)/A(i,i);A(i,:) = A(i,:)/A(i,i);
Permutar las filas Permutar las filas ii y y kk aaikik a akiki
A([i,k],:) = A([k,i],:);A([i,k],:) = A([k,i],:);
Sistema inicialSistema inicial
TriangularizaciónTriangularización
Sustitución regresivaSustitución regresiva
Fases de la eliminaciónFases de la eliminaciónFases de la eliminaciónFases de la eliminación
Ax = bAx = b
Ux = cUx = c
x = Ax = A–1–1bb
Temperatura en una barraTemperatura en una barra
NodosNodosn = 4n = 4
Condiciones Condiciones
de contornode contornoTT00=20=20
TT55=70=70
Sistema linealSistema lineal
)/207(TT
)/2T(TT
)/2T(TT
)/2T(20T
34
423
312
21
)/207(TT
)/2T(TT
)/2T(TT
)/2T(20T
34
423
312
21
20 T1 T2 T3 T4 7020 T1 T2 T3 T4 70
Resolución del sistemaResolución del sistema
70
0
0
20
T
T
T
T
2100
1210
0121
0012
4
3
2
1
70
0
0
20
T
T
T
T
2100
1210
0121
0012
4
3
2
1
Eliminación en sistemas Eliminación en sistemas lineales tridiagonales lineales tridiagonales Ax = bAx = b
n = length(b);n = length(b);
M = [A,b];M = [A,b];
for i=1:n-1for i=1:n-1
M(i,:) = M(i,:)/M(i,i);M(i,:) = M(i,:)/M(i,i);
M(i+1,:) = M(i+1,:)-M(i+1,:) = M(i+1,:)-
M(i+1,i)*M(i,:);M(i+1,i)*M(i,:);
endend
M(n,:) = M(n,:)/M(n,n);M(n,:) = M(n,:)/M(n,n);
Eliminación en sistemas Eliminación en sistemas lineales tridiagonales lineales tridiagonales Ax = bAx = b
for i = n-1:-1:1for i = n-1:-1:1
M(i,:) = M(i,:)-M(i,:) = M(i,:)-M(i,i+1)*M(i+1,:);M(i,i+1)*M(i+1,:);
endend
x = M(:,n+1);x = M(:,n+1);
Limitaciones de los Métodos Limitaciones de los Métodos DirectosDirectos
Acumulación del error de redondeoAcumulación del error de redondeo Coste de la eliminación: O(nCoste de la eliminación: O(n33))
Sensibilidad al error de redondeoSensibilidad al error de redondeo Sistemas mal o bien condicionadosSistemas mal o bien condicionados Número de condiciónNúmero de condición
Estrategia de Pivotación ParcialEstrategia de Pivotación ParcialLlenado de la matrizLlenado de la matriz
Matrices dispersasMatrices dispersas
Número de condición de una Número de condición de una matriz matriz Número de condición de una Número de condición de una matriz matriz
condcond mide el mal condicionamiento mide el mal condicionamiento cond(eye(n))=1 cond(eye(n))=1
cond(matsingular) = infcond(matsingular) = inf
rcondrcond mide el buen condicionamiento mide el buen condicionamiento rcond(eye(n))=1rcond(eye(n))=1
rcond(matsingular) = 0rcond(matsingular) = 0
rcondrcond y y detdet
Pivotación parcialPivotación parcialPivotación parcialPivotación parcial
Un algoritmo deficiente puede arruinar Un algoritmo deficiente puede arruinar
un sistema bien condicionado.un sistema bien condicionado.
Estrategia:Estrategia: Elegir como pivote el Elegir como pivote el
elemento de mayor valor absoluto del elemento de mayor valor absoluto del
resto de la columna.resto de la columna.
El operador El operador \\ para resolver Ax = b para resolver Ax = b
Métodos Iterativos para Métodos Iterativos para
Sistemas de Ecuaciones Sistemas de Ecuaciones
LinealesLineales
Métodos directos frente a Métodos directos frente a métodos iterativosmétodos iterativos
DIRECTOSDIRECTOS
Ax =bAx =b
x = A\x = A\ bb
Tamaño moderadoTamaño moderado
Producen llenado Producen llenado
Error de redondeoError de redondeo
ITERATIVOSITERATIVOS
Mx = (MMx = (MA)x + bA)x + b
MxMx(k+1)(k+1) = (M = (MA) xA) x(k)(k) + b + b
Tamaño grandeTamaño grande
Conservan los cerosConservan los ceros
Error de truncamientoError de truncamiento
Convergencia y número de Convergencia y número de operacionesoperaciones
Coste (para matrices densas)Coste (para matrices densas) Directos: nDirectos: n33 Iterativos: k.n Iterativos: k.n22
Convergencia Convergencia Criterio de paradaCriterio de parada
iter < maxiteriter < maxiter
inf...,,2,1ptol;xxp
(k))1(k+ inf...,,2,1ptol;xxp
(k))1(k+
Ecuación del Calor en un Ecuación del Calor en un rectángulorectángulo
TTCC = (T = (TWW + T + TNN + T + TSS + T + TEE)/4)/4
CC
NN
EEWW
SS
–1–1
–1–1
–1–1
44 –1–1
MoléculaMolécula
Generación de la matriz Generación de la matriz con MATLABcon MATLAB
function A = calor2D(n,m)function A = calor2D(n,m)
p = n*m;p = n*m;
v = ones(1,p-1);v = ones(1,p-1);
for k = n:n:p-n, v(k) = 0; endfor k = n:n:p-n, v(k) = 0; end
w = ones(1,p-n);w = ones(1,p-n);
A = 4*eye(p)...A = 4*eye(p)...
- diag(v,1) - diag(v,-1)... - diag(v,1) - diag(v,-1)... - diag(w,n) - diag(w,-n); - diag(w,n) - diag(w,-n);
Un lado calienteUn lado caliente
12
34
56
12
34
5
0
20
40
60
80
El método de JacobiEl método de Jacobi
Sistema de ecuaciones linealesSistema de ecuaciones lineales
a x
a x
a x
a x
a x a x a x
a x a x a x
a x a x a x
a x a x a x
b
b
b
b
11 1
21 1
31 1
n1 n
12 2 13 3 1n n
22 2 23 3 2n n
32 2 33 3 3n n
n2 2 n3 3 nn n
1
2
3
n
a x
a x
a x
a x
a x a x a x
a x a x a x
a x a x a x
a x a x a x
b
b
b
b
11 1
21 1
31 1
n1 n
12 2 13 3 1n n
22 2 23 3 2n n
32 2 33 3 3n n
n2 2 n3 3 nn n
1
2
3
n
Iteración de JacobiIteración de Jacobi
x (b
x (b
x (b
x (b
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
1(k+1)
1
2(k+1)
2
3(k+1)
3
n(k+1)
n
12 2(k)
13 3(k)
1n n(k)
11
21 1(k)
23 3(k)
2n n(k)
22
31 1(k)
32 2(k)
3n n(k)
33
n1 1(k)
n2 2(k)
n,n 1 n 1(k)
nn
x (b
x (b
x (b
x (b
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
1(k+1)
1
2(k+1)
2
3(k+1)
3
n(k+1)
n
12 2(k)
13 3(k)
1n n(k)
11
21 1(k)
23 3(k)
2n n(k)
22
31 1(k)
32 2(k)
3n n(k)
33
n1 1(k)
n2 2(k)
n,n 1 n 1(k)
nn
A = L + D + UA = L + D + UM = D, N = – (L + U)M = D, N = – (L + U)Mx = Nx + bMx = Nx + b
Expresión matricialExpresión matricial
»M = diag(diag(A))M = diag(diag(A))
»N = M-AN = M-A
»x = M\(Nxx = M\(Nx00+b)+b)
Algoritmo de JacobiAlgoritmo de Jacobi
DatosDatos Sistema lineal:Sistema lineal: Ax = bAx = b Estimación inicial: Estimación inicial: xx00
Proceso: mientras no converja, repetirProceso: mientras no converja, repetir Nueva estimación: Nueva estimación: x = Dx = D–1–1((D – A)x((D – A)x0 0 + b)+ b)
Incremento:Incremento: norm(x – xnorm(x – x00))
Actualizar:Actualizar: xx00 = x = x
ResultadoResultado Estimación final:Estimación final: xx
Iteración de Gauss-SeidelIteración de Gauss-Seidel
x (b
x (b
x (b
x (b
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
1(k+1)
1
2(k+1)
2
3(k+1)
3
n(k+1)
n
12 2(k)
13 3(k)
1n n(k)
11
21 1(k+1)
23 3(k)
2n n(k)
22
31 1(k+1)
32 2(k+1)
3n n(k)
33
n1 1(k+1)
n2 2(k+1)
n,n 1 n 1(k+1)
nn
x (b
x (b
x (b
x (b
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
a x a x a x ) / a
1(k+1)
1
2(k+1)
2
3(k+1)
3
n(k+1)
n
12 2(k)
13 3(k)
1n n(k)
11
21 1(k+1)
23 3(k)
2n n(k)
22
31 1(k+1)
32 2(k+1)
3n n(k)
33
n1 1(k+1)
n2 2(k+1)
n,n 1 n 1(k+1)
nn
A = L + D + UA = L + D + U M = L + D, N = –UM = L + D, N = –U Mx = Nx + bMx = Nx + b
Expresión matricialExpresión matricial
»M = tril(A)M = tril(A)
»N = M - AN = M - A
»x = M\(N*xx = M\(N*x0 0 + b)+ b)
Gauss-SeidelGauss-Seidel
SobrerrelajaciónSobrerrelajación
Método de sobrerrelajaciónMétodo de sobrerrelajación
xik
zi xik+1
ik+1x
i(k)i
1)+(ki zxx ˆ i
(k)i
1)+(ki zxx ˆ
1)(ki
(k)i
1)+(ki x)x(1x ˆ 1)(k
i(k)i
1)+(ki x)x(1x ˆ
i(k)i
1)+(ki zxx i
(k)i
1)+(ki zxx
( L D)x (1 )Dx (b Ux(k+1) (k) (k) )( L D)x (1 )Dx (b Ux(k+1) (k) (k) )
( L D)x b ((1 )D U)x(k+1) (k) ( L D)x b ((1 )D U)x(k+1) (k)
bU)xD1
()xD
(L (k)1)+(k
bU)xD1
()xD
(L (k)1)+(k
Expresión matricialExpresión matricial
Algoritmo de sobrerrelajaciónAlgoritmo de sobrerrelajación
»D = diag(diag(A)) D = diag(diag(A))
»L = tril(A,-1)L = tril(A,-1)
»M = L + D/M = L + D/
»N = M - AN = M - A
»x = M\(N*xx = M\(N*x0 0 + b)+ b)
Condiciones de convergenciaCondiciones de convergencia
Para que un método iterativo converja, la matriz Para que un método iterativo converja, la matriz ha de cumplir ciertas condiciones.ha de cumplir ciertas condiciones.
El coste por iteración es O(nEl coste por iteración es O(n22) o menor si se ) o menor si se aprovecha la dispersidad.aprovecha la dispersidad.
Se espera que converjan en menos de n pasos.Se espera que converjan en menos de n pasos.
Los métodos iterativos se aplican a matrices Los métodos iterativos se aplican a matrices grandes y dispersas.grandes y dispersas.
top related