8.3 Multistep methods

Multistep methods are powerful tools for solving initial value problems in differential equations. They use information from previous steps to approximate solutions, offering improved accuracy and efficiency over single-step methods for smooth, long-interval problems.

These methods come in explicit (Adams-Bashforth) and implicit (Adams-Moulton) varieties, each with unique strengths. Understanding their implementation, error analysis, and stability properties is crucial for effectively solving complex differential equations in various applications.

Multistep Methods for IVPs

Concept and Principles

Top images from around the web for Concept and Principles

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

1 of 3

Top images from around the web for Concept and Principles

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

• 

  Symmetric Hybrid Linear Multistep Method for General Third Order Differential Equations View original

  Is this image relevant?

1 of 3

• Multistep methods are numerical techniques used to solve initial value problems (IVPs) in ordinary differential equations (ODEs) by utilizing information from previous steps to approximate the solution at the current step
• Multistep methods can be classified as explicit or implicit based on how they calculate the solution at the current step
  • Explicit methods (Adams-Bashforth) calculate the solution at the current step using only the information from previous steps
  • Implicit methods (Adams-Moulton) involve the solution at the current step in the calculation, requiring the solution of a system of equations
• The general form of a linear k-step method for solving an IVP $y' = f(t, y), y(t_0) = y_0$ is: $y_{n+1} = a_1 * y_n + a_2 * y_{n-1} + ... + a_k * y_{n-k+1} + h * (b_0 * f(t_{n+1}, y_{n+1}) + b_1 * f(t_n, y_n) + ... + b_k * f(t_{n-k+1}, y_{n-k+1}))$, where $a_i$ and $b_i$ are method-specific coefficients and $h$ is the step size
• The order of a multistep method refers to the highest power of $h$ in the local truncation error, which indicates the method's accuracy

Starting Procedure

• Multistep methods require a starting procedure to generate the initial steps needed to begin the multistep process
• Common starting procedures include Runge-Kutta methods or Taylor series expansions
  • Runge-Kutta methods (RK4) provide high-order approximations for the initial steps by evaluating the derivative at multiple points within each step
  • Taylor series expansions approximate the solution at the initial steps by expanding the solution as a power series in terms of the step size and the derivatives of the function

Implementing Multistep Methods

Adams-Bashforth Methods

• Adams-Bashforth methods are explicit multistep methods that approximate the solution using a polynomial interpolation of the function values at previous steps
• The coefficients for Adams-Bashforth methods can be derived using the Newton-Gregory backward difference formula or the method of undetermined coefficients
• The second-order Adams-Bashforth method (AB2) has the form: $y_{n+1} = y_n + (h/2) * (3 * f(t_n, y_n) - f(t_{n-1}, y_{n-1}))$
  • AB2 uses the function values at the current and previous steps to approximate the solution at the next step
  • Higher-order Adams-Bashforth methods (AB3, AB4) use more previous steps to improve accuracy

Adams-Moulton Methods

• Adams-Moulton methods are implicit multistep methods that approximate the solution using a polynomial interpolation of the function values at both previous and current steps
• The coefficients for Adams-Moulton methods can be derived using the Newton-Gregory forward difference formula or the method of undetermined coefficients
• The second-order Adams-Moulton method (AM2), also known as the trapezoidal rule, has the form: $y_{n+1} = y_n + (h/2) * (f(t_{n+1}, y_{n+1}) + f(t_n, y_n))$
  • AM2 uses the function values at the current and next steps to approximate the solution, requiring the solution of a nonlinear equation at each step
  • Higher-order Adams-Moulton methods (AM3, AM4) use more steps to improve accuracy

Predictor-Corrector Methods

• Predictor-corrector methods combine an explicit method (predictor) and an implicit method (corrector) to improve accuracy and efficiency
  • The predictor step estimates the solution at the current step using an explicit method (Adams-Bashforth)
  • The corrector step refines the solution using an implicit method (Adams-Moulton)
• The Adams-Bashforth-Moulton predictor-corrector method uses an Adams-Bashforth method as the predictor and an Adams-Moulton method as the corrector
  • The predictor step provides an initial estimate for the solution at the current step, which is then used in the corrector step to improve accuracy
  • The corrector step can be applied iteratively until a desired level of accuracy is achieved

Implementation in Programming Languages

