stringtranslate.com

Método lineal de varios pasos

Los métodos lineales de múltiples pasos se utilizan para la solución numérica de ecuaciones diferenciales ordinarias . Conceptualmente, un método numérico comienza desde un punto inicial y luego da un pequeño paso hacia adelante en el tiempo para encontrar el siguiente punto de solución. El proceso continúa con pasos subsiguientes para trazar la solución. Los métodos de un solo paso (como el método de Euler ) se refieren solo a un punto anterior y su derivada para determinar el valor actual. Los métodos como Runge-Kutta toman algunos pasos intermedios (por ejemplo, medio paso) para obtener un método de orden superior, pero luego descartan toda la información anterior antes de dar un segundo paso. Los métodos de múltiples pasos intentan ganar eficiencia al mantener y usar la información de los pasos anteriores en lugar de descartarla. En consecuencia, los métodos de múltiples pasos se refieren a varios puntos anteriores y valores derivados. En el caso de los métodos lineales de múltiples pasos, se utiliza una combinación lineal de los puntos anteriores y los valores derivados.

Definiciones

Los métodos numéricos para ecuaciones diferenciales ordinarias aproximan soluciones a problemas de valor inicial de la forma

El resultado son aproximaciones para el valor de en tiempos discretos : donde es el paso de tiempo (a veces denominado ) y es un número entero.

Los métodos de varios pasos utilizan información de los pasos anteriores para calcular el siguiente valor. En particular, un método de varios pasos lineal utiliza una combinación lineal de y para calcular el valor de para el paso actual deseado. Por lo tanto, un método de varios pasos lineal es un método de la forma con . Los coeficientes y determinan el método. El diseñador del método elige los coeficientes, equilibrando la necesidad de obtener una buena aproximación a la solución verdadera con el deseo de obtener un método que sea fácil de aplicar. A menudo, muchos coeficientes son cero para simplificar el método.

Se puede distinguir entre métodos explícitos e implícitos . Si , entonces el método se llama "explícito", ya que la fórmula puede calcular directamente . Si entonces el método se llama "implícito", ya que el valor de depende del valor de , y la ecuación debe resolverse para . Los métodos iterativos como el método de Newton se utilizan a menudo para resolver la fórmula implícita.

A veces se utiliza un método explícito de varios pasos para "predecir" el valor de . Ese valor se utiliza luego en una fórmula implícita para "corregirlo". El resultado es un método predictor-corrector .

Ejemplos

Consideremos como ejemplo el problema La solución exacta es .

Euler de un paso

Un método numérico simple es el método de Euler: El método de Euler puede verse como un método explícito de múltiples pasos para el caso degenerado de un paso.

Este método, aplicado con tamaño de paso en el problema , da los siguientes resultados:

Adams-Bashforth en dos pasos

El método de Euler es un método de un solo paso . Un método simple de varios pasos es el método de Adams-Bashforth de dos pasos. Este método necesita dos valores, y , para calcular el siguiente valor, . Sin embargo, el problema del valor inicial proporciona solo un valor, . Una posibilidad para resolver este problema es utilizar el calculado por el método de Euler como el segundo valor. Con esta opción, el método de Adams-Bashforth produce (redondeado a cuatro dígitos): La solución exacta en es , por lo que el método de Adams-Bashforth de dos pasos es más preciso que el método de Euler. Este es siempre el caso si el tamaño del paso es lo suficientemente pequeño.

Familias de métodos de varios pasos

Se utilizan comúnmente tres familias de métodos lineales de múltiples pasos: los métodos de Adams-Bashforth, los métodos de Adams-Moulton y las fórmulas de diferenciación hacia atrás (BDF).

Métodos de Adams-Bashforth

Los métodos de Adams-Bashforth son métodos explícitos. Los coeficientes son y , mientras que se eligen de modo que los métodos tengan orden s (esto determina los métodos de forma única).

Los métodos de Adams-Bashforth con s = 1, 2, 3, 4, 5 son (Hairer, Nørsett y Wanner 1993, §III.1; Butcher 2003, pág. 103):

