Konvergenz bei Nullstellenbestimmung mit iterativen Verfahren

23.03.2006, 19:16

555_Nase

Konvergenz bei Nullstellenbestimmung mit iterativen Verfahren

Hallo,
schreibe gerade an meiner Facharbeit zum Thema Nullstellenbestimmung mit iterativen Verfahren, also Intervallhalbierungsverfahren, regula falsi und Newton Verfahren. Was ich allerdings noch nicht verstanden habe sind die Konvergenzkriterien......das scheint ja auch für die Startwerte wichtig zu sein, bzw. die Vorraussetzung für eine korrekte Bestimmung des Startwerts. Ich verstehe nur nicht wie man diese Funktion auf ihre Konvergenz untersucht oder wie auch immer die Beziehung zwischen dem Oberbegriff der Konvergenz und den Verfahren besteht...
Ich wäre um Hilfe sehr dankbar, da ich irgendwie nichts passendes finde was mir hilft....

Schonmal DANKE! Bei Fragen bitte einfach fragen!

24.03.2006, 20:30

Abakus

Auf diesen Beitrag antworten »

RE: Konvergenz bei Nullstellenbestimmung mit iterativen Verfahren
Welche Konvergenzkriterien hast du denn und wo liegt genau der Knackpunkt?

Grüße Abakus smile

24.03.2006, 20:47

mercany

Auf diesen Beitrag antworten »

Meinst du da die Kriterien, damit das Verfahren überhaupt konvergiert oder eher die Fälle, die in Punkto Konvergenz auftreten können - oder beides? smile

Welche Iterationsverfahren beschreibst du denn?

Gruß, mercany

25.03.2006, 16:46

555_Nase

Auf diesen Beitrag antworten »

Also ich such Kriterien mit denen ich bestimmen kann ob ein Punkt zu der Nullstelle konvergiert, meinetwegen auch zu einer bestimmten Nullstelle, falls es so etwas gibt.
Ich habe schon herausgefunden das man nachdem man die Nullstelle berechnet hat den Startpunkt auf seine Konvergenz testen kann. Da gibt es ja irgendwas mit Linearer und quadratrischer Konvergenz.
Eine zusätzliche Frage zum Newton Verfahren:
Ich habe gelesen das man am Anfang ein Intervall suchen muss in dem die Nullstelle ist, andererseits hab ich gelesen das man nur den richtigen Startpunkt braucht (und ich denke das man den mit diesem Konvergenzzeugs bestimmen kann). Was ist denn nun richtig, oder besser, und einfacher?

Aber danke für eure Antworten, ich hoffe ihr könnt mir helfen!
MfG 555_Nase

25.03.2006, 17:18

mercany

Auf diesen Beitrag antworten »

Zitat:

Also ich such Kriterien mit denen ich bestimmen kann ob ein Punkt zu der Nullstelle konvergiert, meinetwegen auch zu einer bestimmten Nullstelle, falls es so etwas gibt.

Keine Ahnung, ob es soetwas gibt. Ich denke, man sieht das halt während der Nährung, indem man das Verfahren benutz.

Es gibt allerdings bestimmte Kriterien, die die Funktion in einem bestimmten Intervall erfüllen sollte, damit die Nährung auch klappt!

Zitat:

Ich habe schon herausgefunden das man nachdem man die Nullstelle berechnet hat den Startpunkt auf seine Konvergenz testen kann. Da gibt es ja irgendwas mit Linearer und quadratrischer Konvergenz.

Soweit ich weiß, konvergiert das Newton-Verfahren mit quadratischer Konvergenz, also vom Typ Konvergenzordnung 2.

Zur Konvergenzordnung ansich:

Lineare Konvergenz liegt vor, falls es ein $\begin{eqnarray*} 0<c<1 \end{eqnarray*}$ gibt, sodass gilt
$\begin{eqnarray*} \|x_{k+1}-x\| \leq c\|x_{k}-x\|, k=0,1,... \end{eqnarray*}$

Konvergenz der Ordnung $\begin{eqnarray*} p \end{eqnarray*}$ mit $\begin{eqnarray*} p>1 \end{eqnarray*}$ bedeutet, dass es ein $\begin{eqnarray*} c>0 \end{eqnarray*}$ gibt, sodass gilt
$\begin{eqnarray*} \|x_{k+1}-x\| \leq c\|x_{k}-x\|^{p}, k=0,1,... \end{eqnarray*}$

Zitat:

