[WS] Trigonometrische Interpolation

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Trigonometrische Interpolation
Gliederung

  1. Bezug zur Analysis

    1a. Definition trigonometrisches Polynom
    1b. Cosinus-Sinus-Darstellung
    1c. Vektorraum der trigonometrischen Polynome

  2. Approximation von Funktionen durch Fourierpolynome

    2a. Fourierreihe und Konvergenz
    2b. Fourierreihen von ungeraden Funktionen - reine Sinusreihe
    2c. Fourierreihen von geraden Funktionen - reine Cosinusreihe
    2d. Periodische Funktionen selbst gemacht

  3. Trigonometrische-Interpolations-Aufgabe (TIPA)

    3a. Darstellung 1
    3b. Darstellung 2
    3c. Existenz und Eindeutigkeit
    3d. Hilfsresultate
    3e. Berechnung der gesuchten Koeffizienten d

  4. Diskrete Fourier Analyse (DFA)

    4a. Eigenschaften der Koeffizienten d
    4b. Zerlegung des in 2 Polynome
    4c. Eigenschaften der beiden Polynome an den Knoten
    4d. Berechnung der Koeffizienten d
    4e. Berechnung der Koeffizienten a,b
    4f. Das gesuchte Polynom

  5. Unterschiede zwischen Approximation und Interpolation

    5a. Approximationspolynom
    5b. Lösung TIPA
    5c. Lösung DFA
    5d. Bemerkung

  6. Fast-Fourier-Transformation (FFT) - Auswertung von trig. Polynomen

    6a. Berechnung der Koeffizienten d
    6b. Gerades N=2M
    6c. N ist eine Zweierpotenz
    6d. Beispielschema

  7. Umsetzung am PC
    7a. Koeffizienten-Näherungen
    7b. "alte Bekannte"
    7c. Effiziente Berechnung

  8. Eine einfache Erklärung der Fouriertransformation
    8a. Filterung der Sinusanteile
    8b. Filterung der Cosinusanteile
    8c. Filterung eines phasenverschobenen Sinus
    8d. Filterung des Mittelwertes

tigerbine Auf diesen Beitrag antworten »
1a. Definition trigonometrisches Polynom
Unter einem trig. Polynom vom Grad N versteht man die Abbildung mit folgender Definition:

 
 
tigerbine Auf diesen Beitrag antworten »
1b. Cosinus-Sinus-Darstellung
Diese Darstellung kann man mittels der Substitution durch geschicktes Zusammenfassung wie folgt umrechnen:



______________________________________________________________

Dabei gilt für die Umrechnung:



tigerbine Auf diesen Beitrag antworten »
1c. Vektorraum der trigonometrischen Polynome



Beweis:
  • Der Nachweis der Vektorraumaxiome erfolgt intuitiv, da die Summe zweier trig. Polynome mit Grad wieder ein trig. Polynom mit Grad ist.

  • Ebenso verifiziert man die abelsche Gruppe mit neutralem Element 0(-Funktion)

  • Weiter ist durch die Definition ersichtlich, dass ein Erzeugendensystem von bilden

  • Somit bleibt die Lineare Unabhängigkeit zu zeigen. Dies macht man dadurch, dass man zeigt, dass die Basisfunktionen paarweise orthogonal sind.

    Man verwendet das Skalarpodukt:



    Desweiteren gilt:



    Damit folgt:



    Denn:




tigerbine Auf diesen Beitrag antworten »
2. Approximation von Funktionen durch Fourierpolynome
Trigonometrische Polynome kann man nun z.B. zur Approximation von 2-periodischen Funktionen f verwenden. Es soll hier die Cosinus-Sinus-Darstellung verwendet werden. Gilt für die Koeffizienten a,b:




so nennt man das trig. Polynom N-tes Fourierpolynom von f:





Wie man auch nicht periodische Funktionen approximieren kann wird in 2.d gezeigt.
________________________________________________________________
Lehrer Trigonometrische Polynome werde oft auch allgemein als Fourier-Polynome bezeichnet. Dabei müssen die Koeffizienten a,b aber nicht obige Gestalt haben.
tigerbine Auf diesen Beitrag antworten »
2a. Fourierreihe und Konvergenz
Unter der Fourierreihe einer 2-periodischen Funktion f versteht man die Folge der Fourierpolyme von f und im Konvergenzfall auch den Grenzwert.





Was läßt sich nun über das Konvergenzverhalten aussagen?

Satz von Carleson, (1964)

Die Fourrierriehe jeder stetigen 2-periodischen Funktion f konvergiert fast überall gegen f.