Los coeficientes se pueden determinar de la siguiente manera. Utilice la interpolación polinómica para encontrar el polinomio p de grado tal que La fórmula de Lagrange para la interpolación polinómica da El polinomio p es localmente una buena aproximación del lado derecho de la ecuación diferencial que se va a resolver, así que considere la ecuación en su lugar. Esta ecuación se puede resolver exactamente; la solución es simplemente la integral de p . Esto sugiere tomar El método de Adams-Bashforth surge cuando se sustituye la fórmula para p . Los coeficientes resultan estar dados por Reemplazar por su interpolante p incurre en un error de orden h s , y se deduce que el método de Adams-Bashforth de s pasos tiene de hecho orden s (Iserles 1996, §2.1)

Los métodos de Adams-Bashforth fueron diseñados por John Couch Adams para resolver una ecuación diferencial que modela la acción capilar debida a Francis Bashforth . Bashforth (1883) publicó su teoría y el método numérico de Adams (Goldstine 1977).

Métodos de Adams-Moulton

Los métodos de Adams-Moulton son similares a los métodos de Adams-Bashforth en que también tienen y . Nuevamente, los coeficientes b se eligen para obtener el orden más alto posible. Sin embargo, los métodos de Adams-Moulton son métodos implícitos. Al eliminar la restricción de que , un método de Adams-Moulton de s pasos puede alcanzar el orden , mientras que un método de Adams-Bashforth de s pasos solo tiene orden s .

Los métodos de Adams-Moulton con s = 0, 1, 2, 3, 4 se enumeran (Hairer, Nørsett y Wanner 1993, §III.1; Quarteroni, Sacco y Saleri 2000), donde los dos primeros métodos son el método de Euler hacia atrás y la regla trapezoidal respectivamente:

La derivación de los métodos de Adams-Moulton es similar a la del método de Adams-Bashforth; sin embargo, el polinomio de interpolación utiliza no solo los puntos , como se indicó anteriormente, sino también . Los coeficientes se dan por

Los métodos de Adams-Moulton se deben únicamente a John Couch Adams , al igual que los métodos de Adams-Bashforth. El nombre de Forest Ray Moulton se asoció con estos métodos porque se dio cuenta de que podían usarse en conjunto con los métodos de Adams-Bashforth como un par predictor-corrector (Moulton 1926); Milne (1926) tuvo la misma idea. Adams utilizó el método de Newton para resolver la ecuación implícita (Hairer, Nørsett y Wanner 1993, §III.1).

Fórmulas de diferenciación hacia atrás (BDF)

Los métodos BDF son métodos implícitos con y los demás coeficientes elegidos de forma que el método alcance el orden s (el máximo posible). Estos métodos se utilizan especialmente para la solución de ecuaciones diferenciales rígidas .

Análisis

Los conceptos centrales en el análisis de métodos lineales de múltiples pasos, y de hecho de cualquier método numérico para ecuaciones diferenciales, son la convergencia, el orden y la estabilidad .

Coherencia y orden

La primera pregunta es si el método es consistente: ¿es la ecuación diferencial una buena aproximación de la ecuación diferencial ? Más precisamente, un método de múltiples pasos es consistente si el error de truncamiento local tiende a cero más rápido que el tamaño del paso h a medida que h tiende a cero, donde el error de truncamiento local se define como la diferencia entre el resultado del método, asumiendo que todos los valores anteriores son exactos, y la solución exacta de la ecuación en el tiempo . Un cálculo utilizando series de Taylor muestra que un método lineal de múltiples pasos es consistente si y solo si Todos los métodos mencionados anteriormente son consistentes (Hairer, Nørsett y Wanner 1993, §III.2).

Si el método es consistente, entonces la siguiente pregunta es qué tan bien la ecuación diferencial que define el método numérico se aproxima a la ecuación diferencial. Se dice que un método de múltiples pasos tiene orden p si el error local es de orden cuando h tiende a cero. Esto es equivalente a la siguiente condición sobre los coeficientes de los métodos: El método de Adams-Bashforth de s pasos tiene orden s , mientras que el método de Adams-Moulton de s pasos tiene orden (Hairer, Nørsett y Wanner 1993, §III.2).

Estas condiciones a menudo se formulan utilizando los polinomios característicos . En términos de estos polinomios, la condición anterior para que el método tenga orden p se convierte en En particular, el método es consistente si tiene orden al menos uno, lo cual es el caso si y .

Estabilidad y convergencia

