Metods Numericos: junio 2012

jueves, 7 de junio de 2012

Metodo de Runge Kutta

En la sección anterior se estableció que el método de Euler para resolver la ecuación diferencial de primer orden

Y' = f(X, Y)

(7)

con la condición inicial

Y(X0) = Y0

(8)

consiste en aplicar repetidamente la fórmula de recurrencia

Yn+1 = Yn + h f(Xn, Yn) donde n = 1, 2, 3, ...

(9)

para determinar la solución de la ecuación diferencial en

X = X1, X2, X3, ...

Sustituyendo la función f(X,Y) dada en (7), en (9), se tiene que

Yn+1 = Yn + h Y'n

(10)

expresión que indica que el método de Euler consiste gráficamente, en ir de un valor Yn conocido de la solución de la ecuación diferencial (7) en un punto, al siguiente por medio de la tangente T1 a la curva integral Y = Y(X) en el mismo punto de la solución conocida, como se muestra en la siguiente figura.

De este planteamiento gráfico puede verse que una mejor aproximación a la solución de la ecuación diferencial se obtendría si en vez de ir por la tangente T1 para determinar la solución en el siguiente Punto Pivote, se utiliza una secante con pendiente igual al promedio de pendientes de la curva integral en los puntos coordenados (Xn, Yn), (Xn+1, Yn+1) en donde Xn+1 y Yn+1 pueden estimarse con el procedimiento normal de Euler, como se muestra en la siguiente gráfica:

Con lo anterior se obtendría un método mejorado de Euler con error del orden de definido por la expresión

(11)

en donde f(Xn+1, Yn+1) es el valor de la función f(X, Y) para:

X = Xn+1

Y = Yn + h f(Xn, Yn)

Observando las expresiones para resolver la ecuación diferencial, puede decirse que ambas consisten en aplicar la fórmula de recurrencia

(12)

en donde

(13)

en el método de Euler y

(14)

en lo que

Y' = f(X, Y)

(15)

en el método de Euler Mejorado.

Como se ve, estos métodos tienen los siguientes puntos en común:

Son métodos de un paso; para determinar Yn+1 se necesita conocer únicamente los valores de Xn y Yn del punto anterior.

No requieren evaluar ninguna derivada, sino únicamente valores de la función f(X, Y).

Estas características dan origen a una gran variedad de métodos conocidos como de Runge-Kutta. La diferencia entre ellos cosiste en la forma como se define la función que aparece en la expresión (12).

La ventaja de los métodos de Runge-Kutta con respecto al uso de la serie de Taylor, que es también un método de un paso, está expresado en el punto (2) anterior; es decir, los métodos de Runge-Kutta requieren sólo de la función f(X, Y) y de ninguna derivada, mientras que la serie de Taylor sí requiere de la evaluación de derivadas. Esto hace que, en la práctica, la aplicación de los métodos de Runge-Kutta sean más simples que el uso de la serie de Taylor.

Metodo de Euler hacia delante y hacia atras

METODO DE EULER HACIA ADELANTE Y HACIA ATRAS

• El presente método, fue ideado por el gran

matemático Leonhard Gauss, hace más de doscientos

años, este resulta ser el más fácil de entender y

aplicar.

• Es muy adecuado para la programación rápida,

debido a su sencillez.

• No es tan preciso como otros métodos mas refinados

(como Heun, Runge-Kutta de 4to Orden, etc...)

[[image:data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABAAAAAQCAIAAACQkWg2AAAAz0lEQVQokaXSMQqDMBQG4HeBLFkd3vAO4AkEnQR7j5a6VN4Bcp0geAbBLYfIIt5AQt1CB0GM1kDpP2X4P8gPD/wu4zgqpfK8AAAAyPNCKTVN074D28sYI6WEU6SUxpgjcM4h4rm9hoiW5R2Atm2v2mu6rgvAs67jgJkDsA29SlXdAhAZsCZN0wAkSRIHiPgf+PlLWZbFQVmWAbg/HnHwapoAaK3jQGsdgHmeI7sR0Tl3PL6+74UQ57YQYhiGL9fqvbfWMjMRrVUiYmZr7b7zAXePHtih8tRrAAAAAElFTkSuQmCC]]

0

• Pártase del más simple tipo de ecuación diferencial
ordinaria, que la de tipo lineal de primer orden, el
clásico Problema de Cauchy de la forma:

Considérese que el problema a sido discretizado
sobre la variable t, donde se cumple:

miércoles, 6 de junio de 2012

Metodo de Gauss Seidel

MÉTODO DE GAUSS - SEIDEL

Autor Intelectual: Diego LópezMonitor

Al igual que el Método de Jacobi, El Método de Gauss-Seidel consiste en hacer iteraciones, a partir de un vector inicial, para encontrar los valores de las incógnitas hasta llegar a una tolerancia deseada, la diferencia radica en que cada vez que se desee encontrar un nuevo valor de una x_i, además de usar los valores anteriores de las x, también utiliza valores actuales de las x encontradas antes (desde x₀ hasta x_i-1).

