matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenFolgen und ReihenNewton Verfahren
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Folgen und Reihen" - Newton Verfahren
Newton Verfahren < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Newton Verfahren: Idee
Status: (Frage) beantwortet Status 
Datum: 09:15 Fr 10.07.2009
Autor: Uebungistalles

Aufgabe
a)f(x) = [mm] x^{3} [/mm] - x    Produziert das Newton Verfahren in diesem Fall eine divergente Folge?

b) Nun nimmt man an das Verfahren produziert eine unendliche Folge , etwa  [mm] (x_{n})_{n}\in\IN [/mm] insbesondere ist [mm] f(x_{n}) \not= [/mm] 0.
Man nehme an die Folge konvergiert und lim [mm] x_{n} [/mm] =  [mm] x_{0} \in \IR [/mm]

Guten Morgen :)

Jetzt ist die Frage wie ich das zeige - habe für a nur gelesen das man den Startwert recht "nah" an der eigentlichen Nullstellen wählen muss , da sonst Divergenz oder ähnliches auftreten kann.

        
Bezug
Newton Verfahren: Antwort
Status: (Antwort) fertig Status 
Datum: 11:45 Fr 10.07.2009
Autor: leduart

Hallo
Welche der 3 Nst. willst du denn finden? Die Aufgabe kann doch nicht genau so gestellt sein.
Warum probierst dus nicht aus?
Eine Skizze der fkt sagt dir auch viel.
Gruss leduart

Bezug
        
Bezug
Newton Verfahren: Antwort
Status: (Antwort) fertig Status 
Datum: 12:29 Fr 10.07.2009
Autor: Al-Chwarizmi


>   [mm] f(x)=x^{3}-x [/mm]    

> Produziert das Newton Verfahren in
> diesem Fall eine divergente Folge?

Ich fasse die Frage so auf:

"Gibt es Startwerte [mm] x_0, [/mm] für welche eine zwar
unendliche, aber nicht konvergente Folge entsteht ?"


Hallo,

zunächst ist ja mal klar, dass man zur Berechnung
der Nullstellen dieser Funktion das Newtonverfahren
nicht braucht - man erschlägt ja Mücken auch nicht
mit dem Hammer.
Anhand einer Zeichnung kann man sich leicht klar
machen: Wenn der Startwert [mm] x_0 [/mm] grösser als 1 ist,
konvergiert die Folge der [mm] x_n [/mm] gegen 1. Analoges
gilt für [mm] x_0<-1. [/mm] Dann ist [mm] \limes_{n\to\infty}x_n=-1 [/mm] .
Wegen der Symmetrie weitere Überlegungen nur
für positive Startwerte:
Liegt [mm] x_0 [/mm] rechts vom Tiefpunkt, also [mm] x_0>\bruch{1}{\sqrt{3}}, [/mm]
so ist [mm] x_1>1 [/mm] und [mm] \limes_{n\to\infty}x_n=1. [/mm]
Für $\ [mm] x_0=\bruch{1}{\sqrt{3}}$ [/mm] ist schon [mm] x_1 [/mm] nicht definiert.
Legt man vom Punkt [mm] (\bruch{1}{\sqrt{3}}/0) [/mm] auf der x-Achse aus
die Tangente an die Kurve und nimmt die x-Koordinate
[mm] x_B [/mm] des Berührungspunktes als Startwert, so geht das
Verfahren beim zweiten Schritt ins Leere. Legt man
von [mm] (x_B/0) [/mm] wieder die Tangente an die Kurve,
kommt man zu einer Stelle, von der aus das
Verfahren beim dritten Schritt nicht mehr weiter
geht, etc.
Es kann also Folgen geben, die nicht konvergent
sind, sondern mit einem "Sprung ins Unendliche"
abbrechen.
Gibt es auch periodische und somit unendliche,
aber nicht konvergente Folgen ? Ja, und zwar wohl
solche mit beliebiger Periodenlänge. Diejenigen mit
Periode zwei findet man folgendermaßen: Löse
die Gleichung [mm] x_2=x_0 [/mm] mittels der Rekursionsformel
auf. Die Lösungen [mm] \xi_k [/mm] dieser Gleichung mit nicht ver-
schwindenden Funktionswerten [mm] f(\xi_k) [/mm] sind die
Startwerte für die möglichen Folgen mit Periode 2.
Für eine Folge mit Periode 3 löse man die Gleichung
[mm] x_3=x_0 [/mm] auf, etc.

Wegen der Symmetrie des Graphen erhält man
Startwerte für eine Folge der Periode 2 auch aus
der Gleichung [mm] x_1=-x_0 [/mm] .

Es gibt jedoch keinen Startwert [mm] x_0 [/mm] , aus
welchem eine bestimmt divergente Folge
resultiert, also etwa mit [mm] \limes_{n\to\infty}x_n=\infty [/mm] .


LG    Al-Chwarizmi    


Bezug
                
Bezug
Newton Verfahren: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:37 Fr 10.07.2009
Autor: Al-Chwarizmi


> >   $\ f(x)\ =\ [mm] x^{3}-x$ [/mm]

> >   $\ [mm] x_{n+1}\ [/mm] =\ [mm] x_n\,-\,\bruch{f(x_n)}{f'(x_n)}$ [/mm]    


Und gleich noch zwei Fragen dazu:

a)  Gibt es auch Startwerte, für welche eine
    nicht abbrechende, nicht konvergente und
    nicht periodische Zahlenfolge entsteht ?

b)  Konkretes Beispiel eines solchen Startwerts ?


LG     Al


Bezug
                        
Bezug
Newton Verfahren: Antwort
Status: (Antwort) fertig Status 
Datum: 05:11 Do 16.07.2009
Autor: felixf

Hallo zusammen

>   [mm]\ f(x)\ =\ x^{3}-x[/mm]
>  
>   [mm]\ x_{n+1}\ =\ x_n\,-\,\bruch{f(x_n)}{f'(x_n)}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

    

Definiere $g(x) := \frac{2 x^3}{3 x^2 - 1} = x - \frac{f(x)}{f'(x)}$ fuer $x \neq \pm \frac{1}{\sqrt{3}}$.

Dann gilt $x_{n+1} = g(x_n)$.

Wie bereits gezeigt hat $g$ die Fixpunkte -1, 0, 1, und fuer $x > 1$ bzw. $x < -1$ konvergiert die entstehende Folge gegen 1 bzw. -1.

Man kann nun folgendes zeigen:

Behauptung 1: Gilt $x \in (\frac{1}{\sqrt{3}}, 1)$, so gilt $g(x) > 1$. Gilt $x \in (-1, -\frac{1}{\sqrt{3}})$, so gilt $g(x) < -1$.
Behauptung 2: Fuer $x \in (0, 1/\sqrt{5}) \cup (-1/\sqrt{5}, 0)$ gilt $|g(x)| < |x|$.
Behauptung 3: Fuer $x \in \{ 1/\sqrt{5}, -1/\sqrt{5} \}$ gilt $g(x) = -x$.
Behauptung 4: Fuer $x \in (1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})$ gilt $|g(x)| > |x|$.


Nun noch eine Hilfsbehauptung:


Lemma: Sei $[a, b)$ ein Intervall und $f : [a, b) \to [a, b)$ stetig mit $f(x) > x$ fuer alle $x \in [a, b)$. Ist $x_0 \in [a, b)$ beliebig und $x_{n+1} := f(x_n)$, so gilt $\lim_{n\to\infty} x_n = b$.

Beweis: Die Folge $(x_n)_{n\in\IN}$ ist streng monoton steigend und nach oben hin durch $b$ beschraenkt, womit sie konvergiert. Sei $x_\infty$ der Grenzwert. Gilt $x_\infty < b$, so ist $x_\infty = \lim_{n\to\infty} x_n = \lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} f(x_n) = f(\lim_{n\to\infty} x_n) = f(x_\infty) > x_\infty$, ein Widerspruch. Also muss $x_\infty = b$ sein.


Daraus folgt: Liegt der Startwert in $(-\frac{1}{\sqrt{5}}, \frac{1}{\sqrt{5}})$, so konvergiert die Folge gegen 0.

Bleibt also $X := (1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})$. Dort gilt $|g(x)| > |x|$, im Absolutbetrag konvergiert die Folge also gegen 1. Tatsaechlich divergiert die Folge jedoch; wenn man jedes zweite Folgenglied nimmt, so erhaelt man eine Folge die gegen 1 oder -1 konvergiert.

> Und gleich noch zwei Fragen dazu:
>  
> a)  Gibt es auch Startwerte, für welche eine
> nicht abbrechende, nicht konvergente und
> nicht periodische Zahlenfolge entsteht ?

Ja: da die periodischen Startwerte durch abzaehlbar viele endliche Mengen beschrieben werden koennen (Teilmenge der Nullstellenmenge von $g(g(g(\cdots(g(x))\cdots))) = x$), ist die Menge dieser Startwerte abzaehlbar.

Da $(1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})$ ueberabzaehlbar viele Elemente enthaelt, muss es also (ueberabzaehlbar viele) Startwerte geben, fuer die die Folge weder periodisch ist noch konvergiert und auch nicht abbricht.

Wenn man etwas genauer hinschaut, sagen die obigen Ergebnisse sogar: es gibt genau zwei Startwerte, fuer die die Folge periodisch wird, naemlich $\frac{1}{\sqrt{5}}$ und $-\frac{1}{\sqrt{5}}$ -- fuer alle anderen Werte im fraglichen Intervall gilt $|g(x)| > |x|$, womit die Folge niemals periodisch werden kann.

Man kann also jedes Element in $(1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})$ als moeglichen Startwert benutzen, u.a. auch $\pm \frac{1}{\sqrt{4}$.

LG Felix


Bezug
                                
Bezug
Newton Verfahren: fraktale Struktur
Status: (Frage) überfällig Status 
Datum: 09:35 Do 16.07.2009
Autor: Al-Chwarizmi


> Hallo zusammen
>  
> >   [mm]\ f(x)\ =\ x^{3}-x[/mm]

  

> >   [mm]\ x_{n+1}\ =\ x_n\,-\,\bruch{f(x_n)}{f'(x_n)}[/mm]    

>
> Definiere [mm]g(x) := \frac{2 x^3}{3 x^2 - 1} = x - \frac{f(x)}{f'(x)}[/mm]
> fuer [mm]x \neq \pm \frac{1}{\sqrt{3}}[/mm].
>  
> Dann gilt [mm]x_{n+1} = g(x_n)[/mm].
>  
> Wie bereits gezeigt hat [mm]g[/mm] die Fixpunkte -1, 0, 1, und fuer
> [mm]x > 1[/mm] bzw. [mm]x < -1[/mm] konvergiert die entstehende Folge gegen 1
> bzw. -1.
>  
> Man kann nun folgendes zeigen:
>  
> Behauptung 1: Gilt [mm]x \in (\frac{1}{\sqrt{3}}, 1)[/mm], so gilt [mm]g(x) > 1[/mm].
>               Gilt [mm]x \in (-1, -\frac{1}{\sqrt{3}})[/mm], so gilt [mm]g(x) < -1[/mm].

> Behauptung 2: Fuer [mm]x \in (0, 1/\sqrt{5}) \cup (-1/\sqrt{5}, 0)[/mm] gilt [mm]|g(x)| < |x|[/mm].

> Behauptung 3: Fuer [mm]x \in \{ 1/\sqrt{5}, -1/\sqrt{5} \}[/mm] gilt [mm]g(x) = -x[/mm].

> Behauptung 4: Fuer [mm]x \in (1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})[/mm] gilt [mm]|g(x)| > |x|[/mm].
>  
>
> Nun noch eine Hilfsbehauptung:
>  
>
> Lemma: Sei [mm][a, b)[/mm] ein Intervall und [mm]f : [a, b) \to [a, b)[/mm]
> stetig mit [mm]f(x) > x[/mm] fuer alle [mm]x \in [a, b)[/mm]. Ist [mm]x_0 \in [a, b)[/mm]
> beliebig und [mm]x_{n+1} := f(x_n)[/mm], so gilt [mm]\lim_{n\to\infty} x_n = b[/mm].
>  
> Beweis: Die Folge [mm](x_n)_{n\in\IN}[/mm] ist streng monoton
> steigend und nach oben hin durch [mm]b[/mm] beschraenkt, womit sie
> konvergiert. Sei [mm]x_\infty[/mm] der Grenzwert. Gilt [mm]x_\infty < b[/mm],
> so ist [mm]x_\infty = \lim_{n\to\infty} x_n = \lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} f(x_n) = f(\lim_{n\to\infty} x_n) = f(x_\infty) > x_\infty[/mm],
> ein Widerspruch. Also muss [mm]x_\infty = b[/mm] sein.
>  
>
> Daraus folgt: Liegt der Startwert in [mm](-\frac{1}{\sqrt{5}}, \frac{1}{\sqrt{5}})[/mm],
> so konvergiert die Folge gegen 0.

Klar. So hat also jeder der drei Attraktionspunkte [mm] a_i [/mm]
vorerst einmal ein großes zusammenhängendes
Intervall [mm] I_0(a_i) [/mm] mit der Eigenschaft, dass jeder Start-
wert aus dem betreffenden Intervall eine Folge liefert,
die gegen den Attraktor konvergiert:

    Für a=0 ist [mm] I_0(a)=I_0(0)=(-\frac{1}{\sqrt{5}}, \frac{1}{\sqrt{5}}) [/mm]
    Für a=1 ist [mm] I_0(a)=I_0(1)=(\frac{1}{\sqrt{3}}, \infty) [/mm]
    Für a=-1 ist [mm] I_0(a)=I_0(-1)=(-\infty,-\frac{1}{\sqrt{3}}) [/mm]

  

> Bleibt also [mm]X := (1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})[/mm].
> Dort gilt [mm]|g(x)| > |x|[/mm],    [ok]

