Kurs:Gewöhnliche Differentialgleichungen/4.3.1 Kollokationsverfahren

Kollokationsverfahren

Der Ausdruck Kollokaltion kommt vom Wort collocate - übereinstimmen, und ist ein eleganter Weg zur Konstruktion impliziter Runge-Kutta Verfahren höherer Konsistenzordnung. Die Grundidee des Kollokationsverfahren ist die Konstruktion eines Polynoms (Kollokationspolynom $u(t)$), dessen Ableitungen $u^{\prime }(\zeta )$ an bestimmten Stellen zwischen $t_i,t_{i+1}$ mit den Ableitungen der gesuchten Funktion, $y^{\prime }(\zeta )=f(\zeta ,y(\zeta ))$ übereinstimmen. Anschließend wird das Interpolationspolynom $u^{\prime }$ zwischen $t_i,t_{i+1}$ numerisch integriert, um den Wert $u(t_{i+1})$ zu erhalten- der approximiet die neue Lösung $y(t_{i+1})$.

---

Definition 4.3 (Kollokationsverfahren)

Seien $c_1,\dots c_s\in [0,1]$ s positive, paarweise verschiedene Zahlen (Stützstellen) zwischen 0 und 1, sei $i=0,1,\dots N_h$. Das Kollokationspolynom $u$ ist definiert durch $$\begin{array}{ccc}u(t_i)& =& {\eta }_i,\\ u^{\prime }(t_i+c_{j}h)& =& f(t_i+c_{j}h,u(t_i+c_{j}h)),\end{array}$$ die neue numerische Lösung wid bestimmt als

$$\begin{array}{c}{\eta }_{i+1}:=u(t_{i+1}).\end{array}$$

---

Im Kollokationverfahren wird das Polynom $u$ in der Praxis nicht explizit berechnet, sondern als Interpolationsaufgabe (4.15), kombiniert mit anschließender numerischen Integration (intepolatorische Quadratur) realisiert. Bei diesem Vorgehen, unter Anwendung des Lagrange Interpolationspolynom in (4.15), und nach der Integration dieses Interpolationspolynoms ergibt sich ein numerisches Verfahren, das sich als Runge-Kutta Verfahren mit den s Stützstellen $c_1,\dots ,c_s$ formulieren lässt. Dieses Erkenntniss ermöglicht eine praktische Umsetzung des Kollokationsverfahrens als ein (implizites) Runge-Kutta Verfahren und wird später als Satz formuliert und konstruktiv bewiesen. Somit wird die Verbindung des Kollokationsverfahren zu iRKV deutlich, in dem das Kollokationsverfahren auf ein Runge-Kutta Verfahren mit speziellen Gewichten und Koeffizienten überführt wird. Das Kollokationsvefahren kann man daher als einen Weg zur Konstuktion spezieller iRKV auffassen.

Bevor wir den Satz über die praktische Umsetzung des Kollokationsverfahren formulieren und beweisen, machen wir einen Exkurs zu den Grundsätzen der numerischen Interpolation und Integration.

Interpolation

Gegeben sei ein Intervall $[a,b]\in ℝ$ die $n+1$ Knoten $x_0,x_1,\dots ,x_n\in [a,b]$ und die Funktionswerte $f(x_0),\dots ,f(x_n)$.
Gesucht wird ein Polynom $p_{int}\in {\mathbb{P}}^n$ des Grades $n$, sodass $$p_{int}(x_i)\stackrel{!}{=}f(x_i)\text{für}i=0,1,\dots n.$$ Das bekannteste Interploationspolynom ist das Lagrange-Interpolationspolynom, das sich als die Kombination der Lagrange-Grundpolynome ${\ell }_i\in {\mathbb{P}}^n$ zusammensetzt: $$\begin{array}{c}{p}_{int}(x)=\sum _{i=0}^{n}f(x_i){\ell }_i(x)\in {\mathbb{P}}^n,\text{mit}\\ {\ell }_i(x)=\prod _{k=1,k\ne i}^n\frac{x-x_k}{x_i-x_k}=\{\begin{array}{ccc}1& & \text{falls}x=x_i,\\ 0& & x=x_j,j\ne i\end{array}(4.16)\end{array}$$

Beispiel 4.3 (Lagrange Interpolationspolynom mit zwei Knoten)
Sei $n=1$ und die Knoten der Interpolation $x_0,x_1$. Die Lagrange-Grudpolynome zu diesen Knoten sind lineare Funktionen $${\ell }_0(x)=\frac{x-x_1}{x_0-x_1}\text{und}{\ell }_1(x)=\frac{x-x_0}{x_1-x_0}.$$

Demzufolge ist das Lagrange-Interpolationspolynom für zwei Knoten $$p_{int}(x)=f(x_0){\ell }_0(x)+f(x_1){\ell }_1(x)=f(x_0)\frac{x-x_1}{x_0-x_1}+f(x_1)\frac{x-x_0}{x_1-x_0}.$$

Für das lineare Polynom $p_{int}$, stimmt in den Knoten $x_0,x_1$ mit der zu interpolierenden Funktion $f$ überein, denn ${\ell }_0(x_0)=1,{\ell }_1(x_0)=0$ und ${\ell }_1(x_1)=1,{\ell }_0(x_1)=0$.

Beispiel 4.4 (Lagrange Interpolationspolynom mit drei Knoten)
Sei $n=2$ und $x_0,x_1,x_2$ die Knoten der Interpolation. Die Lagrange Grundpolynome zu diesen Knoten sind quadratische Funktionen $${\ell }_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)},{\ell }_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)},{\ell }_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}.$$

