Apuntes de Computación Científica II

Métodos EDO - Problemas de valores iniciales


Método de Taylor

  1. Resolución de EDO de primer orden:
  2. Uso del desarrollo de Taylor de la función:

    (concepto de derivada total)
  3. Error (de truncamiento) de orden n+1:
  4. Problemas
    1. Diferenciación de f(x,y) puede ser complicada: uso de programas de cálculo simbólico

Método de Euler (forward)

  1. Método de Taylor de orden 1 (error de orden O(h2)):
  2. Interpretación geométrica:
    1. Aproximación de la solución por la recta tangente
    2. Solución calculada es polilínea con lados igual a rectas con pendiente fi en el intervalo [xi, x i+1]
  3. Problemas de estabilidad y de exactitud (convergencia)
  4. Método de Euler backward (ecuación implícita)

Métodos de Runge-Kutta

  1. Objetivo: evitar cálculo de derivadas de f(x,y), a base de calcular f(x,y) en más puntos, manteniendo el orden del error y la complejidad de cálculo
    1. métodos de orden 2, 3 y 4 requieren el cálculo de f(x,y) en 2, 3 y 4 puntos respectivamente
    2. métodos de orden m > 4 requieren el cálculo de f(x,y) en más de m puntos (no más de m+2)
  2. Uso de función de incremento , aproximación de f(x,y) en intervalo [xi, x i+1]
  3. Deducción de Runge-Kutta de orden 2 (RK-2)
    1. Se expande por Taylor k2, y se iguala desarrollo de Taylor de yi+1 en función de parámetros a, b, p y q con el desarrollo estándar término a término
  4. Métodos de Runge-Kutta de orden 2 ( error de O(h3) )
    1. Para a=b=1/2: promedio de tangentes en extremos (RK2-promedio)
    2. Para a=0, b=1: estimación de tangente en punto medio (midpoint method) (RK2-punto-medio)
    3. Métodos predictor-corrector
    4. ¡OJO! Al implementar el algoritmo, no usar las mismas variables para y para ; ambas son necesarias para calcular
  5. Métodos de Runge-Kutta de orden 3 ( error de O(h4) )
    1. Promedio de tangente en extremos y punto medio
  6. Métodos de Runge-Kutta de orden 4 ( error de O(h5) )
    1. Método atribuido a Kutta
  7. RK3 y RK4 se reducen a fórmula de Simpson de integración (interpolación parabólica de 3 puntos), cuando f(x,y) es función sólo de x:

Método de Runge-Kutta adaptativo

  1. Duplicación de paso (step doubling)
    1. Se repite estimación de y(x+2h) con 2h (y1) y con h (y2)
    2. Estimación del error:
    3. Extrapolación local para aumentar el orden del método
      Ejemplo de RK4:
  2. RK embebido (métodos Runge-Kutta-Fehlberg)
    1. Se aprovechan las evaluaciones de f(x,y) (las ki) de un método de orden superior para calcular una aproximación de orden inferior (método embebido en el anterior)
    2. Ejemplo de RK5 con RK4 embebido (ver coeficientes en Numerical Recipes)
    3. Extrapolación local al tomar cuando en realidad el error se le estima a
  3. Estimación de siguiente paso de integración h
    1. Si (ejemplos anteriores)
    2. Estimación nos da nuevo h para recalcular yi+1 si error era muy grande (mayor que la precisión deseada), o para calcular yi+2 si era muy pequeño
  4. Errores fraccionales (i.e., número de cifras significativas) para fijar : respecto de valor actual de y, máximo de y (conocido o estimado), etc.

Método del punto medio (midpoint) modificado

  1. Método del punto medio también conocido como "centered difference" o "leapfrog"
    1. Método de segundo orden con sólo una evaluación de f(x,y)
  2. Método del punto medio modificado (en los extremos)
  3. Error sólo depende de potencias pares de h
    1. Con técnicas similares a la integración de Simpson se puede aumentar el orden de la aproximación con poco coste
    2. Ejemplo de orden 4:
  4. Aplicación en el método de Richardson

Método de extrapolación de Richardson

  1. Idea similar a paso de integración de Simpson a la de Romberg (aproximación diferida al límite de Richardson)
    1. Se estima valor de y(x0+nh) para distintos pasos de integración (y distintos valores de n: H=nh=cte):
      n=2,4,6,8,10,...2j...
    2. Se extrapolan los valores obtenidos a h=0
  2. Extrapolación por funciones racionales (Burlisch-Stoer) o polinómicas (peores pero más rápidas)
    1. Extrapolación da además estimación de error: uso de algoritmos incrementales de extrapolación (Neville)
    2. Límite en valor máximo de n: si se llega a él, se reduce intervalo de integración (H=nh)
  3. Uso de métodos cuyo error depende de potencias de h2:
    1. Convergencia más rápida: extrapolación depende de h2, y al subdividir más, se aumenta aproximación en 2 órdenes
  4. H ya no es 'pequeño' (10h, 100h)
  5. Importancia de evaluación de por error fraccional; escalado de variables

Métodos predictor-corrector

  1. Métodos multipaso con iteración funcional
  2. Método explícito para estimar yi+1 (predictor):
  3. Ecuación implícita para valor final (corrector), que usa yi+1 anterior para evaluar fi+1:
  4. Diferencia entre los yi+1 da estimación del error de truncamiento local
  5. Se itera hasta reducir este error a los niveles deseados
  6. Método Adams-Bashforth-Moulton de tercer orden (O(h4)):
  7. Si número de iteraciones fijas, se convierte en método explícito: no muy aconsejable
  8. Método corrector multipaso con ecuación implícita resuelta por método de Newton es mejor para problemas stiff

Métodos multivalor (multivalue)

  1. En lugar de calcular yi+1, calculamos en cada paso yi+1 y sus derivadas:
  2. Fórmula:
    1. B se obtiene al derivar:
    2. las condiciones sobre y r2 se obtienen al forzar
  3. Resto componentes de r (r1, r3 , r4) son libres y determinan orden y estabilidad del método
    1. Adams-Moulton (corrector) corresponde a 5/12, 3/4, 1/6
  4. Resolución de método implícito por predictor-corrector o Newton
  5. Son equivalentes a métodos multipaso, pero resuelven dificultades de estos métodos:
    1. Adaptación de paso de integración; incluso se puede cambiar de orden dinámicamente, cambiando r
    2. Arranque del método, empezando con orden 1

Comparación entre los métodos

  1. Runge-Kutta:
    1. Bueno para casi todo
    2. Cuando no se exige mucha eficiencia ni exactitud
  2. Richardson:
    1. Para mejorar eficiencia y exactitud, aunque puede dar más problemas que RK
    2. Falla cuando hay singularidades o si las soluciones son poco suaves
  3. Predictor-corrector:
    1. Richardson los está dejando obsoletos
    2. Útiles para f(x,y) complicada, pero con funciones suaves y se desea alta precisión

Computación Científica II Apuntes de CCII Prácticas de CCII

Página creada por Pedro J. Pascual Broncano y Carlos Santacruz
© Escuela Técnica Superior de Informática de la Universidad Autónoma de Madrid, 2000
Última actualización: PjPB,