Parte 4. Métodos Iterativos Para La Resolución De Sistemas De

Transcript

Parte 4. M´ etodos iterativos para la resoluci´ on de sistemas de ecuaciones lineales Gustavo Montero Escuela T´ ecnica Superior de Ingenieros Industriales Universidad de Las Palmas de Gran Canaria Curso 2006-2007 Generalidades de los m´ etodos iterativos Metodo de Jacobi M´ etodo de Gauss-Seidel M´ etodo de Relajaci´ on Sucesiva Convergencia de los m´ etodos Resumen Generalidades de los m´ etodos iterativos Metodo de Jacobi M´ etodo de Gauss-Seidel M´ etodo de Relajaci´ on Sucesiva Convergencia de los m´ etodos Resumen Introducci´ on Ventaja frente a los m´ etodos directos 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´ etodos directos son considerables Definici´ on de m´ etodo iterativo Un m´ etodo iterativo construye una sucesi´ on de vectores xm tal que lim m→∞ xm = x siendo x la soluci´ on del sistema Ax = b. Construcci´ on de un m´ etodo iterativo Se parte de una aproximaci´ on inicial x0 y luego se calcula 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´ on y de sus propiedades va a depender la convergencia del m´ etodo. Definici´ on de convergencia Definici´ on de convergencia Un m´ etodo se dice que es convergente si: lim m→∞ xm = x = A −1 b Teorema del Punto Fijo Aplicando el Teorema del Punto Fijo, 0 00 0 00 ||F (x ) − F (x )|| ≤ L||x − x || es decir, 0 00 0 00 ||Bx − Bx || ≤ L||x − x || 0 Luego si v = x − x 00 =⇒ ||Bv || ≤ L||v || Teorema general para la convergencia de los m´ etodos iterativos Un m´ etodo iterativo del tipo anterior es convergente si y s´ olo si se cumplen simult´ aneamente las siguientes condiciones, I I c = (I − B)A−1 b ρ(B) < 1 Construcci´ on de m´ etodos iterativos Sea A = M − N, con M invertible Teorema de caracterizaci´ on de m´ etodos iterativos Si se toma, B c = M = M −1 −1 N b el m´ etodo considerado cumple la primera condici´ on anterior. Pero adem´ as se debe cumplir la segunda condici´ on, ρ(M −1 N) < 1 ||M o tambi´ en −1 N|| < 1 Teorema de construcci´ on de los m´ etodos iterativos Todo m´ etodo del tipo estudiado verifica las condiciones del teorema anterior con M − N = A y M invertible. El m´ etodo resulta, xm+1 = M −1 Nxm + M −1 b es decir, Mxm+1 = Nxm + b Por tanto, conviene elegir M tal que sea f´ acilmente invertible (diagonal o triangular). El n´ umero de operaciones de los m´ etodos iterativos es O(n2 ) × no iter Generalidades de los m´ etodos iterativos Metodo de Jacobi M´ etodo de Gauss-Seidel M´ etodo de Relajaci´ on Sucesiva Convergencia de los m´ etodos Resumen Algoritmo de Jacobi Matriz de iteraci´ on de Jacobi Descomposici´ on suma de una matriz La matriz de iteraci´ on de Jacobi resulta, 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 aa11 B 11 B a B B − 21 B 00 B D . a22= B B B a. a B B − 31 @ − . 32 B a33 a033 B B . . B . ··· . 0 ·B · · B . . an2 an1· · · ·@ ·· 0 − − 0 0 ann· · · ann . . .. . . . . . ··· −ann−1 0 0 a13 0− a · · · · · · 0 11 a22 a23· · · 0 − ··· . a22 . . . .. . . 0 ···. 0 ··· ann 1 .. 0. . .0 . C an3 B 0 C− B· · · C a B . nn = B C; U C B .. C B 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 C . −a . 12 C −a13 0 A −a23 0 . .. . . . ··· ··· ··· ··· El m´ etodo de Jacobi consiste en elegir M = D y N = L + U, resultando en forma matricial, Dxm+1 = (L + U)xm + b es decir, aii (xm+1 )i = − n X j=1 j6=i aij (xm )j + bi ; i = 1, 2, . . . , n ··· ··· . . . 0 ··· −a1n −a2n . . . −an−1n 0 1 C C C C C C A Generalidades de los m´ etodos iterativos Metodo de Jacobi M´ etodo de Gauss-Seidel M´ etodo de Relajaci´ on Sucesiva Convergencia de los m´ etodos Resumen Algoritmo de Gauss-Seidel Algoritmo El m´ etodo de Gauss-Seidel consiste en elegir M = D − L y N = U, resultando en forma matricial, (D − L)xm+1 = Uxm + b es decir, i X aij (xm+1 )j = − j=1 o, finalmente, aii (xm+1 )i = − n X aij (xm )j + bi ; i = 1, 2, . . . , n j=i+1 i−1 X aij (xm+1 )j − j=1 n X aij (xm )j + bi ; i = 1, 2, . . . , n j=i+1 Ventaja frente a Jacobi I Menor requerimiento de almacenamiento respecto a Jacobi, ya que no necesita dos vectores para la soluci´ on (xm+1 , xm ). En el m´ etodo de Gauss-Seidel las actualizaciones de la soluci´ on se guardan en las posiciones de los valores anteriores I El m´ etodo de Gauss-Seidel tiene mejores condiciones de convergencia que el de Jacobi Generalidades de los m´ etodos iterativos Metodo de Jacobi M´ etodo de Gauss-Seidel M´ etodo de Relajaci´ on Sucesiva Convergencia de los m´ etodos Resumen Algoritmo de Relajaci´ on Sucesiva Algoritmo Si tomamos un par´ ametro ω 6= 0, podemos hacer la descomposici´ on de A de la forma, A=D−L−U = y eligiendo M = 1 ω D − L, N = 1 aii (xm+1 )i + i−1 X D−L− 1−ω ω D−U 1−ω „ ω 1 ω D + U, resulta ω « „ « 1 1−ω D − L xm+1 = D + U xm + b ω ω aij (xm+1 )j = 1−ω j=1 ω aii (xm )i − n X aij (xm )j + bi ; i = 1, 2, . . . , n j=i+1 Algoritmo en dos pasos El algoritmo SSOR se puede expresar en dos pasos, un primer paso que coincide con el m´ etodo de Gauss-Seidel un segundo paso de relajaci´ on de la soluci´ on, i−1 n X X aii (¯ xm+1 )i + aij (xm+1 )j = aij (xm )j + bi ; i = 1, 2, . . . , n j=1 (xm+1 )i − (xm )i j=i+1 = ω ((¯ xm+1 )i − (xm )i ) Generalidades de los m´ etodos iterativos Metodo de Jacobi M´ etodo de Gauss-Seidel M´ etodo de Relajaci´ on Sucesiva Convergencia de los m´ etodos Resumen Resumen de resultados de Convergencia Si A es sim´ etrica y definida positiva, el m´ etodo de Gauss-Seidel converge. Si A es sim´ etrica y la matriz a11 B −a12 B D+L+U =B . B . @ . −a1n 0 −a12 a22 . . . −a2n ··· ··· .. . ··· −a1n −a2n . . . ann 1 C C C C A es definida positiva, el m´ etodo de Jacobi es convergente. Si A es sim´ etrica y definida positiva, el m´ etodo de relajaci´ on converge si y s´ olo si 0 < ω < 2. Si ω < 1 el m´ etodo se denomina de subrelajaci´ on y si ω > 1, de sobrerrelajaci´ on. Si A es sim´ etrica, definida positiva y tridiagonal, el valor ´ optimo de ω para la convergencia del m´ etodo de relajaci´ on es, 2 ω= q 1 + 1 − ρ2j siendo ρj el radio espectral de la matriz de iteraci´ on del m´ etodo de Jacobi. Generalidades de los m´ etodos iterativos Metodo de Jacobi M´ etodo de Gauss-Seidel M´ etodo de Relajaci´ on Sucesiva Convergencia de los m´ etodos Resumen Resumen I Los m´ etodos iterativos tienen un coste computacional de O(n2 ) × no iteraciones. Si el n´ umero de iteraciones es peque˜ no comparado con n, los m´ etodos iterativos son preferibles a los directos. Asimismo, los errores de blackondeo no se acumulan despu´ es de cada iteraci´ on, lo que supone una ventaja adicional. I El m´ etodo de Gauss-Seidel es usualmente m´ as eficiente que el de Jacobi I Podemos acelerar la convergencia mediante la t´ ecnica de relajaci´ on. Generalmente se suele utilizar valores de ω entre 1 y 2 (sobrerelajaci´ on) I En la actualidad los m´ etodos iterativos estudiados en esta asignatura est´ an obsoletos. Los m´ etodos m´ as utilizados son los basados en los subespacios de Krylov.