Fast überall bedeutet hier: Es gibt eine Ausnahmemenge A vom Lebesgue-Maß 0, so dass gilt.


Satz von Dirichlet

Sei f eine 2 periodische Regelfunktion und besitze im Punkt sowohl eine linksseitige als auch rechtsseitige Ableitung. Dann konvergiert die Fourrierreihe in x gegen das arithmetische Mittel der linksseitigen und rechtsseitigen Grenzwertes von f in x:



Ist f stetig in x, so gilt:





Darstellungssatz

Falls die Fourierreihe einer 2-periodischen Regelfunktion f in einem Punkt x konvergiert, gilt:




____________________________________________________________

Definition (Regelfunktion)
Sei I ein Intervall mit Anfangspunkt a und Endpunkt b. Eine Funktion heiß Regelfunktion auf I, wenn sie
  1. in jedem Punkt sowohl einen linksseitigen als auch einen rechtsseitigen Grenzwert hat,
  2. im Fall in A einen rechtsseitigen und im Fall in b einen linksseitigen Grenzwert hat.

Die Regelfunktionen auf I bilden einen -Vektorraum.
_____________________________________________________________

Lehrer Dass die Stetigkeit alleine nicht reicht, zeigt z.B. das Beispiel von Fejér (vgl. Königsberger Analysis I, 5. Auflage S. 332)
tigerbine Auf diesen Beitrag antworten »
2b. Fourierreihen von ungeraden Funktionen - reine Sinusreihe
Sei nun f eine ungerade -periodische Funktion, d.h. es gilt




Dann gilt für die Koeffizienten des N-ten Fourierpolynoms von f:


Und es ist:




Beweis:

Wichtige Umformung (*)

k=0:




k > 0:

Für k > 0 ist eine - periodische gerade Funktion und es gilt . Somit ist auch eine - periodische gerade Funktion.

tigerbine Auf diesen Beitrag antworten »
2c. Fourierreihen von geraden Funktionen - reine Cosinusreihe
Sei nun f eine gerade -periodische Funktion, d.h. es gilt





Dann gilt für die Koeffizienten des N-ten Fourierpolynoms von f:




Und es ist:

tigerbine Auf diesen Beitrag antworten »
2d. Periodische Funktionen selbst gemacht
  1. Nichtperiodische Funktion

    Sei eine stetige Funktion, so kann man sie wie folgt zu einer 2-periodischen Funktion machen:



    Die Motivation für den Funktionswert am Intervallrand x=0 ist der Darstellungssatz, welcher sich aus dem Satz von Fejér ergibt.

  2. Nur auf definierte Funktion

    Wie sollte man diese auf das Intervall fortsetzen? Für die Intervallränder gilt wieder das Vorgehen gemäß Darstellungssatz. Für das Intervallinnere gibt es die Möglichkeit eine gerade oder ungerade Funktion zu kreieren. Beispiele:

    • ungerade Fortsetzung von auf mit



      Falls in einseitig diff'bar war, dann ist stetig diff'bar.






    • gerade Fortsetzung von auf mit




tigerbine Auf diesen Beitrag antworten »
3. Trigonometrische-Interpolations-Aufgabe
Gesucht ist ein trig. Polynom kleinstes Grades, das die Interpolationsbedingung für die N äquidistanten Knoten und komplexe Funktionswerte erfüllt. Somit lautet die Interpolationsbedingung:





Die Lösung der TIPA soll mit bezeichnet werden.
tigerbine Auf diesen Beitrag antworten »
3a. Darstellung 1
Mit der Definition eines trig. Polynoms von Grad N aus (1a) erhalten wir folgende Darstellung :



Dieses Polynom hat jedoch (2N+1) Koeffizienten und mit nur N Interpolationsbedingungen sind diese nicht eindeutig bestimmbar.
tigerbine Auf diesen Beitrag antworten »
3b. Darstellung 2
Um nun ein Trig. Polynom vom Grad N zu finden, dessen Koeffizienten eindeutig bestimmbar sind, bedient man sich folgender Rechnung. Setzt man für x die Knoten ein, so erhält man:




















D.h. die beiden trig. Polynome vom Grad N, und nehmen an den N Knoten dieselben Funktionswerte an.

Dennoch handelt es sich i.A. um verschiedene Polynome!
tigerbine Auf diesen Beitrag antworten »
3c. Existenz und Eindeutigkeit
Bei dem in 3b gewonnenen trig. Polynom sind jetzt nur N Koeffizienten zu bestimmen. (Dennoch ist es vom Grad N, es gilt eben ). Es gilt also die Koeffizienten so zu bestimmen, dass gilt:



