Startwert Newton-Verfahren

22.06.2006, 16:18

floh

Auf diesen Beitrag antworten »

Startwert Newton-Verfahren

Gibt es eine Formel um den Startwert für das Newton-Verfahren zu ermitteln?

Vielleicht kann mir jemand bei der folgenden Aufgabe weiterhelfen:

$\begin{eqnarray*} f(x)=e^{\frac{1}{3}-\frac{x}{2}} \end{eqnarray*}$
$\begin{eqnarray*} g(x)=x^4-\frac{8}{3}x^3+\frac{67}{24}x^2-\frac{50}{27}x+\frac{257}{162} \end{eqnarray*}$

Bestimmen Sie die Schnittpunkte von f und g mit dem Newtonverfahren.

Lösungsansatz:

$\begin{eqnarray*} x_{n+1}=x_n-\frac{x^4-\frac{8}{3}x^3+\frac{67}{24}x^2-\frac{50}{27}x+\frac{257}{162}-e^{\frac{1}{3}-\frac{x}{2}}}{4x^3-8x^2+\frac{67}{12}x-\frac{50}{27}+\frac{1}{2}e^{\frac{1}{3}-\frac{x}{2}}} \end{eqnarray*}$

Wie kann ich nun die Startwerte ermitteln?

22.06.2006, 16:50

tigerbine

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren
Hallo,

i.A. gibt es keine solche Formel. Das ist ja gerade das Problem beim Newtwon Verfahren.

Es kann zwar gezeigt werden, dass es eine Kugel um die Nullstelle x* der Funktion z(x):=f(x) - g(x) (Ist dann ja der Schnittpunkt von f,g) gibt, in der das Newton Verfahren lokal konvergiert, aber der Kugelradius wird dabei i.A. nicht angegeben.

Man tastet sich mit dem Bisektionsverfahren heran (Intervallschachtelung), aber Achtung!, das geht nur für Nullstellen mit Vorzeichenwechsel!

Für eine zweimal stetig differenzierbare Funktion z, kenne ich folgenden Ansatz: Bestimme durch IV ein Intervall [a,b] in dem nur eine Nullstelle von z liegt. Dann

$\begin{eqnarray*} m:=\min_{x\in[a,b]} |f'(x)|>0; M:=\max_{x\in[a,b]} |f''(x)|<\infty \end{eqnarray*}$

Wähle $\begin{eqnarray*} c > 0 \end{eqnarray*}$ so, dass $\begin{eqnarray*} \frac{M}{2m}c < 1 \end{eqnarray*}$ gilt. Dann konvergiert das Newtonverfahren für alle $\begin{eqnarray*} x \in K_{c}(x*) \end{eqnarray*}$

22.06.2006, 17:18

floh

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren
Woher weiß ich, welchen Intervall ich für das Bisektion-Verfahren wählen muss?

Wie würde das im Beispiel aussehen?

22.06.2006, 17:40

tigerbine

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren
Es muss gelten f(a)*f(b) < 1, D.h. f(a) und f(b) haben unterschiedliche Vorzeichen.

Ausprobieren!

Dann das Intervall mit dem Bisektionsverfahren verkleinern, so ist es wahrscheinlicher, dass die Funktion darin nur eine Nullstelle hat!

22.06.2006, 18:29

floh

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren
Ist es richtig, wenn ich den Intervall im Bisektionsverfahren wie folgt einsetze?

$\begin{eqnarray*} m:=\min_{x\in[a,b]} |f'(x)|=|f'(a)-f'(b)|>0; M:=\max_{x\in[a,b]} |f''(x)|=|f''(a)-f''(b)|<\infty \end{eqnarray*}$

22.06.2006, 19:06

tigerbine

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren
Nein, den Extremwert einer Funktion z auf einem Intervall [a,b] erhälst du doch nicht dadurch, dass Du z(a) - z(b) rechnest!

Sei nun z(x):=f(x) - g(x)
Zunächst musst Du ein, möglichst kleines Intervall [a,b] finden, indem gilt z(a)*z(b) < 0 (Sorry ich hatte f geschrieben)

Dann musst Du das Minimum von z' in [a,b] suchen und das Maximum von z'' in [a,b].

Wie man Extremstellen bestimmt weisst Du doch? (Ableiten - nullsetzten - Nullstell in nächst höhre ableitung einsetzten)

Anzeige

22.06.2006, 20:52

mathemaduenn

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren
Hallo tigerbine

Zitat:

Original von tigerbine

Dann musst Du das Minimum von z' in [a,b] suchen und das Maximum von z'' in [a,b].

