4 SEL Metodos_Iterativos

Embed Size (px)

Citation preview

  • *Metodos de Solucin IterativosEmpezar con una aproximacin inicial para el vector solucin (x0)Actualizar en cada iteracin el vector x usando el sistema Ax=bCada iteracin involucra el producto matriz-vector. Si A es esparcida este producto es realizado eficientemente.

  • *Procedimiento de solucin IterativaEscribir el sistema Ax=b en una forma equivalente x=Tx+cEmpezando con x0, genere una secuencia de aproximaciones {xk} iterativamente porxk+1=Txk+cRepresentacin de T y c dependen del tipo de mtodo usado.Pero para cada mtodo T y c son obtenidas a partir de A y b.

  • *ConvergenciaCuando k, la secuencia {xk} converge a un vector solucin bajo algunas condiciones en la Matriz T.Esto impone condiciones diferentes en la matriz A para diferentes mtodos.Para la misma matriz A, un mtodo puede converger mientras que otro puede divergir.Por lo tanto para cada mtodo la relacin entre A y T deben ser encontradas para decidir la convergencia.

  • *Diferentes metodos IterativosIteracin de JacobiIteracin de Gauss-SeidelSuccessive Over Relaxation (S.O.R)SOR es un mtodo usado para acelerar la convergencia. La iteracin de Gauss-Seidel es un caso especial del mtodo SOR.

  • *Iteracin de Jacobi

  • *Mtodo de Jacobi. Forma Matricial Descomponiendo A = D - L - U.-L=tril(A)-D-U-LDD=diag(diag(A))=-U=triu(A)-D

  • *xk+1=Txk+c - iteracin por el mtodo de Jacobi Se puede escribir como A=D-L-U (No es una factorizacin)xk+1=D-1(L+U)xk+D-1bT=D-1(L+U)c=D-1bAx=b (D-L-U)x=bDxk+1 = (L+U)xk+b

  • *iteracin Gauss-Seidel (GS)

  • *x(k+1)=Tx(k)+x iteracin de Gauss-Seidelxk+1=(D-L)-1Uxk+(D-L)-1bTgs=(D-L)-1Ucgs=(D-L)-1bAx=b (D-L-U)x=b(D-L)xk+1 =Uxk+b

  • *Comparacin teracin de Gauss-Seidel converge ms rpidamente que la iteracin de Jacobi desde que este usa la ltima actualizacin.Pero existen algunos casos que la iteracin de Jacobi converge pero Gauss-Seidel no.El mtodo de sobre relajacin sucesiva es usada para acelerar la convergencia del mtodo de Gauss-Seidel.

  • *Metodo Sobre Relajacin Sucesiva (SOR)Puede ser escrita como sigueConverge ms rpido

  • *SOR Donde el ultimo termino es la estimacin de Gauss-Seidel1
  • *x(k+1)=Tx(k)+c iteracin para SORDxk+1=(1-)Dxk+b+Lxk+1+Uxk(D- L)xk+1=[(1-)D+U]xk+bT=(D- L)-1[(1-)D+U]c= (D- L)-1b

  • *Convergencia de los mtodos iterativosDefine el vector solucin como Define el vector error como

  • *Convergencia de los Mtodos IterativosCondicin de ConvergenciaiteracinpotenciaEl mtodo iterativo convergera para cualquier vector inicial arbitrario si la siguiente condicin es satisfecha

  • *Norma de un vectorLa norma de un vector debe satisfacer estas condiciones:norms Vector pueden ser definidas en diferentes formas tanto como la definicin de norma satisface estas condiciones.

  • *Normas de vectores Comunmente usadasnorma Suma o norma 1norma Euclideana norma 2norma Maxima o norma

  • *Norma de una matrizLa norma de una matriz debe satisfacer estas cond.Importante identidad

  • *Normas de matrices mas usadasNorma Maxima suma_col- o norma 1Norma Espectral o norma 2Norma Maxima suma_fil- o norma

  • *EjemploCalcule las normas 1 y de la matriz

  • *Condicin de ConvergenciaExpresar T en terminos de matriz modal P y : Matriz Diagonal con valores propios de T en la diagonal

  • *Condicin Suficiente para convergenciaSi la magnitud de todos los valores propios de la Matriz de iteracin T es menor que 1 entonces laiteracin es convergenteLos valores propios son mas fcil de calcular que la norma de una matriz

  • *Convergencia de la iteracin de JacobiT=D-1(L+U)

  • *Convergencia de la iteracin de JacobiEvaluar la norma infinita (suma maxima fila) de TMatriz Diagonalmente DominanteSi A es una matriz diagonalmente dominante, entonces la iteracin de Jacobi converge para cualquier valor inicial

  • *Criterios de ParadaAx=bEn cualquier iteracin k, el trmino residual esrk=b-AxkVerificar la norma del trmino residual ||b-Axk||Si esto es menor que la cota del valor de parada

  • *Ejemplo 1 (Iteracin de Jacobi)Matriz Diagonalmente dominante

  • *Ejemplo 1 continuacin...Matriz es diagonalmente dominante, iteraciones de Jacobi son convergentes.

  • *Ejemplo 2La matriz no es diagolmente dominante

  • *Example 2 continuacin...El trmino del residual aumenta en cada iteracin, de tal forma que las iteraciones divergen.Note que la matriz no es diagonalmente dominante

  • *Convergencia de la itercin de Gauss-SeidelIteracin GS converge para cualquier vector inicial si A es una matriz diagonalmente dominanteIteracin GS converge para cualquier vector inicial si A es una matriz simtrica y definida positiva La matriz A es definida positiva si xTAx>0 para cualquier vector x no nulo.

  • *Ejemplo1 (Iteracin de Gauss-Seidel)Matriz Diagonalmente dominante

  • *Ejemplo 1 continuacin...Cuando ambos mtodos de Jacobi y Gauss-Seidel convergen, Gauss-Seidel converge ms rpido.

  • *Convergencia del mtodo SORSi 0
  • *Conteo de operacionesEl # de operaciones para la Eliminacin gaussiana o la descomposicin LU es de 0 (n3), orden de n3 Para los mtodos iterativos, el nmero de multiplicaciones escalares es 0 (n2) en cada iteracin. Si el nmero total de las iteraciones requeridas para la convergencia es mucho menos que n, entonces los mtodos iterativos son ms eficiente que mtodos directos. Los Mtodos iterativos tambin se satisfacen bien para las matrices esparcidas.

  • *Formas Matriciales. ResumenLa solucin del sistema A x = b se obtiene mediante la siguiente expresin recursiva:x ( k ) = Tx ( k-1 ) + c

    A= D - L - U

    MtodoJacobiGauss-SeidelSORT c D-1 (L+U)D-1 b ( D -L)-1 U( D -L)-1 b (D-w L)-1 [(1-w) D + w U ]w(D-w L)-1 b

  • *Problema 1Resolver el siguiente sistema por el mtodo SOR, considere =1.25.

    Aplicamos el metodo de SOR:

  • *Problema 1

  • *Problema 1

    kx1x2x3000010.6252.07031251.271972721.11572272.10357670.964374531.0034371.96404690.99767140.98790542.00448091.001982551.00442392.00088180.9997799

  • *Problema 2Sea el sistema A x = b :Para k=-1, es la matriz A definida positiva?Para que valores de k el sistema converge, al usar el mtodo de Gauss-Seidel?Hacer 03 iteraciones de Gauss-Seidel para k=-3

  • *Problema 2A es definida positiva si:Observese que tambin satisface el criterio de Silvester

  • *Problema 2

  • *Problema 2

    n x1 x20001342963127413.57.5514.257.75614.6257.875714.81257.9375