Kapitel 7
Approximation und Interpolation
Kontext: Wir wenden nun die Idee der Basisfunktionen an, um Funktionen zu approximieren. Hierfür kommen wir zu dem Konzept des Residuums zurück. Ziel der Funktionsapproximation ist es, dass die approximierte Funktion das Residuum minimiert. Aufbauend auf diesen Ideen besprechen wir dann im nächsten Kapitel die Approximation von Differentialgleichungen.
7.1 Residuum
Im vorherigen Abschnitt haben wir beschrieben, wie mit Basisfunktionen eine Reihenentwicklung aufgebaut werden kann. Eine typische Reihenentwicklung enthält eine endliche Zahl an Elementen \(N+1\) und hat die Form \begin {equation} f_N(x) = \sum _{n=0}^N a_n \varphi _n(x), \end {equation} wobei die \(\varphi _n(x)\) die im vorherigen Kapitel eingeführten Basisfunktionen sind.
Wir wollen uns nun der Frage nähern, wie wir ein beliebige Funktion \(f(x)\) über eine solche Basisfunktionsentwicklung annähern können. Hierzu definieren wir das Residuum \begin {equation} R(x) = f_N(x) - f(x), \end {equation} welches an jedem Punkt \(x\) verschwindet wenn \(f_N(x)\equiv f(x)\). Für eine Approximation wollen wir dieses Residuum “minimieren”. (Mit minimieren ist hier gemeint, es möglichst nah an Null zu bringen.) Wir suchen also die Koeffizienten \(a_n\) der Reihenentwicklung, welche die Funktion \(f(x)\) im Sinne einer Minimierung des Residuums approximiert.
An dieser Stelle sei noch bemerkt, dass die Basisfunktionen auf dem gleichen Raum für die Zielfunktion \(f(x)\) definiert sein müssen. Für die Approximation einer periodischen Funktion \(f(x)\) sollte auch ein periodischer Basissatz verwandt werden.
7.2 Kollokation
Als erste Minimierungsstrategie wird hier die Kollokation eingeführt. In diese Methode wird verlangt, dass das Residuum an ausgewählten Kollokationspunkten \(y_n\) verschwindet, \begin {equation} R(y_n) = 0 \quad \text {bzw.}\quad f_N(y_n) = f(y_n). \end {equation} Die Anzahl der Kollokationspunkte muss hier der Anzahl der Koeffizienten in der Reihenentwicklung entsprechen. Die Wahl der idealen Kollokationspunkte \(y_n\) selbst ist nicht-trivial, und wir werden hier nur spezifische Fälle besprechen.
Als erstes Beispiel diskutieren wir hier eine Entwicklung mit \(N\) finiten Elementen. Als Kollokationspunkte wählen wir die Stützstellen der Basis, \(y_n=x_n\). An diesen Stützstellen ist nur eine der Basisfunktionen ungleich Null, \(\varphi _n(y_n)=1\) und \(\varphi _n(y_k)=0\) falls \(n\not =k\). Damit führt die Bedingung \begin {equation} R(y_n) = 0 \end {equation} trivial zu \begin {equation} a_n = f(y_n). \end {equation} Die Koeffizienten \(a_n\) sind also durch den Funktionswert der zu approximierenden Funktion am Kollokationspunkt gegeben. Die Approximation ist damit eine stückweise lineare Funktion zwischen den Funktionswerten von \(f(x)\).
Als zweites Beispiel diskutieren wir hier eine Fourier-Reihe mit entsprechenden \(2N+1\) Fourier-Basisfunktionen, \begin {equation} \varphi _n(x) = \exp \left ( i q_n x \right ). \end {equation} Im Rahmen einer Kollokationsmethode, verlangen wir, dass das Residuum auf \(2N+1\) äquidistanten Punkten verschwindet, \(R(y_n)=0\) mit \begin {equation} y_n = n L / (2N+1). \end {equation} Die Bedingung dafür lautet dann \begin {equation} \sum _{k=-N}^{N} a_k \exp \left (i q_k y_n\right ) = \sum _{k=-N}^{N} a_k \exp \left (i 2\pi \frac {k n}{2N+1}\right ) = f(y_n). \label {eq:fourier-collocation} \end {equation} Gleichungen \eqref{eq:fourier-collocation} können nun nach \(a_k\) aufgelöst werden. Wir nutzen dazu, dass für äquidistanter Kollokationspunkte die Fourier-Matrix \(W_{kn}=\exp (i2\pi kn/(2N+1))\) (bis auf einen Faktor) unitär ist, d.h. ihr Inverses ist durch die Adjungierte gegeben: \(\sum _n W_{kn} W_{nl}^* = (2N+1)\delta _{kl}\). Wir können also Gl. \eqref{eq:fourier-collocation} mit \(W_{nl}^*\) multiplizieren und über \(n\) summieren. Dies ergibt \begin {equation} \sum _{n=-N}^{N} \sum _{k=-N}^{N} a_k \exp \left [i 2\pi \frac {(k - l) n}{2N+1}\right ] = \sum _{k=-N}^{N} N a_k \delta _{kl} = N a_l \end {equation} wobei \begin {equation} \sum _{n=-N}^{N} \exp \left [i 2\pi \frac {(k - l) n}{2N+1}\right ] = (2N+1)\delta _{kl} \end {equation} genutzt wurde. Damit können die Koeffizienten als \begin {equation} a_l = \frac {1}{2N+1} \sum _{n=-N}^{N} f\left (\frac {nL}{2N+1}\right ) \exp \left (-i 2\pi \frac {l n}{2N+1}\right ), \end {equation} bestimmt werden. Dies ist die diskrete Fourier-Transformation der auf den Kollokationspunkten diskretisierten Funktion \(f(y_n)\).
Als einfaches Beispiel zeigen wir hier Approximation der Beispielfunktion \(f(x)=\sin (2\pi x)^3 + \cos (6\pi (x^2-1/2))\) mit Hilfe der Fourier-Basis und der finiten Elemente. Abbildung 7.2 zeigt diese Approximation für \(2N+1=5\) und \(2N+1=11\) Basisfunktionen mit äquidistanten Kollokationspunkten.
Die Abbildung zeigt, dass alle Approximationen, wie von der Kollokationsbedingung verlangt, exakt durch die Kollokationspunkte laufen. Zwischen den Kollokationspunkten interpolieren die beiden Ansätze unterschiedlich. Die finiten Elementen führen zu einer linearen Interpolation zwischen den Punkten. Die Fourier-Basis ist komplizierter. Der Kurvenverlauf zwischen den Kollokationspunkten wird Fourier-Interpolation genannt.
7.3 Gewichtete Residuen
Wir möchten nun die Kollokationsmethode verallgemeinern. Hierzu führen wir das Konzept der Testfunktion ein. Anstelle zu verlangen, dass das Residuum an individuellen Punkten verschwindet, verlangen wir, dass das Skalarprodukt \begin {equation} (v, R) = 0 \label {eq:test-function} \end {equation} mit einer Funktion \(v(x)\) verschwindet. Wenn Gl. \eqref{eq:test-function} für jede beliebigen Testfunktion \(v(x)\) verschwindet, dann ist die “schwache” Formulierung Gl. \eqref{eq:test-function} identisch zur starken Formulierung \(R(x)=0\). Gleichung \eqref{eq:test-function} heißt “schwache” Formulierung, weil die Bedingung nur im integralen Sinne erfüllt ist. Insbesondere wird in Kapitel 9 gezeigt, dass diese schwache Formulierung zu einer schwachen Lösung (engl. “weak solution”) führt, die die ursprüngliche (starke) PDGL nicht in jedem Punkt erfüllen kann. Die Bedingung \eqref{eq:test-function} wird oft unter dem Begriff der gewichteten Residuen subsumiert.
Ein spezieller Satz an Testfunktion führt direkt zur Kollokationsmethode. Wir wählen den Satz von \(N\) Testfunktionen \begin {equation} v_n(x) = \delta (x-y_n) \label {eq:colloctest} \end {equation} wobei \(\delta (x)\) die Diracsche \(\delta \)-Funktion ist und \(y_n\) die Kollokationspunkte. Die Bedingung \((v_n,R)=0\) für alle \(n\in [0,N-1]\) führt direkt zur Kollokationsbedingung \(R(y_x)=0\).
Anmerkung: Die Diracsche \(\delta \)-Funktion sollte aus Vorlesungen zur Signalverarbeitung bekannt sein. Die wichtigste Eigenschaft dieser Funktion ist die Filtereigenschaft, \begin {equation} \int _{-\infty }^{\infty } \dif x\, f(x) \delta (x-x_0) = f(x_0), \end {equation} also das Integral über das Produkt der \(\delta \)-Funktion ergibt den Funktionswert, bei dem das Argument der \(\delta \)-Funktion verschwindet. Hieraus folgen alle weiteren Eingenschaften, z.B. \begin {equation} \int \dif x\, \delta (x) = \Theta (x), \end {equation} wobei \(\theta (x)\) die (Heaviside-)Stufenfunktion ist.
7.4 Galerkin-Methode
Die Galerkin-Methode basiert auf der Idee, als Testfunktionen die Basisfunktionen \(\varphi _n\) der Reihenentwicklung zu verwenden. Dies führt zu den \(N\) Bedingungen \begin {equation} (\varphi _n, R) = 0, \label {eq:galerkinortho} \end {equation} bzw. \begin {equation} (\varphi _n, f_N) = (\varphi _n, f). \end {equation}
Für einen orthogonalen Satz von Basisfunktionen erhält man direkt \begin {equation} a_n = \frac {(\varphi _n, f)}{(\varphi _n, \varphi _n)}. \end {equation} Dieser Ansatz wurde bereits in Abschnitt ?? diskutiert.
Für einen nicht-orthogonalen Basissatz, z.B. der Basis der finiten Elemente, erhält man ein lineares Gleichungssystem, \begin {equation} \sum _{m=0}^N (\varphi _n,\varphi _m) a_m = (\varphi _n, f), \label {eq:galerkin-coefficients} \end {equation} wobei die Matrix \(A_{nm}=(\varphi _n,\varphi _m)\) für die finiten Elemente dünnbesetzt ist.
Wir wollen nun wieder zu unserer Beispielfunktion \(f(x)=\sin (2\pi x)^3 + \cos (6\pi (x^2-1/2))\) zurückkommen. Abbildung 7.2 zeigt die Approximation dieser Funktion mit Fourier und finite Elemente Basissätzen und der Galerkin-Methode. Es gibt keine Kollokationspunkte und die Approximation mit Hilfe der finiten Elemente stimmt auch nicht an den Stützstellen exakt mit der zu approximierenden Funktion überein. Die Funktion wird nur im integralen Sinne approximiert.
Anmerkung: Die Galerkin-Bedingung (siehe auch Gl. \eqref{eq:galerkinortho}) \begin {equation} (\varphi _n, R) = 0, \end {equation} bedeutet, dass das Residuum orthogonal zu allen Basisfunktionen ist. Anders ausgedrückt, im Residuum können nur noch Beiträge zur Funktion vorkommen, die nicht mit dem gegeben Basissatz abgebildet werden können. Das heißt aber auch, dass wir durch Erweiterung des Basissatzes unsere Lösung systematisch verbessern können.
7.5 Minimales Fehlerquadrat
Ein alternativer Ansatz zur Approximation ist es, das Fehlerquadrat des Residuums, \((R, R)\), zu minimieren. Für eine allgemeine Reihenentwicklung mit \(N\) Basisfunktionen erhält man \begin {equation} \begin {split} (R, R) &= (f, f) + (f_N, f_N) - (f_N, f) - (f, f_N) \\ &= (f, f) + \sum _{n=0}^N \sum _{m=0}^N a_n^* a_m (\varphi _n, \varphi _m) - \sum _{n=0}^N a_n^* (\varphi _n, f) - \sum _{n=0}^N a_n (f, \varphi _n). \end {split} \end {equation} Diese Fehlerquadrat ist dann minimiert, wenn \begin {equation} \frac {\partial (R,R)}{\partial a_k} = \sum _{n=0}^N a_n^* (\varphi _n, \varphi _k) - (f, \varphi _k) = 0 \end {equation} und \begin {equation} \frac {\partial (R,R)}{\partial a^*_k} = \sum _{n=0}^N a_n (\varphi _k, \varphi _n) - (\varphi _k, f) = 0. \end {equation} Dieser Ausdruck ist identisch zu Gl. \eqref{eq:galerkin-coefficients} der Galerkin-Methode.