Konvergenz Newton- Verfahren < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:20 Mi 18.02.2009 | | Autor: | kalle754 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo, ich schreibe zurzeit eine Facharbeit über das Newtonverfahren.
Ich habe diese auch schon so gut wie fertig gestellt. Nur bei einem Teil habe ich Probleme.
Was sind die Konvergenzbedingungen?
Warum wird das Newtonverfahren als Fixpunkt iteration interpretiert mit g(x) und die Ableitung von g(x) gebildet , um Konvergenzaussagen zu treffen?
Eine Bedingung auf die man kommt ist doch, dass der Startwert nahe genug an der NS liegt, aber wie kommt man darauf?
Ich weiß Fragen über Fragen, aber ich würde mich über eure Hilfe freuen.
MFG Kalle
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:23 Mi 18.02.2009 | | Autor: | leduart |
Hallo
1. Man muss nicht unbedingt nahe bei der Nullstelle anfangen, Beispiel: du willst mit Newton [mm] \wurzel{2} [/mm] ausrechnen, also die Nullstelle von [mm] f(x)=x^2-2
[/mm]
ausser x=0 kannst du mit jedem Startwert anfangen, also auch mit x=1000 oder x=0.01 und es knvergiert immer gegen [mm] \wurzel{2}
[/mm]
2. weisst du, was ne Fixpunktgleichung ist?
Du suchst eine Stelle, wo der fktswert = der variablen ist. also f(x)=x
Wieder ein einfaches Beispiel [mm] f(x)=x^2
[/mm]
Du kennst sofort 2 Nullstellen , die du aus [mm] x^2=x [/mm] hier ausrechnen kannst x=0 und x=1
Wenn du die nicht kennst, faengst du mit irgendeinem Wert [mm] x_0 [/mm] an, setzt ihn in f(x) ein, also [mm] x_1=f(x_0) x_n=f(x_{n-1})
[/mm]
Wenn du hier also bei [mm] f(x)=x^2 [/mm] Werte [mm] |x_0|>1 [/mm] einsetzt kommst du nie bei dem Fixpkt an.
Grund, die Ableitung von f(x) f'(x)=2x und f'(1)=2
Der Abstand von [mm] x_n, x_{n+1} [/mm] wird immer groesser solange |f'|>1
Wie man die Konvergenz des Newtonverfahrens zeigen soll. ohne es als Fixpktgleichung zu sehen weiss ich nicht.
Natuerlich kannst du das auch weglassen, weil es fuer die Schule schwierig ist, und die Konvergenz graphisch klar machen.
Wenn du ueber den Fixpunktsatz klarer werden willst, zeichne y=x und y=f(x)
die schneiden sich im fixpunkt.
jetzt ueberlege, was bei der Iteration passiert, wenn f(x) steiler ist als y=x, was wenn es flacher ist.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:20 Mi 18.02.2009 | | Autor: | kalle754 |
Vielen Dank schonmal.
Ne herausnehmen kann ich den Teil über die Konvergenz nicht...
Also die Fixpunktgleichung hab ich soweit verstanden.
Nur inwieweit das mit der konvergenz des Newtonverfahrens zu tun hat versteh ich nicht.
Ich habe gelesen, das newton verfahren lässt sich als solche interpretieren:
g(x)=x-(f(x)/(f´(x))
davon wird die Ableitung gebildet um Konvergenzaussagen treffen zu können. g´(x)=(f(x)∙f´´(x))/([f´(x)]²)
Aber was kann ich aus dieser Ableitung ablesen?
Warum muss ich die bilden, um eine Aussage treffen zu können?
Ich hoffe ihr könnt mir da nochmal helfen...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:22 Mi 18.02.2009 | | Autor: | leduart |
Hallo
das Newtonverfahren:
[mm] x_{n+1}=x_n-f(x_n)/f'(x_n)
[/mm]
wenn du jetzt g(x)=x-f(x)/f'(x) definierst, kannst du neu schreiben:
[mm] x_{n+1}=g(xn)
[/mm]
wenn du einen Punkt faendest mit x=g(x) dann haettest du ja (falls [mm] f'(x)\ne0) [/mm] eine Nulstelle von f(x) gefunden.
Damit hast du erstmal das Newtonproblem umgeschrieben als Fixpunktgleichung.
Die Fixpunktgleichung kann man versuchen zu loesen, indem man sie "iteriert", also genau mit dem Verfahren
[mm] x_{n+1}=g(xn)
[/mm]
Nur wann klappt das garantiert?
Wenn die Punkte [mm] x_n,x_{n+1} [/mm] immer staerker zusammenruecken, anders wenn [mm] |x_n-x_{n+1}| [/mm] immer kleiner wird.
oder [mm] |x_n-x_{n+1}|<|x_{n+1}-x_{n+2}|
[/mm]
es gilt [mm] (f(x_n)-f(x_{n+1})/(x_n-x_{n+1})=f'(\xi) [/mm] mit [mm] \xi [/mm] aus dem intervall
falls [mm] f(\xi)=q<1 [/mm] ist gilt dann:
[mm] |f(x_n)-f(x_{n+1}|
aber [mm] f(x_n)=x_{n+1} f(x_{n+1})=x_{n+2}
[/mm]
Du siehst, wenn die Ableitung echt kleiner 1 ist, wird der Abstand jedesmal um den Faktor q verkleinert.
(ich hab jetzt immer f geschrieben, damit aber das g(x) gemeint, von dem wir den Fixpkt suchen)
Dass die Ableitung unserer, die Newtoniteration ersetzenden Fixpunktfkt |g'(x)|=|ff''/f'^2| ist kannst du wohl selbst.
also konvergiert das Newtonverfahren umso besser, je groesser f' der Newtonfkt ist, (je kleiner g' der Fixpktfkt ist.
Ist das jetzt klarer? sonst frag ruhig nach.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:56 Mi 18.02.2009 | | Autor: | kalle754 |
ja vielen Dank wirklich ist schon viel klarer geworden.
So ähnlich kann ich das dann in der facharbeit beschreiben.
Was bedeutet [mm] \delta [/mm] dieses Delta zeichen, könntest du mir das erklären?
und q steht für die Konvergenzgeschwindigkeit, oder?
wie kommt das q aber in die formel duch dieses delta zeichen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:54 Mi 18.02.2009 | | Autor: | leduart |
Hallo
Der Buchstabe, den ich verwendet habe ist ein [mm] \xi=xi, [/mm] es heisst einfach dass die Gleichung an einer bestimten Stelle x=xi die zwischen den beiden Werten [mm] x_n [/mm] und [mm] x_{n+1} [/mm] liegt richtig ist.
(anschaulich, vorne steht die Sehnensteigung der Sehne zwischen [mm] x_n [/mm] und [mm] x_{n+1} [/mm] hinten steht die Steigung der Tangente irgendwo dazwischen.
ich hatte gesagt, dass WENN f' ueberall in dem betrachteten Gebiet <q ist, dann wird der Abstand jedesmal um mindestens den Faktor q kleiner. d.h. je kleiner q ist umso besser konvergiert das Verfahren.
(die Stelle [mm] \xi [/mm] kennt man ja nicht, deshalb nimmt man das "schlimmst" moegliche f' in der Gegend, wo man die Iteration macht.
Beispiel wieder Nullstelle von [mm] f(x)=x^2-2
[/mm]
es ist [mm] ff''/f^2=(x^2-2)*2/(2x)^2=1/2-1/x^2 [/mm] fuer [mm] x>\wurzel [/mm] 2 ist der Betrag immer kleiner 1/2, fuer x<1 nicht immer, aber man kann zeigen, dass man von 0<x<1 als Anfangswert man immer in einem Schritt bei [mm] x>\wurzel{2} [/mm] landet. d.h. das Verfahren konvergiert hier fuer alle Anfangswerte , die groesser als 0 sind.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:07 Mi 18.02.2009 | | Autor: | kalle754 |
Ich versteh nur nicht, wie ich jetzt allgemeine Konvergenzbedingungen aufstelle und daraus dann Aussagen entwickel.
Ich hab Angefangen damit, dass sich das Newtonverfahren auch als Form der Fixpunkt-Iteration interpretieren lässt, indem man die zugehörige Funktion g(x) wie folgt definiert:
[mm] g(x)=x_n-(f(x_n))/(f´(x_n))
[/mm]
dann hab ich die Ableitung gebildet:
g´(x)=(f(x)∙f´´(x))/([f´(x)]²)
Warum ist g´(x )=0 ?
Welche Kovergenzaussagen kann ich daraus treffen?
Wa bedeutet es wenn im Intervall etwas zweima stetig differenzierbar sein soll?
Ich brauch ne "normale NS" [mm] f´\not=0 [/mm] und f = 0
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:35 Mi 18.02.2009 | | Autor: | leduart |
Hallo
Warum ist g'(x)=0 was meinst du damit?
im Fixpunkt selbst ist die Ableitung 0 aber doch sonst nirgends. und den Fixpunkt = Nullstelle deiner fkt. suchst du doch gerade. Also ist [mm] g'(x_i) [/mm] nicht 0, wenn du nicht zufaellig mit der richtigen Nullstelle angefangen hast.
Du faengst mit irgendeinem x deine Iteration an.
Du musst fesstellen, ob in der Umgebung dieses x, und der weiteren x, auf die du stossen kannst g'<q<1 ist.
Wenn das so ist, hab ich dir doch gezeigt, warum dann die abstaende zwischen den erreichten Punkten immer kleiner wird. und dann koennen sie nur auf einen Fixpunkt zulaufen.
In der Def. von g(x) steht kein [mm] x_n [/mm] sondern x!
Wenn deine fkt f, fuer die du die Nst. suchst nicht 2 mal stet, differenzierbar ist, kannst du [mm] g'=ff''/f^2 [/mm] ja nicht abschaetzen, also fesstellen, dass es kleiner q <1 ist.
Gruss leduart.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:48 Mi 18.02.2009 | | Autor: | kalle754 |
Also Newtonverfahren lässt sich auch so schreiben g(x)=x-(f(x))/(f´(x))?
Warum?
Wofür brauch ich die Ableitung von g(x)?
Also ich habe woanders gelesen:
Wegen f(x)=0 und f´(x)≠0 ist: g´(x)=0 wieso und was bedeutet das?
Daraus lässt sich schließen:
Die Funktion f sei für alle xeI=[a,b] zweimal stetig differenzierbar und besitze in (a,b) eine einfache Nullstelle x, d.h. f(x)=0 und f´(x)≠0. Dann gibt es ein abgeschlossenes Intervall U mit x als Mittelpunkt derart, dass die Iterationsfolge [mm] x_(n+1)=(f(x_n))/(f´(x_n)) [/mm] neN, für jeden Startwert x0 gegen x konvergiert.
Oder ist das alles falsch?
Irgendwie versteh ich das noch nicht so richtig.
Vielen Dank für deine Hilfe und vorallem für deine Gedult!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:39 Mi 18.02.2009 | | Autor: | leduart |
Hallo
> Also Newtonverfahren lässt sich auch so schreiben
> g(x)=x-(f(x))/(f´(x))?
> Warum?
besser man kann es als fixpunktgl x=g(x) schreiben, das hab ich dir weiter vorne erklaert.
hier
> Wofür brauch ich die Ableitung von g(x)?
ich hab dir gesagt, warum die Iteration [mm] x_{n+1}=g(x_n) [/mm] "kontrahierend ist, also Abstandsverkleinernd, wenn g'<q<1
> Also ich habe woanders gelesen:
> Wegen f(x)=0 und f´(x)≠0 ist: g´(x)=0 wieso und was
> bedeutet das?
Wenn du g' hinschreibst und f(x)=0 einsetzt ist g'=0
das ist also bei der Nullstelle der Fall. wenn g' stetig ist und an einer Stelle 0, dann ist |g'| in einer Umgebung des Fixpunktes <1 (wie gross die Umgebung ist weiss man natuerlich nicht unbedingt, solange man nicht mehr ueber g' weiss.
> Daraus lässt sich schließen:
>
> Die Funktion f sei für alle xeI=[a,b] zweimal stetig
> differenzierbar und besitze in (a,b) eine einfache
> Nullstelle x, d.h. f(x)=0 und f´(x)≠0. Dann gibt es
> ein abgeschlossenes Intervall U mit x als Mittelpunkt
> derart, dass die Iterationsfolge [mm]x_(n+1)=(f(x_n))/(f´(x_n))[/mm]
> neN, für jeden Startwert x0 gegen x konvergiert.
>
>
> Oder ist das alles falsch?
Das ist genau richtig.
Es wurde die Stetigkeit von g' benutzt um zu sagen, dass es auf jeden Fall in der Naehe von g'=0 (hier ine einem Intervall (a,b) um den fixpkt g'<q<1 gibt, und damit die Iteration der fixpktfkt konvergiert, wie ich jetzt mehrfach gezeigt habe.
Lies dir in Ruhe noch mal alle posts seit dem zitierten durch. Aber langsam. Dann schreib dir auf, was du jeweils verstanden hast und wo es noch hakt. Aber zitier dabei was ich gesagt habe.
Ich hab Geduld, aber keine Gedult
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:19 Do 19.02.2009 | | Autor: | kalle754 |
Das mit der Fixpunktgleichung versteh ich irgendwie nicht. Ich bin ganz durcheinander...
Kannst du mir helfen, wie ich das in meiner Facharbeit kurz erklären kann? bitte
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:44 Do 19.02.2009 | | Autor: | kalle754 |
Ich habe jetzt doch einigermaßen was verstanden.
Könntest du hier mal rüberschauen?
Das Newtonverfahren lässt sich auch als Form der Fixpunkt-Iteration interpretieren, indem man die zugehörige Funktion g(x) wie folgt definiert:
[mm] x_(n+1)=g(x_n [/mm] ) wird im Fall des Newtonverfahrens zu [mm] g(x)=x_n-(f(x_n))/(f´(x_n)).
[/mm]
Die allgemeine Ableitung von wird gebildet, um Konvergenzaussagen aufzustellen.
g´(x)=(f(x)∙f´´(x))/([f´(x)]²)
Da [mm] f(x_s)=0 [/mm] ist [mm] (x_s [/mm] ist die Nullstelle von der Funktion f und soll die Gleichung f(x)=0 lösen), folgt
[mm] g´(x_s [/mm] )=0 .
Wenn sich also g´ in der Nähe von [mm] x_s [/mm] nicht allzu stark ändert, ist die Bedingung
[mm] |g´(x_s [/mm] ) |≤q<1
Nahe bei [mm] x_s [/mm] für ein sehr kleines q>0 und damit besonders gut zu erfüllen. Zu erwarten ist also eine sehr schnelle Konvergenz.
Der Konvergenzsatz beruht jedoch auf der Angabe eines Intervalls. Die Wahl eines allgemeinen Intervalls ist nicht möglich, da dieses von der Funktion f abhängt. Daher kann die Konvergenz des Verfahrens nicht allgemein gesichert werden.
Der Startwert [mm] x_0 [/mm] muss also nahe genug an der Nullstelle liegen, wenn diese Eigenschaft erfüllt ist, ist allerdings eine gute Lokalisierung der Nullstelle möglich.
Is das gut und Fehlerfrei, so um es kurz in der Facharbeit anzusprechen?
Muss es morgen dem Fachlehrer zeigen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:15 Do 19.02.2009 | | Autor: | leduart |
Hallo
Zu allererst solltest du sagen, was eine Fixpunktgleichung ist:
gesucht ist der Punkt der Abbildung g(x) der auf sich selbst abgebildet wird also der Punkt fuer den gilt g(x)=x.
Solche Fixpunkte kann man oft durch ein Iterationsverfahren finden.
man faengt mit einem Punkt [mm] x_0 [/mm] an, und bildet [mm] x_1=g(x_0) [/mm] und immer so weiter, also [mm] x_{n+1}=g(x_n)
[/mm]
So ein verfahren fuehrt zu dem gesuchten Fixpunkt wenn gilt, dass [mm] x_n, x_{n+1} [/mm] naeher aneinander liegen als [mm] x_{n-1},x_n
[/mm]
Wenn der Abstand nicht nur kleiner wird, sondern gegen 0 konvergiert kommt man so zum fixpunkt.
Das ist der Fall, wenn g'(x) in dem gebiet, aus dem die [mm] x_i [/mm] stammen kleiner als q,1 sind.
(Jetzt kommt der Beweis den ich dir vorgemacht habe)
....
Jetzt erst kommt: auch das Newtonverfahren kann man als Fixpunktverfahren auffassen, wenn man g(x)=x-f(x)/f'(x) auffasst. denn dann hat man ja die newtoniteration [mm] x_{n+1}=g(x_n)
[/mm]
Dieses "Umdenken" ist deshalb praktisch, weil wir jetzt leichter sehen koennen, dass 1. das newtonverfahren immer klappt, wenn man nahe genug an der Nullstelle anfaengt, aber auch zeigt, wie weit davon weg man noch anfangen kann, wenn man f' und f'' kennt und sie stetig sind.
> Könntest du hier mal rüberschauen?
>
> Das Newtonverfahren lässt sich auch als Form der
> Fixpunkt-Iteration interpretieren, indem man die zugehörige
> Funktion g(x) wie folgt definiert:
hier hab ich oben gesagt, dass ich denke man muss da erst genauer drueber reden
> [mm]x_{n+1}=g(x_n[/mm] ) wird im Fall des Newtonverfahrens zu
> [mm]g(x)=x_n-(f(x_n))/(f´(x_n)).[/mm]
>
> Die allgemeine Ableitung von wird gebildet, um
> Konvergenzaussagen aufzustellen.
Warum "allgemeine Ableitung? und nicht enfach Ableitung?
Wenn du den vorgeschlagenen Vorderteil hast ist klar warum man g' ansieht
> g´(x)=(f(x)∙f´´(x))/([f´(x)]²)
>
> Da [mm]f(x_s)=0[/mm] ist [mm](x_s[/mm] ist die Nullstelle von der Funktion f
> und soll die Gleichung f(x)=0 lösen), folgt
> [mm]g´(x_s[/mm] )=0 .
>
> Wenn sich also g´ in der Nähe von [mm]x_s[/mm] nicht allzu stark
> ändert, ist die Bedingung
> [mm] |g´(x_s[/mm] ) |≤q<1
Nicht Wenn sich g' nicht allzustark aendert, sondern WEIL g' stetig ist, MUSS es eine umgebung von [mm] x_s [/mm] geben in der g'(x)<q<1 ist. (je nach g bzw. f kann diese Umgebung sehr gross sein oder auch klein )
> Nahe bei [mm]x_s[/mm] für ein sehr kleines q>0 und damit besonders
> gut zu erfüllen. Zu erwarten ist also eine sehr schnelle
> Konvergenz.
Wenn man nahe bei [mm] x_s [/mm] anfaengt, aber auch noch gute konvergenz, wenn man nur irgendwo anfaengt, wo g'<q<1
> Der Konvergenzsatz beruht jedoch auf der Angabe eines
> Intervalls. Die Wahl eines allgemeinen Intervalls ist nicht
> möglich, da dieses von der Funktion f abhängt. Daher kann
> die Konvergenz des Verfahrens nicht allgemein gesichert
> werden.
Doch, nur eben nur in ner kleinen Umgebung von [mm] x_s [/mm] wenn nur [mm] f'(x)\ne0
[/mm]
> Der Startwert [mm]x_0[/mm] muss also nahe genug an der Nullstelle
> liegen, wenn diese Eigenschaft erfüllt ist, ist allerdings
> eine gute Lokalisierung der Nullstelle möglich.
>
Ich hab dir Praezissierungen aufgezeigt. ob du es so machen willst, oder kuerzer ist deine Sache.
Mir scheint dass du einige Unsicherheit bei der Darstellung zeigst.
Wenn dus neu aufschreibst, korrigier ich dir es gern noch mal.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:53 Do 19.02.2009 | | Autor: | kalle754 |
Das Newtonverfahren lässt sich auch als Form der Fixpunkt-Iteration interpretieren. In einer Fixpunktgleichung ist der Punkt der Abbildung g(x) gesucht der auf sich selbst abgebildet wird, also der Punkt für den gilt g(x)=x .
Solche Fixpunkte kann man oft durch ein Iterationsverfahren finden. Man fängt mit einem Punkt [mm] x_0 [/mm] an und bildet [mm] x_1=g(x_0) [/mm] und immer so weiter, also gilt:
[mm] x_(n+1)=g(x_n [/mm] )
So ein Verfahren führt zu dem gesuchten Fixpunkt wenn gilt, dass [mm] x_n∙x_(n+1) [/mm] näher aneinander liegt als [mm] x_(n-1)∙x_n [/mm] .
Wenn der Abstand nicht nur kleiner wird, sondern gegen 0 konvergiert kommt man zum Fixpunkt. Das ist der Fall, wenn [mm] g´(x_s) [/mm] im Intervall (a,b) kleiner als q und q kleiner 1 ist.
Daher lässt sich das Newtonverfahren als Form der Fixpunkt-Iteration interpretieren,
indem man die zugehörige Funktion g(x) wie folgt definiert:
wird im Fall des Newtonverfahrens zu [mm] g(x)=x_n-(f(x_n))/(f´(x_n)).
[/mm]
Die Ableitung von wird gebildet, um Konvergenzaussagen aufzustellen.
g´(x)=(f(x)∙f´´(x))/([f´(x)]²)
Da [mm] f(x_s)=0 [/mm] ist [mm] (x_s [/mm] ist die allgemeine Nullstelle der Funktion f und soll die Gleichung f(x)=0 lösen), folgt
[mm] g´(x_s [/mm] )=0 .
Wenn also g´ in der Nähe von [mm] x_s [/mm] stetig ist, muss es ein Intervall von [mm] x_s [/mm] geben in dem
[mm] |g´(x_s [/mm] ) |≤q<1
gilt. (Je nach g bzw. f kann dieses Intervall sehr groß oder klein sein.) Zu erwarten ist also eine sehr schnelle Konvergenz.
Der Startwert [mm] x_0 [/mm] muss also nahe genug an der Nullstelle liegen, wenn diese Eigenschaft erfüllt ist, ist allerdings eine gute Lokalisierung der Nullstelle möglich.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:02 Do 19.02.2009 | | Autor: | leduart |
Hallo
> Das Newtonverfahren lässt sich auch als Form der
> Fixpunkt-Iteration interpretieren. In einer
> Fixpunktgleichung ist der Punkt der Abbildung g(x) gesucht
> der auf sich selbst abgebildet wird, also der Punkt für den
> gilt g(x)=x .
> Solche Fixpunkte kann man oft durch ein
> Iterationsverfahren finden. Man fängt mit einem Punkt [mm]x_0[/mm]
> an und bildet [mm]x_1=g(x_0)[/mm] und immer so weiter, also gilt:
>
> [mm]x_(n+1)=g(x_n[/mm] )
> So ein Verfahren führt zu dem gesuchten Fixpunkt wenn
> gilt, dass [mm]x_n;x_(n+1)[/mm] näher aneinander liegt als
> [mm]x_(n-1);x_n[/mm] .
> Wenn der Abstand nicht nur kleiner wird, sondern gegen 0
> konvergiert kommt man zum Fixpunkt. Das ist der Fall, wenn
> [mm]g´(x_s)[/mm] im Intervall (a,b) kleiner als q und q kleiner 1
> ist.
>
> Daher lässt sich das Newtonverfahren als Form der
> Fixpunkt-Iteration interpretieren,
>
> indem man die zugehörige Funktion g(x) wie folgt definiert:
> wird im Fall des Newtonverfahrens zu
> [mm]g(x)=x_n-(f(x_n))/(f´(x_n)).[/mm]
so falsch, in g(x) muss x, nicht [mm] x_n [/mm] stehen. bie der Iteration erst kommt da [mm] x_n [/mm] rein!
> Die Ableitung von wird gebildet, um Konvergenzaussagen
> aufzustellen.
>
> g´(x)=(f(x)∙f´´(x))/([f´(x)]²)
>
> Da [mm]f(x_s)=0[/mm] ist [mm](x_s[/mm] ist die allgemeine Nullstelle der
> Funktion f und soll die Gleichung f(x)=0 lösen), folgt
> [mm]g´(x_s[/mm] )=0 .
> Wenn also g´ in der Nähe von [mm]x_s[/mm] stetig ist, muss es ein
> Intervall von [mm]x_s[/mm] geben in dem
> [mm] |g´(x_s[/mm] ) q<1
> gilt. (Je nach g bzw. f kann dieses Intervall sehr groß
> oder klein sein.) Zu erwarten ist also eine sehr schnelle
> Konvergenz.
> Der Startwert [mm]x_0[/mm] muss also nahe genug an der Nullstelle
So falsch! er muss nicht nahe liegen, dafuer hatte ich dir ein Bsp. geschrieben, sonder n WENN er nahe ist gilt sicher g'<q<1 es kann aber auch fuer grosse Gebiete gelten.
> liegen, wenn diese Eigenschaft erfüllt ist, ist allerdings
> eine gute Lokalisierung der Nullstelle möglich.
es fehlt [mm] f'\ne0
[/mm]
und es fehlt der beweis, dass fuer g'<q<1 die Fixpunktiteration konvergiert.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:19 Do 19.02.2009 | | Autor: | kalle754 |
"es fehlt f´(x)=0
und es fehlt der beweis, dass fuer g'<q<1 die Fixpunktiteration konvergiert. "
Wo muss den f´(x)=0 hin?
Und wie lautett der Beweis?
hm..hört sich das denn sonst schon ganz gut an?
Danke für deine Hilfe!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:25 Do 19.02.2009 | | Autor: | leduart |
Hallo
wenn [mm] f'(x_s)=0 [/mm] ist am Fixpunkt (oder sehr nahe, dann ist g' riesig, bzw unendlich, da ja f" im nenner steht.
also "doppelte Nullstellen" (Minima oder Max die auch Nst. sind findet das Newtonverfahren nicht.
Den Beweis hatte ich dir in einem meiner posts geschrieben , lies die noch mal durch.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:57 Do 19.02.2009 | | Autor: | kalle754 |
So habe den Text nochmal abgeändert. Das Forum spielt bei mir irgendwie verrückt.
Ich hoffe das ist jetzt so richtig.
Das Newtonverfahren lässt sich auch als Form der Fixpunkt-Iteration interpretieren. In einer Fixpunktgleichung ist der Punkt der Abbildung g(x) gesucht der auf sich selbst abgebildet wird, also der Punkt für den gilt g(x)=x .
Solche Fixpunkte kann man oft durch ein Iterationsverfahren finden. Man fängt mit einem Punkt [mm] x_0 [/mm] an und bildet [mm] x_1=g(x_0) [/mm] und immer so weiter, also gilt:
[mm] x_(n+1)=g(x_n [/mm] )
So ein Verfahren führt zu dem gesuchten Fixpunkt wenn gilt, dass [mm] x_n∙x_(n+1) [/mm] näher aneinander liegt als [mm] x_(n-1)∙x_n [/mm] .
>>>>>Den obigen Satz versteh ich noch nicht<<<<<<<<
Wenn der Abstand nicht nur kleiner wird, sondern gegen 0 konvergiert kommt man zum Fixpunkt. Das ist der Fall, wenn [mm] g´(x_s) [/mm] im Intervall (a, b) kleiner als q und q kleiner 1 ist.
Daher lässt sich das Newtonverfahren als Form der Fixpunkt-Iteration interpretieren,
indem man die zugehörige Funktion g(x) wie folgt definiert:
g(x)=x-(f(x))/(f´(x)).
Die Ableitung von wird gebildet, um Konvergenzaussagen aufzustellen.
g´(x)=(f(x)∙f´´(x))/([f´(x)]²)
Da [mm] f(x_s)=0 [/mm] ist [mm] (x_s [/mm] ist die allgemeine Nullstelle der Funktion f und soll die Gleichung f(x)=0 lösen)
und f´(x)≠0, folgt
[mm] g´(x_s [/mm] )=0 .
Im Fixpunkt selbst ist die Ableitung 0 und der Fixpunkt ist die Nullstelle von f(x).
g´(x) ist also nicht 0, sondern nur wenn man mit der richtigen Nullstelle angfängt. Normalerweise fängt man mit irgendeinem x die Iteration an und in dem Intervall dieser Näherungswerte muss g´≤q<1 gelten.
Wenn also g´ in der Nähe von [mm] x_s [/mm] stetig ist, muss es ein Intervall von [mm] x_s [/mm] geben in dem
[mm] |g´(x_s [/mm] ) |≤q<1
gilt. (Je nach g bzw. f kann dieses Intervall sehr groß oder klein sein.)
Es wurde die Stetigkeit von g' benutzt um zu sagen, dass auf jeden Fall in der Nähe von g'=0 (hier in einem Intervall (a,b) um den Fixpunkt g'<q<1 gibt) damit die Iteration der Fixpunktfunktion konvergiert.
Zu erwarten ist also eine sehr schnelle Konvergenz.
Wenn diese Eigenschaften erfüllt sind, ist eine gute Lokalisierung der Nullstelle möglich.
Fehlt noch etwas?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:12 Do 19.02.2009 | | Autor: | leduart |
Hallo
Bei mir spinnt das forum auch und zeigt keine formeln mehr an. Ich hoffe deine sind richtig.
Wenn [mm] |x_{n+1}-x_n|<|x_{n-1}-x_n| [/mm] ist heisst das doch dass [mm] x_{n+1} [/mm] naeher am fixpkt liegt als [mm] x_n
[/mm]
denn [mm] x_{n+1}=g(x_n) [/mm] dann ist doch der Unterschied
[mm] |g(x_n)-x_n| [/mm] kleiner, d.h. du bist naeher an x=g(x) (da ist der Unterschied 0
jetzt hatte ich dir gezeigt, dass der Abstand jedesmal mindestens mit dem Faktor q verkleinert wird, wenn g'<q<1 ist.
Siehe mein post Mi 20Uhr22.
Wenn du die Formeln nicht lesen kannst: mach zu dem Artikel ne Mitteilung auf, klick unter dem Fenster zitieren an, dann siehst du in unschoener form, was ich geschrieben hab.
Wenn du dann nichts mitteilen willst sondern nur lesen, geh einfach auf abbrechen statt senden.
Da du ja ne Menge meiner Saetze benutzt hast, muss ich wohl was du geschrieben hast ganz gut finden, bis auf den fehlenden Beweis, aber ob den dein Lehrer will, kannst du ja erst testen indem du es ihm erstmal ohne zeigst.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:33 Do 19.02.2009 | | Autor: | kalle754 |
So ein Verfahren führt zu dem gesuchten Fixpunkt wenn gilt, dass [mm] x_n∙x_(n+1) [/mm] näher aneinander liegt als [mm] x_(n-1)∙x_n [/mm] .
steht da [mm] x_n [/mm] mal [mm] x_x+1 [/mm] oder minus?
kann das nicht erkennen...
Ist der restliche text denn jetzt richtig?
MFG
|
|
|
| |
|
Hallo Kalle,
da Du den Stand morgen schon vorlegen musst, würde ich Dir ja glatt noch helfen, aber es geht im Moment technisch nicht, wie Du sicher auch siehst. Nicht nur, dass die Oberfläche ziemlich zerstört ist, auch die Beiträge sind eigentlich nicht mehr lesbar, da die ganzen Formelgrafiken nicht geladen werden. Und alles aus den Hover-Boxen (die Dinger, die erscheinen, wenn man mit dem Mauszeiger über eine der Grafiken fährt) im Quelltext zu lesen, ist bei einem so langen Diskussionsstrang überhaupt nicht erquicklich.
Nach dem, was ich bis heute Abend noch mitverfolgt habe, bist Du aber auf einem guten Weg. Wenn morgen nur die Zwischenberatung ist und nicht gleich Abgabe, dann kannst Du mit Deinen Ergebnissen bestimmt hingehen.
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:36 Fr 20.02.2009 | | Autor: | kalle754 |
oh da hab ich mich wohl falsch ausgedrückt, morgen ist Abgabetermin.
Schade wegen den technischen Problemen.
Ich brauch eigentlich nur ne Antwort auf meine letzte Frage.
was da zwischen [mm] x_n [/mm] und [mm] x_n+1 [/mm] für ein zeichen steht?
das gleiche Problem bei [mm] x_n-1 [/mm] und [mm] x_n?
[/mm]
Ein Komma?
Weil der Satz hat für mich keinen Sinn ergeben.
Sonst hab ich eigentlich schon viel verstanden. Und ich denke das reicht auch für ne Facharbeit.
|
|
|
| |
|
Na dann: da steht ein Minus, soweit ich sehe und verstehe. Ein Multiplikationszeichen würde angesichts der Betrachtung doch auch keinen Sinn ergeben.
Viel Erfolg! - und gute Nacht. 
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:09 Fr 20.02.2009 | | Autor: | kalle754 |
aber es steht doch nicht bei beiden ein minus oder?
in den vorherigen Posts kam das auch schon vor.
Vielen Dank und ebenfalls gute Nach!
|
|
|
| |
|
Doch, bei beiden ein Minus.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:05 Fr 20.02.2009 | | Autor: | leduart |
Hallo
Es ist der Abstand zwischen den 2 aufeinanderfolgenden x, also muss es ein Minus sein
Gruss leduart
|
|
|
| |
|
> es gilt [mm](f(x_n)-f(x_{n+1})/(x_n-x_{n+1})=f'(\xi)[/mm] mit [mm]\xi[/mm]
> aus dem intervall
> falls [mm]f(\xi)=q<1[/mm] ist gilt dann:
> [mm]|f(x_n)-f(x_{n+1}|
> aber [mm]f(x_n)=x_{n+1} f(x_{n+1})=x_{n+2}[/mm]
> Du siehst, wenn
> die Ableitung echt kleiner 1 ist, wird der Abstand
> jedesmal um den Faktor q verkleinert.
> (ich hab jetzt immer f geschrieben, damit aber das g(x)
> gemeint, von dem wir den Fixpkt suchen)
Also muss ich jetzt überall (beim Zitierten) das f durch ein g ersetzen? So oder so, ich kann mir beides nicht ganz erklären.
Möchte das jemand vielleicht detailliert erklären?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:43 Do 18.03.2010 | | Autor: | leduart |
Hallo
erstmal zum Erklären.
du suchst nen Fixpunkt von g(x) also einen Punkt mit g(x)=x
du fängst an mit [mm] x_0 [/mm] und hast dann [mm] x1=g(x_0) x_2=g(x1)
[/mm]
jetzt betrachte g(x1)-g(x2) und vergleiche mit [mm] (x_2-x1)
[/mm]
(g(x1)-g(x2)/ [mm] (x_2-x1) [/mm] ist die Stigung der Sehne, die ist ungefähr gleich der Tangente,in x1 oder genau = einer Tangente in einem Punkt zwischen x1 und x2
den Punkt nenn ich X
es gilt also (g(x1)-g(x2)/ [mm] (x_2-x1) [/mm] =g'(X) oder (g(x1)-g(x2)=g'(X)*(x2-x1)
wenn g' also kleiner ist als 1 ist g(x2) näher an g(x1)=x2 [mm] g(x_1) [/mm] an [mm] g(x_0)=x1
[/mm]
und zwar um den Faktor g'(X) näher. wenn jetzt alle g' in dem betrachteten Bereich kleiner als 1 sind, verkleinert sich der Abstand zwischen [mm] x_n [/mm] und [mm] g(x_n) [/mm] jedesmal um den Faktor g'
wenn z. Bsp, g' überall wo du grade bist <0,5 ist halbiert sich derAbstand zw. [mm] x_n [/mm] und [mm] g(x_n) [/mm] jedesmal um mindestens einen Faktor 0.5
Gruss leduart
|
|
|
| |
|
Ich habe noch einige Fragen.
Mir ist die "Funktionisierung" des Newton-Verfahren an sich klar, doch habe ich mir den Graphen an einem Beispiel angeschaut [mm] (f(x)=x^{2} [/mm] - 2 ). Bei diesem Graphen (hier g(x)) suchen wir den Fixpunkt, der dann die Nullstelle für f(x) angibt. Bei g(x) muss die Steigung 0 sein, deswegen ja auch: g'(x)=0=f(x). Aber warum ist die Steigung dann 0?
Und wenn bei dieser Konvergenzbedingung g'(x)>1 ist, dann ist dieser Startwert (manchmal) ein schlechter Startwert, so wie ich es hier herausgelesen habe. Aber wieso? Was könnte im schlimmsten Fall passieren?
Danke!
|
|
|
| |
|
> Ich habe noch einige Fragen.
>
> Mir ist die "Funktionisierung" des Newton-Verfahren an sich
> klar, doch habe ich mir den Graphen an einem Beispiel
> angeschaut [mm](f(x)=x^{2}[/mm] - 2 ). Bei diesem Graphen (hier
> g(x)) suchen wir den Fixpunkt, der dann die Nullstelle für
> f(x) angibt. Bei g(x) muss die Steigung 0 sein, deswegen ja
> auch: g'(x)=0=f(x). Aber warum ist die Steigung dann 0?
Nun du suchst doch die Lösung der Gleichung f(x)=0 mit dem Newton-Verfahren. g(x) ist nicht der Graph von f(x) sondern die Iterationsfunktion [mm] x_{n+1} [/mm] = [mm] x_{n} [/mm] - [mm] \bruch{f(x_{n})}{f'(x_{n})} [/mm] diese wird beim Fixpunkt, welcher ja die Lösung von f(x) ist =0 (oder [mm] \rightarrow [/mm] 0) d.h. der Funktionswert von g(x) ändert sich nicht mehr, du hast deine Lösung gefunden! Deswegen g(x)=f(x)=0
>
> Und wenn bei dieser Konvergenzbedingung g'(x)>1 ist, dann
> ist dieser Startwert (manchmal) ein schlechter Startwert,
> so wie ich es hier herausgelesen habe. Aber wieso? Was
> könnte im schlimmsten Fall passieren?
nun wenn g'(x)>1 ist, dann hast du einen sogenannten abstoßenden Fixpunkt. Deine Iteration bringt dich immer weiter weg von deiner Lösung.
Das schlimmste ist damit, dass du rechnest und rechnest und nichts damit erreichst....
> Danke!
Gruss Christian
|
|
|
| |
|
> Nun du suchst doch die Lösung der Gleichung f(x)=0 mit
> dem Newton-Verfahren. g(x) ist nicht der Graph von f(x)
> sondern die Iterationsfunktion [mm]x_{n+1}[/mm] = [mm]x_{n}[/mm] -
> [mm]\bruch{f(x_{n})}{f'(x_{n})}[/mm] diese wird beim Fixpunkt,
> welcher ja die Lösung von f(x) ist =0 (oder [mm]\rightarrow[/mm] 0)
> d.h. der Funktionswert von g(x) ändert sich nicht mehr, du
> hast deine Lösung gefunden! Deswegen g(x)=f(x)=0
Ja, mir war schon klar, dass der Graph von g(x) nicht f(x) ist. (Zugegeben, habe mich etwas missverständlich ausgedrückt). Aber ich glaube, deine letzte Gleichung "g(x)=f(x)=0" stimmt nicht. Du meinst wohl g'(x), oder? Denn der gesuchte Punkt g(x) ist nicht die Nullstelle, sondern der Fixpunkt, der in meinem Beispiel [mm] P(\wurzel{2}|\wurzel{2}) [/mm] ist.
Aber die Frage ist nicht mehr zu beantworten, ich hätte mir am Besten gleich den Graphen etwas genauer anschauen sollen.
> nun wenn g'(x)>1 ist, dann hast du einen sogenannten
> abstoßenden Fixpunkt. Deine Iteration bringt dich immer
> weiter weg von deiner Lösung.
> Das schlimmste ist damit, dass du rechnest und rechnest
> und nichts damit erreichst....
> > Danke!
> Gruss Christian
Ah, OK! Jetzt suche ich nur noch ein Beispiel dafür, aber das mache ich wohl alleine.
Dankeschön! Mir ist jetzt alles verständlich.
|
|
|
|
