Collocation method

A projection method for solving integral and differential equations in which the approximate solution is determined from the condition that the equation be satisfied at certain given points. For example, for the approximate solution of the integral equation

$$u(t)=\underset{a}{\overset{b}{\int }}K(t,s,u(s))ds+f(t)$$

one chooses a certain $n$- parameter family of functions $\varphi (t,c_1\dots c_n)$ and certain points (collocation knots, collocation nodes) $t_1\dots t_n$ on the interval $[a,b]$. The approximate solution $u_n(t)=\varphi (t,c_1\dots c_n)$ is determined from the conditions

$$u_n(t_i)=\underset{a}{\overset{b}{\int }}K(t_i,s,u_n(s))ds+f(t_i),i=1\dots n,$$

which represent a system of $n$ equations in the unknowns $c_1\dots c_n$. If the equation is linear and the approximate solution is sought in the form of a linear combination $u_n(t)=c_1{\varphi }_1(t)+\cdots +c_n{\varphi }_n(t)$ of the given (so-called coordinate) functions ${\varphi }_1\dots {\varphi }_n$, then the system of equations in $c_1\dots c_n$ will also be linear.

Convergence of the collocation method for linear boundary value problems.[edit]

Suppose that for $t$ on $(-1,1)$ the following boundary value problem is posed:

$$\begin{array}{}\text{(1)}& Lu=u^{(m)}+a_1(t)u^{(m-1)}+\cdots +a_m(t)u=f(t),\end{array}$$

$$\begin{array}{}\text{(2)}& \sum _{j=0}^{m-1}[{\alpha }_{ij}{u}^{(j)}(-1)+{\beta }_{ij}{u}^{(j)}(1)]=0,i=1\dots m.\end{array}$$

One looks for an approximate solution of this problem in the form where the ${\varphi }_j(t)$ are polynomials of degree $m+j-1$ satisfying the boundary conditions (2). The coefficients $c_1\dots c_n$ are determined from the linear system

$$\begin{array}{}\text{(3)}& [L{u}_n-f{]}_{t=t_i}=0,i=1\dots n,\end{array}$$

with Chebyshev nodes $t_i=t_i^{(n)}=\cos ((2i-1)\pi /2n)$, $i=1\dots n$. The following theorem [1] holds. Suppose that the functions $f$ and $a_j$, $j=1\dots m$, are continuous on $[-1,1]$ and that the boundary value problem (1), (2) has a unique solution $u(t)$. Then there exists an $n_0$ such that for $n\ge n_0$ the system (3) is uniquely solvable and

$$\underset{-1\le t\le 1}{max}|u_n^{(k)}(t)-u^{(k)}(t)|\le c{E}_n(u^{(m)})\to 0,$$

$$k=0\dots m-1,$$

$${\left\{\underset{-}{\int }{1}^1\frac{|u_n^{(m)}(t)-u^{(m)}(t){|}^2}{\sqrt{1-t^2}}dt\right\}}^{1/2}\le c{E}_n(u^{(m)})\to 0,$$

where $c=\text{ const }$,

$$E_n(v)=\underset{b_0\dots b_{n-1}}{min}\underset{-1\le t\le 1}{max}|v(t)-\sum _{j=0}^{n-1}{b}_j{t}^j|.$$

Similar results hold (see [1]) if the nodes are roots of orthogonal polynomials with respect to some weight function. For equally-spaced nodes the above method diverges. Effective computational schemes with coordinate spline functions have also been developed (see [2], [3], [4]).

References[edit]

Comments[edit]

In general, collocation schemes involve linear systems (3) where $L$ is dense (i.e. does not contain many systematical zero elements). However, by considering piecewise polynomials the efficiency is greatly enhanced (the resulting systems have a small bandwidth). Most popular are methods where the interval is divided into subintervals $(t_i,t_{i+1})$ and it is required that the (approximating) local polynomial satisfies (1) at the zeros of a Legendre or Lobatto polynomial (cf. Legendre polynomials). The numerical properties of this type of collocation go far beyond approximation considerations, as they appear to have a nice numerical stability (see Difference schemes, theory of); this makes them e.g. very suitable for solving singular perturbation problems (cf. Perturbation theory).

Apart from collocation methods for Fredholm equations and boundary value problems as discussed above, collocation has also been applied to initial-value problems and Volterra integral equations.

In [a12] and [a13] collocation methods in classical spline spaces for initial-value problems for first-order ordinary differential equations were introduced (see also [a6] for applications with low-order splines). A general analysis of polynomial spline collocation can be found in [a14]. Collocation methods in certain non-polynomial spline spaces have been studied in [a10]. A general analysis of projection methods (of which collocation is a special case) for the solution of initial-value problems for $k$- th order ordinary differential equations was given in [a11]. So-called perturbed collocation methods (which furnish an elegant framework for the study of order results for Runge–Kutta methods, cf. Runge–Kutta method) were introduced in [a15] and [a16]. This work generalizes earlier results published in [a7] and [a18]. In the latter reference it is shown that certain implicit Runge–Kutta methods are in fact collocation methods, thus linking the attainable order of such a Runge–Kutta method with that of the underlying quadrature formula. The question of superconvergence of collocation methods for first-order initial-value problems was discussed in [a1].

The idea of using elements from the space of piecewise-linear polynomials to obtain numerical approximations to solutions of Volterra integral equations is apparently due to A. Huber [a8] (see [a17]). In [a9] it was shown that Huber's method is a special case of collocation. A related method was proposed in [a2] where the kernel and forcing function of the Volterra equation are approximated by step functions. Collocation software for second-kind equations will be published in [a3] and [a4]. The recent development of collocations methods for Volterra equations is mainly due to H. Brunner. A state-of-the-art in collocation methods for Volterra equations and an extensive bibliography up to 1986 may be found in [a5].

References[edit]