Wie man Extremstellen bestimmt weisst Du doch? (Ableiten - nullsetzten - Nullstell in nächst höhre ableitung einsetzten)

Das Problem was ich da sehe ist:
Das ist doch fast genauso schwierig wie die Nst. der Funktion selbst bestimmen.
Diese Abschätzungen sind wohl eher theoretisch interessant oder?
viele Grüße
mathemaduenn

22.06.2006, 21:05

tigerbine

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren
Leider ist das bei Newton so. Und das Verfahren was ich hingeschrieben habe ist der mir im moment einzig "konkrete" Weg zu einer Lösung.

Dass sich gerade die e-Funktion nicht stark verändert ist klar Augenzwinkern

Augenzwinkern

Deswegen bleibt wohl nur Bisektion und dann hoffen, dass man schon im Konvergenzintervall ist. Wink

Wink

22.06.2006, 23:19

floh

Auf diesen Beitrag antworten »

Ok, ich versuch's mal an einem einfacherem Beispiel:

$\begin{eqnarray*} f(x)=x^3-2 \end{eqnarray*}$
$\begin{eqnarray*} f'(x)=3x^2 \end{eqnarray*}$

$\begin{eqnarray*} x_{k+1}=\frac{2}{3}(x_k+\frac{1}{x^2_k}) \end{eqnarray*}$

Um den Startwert für das Newton-Verfahren zu finden, wähle ich einen Intervall [a,b]. Wenn ich für a=0 und b=2 einsetze, so erhalte ich $\begin{eqnarray*} f(a)*f(b)= (-2)*(6)=-12<0 \end{eqnarray*}$

$\begin{eqnarray*} f(x)=0 \end{eqnarray*}$ :
$\begin{eqnarray*} x=\sqrt[3]{2} \end{eqnarray*}$

$\begin{eqnarray*} m:=|f'(\sqrt[3]{2})|=|3(\sqrt[3]{2})^2=4,76|>0 \end{eqnarray*}$ für das Minimum
$\begin{eqnarray*} M:=|f''(\sqrt[3]{2})|=|6(\sqrt[3]{2})=7,56|<\infty \end{eqnarray*}$ für das Maximum

Wenn ich jetzt in $\begin{eqnarray*} \frac{M}{2m}c=\frac{7,56}{2*4,76}c<1 \end{eqnarray*}$ einsetze erhalte ich $\begin{eqnarray*} 0,794c<1 \end{eqnarray*}$

Es stimmt so nicht, oder? Denn der Startwert fehlt dann immer noch. Der ist in der Lösung mit 2 angegeben.

22.06.2006, 23:24

tigerbine

Auf diesen Beitrag antworten »

ich rechne es mal durch. Kann aber nen Moment dauern

Gruß vom Tiger Wink

Wink

22.06.2006, 23:45

tigerbine

Auf diesen Beitrag antworten »

Also $\begin{eqnarray*} f(x) = x^{3} - 2 \end{eqnarray*}$
$\begin{eqnarray*} f'(x) = 3x^{2} \end{eqnarray*}$

Das Intervall [a,b] muss nun so gewählt wrden, dass f(a)f(b) < 0 und

$\begin{eqnarray*} min_{x \in [a,b]}|f'(x)| > 0 \end{eqnarray*}$ gilt.

Deswegen ist deine Wahl für a=0 nicht gut. Wählen wir a=1 und b=2. Dann ist: f(a) = -1 und f(b) = 6, also f(1)f(2) < 0.

$\begin{eqnarray*} f''(x) = 6x \end{eqnarray*}$ ist auf [1,2] >0, somit ist $\begin{eqnarray*} f'(x) \end{eqnarray*}$ auf [1,2] streng monoton steigend. Daher folgt:

m:= |f'(1)| = 3

M:= |f''(2)| = 12

Wähle nun r so, dass $\begin{eqnarray*} \frac{12}{2*3} r= 2r < 1 \end{eqnarray*}$ gilt, also z.B. $\begin{eqnarray*} r = \frac{1}{4} \end{eqnarray*}$

Dies mal zu deinen Berechnungen.

Dein "Musterstartwert 2" hängt hier mit der Besonderen Aufgabenstellung zusammen. Allgemein handelt es sich um die Bestimmung der n-ten Wurzel einer Zahl a >0. In diesem Fall konvergiert das NewtonVerfahren für alle Startwerte x0 > 0. Die Wahl fiel wohl auf 2, da sie die nächste ganze Zahl nach der gesuchten Wurzel ist.

Gruß Wink

Wink

26.06.2006, 02:04

floh

Auf diesen Beitrag antworten »

