I am studying numerical methods for ODEs. At the moment I am trying to get the big-picture of collocation methods. As I understand it, there are two main things: Where to set the so called "collocation points" and how to interpolate these points (interpolation polynomials).
My question: Is it correct, that "quadrature methods (like Gauss, Radau, Lobatto)" define where to set the collocation points and the "Lagrange interpolation polynomial" interpolates between these points?
Given an ODE: $\dot y = f\big(y(t),t\big)$
What is the main difference between collocation methods and Runge-Kutta methods? Given the collocation points $n_k$, how do I calculate $y(n_k), \dot y(n_k)$ on an intervall $[t_0,t_0+h]$?
Best Answer
This answer will more or less be a summary of selected parts from chapter 2, in the book Geometric Numerical Integration, 2nd edition, by Hairer (not the Fields medalist, but his dad), Lubich and Wanner.
By definition, a collocation method is specified by choosing distinct real numbers $c_1,\ldots,c_s$ (often from the interval $[0,1]$), and by defining the so called collocation polynomial $u(t)$ of degree $s$ via the conditions
The numerical solution is denoted $y_1=u(t_0+h)$.
So indeed, the $c_i$ determine the intervals on which we must interpolate the solution. As for the connection to quadrature methods, these $c_i$ are given in the leftmost column of the Butcher tableau (this would answer the first half of the question "Is it correct..."). And yes, we will need to interpolate between the collocation points using the Lagrange interpolation polynomial in the following (answering the second half of the "Is it correct" question).
So, what is the difference between collocation and Runge-Kutta? Short answer - there is (almost, see the comments below) none:
Recall that an $s$-stage Runge-Kutta method is given by
where $c_i=\sum_{j=1}^sa_{ij}$
A theorem by Guillou and Soulé (1969), also proven by Wright (1970) show that the collocation method defined above is actually equivalent to an $s$-stage Runge-Kutta with coefficients
where $l_i$ is the Lagrange interpolation polynomial $l_i(\tau)=\prod_{l\neq i} \frac{\tau-c_l}{c_i-c_l}$.
Proof: Using the same notations as above, we define $k_i:=\dot{u}(t_0+c_ih)$. By Lagrange interpolation we have $\dot{u}(t_0+\tau h)=\sum_{j=1}^s k_jl_j(\tau)$, and if we integrate this from $0$ to $c_i$ we have $$u(t_0+c_ih)=y_0+h\sum_{j=1}^s k_j \int^{c_i}_0 l_j(\tau) d\tau=y_0+h\sum_{j=1}^s k_j a_{ij}$$ Insert this into condition 2 for the collocation polynomial above, and we get
$$k_i=\dot{u}(t_0+c_ih)=f(t_0+c_ih, u(t_0+c_ih))= f(t_0+c_ih, y_0+h\sum_{j=1}^s k_j a_{ij}),$$ so we have retrieved the $k_i$ from the definition of the Runge-Kutta above.
If we integrate $\dot{u}(t_0+\tau h)$ from $0$ to $1$ instead of only to $c_i$, we get
$$u(t_0+h)=y_0+h\sum_{j=1}^s k_j \int^{1}_0 l_j(\tau) d\tau=y_0+h\sum_{j=1}^s k_j b_{j},$$
and since we defined $y_1=u(t_0+h)$ for the collocation method and the obtained expression for $y_1$ agrees with that of the Runge-Kutta above, we have established that $y_1$ is the same for both collocation and Runge-Kutta. The reasoning is reversible, so any Runge-Kutta is in the same manner equivalent to some collocation method. Proof complete.
As for concrete computation using collocation, you just have to find the collocation polynomial from the conditions 1 and 2 above. You might end up with an implicit scheme. See https://en.wikipedia.org/wiki/Collocation_method for a concrete example and some links to further references.