6.4 Multistep methods

Multistep methods in ODEs use info from previous steps to find the next solution point. They're more accurate and efficient than single-step methods, allowing for larger step sizes. These methods come in explicit and implicit flavors, each with their own strengths.

Stability and convergence are key in multistep methods. The root condition and zero-stability are crucial for convergence. When choosing a method, consider the problem's stiffness, desired accuracy, and computational resources. Adaptive strategies can optimize performance for different scenarios.

Multistep Methods Principles

Fundamental Concepts and Characteristics

Top images from around the web for Fundamental Concepts and Characteristics

• 

  Asymptotics of Polynomial Interpolation and the Bernstein Constants | SpringerLink View original

  Is this image relevant?

• 

  High Order Semi-implicit Multistep Methods for Time-Dependent Partial Differential Equations ... View original

  Is this image relevant?

• 

  Exponential mean-square stability properties of stochastic linear multistep methods | Advances ... View original

  Is this image relevant?

• 

  Asymptotics of Polynomial Interpolation and the Bernstein Constants | SpringerLink View original

  Is this image relevant?

• 

  High Order Semi-implicit Multistep Methods for Time-Dependent Partial Differential Equations ... View original

  Is this image relevant?

1 of 3

Top images from around the web for Fundamental Concepts and Characteristics

• 

  Asymptotics of Polynomial Interpolation and the Bernstein Constants | SpringerLink View original

  Is this image relevant?

• 

  High Order Semi-implicit Multistep Methods for Time-Dependent Partial Differential Equations ... View original

  Is this image relevant?

• 

  Exponential mean-square stability properties of stochastic linear multistep methods | Advances ... View original

  Is this image relevant?

• 

  Asymptotics of Polynomial Interpolation and the Bernstein Constants | SpringerLink View original

  Is this image relevant?

• 

  High Order Semi-implicit Multistep Methods for Time-Dependent Partial Differential Equations ... View original

  Is this image relevant?

1 of 3

• Multistep methods utilize information from several previous steps to compute the next solution point
  • Improves accuracy and efficiency compared to single-step methods
  • Allows for larger step sizes in many cases
• Characterized by their order determining the degree of polynomial interpolation used
  • Higher-order methods generally provide increased accuracy
  • Order affects the method's stability and computational complexity
• General form involves a linear combination of function evaluations at current and previous steps
  • Expressed mathematically as $\sum_{j=0}^k \alpha_j y_{n+j} = h \sum_{j=0}^k \beta_j f(t_{n+j}, y_{n+j})$
  • Coefficients α_j and β_j define the specific method

Derivation and Error Analysis

• Derived by integrating interpolating polynomials approximating the solution over multiple time steps
  • Uses techniques such as Lagrange interpolation or finite difference formulas
• Local truncation error crucial for understanding accuracy and determining method order
  • Defined as the error introduced in a single step, assuming previous steps are exact
  • Expressed as $LTE = y(t_{n+1}) - y_{n+1}$
• Trade-off between computational efficiency and stability
  • Higher-order methods often more accurate but potentially less stable
  • Requires careful selection based on problem characteristics

Explicit vs Implicit Multistep Methods

Explicit Methods: Adams-Bashforth

• Use only previously computed values to determine the next solution point
  • General form of k-step Adams-Bashforth method: $y_{n+1} = y_n + h \sum_{j=0}^{k-1} b_j f(t_{n-j}, y_{n-j})$
• Computationally efficient as they don't require solving equations at each step
• Examples of Adams-Bashforth methods:
  • 2-step: $y_{n+1} = y_n + \frac{h}{2}(3f_n - f_{n-1})$
  • 3-step: $y_{n+1} = y_n + \frac{h}{12}(23f_n - 16f_{n-1} + 5f_{n-2})$

Implicit Methods: Adams-Moulton

