Collocation method (original) (raw)

From Wikipedia, the free encyclopedia

Mathematical method for approximating solutions to differential and integral equations

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 ) ) , y ( t 0 ) = y 0 , {\displaystyle y'(t)=f(t,y(t)),\quad y(t_{0})=y_{0},} {\displaystyle y'(t)=f(t,y(t)),\quad y(t_{0})=y_{0},}

is to be solved over the interval [ t 0 , t 0 + c k h ] {\displaystyle [t_{0},t_{0}+c_{k}h]} {\displaystyle [t_{0},t_{0}+c_{k}h]}. Choose c k {\displaystyle c_{k}} {\displaystyle c_{k}} from 0 ≤ _c_1< _c_2< ... < c n ≤ 1.

The corresponding (polynomial) collocation method approximates the solution y by the polynomial p of degree n which satisfies the initial condition p ( t 0 ) = y 0 {\displaystyle p(t_{0})=y_{0}} {\displaystyle p(t_{0})=y_{0}}, and the differential equation p ′ ( t k ) = f ( t k , p ( t k ) ) {\displaystyle p'(t_{k})=f(t_{k},p(t_{k}))} {\displaystyle p'(t_{k})=f(t_{k},p(t_{k}))}at all collocation points t k = t 0 + c k h {\displaystyle t_{k}=t_{0}+c_{k}h} {\displaystyle t_{k}=t_{0}+c_{k}h} for k = 1 , … , n {\displaystyle k=1,\ldots ,n} {\displaystyle k=1,\ldots ,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 coefficients c k 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 _c_1 = 0 and _c_2 = 1 (so n = 2). The collocation conditions are

p ( t 0 ) = y 0 , {\displaystyle p(t_{0})=y_{0},\,} {\displaystyle p(t_{0})=y_{0},\,}

p ′ ( t 0 ) = f ( t 0 , p ( t 0 ) ) , {\displaystyle p'(t_{0})=f(t_{0},p(t_{0})),\,} {\displaystyle p'(t_{0})=f(t_{0},p(t_{0})),\,}

p ′ ( t 0 + h ) = f ( t 0 + h , p ( t 0 + h ) ) . {\displaystyle p'(t_{0}+h)=f(t_{0}+h,p(t_{0}+h)).\,} {\displaystyle 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 ) = α ( t − t 0 ) 2 + β ( t − t 0 ) + γ {\displaystyle p(t)=\alpha (t-t_{0})^{2}+\beta (t-t_{0})+\gamma \,} {\displaystyle 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

α = 1 2 h ( f ( t 0 + h , p ( t 0 + h ) ) − f ( t 0 , p ( t 0 ) ) ) , β = f ( t 0 , p ( t 0 ) ) , γ = y 0 . {\displaystyle {\begin{aligned}\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{aligned}}} {\displaystyle {\begin{aligned}\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{aligned}}}

The collocation method is now given (implicitly) by

y 1 = p ( t 0 + h ) = y 0 + 1 2 h ( f ( t 0 + h , y 1 ) + f ( t 0 , y 0 ) ) , {\displaystyle y_{1}=p(t_{0}+h)=y_{0}+{\frac {1}{2}}h{\Big (}f(t_{0}+h,y_{1})+f(t_{0},y_{0}){\Big )},\,} {\displaystyle y_{1}=p(t_{0}+h)=y_{0}+{\frac {1}{2}}h{\Big (}f(t_{0}+h,y_{1})+f(t_{0},y_{0}){\Big )},\,}

where _y_1 = p(_t_0 + h) is the approximate solution at t = _t_1 = _t_0 + 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 ) + ∫ t 0 t f ( τ , y ( τ ) ) d τ , {\displaystyle y(t)=y(t_{0})+\int _{t_{0}}^{t}f(\tau ,y(\tau ))\,{\textrm {d}}\tau ,\,} {\displaystyle 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.

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

In fact, one can show that the order of a collocation method corresponds to the order of the quadrature rule that one would get using the collocation points as weights.

Orthogonal collocation method

[edit]

In direct collocation method, we are essentially performing variational calculus with the finite-dimensional subspace of piecewise linear functions (as in trapezoidal rule), or cubic functions, or other piecewise polynomial functions. In orthogonal collocation method, we instead use the finite-dimensional subspace spanned by the first N vectors in some orthogonal polynomial basis, such as the Legendre polynomials.

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