Proposition: Globale Konvergenz des Newton-Verfahren in IR

28.05.2021, 08:36

FfWm

Proposition: Globale Konvergenz des Newton-Verfahren in IR

Meine Frage:
Guten Tag zusammen, ich habe eine Frage bezüglich einer eingeführten Proposition in unserer Numerik 1 VL. Die Proposition lautet:
Sei $\begin{eqnarray*} X = \mathbb{R} \end{eqnarray*}$ ein Banachraum und $\begin{eqnarray*} U \neq \varnothing \end{eqnarray*}$ offenes Intervall, $\begin{eqnarray*} f \in C^1\left ( U,\mathbb{R} \right ) \end{eqnarray*}$ eine stetig diffbare Funktion mit Nullstelle $\begin{eqnarray*} x^* \in U \end{eqnarray*}$ .
Dann gelten die beiden Aussagen:
i) f strikt konvex => Newton-Verfahren konv. $\begin{eqnarray*} \forall x_0 \in U \end{eqnarray*}$ mit $\begin{eqnarray*} f\left ( x_0 \right ) > 0 \end{eqnarray*}$ gegen eine Nullstelle von f

ii) f strikt konkav => Newton-Verfahren konv. $\begin{eqnarray*} \forall x_0 \in U \end{eqnarray*}$ mit $\begin{eqnarray*} f\left ( x_0 \right ) < 0 \end{eqnarray*}$ gegen eine Nullstelle von f

Die Proposition behandelt also die Globale Konvergenz in IR.
Nun zu meiner Frage:
Die Proposition an sich, mit den Aussagen und den Voraussetzungen verstehe ich natürlich, ist ja nicht ganz schwer, allerdings kommt sie mir "zu mächtig" in Bezug auf eine Aufgabe vor, wenn man zeigen soll, dass eine Funktion für alle Startwerte konvergiert.

Meine Ideen:
Habe ich bsp. die Funktion f gegeben mit:
$\begin{eqnarray*} f:\mathbb{R}\rightarrow \mathbb{R}, x \mapsto f\left ( x \right ) = exp(50x)-exp(-50) \end{eqnarray*}$ .
Dann sind ja offensichtlich alle Voraussetzungen erfüllt.
1. IR ist Banachraum
2. U ist nicht leeres, offenes Intervall
3. f sogar unendlich oft stetig diffbar, also $\begin{eqnarray*} f \in C^{\infty }\left ( U,\mathbb{R} \right ) \end{eqnarray*}$ , also auch 1-mal stetig diffbar
4. f hat Nullstelle (eine reelle, mehrere komplexe) $\begin{eqnarray*} x^* = -1 \in U \end{eqnarray*}$
Also sind ja alle Voraussetzungen erfüllt.
Nun wende ich die Porp. an:
Leite f zweimal ab und bekomme $\begin{eqnarray*} f''(x) = 2500exp(50x) > 0 \forall x \in \mathbb{R} \end{eqnarray*}$ => f konvex
=> nach Prop. Newton-Verfahren konv. für alle Startwerte, da $\begin{eqnarray*} f(x_0) > 0 \forall x_0 \in \mathbb{R} \end{eqnarray*}$
Übersehe ich hier etwas?

LG

28.05.2021, 13:50

Huggy

Auf diesen Beitrag antworten »

RE: Proposition: Globale Konvergenz des Newton-Verfahren in IR

Zitat:

Original von FfWm
=> nach Prop. Newton-Verfahren konv. für alle Startwerte, da $\begin{eqnarray*} f(x_0) > 0 \forall x_0 \in \mathbb{R} \end{eqnarray*}$

$\begin{eqnarray*} f(x_0) > 0 \, \forall x_0 \in \mathbb{R} \end{eqnarray*}$

ist nicht richtig. Für $\begin{eqnarray*} x_0<-1 \end{eqnarray*}$ ist doch $\begin{eqnarray*} f(x_0)<0 \end{eqnarray*}$ . Trotzdem konvergiert bei dieser Funktion das Newtonverfahren im Prinzip auch bei Startwerten $\begin{eqnarray*} x_0<-1 \end{eqnarray*}$ . Allerdings bekommt man dann leicht numerische Probleme, weil die Tangentensteigung gegen Null geht, wenn man $\begin{eqnarray*} x_0 \end{eqnarray*}$ immer mehr verkleinert.

28.05.2021, 14:01

FfWm

Auf diesen Beitrag antworten »

Oh vielen Dank für das drauf aufmerksam machen. Tendenziell würde es aber klappen, also mit einer anderen Funktion, für die alles passt?
Um auf das Beispiel zurück zukommen, hier dann einfach stumpf nachweisen, dass die Folge $\begin{eqnarray*} x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \end{eqnarray*}$ eine konvergente Folge ist, um nachzuweisen, dass das Newton-Verfahren für alle Startwerte konvergiert?

LG

28.05.2021, 15:20

Huggy

Auf diesen Beitrag antworten »

Das sind doch oben zwei unterschiedliche Fälle. Eine Funktion kann nicht zugleich strikt konvex und strikt konkav sein.

29.05.2021, 09:47

FfWm

Auf diesen Beitrag antworten »

Nein das meine ich nicht, für das Beispiel konkret dann zeigen das die Folge konv. ohne die Propisition.
Beispielsweise mittels Monotonie und Beschränktheit als Kriterium einer konvergenten Folge.
Gibt es sonst noch Alternativen, wenn man zeigen soll, dass eine Funktion für alle Startwerte mit dem Newton-Verfahren konvergiert?

LG

29.05.2021, 10:36

Huggy

Auf diesen Beitrag antworten »

Mir ist nicht klar, wie dein Beweis für deine Funktion im Detail aussieht. Aber irgendwie wird da schon eingegangen sein, dass sie strikt konvex ist.

Wenn eine Funktion weder strikt konvex noch strikt konkav ist, wird das Verfahren im allgemeinen nicht für alle Startwerte konvergieren.

29.05.2021, 11:33

IfindU

Auf diesen Beitrag antworten »

@FfWm

Ist stimme zu, du wirst es per Definition nachweisen müssen. Derzeit hab ich die Hoffnung, dass $\begin{eqnarray*} x_1 >0 \end{eqnarray*}$ ist, falls $\begin{eqnarray*} x_0 < -1 \end{eqnarray*}$ im Iterationsschritt. Wenigstens anschaulich könnte es gut hinhauen (Funktion ist für negative $\begin{eqnarray*} x \end{eqnarray*}$ super flach und steigend, daher vermute ich die Tangente trifft die positive $\begin{eqnarray*} x \end{eqnarray*}$ -Achse). Wenn du dann noch zeigst, dass die Funktionswerte rechts von der Nullstelle immer positiv bleiben, dann kannst du den Satz anwenden.

29.05.2021, 12:45

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Wenn du dann noch zeigst, dass die Funktionswerte rechts von der Nullstelle immer positiv bleiben, dann kannst du den Satz anwenden.

Wenn ich den Fragesteller richtig verstehe, möchte er die Konvergenz der Newton-Iteration für jeden Startwert bei seiner Funktion nachweisen, ohne die Proposition zu benutzten:

Zitat:

Original von FfWm
Nein das meine ich nicht, für das Beispiel konkret dann zeigen das die Folge konv. ohne die Propisition.

29.05.2021, 17:08

IfindU

Auf diesen Beitrag antworten »

@Huggy Ich habs so verstanden, dass er die Aufgabe lösen wollte. Die Proposition kann man nur für gewisse Anfangswerte benutzen, d.h. es ist noch Arbeit notwendig, wenn man es für alle Anfangswerte zeigen kann.

30.05.2021, 17:21

FfWm

Auf diesen Beitrag antworten »

Entschudigung für die verspätete Antwort. Es ist genau wie Huggy in seinem letzten Beitrag geschrieben hat. Ich soll zeigen, dass die Funktion f für alle Startwerte mit dem Newton-Verfahren konvergiert. Ich dachte mit der Proposition würde es gehen, bis Huggy mich eines Besseren belehrt hat.
Dann war meine Anschlussfrage, wie ich noch zeigen könnte, dass die Funktion für alle Startwerte konvergiert. Darauf hab ich nun die Antwort bekommen, mittels der Definition.
Scheinbar laut IfindU auch möglich die Proposition zu nutzen, wenn ich zeige, dass die Funktionswerte rechts von der Nullstelle immer positiv bleiben.
Also über die stumpfe Definition oder eben mithilfe der Proposition (mit etwas Arbeit vorher).
Über die Definition ist mir allerdings unklar.

LG

30.05.2021, 17:46

Huggy

Auf diesen Beitrag antworten »

Für $\begin{eqnarray*} x_0<-1 \end{eqnarray*}$ musst du nur zeigen, dass dann $\begin{eqnarray*} x_1>-1 \end{eqnarray*}$ . Danach kannst du wieder die Proposition i) benutzen.

30.05.2021, 19:20

FfWm

Auf diesen Beitrag antworten »

Ja das dachte ich mir, dass es mit der Proposition irgendwie "einfacher", bzw. eleganter ist.
Dann beweise ich das so, allerdings noch die Frage was mit über Definition gemeint ist.
Einfach wie ich erläutert habe, dass ich zeige, dass die Folge $\begin{eqnarray*} x_{n+1} = x_n + \frac{f(x_n)}{f'(x_n)} \end{eqnarray*}$ monoton und beschränkt ist? (kommt mir etwas umständlich vor)

31.05.2021, 07:20

Huggy

Auf diesen Beitrag antworten »

Bei $\begin{eqnarray*} x_0<-1 \end{eqnarray*}$ musst du für die erste Iteration die Definition anwenden. Wenn du für $\begin{eqnarray*} x_0>-1 \end{eqnarray*}$ mit der Definition arbeiten willst, geht das so, wie von dir beschrieben. Natürlich ist das umständlicher, als den schon bewiesenen Satz zu verwenden.

31.05.2021, 08:30

FfWm

Auf diesen Beitrag antworten »

Sehr gut, vielen Dank für die Hilfe!

LG

Neue Frage »

Antworten »

Proposition: Globale Konvergenz des Newton-Verfahren in IR

Verwandte Themen