• Require solving an equation involving the current solution point at each step
  • General form: $y_{n+1} = y_n + h \sum_{j=-1}^{k-1} b_j f(t_{n-j}, y_{n-j})$
• Typically offer better stability and accuracy compared to explicit methods of the same order
• Examples of Adams-Moulton methods:
  • 2-step: $y_{n+1} = y_n + \frac{h}{12}(5f_{n+1} + 8f_n - f_{n-1})$
  • 3-step: $y_{n+1} = y_n + \frac{h}{24}(9f_{n+1} + 19f_n - 5f_{n-1} + f_{n-2})$

Implementation Considerations

• Predictor-corrector methods combine explicit and implicit approaches
  • Use explicit method to predict solution
  • Refine prediction using implicit method
  • Example: Adams-Bashforth-Moulton predictor-corrector pair
• Careful initialization required for multistep methods
  • Need several starting values typically obtained using single-step method (Runge-Kutta)
• Choice between explicit and implicit methods depends on:
  • Problem stiffness
  • Desired accuracy
  • Available computational resources
• Efficient implementation of implicit methods often involves:
  • Newton's method for solving nonlinear equations
  • Fixed-point iteration for linear problems

Stability and Convergence of Multistep Methods

Stability Analysis

• Root condition examines roots of method's characteristic polynomial
  • Polynomial derived from method's coefficients
  • Roots must lie within or on unit circle for stability
• A-stability and L-stability assess suitability for stiff problems
  • A-stable: stable for all step sizes when applied to linear test equation
  • L-stable: A-stable and solution decays rapidly for very stiff problems
• Zero-stability essential for convergence
  • Determined by method's behavior as step size approaches zero
  • Roots of first characteristic polynomial must lie within or on unit circle

Convergence Properties

• Dahlquist's barrier theorem limits maximum order of A-stable linear multistep methods
  • Order cannot exceed 2 for A-stable methods
  • Influences method selection for stiff problems
• Relative stability compares stability regions of different methods
  • Helps in choosing appropriate methods for specific problems
  • Visualized using stability region plots
• Convergence depends on consistency and zero-stability (Dahlquist equivalence theorem)
  • Consistency: local truncation error approaches zero as step size decreases
  • Zero-stability: method stable for arbitrarily small step sizes

Error Analysis

• Local truncation error (LTE) measures error introduced in a single step
  • Influenced by method's order and step size
  • Generally of the form $LTE = O(h^{p+1})$ for a p-th order method
• Global truncation error (GTE) accumulates over all steps
  • Typically one order lower than LTE
  • For a p-th order method: $GTE = O(h^p)$
• Error analysis guides step size selection and method order choice

Choosing Multistep Methods for IVPs

Problem Characteristics and Method Selection

• Choice depends on problem's characteristics:
  • Stiffness (ratio of largest to smallest eigenvalues of Jacobian)
  • Desired accuracy
  • Computational constraints (memory, processing power)
• Non-stiff problems often suit explicit methods (Adams-Bashforth)
  • Simpler implementation
  • More efficient for problems with easy function evaluations
• Stiff problems generally require implicit methods or predictor-corrector schemes
  • Ensure stability even with larger step sizes
  • Examples: Adams-Moulton, backward differentiation formulas (BDF)

Optimization and Adaptive Strategies

• Order selection balances accuracy requirements with stability and computational cost
  • Higher-order methods more accurate but potentially less stable
  • Lower-order methods more robust but may require smaller step sizes
• Variable step size implementations adaptively adjust to changing solution behavior
  • Increase step size in smooth regions
  • Decrease step size near rapid changes or discontinuities
• Variable order methods dynamically change order based on local error estimates
  • Combine benefits of high-order accuracy and low-order stability
  • Examples: VODE, LSODE solvers
• For oscillatory solutions, consider methods with extended stability along imaginary axis
  • Symplectic methods for Hamiltonian systems
  • Exponential integrators for highly oscillatory problems