La ecuación es la siguiente:

$x_i^{(k)} = \left( {b_i - \sum\limits_{j = 1}^{i - 1} {a_{ij} x_j^k } - \sum\limits_{j = i + 1}^n {a_{ij} x_j^{(k - 1)} } } \right)/a_{ij}$

Este proceso de usar valores actuales para hallar un valor de x puede facilitar la convergencia del mismo.

Convergencia del método:

Para determinar si el método de Gauss-Seidel converge hacia una solución. Se evalúan las siguientes condiciones de convergencia (Nota: las siguientes van en un órden de modo que si se cumple una de las condiciones, comenzando por la primera por supuesto, la evaluación de las siguientes no es necesario realizarlas):

La matriz sea estrictamente dominante diagonalmente por filas (E.D.D. por filas), es decir, para todo i desde 1 hasta n que es el tamaño de la matriz A:

$\left| {a_{ii} } \right| \ge \sum\limits_{j = 1}^{i - 1} {\left| {a_{ij} } \right|} + \sum\limits_{j = i + 1}^n {\left| {a_{ij} } \right|}$

Es decir, el elemento de la diagonal correspondiente a la fila i debe ser mayor a la suma de los elementos de esa fila i.
A partir de la siguiente identidad:

Donde D corresponde a la matriz formada por los elementos de la diagonal de A (D=diag(a₁₁, a₂₂, ..., a_nn)), -L corresponde a la matriz triangular inferior obtenida de la parte triangular estrictamente inferior de A, y -U corresponde a la matriz triangular superior obtenida de la parte triangular estrictamente superior de A, se puede deducir la fórmula vectorial de este método:

$X^k = (D - L)^{ - 1} UX^{(k - 1)} + (D - L)^{ - 1} b$ , k = 1, 2, ...

De donde B_G (conocida como la matriz de iteración de Gauss-Seidel) es (D-L)^-1U. Para que el método de Jacobi converja hacia una solución,

$\left\| {B_G } \right\|_{norma} < 1$ , para una norma matricial inducida.
ρ(B_G), que corresponde al máximo de los valores absolutos de las raíces de la ecuación característica de la matriz B_G (det(B_G - λI)) es menor que 1

Agradecimientos especiales a Diego Lopez edicion especial de sus apuntes

Metodos de Newton Raphson

Este método, el cual es un método iterativo, es uno de los más usados y efectivos. A diferencia de los métodos anteriores, el método de Newton-Raphson no trabaja sobre un intervalo sino que basa su fórmula en un proceso iterativo.
Supongamos que tenemos la aproximación

a la raíz

,

Trazamos la recta tangente a la curva en el punto

; ésta cruza al eje

en un punto

que será nuestra siguiente aproximación a la raíz

.
Para calcular el punto

, calculamos primero la ecuación de la recta tangente. Sabemos que tiene pendiente

Y por lo tanto la ecuación de la recta tangente es:

Hacemos

Y despejamos

Que es la fómula iterativa de Newton-Raphson para calcular la siguiente aproximación:

, si

Note que el método de Newton-Raphson no trabaja con intervalos donde nos asegure que encontraremos la raíz, y de hecho no tenemos ninguna garantía de que nos aproximaremos a dicha raíz. Desde luego, existen ejemplos donde este método no converge a la raíz, en cuyo caso se dice que el método diverge. Sin embargo, en los casos donde si converge a la raíz lo hace con una rapidez impresionante, por lo cual es uno de los métodos preferidos por excelencia.
También observe que en el caso de que

, el método no se puede aplicar. De hecho, vemos geométricamente que esto significa que la recta tangente es horizontal y por lo tanto no intersecta al eje

en ningún punto, a menos que coincida con éste, en cuyo caso

mismo es una raíz de

!
Ejemplo 1
Usar el método de Newton-Raphson, para aproximar la raíz de

, comenzando con

y hasta que

.
Solución
En este caso, tenemos que

De aquí tenemos que:

Comenzamos con

y obtenemos:

En este caso, el error aproximado es,

Continuamos el proceso hasta reducir el error aproximado hasta donde se pidió.
Resumimos los resultados en la siguiente tabla:

Aprox. a la raíz	Error aprox.
1
1.268941421	21.19%
1.309108403	3.06%
1.309799389	0.052%

De lo cual concluímos que

, la cual es correcta en todos sus dígitos!
La misma idea puede aplicarse para crear algoritmos que aproximen raíces

-ésimas de números reales positivos.
Observe que cuando el método de Newton-Raphson converge a la raíz, lo hace de una forma muy rápida y de hecho, observamos que el error aproximado disminuye a pasos agigantados en cada paso del proceso. Aunque no es nuestro objetivo establecer formalmente las cotas para los errores en cada uno de los métodos que hemos estudiado, cabe mencionar que si existen estas cotas que miden con mayor precisión la rapidez ó lentitud del método en estudio.