Beweis zu Stützstellen < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:37 Mi 10.10.2007 | | Autor: | Franzie |
| Aufgabe | Beweise, dass die zu paarweise verschiedenen Stützstellen [mm] x_{0},....,x_{n} [/mm] und zugehörigen Stützwerten [mm] f_{0},....,f_{n} [/mm] gebildeten dividierten Differenzen die explizite Darstellung
[mm] f[x_{k},...,x_{k+j}]=\summe_{i=k}^{k+j}f_{i}\produkt_{m=k,m\not=i}^{k+j}\bruch{1}{x_{i}-x_{m}},
[/mm]
k=0,...,n-j
j=1,....,n besitzen. Was geschieht mit den dividierten Differenzen im Grenzfall zusammenfallender Stützstellen? |
Hallo ihr Lieben!
Hab jetzt meine ersten Numerikvorlesungen diese Woche hinter mir. Hab im Moment noch keinen richtigen Durchblick, da die Vorlesung so was von unstrukturiert ist und ich daher auch noch nicht im Geringsten weiß, worauf die hinaus wollen. Muss aber trotzdem diese Aufgabe abgeben und hab noch keinerlei Idee, was da von mir verlangt wird bzw. wie man an solche Aufgaben herangeht. Gibt es vielleicht irgendwelche Tricks, die speziell in der Numerik angewendet werden?
Würde mich über jeden Hinweis freuen.
liebe Grüße
Franzie
|
|
| |
|
> Beweise, dass die zu paarweise verschiedenen Stützstellen
> [mm]x_{0},....,x_{n}[/mm] und zugehörigen Stützwerten
> [mm]f_{0},....,f_{n}[/mm] gebildeten dividierten Differenzen die
> explizite Darstellung
> [mm]f[x_{k},...,x_{k+j}]=\summe_{i=k}^{k+j}f_{i}\produkt_{m=k,m\not=i}^{k+j}\bruch{1}{x_{i}-x_{m}},[/mm]
> k=0,...,n-j
> j=1,....,n besitzen. Was geschieht mit den dividierten
> Differenzen im Grenzfall zusammenfallender Stützstellen?
> Gibt es vielleicht
> irgendwelche Tricks, die speziell in der Numerik angewendet
> werden?
Hallo,
ein Standardtrick bei jeglicher Art von Aufgabe ist das Klären der Begriffe.
Schreib doch zunächst einmal auf, wie diese dividierten Differenzen definiert sind.
Als nächstes würde ich mir mal ein Beispiel machen, z.B. mir 4 Stützstellen nehmen, die dividierten Differenzen berechnen und prüfen, ob die oben gegebene Darstellung stimmt.
Als nächstes kannst Du testen, was passiert, wenn Du zwei gleiche Stützstellen nimmst.
So kriegst Du schonmal ein Gefühl dafür, wie der Hase läuft.
Ich habe die Aufgabe jetzt nicht gerechnet.
Ich vermute jedoch, daß man zum Ziel kommt, wenn man so eine Art Induktion über j macht.
Wie gesagt: mit der Definition der dividierten Differenzen beginnt hier alles.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:37 Mo 15.10.2007 | | Autor: | Franzie |
Ja, so habe ich das bisher ja auch immer gemacht. Aber genau da liegt an dieser Stelle das Problem. In der Vorlesung ist der Begriff dividierter Differenzen noch nie aufgetaucht.
Kannst du mir kurz erklären, was man explizit darunter versteht?
|
|
|
| |
|
> Ja, so habe ich das bisher ja auch immer gemacht. Aber
> genau da liegt an dieser Stelle das Problem. In der
> Vorlesung ist der Begriff dividierter Differenzen noch nie
> aufgetaucht.
> Kannst du mir kurz erklären, was man explizit darunter
> versteht?
Hallo,
in diesem Falle ist unsere Freundin![[]](/images/popup.gif) wikipedia prompt mit ihren Erklärungen zur Stelle.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:35 Mo 15.10.2007 | | Autor: | Franzie |
Aha...also wenn ich folgendes Beispiel betrachte:
[mm] x_{j}:-1 [/mm] 0 1 2
[mm] f_{j}:-4 [/mm] -4 0 14 seien meine gegebenen Wertepaare.
Wenn ich nun das mit den dividierten Differenzen machen will, muss ich doch folgendermaßen vorgehen:
[mm] c_{0}=f_{0}=-4
[/mm]
[mm] c_{1}=f[x_{0},x_{1}]=\bruch{f_{1}-f_{0}}{x_{1}-x_{0}}=0
[/mm]
[mm] c_{2}=\bruch{f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}=2 [/mm] mit [mm] f[x_{1},x_{2}]=\bruch{f_{2}-f_{1}}{x_{2}-x_{1}}
[/mm]
aber irgendwie komme ich nicht auf das richtige [mm] c_{3}, [/mm] welches ja eigentlich 1 sein müsste, oder?
[mm] c_{3}=\bruch{f[x_{2},x_{3}]-f[x_{1},x_{2}]}{x_{3}-x_{1}}
[/mm]
Wo liegt denn hier mein Denkfehler?
|
|
|
| |
|
> Aha...also wenn ich folgendes Beispiel betrachte:
> [mm]x_{j}:-1[/mm] 0 1 2
> [mm]f_{j}:-4[/mm] -4 0 14 seien meine gegebenen Wertepaare.
> Wenn ich nun das mit den dividierten Differenzen machen
> will, muss ich doch folgendermaßen vorgehen:
> [mm]c_{0}=f_{0}=-4[/mm]
> [mm]c_{1}=f[x_{0},x_{1}]=\bruch{f_{1}-f_{0}}{x_{1}-x_{0}}=0[/mm]
> [mm]c_{2}=\bruch{f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}=2[/mm]
> mit [mm]f[x_{1},x_{2}]=\bruch{f_{2}-f_{1}}{x_{2}-x_{1}}[/mm]
> aber irgendwie komme ich nicht auf das richtige [mm]c_{3},[/mm]
> welches ja eigentlich 1 sein müsste, oder?
> [mm]c_{3}=\bruch{f[x_{2},x_{3}]-f[x_{1},x_{2}]}{x_{3}-x_{1}}[/mm]
> Wo liegt denn hier mein Denkfehler?
Hallo,
ja, lt. meiner Rechnung ist [mm] c_3 [/mm] =1. Hast Du eine Musterlösung, oder woher weißt Du das?
Ich kann in Deiner Rechnung bisher keinen Fehler entdecken, weder einen Rechenfehler noch einen Denkfehler. Du hast die Differenzen in Zähler und Nenner jeweils andersrum als im Wiki-Link, aber da Du das konsequent so machst, ist es ja egal, jedenfalls, wenn Du konkret mit Zahlen rechnest.
(Symbolische Rechnungen sind mit der anderen Reihenfolge übersichtlicher)
Der Fehler kann eigentlich nur beim Berechnen von [mm] f[x_2,x_3] [/mm] liegen, das Ergebnis teilst Du in Deinem Post nicht mit.
Wenn ich die dividierten Differenzen bereche, mache ich mir immer so ein dreieckiges Schema wie im wiki-Link.
Ganz vorne, jeweils vo die [mm] f[x_i] [/mm] schreibe ich mir noch die zugehörigen [mm] x_i [/mm] hin. So hat man wenig zu schreiben und verliert nicht so leicht den Überblick.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:59 Di 16.10.2007 | | Autor: | Franzie |
Okay, also hab es jetzt nochmal mit dem Newton-Schema gemacht und da komm ich auch auf das richtige c. Weiß jetzt auch nicht so genau, wo da der Fehler liegt.
Mein Problem liegt jetzt allerdings schon beim Verständnis der Formel, die ich zu beweisen hab. Wenn ich von meinem Beispiel mit den Stützstellen ausgehe, was muss ich denn dann für k,j,i oder m einsetzen? Ich weiß bei den ganzen Variablen leider noch nicht so richtig, was was sein soll.
|
|
|
| |
|
> Ich weiß bei den ganzen
> Variablen leider noch nicht so richtig, was was sein soll.
Hallo,
Du sollst ja zeigen
"$ [mm] f[x_{k},...,x_{k+j}]=\summe_{i=k}^{k+j}f_{i}\produkt_{m=k,m\not=i}^{k+j}\bruch{1}{x_{i}-x_{m}}, [/mm] $
k=0,...,n-j
j=1,....,n ".
In unserem Beispiel war ja n=4 (4 Stützstellen)
Wenn wir jetzt sagen k=2 j=2, dann wäre zu zeigen
[mm] f[x_{2},...,x_{4}]=\summe_{i=2}^{4}f_{i}\produkt_{m=2,m\not=i}^{4}\bruch{1}{x_{i}-x_{m}}
[/mm]
[mm] =f_{2}\produkt_{m=2,m\not=2}^{4}\bruch{1}{x_{2}-x_{m}}+f_{3}\produkt_{m=2,m\not=3}^{4}\bruch{1}{x_{3}-x_{m}}+f_{4}\produkt_{m=2,m\not=4}^{4}\bruch{1}{x_{4}-x_{m}}
[/mm]
[mm] =f_{2}\bruch{1}{(x_{2}-x_{3})(x_{2}-x_{4})}+f_{3}\bruch{1}{(x_{3}-x_{2})(x_{3}-x_{4})}+f_{4}\produkt_{m=2,m\not=4}^{4}\bruch{1}{(x_{4}-x_{2})(x_{4}-x_{3})}
[/mm]
Kannst ja mal nachprufen, ob das stimmt.
Danach kannst Du Dich ja mal vorsichtig am Beweis (Induktion) versuchen.
Ich würde sagen: sei [mm] j\in \{1,....,n} [/mm] beliebig, aber fest.
Dann zeig, daß die Aussage für k=0 gilt.
Nimm an, daß sie für alle k gilt und zeig: dann gilt sie auch für k+1.
So müßte es klappen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:34 Di 16.10.2007 | | Autor: | Franzie |
Okay. Danke schon mal. Also bezüglich der Formel hat es jetzt klick gemacht. Hab jetzt den Sinnzusammenhang verstanden. Die von dir durchgeführte Berechnung stimmt auch mit dem Beispiel überein laut meiner Nachrechnung.
Hab jetzt versucht, mich an den Induktionsbeweis zu setzen.
Dafür habe ich k=0 gesetzt.
Dann erhalte ich auf der linken Seite der Formel:
[mm] f[x_{k},....x_{k+j}]=f[x_{0},...,x_{j}]
[/mm]
= [mm] \bruch{f[x_{1},x_{j}-f[x_{0},x_{j-1}]}{x_{j}-x_{0}}, [/mm] wobei hier
[mm] f[x_{1},...,x_{j}]= \bruch{f[x_{2},x_{j}-f[x_{1},x_{j-2}]}{x_{j}-x_{1}} [/mm] und
[mm] f[x_{0},...,x_{j-1}]= \bruch{f[x_{1},x_{j-1}-f[x_{0},x_{j-2}]}{x_{j-1}-x_{0}}....
[/mm]
aber das kann ich ja noch unendlich weiter aufschlüsseln oder?
Auf der rechten Seite hätte ich dann
[mm] \summe_{i=0}^{j}f_{i}\produkt_{m=0,m\not=0}^{j}\bruch{1}{x_{i}-x_{m}}
[/mm]
[mm] =f_{0}\produkt_{m=0,m\not=0}^{j}\bruch{1}{x_{0}-x_{m}}+
[/mm]
[mm] f_{1}\produkt_{m=0,m\not=1}^{j}\bruch{1}{x_{1}-x_{m}}+....
[/mm]
+ [mm] f_{j}\produkt_{m=0,m\not=j}^{j}\bruch{1}{x_{j}-x_{m}}
[/mm]
= [mm] f_{0}\bruch{1}{(x_{0}-x_{1})...(x_{0}-x_{j}}
[/mm]
+ [mm] f_{1}\bruch{1}{(x_{1}-x_{0})...(x_{1}-x_{j}}+...
[/mm]
+ [mm] f_{j}\bruch{1}{(x_{j}-x_{1})...(x_{j}-x_{j-1}}
[/mm]
|
|
|
| |
|
> Okay. Danke schon mal. Also bezüglich der Formel hat es
> jetzt klick gemacht. Hab jetzt den Sinnzusammenhang
> verstanden. Die von dir durchgeführte Berechnung stimmt
> auch mit dem Beispiel überein laut meiner Nachrechnung.
> Hab jetzt versucht, mich an den Induktionsbeweis zu
> setzen.
> Dafür habe ich k=0 gesetzt.
> Dann erhalte ich auf der linken Seite der Formel:
> [mm]f[x_{k},....x_{k+j}]=f[x_{0},...,x_{j}][/mm]
> = [mm]\bruch{f[x_{1},x_{j}-f[x_{0},x_{j-1}]}{x_{j}-x_{0}},[/mm]
> wobei hier
> [mm]f[x_{1},...,x_{j}]= \bruch{f[x_{2},x_{j}-f[x_{1},x_{j-2}]}{x_{j}-x_{1}}[/mm]
> und
> [mm]f[x_{0},...,x_{j-1}]= \bruch{f[x_{1},x_{j-1}-f[x_{0},x_{j-2}]}{x_{j-1}-x_{0}}....[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> aber das kann ich ja noch unendlich weiter aufschlüsseln
> oder?
Naja, unendlich oft nicht, denn irgendwann hat die Sache ein Ende zum Glück.
Aber ich sehe das Problem...
Es wäre eine Induktion über j um Klassen geschickter.
Tut mir leid, daß ich das nicht gleich gesehen habe - ich bin in der Numerik nicht drin (und ich habe sie nie geliebt...)
Im Induktionsanfang hat man dann
Sei 1=j
Es ist f[x_k, x_{k+1]=...
So geht's besser!
Gruß v. Angela
> Auf der rechten Seite hätte ich dann
>
> [mm]\summe_{i=0}^{j}f_{i}\produkt_{m=0,m\not=0}^{j}\bruch{1}{x_{i}-x_{m}}[/mm]
> [mm]=f_{0}\produkt_{m=0,m\not=0}^{j}\bruch{1}{x_{0}-x_{m}}+[/mm]
>
> [mm]f_{1}\produkt_{m=0,m\not=1}^{j}\bruch{1}{x_{1}-x_{m}}+....[/mm]
> + [mm]f_{j}\produkt_{m=0,m\not=j}^{j}\bruch{1}{x_{j}-x_{m}}[/mm]
> = [mm]f_{0}\bruch{1}{(x_{0}-x_{1})...(x_{0}-x_{j}}[/mm]
> + [mm]f_{1}\bruch{1}{(x_{1}-x_{0})...(x_{1}-x_{j}}+...[/mm]
> + [mm]f_{j}\bruch{1}{(x_{j}-x_{1})...(x_{j}-x_{j-1}}[/mm]
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:23 Mi 17.10.2007 | | Autor: | Franzie |
Aber wäre es nicht vielleicht sinnvoller die Induktion über j durchzuführen und mit j=1 zu starten?
|
|
|
| |
|
> Aber wäre es nicht vielleicht sinnvoller die Induktion über
> j durchzuführen und mit j=1 zu starten?
>
Hallo,
das meinte ich eigentlich - ich bin einer Indexverwirrung zum Opfer gefallen. ich hatte an [mm] f[x_k,...x_j] [/mm] gedacht.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:29 Fr 19.10.2007 | | Autor: | Franzie |
Also, hab mich jetzt an den Beweis gesetzt. Beim Induktionsanfang sieht eigentlich auch alles ganz gut aus:
Sei k fest, k beliebig aus {1,....,n}
j=1:
linke Seite: [mm] f[x_{k},x_{k+1}]=\bruch{f_{k+1}-f_{k}}{x_{k+1}-x_{k}}
[/mm]
rechte Seite:
[mm] \summe_{i=k}^{k+1}f_{i}\produkt_{m=k, m\not=k}^{k+1}\bruch{1}{x_{i}-x_{m}}=f_{k}*\produkt_{m=k, m\not=k}^{k+1}\bruch{1}{x_{k}-x_{m}}+f_{k+1}*\produkt_{m=k, m\not=k+1}^{k+1}\bruch{1}{x_{k+1}-x_{m}}
[/mm]
[mm] =f_{k}*\bruch{1}{x_{k}-x_{k+1}}+f_{k+1}*\bruch{1}{x_{k+1}-x_{k}}
[/mm]
[mm] =\bruch{f_{k}}{x_{k}-x_{k+1}}+\bruch{f_{k+1}}{x_{k+1}-x_{k}}
[/mm]
= [mm] \bruch{f_{k+1}-f_{k}}{x_{k+1}-x_{k}}
[/mm]
also linke Seite = rechte Seite
Gelte die Behauptung nun für j. Zu zeigen ist, dass sie auch für j+1 gilt.
linke Seite:
[mm] f[x_{k},....,x_{j+k+1}]=\bruch{f[x_{k+1},...,x_{k+j+1}]-f[x_{k},...,x_{j+k}}{x_{k+j+1}-x_{k}}
[/mm]
mit [mm] f[x_{k+1},....,x_{j+k+1}]=\bruch{f[x_{k+2},...,x_{k+j+1}]-f[x_{k+1},...,x_{j+k}}{x_{j+k+1}-x_{k+1}}
[/mm]
und
[mm] f[x_{k},....,x_{j+k}]=\bruch{f[x_{k+1},...,x_{k+j}]-f[x_{k},...,x_{j+k+1}}{x_{k+j}-x_{k}}
[/mm]
aber hier kann ich doch immer wieder weiter rekursiv fortfahren und weiß daher nicht, wie ich diese Seite noch günstig vereinfachen kann. Ich sehe den Kniff einfach nicht.
rechte Seite:
[mm] \summe_{i=k}^{k+j+1}f_{i}\produkt_{m=k, m\not=k}^{k+j+1}\bruch{1}{x_{i}-x_{m}}=f_{k}*\produkt_{m=k, m\not=k}^{k+j+1}\bruch{1}{x_{k}-x_{m}}+f_{k+1}*\produkt_{m=k, m\not=k+1}^{k+j+1}\bruch{1}{x_{k+1}-x_{m}}+f_{k+2}*\produkt_{m=k, m\not=k+2}^{k+j+1}\bruch{1}{x_{k+2}-x_{m}}+....
[/mm]
+ [mm] f_{k+j+1}*\produkt_{m=k, m\not=k+j+1}^{k+j+1}\bruch{1}{x_{k+j+1}-x_{m}}
[/mm]
hier könnte ich jetzt zwar das Summen- und Produktzeichen noch auflösen, aber dann hab ich auch hier wieder das Problem zu vieler Summanden, die ich nicht zusammenfassen kann. Oder funktioniert das hier irgendwie über eine Abspaltung der Summanden? Mein Problem ist, dass ich nicht recht sehe, wie ich nun die rechte und die linke Seite vergleichen kann.....
|
|
|
| |
|
> Gelte die Behauptung nun für j. Zu zeigen ist, dass sie
> auch für j+1 gilt.
> linke Seite:
> [mm]f[x_{k},....,x_{j+k+1}]=\bruch{f[x_{k+1},...,x_{k+j+1}]-f[x_{k},...,x_{j+k}}{x_{k+j+1}-x_{k}}[/mm]
Hallo,
hier kannst Du doch die Induktionsvoraussetzung jeweils für [mm] f[x_{k+1},...,x_{k+j+1}] [/mm] und [mm] f[x_{k},...,x_{j+k}] [/mm] einsetzen.
Dann mußt Du versuchen, das zielstrebig umzuformen.
Gruß v. Angela
> mit
> [mm]f[x_{k+1},....,x_{j+k+1}]=\bruch{f[x_{k+2},...,x_{k+j+1}]-f[x_{k+1},...,x_{j+k}}{x_{j+k+1}-x_{k+1}}[/mm]
> und
> [mm]f[x_{k},....,x_{j+k}]=\bruch{f[x_{k+1},...,x_{k+j}]-f[x_{k},...,x_{j+k+1}}{x_{k+j}-x_{k}}[/mm]
> aber hier kann ich doch immer wieder weiter rekursiv
> fortfahren und weiß daher nicht, wie ich diese Seite noch
> günstig vereinfachen kann. Ich sehe den Kniff einfach
> nicht.
> rechte Seite:
> [mm]\summe_{i=k}^{k+j+1}f_{i}\produkt_{m=k, m\not=k}^{k+j+1}\bruch{1}{x_{i}-x_{m}}=f_{k}*\produkt_{m=k, m\not=k}^{k+j+1}\bruch{1}{x_{k}-x_{m}}+f_{k+1}*\produkt_{m=k, m\not=k+1}^{k+j+1}\bruch{1}{x_{k+1}-x_{m}}+f_{k+2}*\produkt_{m=k, m\not=k+2}^{k+j+1}\bruch{1}{x_{k+2}-x_{m}}+....[/mm]
>
> + [mm]f_{k+j+1}*\produkt_{m=k, m\not=k+j+1}^{k+j+1}\bruch{1}{x_{k+j+1}-x_{m}}[/mm]
>
> hier könnte ich jetzt zwar das Summen- und Produktzeichen
> noch auflösen, aber dann hab ich auch hier wieder das
> Problem zu vieler Summanden, die ich nicht zusammenfassen
> kann. Oder funktioniert das hier irgendwie über eine
> Abspaltung der Summanden? Mein Problem ist, dass ich nicht
> recht sehe, wie ich nun die rechte und die linke Seite
> vergleichen kann.....
|
|
|
|
