[WS] Orthogonale Polynome

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Orthogonale Polynome
Gliederung

tigerbine Auf diesen Beitrag antworten »
Tschebyscheff-Polynome
Darunter versteht man die durch definierten Polynome. Sie treten z.B. beim Lösen der Tschebyscheff-Differentialgleichungen, der optimalen Knotenwahl bei der Lagrange-Interpolation oder bei der Gauß-Quadratur (Gewichtsfunktion ) auf.
 
 
tigerbine Auf diesen Beitrag antworten »
1a. Definition









etc.
tigerbine Auf diesen Beitrag antworten »
1b. Rekursion
Mittels des Additionstheorems ergibt sich die Rekursionsformel:


tigerbine Auf diesen Beitrag antworten »
1c. Polynomeigenschaft
Aus der Drei-Term-Rekursion (1b) folgt (durch Induktion) wegen und dass gilt:

tigerbine Auf diesen Beitrag antworten »
1d. Nullstellen
Allgemein gilt für alle ungeraden Vielfachen von . Also



Damit ergibt sich für die Forderung:









Probe der so bestimmen Nullstellen :






In welchem Intervall liegen die :

Da der Cosinus nur Werte aus dem Intervall [-1, 1] annimmt, liegen die Nullstellen der Tschebyscheff-Polynome folglich auch in diesem Intervall.
(Beliebte Prüfungsfrage)


Sortierung der Nullstellen:







Da der Cosinus in streng monoton fallend ist, folgt für .

Will man die Nullstellen des Tschebyscheff Polynoms in der Sortierung berechnen, so schreibt man:



Bitte beachten, dass es sich hier um die n-Nullstellen von handelt. Bei der Polynominterpolation benötigt man die (n+1)-Nullstellen von
tigerbine Auf diesen Beitrag antworten »
1e. Linearfaktorzerlegung
Da n reelle Nullstellen besitzt, zerfällt das Polynom über in Linearfaktoren und man kann schreiben:



Mit der Drei-Term-Rekursion (1b) ergibt sich dann, dass der Leitkoeffizient c von gleich ist. Somit gilt also:

tigerbine Auf diesen Beitrag antworten »
1f. Extremstellen
Aus der Definition von folgt

D.h. der Funktionswert an einer Extremstelle ist +/- 1.

________________________________________________________
Allgemein gilt für alle geraden Vielfachen von

und für alle ungeraden Vielfachen von ,


________________________________________________________


Damit ergibt sich für die gesuchten Extremstellen :



Probe:

tigerbine Auf diesen Beitrag antworten »
1g. Bezug zum Knotenpolynom der Polynominterpolation
Neben den Extremwerten aus 1e hat keine weiteren Extremwerte. Verwendet man zur Interpolation die Tschebyscheff-Knoten , also die Nullstellen von , so gilt für das Knotenpolynom :



Warum minimiert nun diese Wahl den maximales Ausschlag des Knotenpolynoms w?

Siehe Workshop Polynominterpolation
tigerbine Auf diesen Beitrag antworten »
1h. Orthogonalität
Betrachten wir das Skalarprodukt:



Dann gilt mit der in der Einleitung erwähnten Gewichtsfunktion für die Tschebyscheff-Polynome:




Beweis:

Es werden folgende Bezeichnungen eingeführt:






Dann gilt:













Und somit:




Damit kann man nun die Behauptungen nachweisen:













tigerbine Auf diesen Beitrag antworten »
1i. Symmetrieverhalten
Es ist




Die ungeraden Tschebyscheff-Polynome sind punktsymmetrisch zum Ursprung und es kommen nur ungerade Potenzen von x vor.





Die geraden Tschebyscheff-Polynome sind achsensymmetrisch zur y-Achse und es kommen nur gerade Potenzen von x vor.

--------------------------------------------------------------------------------------------------------