• Implementing multistep methods in programming languages involves defining the problem, initializing the solution array, implementing the starting procedure, and iterating through the steps using the chosen multistep method
• The problem definition includes specifying the differential equation, initial conditions, and the integration interval
• The solution array is initialized using the starting procedure (Runge-Kutta or Taylor series) to generate the initial steps
• The main loop iterates through the steps, applying the chosen multistep method (Adams-Bashforth, Adams-Moulton, or predictor-corrector) to calculate the solution at each step
  • The loop updates the solution array and the function values at each step
  • The loop continues until the end of the integration interval is reached

Analyzing Multistep Methods

Local and Global Truncation Errors

• The local truncation error (LTE) of a multistep method is the error introduced in a single step, assuming the previous steps are exact
  • The LTE can be determined by comparing the numerical solution with the Taylor series expansion of the true solution
  • The order of a multistep method is the highest power of $h$ in the LTE, indicating the rate at which the error decreases as the step size is reduced
• The global truncation error (GTE) is the accumulated error over the entire integration interval, which depends on the LTE and the stability of the method
  • The GTE represents the difference between the numerical solution and the true solution at the end of the integration interval
  • The GTE is influenced by the order of the method, the step size, and the stability properties

Stability Analysis

• The stability of a multistep method refers to its ability to control the growth of errors over time
• A method is said to be stable if the numerical solution remains bounded as the number of steps increases, given that the true solution is bounded
• The stability of a multistep method can be analyzed using the characteristic polynomial and the root condition
  • The characteristic polynomial is derived from the method's coefficients and represents the growth or decay of errors
  • The root condition states that a multistep method is stable if all the roots of the characteristic polynomial lie within or on the unit circle in the complex plane
  • Methods that satisfy the root condition are less prone to error propagation and provide more reliable solutions

Convergence Properties

• The convergence of a multistep method ensures that the numerical solution approaches the true solution as the step size tends to zero
• The Dahlquist equivalence theorem states that a consistent and zero-stable multistep method is convergent
  • Consistency refers to the method's ability to reproduce the differential equation as the step size approaches zero
  • Zero-stability ensures that the method's solutions remain bounded as the step size approaches zero
• Convergent multistep methods provide accurate solutions as the step size is reduced, allowing for the control of the global truncation error
  • The rate of convergence depends on the order of the method and the smoothness of the solution
  • Higher-order methods generally exhibit faster convergence rates, but may require additional computational effort

Multistep vs Single-Step Methods

Comparison of Characteristics

• Single-step methods (Euler's method, Runge-Kutta methods) calculate the solution at the current step using only the information from the immediately preceding step
  • Euler's method is a first-order single-step method that approximates the solution using the tangent line at the current point
  • Runge-Kutta methods (RK4) improve accuracy by evaluating the derivative at multiple points within each step
• Multistep methods utilize information from several previous steps to approximate the solution at the current step, potentially offering better accuracy and stability compared to single-step methods
• Single-step methods are self-starting, meaning they do not require a special starting procedure, while multistep methods need a starting procedure to generate the initial steps

Efficiency and Suitability

• Multistep methods generally require fewer function evaluations per step compared to high-order Runge-Kutta methods, making them more efficient for problems with expensive function evaluations
  • The computational cost of multistep methods depends on the number of steps used and the order of the method
  • Implicit multistep methods may require the solution of a system of equations at each step, which can increase the computational cost
• Single-step methods are more suitable for problems with discontinuities or rapidly changing solutions, as they do not rely on the smoothness of the solution over multiple steps
  • Discontinuities can cause instabilities or inaccuracies in multistep methods due to the reliance on previous steps
  • Single-step methods can adapt more easily to changes in the solution by adjusting the step size or order

Choosing the Appropriate Method

• The choice between single-step and multistep methods depends on the specific problem, the desired accuracy, the computational cost, and the smoothness of the solution
• Multistep methods are often preferred for problems with smooth solutions and long integration intervals, where their efficiency and stability can provide accurate results with fewer steps
• Single-step methods are favored for problems with discontinuities, rapidly changing solutions, or when the solution is required at specific points rather than over a continuous interval
• In practice, a combination of methods may be used, such as starting with a single-step method and switching to a multistep method once sufficient initial steps have been generated
  • This approach takes advantage of the self-starting nature of single-step methods and the efficiency of multistep methods
  • Adaptive methods can automatically switch between different methods based on the characteristics of the problem and the desired accuracy