Eine zusätzliche Frage zum Newton Verfahren:
Ich habe gelesen das man am Anfang ein Intervall suchen muss in dem die Nullstelle ist, andererseits hab ich gelesen das man nur den richtigen Startpunkt braucht (und ich denke das man den mit diesem Konvergenzzeugs bestimmen kann). Was ist denn nun richtig, oder besser, und einfacher?

"Den richtigen" Startpunkt, finde ich etwas weit hergeholt. Indem du dein Intervall um die Nullstelle möglichst gut eingrenzt, erhälst du ja schon einen eine Stelle, die ziemlich nah an deiner Nullstelle liegt. Je näher das ist, desto schneller konvergiert dein Verfahren auch.

Zur Konvergenz allgemein, können folgende Fälle auftreten.

- die Folge divergiert
- die Folge divergiert, jedoch beschränkt. Sie ist z.B. periodisch - d.h. sie oszilliert.
- die Folge konvergiert, jedoch gegen eine andere Nullstelle

Dazu habe ich irgendwann hier im Forum auchschonmal eine Frage gestellt. Musst du mal suchen...

Gruß, mercany

25.03.2006, 17:37

555_Nase

Auf diesen Beitrag antworten »

Zu den beiden Konvergenzordnungen, die hab ich auch schon öfters gesehen, ich frag mich nur wie man die anwendet, wäre sehr sehr sehr nett wenn du vllt anhand eines beispiels die konvergenzordnungen erklären könntest...

Das mit den Fällen die auftreten können wollte ich auch mit rein bringen, hab auch schon beispiele, ich hoffe nur der platz reicht aus am ende...*g*

MfG 555_Nase

25.03.2006, 17:44

Leopold

Auf diesen Beitrag antworten »

Ein hinreichendes Kriterium beim Newton-Verfahren ist das Folgende.

$\begin{eqnarray*} f \end{eqnarray*}$ sei im Intervall $\begin{eqnarray*} I = [a,b] \end{eqnarray*}$ zweimal differenzierbar und für alle $\begin{eqnarray*} x \in I \end{eqnarray*}$ gelte entweder $\begin{eqnarray*} f''(x)>0 \end{eqnarray*}$ oder $\begin{eqnarray*} f''(x)<0 \end{eqnarray*}$ (der Graph von $\begin{eqnarray*} f \end{eqnarray*}$ ist also über $\begin{eqnarray*} I \end{eqnarray*}$ entweder gänzlich konvex oder gänzlich konkav). Wenn $\begin{eqnarray*} f(a) \end{eqnarray*}$ und $\begin{eqnarray*} f(b) \end{eqnarray*}$ verschiedene Vorzeichen haben, dann besitzt $\begin{eqnarray*} f \end{eqnarray*}$ in $\begin{eqnarray*} I \end{eqnarray*}$ genau eine Nullstelle $\begin{eqnarray*} \xi \end{eqnarray*}$ . Man erhält sie als Limes der durch

$\begin{eqnarray*} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \ \ \mbox{für} \ n \geq 0 \end{eqnarray*}$

rekursiv definierten Folge $\begin{eqnarray*} (x_n)_{n \geq 0} \end{eqnarray*}$ :

$\begin{eqnarray*} \xi = \lim_{n \to \infty} x_n \end{eqnarray*}$

Für den ansonsten beliebigen Startwert $\begin{eqnarray*} x_0 \in I \end{eqnarray*}$ hat man zu verlangen, daß $\begin{eqnarray*} f(x_0) \end{eqnarray*}$ und $\begin{eqnarray*} f''(x_0) \end{eqnarray*}$ dasselbe Vorzeichen besitzen.

Es gibt natürlich Kriterien, die mit weniger Voraussetzungen auskommen. Diese sind oft aber nicht so einfach überprüfbar.

Ein Beispiel:

$\begin{eqnarray*} f(x) = \operatorname{e}^x - \cos{x} \end{eqnarray*}$

Natürlich ist $\begin{eqnarray*} 0 \end{eqnarray*}$ eine Nullstelle von $\begin{eqnarray*} f \end{eqnarray*}$ . Zeichnet man sich die Graphen von $\begin{eqnarray*} x \mapsto \operatorname{e}^x \end{eqnarray*}$ und $\begin{eqnarray*} x \mapsto \cos{x} \end{eqnarray*}$ , so erkennt man, daß $\begin{eqnarray*} f \end{eqnarray*}$ unendlich viele Nullstellen besitzen muß (es sind ja gerade die Abszissen der Schnittpunkte der beiden Graphen), alle in $\begin{eqnarray*} (-\infty,0] \end{eqnarray*}$ . Die am weitesten rechts liegende negative Nullstelle muß in $\begin{eqnarray*} \left( - \frac{\pi}{2} , 0 \right) \end{eqnarray*}$ liegen. Versuchen wir es mit dem Intervall

