3.3 Backward Differentiation Formulas (BDF)

Backward Differentiation Formulas (BDF) are powerful tools for solving stiff ordinary differential equations. These implicit methods offer superior stability, making them ideal for problems with multiple time scales that would cause explicit methods to struggle.

BDF methods work by interpolating the solution at previous points and evaluating the derivative at the current point. Their implementation involves discretizing the ODE and solving a nonlinear system at each step, often using iterative methods like Newton's method or fixed-point iteration.

Backward Differentiation Formulas

Formulation and Properties

Top images from around the web for Formulation and Properties

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

• 

  An Adaptive Time-Step Backward Differentiation Algorithm to Solve Stiff Ordinary Differential ... View original

  Is this image relevant?

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

1 of 3

Top images from around the web for Formulation and Properties

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

• 

  An Adaptive Time-Step Backward Differentiation Algorithm to Solve Stiff Ordinary Differential ... View original

  Is this image relevant?

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

• 

  Frontiers | Composite Backward Differentiation Formula for the Bidomain Equations View original

  Is this image relevant?

1 of 3

• BDF methods are a class of implicit linear multistep methods used for solving stiff ordinary differential equations (ODEs)
• The general form of a k-step BDF method is: $\sum_{i=0}^k \alpha_i y_{n-i} = h \beta f(t_n, y_n)$
  • $\alpha_i$ and $\beta$ are method-specific coefficients
  • $h$ is the step size
  • $f$ is the right-hand side of the ODE
• BDF methods are derived by interpolating the solution at $k$ previous points and evaluating the derivative at the current point $t_n$
• The order of a BDF method is determined by the number of steps $k$ used in the formula
  • Higher-order methods provide better accuracy but require more computational effort
• The coefficients $\alpha_i$ and $\beta$ are chosen to ensure the method's stability and accuracy properties

Suitability for Stiff ODEs

• BDF methods are particularly well-suited for stiff ODEs due to their superior stability properties compared to explicit methods
• Stiff ODEs are characterized by the presence of multiple time scales and require methods with good stability properties to avoid excessively small step sizes
• BDF methods can efficiently solve stiff ODEs without the need for extremely small step sizes, making them computationally advantageous
• Examples of stiff ODEs include chemical kinetics problems and electrical circuit simulations

Implementing BDF Methods

Discretization and Nonlinear System Solving

• Implementing BDF methods involves discretizing the ODE using the BDF formula and solving the resulting nonlinear system at each time step
• The nonlinear system can be solved using iterative methods such as Newton's method or fixed-point iteration
  • Newton's method requires the computation of the Jacobian matrix and solves a linear system at each iteration
  • Fixed-point iteration is simpler to implement but may converge slower than Newton's method
• To initialize the BDF method, a suitable starting procedure (e.g., Runge-Kutta methods) is used to compute the solution at the first $k$ points
  • Runge-Kutta methods are explicit methods that can provide accurate initial values for the BDF method
  • The order of the Runge-Kutta method should be at least as high as the order of the BDF method to ensure consistent accuracy

Variable Step Size Adaptation

• Variable step size adaptation can be incorporated into BDF methods to improve efficiency and accuracy
• Step size selection strategies, such as the PI controller or the PID controller, can be used to adjust the step size based on local error estimates
  • The PI controller adjusts the step size based on the current and previous error estimates
  • The PID controller additionally considers the rate of change of the error estimate for better step size control
• When changing the step size, the coefficients $\alpha_i$ and $\beta$ need to be recomputed to maintain the method's stability and accuracy properties
• Variable step size adaptation allows the method to use larger step sizes when the solution is smooth and smaller step sizes when the solution varies rapidly
• Examples of problems benefiting from variable step size include chemical reactions with varying time scales and mechanical systems with impact events

Stability and Convergence of BDF

Stability Analysis

• BDF methods have excellent stability properties, making them suitable for solving stiff ODEs
• The stability region of a BDF method can be analyzed using the method's characteristic polynomial and the resulting root condition
• A-stability is a desirable property for stiff ODEs, which means that the method is stable for all linear problems with eigenvalues in the left half-plane
  • A-stability ensures that the numerical solution remains bounded for any step size
• BDF methods of order 1 and 2 are A-stable, while higher-order BDF methods (up to order 6) are A($\alpha$)-stable
  • A($\alpha$)-stability means the method is stable in a wedge-shaped region of the left half-plane with an angle $\alpha$
  • The value of $\alpha$ decreases as the order of the BDF method increases

Convergence Properties

• The convergence of BDF methods can be studied using the concept of zero-stability and consistency
• BDF methods are zero-stable for orders up to 6, ensuring that the global error remains bounded as the step size tends to zero
  • Zero-stability is a necessary condition for convergence and ensures that the method does not amplify errors over long time intervals
• The order of convergence of a BDF method is equal to its order of accuracy, provided that the method is zero-stable and consistent
  • Consistency means that the local truncation error of the method tends to zero as the step size tends to zero
• The global error of a BDF method of order $p$ is proportional to $h^p$, where $h$ is the step size
  • Reducing the step size by a factor of 2 reduces the global error by a factor of $2^p$, demonstrating the method's convergence rate

BDF vs Other Multistep Methods

Comparison with Adams Methods

• BDF methods can be compared with other linear multistep methods, such as Adams-Bashforth (explicit) and Adams-Moulton (implicit) methods
• For stiff ODEs, BDF methods generally outperform explicit methods like Adams-Bashforth due to their superior stability properties
  • Explicit methods may require extremely small step sizes to maintain stability for stiff problems
• When compared to other implicit methods like Adams-Moulton, BDF methods often provide a better balance between stability and accuracy
  • Adams-Moulton methods have a larger stability region than BDF methods but may be less accurate for the same order
• The efficiency of BDF methods can be assessed by considering the number of function evaluations and linear system solves required per step
  • BDF methods typically require one function evaluation and one linear system solve per step
  • Adams-Moulton methods may require multiple function evaluations and linear system solves per step, depending on the implementation

Efficiency and Accuracy Considerations

• Higher-order BDF methods (up to order 6) can achieve better accuracy than lower-order methods, but they may require more computational effort per step
  • The increased accuracy of higher-order methods can allow for larger step sizes while maintaining the desired error tolerance
  • The computational cost per step increases with the order of the method due to the larger nonlinear systems that need to be solved
• The choice between BDF methods and other multistep methods depends on the specific problem, the desired accuracy, and the available computational resources
  • For highly stiff problems, BDF methods are often the preferred choice due to their strong stability properties
  • For moderately stiff problems, Adams-Moulton methods may be more efficient if high accuracy is not required
  • The performance of different methods can be compared by measuring the computational time and the achieved accuracy for a given problem