Nichtlineare Gleichungen, das gewöhnliche Newton-Verfahren

Question

Aufgabe: Nichtlineare Gleichungen.

Die Funktion \( f: \mathbb{R} \rightarrow \mathbb{R}, f(x)=\frac{1}{x^{3}}-\frac{1}{27} \) beschreibt die nichtlineare Gleichung \( f(x)=0 \) mit der eindeutigen Lösung \( \hat{x}=3 \).

a) Berechnen Sie die Iterationsfunktion \( \Phi(x) \) des gewöhnlichen Newton-Verfahrens für obiges Problem. Betrachten Sie das kompakte Intervall \( U=[2,4] \). Leiten Sie eine Konstante \( C>0 \) her, so dass für die Iteration aus dem gewöhnlichen Newton-Verfahren gilt
\( \left|x^{k+1}-\hat{x}\right| \leq C \cdot\left|x^{k}-\hat{x}\right|^{2} \)
sofern \( x^{k} \in U \). Bestimmen Sie ein \( 0<\delta \leq 1 \), welches die Konvergenz des gewöhnlichen Newton-Verfahrens für alle Startwerte \( x^{0} \in(\hat{x}-\delta, \hat{x}+\delta) \) garantiert.

b) Berechnen Sie für obiges Problem die Iterationsfunktion \( \Psi(x) \) des vereinfachten Newton-Verfahrens mit Startwert \( x^{0}=2 \).

c) Werten Sie \( \Phi^{\prime}(\hat{x}) \) und \( \Psi^{\prime}(\hat{x}) \) aus und ziehen Sie daraus Folgerungen für die Konvergenzordnung des jeweiligen Verfahrens.

Problem/Ansatz:

Hallo zusammen, könnte mir jemand bitte dabei helfen? Ich habe was gemacht aber ich bin mir nicht sicher, ob es richtig ist...

zu a)