Das Lagrange-Interpolationspolynom für drei Knoten ist die quadratische Funktion $$\begin{array}{ccc}& & p_{int}(x)=f(x_0){\ell }_0(x)+f(x_1){\ell }_1(x)+f(x_2){\ell }_2(x)=\\ & & f(x_0)\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+f(x_1)\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}+f(x_2)\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}.\end{array}$$

In den Knoten $x_0,x_1,x_2$ stimmt $p_{int}$ mit $f$ überein, da ${\ell }_i(x_i)=1,i=1,2,3$ und ${\ell }_i(x_j)=0$ falls $i\ne j$.

Abbildung 4.2: Interpolation im Intervall $[a,b]$ mit drei Knoten: die Lagrange Grundpolynome ${\ell }_0,{\ell }_1,{\ell }_2$ und die zu interpolierende Funktion $f$.

Numerische Integration

Numerische Integration - die Quadratur - ist ein Weg das bestimmte Integral einer Funktion mit einer Summe, d.h., mit einer linearen Kombination bestimmter Funktionwerte zu approximieren und somit algoritmisch zu berechnen, $$Q[f]:=\sum _{i=0}^n{\alpha }_{i}f(x_i)\approx \underset{a}{\overset{b}{\int }}f(s)ds.(4.17)$$

$x_i$ sind die Knoten, ${\alpha }_i$ die Gewichte der Quadratur genannt.
Ein natürlicher Weg ein Integral durch Summe zu approximieren ist die Interpolatorische Quadratur: die Integration des Interpolationspolynom. Beispiel einer interpolatorischen Quadratur ist die Newton-Cotes Quadratur, hierbei wird das Lagrange-Interpolationspolynom für die zu integrierende Funktion gebildet und integriert, $$\begin{array}{c}\underset{a}{\overset{b}{\int }}f(s)ds\approx \underset{a}{\overset{b}{\int }}{p}_{int}(s)ds=\underset{a}{\overset{b}{\int }}\sum _{i=0}^{n}f(x_i){\ell }_i(s)=\sum _{i=0}^{n}f(x_i)\underset{:={\alpha }_i}{\underbrace{\underset{a}{\overset{b}{\int }}{\ell }_i(s)ds}}.(4.18)\end{array}$$

Somit is die Newton-Cotes Quadratur zu den beliebigen, paarweise verschiedenen Knoten $x_0,x_1,\dots ,x_n$ definiert durch (4.17) mit speziellen Gewichten $$Q[f]:=\sum _{i=0}^n{\alpha }_{i}f(x_i),{\alpha }_i=\underset{a}{\overset{b}{\int }}{\ell }_i(s)ds.(4.19)$$

Abbildung 4.3: Interpolatorische Quadratur von $f$ im Intervall $[a,b]$ als Integral des Lagrange Interpolationspolynom (Beispiel 4.4). Hier $Q[f]={\int }_a^b{p}_{int}$ in blau und ${\int }_a^{b}f$ in rot- gestreift.

Exaktheitsgrad einer Quadratur

ist der Grad der Polynome, für welchen die Quadratur das Integral noch exakt berechnet.

Im Falle von interpolatorischer Quadratur hängt die Exakheit der Quadratur direkt mit der Exaktheit der Interpolation zusammen. Bei $n+1$ Knoten wird ein Interpolationspolynom $n$-ten Grades eindeutig bestimmt und somit werden alle Polynome $n$-ten Grades, die in $n+1$ Knoten übereinstimmen identisch. Beispielsweise wird eine lineare Funktion durch Interpolationspolynom mit zwei Knoten, siehe Beispiel 4.3, eindeutig und exakt (ohne Fehler) dargestellt, eine quadratische Funktion ist durch Interpolationspolynom mit drei Knoten, siehe Beispiel 4.4 eindeutig und exakt bestimmt usw. Da es sich bei interpolatorische Quadratur um anschließende (exakte) Integration handelt, ist der Exakhteisgrad dieser Quadraur für frei wählbare Knotnen $x_0\ne x_1\ne \dots \ne x_n\in [a,b]$ dadurch mindestens $n$. Sind die Knoten $x_i$ der interpolatorischen Quadratur speziell gewählt, kann sogar noch höherer Exaktheitsgrad erreicht werden. Dies ist der Fall bei der Gauss-Quadraur, die bei $n+1$ speziell gewählten Knoten den maximalen Exaktheitsgrad $2n+1$ erreicht, mehr zu Gauss-Quadraur findet man z. B. in [3].

