Source: http://docplayer.es/6840928-Tema-3-resolucion-de-sistemas-de-ecuaciones-lineales.html
Timestamp: 2017-12-13 11:48:21+00:00

Document:
Tema 3 Resolución de Sistemas de Ecuaciones Lineales - PDF
Download "Tema 3 Resolución de Sistemas de Ecuaciones Lineales"
Marcos Rivero Padilla
1 Tema Resolución de Sistemas de Ecuaciones Lineales Índice Introducción 2 Método de Gauss 2 Resolución de sistemas triangulares 22 Triangulación por el método de Gauss 2 Variante Gauss-Jordan 24 Comentarios al método de Gauss Inestabilidad del Método de Gauss y Estrategias de Pivote Pivote parcial 2 Pivote total 4 Condicionamiento de sistemas de ecuaciones lineales 5 Otros métodos directos 5 Factorización LU 52 Método de Cholesky 6 Métodos iterativos usuales 6 Método de Jacobi 62 Método de Gauss-Seidel 6 Método de relajación
2 Introducción El objetivo de este tema es la resolución de un sistema de n ecuaciones lineales con n incógnitas: a x + a 2 x a n x n = b, a 2 x + a 22 x a 2n x n = b 2, a n x + a n2 x a nn x n = b n, donde son conocidos la matriz de coecientes a a 2 a n a 2 a 22 a 2n A = a n a n2 a nn y el vector de términos independientes b b 2 b = b n En notación matricial, el sistema de ecuaciones lineales se escribe: Ax = b y se puede resolver por dos tipos de métodos: Métodos directos: son métodos que, en un número nito de operaciones, obtienen la solución exacta Métodos iterativos: son métodos que generan una sucesión de aproximaciones {x (m } que converge a la solución del sistema: x = A b Recordemos que el Método de Cramer para la resolución de un sistema de n con n incógnitas x,, x n consiste en calcular las incógnitas mediante la fórmula x i = det A i, i =,, n, det A 2
3 siendo A la matriz de coecientes y A i la matriz que resulta de sustituir la columna i-ésima de la matriz de coecientes por el vector de términos independientes Teniendo en cuenta que el coste de un proceso de cálculo se puede estimar mediante el número total de operaciones aritméticas necesarias, entonces el coste de un determinante de orden n es n!n y, por tanto, el coste del Método de Cramer es (n + n! A continuación aparece una tabla con el tiempo estimado para resolver con el método de Cramer un sistema de orden n, para distintos valores de n, con una máquina que realice unas 0 6 operaciones por segundo: Algunos costes del método de Cramer n Coste del Método de Cramer Tiempo (0 6 oper/s 5 600,6 milisegundos minutos 9 segundos 20, ,4 millones de años Por último, recordemos algunas deniciones sobre matrices A n n = (a ij se dice Ortogonal Simétrica si verica A T = A A T = A Diagonal si i j entonces a ij = 0 Tridiagonal si i j > entonces a ij = 0 Triangular superior si i > j entonces a ij = 0 Hessenberg superior si i > j + entonces a ij = 0 (SemiDenida positiva x t Ax( > 0, x 0 (EstrictamenteDiagonalmente dominante a ij (< a ii, i j i
4 2 El método de Gauss 2 Resolución de Sistemas Triangulares Sea Ux = b un sistema de ecuaciones lineales con solución única (det U 0 en el que la matriz de coecientes U n n es triangular superior Entonces las componentes de la solución se pueden calular mediante el método de sustitución regresiva, es decir, se despeja la última incógnita de la última ecuación, se sustituye en la penúltima ecuación; después se despeja de esta ecuación la penúltima incóngnita y se repite el proceso hacia arriba hasta calcular el valor de la primera incógnita Algoritmo del Método de Sustitución Regresiva x i = n b i u ij x j j=i+ u ii, i = n, n,, Ejemplo: Consideremos el sistema de ecuaciones lineales x + 2x 2 2x + 4x 4 = 5, x 2 5x x 4 = 0, 4x + x 4 =, 2x 4 = 6 Entonces, aplicando el método de sustitución regresiva se tiene: x 4 = 6 2 =, x = x 4 4 x 2 = 5x + x 4 = 2, = 2, x = 5 2x 2 + 2x 4x 4 = 7 4
5 22 Triangulación por el Método de Gauss Se trata de transformar el sistema de ecuaciones lineales Ax = b en otro equivalente Ux = c que sea triangular superior El método se realiza por etapas: ª etapa: Transformar a 2, a,, a n en ceros 2ª etapa: Transformar a (2 2,, a (2 n2 en ceros ª etapa: Transformar a ( 4,, a ( n en ceros etapa n-: Transformar a (n n,n en cero Las transformaciones en cero de cada etapa se relizarán mediante operaciones elementales: para transformar a (k ik en cero usado como pivote ik, se multiplica la ecuación número k por a(k y se le suma la ecuación a (k kk número i Para evitar pivotes nulos se permite permutar las ecuaciones desde la número k hasta la n Ejemplo: A continuación resolvemos por el método de Gauss el sistema de ecuaciones lineales cuya matriz ampliada es a (k kk ª etapa:
6 2ª etapa: ª etapa: Solución: El coste del método de Gauss (fase de triangulación es c(gauss n = 4n + n 2 7n 6 ( 2n = O Faltaría añadirle el coste de la sustitución regresiva En la siguiente tabla se calculan algunos costes y tiempos de triangulación con el método de Gauss en una máquina que realice 0 6 operaciones por segundo 6
7 Algunos costes con el método de Gauss n Coste del Método de Gauss Tiempo (0 6 oper/s microsegundos ,7 milisegundos ,5 milisegundos ,67 segundos millones minutos 2 Variante de Gauss-Jordan Se trata de transformar el sistema de ecuaciones lineales Ax = b en un sistema equivalente Dx = c, con D una matriz diagonal En cada etapa k se deben hacer cero las posiciones a (k k,, a(k k,k, a(k k+,k,, a(k nk, donde k =,, n (n etapas El coste del método de Gauss-Jordan es n + n 2 2n, a falta de añadir n divisiones para calcular las incógnitas 24 Comentarios al método de Gauss Aplicaciones del método de Gauss Resolución de sistemas de ecuaciones lineales con solución única (det A 0 Resolución de sistemas de ecuaciones lineales sin saber si det A 0 Discusión general de sistemas de ecuaciones lineales Resolución simultánea de sistemas de ecuaciones lineales Cálculo eciente de determinantes Cálculo eciente de inversas Inconvenientes del método de Gauss No adecuado para sistemas muy grandes (dispersos Inestable 7
8 Inestabilidad del Método de Gauss y Estrategia de Pivote Consideremos el sistema de ecuaciones lineales de matriz ampliada ( 0,000 cuya solución exacta es (,0000 0, Si aplicamos el método de Gauss con una máquina que admite solo decimales se tiene la siguiente triangulación: ( 0,000 y se obtiene como solución ( 0 Pivote parcial Pivote Parcial Se busca la ecuación i > k tal que a ik = máx k r n a rk y se permuta con la ecuación k ( 0,000 2 Efectuando un cambio de la ( 2 0,000 exacta ( 2 0 Pero ( 0,000 0,000 0,000 0,0002 (,0000 0,99990 ( pp ( pp 0 Pivote parcial con escalado: Igual que el pivote parcial, reescalando las ecuaciones antes del pivotaje para que máx a ( ij = máx a(2 2j = = máx a(n nj 8
9 2 Pivote total Se toma (i, j tal que a (k ij = máx a (k rs, k r n k s n y se permutan las ecuaciones i y k, y las incógnitas j y k 4 Condicionamiento de Sistemas de Ecuaciones Lineales Para entender el concepto de condicionamiento, consideremos el siguiente ejemplo de RS Wilson: Se trata del sistema de ecuaciones lineales cuya matriz ampliada y solución exacta son: solexacta mientras que si se produce una pequeña variación en los términos independentes (datos se produce una gran modicación en la solución (resultados: , 9, , , solexacta 2,6 4, ,9,, Esto indica que el método de resolución de sistemas de ecuaciones empleado (Gauss están mal condicionado 9
10 5 Otros métodos directos 5 Factorización LU Resolución de un sistema factorizado en LU Si A = LU, con L una matriz triangular inferior (low y U una matriz triangular superior (upper, entonces el sistema de ecuaciones lineales Ax = b se puede resover en dos fases: a Ly = b, b Ux = y, con un coste de 2n 2 operaciones Ejemplo: x = Aplicando el algoritmo de resolución de un sistema factorizado en LU, obtenemos = y = = x = 2 0 0
11 Algoritmo del la Factorización LU Para k =,, n, k l kk u kk = a kk l kr u rk ; r= k a ik l ir u rk r= l ik = u kk, i = k +,, n; k a kj l kr u rj r= u kj = l kk, j = k +,, n Coste general de la factorización: n 2 + n 2 Algunas variantes: 4n + 2n 6 = O( 2n, (a falta de añadir Variante de Doolittle: L tiene diagonal de Variante de Crout: U tiene diagonal de Factorización LU para matrices tridiagonales Si A = LU es tridiagonal (a ij = 0 si i j >, entonces L y U también lo son y, para k =,, n, l kk u kk = a kk l k,k u k,k ; l k+,k u k,k+ = a k+,k u kk ; = a k,k+ l kk Coste: 4n para factorizar y 2(n 2 para resolver
12 52 Método de Cholesky Se trata de un método de descomposiciçón LU en el caso en que la matriz A sea simétrica y denida positiva Basta con tomar U = L T y, por tanto, A = LL t Método de Cholesky Para k =,, n, k l kk = akk l 2 k,r ; r= k a i,k l ir l kr r= l i,k =, i = k +,, n l kk Coste: O( n Propiedades Sirve para saber si una matriz simétrica es denida postiva Es estable 2
13 6 Métodos iterativos usuales Consisten en descomponer la matriz de coecientes A en la forma A = D L U, donde D = diag(a, L es triangular inferior con l ij = a ij, para i > j, y U es triangular superior, con u ij = a ij, para i < j Suponemos que A y D son invertibles 6 Método de Jacobi De Ax = b se tiene que (D L Ux = b y, por tanto, Dx = (L+Ux+b Luego x = D (L + Ux + D b Teniendo en cuenta la anterior igualdad se deduce el siguiente método interativo x (m+ = B J x (m + c J, siendo 0 a 2 a n a a 2 0 a 2n B J = D (L + U = a 22 a 22, a n a n2 0 a nn a nn c J = D b = b a b 2 a 22 b n a nn Por tanto, el valor de cada incógnita en cada paso del método m es x (m+ i = b i a ij x (m j j i, i =,, n a ii
14 62 Método de Gauss-Seidel De Ax = b se tiene que (D L Ux = b y, por tanto, (D Lx = Ux+b Luego x = (D L Ux + (D L b Teniendo en cuenta la anterior igualdad se deduce el siguiente método interativo (D Lx (m+ = Ux (m + b, que se trata de un sistema triangular inferior en cada paso, que se resuelve por sustitución progresiva Por tanto, el valor de cada incógnita en cada paso del método m es x (m+ i = b i j<i 6 Método de relajación a ij x (m+ j a ij x (m j j>i, i =,, n a ii En este caso, dado ω R, se considera la descomposición de la matriz de coecientes en la forma: Luego A = ω D ω ω D L U (D ωlx = (( ωd + ωux + ωb Teniendo en cuenta la anterior igualdad se deduce el siguiente método interativo (D ωlx (m+ = (( ωd + ωux (m + ωb que se trata de un sistema triangular inferior en cada paso, que se resuelve por sustitución progresiva Por tanto, el valor de cada incógnita en cada paso del método m es x (m+ i = ω b i j<i a ij x (m+ j a ii j>i a ij x (m j + ( ωx (m i, i =,, n Se pueden demostrar los sisguientes resultados de convergencia: 4
15 Teorema: Si A es estrictamente diagonalmente dominante entonces los métodos de Jacobi y Gauss-Seidel convergen Teorema: Si el método de relajación converge entonces ω [0, 2] 5
Facultad de Ciencias Trabajo Fin de Grado Grado en Matemáticas Matrices no negativas: algunos resultados y aplicaciones. Autora: Yaiza Fernández de la Fuente Tutora: María Paz Calvo Cabrero Índice 1.
UNIVERSIDAD DE CASTILLA-LA MANCHA ESCUELA TÉCNICA SUPERIOR DE INGENIEROS DE CAMINOS, CANALES Y PUERTOS MECÁNICA COMPUTACIONAL EN LA INGENIERÍA CON APLICACIONES EN MATLAB Eduardo W. V. Chaves y Roberto
prac.nb PRÁCTICA Num. Introducción a MATHEMATICA métodos directos para la resolución de sistemas de ecuaciones lineales INTRODUCCION: El programa Mathematica tiene incorporadas la mayor parte de las funciones

References: Resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 resolución