\( f(x) = \frac{1}{x^3} - \frac{1}{27} = 0 \). Ableiten ergibt \( f'(x) = -\frac{3}{x^4} \).

Die Iterationsfunktion \( \Phi(x) \) lautet dann: \( \Phi(x) = x - \frac{f(x)}{f'(x)} = x - \frac{\frac{1}{x^3} - \frac{1}{27}}{-\frac{3}{x^4}} \).


zu b)

Das vereinfachte Newton-Verfahren hat die Iterationsfunktion \( \Psi(x) \) gegeben durch: \( \Psi(x) = x - \frac{f(x)}{f'(x_0)} \)

= \( \Psi(x) = 2 - \frac{\frac{19}{216}}{-\frac{3}{16}} \)

Comments

Ich würde zunächst \(\Phi\) vereinfachen und \(\Psi\) korrigieren (unterscheide zwischen x und \(x_0\)).

Dann die Gretchenfrage: Habt Ihr in der Vorlesung allgemeine Formeln zur Bestimmung der Konstanten C und delta hergleitet - oder sollt Ihr das mit elementaren Analysis-Kenntnissen erledigen?

---

Definition: Sei \( \hat{x} \in D \) ein Fixpunkt von \( \Phi: D \rightarrow D \). Die Iteration (8.4) ist lokal konvergent von (mindestens) der Ordnung \( p \geq 1 \), wenn eine Umbegbung \( V \subset D \) von \( \hat{x} \) existiert, so dass

\( \left|x^{k+1}-\hat{x}\right| \leq C\left|x^{k}-\hat{x}\right|^{p} \)
für alle Startwerte \( x^{0} \in V \) gilt mit einer Konstanten \( C \geq 0 \). Im Fall \( p=1 \) muss zudem \( C<1 \) gelten.

Ich weiß nicht ob das jetzt hilft..

---

Das ist nur die Definition von Konvergenzordnung. Wie sieht denn Deine Vereinfachung von Phi aus?

---

phi ist gleich \( -\frac{x(3-x)(9+3x+x^2)}{81} \)

---

Berechne mal Phi(3) für das Original und die Vereinfachung

---

aber wieso 3?

---

Du hast eingangs eine Funktion Phi definiert. Dann hast Du dies vereinfacht. Um zu prüfen ob Du das richtig gemacht hast, sollst Du beide Varianten für x=3 auswerten.

---

Ja das war faksch ich habe das jetzt korrigiert. Die Vereinfachung ist: \( \frac{x(108-x^3)}{81} \).

Kannst du mir bitte bei c) und bei dem zweiten Teil von a) helfen?

---

Das \(\Phi\) stimmt nun.
Habt Ihr in der Vorlesung nachgewiesen, dass das Newton-Verfahren lokal quadratisch konvergiert?

Welche Sätze habt Ihr zur Konvergenz von Fixpunktiterationen gemacht?

---

Meinst du sie ne?

Satz: Sei \( \hat{x} \) eine Nullstelle von \( F: D \rightarrow \mathbb{R}^{n}\left(D \subset \mathbb{R}^{n}\right) \),

\( F(x)=\left(f_{1}(x), \ldots, f_{n}(x)\right)^{\top}, \quad x=\left(x_{1}, \ldots, x_{n}\right)^{\top} \)
und \( F \in C^{2}(D) \). Wir definieren bezüglich der Maximumnorm
\( \mathcal{K}:=\left\{x \in \mathbb{R}^{n}:\|x-\hat{x}\|_{\infty} \leq r\right\} \subset D \)
und
\( M:=\max \left\{\left|\frac{\partial^{2} f_{\ell}}{\partial x_{i} \partial x_{j}}(x)\right|: 1 \leq \ell, i, j \leq n, \quad x \in \mathcal{K}\right\} . \)
Wenn \( \operatorname{det} D F(\hat{x}) \neq 0 \) und
\( \beta r \leq \frac{1}{2} \quad \text { mit } \quad \beta:=n^{2} M\left\|D F(\hat{x})^{-1}\right\|_{\infty} \)
gilt, dann existiert die Folge \( \left(x^{k}\right)_{k \in \mathbb{N}} \) definiert durch das Newton-Verfahren für beliebiges \( x^{0} \in \mathcal{K} \), d.h. alle Matrizen \( D F\left(x^{k}\right) \) sind regulär. Die Folge konvergiert gegen \( \hat{x} \) und es gilt
\( \left\|x^{k+1}-\hat{x}\right\|_{\infty} \leq \beta\left\|x^{k}-\hat{x}\right\|_{\infty}^{2} \leq \frac{1}{2}\left\|x^{k}-\hat{x}\right\|_{\infty} . \)

Satz: (Newton-Kantorovich)

Sei \( D \subset \mathbb{R}^{n} \) offen und konvex sowie \( F: D \rightarrow \mathbb{R}^{n} \) eine glatte Funktion \( \left(F \in C^{1}\right) \). Für einen Startwert \( x^{0} \in D \) sei \( \operatorname{det} D F\left(x^{0}\right) \neq 0 \). Konstanten \( \alpha, \beta, \gamma \geq 0 \) sollen existieren mit
(i) \( \left\|D F\left(x^{0}\right)^{-1} F\left(x^{0}\right)\right\| \leq \alpha \)
(ii) \( \left\|D F\left(x^{0}\right)^{-1}\right\| \leq \beta \)
(iii) \( \|D F(x)-D F(y)\| \leq \gamma\|x-y\| \) für alle \( x, y \in D \).
in einer beliebigen Vektornorm und korrespondierender Matrixnorm. Wir definieren die Werte
\( h:=\alpha \beta \gamma, \quad \rho_{1,2}:=\frac{\alpha}{h}(1 \mp \sqrt{1-2 h}) \)
und Mengen
\( S_{\rho_{1 / 2}}\left(x^{0}\right):=\left\{x \in \mathbb{R}^{n}:\left\|x-x^{0}\right\|<\rho_{1 / 2}\right\} . \)
Wenn \( h \leq \frac{1}{2} \) und \( \overline{S_{\rho_{1}}\left(x^{0}\right)} \subset D \) gilt, dann existiert die Folge \( \left(x^{k}\right)_{k \in \mathbb{N}} \) aus dem Newton-Verfahren (alle Matrizen DF \( \left(x^{k}\right) \) sind regulär). Die Folge ist in \( S_{\rho_{1}}\left(x^{0}\right) \) enthalten und konvergiert gegen eine Nullstelle von \( F \). Diese Nullstelle ist eindeutig in der Menge \( D \cap S_{\rho_{2}}\left(x^{0}\right) \).

---

Aha, also kommt die Aufgabe doch nicht aus heiterem Himmel.

Schreib den ersten Satz auf für den Fall hier, also für diese f und dieses n=1. Erstmal nur abschreiben(!!!) mit den Angaben aus der Aufgabenstellung.

Übungsaufgaben dienen in der Regel dazu, den Vorlesungsstoff zu festigen. Wenn Du uns den nicht wissen lässt, können wir nicht gut helfen.

---

Satz: Sei \( \hat{x} \) eine Nullstelle von \( f: \mathbb{R} \rightarrow \mathbb{R} \) mit \( f(x) = \frac{1}{x^3} - \frac{1}{27} \), und es gelte \( f \in C^2(\mathbb{R}) \). Bezüglich der Maximumnorm sei

\( \mathcal{K}:=\left\{x \in \mathbb{R} : \|x - \hat{x}\|_{\infty} \leq r\right\} \)

ein kompaktes Intervall um \( \hat{x} \), und \( M \) sei definiert als

\( M := \max \left\{\left|\frac{\partial^{2} f}{\partial x^{2}}(x)\right| : x \in \mathcal{K}\right\} \)

Wenn \( f'(\hat{x}) \neq 0 \) und

\( \beta r \leq \frac{1}{2} \)

mit

\( \beta := M \left| \frac{1}{{f}'(\hat{x})} \right| \)

gilt, dann existiert die Folge \( \left(x^{k}\right)_{k \in \mathbb{N}} \) definiert durch das Newton-Verfahren für beliebiges \( x^{0} \in \mathcal{K} \). Die Folge konvergiert gegen \( \hat{x} \) und es gilt

\( \left|x^{k+1} - \hat{x}\right|_{\infty} \leq \beta \left|x^{k} - \hat{x}\right|_{\infty}^{2} \leq \frac{1}{2} \left|x^{k} - \hat{x}\right|_{\infty} \)

So?

---

Zu c) Wir berechnen die Ableitung von \(\Phi(x)\) und \(\Psi(x)\) an der Stelle \(\hat{x}=3\) (da \(\hat{x}=3\) die eindeutige Lösung der Gleichung \(f(x) = 0\) ist):

Für \(\Phi(x)\):

\( \Phi(x) = \frac{x(108-x^3)}{81} \)
\( \Phi'(x) = \frac{108-4x^3}{81} \)

Setzen wir \(x=\hat{x}=3\) ein:

\( \Phi'(\hat{x}) = \frac{108-4(3)^3}{81} = 0 \)

Die Konvergenzordnung des gewöhnlichen Newton-Verfahrens ist \(p = 2\), da \(\Phi'(\hat{x}) = 0\).

Für \(\Psi(x)\):

\( \Psi(x) = x + \frac{16}{3x^3}-\frac{16}{81} \)

\( \Psi'(x) = 1 - \frac{16}{x^4} \)

Setzen wir \(x=\hat{x}=3\) ein:

\( \Psi'(\hat{x}) = 1 - \frac{16}{(3)^4} = \frac{65}{81} \)

Die Konvergenzordnung des vereinfachten Newton-Verfahrens ist \(p = 1\), da \(\Psi'(\hat{x}) \neq 0\).






Ich glaube das ist richtig oder?

---

Ich komme auf ein anderes \(\Psi(x)\).

---

Wie sieht dein \(\Psi(x)\) aus? Ich habe nochmal gerechnet und habe das gleiche rausbekommen

---

Ich hab keine Ahnung wo Du die 16 herholst. Hast Du vielleicht ein falsches \(\hat x\) eingesetzt?

---

Ich habeden Startwert x^0 = 2 eingesetzt

---

Ich komme auch auf

Ψ(x) = x - f(x)/f'(2) = x + 16/(3·x^3) - 16/81

---

Achso, sorry, ich hab falsch eingesetzt. Ich bin einfach nicht gut darin, mehrere ähnliche Aufgaben parallel zu bearbeiten.

Die Schlussfolgerung ist dann richtig, wenn das entsprechende Resultat in der Vorlesung dran war (und das sollte man hier erwähnen und nicht einfach schreiben, "ist so").

Teil a) fehlt weiterhin.

---

Hi,

ich hab mal auf der Studeez App die Lösung generieren lassen, schau mal hier :) Vielleicht hilft das weiter! Kann die App auf jeden Fall empfehlen, da dir die KI die Aufgaben erklärt und du einfach nur ein Bild machen musst von der Aufgabe.

---

Du solltest Dir die Mühe machen, das Ergebnis zu prüfen, bevor Du es empfiehlst!

Answer 1

Hallo,

ich schreibe mal eine Lösung auf, die direkt mit der Iterationsfunktion Phi arbeitet, die ich zur Vereinfachung mit T bezeichne, also

$$T(x)=\frac{4}{3}x-\frac{1}{81}x^4$$

Mit Ideen aus Deinen anderen Posts:

$$|x^{k+1}-3|=|T(x^k)-3|=|T(3)+T'(3)(x^k-3)+\frac{1}{2}T''(s)(x^k-3)^2| \\\quad=\frac{1}{2}T''(s)(x^k-3)^2|$$

mit einer "Zwischenstelle" s zwischen \(x^k\) und 3. Mit der Vorgabe aus der Aufgabe lässt sich auf U abschätzen:

$$|T''(s)|=|\frac{3\cdot 4}{81}s^2| \leq \frac{12\cdot 16}{81}$$

Also geht \(C=32/27\)

Konvergenz im Intervall \((83-\delta,3+\delta)\) mit \(\delta<1\) tritt offenbar ein, wenn

$$C \delta<1, \text{   also }\delta<27/32$$

Comments

Danke erstmal für deine Antwort

Woher hast du das? \( T(x)=\frac{4}{3} x-\frac{1}{81} x^{4} \)

Ich verstehe nicht woher du die Werte hast

---

Es ist T=\(\Phi\), wie Du es oben angegeben hast

---

Ich habe noch zwei Fragen:

1. Wie kommst du auf 32/27 ? Also (12*16)/81 = 64/27 und nicht 32/27.. oder haben sie nicht miteinander zu tun?

2. Wieso hast da 83 geschrieben und nicht 3 ?

---

1. In der Taylorentwicklung oben hat T'' noch einen Faktor 1/2.

2. Habe mich vertippt.

---

Alles klar danke dir sehr!! :)

---

Meinst du ist das richtig was die App von “Tangente123” gelöst hat, dass C = 3/8 ?

---

Das ist doch offenbar Quatsch

---

mit \(\delta<1\) tritt offenbar ein, wenn$$C \delta<1, \text{  also }\delta<27/32$$

delta sollte kleiner gleich sein, und nicht nur kleiner als ne?

Answer 2

Fast. Mit der \(\infty\)-Norm haben wir hier nichts zu tun. Passe entsprechend an.

Nächster Schritt: weitere Anpassungen: \(K=?, \hat x=?, R=?\), usw.

Comments

Ehrlich gesagt keine Ahnung..

---

\( \hat{x}=3 \)

\(f(x) = \frac{1}{x^3} - \frac{1}{27}\)

\(f'(x) = -\frac{3}{x^4}\)

\(f''(x) = \frac{12}{x^5}\)

\(M = \max \left\{\left|\frac{12}{x^5}\right| : x \in [2, 4]\right\}\)

Um das Maximum zu finden, betrachten wir die Randpunkte des Intervalls und die kritischen Punkte im Inneren des Intervalls:

1. Für \(x = 2\): \(|f''(2)| = \frac{12}{2^5} = \frac{3}{16}\)
2. Für \(x = 4\): \(|f''(4)| = \frac{12}{4^5} = \frac{3}{512}\)

\(M = \frac{3}{16}\).

\( \beta := M \left| \frac{1}{{f}'(\hat{x})} \right| = \frac{3}{16} \left| \frac{1}{-\frac{1}{27}} \right| = \frac{3}{16} \cdot 27 = \frac{81}{16} \)

\( \beta r \leq \frac{1}{2} \)

\( \frac{81}{16} \cdot r \leq \frac{1}{2} \)

\( r \leq \frac{1}{2} \cdot \frac{16}{81} \)

\( r \leq \frac{8}{81} \)

\( \mathcal{K} = \left\{ x \in \mathbb{R} : |x - 3| \leq r \right\} \)

---

Ok. Aber gehe geordnet vor, so wie es im Satz erwähnt ist: Zuerst kommt \(\cal K\), mit seinem \(r\). Danach(!) kannst Du auch erst \(M\) bestimmen. Passe entsprechend an und teile dann mit, ob der Satz schon das gewünschte liefert oder was noch nötig ist.

---

Satz: Sei \( \hat{x} \) eine Nullstelle von \( f: \mathbb{R} \rightarrow \mathbb{R} \) mit \( f(x)=\frac{1}{x^{3}}-\frac{1}{27} \), und es gelte \( f \in C^{2}(\mathbb{R}) \). Bezüglich der Maximumnorm sei

\( \mathcal{K}:=\left\{x \in \mathbb{R}:\|x-3\| \leq r\right\} \)
ein kompaktes Intervall um 3, und \( M \) sei definiert als
\( M:=\max \left\{\left|\frac{12}{x^{5}}\right|: x \in [2,4]\right\} \) = \( \frac{3}{16} \)
Wenn \( f^{\prime}(\hat{x}) \neq 0 \) und
\( \beta r \leq \frac{1}{2} \) \(   ==> r \leq \frac{8}{81} \)
mit
\( \beta:=M\left|\frac{1}{f^{\prime}(\hat{x})}\right| \) = \( \frac{81}{16} \)
gilt, dann existiert die Folge \( \left(x^{k}\right)_{k \in \mathbb{N}} \) definiert durch das Newton-Verfahren für beliebiges \( x^{0} \in \mathcal{K} \). Die Folge konvergiert gegen \( \hat{x} \) und es gilt
\( \left|x^{k+1}-3\right| \leq \frac{81}{16} \left|x^{k}-3\right|^{2} \leq \frac{1}{2}\left|x^{k}-3\right| \)

Kannst du mir jetzt Tipps geben, wie ich das überprüfen kan, ob der Satz schon das gewünschte liefert oder was noch nötig ist.

---

Ich wiederhole vorherige Kommentare:

Mit der \(\infty\)-Norm haben wir hier nichts zu tun.

Aber gehe geordnet vor, so wie es im Satz erwähnt ist: Zuerst kommt \(\cal K\), mit seinem \(r\). Danach(!) kannst Du auch erst \(M\) bestimmen. Passe entsprechend an und teile dann mit, ob der Satz schon das gewünschte liefert oder was noch nötig ist.

---

ok

Kannst du mir bitte noch Tipps zu c) geben?

---

c) kommt nach a) und b).

---

b) habe ich schon gemacht.

a) komme ich nicht weiter deswegen möchte ich lieber mit c) versuchen

---

Das baut doch aufeinander auf. Du musst Dich schon gründlich(!) durcharbeiten. Die Aufgabe ist ein Beispiel für einen Satz aus der Vorlesung. Wenn Du bei der Bearbeitung Teile überspringst, ist klar, dass Du nicht durchkommst. Daher meine Tipps. Wenn Du nicht sagst, wo Du hängen bleibst, kann ich Dir nicht helfen.

---

https://www.mathelounge.de/1027694/entwicklung-iterationsfunktion-gewohnlichen-verfahren

Kannst du bitte da einen Blick werfen, ob meine Lösung richtig ist?

---

Bei der anderen Frage hast Du schon Hilfe.

---

Kannst du mir bitte dabei helfen?..

Sei \( f: \mathbb{R} \rightarrow \mathbb{R} \) eine zweimal stetig differenzierbare Funktion mit einer eindeutigen Nullstelle \( \hat{x} \) für die \( f^{\prime}(\hat{x}) \neq 0 \) gilt. Die Iteration des gewöhnlichen Newton-Verfahrens lautet

\( x^{k+1}=x^{k}-\frac{f\left(x^{k}\right)}{f^{\prime}\left(x^{k}\right)} \text {. } \)

Beschreiben Sie ein Konstruktionsprinzip des gewöhnlichen Newton-Verfahrens und leiten Sie damit die Formel her.

---

Bei der anderen Frage hast Du schon Hilfe.

ja :)

Sei \( f: \mathbb{R} \rightarrow \mathbb{R} \) eine zweimal stetig differenzierbare Funktion mit einer eindeutigen Nullstelle \( \hat{x} \) für die \( f^{\prime}(\hat{x}) \neq 0 \) gilt. Die Iteration des gewöhnlichen Newton-Verfahrens lautet

\( x^{k+1}=x^{k}-\frac{f\left(x^{k}\right)}{f^{\prime}\left(x^{k}\right)} \text {. } \)
Beschreiben Sie ein Konstruktionsprinzip des gewöhnlichen Newton-Verfahrens und leiten Sie damit die Formel her.

Fällt dir da was ein?

---

Sei \( f: \mathbb{R} \rightarrow \mathbb{R} \) eine zweimal stetig differenzierbare Funktion mit einer eindeutigen Nullstelle \( \hat{x} \) für die \( f^{\prime}(\hat{x}) \neq 0 \) gilt. Die Iteration des gewöhnlichen Newton-Verfahrens lautet\( x^{k+1}=x^{k}-\frac{f\left(x^{k}\right)}{f^{\prime}\left(x^{k}\right)} \text {. } \)Beschreiben Sie ein Konstruktionsprinzip des gewöhnlichen Newton-Verfahrens und leiten Sie damit die Formel her.

Das habe ich jetzt hinbekommen :)

Könntest du mir bitte bei a) und bii) helfen:

https://www.mathelounge.de/1027849/nichtlineare-gleichungen-quadratische-konvergenz