La solución numérica de un método de un paso depende de la condición inicial , pero la solución numérica de un método de s pasos depende de todos los valores iniciales s , . Por lo tanto, es de interés si la solución numérica es estable con respecto a perturbaciones en los valores iniciales. Un método lineal de múltiples pasos es estable a cero para una cierta ecuación diferencial en un intervalo de tiempo dado, si una perturbación en los valores iniciales de tamaño ε hace que la solución numérica durante ese intervalo de tiempo cambie en no más de K ε para algún valor de K que no depende del tamaño del paso h . Esto se llama "estabilidad a cero" porque es suficiente para verificar la condición para la ecuación diferencial (Süli & Mayers 2003, p. 332).

Si todas las raíces del polinomio característico ρ tienen un módulo menor o igual a 1 y las raíces de módulo 1 tienen multiplicidad 1, decimos que se cumple la condición de raíz . Un método lineal de múltiples pasos es estable a cero si y solo si se cumple la condición de raíz (Süli y Mayers 2003, p. 335).

Ahora supongamos que se aplica un método lineal de múltiples pasos consistente a una ecuación diferencial suficientemente suave y que todos los valores iniciales convergen al valor inicial como . Entonces, la solución numérica converge a la solución exacta como si y solo si el método es estable a cero. Este resultado se conoce como el teorema de equivalencia de Dahlquist , llamado así por Germund Dahlquist ; este teorema es similar en espíritu al teorema de equivalencia de Lax para métodos de diferencias finitas . Además, si el método tiene orden p , entonces el error global (la diferencia entre la solución numérica y la solución exacta en un tiempo fijo) es (Süli & Mayers 2003, p. 340).

Además, si el método es convergente, se dice que es fuertemente estable si es la única raíz de módulo 1. Si es convergente y no se repiten todas las raíces de módulo 1, pero hay más de una raíz de ese tipo, se dice que es relativamente estable . Nótese que 1 debe ser una raíz para que el método sea convergente; por lo tanto, los métodos convergentes son siempre uno de estos dos.

Para evaluar el desempeño de los métodos multipaso lineales en ecuaciones rígidas , considere la ecuación de prueba lineal y' = λ y . Un método multipaso aplicado a esta ecuación diferencial con tamaño de paso h produce una relación de recurrencia lineal con polinomio característico Este polinomio se llama polinomio de estabilidad del método multipaso. Si todas sus raíces tienen módulo menor que uno, entonces la solución numérica del método multipaso convergerá a cero y se dice que el método multipaso es absolutamente estable para ese valor de h λ. Se dice que el método es A-estable si es absolutamente estable para todos los h λ con parte real negativa. La región de estabilidad absoluta es el conjunto de todos los h λ para los cuales el método multipaso es absolutamente estable (Süli & Mayers 2003, pp. 347 y 348). Para más detalles, vea la sección sobre ecuaciones rígidas y métodos multipaso .

Ejemplo

Considere el método de tres pasos de Adams-Bashforth. Un polinomio característico es entonces que tiene raíces , y se cumplen las condiciones anteriores. Como es la única raíz de módulo 1, el método es fuertemente estable.

El otro polinomio característico es

Primera y segunda barrera de Dahlquist

Estos dos resultados fueron demostrados por Germund Dahlquist y representan un límite importante para el orden de convergencia y para la estabilidad A de un método lineal de múltiples pasos. La primera barrera de Dahlquist fue demostrada en Dahlquist (1956) y la segunda en Dahlquist (1963).

Primera barrera de Dahlquist

La primera barrera de Dahlquist establece que un método multipaso lineal y estable en cero no puede alcanzar un orden de convergencia mayor que q + 1 si q es impar y mayor que q + 2 si q es par. Si el método también es explícito , entonces no puede alcanzar un orden mayor que q (Hairer, Nørsett y Wanner 1993, Tesis III.3.5).

Segunda barrera de Dahlquist

La segunda barrera de Dahlquist establece que ningún método lineal multipaso explícito es A-estable . Además, el orden máximo de un método lineal multipaso (implícito) A-estable es 2. Entre los métodos lineales multipaso A-estables de orden 2, la regla trapezoidal tiene la constante de error más pequeña (Dahlquist 1963, Tesis 2.1 y 2.2).

Véase también

Referencias

Enlaces externos