Collocation method

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a collocation method is a method for the numerical solution of ordinary differential equations, partial differential equations and integral equations. The idea is to choose a finite-dimensional space of candidate solutions (usually, polynomials up to a certain degree) and a number of points in the domain (called collocation points), and to select that solution which satisfies the given equation at the collocation points.

Ordinary differential equations[edit]

Suppose that the ordinary differential equation

 y'(t) = f(t,y(t)), \quad y(t_0)=y_0,

is to be solved over the interval [t0t0 + h]. Choose 0 ≤ c1< c2< … < cn ≤ 1.

The corresponding (polynomial) collocation method approximates the solution y by the polynomial p of degree n which satisfies the initial condition p(t0) = y0, and the differential equation p'(t) = f(t,p(t)) at all points, called the collocation points, t = t0 + ckh where k = 1, …, n. This gives n + 1 conditions, which matches the n + 1 parameters needed to specify a polynomial of degree n.

All these collocation methods are in fact implicit Runge–Kutta methods. The coefficient ck in the Butcher tableau of a Runge–Kutta method are the collocation points. However, not all implicit Runge–Kutta methods are collocation methods. [1]

Example: The trapezoidal rule[edit]

Pick, as an example, the two collocation points c1 = 0 and c2 = 1 (so n = 2). The collocation conditions are

 p(t_0) = y_0, \,
 p'(t_0) = f(t_0, p(t_0)), \,
 p'(t_0+h) = f(t_0+h, p(t_0+h)). \,

There are three conditions, so p should be a polynomial of degree 2. Write p in the form

 p(t) = \alpha (t-t_0)^2 + \beta (t-t_0) + \gamma \,

to simplify the computations. Then the collocation conditions can be solved to give the coefficients

 
   \begin{align}
   \alpha &= \frac{1}{2h} \Big( f(t_0+h, p(t_0+h)) - f(t_0, p(t_0)) \Big), \\
   \beta &= f(t_0, p(t_0)), \\
   \gamma &= y_0. 
   \end{align}

The collocation method is now given (implicitly) by

 y_1 = p(t_0 + h) = y_0 + \frac12h \Big (f(t_0+h, y_1) + f(t_0,y_0) \Big), \,

where y1 = p(t0 + h) is the approximate solution at t = t0 + h.

This method is known as the "trapezoidal rule" for differential equations. Indeed, this method can also be derived by rewriting the differential equation as

 y(t) = y(t_0) + \int_{t_0}^t f(\tau, y(\tau)) \,\textrm{d}\tau, \,

and approximating the integral on the right-hand side by the trapezoidal rule for integrals.

Other examples[edit]

The Gauss–Legendre methods use the points of Gauss–Legendre quadrature as collocation points. The Gauss–Legendre method based on s points has order 2s.[2] All Gauss–Legendre methods are A-stable.[3]

Notes[edit]

  1. ^ Ascher & Petzold 1998; Iserles 1996, pp. 43–44
  2. ^ Iserles 1996, pp. 47
  3. ^ Iserles 1996, pp. 63

References[edit]