Metodos Num´ ericos´
Transcript of Metodos Num´ ericos´
ur-logo
Metodos Numericos
Miguel Angel Cano [email protected]
Universidad WienerSistema de Ecuaciones Lineales:Metodos Directos
Junio del 2013
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
Contenido
1 Introduccion
2 Sistema de Ecuaciones Lineales
3 Metodos DirectosSistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
4 Referencias
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Palabras clavesSistemas Lineales
La necesidad de resolver sistemas lineales aparece enuna gran cantidad de problemas cientıficos.Existen estimativas que de cuatro problemas desimulacion en matematica, tres se convierten en resolversistemas lineales.Un ejemplo es la solucion de ecuaciones diferenciales porelementos finitos y diferencias finitas.Existen dos clases de metodos para resolver sistemaslineales: metodos directos y iterativos.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Palabras clavesSistemas Lineales
Sistema LinealEl problema de resolver un sistema de ecuaciones linealesconsiste en encontrar x = (x1, x2, ..., xn) tal que
a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
...
an1x1 + a22x2 + ... + annxn = bn
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Palabras clavesSistemas Lineales
Expresion MatricialDefiniendo
A =
a11 a12 ... a1na21 a22 ... a2n... ... ... ...
an1 an2 ... ann.
, b =
b1b2...bn
el problema anterior es equivalente a:
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Palabras clavesSistemas Lineales
Expresion Matricial
encontrar el vector x ∈ Rn tal que:
Ax = b
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Palabras clavesSistemas Lineales
ObservaSi admitimos que A ∈ Rn×n es invertible, entonces la solucionsera
x∗ = A−1b.
Lamentablemente, tanto el saber si la matriz es invertible comotambien obtener la inversa de una matriz, son trabajoscomplicados del punto de vista computacional.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LURefinamiento de la SolucionCondicionamiento de la matriz y estimativa del errorSistemas In(sobre)-determinadosDescomposicion en valores singularesUso de Matlab en la solucion de sistemas lineales
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Sistemas Triangulares
Supongamos que tenemos un sistema donde n = 2. En estecaso: {
a11x1 + a12x2 = b1a22x2 = b2
donde a11 6= 0 y a22 6= 0, entonces:
x2 =b2
a22
x1 =1
a11(b1 − a12x2)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Supongamos que tenemos un sistema donde n = 3. En estecaso:
a11x1 + a12x2 + a13x3 = b1a22x2 + a23x3 = b2
a33x3 = b3
donde a11, a22, a33 6= 0 entonces:
x3 =b3
a33
x2 =1
a22(b2 − a23x3)
x1 =1
a11(b1 − a13x3 − a12x2)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
En general, consideremos el sistemaa11x1 + a12x2 ... + a1,n−1xn−1 +a1nxn = b1
0 + a22x2 ... + a2,n−1xn−1 +a2nxn = b2... ... ... ... ... ... ...0 0 0 0 0 an−1,n−1xn−1 +an−1,nxn = bn−10 0 0 0 0 0 annxn = bn
donde aii 6= 0 para todo i = 1, ..., n. Entonces:
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
xn =bn
ann
xn−1 =1
an−1,n−1
(bn−1 − an−1,nxn
)...
x2 =1
a22
(b2 − a2nxn − a2,n−1xn−1 − ...− a23x3
)x1 =
1a11
(b1 − a1nxn − a1,n−1xn−1 − ...− a13x3 − a12x2
)Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Algoritmo TriangularDados aij, j ≥ i , bi , 1 ≤ i , j ≤ n.
Hacer xn = bnann
suma = 0Para k = n − 1 : 1 hacer
suma = bkPara j = k + 1 : n hacer
suma = suma− akjxjFin (Para)xk = suma
akkFin(Para)
Fin(Para)Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
EjemploSea el problema
3x1 + 2x2 + 2x3 = 52x2 + 2x3 = 6
1x3 = 3
La solucion es:
x∗1 = −1/3, x∗2 = 0, x∗3 = 3
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
ComplejidadVemos directamente que el algoritmo envuelve:
1 n divisiones
2 Adiciones:n∑
j=1j = n(n−1)
2
3 Multiplicaciones:n∑
j=1j = n(n−1)
2
Ası la complejidad del numero total de operaciones realizadases
o(n2).
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Metodo de eliminacion Gausiana
Propiedad
Los metodos directos utilizados para resolver el sistemaAx = b no se altera si lo sometemos a una sucesion deoperaciones del tipo:
1 Multiplicacion de una ecuacion por una constante no nula.2 Suma del multiplo de una ecuacion con otra.3 Cambio de orden de las ecuaciones
Presentaremos el metodo de eliminacion Gausiana (Gaus,1777-1855)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Considere el sistema:a11 a12 a13 a14 b1a21 a22 a23 a24 b2a31 a32 a33 a34 b3a41 a42 a43 a44 b4.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Eliminacion de la primera columna:Supongamos que a11 6= 0.Trabajando en la segunda fila
(a11 a12 a13 a14 b1)×−a21a11
+
(a21 a22 a23 a24 b2)
0 a22 − (a21a11
)a12 a23 − (a21a11
)a13 a24 − (a21a11
)a14 b2 − (a21a11
)b1
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Trabajando en la tercera fila
(a11 a12 a13 a14 b1)×−a31a11
+
(a31 a32 a33 a34 b3)
0 a32 − (a31a11
)a12 a33 − (a31a11
)a13 a34 − (a31a11
)a14 b3 − (a31a11
)b1
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Trabajando en la cuarta fila
(a11 a12 a13 a14 b1)×−a41a11
+
(a41 a42 a43 a44 b4)
0 a42 − (a41a11
)a12 a43 − (a41a11
)a13 a44 − (a41a11
)a14 b4 − (a41a11
)b1
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Trabajando en la i−esima fila, i = 2, 3, 4.
(a11 a12 a13 a14 b1)×− ai1a11
+
(ai1 ai2 ai3 ai4 bi)
0 ai2 − ( ai1a11
)a12 ai3 − ( ai1a11
)a13 ai4 − (a41a11
)a14 bi − ( ai1a11
)b1
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Este proceso podemos expresarlo como:Para i = 2 hasta 4, hacer
Para j = 2 hasta 4a(2)
ij = aij − ( ai1a11
)a1jFin (Para)b(2)
i = bi − ( ai1a11
)b1.Fin (Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
En general:Para i = 2 hasta n, hacer
Para j = 2 hasta na(2)
ij = aij − ( ai1a11
)a1jFin (Para)b(2)
i = bi − ( ai1a11
)b1.Fin (Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
La matriz quedaa11 a12 a13 a14 b1
0 a(2)22 a(2)
23 a(2)24 b(2)
20 a(2)
32 a(2)33 a(2)
34 b(2)3
0 a(2)42 a(2)
43 a(2)44 b(2)
4 .
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Eliminacion de la segunda columna:Supongamos que a(2)
22 6= 0.Trabajando en la tercera fila
(0 a(2)22 a(2)
23 a(2)24 b(2)
2 )×− a32
a(2)22
+
(0 a(2)32 a(2)
33 a(2)34 b(2)
3 )
0 0 a(2)33 − (
a(2)32
a(2)22
)a(2)23 a(2)
34 − (a(2)
32
a(2)22
)a(2)24 b(2)
3 − (a(2)
32
a(2)22
)b(2)2
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
Trabajando en la cuarta fila:
(0 a(2)22 a(2)
23 a(2)24 b(2)
2 )×− a42
a(2)22
+
(0 a(2)42 a(2)
43 a(2)44 b(2)
4 )
0 0 a(2)43 − (
a(2)42
a(2)22
)a(2)23 a(2)
44 − (a(2)
42
a(2)22
)a(2)24 b(2)
4 − (a(2)
42
a(2)22
)b(2)2
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
En general:Para i = 3 hasta n, hacer
Para j = 3 hasta n
a(3)ij = a2
ij − (a(2)
i2
a(2)22
)a(2)2j
Fin (Para)
b(3)i = b(2)
i − (a(2)
i2
a(2)22
)b(2)2 .
Fin (Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
El sistema queda como:a11 a12 a13 a14 b1
0 a(2)22 a(2)
23 a(2)24 b(2)
20 0 a(3)
33 a(3)34 b(3)
30 0 a(3)
43 a(3)44 b(3)
4 .
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
En general, repitiendo el proceso obtendremos un sistema dela forma:
a11x1 + a12x2 ... + a1,n−1xn−1 +a1nxn = b1
0 + a(2)22 x2 ... + a(2)
2,n−1xn−1 +a2nxn = b(2)2
... ... ... ... ... ... ...
0 0 0 0 0 a(n−1)n−1,n−1xn−1 +a(n−1)
n−1,nxn = b(n−1)n−1
0 0 0 0 0 0 a(n)nn xn = b(n)
n
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Palabras clavesSistemas Lineales
ObservacionEn el proceso de eliminacion, los elementosa11, a(2)
22 , a(3)33 , ..., a(j)
jj que aparecen en la diagonal sonllamados pivots.Si en el proceso de eliminacion uno de los pivots se anula,debemos cambiar las filas (siempre escogiendo aquellasdebajo de la diagonal para no perder la eliminacionanterior).
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Algoritmo Eliminacion Gaussiana
Dados aij, bi , 1 ≤ i , j ≤ n.Para k = 1 : n − 1 hacer
encontrar i ≥ k tal que aik 6= 0Si aii = 0 para todo i ≥ k entonces A−1 no existeCambie la linea k con la linea iPara i = k + 1 : n hacer
m = mik = aikakk
bi = bi −mbkPara j = k + 1 : n hacer
aij = aij −makjFin (Para)
Fin(Para)Fin(Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Complejidad de la eliminacion de Gauss
Para cada valor j en el tercer bloque del algoritmo sonrealizadas dos operaciones: una multiplicacion y unaadicion. Ası en este lazo son necesarias:
n∑j=k+1
2 = 2(n − k).
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Complejidad de la eliminacion de Gauss
En el segundo bloque (el bloque en i) ademas de lasoperaciones contabilizadas anteriormente, para cad irealizamos una division, una multiplicacion y una resta.Ası el numero de operaciones sera:
n∑i=k+1
[3 + 2(n − k)] = [3 + 2(n − k)](n − k).
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Complejidad de la eliminacion de GaussMetodo de Gauss
Para obtener el numero total de operaciones realizamos lasuma en k , correspondiente al bloque externo delalgoritmo:
n−1∑k=1
3(n−k)+2(n−k)(n−k) = 3n−1∑k=1
(n−k)+2n−1∑k=1
(n−k)2.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Complejidad de la eliminacion de GaussMetodo de Gauss
Numero de operaciones aritmeticas (cont.)Obteniendo ası, la cantidad de operaciones
23
n3 +n2
2− 7
6n.
Observe que en los calculos anteriores usamos el resultado:
n−1∑k=1
k2 =(n − 1)n(2n − 1)
6
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Numero de operaciones aritmeticasMetodo de Gauss
Para obtener el numero total de operaciones en el metodode eliminacion gaussiana, necesitamos sumar el numerode operaciones necesarias para resolver el sistematriangular.Ası, la aplicacion del metodo de eliminacion de Gauss, elnumero de operaciones aritmeticas es:
23
n3 +n2
2− 7
6n + n2 =
23
n3 +32
n2 − 76
n.
Si n = 100 se necesitan 681550 operaciones aritmeticas.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
EjemploMetodo de Gauss
2x1 + 4x2 + 6x3 = 16
−1x2 + x3 = 12x1 + −x2 + 4x3 = 7
La solucion es:x∗1 = 0, x∗2 = 1, x∗3 = 2.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Estrategia de Pivoteamiento
Considere el sistema:{0.004x1 + 15.73x2 = 15.770.423x1 − 24.72x2 = −20.49
Trabajando con 4 dıgitos en la representacion de punto flotantey redondeando al despreciar el quinto dıgito, procedemos a laeliminacion Gaussina de x1 en la segunda ecuacion.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Estrategia de Pivoteamiento
Obtenemos que:m = 105.8{
0.004x1 + 15.73x2 = 15.77−1689x2 = −1688
De esta manera la solucion obtenida es:
x1 = 12.5; x2 = 0.9994.
Por otro lado, podemos verificar que la solucion es:
x∗1 = 10; x∗2 = 1.
ErrorR = 25%
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Estrategia de Pivoteamiento
Invirtiendo el orden de las filas en el sstema, tenemos{0.423x1 − 24.72x2 = −20.490.004x1 + 15.73x2 = 15.77
Trabajando de nuevo con cuatro dıgitos y eliminamos x1 en lasegunda fila tenemos: m = 0.956× 10−2, tenemos{
0.423x1 − 24.72x2 = −20.49−15.96x2 = 15.96
De esta manera la solucion obtenida es:
x1 = 10; x2 = 1
que es la solucion real.
Error = 0.Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Algoritmo Eliminacion Gaussiana con pivoteamiento
Para k = 1 : n − 1 hacerw = |akk |Para j = k : n hacer
Si |ajk | > w entonces w = |ajk | y r = jFin (Para)Cambiar las fılas k y rPara i = k + 1 : n hacer
m = mik = aikakk
bi = bi −mbkPara j = k + 1 : n hacer
aij = aij −makjFin (Para)
Fin(Para)Fin(Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Matriz de banda
Una matriz es dicha esparsa si la cantidad de ceros essuperior al numero de elementos no nulos.Si ademas de esparsa, la matriz tiene los elementos nonulos concentrados en torno de la diagonal, esta esllamada matriz de banda.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Matriz de banda
DefinicionUna matriz A = (aij) es una matriz de banda p + q + 1, siaij = 0, si i > j + q o i < j − p.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Matriz Tridiagonal
Si p = q = 1, la matriz de banda es llamada tridiagonal, i.e,
A =
d1 c1a2 d2 c2
... ... ...an−1 dn−1 cn−1
an dn
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Matriz Tridiagonal
Para resolver un sistema lineal con una matriz tridiagonal, i. e,
A =
d1 c1a2 d2 c2
... ... ...an−1 dn−1 cn−1
an dn
, b =
b1b2...bn
podemos usar cuatro vectores, una para la diagonal principal,dos para las diagonales secundarias y una para el terminoindependiente, como se muestra en el siguiente algoritmo:
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Algoritmo Sistema Tridiagonal
Dados vectores a, b, c, d
Para k = 1 : n − 1 hacerdk+1 = dk+1 − (
ak+1dk
)ck
bk+1 = bk+1 − (ak+1dk
)bk
xn = bndn
Para k = n − 1 : 1 hacerxk = (bk − ckxk+1)/dk
Fin(Para)Fin(Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Factorizacion LU
Supongamos queA = LU,
dondeL es una matriz triangular inferior con elementos de sudiagonal igual a 1, yU es una matriz triangular superior, entonces
Ax = b ⇐⇒ LUx = b
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Factorizacion LU
el cual permite obtener dos sistemas:Sistema 1: encontrar y tal que:
Ly = b
Sistema 2: encontrar x tal que:
Ux = y .
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Factorizacion LU
Conocidas L y U, el sistema sera resuelta en
2n2
operaciones aritmeticas (dos sistemas triangulares) lo querepresenta una ganancia substancial comparado con 2/3n3
operaciones del metodo de Gauss.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejercicio de Factorizacion LU
Estudiar el problema de la existencia de las matrices L y U.
Referencia: Matrix Computation, Golub-Van Loan, 1989.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Observaciones
1 Dada una matriz A, los factores L y U son unicos siexigimos que todos los elementos de la diagonal de L soniguales a 1.
2 Se pueden encontrar directamente los elementos de L y Ua partir de la definicion de producto de matrices,obteniendose un sistema de n2 ecuaciones y n2
incognitas, que sera resuelto progresivamente a partir delos valores anteriormente calculados.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
Considere la matriz:
A =
a11 a12 a13a21 a22 a23a31 a32 a33
Hallemos la factorizacion L y U.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
Considere la matriz:
LU =
1 0 0m21 1 0m31 m32 1
u11 u12 u130 u22 u230 0 u33
=
a11 a12 a13a21 a22 a23a31 a32 a33
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
u11 u12 u13m21u11 m21u12 + u22 m21u13 + u23m31u11 m31u12 + m32u22 m31u13 + m32u23 + u33
=
a11 a12 a13a21 a22 a23a31 a32 a33
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Formulacion
De esta manera, si llamamos mij los elementos de L y de uij loselementos de U, obtenemos:
mii = 1,∀i = 1, ..., n
uij = aij −i−1∑k=1
mikukj , para i ≤ j
mij =
aij −j−1∑k=1
mikukj
/ujj
Ası obtenemos el siguiente algoritmo:
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Algoritmo Factorizacion LU
Dado la matriz A = (aij)Para i = 1 : n hacer
Para j = i : n, hacer
uij = aij −i−1∑k=1
mikukj
Fin (Para)Para j = i + 1 : n, hacer
mji =
(aji −
i−1∑k=1
mjkuki
)/uii
Fin(Para)Fin(Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Observaciones
1 Se puede mostrar que los coeficientes mij calculados en elalgoritmo de eliminacion Gaussina forman la matriz L(desde que no se realice ningun cambio de fila) y que lamatriz triangular superior del metodo de eliminacionGaussiana es la propia matriz U.
2 En el caso de cambio de filas (pivoteamiento) en laeliminacion gaussiana tambien tendremos unafactorizacion triangular pero con LU = A′, donde A′ esobtenida con el cambio de filas de A, (ver Ruggiero-Lopes,1997).
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
Sea la matriz:
A =
1 +2 −12 +3 −21 −2 +1
, b =
230
Resolveremos el sistema Ax = b usando descomposicion L U.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
Calculando los mij y uij por el algoritmo presentado obtenemos:
L =
1 0 02 1 01 4 1
; U =
1 +2 −10 −1 00 0 2
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
Resolveremos el problema usando los sistemas:Sistema 1: encontrar y tal que:
Ly = b
Sistema 2: encontrar x tal que:
Ux = y .
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
Sistema 1:
L =
1 0 02 1 01 4 1
y1y2y3
=
230
obtenemos:
y1 = 2; y2 = −1; y3 = 2
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Ejemplo
Sistema 2: con estos valores calculamos x atraves del sistemaUx = y , i.e., 1 2 −1
0 −1 00 0 2
x1x2x3
=
2−12
obtenemos:
x1 = 1; x2 = 1; x3 = 1
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
En algunas aplicaciones, la matriz A es simetrica (A = AT ) ydefinida positiva (xT Ax > 0,∀x ∈ Rn, x 6= 0). En este caso, sepuede demostrar que la factorizacion triangular es:
A = LDLT ,
donde L es una matriz triangular inferior (con 1 en la diagonal)y D es una matriz diagonal. Esta es la descomposicion deCholesky, y el algoritmo es el siguiente:
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Algoritmo Factorizacion de Cholesky
Dado la matriz A = (aij), simetrica y definida positiva.Para j = 1 : n, hacer
dj = ajj −∑
dk ljk
Para i = j + 1 : n, hacer
lij =
(aij −
j−1∑k=1
dk lik ljk
)/dj
Fin(Para)Fin(Para)
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Sistemas TriangularesMetodo de eliminacion GausianaEstrategia de PivotiamientoMatrices TridiagonalesFactorizacion LUDescomposicion de Cholesky
Observaciones
La existencia de la descomposicion de Cholesky es unacondicion necesaria y suficiente para que una matriz seadefinida positiva. Ası, el algoritmo tambien puede ser usadopara verificar si una matriz simetrica es definida positiva.
Miguel Angel Cano Lengua [email protected] Metodos Numericos
ur-logo
IntroduccionSistema de Ecuaciones Lineales
Metodos DirectosReferencias
Referencias
1 R. L. Burden y J. D. Faires. Analisis Numerico. EditorialIberoamericana. Mexico 1995.
2 A. Nieves Hurtado y F. C. Domınguez S. MetodosNumericos aplicados a la Ingenierıa. Cıa EditorialContinental. Mexico, 1996.
3 S. Chapra y R. Canale. Metodos Numericos paraIngenieros, 5 Edicion, Mc Graw Hill, 2007.
4 David Kincaid y Ward Cheney. Analisis Numerico. LasMatematicas del Calculo Cientıfico. EditorialAddison-Wesley Iberoamericana, Mexico, 1994.
Miguel Angel Cano Lengua [email protected] Metodos Numericos