Interactive Educational Modules in
Scientific Computing

Collocation Methods for Initial Value Problems

This module illustrates collocation methods for numerically solving initial value problems for ordinary differential equations. A numerical method for an ordinary differential equation (ODE) generates an approximate solution step-by-step in discrete increments across the interval of integration. Given an ODE y′ = f(t, y) and an approximate solution value y_k at time t_k, a collocation method approximates the solution y over the interval [t_k, t_k+1], where t_k+1 = t_k + h_k, by a polynomial that satisfies the ODE at selected collocation points within the interval [t_k, t_k+1], and whose value at t_k agrees with the given value y_k. Specifically, we determine a polynomial p(t) of degree q satisfying

p(t_k) = y_k,
p′(t_k + c_i h_k) = f(t_k + c_i h_k, p(t_k + c_i h_k)), i = 1,…,q ,

where c₁,…,c_q are distinct values between 0 and 1. Solving the foregoing system of q+1 equations uniquely determines the q+1 coefficients of the polynomial p(t) of degree q. Unlike many other numerical methods for ODEs, which produce only a table of values of the approximate solution at discrete points, collocation methods provide a continuous approximation to the solution by a piecewise polynomial.

The number and location of collocation points determine different methods. For q = 1, for example, the choice c₁ = 0 gives Euler's method, c₁ = 1 gives the backward Euler method, and c₁ = ½ gives the midpoint method. For q = 2, the choice c₁ = 0, c₂ = 1 gives the trapezoid method. More generally, it can be shown that a collocation method is equivalent to a q-stage (usually implicit) Runge-Kutta method. As with numerical quadrature, choosing the collocation points to be equally spaced does not yield the highest possible order of accuracy, and using instead the Gauss points of Gaussian quadrature (for q = 2, for example, c₁ = (3 − √3) ⁄ 6, c₂ = (3 + √3) ⁄ 6) yields much greater accuracy for a given value of q.

The user begins by selecting a differential equation and the number and location of collocation points from the menus provided. A solution value y₀ for the selected ODE at an initial time t₀ is marked in the left panel with a black dot. The exact solution curve for the resulting initial value problem is drawn in the left panel in black. Starting from the initial value, the user advances the solution through successive steps using the selected collocation method. The right panel will show the polynomial to be computed as part of each step. Each step of the method is presented as a four-stage process. Each stage is executed by clicking either Next or the currently highlighted stage:

1. Using the slider, the user can select any desired size h_k for the step from t_k to t_k+1, subject to minimum and maximum allowed values. A red horizontal line in the left panel indicates the length of the step to be taken. Once the user has set the slider for the desired step size, this choice takes effect by clicking Choose Step Parameters or Next, which changes the color of the line from red to black, indicating that the length of this step is now fixed.
2. The next stage is to solve the collocation system to determine the coefficients of the polynomial p(t). The resulting polynomial is drawn in the right panel in green, along with the exact solution through the point (t_k, y_k) drawn in black. The derivative values used in determining the polynomial are shown as tangent lines drawn in yellow. Exact solutions of the ODE passing through each collocation point are drawn in gray. If the iterative solution process for determining the polynomial coefficients fails, then the step size should be decreased or the number of collocation points increased.
3. The current step is concluded by clicking Take Step or Next. The approximate and true solution values at the new point are recorded in the table below, and in the left panel the polynomial approximation to the solution over the current step is drawn in green and the exact solution to the ODE passing through the new point is drawn in gray.
4. Preparation for another step is initiated by clicking Initialize Next Step or Next, which displays the new step in red, ready for selecting the new step parameters, with a default step size equal to the size of the previous step, if possible. The number and location of collocation points can be changed for each step, if desired.

Successive steps may be continued until the the interval has been fully traversed.

Reference: E. Hairer, C. Lubich, and G. Wanner, Geometric Numerical Integration, Springer, New York, 2002. See Section II.1.2, pages 26-31.

Developers: Evan VanderZee and Michael Heath