Vielen Dank für die Antwort! Bis hier hin habe ich es soweit verstanden. Wie bekomme ich daraus den gesuchten Startwert?

26.06.2006, 12:24

tigerbine

Auf diesen Beitrag antworten »

Hallo Floh,

ich habe deine Frage zur Kenntnis genommen. Schreibe Dir im Laufe des Nachmittags nochmal zu dem Thema.

Gruß,
Tigerbine Wink

Wink

So, wieder zurück.

also wir haben jetzt rausgefunden, dass es ein Intervall um die Lösung x* , der Länge $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ gibt, indem das Newoten Verfahren konvergiert. Unser Intervall [a,b] = [1,2] ist also noch ein bischen zu groß. Da machen wir nochmal Bisektion:

[1, 1,5], da gilt f(1)(f(1,5) <0.

Da wir aber nicht wissen, ob x* sehr nahe am Rand dieses Intervalls liegt, versuchen wir mittels Bisejktion das Intervall auf die Länge $\begin{eqnarray*} \frac{1}{4} \end{eqnarray*}$ zu bringen. Dann ist man auf der sicheren Seite!

Da gehört halt ein bischen Ausdauer und Glück dazu :-)

[1,25;1,5], da gilt f(1,25)f(1,5) < 0

Also finally wird das Newtonverfahren für jeden Startwert aus diesem Intervall konvergieren.

Heißt für die Anwendung von r aus n, M: Bestimme mit Bisektion ein Intervall der Länge r, in dem f(a)f(b) < 0 gilt. Dann konvergiert das NewtonVerfahren für jeden Startwert aus [a,b]

Gruß Wink

Wink

27.06.2006, 11:12

mathemaduenn

Auf diesen Beitrag antworten »

Ausprobieren
Hallo zusammen,
Mal was anderes:
Wie wär's mit ausprobieren. 0 und 1 scheinen mir doch sehr sinnvolle Startwerte zu sein...
viele Grüße
mathemaduenn

27.06.2006, 13:11

tigerbine

Auf diesen Beitrag antworten »

RE: Startwert Newton-Verfahren

Zitat:

Original von floh
Gibt es eine Formel um den Startwert für das Newton-Verfahren zu ermitteln?

@mathemaduenn

Wenn Du "Raten" als Formel ansiehst Augenzwinkern

Augenzwinkern

29.06.2011, 12:37

Steinenberg

Auf diesen Beitrag antworten »

Hallo Tigerbiene!
Ich hätte da mal 2 Fragen zu deinen Erklärungen:

1.Wähle nun r so, dass $\begin{eqnarray*} \frac{12}{2*3} r= 2r < 1 \end{eqnarray*}$ gilt, also z.B. $\begin{eqnarray*} r = \frac{1}{4} \end{eqnarray*}$
Warum wird hier nicht r mittels dieser Formel ausgerechnet? $\begin{eqnarray*} \frac{M}{2m}r < 1 \end{eqnarray*}$
Das würde auch den "Musterstartwert 2" erklären.

2.Wie kommst du auf diese Aussage:
"also wir haben jetzt rausgefunden, dass es ein Intervall um die Lösung x* , der Länge $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ gibt, indem das Newton..."

Vielen dank schon im Voraus!

29.06.2011, 13:49

tigerbine

Auf diesen Beitrag antworten »

Hallo,

verstehe nicht, was du mit Ausrechnen meinst. Wir haben die Abschätzung doch verwendet. Das r ist der Radius der Umgebung um die Nullstelle. Für den muss gelten $\begin{eqnarray*} r < \frac{1}{2} \end{eqnarray*}$ . Da habe ich einfach ein Beispiel gewählt. Es ist ja nicht verlangt, das maximale Intervall zu bestimmen. Mein gewählter Radius um die Nullstelle liefert dann ein Intervall der Länge 0.5.

Wir waren hier ja so vorgegangen, ein Intervall zu bestimmen, wo wir (mind) eine Nullstelle wissen.

Dort haben wir dann die Umgebung der quadr. Konvergenz bestimmt. [WS] Eindimensionale Nullstellenprobleme 2 - Das Newton Verfahren Einfach aus dem Grund, dass man das auch bei anderen Beispielen so machen kann.

Diese spezielle Aufgabe genügt aber auch diesem Konvergenzbeweis, so dass man mit jedem positiven Startwert hätte starten können. [WS] Eindimensionele Nullstellenprobleme - Beispiele Also auch mit der 2.

29.06.2011, 15:33

Steinenberg

Auf diesen Beitrag antworten »

Hallo!

Vielen vielen Dank für die schnelle und ausführliche Antwort - hab alles verstanden!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »