Newtonverfahren - Konvergenz < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
| |
|
Hallo Bastiane,
Das Newtonverfahren ist ja ein Fixpunktverfahren.
Also [mm] T(x)=x-\bruch{f(x)}{f'(x)}
[/mm]
Um die Voraussetzungen des Banachschen Fixpunktsatzes zu erfüllen muß das Ganze eine Kontraktion sein. (|T'(x)|<1) und außerdem von [mm] (0,\infty) [/mm] nach [mm] (0,\infty) [/mm] abbilden. Also mit x>0 muß auch T(x) größer 0 sein.
O.K. erstmal?
viele Grüße
mathemaduenn
P.S.: Übrigens hat Karthagoras das Verfahren schonmal ![[a]](/images/paperclip.gif "Dateianhänge") implementiert
Edit: das funktioniert glaub ich doch nicht. Man kann sich aber wohl überlegen das [mm] x_{n+1}=T(x_n) [/mm] eine monoton fallende nach unten beschränkte Folge ist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:49 So 25.06.2006 | | Autor: | Bastiane |
Hallo mathemaduenn!
Danke für deine Antwort, aber ich habe noch ein paar Fragen dazu:
> Das Newtonverfahren ist ja ein Fixpunktverfahren.
Aber auch wenn die Voraussetzungen des Banachschen Fixpunktsatzes nicht erfüllt sind, kann das Verfahren konvergieren, oder ist das eine "genau dann wenn"-Aussage?
> Also [mm]T(x)=x-\bruch{f(x)}{f'(x)}[/mm]
> Um die Voraussetzungen des Banachschen Fixpunktsatzes zu
> erfüllen muß das Ganze eine Kontraktion sein. (|T'(x)|<1)
Muss es nicht eine Konstante K<1 geben, so dass |T'(x)|<K?
> und außerdem von [mm](0,\infty)[/mm] nach [mm](0,\infty)[/mm] abbilden. Also
> mit x>0 muß auch T(x) größer 0 sein.
Das ist aber nicht genau dasselbe, wie von [mm] (0,\infty) [/mm] nach [mm] (0,\infty) [/mm] oder? Wenn für x>0 auch T(x)>0 ist, könnte es ja sein, dass die Abbildung nur von [a,b] nach [A,B] mit a und A [mm] \not=0 [/mm] oder so abbildet, oder? Außerdem stimmt das hier doch nicht mal, oder?
> O.K. erstmal?
Und was sagt mir dann der Fixpunktsatz? Dass es einen eindeutigen Fixpunkt gibt, oder? Und dann weiß ich direkt, dass das Verfahren für alle [mm] x_0>0 [/mm] konvergiert?
Und noch eine Frage: damit wäre dann gezeigt, dass es global konvergiert oder wie?
> viele Grüße
> mathemaduenn
> P.S.: Übrigens hat Karthagoras das Verfahren schonmal
> implementiert
> Edit: das funktioniert glaub ich doch nicht. Man kann sich
> aber wohl überlegen das [mm]x_{n+1}=T(x_n)[/mm] eine monoton
> fallende nach unten beschränkte Folge ist.
Ääh - das lese ich jetzt erst: was davon funktioniert doch nicht???
Jedenfalls soll das, was du hier sagst, in Teil b) gezeigt werden.
Ich hatte da jetzt schon mal angefangen, es so zu machen, wie du gesagt hast. Bisher habe ich raus:
[mm] T'(x)=\bruch{(n-1)(1-ax^{-n})}{n}
[/mm]
Und wenn das <1 sein soll, dann habe ich umgeformt bis:
[mm] ax^{-n}(-n+1)<1
[/mm]
und dann weiß ich nicht mehr weiter.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:33 So 25.06.2006 | | Autor: | ardik |
Seiteneinwurf eines Uni-mathematischen Dilettanten:
> [mm]ax^{-n}(-n+1)<1[/mm]
>
> und dann weiß ich nicht mehr weiter.
Das ist zwar für $a, x > 0$ und $n [mm] \in \IN$ [/mm] immer negativ (bzw. null für n=1), aber der Betrag davon ist bei genügend großem a jedenfalls nicht für alle $x > 0$ kleiner als 1.
schöne Grüße,
ardik
|
|
|
| |
|
Hallo Bastiane,
> Aber auch wenn die Voraussetzungen des Banachschen
> Fixpunktsatzes nicht erfüllt sind, kann das Verfahren
> konvergieren, oder ist das eine "genau dann wenn"-Aussage?
Ja, es ist keine genau dann wenn Aussage.
> > Also [mm]T(x)=x-\bruch{f(x)}{f'(x)}[/mm]
> > Um die Voraussetzungen des Banachschen Fixpunktsatzes
> zu
> > erfüllen muß das Ganze eine Kontraktion sein. (|T'(x)|<1)
>
> Muss es nicht eine Konstante K<1 geben, so dass |T'(x)|<K?
![[ok]](/images/smileys/ok.gif "[ok]")
> > und außerdem von [mm](0,\infty)[/mm] nach [mm](0,\infty)[/mm] abbilden. Also
> > mit x>0 muß auch T(x) größer 0 sein.
>
> Das ist aber nicht genau dasselbe, wie von [mm](0,\infty)[/mm] nach
> [mm](0,\infty)[/mm] oder? Wenn für x>0 auch T(x)>0 ist, könnte es ja
> sein, dass die Abbildung nur von [a,b] nach [A,B] mit a und
> A [mm]\not=0[/mm] oder so abbildet, oder? Außerdem stimmt das hier
> doch nicht mal, oder?
Wieso nicht?
Ein kleineres Inervall könnte es theoretisch nat. immer sein.
> Und was sagt mir dann der Fixpunktsatz? Dass es einen
> eindeutigen Fixpunkt gibt, oder? Und dann weiß ich direkt,
> dass das Verfahren für alle [mm]x_0>0[/mm] konvergiert?
> Und noch eine Frage: damit wäre dann gezeigt, dass es
> global konvergiert oder wie?
Global hieße ja für alle x aber die negativen sind ja bereits ausgeschlossen...
> > viele Grüße
> > mathemaduenn
> > P.S.: Übrigens hat Karthagoras das Verfahren schonmal
> > implementiert
> > Edit: das funktioniert glaub ich doch nicht. Man kann
> sich
> > aber wohl überlegen das [mm]x_{n+1}=T(x_n)[/mm] eine monoton
> > fallende nach unten beschränkte Folge ist.
>
> Ääh - das lese ich jetzt erst: was davon funktioniert doch
> nicht???
> Jedenfalls soll das, was du hier sagst, in Teil b) gezeigt
> werden.
>
> Ich hatte da jetzt schon mal angefangen, es so zu machen,
> wie du gesagt hast. Bisher habe ich raus:
>
> [mm]T'(x)=\bruch{(n-1)(1-ax^{-n})}{n}[/mm]
Diese Abschätzung gibt Konvergenz falls [mm] x>\wurzel[n]{a} [/mm] weil dann [mm] (1-ax^{-n})< [/mm] 1 O.K.?
Soweit ich mich erinnere funktionierte das so:
Ist [mm] x_i>\wurzel[n]{a} [/mm] dann ist auch [mm] x_{i+1}>\wurzel[n]{a} [/mm] daraus folgt dann direkt Konvergenz mit der Abschätzung für T'(x).
Ist [mm] x_0<\wurzel[n]{a} [/mm] so ist [mm] x_1>\wurzel[n]{a} [/mm] damit Konvergenz ab [mm] x_1 [/mm] mittels BFPS
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:02 Mo 26.06.2006 | | Autor: | leduart |
Hallo Bastiane
Ich glaub, das mit dem Fixpunktsatz und der kontrahierenden Abbildung ist hier die falsche Idee, warum sollte das Newtonverfahren auf dem ganzen gebiet kontrahierend sein?
Wenn man gezeigt hat (Zwischenwertsatz) dass eine Nullstelle existiert, kommt eine Fallunterscheidung: Wegen f''>0 für alle x>0 gilt, wenn ich mit x links der Nullstelle starte, ist der nächste wert oberhalb der Nullstelle (die Funktion liegt immer über ihrer Tangente.
Damit kann ich vorraussetzen, dass die iteration mit x>xn losgeht.
jetzt kann man zeigen, dass die iteration eine monoton fallende Folge bildet, die nach unten durch xn nach unten beschränkt ist (dazu brauch ich die Existenz der Nst.) Und damit hab ich die Konvergenz. eingehen tut dabei nur f''>0 und für den 1. Schritt f'>0.
Ich hoff du kannst die Skizze formalisieren
Gruss leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:45 Mo 26.02.2007 | | Autor: | tragor |
Hallo,
man kann die Iterationsvorschrift noch weiter vereinfachen:
[mm]
x-\bruch{x^n-a}{nx^{n-1}}
=\bruch{nxx^{n-1}}{nx^{n-1}}-\bruch{x^n-a}{nx^{n-1}}
=\bruch{nx^n-x^n-a}{nx^{n-1}}=
\bruch{1}{n}((n-1)x+\bruch{a}{x^{n-1}})
[/mm]
Muss auch grad numerik lernen, das kann ganz schön nerven! Viel Erfolg!
tragor
|
|
|
|
![[haee]](/images/smileys/haee.gif "[haee]"){kind=small}
