Newton-Verfahren < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:40 Mi 15.12.2010 | | Autor: | dennis2 |
| Aufgabe | Das Konvergenzverhalten des Newton-Verfahrens soll am Beispiel der Nullstellenbestimmung der Funktion
[mm] f(x)=x^3-2x, x\in [/mm] [-2,2]
untersucht werden.
(a) Konvergiert das Newton-Verfahren mit dem Startwert [mm] x_0=2?
[/mm]
(b) Bestimmen Sie ein (möglichst großes) Intervall I, sodass für alle Startwerte [mm] x_0 \in [/mm] I das Newton-Verfahren gegen 0 konvergiert. |
Zu (a):
Genügt es hier, wenn man einfach zeigt bzw. ausrechnet, dass das Verfahren gegen einen Wert (eine Nullstelle) konvergiert? Wenn ich richtig gerechnet habe, dann bekommt man nämlich schon nach 4 Schritten, dass das Verfahren gegen [mm] \wurzel{2} [/mm] konvergiert, was tatsächlich eine der Nullstellen ist.
(b) Braucht man hier, dass das Newtonverfahren auch eine Fixpunktiteration ist?
Bei (b) würde ich mich über einen kleinen Tipp sehr freuen.
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:44 Mi 15.12.2010 | | Autor: | dennis2 |
| Aufgabe | Ich habe zu (b) irgendwo gelesen, dass man zunächst ein Intervall (a,b) bestimmt, für das [mm] |\phi(x)'|<1 [/mm] gilt.
In meinem Beispiel wäre das für (-1,1) der Fall. |
Wieso macht man das?
(Worin liegt das begründet?)
Und wie macht man dann weiter?
Ich habe dann ausgerechnet, für welche Werte gilt:
f(x)=-1 und f(x)=1 und habe als gesuchtes Intervall
I=(-0.618034,0.618034) und wenn ich das nachrechne (z.B. mit einem Online-Rechner), scheint das auch beinah das Intervall aller Startwerte zu sein, für die das Newton-Verfahren gegen 0 konvergiert.
Ich verstehe aber nicht, was da hintersteckt.
Wer kann mir das erklären?
|
|
|
| |
|
Hallo dennis2,
> Das Konvergenzverhalten des Newton-Verfahrens soll am
> Beispiel der Nullstellenbestimmung der Funktion
>
> [mm]f(x)=x^3-2x, x\in[/mm] [-2,2]
>
> untersucht werden.
>
> (a) Konvergiert das Newton-Verfahren mit dem Startwert
> [mm]x_0=2?[/mm]
>
> (b) Bestimmen Sie ein (möglichst großes) Intervall I,
> sodass für alle Startwerte [mm]x_0 \in[/mm] I das Newton-Verfahren
> gegen 0 konvergiert.
> Zu (a):
>
> Genügt es hier, wenn man einfach zeigt bzw. ausrechnet,
> dass das Verfahren gegen einen Wert (eine Nullstelle)
> konvergiert? Wenn ich richtig gerechnet habe, dann bekommt
> man nämlich schon nach 4 Schritten, dass das Verfahren
> gegen [mm]\wurzel{2}[/mm] konvergiert, was tatsächlich eine der
> Nullstellen ist.
Nein, das genügt nicht.
Es ist doch zu zeigen, daß
[mm]\vmat{\bruch{f\left(x\right)*f''\left(x\right)}{\left(f'\left(x\right)\right)^{2}}} < 1[/mm]
für x=2 ist.
>
> (b) Braucht man hier, dass das Newtonverfahren auch eine
> Fixpunktiteration ist?
>
> Bei (b) würde ich mich über einen kleinen Tipp sehr
> freuen.
Hier muss das Intervall aus
[mm]\vmat{\bruch{f\left(x\right)*f''\left(x\right)}{\left(f'\left(x\right)\right)^{2}}} < 1[/mm]
bestimmt werden.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 06:36 Do 16.12.2010 | | Autor: | dennis2 |
| Aufgabe | Danke für den wichtigen Hinweis!
Warum muss man bei (a) gerade das zeigen? |
[Als Tipp habe ich von einem Tutor bekommen, dass man den Banachschen Fixpunktsatz verwenden soll, s. meine weiteren Fragen und meine Mitteilung. Es kann auch gut sein, dass Du den gleichen Tipp gegeben hast und ich es nur nicht sehe.]
Zunächst aber zum ersten Tipp:
Das heißt für (a):
[mm] f(x)=x^3-2x;
[/mm]
[mm] f'(x)=3x^2-2;
[/mm]
[mm] f''(x)=6x [/mm]
[mm] \bruch{f(x)*f''(x)}{(f'(x))^2}=\bruch{6x^2*(x^2-2)}{9x^4-12x^2+4}
[/mm]
[Die Betragsstriche fehlen hier, ich wusste nicht, wie man das hier hinbekommt.]
Und jetzt muss ich einfach nur x=2 einsetzen??
Also dann ergibt sich:
[mm] \bruch{48}{100}=0.48<1.
[/mm]
Das war die (a)?
Ich verstehe wirklich nicht, was man hier gemacht hat und was das mit dem Newton-Verfahren zu tun hat. Das kommt mir so einfach vor, ich dachte, das wäre hier viel schwieriger gemeint.
Und zu (b):
Wie bestimmt man denn ein Intervall aus
$ [mm] \vmat{\bruch{f\left(x\right)\cdot{}f''\left(x\right)}{\left(f'\left(x\right)\right)^{2}}} [/mm] < 1 $ ??
Verstehe nicht so ganz, was Du damit meinst.
Kannst Du es vllt. erklären, sodass auch ich das verstehe?
Wenn ich es recht verstanden habe, dann gilt die Bedingung genau dann, wenn [mm] x\not= [/mm] -0.816497 und [mm] x\not= [/mm] 0.816497 (das sind die Nullstellen der ersten Ableitung, also die Extremstellen der Funktion).
Das bringt mich aber irgendwie nicht weiter bzw. ich begreife vielleicht nicht, was Du gemeint hast.
Wir hatten in der Vorlesung einen Satz, der mir für diesen Fall sehr passend erscheint:
Sei [mm] g:\IR \to \IR [/mm] eine [mm] C^p [/mm] Funktion mit [mm] p\in \IN_+. [/mm] Sei [mm] \overline{x} [/mm] ein Fixpunkt mit
(a) [mm] |g'(\overline{x})|<1 [/mm] für p=1
(b) [mm] g^{(i)}(\overline{x})=0 [/mm] (i=1,...,p-1),p>1
Dann gibt es ein Intervall [mm] I=[\overline{x}-\delta,\overline{x}+\delta],\delta [/mm] >0, sodass für alle [mm] x_0\in [/mm] I die Iteration [mm] x_{k+1}=g(x_k),k=0,1,2,... [/mm] konvergent vom Grade p ist mit [mm] \limes_{k\rightarrow\infty}\bruch{|x_{k+1}-\overline{x}|}{|x_k-\overline{x}|^p}=\bruch{1}{p!}g^{(p)}(\overline{x}).
[/mm]
Kann man damit vllt. arbeiten?
Denn ich habe mal ausgerechnet, wann gilt |g'(0)|<1.
Das ist schonmal für das Intervall (-1,1) der Fall.
Und dann habe ich geguckt, wann f(x) die Werte 1 bzw. -1 annimt und das ist für ca. 0.61 bzw. 0.62 der Fall.
Und http://www.arndt-bruenner.de/mathe/java/newton.htm verrät mir, dass die Werte wohl ganz gut hinkommen und das Intervall demnach so in etwa [-0.63,0.63] sein muss, damit das Verfahren für Startwerte aus diesem Intervall gegen 0 konvergiert.
Liebe Grüße und nochmal vielen Dank bis hierher!!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:26 Do 16.12.2010 | | Autor: | dennis2 |
Ich habe den Tipp bekommen, man könne (a) auch mit Hilfe des Banachschen Fixpunktsatzes beweisen. Ich habe noch nie mit diesem Satz konkreten Umgang gehabt, darum wäre es nett, wenn jemand einen Blick über Folgendes wirft:
Zunächst nenne ich nochmal den Banachschen Fixpunktsatz, damit man sieht, wonach ich mich richten muss:
Banachscher Fixpunktsatz :
Sei [mm] \phi:E\to E,E=\IR^n, [/mm] eine [mm] Iterationsfunktion,x_0\in [/mm] E ein Startvektor und [mm] x_{i+1}:=\phi(x_i),i=0,1,... [/mm] . Es gebe eine Umgebung [mm] S_r(x_0):=\{x| ||x-x_0||
I.) [mm] ||\phi(x)-\phi(y)||\le [/mm] K*||x-y|| für alle [mm] x,y\in \overline{S_r(x_0)}:=\{x| ||x-x_0||\le r\},
[/mm]
II.) [mm] ||x_1-x_0||=||\phi(x_0)-x_0||\le [/mm] (1-K)r<r.
Dann gilt:
1) [mm] x_i\in S_r(x_0) [/mm] für alle i=0,1,...;
2) [mm] \phi [/mm] besitzt in [mm] S_r(x_0) [/mm] genau einen Fixpunkt [mm] x',\phi(x')=x', [/mm] und es gilt [mm] \limes_{i\rightarrow\infty}x_i=x', ||x_{i+1}-x'||\le K||x_i-x'||,
[/mm]
und die Fehlerabschätzung
[mm] ||x_i-x'||\le \bruch{Kî}{1-K}||x_1-x_0||.
[/mm]
Das alles muss ich jetzt wohl nachweisen für das Newton-Verfahren und den Startwert [mm] x_0=2.
[/mm]
Ich würde mich freuen, wenn mir jemand behilflich sein könnte.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:27 Do 16.12.2010 | | Autor: | dennis2 |
Hier ist mein Versuch, (a) mittels des Banachschen Fixpunktsatzes zu lösen:
Zunächst:
[mm] x_{k+1}=\phi(x) [/mm] mit [mm] \phi(x)=x-\bruch{x^3-2x}{3x^2-2}.
[/mm]
Betrachte das Intervall [mm] I=[\wurzel{2},2],\phi:I\to [/mm] I,k=0,1,... .
Setze K=0,4
r=1
[mm] S_r(2)=\{x| |x-2|<1\}
[/mm]
Außerdem gelten unter diesen Voraussetzungen
[mm] |\phi(2)-\phi(\wurzel{2})|=0,185786\le 0,4*|2-\wurzel{2}|=0,23415
[/mm]
sowie
[mm] |x_1-x_0|=|\phi(2)-2|=0,4\le [/mm] (1-K)*r=0.6<1.
Damit sind alle Voraussetzungen des Banachschen Fixpunktsatzes (wie ich ihn in meiner Frage formuliert habe) m.E. erfüllt und es gibt im Intervall I genau einen Fixpunkt, gegen den [mm] \phi [/mm] konvergiert [Dieser ist [mm] \wurzel{2}, [/mm] danach hatte ich stillschweigend das Intervall gewählt].
Also konvergiert das Newton-Verfahren für den Startwert [mm] x_0=2\in [/mm] I.
Kann man das so zeigen?
Die anderen Folgerungen des Banachschen Fixpunktsatzes benötige ich hier ja eigentlich gar nicht, die Voraussetzungen sind ja aber alle erfüllt.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:56 Do 16.12.2010 | | Autor: | max3000 |
Hallo Dennis.
Für uns ist es sehr schwierig auf deine Fragen zu antworten, da wir nicht genau wissen, was für Konvergenzsätze in eurer Vorlesung für das Newton-Verfahren behandelt wurden.
Es gibt etliche Sätze, die hinreichende Bedingungen für Konvergenz bzw. lokal quadratische Konvergenz geben. Darüber werden ganze Bücher geschrieben. Das bekannteste dazu ist das von Deuflhard:
![[]](/images/popup.gif) http://www.zib.de/deuflhard/pub/newton.html
Falls du das Buch irgendwo ausleihen könntest würde ich dir empfehlen da mal rein zu lesen.
Ok, zu deiner Frage kann ich dir leider auch nicht helfen, weil ich deine letzte Mitteilung nicht verstehe, also warum K=0,4 gesetzt wird und was K überhaupt ist.
Jedenfalls... wenn das eine Übung zu deiner Numerik-Vorlesung sein sollte, dann wirst du sicherlich die Konvergenz mit einem Kriterium zeigen können, das ihr in der Vorlesung behandelt habt.
Ich denke auch dass du das mit dem Banachschen Fixpunktsatz vergessen kannst. Dieser dient eigentlich nur zum Beweis der üblichen Sätze, die es zum Newton-Verfahren gibt.
Wenn du an einer bestimmten Stelle nicht weiter kommst, dann poste bitte nochmal konkret in kurzer Fassung dein Problem.
Ansonsten verfolge doch mal den Hinweis von Mathepower.
Weitere Bedingungen sind zum Beispiel:
[mm] f:(a,b)\rightarrow\IR [/mm] ist konvex und 2 mal stetig differenzierbar
[mm] \Rightarrow [/mm]
Konvergenz für beliebiges [mm] x^0\in(a,b).
[/mm]
Ob das erfüllt ist würde ich auch mal nachprüfen.
Schönen Gruß.
Max
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:10 Do 16.12.2010 | | Autor: | dennis2 |
| Aufgabe | Ich verstehe jetzt nur noch Bahnhof!
Wieso sollte man es denn nicht so machen können, wie ich es mit dem Banachschen Fixpunktsatz zumindest versucht habe:
Man wählt ein Intervall, in dem der Startwert 2 enthalten ist und wenn man zeigen kann, das für dieses Intervall die Voraussetzungen des Satzes (den ich extra nochmal genannt habe und dort kann man auch sehen, was z.B. das K bedeuten soll) erfüllt sind, dann konvergiert das Verfahren für alle Startwerte aus diesem Intervall, also auch für 2, gegen den Fixpunkt. Also ist das Verfahren für den Startwert 2 konvergent.
Ich habe einfach mal K=0,4 usw. gewählt.
Es soll ein Beispielfall sein, der das zeigt. |
Ich lasse mich sehr gerne eines Besseren belehren, aber ich möchte erst verstehen, wieso man es so NICHT zeigen können sollte.
Zumal mein Tutor mir explizit diesen Tipp gegeben hat: Banachscher Fixpunktsatz.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:27 Do 16.12.2010 | | Autor: | max3000 |
Ok dann versuchen wir das mal mit BFPS (das ist jetzt für diese Thread die offizielle Abkürzung für Banachscher Fixpunktsatz).
Du hast ja deine Funktion [mm] \Phi [/mm] schon aufgestellt, die du auf Fixpunkte untersuchen willst.
Du musst noch Kontraktion zeigen, das heißt
[mm] |\Phi(x)-\Phi(y)|
Du hast das jetzt nur für [mm] x=\sqrt{x} [/mm] und [mm] y=\2 [/mm] gezeigt, dass das kleiner ist als irgendetwas. Das ist aber noch nicht die Kontraktion. Das muss für ALLE [mm] x,y\in(a,b) [/mm] gelten. Du musst jetzt denke ich geschickt deinen Bruch umstellen.
[mm] |\Phi(x)-\Phi(y)|=|\bruch{x^3-2x}{3x^2-2}-\bruch{y^3-2y}{3y^2-2}|
[/mm]
[mm] =|\bruch{(x^3-2x)(3y^2-2)-(y^3-2y)(3x^2-2)}{(3x^2-2)(3y^2-2)}|
[/mm]
[mm] =|\bruch{x(x^2-2)(3y^2-2)-y(y^2-2)(3x^2-2)}{(3x^2-2)(3y^2-2)}|
[/mm]
Meine Idee wäre es jetzt das ganze irgendwie gegen etwas der Form K(x,y)|x-y| nach oben abzuschätzen und dann zu zeigen, dass K(x,y) für alle x,y aus (a,b) kleiner ist als 1. Ich überleg auch noch etwas. Wenn uns das gelingen sollte, dann ist die Konvergenz gezeigt. Komme aber grad auch nicht weiter. Mit Mathematica lässt sich der Ausdruck auch nicht kürzen oder so. Vielleicht überseh ich ja grad irgendetwas.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:40 Do 16.12.2010 | | Autor: | dennis2 |
| Aufgabe | [mm] \phi(x)=x-\bruch{x^3-2x}{3x^2-2}
[/mm]
[mm] \phi(y)=y-\bruch{y^3-2y}{3y^2-2}
[/mm]
Hast Du nicht heweils die ersten Glieder vergessen? |
Oder sehe ich das nicht, dass du sie bereits verrechnet hast?
Dann erhalte ich für [mm] |\phi(x)-\phi(y)|=|\bruch{4x}{3(3x^2-2)}+\bruch{2x}{3}-\bruch{28}{27(3y-2)}+\bruch{y^2}{3}-\bruch{7y}{9}-\bruch{14}{27}|
[/mm]
Ist von Belang, dass in der Aufgabenstellung steht: [mm] x\in [/mm] [-2,2]?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:09 Do 16.12.2010 | | Autor: | leduart |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo
eigentlich war deine erste Anwendung des BFS schon fast richtig. nur wenn du x_0=2 nimmst und r=1 dann hast du ja Werte zw. 1 und 3
dann kann man k als max \Phi'(x) in [1,3} nehmen, du hast aber einfach nur für k \Phi'(2) genommen. eigentlich willst du r gar nicht so groß. wenn du also ein Interrvall was kleiner nimmst, kannst du ein k<1 finden und bist damit fertig. nur musst du es begründen. bei ersten Schritt kommst du ja von 2 weg, damit hast du dann \phi' an der neuen Stelle. nur wenn du im ganzen intervall |k|<1 hast konvergiert das Verfahren garantiert.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:26 Do 16.12.2010 | | Autor: | dennis2 |
| Aufgabe | Kann es sein, dass ich alles unnötig verkompliziert habe?
und ich mich lieber an MathePower gehalten hätte?
Denn: |
Ich habe Folgendes gefunden:
1.)
Banachscher Fixpunktsatz (einfach):
Sei [mm] \phi:[a,b]\to [/mm] [a,b] [mm] differenzierbar,|\phi'(x)|\le [/mm] q für alle [mm] x\in [/mm] [a,b] mit einem q<1. Dann hat [mm] \phi [/mm] in [a,b] genau einen Fixpunkt [mm] \overline{x} [/mm] und jede Folge [mm] (x_n)_{n\in \IN_0} [/mm] mit [mm] x_0\in [/mm] [a,b] und [mm] x_{n+1}=\phi(x_n) [/mm] (n=0,1,2,...) konvergiert gegen [mm] \overline{x}.
[/mm]
2.)
Kontraktionsbedingung:
[mm] |\phi'(x)|=$ \vmat{\bruch{f\left(x\right)\cdot{}f''\left(x\right)}{\left(f'\left(x\right)\right)^{2}}}\le [/mm] q<1.
Das heißt, ich muss das in den falschen Hals bekommen haben, mein Tutor meinte wahrscheinlich DIESE Version des Fixpunktsatzes (und die meinte auch MathePower).
Wenn ich jetzt für das Intervall [-2,2] das zeige, ist die Aufgabe (a) doch gelöst, richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:33 Do 16.12.2010 | | Autor: | leduart |
Hallo
ich krieg nicht in dem ganzen intervall |q|<1
in dem intervall liegen doch 3 Nst? 0, [mm] /pm\wurzel{2}
[/mm]
gegen welche soll das denn konv.?
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:35 Do 16.12.2010 | | Autor: | dennis2 |
| Aufgabe | Die Aufgabenstellung sagt gar nicht, gegen welche der Nullstellen das Verfahren für den Startwert 2 konvergiert (Es ist aber, das habe ich nachgerechnet, die Nullstelle [mm] \wurzel{2}).
[/mm]
Kann man dann das Intervall [a,b] kleiner wählen, damit die Aussage stimmt? |
Ich hatte genau aus diesem Grund das Intervall [mm] [\wurzel{2},2] [/mm] genommen, denn da liegt ja nur diese eine Nullstelle drinnen und für dieses Intervall gilt auch das Kontraktionskriterium. Damit wäre doch eigentlich gezeigt, dass das Verfahren halt für [mm] x_0=2 [/mm] (2 liegt in dem Intervall) gegen einen Fixpunkt konvergiert [Man soll ja eigentlich nur die Frage beantworten, OB das Verfahren für diesen speziellen Startwert konvergiert und das ist doch so gezeigt]. ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:20 Do 16.12.2010 | | Autor: | dennis2 |
| Aufgabe | | Und nochmal zu (b). |
Mathepower hatte geschrieben, dass man das gesuchte Intervall aus
$ [mm] \vmat{\bruch{f\left(x\right)\cdot{}f''\left(x\right)}{\left(f'\left(x\right)\right)^{2}}} [/mm] < 1 $
bestimmen muss.
Das habe ich so verstanden, dass ich schaue, wann diese Bedingung erfüllt ist.
Ich habe raus, dass das gilt, wenn [mm] x\not= [/mm] -0.816497 und [mm] x\not= [/mm] 0.816497.
Das heißt schonmal [mm] I\subseteq [/mm] (-0.816497,0,816497).
Aber ganz stimmt es noch nicht, denn z.B. für x=0,7 konvergiert das Verfahren gegen die Nullstelle [mm] \wurzel{2}.
[/mm]
Wie mache ich weiter?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:23 Do 16.12.2010 | | Autor: | leduart |
Hallo
dies ungleich ist komisch, du musst doch ein ganzes Intervall haben wo du <^hast und ausserhalb >1?
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:27 Do 16.12.2010 | | Autor: | dennis2 |
| Aufgabe | Ja, das ist wirklich komisch!
Was ist dein Vorschlag?
[Ich werde langsam verrückt an dieser blöden Aufgabe!] |
Wie findet man so ein Intervall denn bloß?!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:00 Do 16.12.2010 | | Autor: | max3000 |
Du hast doch die Ungleichung 0<K<1, die erfüllt werden soll. Beide Teile, also 0<K und K<1 stellst du so um, dass x nur auf einer Seite steht, dann hast du
a<x<b
und das ist dein Interval.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:21 Do 16.12.2010 | | Autor: | leduart |
Hallo
wenn du ein k<1 für dein ganzes intervall gegeben hast ist das ok, allerdings weiss man ja normalerweise die Nst nicht, ausserdem nicht, ob du von 2 aus noch weiter nach rechts kommst, also solltest du ein intervall um 2 rum nehmen, wo das Verfahren konv. in b) dann eins um 0 rum, oder zeigen, dass [mm] x_2
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:18 Do 16.12.2010 | | Autor: | dennis2 |
Was bedeutet denn, dass das Newton-Verfahren für einen Startwert gegen 0 konvergiert??
Ist hier gemeint: Gegen die endgültige Nullstelle 0?
Oder soll man hier jetzt davon ausgehen, dass man weiß, dass 0eine Nullstelle ist und deswegen findet man ein Intervall um 0 und Startwerte, die konvergeiren (und dann halt automatisch gegen 0, wobei es darauf nicht ankommt und man letztendlich nur die Konvergenz des Intervalls zeigen muss?)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:53 Do 16.12.2010 | | Autor: | dennis2 |
Ich würde mich freuen, wenn jemand einen Blick darüber wirft.
Zu (a) habe ich jetzt Folgendes:
Anwenden des Banachschen Fixpunktsatzes:
Betrachte I=[1.5,2.5] mit [mm] x_0=2\in [/mm] I.
I ist abgeschlossen und [mm] \phi:I\to R^n [/mm] ist kontrahierend in I, d.h. [mm] \phi(I)\subseteq [/mm] I, denn:
I ist konvex, d.h. für alle [mm] a\in [/mm] [0,1] gilt:
[mm] ax+(1-a)*y\in [/mm] I für alle [mm] x,y\in [/mm] I
und [mm] |\phi'(x)|<1 [/mm] für alle [mm] x\in [/mm] I, denn [mm] |\phi'(2.5)|=0.568055<1 [/mm] und da [mm] \phi'(x) [/mm] in I monoton fallend ist, gilt das für das ganze Intervall I.
Außerdem ist [mm] \phi [/mm] diff.bar, denn [mm] \phi(x)=x-\bruch{x^3-2x}{3x^2-2} [/mm] ist diff.bar, da x diff.bar und der Bruch diff.bar.
Also gilt der Banachsche Fixpunktsatz und die Folge [mm] x_{k+1}=\phi(x_k), [/mm] k=0,1,... konvergiert für alle [mm] x_0\in [/mm] I, also auch für [mm] x_0=2 [/mm] gegen den eindeutig bestimmten Fixpunkt [mm] \overline{x} [/mm] in I.
Zu (b)
Da habe ich jetzt einfach geguckt, für welche x-Werte um den Punkt 0 gilt [mm] |\phi'(x)|<1 [/mm] und das ist m.E. der Fall für das Intervall [mm] I\approx [/mm] [-0.43,0.43]
Auch alle anderen Voraussetzungen des Banachschen Fixpunktsatzes (Differenzierbarkeit, Kontraktion) gelten für dieses Intervall.
D.h. für alle Startwerte aus dem Intervall konvergiert das Newton-Verfahren wieder gegen den eindeutigen Fixpunkt in diesem Intervall; dieser ist natürlich 0, da 0 offensichtlich Nullstelle der Funktion f ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:58 Do 16.12.2010 | | Autor: | max3000 |
> Ich würde mich freuen, wenn jemand einen Blick darüber
> wirft.
>
> Zu (a) habe ich jetzt Folgendes:
>
> Anwenden des Banachschen Fixpunktsatzes:
>
> Betrachte I=[1.5,2.5] mit [mm]x_0=2\in[/mm] I.
> I ist abgeschlossen und [mm]\phi:I\to R^n[/mm] ist kontrahierend in
> I, d.h. [mm]\phi(I)\subseteq[/mm] I, denn:
Definiere das lieber als [mm] $\phi:I\rightarrow [/mm] I$. Der BFPS will das halt so :)
> I ist konvex, d.h. für alle [mm]a\in[/mm] [0,1] gilt:
> [mm]ax+(1-a)*y\in[/mm] I für alle [mm]x,y\in[/mm] I
Die Aussage ist sinnlos. Wir reden hier über ein Intervall. Da brauchst du nicht zeigen dass das eine konvexe Menge ist.
> und [mm]|\phi'(x)|<1[/mm] für alle [mm]x\in[/mm] I, denn
> [mm]|\phi'(2.5)|=0.568055<1[/mm] und da [mm]\phi'(x)[/mm] in I monoton
> fallend ist, gilt das für das ganze Intervall I.
Das reicht als Argument nicht. Was ist, wenn [mm] \phi(x)<-1 [/mm] wird? Das solltest du noch sauberer untersuchen.
> Außerdem ist [mm]\phi[/mm] diff.bar, denn
> [mm]\phi(x)=x-\bruch{x^3-2x}{3x^2-2}[/mm] ist diff.bar, da x
> diff.bar und der Bruch diff.bar.
>
> Also gilt der Banachsche Fixpunktsatz und die Folge
> [mm]x_{k+1}=\phi(x_k),[/mm] k=0,1,... konvergiert für alle [mm]x_0\in[/mm]
> I, also auch für [mm]x_0=2[/mm] gegen den eindeutig bestimmten
> Fixpunkt [mm]\overline{x}[/mm] in I.
>
Also das ist zwar, denke ich, richtig, aber mir gefällt dieser Beweis nicht wirklich. Ich bin immer noch der Meinung dass es einfachere Sätze gibt, mit denen man das nachweisen kann und ich bin mir ziemlich sicher, dass ihr auch so einen in der Vorlesung hattet.
> Zu (b)
>
> Da habe ich jetzt einfach geguckt, für welche x-Werte um
> den Punkt 0 gilt [mm]|\phi'(x)|<1[/mm] und das ist m.E. der Fall
> für das Intervall [mm]I\approx[/mm] [-0.43,0.43]
Plotte dir einfach mal die Kurve [mm] \Phi' [/mm] und beantworte dir selbst, ob das richtig gerechnet ist oder nicht.
> Auch alle anderen Voraussetzungen des Banachschen
> Fixpunktsatzes (Differenzierbarkeit, Kontraktion) gelten
> für dieses Intervall.
Differenzierbarkeit ist keine Vorraussetzung des BFPS. Das kannst du auch in Teil a wieder rausstreichen.
> D.h. für alle Startwerte aus dem Intervall konvergiert das
> Newton-Verfahren wieder gegen den eindeutigen Fixpunkt in
> diesem Intervall; dieser ist natürlich 0, da 0
> offensichtlich Nullstelle der Funktion f ist.
>
Ist auch richtig, allerdings mit dem selben "aber", wie bei Aufgabe (a).
Grüße
Max
|
|
|
| |
|
> Und dann habe ich geguckt, wann f(x) die Werte 1 bzw. -1
> annimt und das ist für ca. 0.61 bzw. 0.62 der Fall.
> Und http://www.arndt-bruenner.de/mathe/java/newton.htm
> verrät mir, dass die Werte wohl ganz gut hinkommen und das
> Intervall demnach so in etwa [-0.63,0.63] sein muss, damit
> das Verfahren für Startwerte aus diesem Intervall gegen 0
> konvergiert.
Hallo Dennis und die übrigen Interessierten:
letzteres Intervall kommt schon ganz gut hin.
Nach meinen in meinem anderen Artikel angegebenen
Überlegungen findet man als größtmögliches zusam-
menhängendes Intervall:
$\ I\ =\ [mm] \left(\,-\sqrt{0.4}\ ..... +\sqrt{0.4}\,\right)\ \approx\ (\,-0.63246\ [/mm] ..... [mm] +0.63246\,)$
[/mm]
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 06:27 Fr 17.12.2010 | | Autor: | dennis2 |
> Hallo Dennis und die übrigen Interessierten:
> letzteres Intervall kommt schon ganz gut hin.
> Nach meinen in meinem
> anderen Artikel
> angegebenen
> Überlegungen findet man als größtmögliches zusam-
> menhängendes Intervall:
>
> [mm]\ I\ =\ \left(\,-\sqrt{0.4}\ ..... +\sqrt{0.4}\,\right)\ \approx\ (\,-0.63246\ ..... +0.63246\,)[/mm]
>
>
> LG Al-Chw.
Ich habe das leider nichtt ganz verstanden, wie Du auf dieses Ergebnis gekommen bist. Kannst Du es nochmal erklären?
|
|
|
| |
|
> > Hallo Dennis und die übrigen Interessierten:
> > letzteres Intervall kommt schon ganz gut hin.
> > Nach meinen in meinem
> > anderen Artikel
> > angegebenen
> > Überlegungen findet man als größtmögliches zusam-
> > menhängendes Intervall:
> >
> > [mm]\ I\ =\ \left(\,-\sqrt{0.4}\ ..... +\sqrt{0.4}\,\right)\ \approx\ (\,-0.63246\ ..... +0.63246\,)[/mm]
>
> >
> >
> > LG Al-Chw.
>
> Ich habe das leider nichtt ganz verstanden, wie Du auf
> dieses Ergebnis gekommen bist. Kannst Du es nochmal
> erklären?
Hi Dennis,
ich habe mir (mehr oder weniger anschaulich) klar gemacht,
dass der rechte Randpunkt des gesuchten Intervalls die Stelle
[mm] x_0 [/mm] mit [mm] x_0>0 [/mm] und [mm] x_1=-x_0 [/mm] sein muss. Dabei ist [mm] x_1 [/mm] der Wert, den
das Newtonverfahren ausgehend von [mm] x_0 [/mm] als nächsten Näherungswert
liefert, also
$\ [mm] x_1\ [/mm] =\ [mm] x_0-\frac{f(x_0)}{f'(x_0)}$
[/mm]
Setzen wir der Einfachheit halber einfach $x$ statt [mm] x_0 [/mm] , so erhalten
wir mit der vorliegenden Funktion $\ f(x)\ =\ [mm] x^3-2\,x$ [/mm] für dieses $x$ die
Gleichung:
$\ -x\ =\ [mm] x-\frac{x^3-2\,x}{3\,x^2-2}$
[/mm]
Nimmt man als Startwert gerade eine der beiden Lösungen
dieser Gleichung, so pendelt das Newtonverfahren zwischen
diesen beiden Werten hin und her und konvergiert also nicht.
Liegt aber der Startwert nur geringfügig näher bei Null, so
kann man zeigen, dass das Newtonverfahren zum Grenzwert
Null konvergieren muss.
LG Al-Chwarizmi
|
|
|
| |
|
> Das Konvergenzverhalten des Newton-Verfahrens soll am
> Beispiel der Nullstellenbestimmung der Funktion
>
> [mm]f(x)=x^3-2x, x\in[/mm] [-2,2]
>
> untersucht werden.
>
> (a) Konvergiert das Newton-Verfahren mit dem Startwert
> [mm]x_0=2?[/mm]
>
> (b) Bestimmen Sie ein (möglichst großes) Intervall I,
> sodass für alle Startwerte [mm]x_0 \in[/mm] I das Newton-Verfahren
> gegen 0 konvergiert.
> Zu (a):
> Genügt es hier, wenn man einfach zeigt bzw. ausrechnet,
> dass das Verfahren gegen einen Wert (eine Nullstelle)
> konvergiert? Wenn ich richtig gerechnet habe, dann bekommt
> man nämlich schon nach 4 Schritten, dass das Verfahren
> gegen [mm]\wurzel{2}[/mm] konvergiert, was tatsächlich eine der
> Nullstellen ist.
>
> (b) Braucht man hier, dass das Newtonverfahren auch eine
> Fixpunktiteration ist?
Hallo Dennis,
ich habe die anderen Beiträge nicht vollständig durchgelesen
und bitte um Entschuldigung, falls ich dort gegebene Hinweise
allenfalls nicht beachtet habe.
Bei (a) könnte man wohl zeigen, dass vom Startwert [mm] x_0=2 [/mm]
ausgehend eine monoton fallende und beschränkte Folge
[mm]
konvergent sein muss.
Für die Bestimmung des größtmöglichen Intervalls für (b)
würde ich mir ein paar geometrische Überlegungen zum
Konvergenzverhalten des Newtonverfahrens machen.
Erstens: wegen der O-Symmetrie des Funktionsgraphen
von [mm] y=x^3-2\,x [/mm] muss auch das gesuchte Intervall symmetrisch
bezüglich x=0 sein.
Im Folgenden kann man sich deshalb auf die Betrachtung
positiver Startwerte beschränken.
Zweitens: für alle [mm] x_0 [/mm] mit [mm] x_0\ge\sqrt{2} [/mm] und folglich auch für
alle [mm] x_0 [/mm] mit [mm] x_0>x_T [/mm] (T=Tiefpunkt des Graphen) konver-
giert das Verfahren gegen [mm] \sqrt{2} [/mm] . Dies ist geometrisch
leicht einzusehen.
Drittens: um den größtmöglichen zusammenhängenden
Attraktionsbereich des Zielpunktes z=0 zu bestimmen,
prüfe man dann, für welche [mm] x_0\in\IR [/mm] die Tangente des
Graphen in $\ [mm] P_0(x_0\ [/mm] |\ [mm] f(x_0)\,)$ [/mm] die x-Achse an einer
Stelle [mm] x_1 [/mm] mit $\ [mm] |x_1|\ [/mm] <\ [mm] |x_0|$ [/mm] schneidet. Aufgrund
der geometrischen Eigenschaften des Graphen kann man
schließen (und falls gewünscht auch exakt nachweisen), dass
für alle solchen [mm] x_0 [/mm] die Konvergenz gegen z=0 folgt.
Zu zeigen bliebe dann noch, dass man damit auch das
größte zusammenhängende Intervall mit den verlangten
Eigenschaften hat. Dies ergibt sich aber leicht aus der
Betrachtung für den Fall der Randpunkte jenes Intervalls,
nämlich für jene beiden Werte [mm] x_0 [/mm] , für welche [mm] x_1=-x_0 [/mm] ist.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:22 Fr 17.12.2010 | | Autor: | dennis2 |
Ein großes Danke an alle, die mir bei dieser Frage geholfen haben!
Es war sehr umständlich...
|
|
|
|