Die Anwendung der numerischen Interpolation und der Newton-Cotes (interpolatorischen) Quadratur (4.17)–(4.19) für die Ableitung des Kollokationspolynoms $u$ führt zu folgendem Satz über die prakische Anwendung des Kollokationsverfahren, wie vorher avisiert.

---

Satz 4.3 (Kollokationsverfahren als iRKV)

Das Kollokationsverfahren (4.15) ist äquivalent zu einem s-stufigem Runge-Kutta Verfahren mit den Stützstellen $c_1,\dots ,c_s$ und folgenden Koeffizienten: $$\begin{array}{ccc}{a}_{jm}=\underset{0}{\overset{c_j}{\int }}{\ell }_m(t)dt& & b_m=\underset{0}{\overset{1}{\int }}{\ell }_m(t)dt,m,j=1,\dots ,s,\\ \text{wobei}& & {\ell }_m(t)=\prod _{k=1,k\ne m}^s\frac{t-c_k}{c_m-c_k}\in {\mathbb{P}}^{s-1}\end{array}(4.20)$$ das Lagrange Grundpolynom ist.

---

Beweis

In (4.15) bezeichne $u^{\prime }(t_i+c_{j}h)=f(t_i+c_{j}h,u(t_i+c_{j}h)):=k_j$ und bilde das Interpolationspolynom auf $[t_i,t_i+h]$ für die Ableitung $u^{\prime }$ über den s Knoten $t_i+c_{j}h,j=1,\dots ,s,c_j\in [0,1]$, $$u^{\prime }(t)=\sum _{m=1}^s{k}_m{\tilde{\ell }}_m(t),{\tilde{\ell }}_j(t)=\prod _{k=1,k\ne j}^s\frac{t-(t_i+h{c}_k)}{t_i+h{c}_j-(t_i+h{c}_k)}\in {\mathbb{P}}^{s-1}.(4.21)$$

Nach der Integration ${\int }_{t_i}^{t_i+c_{j}h}dt$ erhält man mit Hilfe von $u(t_i)={\eta }_i$ aus obiger Gleichung: $$u(t_i+c_{j}h)=u(t_i)+\sum _{m=1}^s{k}_m\underset{t_i}{\overset{t_i+c_{j}h}{\int }}{\tilde{\ell }}_m(t)dt={\eta }_i+h\sum _{m=1}^s{k}_m\underset{0}{\overset{c_j}{\int }}{\ell }_m(c)dc,(4.22)$$

wobei hier die Variable-Substitution $c:=\frac{t-t_i}{h},c\in [0,1]$ vewendet wurde und ${\ell }_m$ wie im (4.20) definier ist. Integriert man nun in (4.21) bis zu $t_i+h$, so erhalten wir mit derselben Substitution, $$u(t_i+h)\mathrm{\%}=u(t_i)+\sum _{m=1}^s{k}_m\underset{t_i}{\overset{t_i+c_{j}h}{\int }}{\tilde{\ell }}_m(t)dt={\eta }_i+h\sum _{m=1}^s{k}_m\underset{0}{\overset{1}{\int }}{\ell }_m(c)dc.(4.23)$$

Bezeichnet man nun $$b_m:=\underset{0}{\overset{1}{\int }}{\ell }_m(c)dc,$$

so berechnet sich nach dem Kollokationsverfahren der neue numerische Wert ${\eta }_{i+1}$ als $u(t_i+h)$ und somit anhand von (4.23) als $${\eta }_{i+1}={\eta }_i+h\sum _{m=1}^s{k}_m{b}_m,$$ was der Form eines RK-Update entspricht, siehe (4.2).

Um das Kollokationsverfahren vollständig mit einem Runge-Kutta Verfahren zu identifizieren, müssen noch die $k_j:=f(t_i+c_{j}h,u(t_i+c_{j}h)),j=1,\dots ,s$ aus dem Anfang des Beweises mit den Funktionsauswertungen $k_j$ in den Zwischenstufen (4.1) ($k_j$ berechnet anhand einer Koeffizientenmatrix) übereinstimmen. Hierzu braucht man nur die Werte $u(t_i+c_{j}h)$ im Argument von $f$ mit Hilfe von (4.22) zu ersetzten und man erhält $$k_j:=f(t_i+c_{j}h,u(t_i+c_{j}h))=f(t_i+c_{j}h,{\eta }_i+h\sum _{m=1}^s{k}_m\underset{0}{\overset{c_j}{\int }}{\ell }_m(c)dc),$$ was mit der Bezeichnung $$a_{jm}:=\underset{0}{\overset{c_j}{\int }}{\ell }_m(c)dc$$

die Stufen $k_j$ eines (impliziten) Runge-Kutta Verfahren, (4.1), mit Koeffizientenmatrix $(A{)}_{jm}=a_{jm}$ definiert. ◻