> im Absolutbetrag konvergiert die
> Folge also gegen 1.    [verwirrt]

Das Intervall [mm] (1/\sqrt{5}, 1/\sqrt{3}) [/mm] enthält ein Subintervall
mit der Eigenschaft, dass der Start aus einem
beliebigen seiner Punkte schon im ersten Schritt ins
Intervall [mm] I_0(-1) [/mm] und deshalb zu einer Folge mit
dem Grenzwert -1 führt.
Und es wird klar, dass dieser Prozess sich wiederholt
und der Menge [mm] \IR [/mm] eine fraktale Struktur aufprägt.

> Tatsaechlich divergiert die Folge
> jedoch; wenn man jedes zweite Folgenglied nimmt, so erhaelt
> man eine Folge die gegen 1 oder -1 konvergiert.

Das verstehe ich jetzt nicht.
  

> > Und gleich noch zwei Fragen dazu:
> >  

> > a)  Gibt es auch Startwerte, für welche eine
> > nicht abbrechende, nicht konvergente und
> > nicht periodische Zahlenfolge entsteht ?
>  
> Ja: da die periodischen Startwerte durch abzaehlbar viele
> endliche Mengen beschrieben werden koennen (Teilmenge der
> Nullstellenmenge von [mm]g(g(g(\cdots(g(x))\cdots))) = x[/mm]), ist
> die Menge dieser Startwerte abzaehlbar.
>  
> Da [mm](1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})[/mm]
> ueberabzaehlbar viele Elemente enthaelt, muss es also
> (ueberabzaehlbar viele) Startwerte geben, fuer die die
> Folge weder periodisch ist noch konvergiert und auch nicht
> abbricht.

Da für viele (nämlich überabzählbar viele) Startwerte
in der Menge X die entsprechenden Folgen schon
nach einem oder nach mehreren Schritten in
eines der drei Attraktionsgebiete abdriften, bleibt
die Frage nach der Mächtigkeit der Menge der
nichtperiodischen, nichtabbrechenden, nichtkon-
vergenten Folgen wohl doch wieder offen ...
  

> Wenn man etwas genauer hinschaut, sagen die obigen
> Ergebnisse sogar: es gibt genau zwei Startwerte, fuer die
> die Folge periodisch wird, naemlich [mm]\frac{1}{\sqrt{5}}[/mm] und
> [mm]-\frac{1}{\sqrt{5}}[/mm] -- fuer alle anderen Werte im
> fraglichen Intervall gilt [mm]|g(x)| > |x|[/mm], womit die Folge
> niemals periodisch werden kann.
>  
> Man kann also jedes Element in [mm](1/\sqrt{5}, 1/\sqrt{3}) \cup (-1/\sqrt{3}, -1/\sqrt{5})[/mm]
> als moeglichen Startwert benutzen, u.a. auch [mm]\pm \frac{1}{\sqrt{4}[/mm].

Mit anderen Worten wäre dies [mm] x_0=\bruch{1}{2} [/mm] .
Dann wird [mm] x_1=g(x_0)=-1 [/mm] , und wir sind in einem
einzigen Schritt zum Grenzwert gekommen ...

> LG Felix

>

Vielleicht müsste man zu diesem Thema wieder
einmal Benoît Mandelbrot konsultieren ...  

Gruß    Al-Chwarizmi

Bezug
                                        
Bezug
Newton Verfahren: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:20 Sa 18.07.2009
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]