Collocation method: Difference between revisions

Revision as of 19:34, 30 April 2008

Latest revision as of 09:17, 13 August 2025

(48 intermediate revisions by 36 users not shown)

Line 1:

{{Short description|Mathematical method for approximating solutions to differential and integral equations}}

In mathematics, a '''collocation method''' is a method for the [[numerical analysis|numerical]] solution of [[ordinary differential equation]] ands, [[partial differential equation]]s and [[integral equation]]s. The idea is to choose a finite-dimensional space of candidate solutions (usually, [[polynomial]]s 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 ==

Line 5 ⟶ 6:

Suppose that the [[ordinary differential equation]]

:<math> y'(t) = f(t,y(t)), \quad y(t_0)=y_0, </math>

is to be solved over the interval <math> [''t''t_0,t_0+h]<sub/math>0. Choose <math>c_k</submath>,&nbsp; from 0 ≤ ''tc''₀₁+''h'']. Denote the collocation points by< ''c''₁₂,&nbsp;&hellip;,&nbsp;< ... < ''c''_''n''. For≤ simplicity, it is assumed that the collocation points are all different1.

The corresponding (polynomial) collocation method approximates the solution ''y'' by the polynomial ''p'' of degree ''n'' which satisfies the initial condition ''<math>p''(''t''₀t_0)&nbsp; =&nbsp;''y''<sub>0 y_0</submath>, and the differential equation ''p''<nowikimath>p'</nowiki>(''t''t_k)&nbsp; =&nbsp;'' f''(''t''t_k,''p''(''t''t_k)) at all points ''t''&nbsp;=&nbsp;''t''<sub>0</submath>&nbsp;+&nbsp;''c''_''k''''h'' where ''k''&nbsp;=&nbsp;1,&nbsp;&hellip;,&nbsp;''n''. This gives ''n''&nbsp;+&nbsp;1 conditions, which matches the ''n''&nbsp;+&nbsp;1 parameters needed to specify a polynomial of degree ''n''.

at all ''collocation points'' <math>t_k = t_0 + c_k h</math> for <math>k = 1, \ldots, n</math>. This gives ''n''&nbsp;+&nbsp;1 conditions, which matches the ''n''&nbsp;+&nbsp;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.

<ref>{{harvnb|Ascher|Petzold|1998}}; {{harvnb|Iserles|1996|pp=43–44}}</ref>

=== Example: The trapezoidal rule ===

Pick, as an example, the two collocation points ''c''<mathsub>1</sub> c_1= 0 </math> and ''c''<mathsub> c_2=12</mathsub> = 1 (so <math>''n'' n= 2 </math>). The collocation conditions are

Pick, as an example, the two collocation points <math> c_1=0 </math> and <math> c_2=1</math> (so <math> n=2 </math>). The collocation conditions are

:<math> p(t_0) = y_0, \, </math>

:<math> p'(t_0) = f(t_0, p(t_0)), \, </math>

:<math> p'(t_0+h) = f(t_0+h, p(t_0+h)). \, </math>

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

:<math> p(t) = \alpha (t-t_0)^2 + \beta (t-t_0) + \gamma \, </math>

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

:<math>

\begin{align}

Line 27 ⟶ 34:

\end{align}

</math>

The collocation method is now given (implicitly) by

:<math> y_1 = p(t_0 + h) = y_0 + \frac12h \Big (f(t_0+h, y_1) + f(t_0,y_0) \Big), \, </math>

where <math> y_1 = p(t_0+h) </math> is the approximate solution at <math> t = t_0+h </math>.

where ''y''₁ = ''p''(''t''₀&nbsp;+&nbsp;''h'') is the approximate solution at ''t'' = ''t''₁ = ''t''₀&nbsp;+&nbsp;''h''.

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

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

:<math> y(t) = y(t_0) + \int_{t_0}^t f(\tau, y(\tau)) \,\textrm{d}\tau, \, </math>

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

=== Other examples ===

The [[Gauss–Legendre method]]s use the points of [[Gauss–Legendre quadrature]] as collocation points. The Gauss–Legendre method based on ''s'' points has order 2''s''.<ref>{{harvnb|Iserles|1996|pp=47}}</ref> All Gauss–Legendre methods are [[A-stability|A-stable]].<ref>{{harvnb|Iserles|1996|pp=63}}</ref>

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 ==

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 polynomials|orthogonal polynomial]] basis, such as the [[Legendre polynomials]].

== Applications ==

=== Motorsport ===

Top F1 teams began switching from Quasi-Static simulation to collocation methods in 2010s to simulate the time it takes for a car to go around a circuit. It is thought that Sauber were one of the first teams to make this transition. Traditional Quasi-Static simulation involves the construction of a gLat-gLong-vCar performance envelope for the car, then starting at each apex (minimum car speed) and accelerating forwards, and backwards through the braking zone using this envelope to stitch a lap together. It is a gross simplification of the problem because the envelope is steady state so ignores any of the dynamics that occur, for example, the car can switch instantaneously between understeer and oversteer.

The switch to collocation methods in simulation involved casting the entire lap as an optimisation problem, broken down by distance steps around the lap which describe the car physics at each point. The objective is to minimise laptime and error in the physics at each point. Once the optimisation is complete, the collocation method finds the minimum laptime for a particular car setup around a circuit by varying brake/throttle and steering wheel angle while obeying the physics at every point. Additional constraints can be added to the objective function alongside minimisation of laptime, such as energy constraints (fuel, electrical, tyre sliding, brakes), and temperature constraints (tyres, battery temperature), and additional controls, such as multiple throttle pedals controlling power to all four wheels can be added to the physics. This allows for extremely complex problems to be solved optimally.

== Notes ==

{{Reflist}}

== References ==

* {{Citation | last1=Ascher | first1=Uri M. | last2=Petzold | first2=Linda R. |author2-link=Linda Petzold| title=Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations | publisher=[[Society for Industrial and Applied Mathematics]] | ___location=Philadelphia | isbn=978-0-89871-412-8 | year=1998}}.

* {{Citation | last1=Hairer | first1=Ernst | last2=Nørsett | first2=Syvert Paul | last3=Wanner | first3=Gerhard | title=Solving ordinary differential equations I: Nonstiff problems | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | isbn=978-3-540-56670-0 | year=1993}}.

* {{Citation | last1=Iserles | first1=Arieh | author1-link=Arieh Iserles | title=A First Course in the Numerical Analysis of Differential Equations | publisher=[[Cambridge University Press]] | isbn=978-0-521-55655-2 | year=1996| bibcode=1996fcna.book.....I |url=https://books.google.com/books?id=7Zofw3SFTWIC&q=%22Collocation+method%22}}.

* {{Citation | last1=Wang | first1=Yingwei | last2=Chen|first2=Suqin|last3=Wu|first3=Xionghua| title=A rational spectral collocation method for solving a class of parameterized singular perturbation problems|date=2009|journal= Journal of Computational and Applied Mathematics|volume=233|issue=10|pages=2652&ndash;2660|doi=10.1016/j.cam.2009.11.011|doi-access=free}}.

*Ernst Hairer, Syvert Nørsett and Gerhard Wanner, ''Solving ordinary differential equations I: Nonstiff problems,'' second edition, Springer Verlag, Berlin, 1993. ISBN 3-540-56670-8.

*Arieh Iserles, ''A First Course in the Numerical Analysis of Differential Equations,'' Cambridge University Press, 1996. ISBN 0-521-55376-8 (hardback), ISBN 0-521-55655-4 (paperback).

{{Numerical PDE}}

{{DEFAULTSORT:Collocation Method}}

[[Category:Curve fitting]]

[[Category:Numerical differential equations]]