Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

El método de relajación para sistemas lineales

No description
by

Laura Prados

on 9 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of El método de relajación para sistemas lineales

Introducción
Nuestro trabajo se va a encargar de explicar el método de relajación. Para ello, lo compararemos con los demás métodos iterativos que hemos estudiado, para que por último podamos dar respuesta a la siguiente cuestión: ¿cuál de ellos es mejor?
Parámetro de relajación
El método de relajación para sistemas lineales

Alicia Pacheco Aguilar
Alicia Quero de la Rosa
Lucía Pleguezuelos Bonilla
Pablo Ruíz Mérida
Laura Prados Sáez
Elena María Moreno Pérez
María Araceli Muñoz Jiménez
Pilar Cobos Fernández
Rocío del Amo Oliver

ÍNDICE
LOS MÉTODOS ITERATIVOS
Tratan de resolver un sistema de ecuaciones lineales de la forma:
Así, quedaría definida como:
Ax=b
Método de Jacobi
A=D-L-U
Para lo cual definimos las
matrices:
Método de Gauss-Seidel
Consideramos el siguiente sistema de ecuaciones
Gauss-Seidel
Consideramos el siguiente sistema de ecuaciones
Jacobi
Ecuación del método de Jacobi:
Ecuación del método de Gauss-Seidel:
Parámetro de relajación
Dependiendo de este, el método adquiere dos definiciones diferentes:
si ω>1
Sobrerelajación
Acelerar convergencia de Jacobi y Gauss-Seidel
si ω<1
Subrelajación
Jacobi y Gauss-Seidel no convergen
Teoremas y lemas
Teorema de Ostrowski-Reich
A=Matriz de coeficientes
D=Matriz diagonal principal de A
L=Parte inferior de la matriz A cambiada de signo
U=Parte superior de la matriz A cambiada de signo
O matricialmente:
O matricialmente:
Fue desarrollado por el ingeniero británico
Richard Southwell
(1888-1970), para la resolución de ecuaciones diferenciales parciales en ingeniería y física teórica.
Las ecuaciones diferenciales se empezaron a discretizar primero haciendo uso de unos métodos muy limitados.
Para que la ecuación discretizada fuera satisfactoria los valores de la función debían de estar ajustados de forma iterativa.
Pero por aquel entonces como no existían los ordenadores digitales, y los cálculos se tenían que hacer a mano.
Southwell desarrolló varias técnicas para acelerar dichos cálculos. Por ejemplo, el método de SOR (Successive Over-Relaxation).
Método de relajación
Fijamos un vector inicial arbitrario.
Hallamos el valor de la siguiente iteración:
donde ω distinto de 0 es un factor al que llamaremos
parámetro de relajación
Aplicado
al
Método de Jacobi
Al no suponer ninguna mejora sustancial del método de Jacobi, no se utiliza.
Método de Gauss-Seidel
Dividiendo por ω la versión
matricial de Gauss-Seidel
Matriz de relajación
Comparación de los métodos iterativos
Vamos a ver la relación entre los distintos métodos de relajación.

Ya sabemos que Gauss-Seidel es más rápido que Jacobi, ahora vamos a ver que si escogemos el omega óptimo, el método de relajación converge a más velocidad que Gauss-Seidel.
Sea A una matriz tridiagonal tal que todos los autovalores de la matriz de Jacobi son reales.
La función alcanza su mínimo absoluto en:
Aclaramos unos conceptos antes de proseguir:

El
radio espectral
es el máximo de los valores absolutos de los valores propios de la matriz.
La
matiz hermítica
es una matriz cuadrada de elementos complejos que se caracteriza por ser igual a su propia traspuesta conjugada:
En álgebra lineal se denomina
matriz tridiagonal
a una matriz cuyos elementos son solo distintos de cero en la diagonal principal y las diagonales adyacentes por encima y por debajo a esta.
Comparación de Jacobi y Gauss-Seidel
La pregunta obvia es cómo determinar el valor de ω óptimo
Una vez aclaradas estas definiciones...
Los radios espectrales estan relacionados por
ω óptimo
En el caso particular de
ω=1
, tenemos el método de Gauss-Seidel. Pero para determinar
ω óptimo... Lo primero que tenemos que saber es :
¿En qué consiste el método de relajación?
1.-Consite en determinar (si existe) un intervalo I, perteneciente a los números reales que no contenga al origen , tal que:

2.- Un parámetro de relajación óptimo perteneciente al intervalo I, tal que:
Debido a esto, los métodos convergen o divergen simultáneamente y Gauss-Seidel es más rápido que Jacobi, a pesar de esto, a veces Gauss-Seidel no converge mientras que Jacobi sí.
y en determinar el parámetro óptimo dado por:
1.-
Introducción: los métodos iterativos.
2.-
Método de Jacobi y método de Gauss-Seidel.
3.-
Introducción al método de relajación.
4.-
Parámetros de relajación.
5.-
Aplicación a Jacobi y a Gauss-Seidel.
6.-
Sobrerelajación y subrelajación.
7.-
Parámetro de relajación óptimo.
8.-
Teoremas y lemas.
9.-
Comparaciones:
Método de Jacobi y de relajación.
Método de Gauss-Seidel y de Jacobi.
Los tres métodos (mediante ejemplo).
Introducción
Teorema de Kahan
Lema 1
Se verifica tanto para Jacobi como para Gauss-Seidel:
si la matriz de coeficientes del sistema de ecuaciones es estrictamente
diagonal dominante entonces el método de relajación converge.
¡IMPORTANTE!
Método de Jacobi Método de relajación
MÉTODO DE JACOBI-MÉTODO DE RELAJACIÓN
converge o diverge para
0<ω<2
converge o diverge para
0<ω<2
Ambas convergen o divergen simultáneamente
En caso de
convergencia
Método de Jacobi
Método de
Gauss-Seidel
Si A es tridiagonal
Comparación de los tres métodos
(mediante ejemplo)
donde
es el
error aproximado porcentual
Jacobi
para
ω=1.2
Gauss-Seidel
Método de Relajación
Se observa que para las tres incógnitas con método de Jacobi, los resultados son más oscilantes y convergen de forma más lenta.
Por el método de Gauss-Seidel, se da una convergencia relativamente rápida.
Por el método de relajación, la convergencia es mucho más rápida.
Gráficamente:
Full transcript