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 ${\textstyle u(t)}$), dessen Ableitungen ${\textstyle u'(\zeta )}$ an bestimmten Stellen zwischen ${\textstyle t_{i},t_{i+1}}$ mit den Ableitungen der gesuchten Funktion, ${\textstyle y'(\zeta )=f(\zeta ,y(\zeta ))}$ übereinstimmen. Anschließend wird das Interpolationspolynom ${\textstyle u'}$ zwischen ${\textstyle t_{i},t_{i+1}}$ numerisch integriert, um den Wert ${\textstyle u(t_{i+1})}$ zu erhalten- der approximiet die neue Lösung ${\textstyle y(t_{i+1})}$.

---

Definition 4.3 (Kollokationsverfahren)

Seien ${\textstyle c_{1},\dots c_{s}\in [0,1]}$ s positive, paarweise verschiedene Zahlen (Stützstellen) zwischen 0 und 1, sei ${\textstyle i=0,1,\ldots N_{h}}$. Das Kollokationspolynom ${\textstyle u}$ ist definiert durch

$${\begin{aligned}u(t_{i})&=&\eta _{i},\qquad \qquad \qquad \qquad \quad \\u'(t_{i}+c_{j}h)&=&f(t_{i}+c_{j}h,u(t_{i}+c_{j}h)),\end{aligned}}$$

die neue numerische Lösung wid bestimmt als

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

---

Im Kollokationverfahren wird das Polynom ${\textstyle 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 ${\textstyle c_{1},\ldots ,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 ${\textstyle [a,b]\in {\mathbb {R} }}$ die ${\textstyle n+1}$ Knoten ${\textstyle x_{0},x_{1},\ldots ,x_{n}\in [a,b]}$ und die Funktionswerte ${\textstyle f(x_{0}),\ldots ,f(x_{n})}$.
Gesucht wird ein Polynom ${\textstyle p_{int}\in {\mathbb {P} }^{n}}$ des Grades ${\textstyle n}$, sodass

$$p_{int}(x_{i}){\stackrel {!}{=}}f(x_{i})\ {\mbox{für}}\ i=0,1,\ldots n.$$

Das bekannteste Interploationspolynom ist das Lagrange-Interpolationspolynom, das sich als die Kombination der Lagrange-Grundpolynome ${\textstyle \ell _{i}\in {\mathbb {P} }^{n}}$ zusammensetzt:

$${\begin{aligned}p_{int}(x)=\sum _{i=0}^{n}f(x_{i})\ell _{i}(x)\in {\mathbb {P} }^{n},\ \qquad {\mbox{mit}}\qquad \\\ell _{i}(x)=\prod _{k=1,k\neq i}^{n}{\frac {x-x_{k}}{x_{i}-x_{k}}}=\left\{{\begin{matrix}1&&\ {\mbox{falls}}\ x=x_{i},\\0&&\ x=x_{j},\;j\neq i\end{matrix}}\right.\qquad \qquad (4.16)\end{aligned}}$$

Beispiel 4.3 (Lagrange Interpolationspolynom mit zwei Knoten)
Sei ${\textstyle n=1}$ und die Knoten der Interpolation ${\textstyle x_{0},x_{1}}$. Die Lagrange-Grudpolynome zu diesen Knoten sind lineare Funktionen

$$\ell _{0}(x)={\frac {x-x_{1}}{x_{0}-x_{1}}}\ \ {\mbox{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 ${\textstyle p_{int}}$, stimmt in den Knoten ${\textstyle x_{0},x_{1}}$ mit der zu interpolierenden Funktion ${\textstyle f}$ überein, denn ${\textstyle \ell _{0}(x_{0})=1,\ell _{1}(x_{0})=0}$ und ${\textstyle \ell _{1}(x_{1})=1,\ell _{0}(x_{1})=0}$.

Beispiel 4.4 (Lagrange Interpolationspolynom mit drei Knoten)
Sei ${\textstyle n=2}$ und ${\textstyle 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{aligned}&&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{aligned}}$$

In den Knoten ${\textstyle x_{0},x_{1},x_{2}}$ stimmt ${\textstyle p_{int}}$ mit ${\textstyle f}$ überein, da ${\textstyle \ell _{i}(x_{i})=1,i=1,2,3}$ und ${\textstyle \ell _{i}(x_{j})=0}$ falls ${\textstyle i\neq j}$.

Abbildung 4.2: Interpolation im Intervall ${\textstyle [a,b]}$ mit drei Knoten: die Lagrange Grundpolynome ${\textstyle \ell _{0},\ \ell _{1},\ \ell _{2}}$ und die zu interpolierende Funktion ${\textstyle 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 \int _{a}^{b}f(s)ds.\qquad \qquad (4.17)$$

${\textstyle x_{i}}$ sind die Knoten, ${\textstyle \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{aligned}\int _{a}^{b}f(s)ds\approx \int _{a}^{b}p_{int}(s)ds=\int _{a}^{b}\sum _{i=0}^{n}f(x_{i})\ell _{i}(s)=\sum _{i=0}^{n}f(x_{i})\underbrace {\int _{a}^{b}\ell _{i}(s)ds} _{:=\alpha _{i}}.\quad (4.18)\end{aligned}}$$

Somit is die Newton-Cotes Quadratur zu den beliebigen, paarweise verschiedenen Knoten ${\textstyle x_{0},x_{1},\ldots ,x_{n}}$ definiert durch (4.17) mit speziellen Gewichten

$$Q[f]:=\sum _{i=0}^{n}\alpha _{i}f(x_{i}),\quad \alpha _{i}=\int _{a}^{b}\ell _{i}(s)ds.\quad (4.19)$$

Abbildung 4.3: Interpolatorische Quadratur von ${\textstyle f}$ im Intervall ${\textstyle [a,b]}$ als Integral des Lagrange Interpolationspolynom (Beispiel 4.4). Hier ${\textstyle Q[f]=\int _{a}^{b}p_{int}}$ in blau und ${\textstyle \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 ${\textstyle n+1}$ Knoten wird ein Interpolationspolynom ${\textstyle n}$-ten Grades eindeutig bestimmt und somit werden alle Polynome ${\textstyle n}$-ten Grades, die in ${\textstyle 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 ${\textstyle x_{0}\neq x_{1}\neq \ldots \neq x_{n}\in [a,b]}$ dadurch mindestens ${\textstyle n}$. Sind die Knoten ${\textstyle 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 ${\textstyle n+1}$ speziell gewählten Knoten den maximalen Exaktheitsgrad ${\textstyle 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 ${\textstyle 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 ${\textstyle c_{1},\ldots ,c_{s}}$ und folgenden Koeffizienten:

$${\begin{aligned}a_{jm}=\int _{0}^{c_{j}}\ell _{m}(t)dt&&b_{m}=\int _{0}^{1}\ell _{m}(t)dt,\ m,j=1,\ldots ,s,\\{\mbox{wobei}}&&\ell _{m}(t)=\prod _{k=1,k\neq m}^{s}{\frac {t-c_{k}}{c_{m}-c_{k}}}\in {\mathbb {P} }^{s-1}\end{aligned}}\qquad (4.20)$$

das Lagrange Grundpolynom ist.

---

Beweis

In (4.15) bezeichne ${\textstyle u'(t_{i}+c_{j}h)=f(t_{i}+c_{j}h,u(t_{i}+c_{j}h)):=k_{j}}$ und bilde das Interpolationspolynom auf ${\textstyle [t_{i},t_{i}+h]}$ für die Ableitung ${\textstyle u'}$ über den s Knoten ${\textstyle t_{i}+c_{j}h,\ j=1,\ldots ,s,\ c_{j}\in [0,1]}$,

$$u'(t)=\sum _{m=1}^{s}k_{m}{\tilde {\ell }}_{m}(t),\quad {\tilde {\ell }}_{j}(t)=\prod _{k=1,k\neq j}^{s}{\frac {t-(t_{i}+hc_{k})}{t_{i}+hc_{j}-(t_{i}+hc_{k})}}\in {\mathbb {P} }^{s-1}.\quad (4.21)$$

Nach der Integration ${\textstyle \int _{t_{i}}^{t_{i}+c_{j}h}dt}$ erhält man mit Hilfe von ${\textstyle u(t_{i})=\eta _{i}}$ aus obiger Gleichung:

$$u(t_{i}+c_{j}h)=u(t_{i})+\sum _{m=1}^{s}k_{m}\int _{t_{i}}^{t_{i}+c_{j}h}{\tilde {\ell }}_{m}(t)dt=\eta _{i}+h\sum _{m=1}^{s}k_{m}\int _{0}^{c_{j}}\ell _{m}(c)dc,\qquad (4.22)$$

wobei hier die Variable-Substitution ${\textstyle c:={\frac {t-t_{i}}{h}},\ c\in [0,1]}$ vewendet wurde und ${\textstyle \ell _{m}}$ wie im (4.20) definier ist. Integriert man nun in (4.21) bis zu ${\textstyle t_{i}+h}$, so erhalten wir mit derselben Substitution,

$$u(t_{i}+h)\%=u(t_{i})+\sum _{m=1}^{s}k_{m}\int _{t_{i}}^{t_{i}+c_{j}h}{\tilde {\ell }}_{m}(t)dt=\eta _{i}+h\sum _{m=1}^{s}k_{m}\int _{0}^{1}\ell _{m}(c)dc.\qquad (4.22)$$

Bezeichnet man nun

$$b_{m}:=\int _{0}^{1}\ell _{m}(c)dc,$$

so berechnet sich nach dem Kollokationsverfahren der neue numerische Wert ${\textstyle \eta _{i+1}}$ als ${\textstyle 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 ${\textstyle k_{j}:=f(t_{i}+c_{j}h,u(t_{i}+c_{j}h)),\ j=1,\ldots ,s}$ aus dem Anfang des Beweises mit den Funktionsauswertungen ${\textstyle k_{j}}$ in den Zwischenstufen (4.1) (${\textstyle k_{j}}$ berechnet anhand einer Koeffizientenmatrix) übereinstimmen. Hierzu braucht man nur die Werte ${\textstyle u(t_{i}+c_{j}h)}$ im Argument von ${\textstyle 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{\Big (}t_{i}+c_{j}h,\eta _{i}+h\sum _{m=1}^{s}k_{m}\int _{0}^{c_{j}}\ell _{m}(c)dc{\Big )},$$

was mit der Bezeichnung

$$a_{jm}:=\int _{0}^{c_{j}}\ell _{m}(c)dc$$

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