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 yk at time
tk, a collocation method
approximates the solution y over the interval
[tk,
tk+1], where
tk+1 = tk +
hk, by a polynomial that satisfies the
ODE at selected collocation points within the interval
[tk,
tk+1], and whose value at
tk agrees with the given value
yk. Specifically, we determine a polynomial
p(t) of degree q satisfying
p(tk) = yk,
p′(tk + ci
hk) = f(tk +
ci hk,
p(tk + ci
hk)), i = 1,…,q ,
where c1,…,cq 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
c1 = 0 gives Euler's method,
c1 = 1 gives the backward Euler method, and
c1 = ½ gives the midpoint method.
For q = 2, the choice c1 = 0,
c2 = 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, c1 = (3 − √3)
⁄ 6, c2 = (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 y0 for the selected ODE at an initial time
t0 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:
- Using the slider, the user can select any desired size
hk for the step from
tk to
tk+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.
- 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 (tk,
yk) 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.
- 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.
- 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