$\begin{eqnarray*} I = \left[ - \frac{\pi}{2} , - \frac{\pi}{4} \right] \end{eqnarray*}$

1. Überprüfen der Randvorzeichen von $\begin{eqnarray*} f \end{eqnarray*}$ :

$\begin{eqnarray*} f \left(- \frac{\pi}{2} \right) = \operatorname{e}^{- \frac{\pi}{2}} > 0 \end{eqnarray*}$

$\begin{eqnarray*} f \left(- \frac{\pi}{4} \right) = \operatorname{e}^{- \frac{\pi}{4}} - \sqrt{\frac{1}{2}} < 0 \end{eqnarray*}$

Das ist offensichtlich aufgrund des Verlaufs der Graphen der Exponentialfunktion und der Cosinusfunktion.

2. Überprüfen der Vorzeichenbedingung für $\begin{eqnarray*} f'' \end{eqnarray*}$ :

$\begin{eqnarray*} f''(x) = \operatorname{e}^x + \cos{x} > 0 \ \ \mbox{für alle} \ x \in I \end{eqnarray*}$

Auch das ist offensichtlich, denn der erste Summand ist stets positiv und die Cosinusfunktion ist in $\begin{eqnarray*} I \end{eqnarray*}$ nicht negativ.

3. Einen Startwert festlegen:

Wegen 2. haben wir für den Startwert $\begin{eqnarray*} f(x_0) > 0 \end{eqnarray*}$ zu verlangen. Man kann daher $\begin{eqnarray*} x_0 = - \frac{\pi}{2} \end{eqnarray*}$ selbst nehmen.

Nach dem Satz muß bei dieser Wahl des Startwertes das Verfahren gegen die gesuchte erste negative Nullstelle von $\begin{eqnarray*} f \end{eqnarray*}$ konvergieren.

25.03.2006, 18:07

555_Nase

Auf diesen Beitrag antworten »

Also da bin ich begeistert, eine perfekte Erklärung!
Besten Dank!

Zitat:

Für den ansonsten beliebigen Startwert x_0 \in I hat man zu verlangen, daß f(x_0) und f''(x_0) dasselbe Vorzeichen besitzen.

Das ist dann die Notwendige Bedingung oder?

25.03.2006, 18:12

Mathespezialschüler

Auf diesen Beitrag antworten »

Nein, es ist eine hinreichende, keine notwendige!

@Leopold
Hast du $\begin{eqnarray*} f'\neq 0 \end{eqnarray*}$ absichtlich nur vergessen oder einfach als selbstverständlich schon vorausgesetzt?

Gruß MSS

25.03.2006, 18:27

555_Nase

Auf diesen Beitrag antworten »

Kann mir vielleicht jemand von euch Spezialisten eine Quellenangabe in Form eines Links geben? Ich finde nämlich nichts, wäre herrlich!
MfG 555_Nase

25.03.2006, 18:45

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Mathespezialschüler
Hast du $\begin{eqnarray*} f'\neq 0 \end{eqnarray*}$ absichtlich nur vergessen oder einfach als selbstverständlich schon vorausgesetzt?

Diese Bedingung ist, wie ich glaube, nicht erforderlich. Wenn man sich eine Skizze zeichnet, leuchtet das auch ein. Aufgrund der Forderung an $\begin{eqnarray*} f''(x) \end{eqnarray*}$ ist der Graph ja überall konvex bzw. überall konkav. Wenn da noch ein Hoch- oder Tiefpunkt liegt, stört das nicht. Beachte auch, was ich für den Startwert der Folge verlange.

26.03.2006, 17:09

555_Nase

Auf diesen Beitrag antworten »

Kann mir jemand sagen wozu diese Konvergenzbedingung gut sein soll?
$\begin{eqnarray*} \mid \frac{f(x) * f''(x)}{f'(x) ²} \mid \end{eqnarray*}$ < 1

MfG 555_Nase

Neue Frage »

Antworten »

Konvergenz bei Nullstellenbestimmung mit iterativen Verfahren

Verwandte Themen