Das gesuchte trig. Polynom hat nach (3b) also die Gestalt:



Da die N-Knoten paarweise verschieden sind, folgt aus dieser Darstellung, dass das trig. Interpolationsprobelm:



immer (komplexe oder reelle ) eindeutig lösbar ist. Nun benötigt man aber noch einen Weg, die gesuchten Koeffizienten zu bestimmen.

Aus der Darstellung



erkennt man, dass es sich um eine Abbildung von handelt, selbst wenn die alle reell sind. Zur endgültigen Lösung des Problems sind die folgenden Hilfsresultate nötig.

_____________________________________________________________
Legende zu 3a,b,c:





tigerbine Auf diesen Beitrag antworten »
3d. Hilfsresultate
Hilfsresultat 1



Beweis:

Es gilt für


(*)

Für diese Gleichheit gibt es 2 Möglichkeiten:

  1. Für muss gelten , also . Daraus folgt:



  2. Sei nun , dann gilt wegen (1) offensichtlich .
    Da jedoch die Gleichung (*) für alle l gilt, muss für alle gelten




Hilfsresultat 2:

Um die Koeffizienten bestimmen zu können, multipliziert man die Interpolationsbedingung:



für l =0,1,...,N-1 mit und summiert über k:







Für j=l gilt (j-l) = 0 und es folgt mit HR 1:



Für gilt und es folgt:





tigerbine Auf diesen Beitrag antworten »
3e. Berechnung der Koeffizienten d
Somit kann man (durch ersetzen von l durch j) wie folgt umstellen:

tigerbine Auf diesen Beitrag antworten »
4. Diskrete Fourier Analyse / Transformation
Sind nun die Funktionswerte an den Knoten reell, also , so sucht man anstatt dem soeben bestimmenten interpolierenden trig.Polynom



ein trignomotrisches Polynom mit dem folgenden Abbildungsverhalten:



Dieses soll dann in der Darstellung



vorliegen. Da zu seiner Berechnung nur N Knoten voliegen, kann kein trig. Polynom vom Grad N sein, sondern nur den Grad



(Gausklammer) haben. Wir schreiben also:



Dennoch soll dieses Polynom in Bezug zu gestellt werden, um die Existenz und Eindeutigkeitsaussage übernehmen zu können.
tigerbine Auf diesen Beitrag antworten »
4a. Eigenschaften Koeffizienten d
Da die alle reell sind, folgt für die Koeffizienten von :







  • für gerades N gilt:


tigerbine Auf diesen Beitrag antworten »
4b. Zerlegung in 2 Polynome
Auf grund des gewünschten Grades von zerlegen wir in die Summe zweier Polynome:




Wobei folgende Definitionen verwendet werden:








tigerbine Auf diesen Beitrag antworten »
4c-1. Eigenschaften der beiden Polynome an den Knoten
Die in (4b) behauptete Zerlegung von bzgl. der Definition muss natürlich noch nachgewiesen werden. Des weiteren sollen noch 2 wichtige Eigenschaften der beiden Zerlegungspolynome nachgewiesen werden. Aus Übersichtsgründen finden sich die Beweise dazu im nächsten Abschnitt (4c-2).

Behauptung 1:




Behauptung 2:




Behauptung 3:

tigerbine Auf diesen Beitrag antworten »
4c-2. Beweise
Beweis 1:



Dabei gilt:





Somit gilt wie behauptet:




Beweis 2:




Aufgrund der Summenaufteilung ist nun auch klar, warum für ungerades N gilt.



Beweis 3:

Folgt direkt mit den zwei vorherigen Beweisen. Denn damit gilt:

tigerbine Auf diesen Beitrag antworten »
4d. Berechnung der Koeffizienten d
Somit erfüllen sowohl als auch die Interpolationsbedingung. Da aber ein reelles trig. Polynom von möglichst kleinem Grad gesucht ist, lautet die Lösung der diskreten Fourier Analyse:




mit



tigerbine Auf diesen Beitrag antworten »
4e. Berechnung der Koeffizienten a,b
Um das Polynom auf eine Cosinus/Sinus Darstellung zu bringen, ersetzt man wie in (1b):



Damit ergibt sich:











In Analogie zu (1b) erhält man aus:



die gesuchten Koeffizienten:




tigerbine Auf diesen Beitrag antworten »
4f. Das gesuchte Polynom
Es gelten die Folgerungen:






Damit ergibt sich (verlgeiche auch 4a!):







tigerbine Auf diesen Beitrag antworten »
5. Unterschiede zwischen Approximation und Interpolation
Nach all diesen Rechnungen und Polynomen mit einen "T" oder "t" im Namen, sollen diese anhand eines Beispiels dargestellt werden. Es soll die Funktion






