Chebyshev Polynome Beweis < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:50 Sa 14.05.2011 | | Autor: | qsxqsx |
Hallo,
Weder in Vorlesung noch im google gibt es einen Beweis zu den Chebyshev Nodes - weshalb sie so gewählt werden müssen wie sie gewählt werden...
Im Invervall [-1,1] sind sie so zu wählen:
[mm] x_{i} [/mm] = [mm] cos(\bruch{2*i - 1}{2n}*\pi)
[/mm]
Zu minimieren ist ja angeblich w(x) = [mm] \produkt_{i=0}^{n}(x-x_{i})
[/mm]
(oder vielleicht auch [mm] max_{[-1,1]}|w(x)| [/mm] = [mm] max_{[-1,1]}|\produkt_{i=0}^{n}(x-x_{i})| [/mm] wobei ich mir da auch nicht so sicher bin).
Nur: für verschiedene x ist ja das auch verschieden gross...da
die Chebyshev Nullstellen vorallem nahe bei -1 bzw. 1 sind macht das für x nahe bei 0 ja keinen Sinn. Ich weiss nicht wie ich das minimieren soll...
Grüsse
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:03 Sa 14.05.2011 | | Autor: | Teufel |
Hi!
Die Aufgabe musste ich letztens auch noch lösen. Dabei musste ich verschiedene Teilaufgaben bearbeiten und wurde so schrittweise an die Lösung herangeführt. Ich schreib es dir einfach mal auf, die Aufgaben selbst kannst du vielleicht selbst lösen!
a) Zeigen Sie: Für $n [mm] \in \IN_0$ [/mm] ist durch [mm] T_n(x):=cos(n*arccos(x)) [/mm] ein Polynom [mm] $T_n\in\IP_n$ [/mm] definiert und es gilt
[mm] T_{n+1}(x)=2^n*(x-x_0)*...*(x-x_n) [/mm] mit [mm] x_i:=cos(\frac{(2i+1)*\pi}{2*(n+1)}), [/mm] i=0,1,...,n.
Anmerkung von mir: [mm] \IP_n [/mm] ist der Raum aller Polynome vom Grad n. [mm] T_n(x) [/mm] ist gerade das Tschebyscheff-Polynom vom Grad n.
b) Zeigen sie, dass
[mm] ||T_{n+1}(x)||_{\infty,[-1,1]}\le 2^n*||(x-y_0)*...*(x-y_n)||_{\infty,[-1,1]} [/mm] für alle [mm] $y_0, [/mm] ..., [mm] y_n \in [/mm] [-1,1]$ gilt.
Anleitung: machen Sie zuerst die Annahme, dass für [mm] $y_0, [/mm] ..., [mm] y_n \in [/mm] [-1,1]$ die behauptete Ungleichung nicht gilt. Wie viele Nullstellen hat dann das Polynom [mm] T_{n+1}(x)-2^n*\produkt_{i=0}^{n}(x-y_i)?
[/mm]
Anmerkung von mir: [mm] ||.||_{\infty,[-1,1]} [/mm] ist die Supremumsnorm auf [-1,1].
Wenn du das lösen kannst, hast du alles gezeigt!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:11 Sa 14.05.2011 | | Autor: | qsxqsx |
Hallo Teufel,
a.) Hier zeige ich eigentlich, dass eben die durch den cosinus bestimmten Nullstellen zu den Chebychef Polynomen gehören. Okay soweit.
b.) Was mir nicht klar ist: Wieso muss man das für die [mm] ||.||_{\infty} [/mm] norm Zeigen? Ich meine das bedeutet doch den Maximalen Wert auf dem Intervall [-1,1]. Dieser Wert wird irgendwo an einer Stelle [mm] x_{f Betrag is maximal} [/mm] angenommen. Aber was ist für alle anderen x auf dem Intervall? Ich verstehe einfach nicht wieso das dann dieses w(x) minimieren soll. x ist ja eine Variable...
Aber danke erstmal werd ich die zwei Punkte versuchen zu beweisen. Meld mich dann nochmal...
Grüsse
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:52 Sa 14.05.2011 | | Autor: | Teufel |
Hi!
Ja, eigentlich sollte da auch stehen, dass die Maximumsnorm von w(x) minimiert wird.
Denn den Fehler der Polynominterpolation kann man ja durch [mm] \frac{1}{(n+1)!}*||f^{(n+1)}(x)||_\infty*||w(x)||_\infty [/mm] (auf dem Intervall, auf dem man interpoliert) abschätzen.
Genau, und bei der a) musst du auch noch zeigen, dass der Vorfaktor [mm] 2^n [/mm] stimmt. Das geht z.B. recht einfach mit der Rekursionsformel [mm] T_{n+1}=2x*T_n(x)-T_{n-1}(x) [/mm] und Induktion.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:27 So 22.05.2011 | | Autor: | qsxqsx |
Also:
> a) Zeigen Sie: Für [mm]n \in \IN_0[/mm] ist durch
> [mm]T_n(x):=cos(n*arccos(x))[/mm] ein Polynom [mm]T_n\in\IP_n[/mm] definiert
Das lässt sich mittels Induktion und cos(x + y) = cos(x)cos(y) + sin(x)sin(y) und sin(arccos(x)) = [mm] \wurzel{1 - x^{2}} [/mm] zeigen.
> und es gilt
> [mm]T_{n+1}(x)=2^n*(x-x_0)*...*(x-x_n)[/mm] mit
> [mm]x_i:=cos(\frac{(2i+1)*\pi}{2*(n+1)}),[/mm] i=0,1,...,n.
> Anmerkung von mir: [mm]\IP_n[/mm] ist der Raum aller Polynome vom
> Grad n. [mm]T_n(x)[/mm] ist gerade das Tschebyscheff-Polynom vom
> Grad n.
Induktionsverankerung: cos(arccos(x)) = [mm] T_{1} [/mm] = x = [mm] T_{0 + 1} [/mm] = [mm] 2^{0}(x-x_{0}), x_{0} [/mm] = [mm] cos(\bruch{\pi}{2})
[/mm]
Jetzt auf n+1 gehen. Ich habe noch nicht genug lange probiert, weiss aber das es nicht so trivial ist, weil die [mm] x_{i} [/mm] sich ja auch verändern...
>
> b) Zeigen sie, dass
> [mm]||T_{n+1}(x)||_{\infty,[-1,1]}\le 2^n*||(x-y_0)*...*(x-y_n)||_{\infty,[-1,1]}[/mm]
> für alle [mm]y_0, ..., y_n \in [-1,1][/mm] gilt.
> Anleitung: machen Sie zuerst die Annahme, dass für [mm]y_0, ..., y_n \in [-1,1][/mm]
> die behauptete Ungleichung nicht gilt.
Demzufolge soll man die Annhame [mm]||T_{n+1}(x)||_{\infty,[-1,1]}> 2^n*||(x-y_0)*...*(x-y_n)||_{\infty,[-1,1]}[/mm] machen.
Wie viele
> Nullstellen hat dann das Polynom
> [mm]T_{n+1}(x)-2^n*\produkt_{i=0}^{n}(x-y_i)?[/mm]
Die Frage ist äquivalent zu wieviele Nullstellen hat das Polynom P(x) = [mm] \produkt_{i=0}^{n}(x-x_i) [/mm] - [mm] \produkt_{i=0}^{n}(x-y_i). [/mm] Ich würde sagen, es hat höchsten n+1 Nullstellen, da der Grad bei der Addition nicht grösser wird.
> Anmerkung von mir: [mm]||.||_{\infty,[-1,1]}[/mm] ist die
> Supremumsnorm auf [-1,1].
>
> Wenn du das lösen kannst, hast du alles gezeigt!
Ich versteh den Zusammenhang bei b.) noch nicht. Kannst du mir das bitte noch in zwei Sätzen sagen was die Nullstellen mit dem > zu tun haben?
Danke.
Grüsse
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:36 Mo 23.05.2011 | | Autor: | Teufel |
Hi!
Ok, also dass die Nullstellen $ [mm] x_i=cos(\frac{(2i+1)\cdot{}\pi}{2\cdot{}(n+1)})$ [/mm] sind, kannst du einfach nachprüfen, indem du sie in [mm] T_{n+1}(x)=cos((n+1)*arccos(x)) [/mm] einsetzt. Dann hast du n+1 Nullstellen für das Polynom (n+1)-ten Grades.
Bleibt noch zu zeigen, dass [mm] 2^n [/mm] der Koeffizient vor dem [mm] x^{n+1} [/mm] ist. Das kannst du z.B. mit Induktion und der Rekursionsformel [mm] T_{n+1}=2*x*T_n(x)-T_{n-1}(x) [/mm] machen.
Nun zur Sache mit den Nullstellen.
Weil [mm] T_{n+1}(x) [/mm] die Form [mm] 2^nx^{n+1}+... [/mm] hat (nach a)), hat das Polynom [mm] $T_{n+1}(x)-2^n\cdot{}\produkt_{i=0}^{n}(x-y_i)$ [/mm] den Grad n.
Nun musst du argumentiere, dass [mm] $T_{n+1}(x)-2^n\cdot{}\produkt_{i=0}^{n}(x-y_i)$ [/mm] n+1 Nullstellen hat, wenn die Annahme, dass die Ungleichung nicht gilt, gelten würde (also wenn ">" gilt). Das kann aber nicht sein, wenn das Polynom nur Grad n hat. Das ist dann der Widerspruch, also muss die Annahme falsch sein und die Ungleichung, die in der Aufgabe steht, ist richtig.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:06 Mo 23.05.2011 | | Autor: | qsxqsx |
Hallo,
War ne Stunde dran mann!:
Also wenn der Betrag von P(x) = [mm] \produkt_{i=0}^{n}(x-y_i), [/mm] also [mm] |\produkt_{i=0}^{n}(x-y_i)| [/mm] < [mm] \bruch{|T_{n+1}(x)|}{2^{n}} [/mm] ist, dann ist
und die Extrama von [mm] T_{n+1}(x) [/mm] sind [mm] \pm [/mm] 1, so muss ja sein
[mm] P(x_{0}) [/mm] < [mm] \bruch{1}{2^{n}}
[/mm]
und
[mm] P(x_{1}) [/mm] > [mm] -\bruch{1}{2^{n}}
[/mm]
usw.
Zieht man die Polynome voneinander ab, sieht man, dass es n+1 Nullstellen gibt...
(Eins weiss ich immer noch nicht: Wie ist Chebychev überhaupt auf die Idee gekommen die Nullstellen so zu wählen......?)
Grüsse
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:15 Mo 23.05.2011 | | Autor: | Teufel |
Ja, genau so habe ich auch ungefähr argumentiert. :)
Glückwunsch, damit hast du das auch gezeigt!
Wie man darauf kommt? Ich weiß es nicht. Mich erstaunt es immer wieder, was es für Beweise und andere Erkenntnisse gibt, auf die ich im Leben nie gekommen wäre. Aber wenigstens nachvollziehen kann man sie noch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:41 Mo 23.05.2011 | | Autor: | qsxqsx |
Danke vielmals für die Hilfe.
Abend!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 So 22.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