In der Sammlung nun ein paar kleine m-files zur Umrechnung von Monom in Tschebyscheff-Darstellung und Auswertung mittels Clenshaw Algorithmus. http://www.smileygarden.de/smilie/Computer/68.gif
tigerbine Auf diesen Beitrag antworten »
1j. Einige Plots
Lehrer

Vergleiche hierzu die Rekursionsformel in 1b. Dabei gilt es zu beachten, dass nur der Teil der Funktion im Intervall [-1,1] das entsprechende Tschebyscheff Polynom darstellt (Definitionsmenge)

















....





...



tigerbine Auf diesen Beitrag antworten »
Legendre-Polynome
Darunter versteht man die durch definierten Polynome (Dabei seht für die n-te Ableitung). sie treten z.B. beim Lösen der Legendre-Differentialgleichungen oder bei der Gauß-Quadratur (Gewichtsfunktion ) auf.
tigerbine Auf diesen Beitrag antworten »
2a. Definition









etc.
tigerbine Auf diesen Beitrag antworten »
2b. Polyomeigenschaft
Als n-te Ableitung eines Polynoms vom Grad (2n) ist ein Polynom vom Grad n. Dabei hat P_n den Leitkoeffizienten



Beweis:

Ergibt sich direkt aus den Ableitungsregeln für Polynome.
tigerbine Auf diesen Beitrag antworten »
2c. Nullstellen
Hilfssatz

Die Funktion sei beliebig oft differenzierbar und habe in (a,b) mindestens p Nullstellen. Mit einer natürlichen Zahl n setzte man:




Dann gilt:

hat die Gestalt

wobei in [a,b] beliebig oft differenzierbar ist und in (a,b) mindestens (p+k) Nullstellen hat.


Beweis:



Hier ist die Behauptung gerade die Voraussetzung.




Dann ist in [a,b] beliebig oft differenzierbar ist und hat in (a,b) mindestens (p+k) Nullstellen.















hat nach Induktionsbehauptung mindestens (p+k) Nullstellen in (a,b). Diese seinen wie folgt bezeichnet:




hat dann die Nullstellen:




Nach dem Satz von Rolle hat dann in jedem der (p+k+1)- Intervalle



eine Nullstelle. Folglich hat dann (p+k+1) Nullstellen im Intervall (a,b).

*******************************************************

Betrachtet man nun die Funktion



So ist in Bezug zum obigen Hilfssatz





Für die k-te Ableitung der Funktion gilt dann:



wobei in (-1,1) dann mindestens (p+k) = (0+k) Nullstellen hat. Damit ergibt sich, dass



mindestens n Nullstellen in (-1,1) hat. Da aber ein Polxnom vom Grad n (ungleich dem Nullpolynom) ist, hat es genau n Nullstellen in (-1,1).

**********************************************************

Da sich die Legendre Polynome nur durch den Faktor von den Polynomen unterscheiden - auch sie sind Polynome vom Grad n - haben auch sie genau n Nullstellen im Intervall (-1,1).
tigerbine Auf diesen Beitrag antworten »
2d. Orthogonalität
Betrachten wir das Skalarprodukt:



So lautet mit der hier verwendeten Gewichtsfunktion () das Skalarprodukt:




Zum Nachweis von



genügt es zu zeigen, dass

.

Dieses wiederum ist in der Behauptung



enthalten. Dabei ist wie im vorherigen Absatz





Beweis: Induktion nach k









D.h. es gilt






Bemerkung:

Es ist ein Polynom vom Grad (2n), dass in x=-1 und x=1 jeweils eine n-fache Nullstelle besitzt. Somit gilt auch für die (k-1)-te Ableitung (wegen k-1 < n ):




Damit ist die Orthogonalität der Legendre-Polynome nachgewiesen. In Analogie zu den Tschebyscheff-Polynomen soll noch der Fall m=n angegeben werden.


tigerbine Auf diesen Beitrag antworten »
2e. Symmetrie
Nach dem Binomischen Satz ist:



Also ein gerades Polynom. Daher folgt mit den Ableitungsregeln für Polynome:




Daher gilt also:




Als direkte Folgerung ergibt sich dann für den ungeraden Fall n=2k+1:

tigerbine Auf diesen Beitrag antworten »
2f. Rekursion
Es ist und aufgrund ihrer gezeigten Orthogonalität sind die Polynome linear unabhängig und bilden eine Basis der . Deswegen kann man für schreiben:








********************************************************
Aus den Eigenschaften des hier verwendeten Skalarproduktes folgt:




Mit dem Beweis zur Orthogonalität und den Rechenregeln des Skalarprodukts folgt dann:



Damit gilt auch:


Andererseits ist mit (*):



Damit folgt wegen


*********************************************************

Aufgrund des Symmetrieverhaltens ergibt sich aus (*) mit Q(x)=0:






**********************************************************

Somit erhält man die Rekurisonsformel:





Vergleicht man die Höchstkoeffizienten-Darstellung beider Seiten, so erhält man:





***********************************************************

Damit erhält man die Rekurionsformel




Durch Bilden des Sklalarprodukts mit folgt:






**********************************************************

Somit lautet also abschließend die Rekursionsformel zur Berechnung der Legendre-Polynome durch Drei-Term-Rekusion:

tigerbine Auf diesen Beitrag antworten »
2g. Gemeinsame Punkte
Aus der DTR-Formel ergibt sich dann noch, dass für alle gilt:




Beweis:




Aus der Definition kann man sich ja nun noch die ersten beiden bestimmen und erhält:





Überprüfung zeigt, dass für beide gilt:



Mit der DTK-Formel folgt dann:



Und auch hier ist:




Allgemein folgt aus der Annahme, dass die Behauptung richtig ist für (k-1) und (k):

tigerbine Auf diesen Beitrag antworten »
2h. Einige Plots
Drei-Term-Rekursion















tigerbine Auf diesen Beitrag antworten »
3. Jacobi-Polynome
Die in 1 und 2 vorgestellten Polynome kann man als Spezialfälle der Jacobi-Polynome betrachten. Diese haben die allgemeine Gewichtsfunktion




Legendre-Polynome




Tschebyscheff-Polynome

tigerbine Auf diesen Beitrag antworten »
4. Schema von Golub & Welsch
...oder anders gesagt, die Berechnung der Nullstellen von orthogonalen Polynomen mittels der Eigenwerte einer Tridiagonalmatrix. Der Beweis, warum das Verfahren erfolgreich ist, soll hier nicht geführt werden.Man findet ihn zum Bsp. hier oder hier. Es soll vielmehr dargestellt werden, wie man aus den bekannten Rekursionsformeln (Dreitermrekursion) die Matrix bestimmt und auswertet.


Allgemeine Dreitermrekursion

Seien bezüglich des Skalarprodukts orthogonale Polynome mit den Höchstkoeffizienten . Dann gibt es Zahlen so dass gilt:





Dabei gilt für die Koeffizienten:





Normierte Dreitermrekursion












Dabei gilt:




Nullstellen und Eigenwerte

Hat das orthogonale Polynom den Grad (n+1), so sind seine Nullstellen die Eigenwerte der Tridiagonalmatrix




Gewichte und Eigenvektoren

Die Eigenvektoren müssen so normiert sein, dass gilt:



Dabei gilt für das Skalarprodukt auf der rechten Seite:




Dann kann man die gesuchten Eigenvektoren wie folgt aus denen aus einem Algorithmus erhaltenen Eigenvektoren erhalten:



Das gesuchte Gewicht erhalt man dann, indem man die erste Komponente des EVs quadriert.

tigerbine Auf diesen Beitrag antworten »
4a. Schema für die Legendre-Polynome
Aus der Rekursionsformel entnehmen wir die Werte:




Daraus ergeben sich dann:




Die Gewichtsfunktion lautet



Daraus ergibt sich insbesondere, dass die Summe der Gewichte gleich der Länge des Intervalls [-1,1] ist.

Daraus ergeben sich dann:






code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
In den Zeilen stehen aufsteigend die Koeffizienten der
LEGENDRE-Polynome:
------------------------------------------------------
LP =
    1.0000         0         0         0         0
         0    1.0000         0         0         0
   -0.5000         0    1.5000         0         0
         0   -1.5000         0    2.5000         0
    0.3750         0   -3.7500         0    4.3750
 
Die 5 Knoten lauten:
-----------------------
x =
   -0.9062   -0.5385    0.0000    0.5385    0.9062
 
Die 5 Gewichte lauten:
-----------------------
w =
    0.2369    0.4786    0.5689    0.4786    0.2369
 
tigerbine Auf diesen Beitrag antworten »
4b. Schema für die Tschebyscheff-Polynome (erster Art)
Aus der Rekursionsformel entnehmen wir die Werte (für n>1):




Daraus ergeben sich dann:




Die Gewichtsfunktion lautet




Daraus ergeben sich dann:






code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
n den Zeilen stehen aufsteigend die Koeffizienten der
TSCHEBYSCHEFF-Polynome:
------------------------------------------------------
TP =
     1     0     0     0     0
     0     1     0     0     0
    -1     0     2     0     0
     0    -3     0     4     0
     1     0    -8     0     8
 
Die 4 Knoten lauten:
-----------------------
xT =
   -0.9239   -0.3827    0.3827    0.9239
 
Die 4 Gewichte lauten:
-----------------------
wT =
    0.7854    0.7854    0.7854    0.7854
 



Hier sei angemerkt, dass es für die Nullstellen der Tschebyscheff-Polynome auch eine direkte Berechnung gibt:




Auch die Berechnung der Gewichte gelingt einfacher, denn sie sind alle gleich groß:

tigerbine Auf diesen Beitrag antworten »
4c. Schema für die Laguerre-Polynome
Detaillierte Information zu diesen Polynomen gibt es hier.

Die ersten Polynome



Die Nullstellen liegen im Intervall , approximiert wird bei dieser Gauss-Quadratur das uneigentliche Integral



Aus der Rekursionsformel entnehmen wir die Werte:




Daraus ergeben sich dann:




Die Gewichtsfunktion lautet




Daraus ergeben sich dann:






code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
In den Zeilen stehen aufsteigend die Koeffizienten der
LAGUERRE-Polynome:
------------------------------------------------------
LaP =
    1.0000         0         0         0         0
    1.0000   -1.0000         0         0         0
    1.0000   -2.0000    0.5000         0         0
    1.0000   -3.0000    1.5000   -0.1667         0
    1.0000   -4.0000    3.0000   -0.6667    0.0417
 
Die 4 Knoten lauten:
-----------------------
xLa =
    0.3225    1.7458    4.5366    9.3951
 
Die 4 Gewichte lauten:
-----------------------
wLa =
    0.6032    0.3574    0.0389    0.0005
tigerbine Auf diesen Beitrag antworten »
4d. Schema für die Hermite-Polynome
Detaillierte Informationen zu diesen Polynomen gibt es hier

Die ersten Polynome



Die Nullstellen liegen im Intervall , approximiert wird bei dieser Gauss-Quadratur das uneigentliche Integral



Aus der Rekursionsformel entnehmen wir die Werte:




Daraus ergeben sich dann:



Die Gewichtsfunktion lautet




Daraus ergeben sich dann:





code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
In den Zeilen stehen aufsteigend die Koeffizienten der
HERMITE-Polynome:
------------------------------------------------------
HP =
     1     0     0     0     0
     0     2     0     0     0
    -2     0     4     0     0
     0   -12     0     8     0
    12     0   -48     0    16
 
Die 4 Knoten lauten:
-----------------------
xH =
   -1.6507   -0.5246    0.5246    1.6507
 
Die 4 Gewichte lauten:
-----------------------
wH =
    0.0813    0.8049    0.8049    0.0813
Neue Frage »
Antworten »



Verwandte Themen

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