approximiert werden, oder der Datensatz interpoliert werden.

Es gelte N = 4



tigerbine Auf diesen Beitrag antworten »
5a. Approximationspolynom


Da es sich um eine ungerade Funktion handelt, gilt nach 2d:



Für die Koeffizienten b gilt:






Somit lautet das gesuchte Polynom:





Die zu erkennende Überschwingung an den Sprungstellen wird als Gibbsches Phänomen bezeichnet.
tigerbine Auf diesen Beitrag antworten »
5b. Lösung der trig. Interpolationsaufgabe







Damit erhalten wir für die Koeffizienten:










Somit lautet die Lösung der trig. Interpolationsaufgabe:

















tigerbine Auf diesen Beitrag antworten »
5c. Lösung der diskreten Fourier-Analyse








Damit erhält man für die Koeffizienten:










Somit lautet die Lösung der diskreten Fourier-Analyse:



tigerbine Auf diesen Beitrag antworten »
5d. Bemerkung
Wie in 3b. erwähnt, sind der Realteil des trig. Interpolationspolynoms und die Lösung der diskreten Fourier-Analyse verschieden:






tigerbine Auf diesen Beitrag antworten »
6. Fast Fourier Transformation
Sei ein Fourierpolynom vom Grad N. Dieses soll an den N Stellen ausgewertet werden. Aus (3b) wissen wir, dass dort dieselben Funktionswerte annimmt wie , es gilt also:
tigerbine Auf diesen Beitrag antworten »
6a. Berechnung der Koeffizieten d





Für die Umrechnung der Koeffizienten gilt:





Es gilt:




Man benötigt also für jedes x, neben den trig. Funktionen, genau 2N Multiplikationen. Für alle auszuwertenden Stellen also 2N².
tigerbine Auf diesen Beitrag antworten »
6b. Gerades N = 2M
Mit dem Wissen über Einheitswurzel verifiziere man:




Sei nun gerade. So kann man definieren. Die Auszuwertenden Stellen werden nun in gerade und ungerade unterteit.


Für gerades k = 2l







Für ungerades k=2l+1















Somit erhält man die neuen Koeffizienten:



tigerbine Auf diesen Beitrag antworten »
6c. N ist eine Zweierpotenz
Gilt nun so läßt sich das Schema von 7b n-mal durchführen und man erhält am Ende die gesuchten Funktionswerte. Der Berechnungsaufwand liegt nun nur noch bei



Rechenoperationen nötig.
tigerbine Auf diesen Beitrag antworten »
6d. Beispielschema für n=8
An welcher Stelle dann die Funktionswerte stehen, soll am Beispiel von verdeutlicht werden. Ist mit den Koeffizeienten c gegeben, so berechnet man sich zunächst einmal mit den Koeffizienten d. Dann schreibt man die in eine Tabelle.



Wie kommt man von j nach k?

tigerbine Auf diesen Beitrag antworten »
7. Umsetzungen im PC
Hier soll noch einmal auf die 3 Varianten (Approximation, trig. Interpolation, Diskrete Fourier Analyse) zurückgekommen werden. Die letzten beiden lassen sich ja noch recht einfach implementieren. Bei ersterem benötigt man zur Berechnung ger Koeffizienten Integrale. Dies wirft sogleich die Frage auf "Wie wird numerisch integriert"

[WS] Numerische Integration -Theorie
[WS] Extrapolation

Folgendes gilt es zu berechnen:









Diese wollen wir nun nicht exakt berechnen, sondern Näherungen verwendet. Dabei kommt auch die in Punkt 6 kennengelernte FFT ins Spiel.
tigerbine Auf diesen Beitrag antworten »
7a. Koeffizienten-Näherungen
Wir wollen die Koeffizienten durch die N-fach wiederholte Trapezregel approximieren.

Zitat:


Dabei gilt für die Koeffizienten :










Somit folgt



Und für die Koeffizienten folgt:



Analog zeigt man

tigerbine Auf diesen Beitrag antworten »
7b. "Alte Bekannte"
Schauen wir uns die Näherungen noch einmal an. Dann sollte man erkennen, dass dies gerade die Koeffizienten der reellen trig. Interpolationsaufgabe (Diskrete Fourier Analyse) sind.

Für unsere Vergleichsaufgabe ergibt sich dann mit N=4:












Das ist noch nicht gerade eine berauschende Genauigkeit. Ist der Ansatz daher falsch? Nein, denn würde man die Aufgabe aus dem Blickwinkel der num. Integration sehen, wäre es schon eher "verwunderlich", wenn man bei so kleinem N (2²) schon "dicht" dran liegen würde. Werfen wir einen Blick in die Fehlerabschätzung der summierten Trapezregel und das umformulierte Integral, so dass wir direkt die Ableitung der zu integrierenden Funktion bilden können':

Zitat:





Damit ergibt sich dann für N:



Die Periodenlänge des Sinus verkleinert sich, daher folgt:




Welche maximale Genauigkeit können wir so erreichen?



Das größte j ist j=N-1, daher:





Unabhängig von N erhalten wir damit die Abschätzung:








Nun wählen wir die Knoten unabhängig vom Grad des FourierPolyoms.



Ist nun eine gewünschte Genauigkeit vorgegeben, so erhlät man:



Beispiel für N=4:





Die tatsächlich benötige Zahl N wird wohl darunter liegen, da wir den Fehler nur abgeschätzt haben. Dies liegt daran, dass man das in der exakten Fehlerdarstellung (vgl. einfache Trapezregel) im Allgemeinen nicht kennen.
tigerbine Auf diesen Beitrag antworten »
7c. Effiziente Berechnung
Wählt wir nun N als Zweierpotenz, so kann man die FFT zur Berechnung der approximierten Koeffizienten verwenden.

[Artikel] Schnelle Fourier Transformation (FFT)
Steffen Bühler Auf diesen Beitrag antworten »

8. Eine einfache Erklärung der Fouriertransformation

Man kann sich die Fouriertransformation wie ein Filter vorstellen, das nur eine einzige Frequenz aus einem Gemisch rausholt.

Nehmen wir mal so ein wirres Signalgemisch:



8a. Filterung der Sinusanteile

Jetzt lassen wir Fourier drauf los. Der sagt ja: "multipliziere das Signal erst einmal mit einem Sinus der Frequenz, an der Du interessiert bist".

Zuerst mal mit sin(x), also Frequenz 1:



Dann mit sin(2x):



Jetzt mit sin(3x):



Bei der Frequenz 3 ist der Mittelwert hochgegangen, bei den anderen beiden Frequenzen unten geblieben. Den genauen Mittelwert kann man ausrechnen, indem man die Flächen über und unter der x-Achse zusammenzählt (über der x-Achse positiv, sonst negativ) und durch die Länge der x-Achse dividiert. Wenn man das tut, ergibt sich bei den beiden ersten Frequenzen exakt Null (die Flächen gleichen sich aus), bei der Frequenz 3 dagegen der Wert 0,5. Fourier sagt nun, dass dieser Wert, wenn man ihn verdoppelt, genau die Amplitude des Sinus der Frequenz 3 ist, der in dem Gemisch versteckt ist.
Steffen Bühler Auf diesen Beitrag antworten »

8b. Filterung der Cosinusanteile

So kann man nun für jeden Sinus, der in dem Gemisch enthalten ist, die Amplitude herausfinden. Ein Cosinus dagegen wird auf diese Weise nicht gefunden! Wenn wir die sin(3x)-Komponente des Gemischs durch eine cos(3x)-Komponente ersetzen, sieht das Signal zwar ähnlich aus:



Multipliziert man das nun mit sin(3x), bleibt der Mittelwert unten!



Erst wenn man mit cos(3x) multipliziert, ergibt sich ein positiver Mittelwert:



Das ist der Grund, warum man Sinus- und Cosinusglieder getrennt voneinander untersuchen muss.
Steffen Bühler Auf diesen Beitrag antworten »

8c. Filterung eines phasenverschobenen Sinus

So eine Zerlegung in Sinus- und Cosinusanteile bedeutet aber auch, dass Sinusfunktionen mit beliebiger Phasenverschiebung untersucht werden können! Denn nach den Additionstheoremen gilt .

Nehmen wir also zum Beispiel einen um 18° verschobenen Sinus:



Den kann man nach obiger Formel in einen reinen Sinus- und einen reinen Cosinusanteil zerlegen:



Bei der Fouriertransformation sollte also für diesen phasenverschobenen Sinus ein Sinusanteil mit Amplitude 0,951 und ein Cosinusanteil Amplitude 0,309 herauskommen, wobei die Amplitude des Sinusanteil etwa dreimal so hoch sein sollte. Probieren wir's aus:



Mulitplikation mit sin(x):



Mulitplikation mit cos(x):



In der Tat ist der Mittelwert (der Wert, um den die Schwingungen "pendeln") der Sinusmultiplikation bei etwas weniger als 0,5 und die der Cosinusmultiplikation bei ungefähr 0,15. Und das entspricht ja der jeweiligen erwarteten halben Amplitude.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »