0 Daumen
2,6k Aufrufe

Aufgabe: Nichtlineare Gleichungen.


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

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

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

c) Werten Sie Φ(x^) \Phi^{\prime}(\hat{x}) und Ψ(x^) \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)=1x3127=0 f(x) = \frac{1}{x^3} - \frac{1}{27} = 0 . Ableiten ergibt f(x)=3x4 f'(x) = -\frac{3}{x^4} .

Die Iterationsfunktion Φ(x) \Phi(x) lautet dann: Φ(x)=xf(x)f(x)=x1x31273x4 \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 Ψ(x) \Psi(x) gegeben durch: Ψ(x)=xf(x)f(x0) \Psi(x) = x - \frac{f(x)}{f'(x_0)}

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

Avatar von

Ich würde zunächst Φ\Phi vereinfachen und Ψ\Psi korrigieren (unterscheide zwischen x und x0x_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 x^D \hat{x} \in D ein Fixpunkt von Φ : DD \Phi: D \rightarrow D . Die Iteration (8.4) ist lokal konvergent von (mindestens) der Ordnung p1 p \geq 1 , wenn eine Umbegbung VD V \subset D von x^ \hat{x} existiert, so dass

xk+1x^Cxkx^p \left|x^{k+1}-\hat{x}\right| \leq C\left|x^{k}-\hat{x}\right|^{p}
für alle Startwerte x0V x^{0} \in V gilt mit einer Konstanten C0 C \geq 0 . Im Fall p=1 p=1 muss zudem C<1 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 x(3x)(9+3x+x2)81 -\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: x(108x3)81 \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 x^ \hat{x} eine Nullstelle von F : DRn(DRn) F: D \rightarrow \mathbb{R}^{n}\left(D \subset \mathbb{R}^{n}\right) ,

F(x)=(f1(x),,fn(x)),x=(x1,,xn) F(x)=\left(f_{1}(x), \ldots, f_{n}(x)\right)^{\top}, \quad x=\left(x_{1}, \ldots, x_{n}\right)^{\top}
und FC2(D) F \in C^{2}(D) . Wir definieren bezüglich der Maximumnorm
K : ={xRn : xx^r}D \mathcal{K}:=\left\{x \in \mathbb{R}^{n}:\|x-\hat{x}\|_{\infty} \leq r\right\} \subset D
und
M : =max{2fxixj(x) : 1,i,jn,xK}. 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 detDF(x^)0 \operatorname{det} D F(\hat{x}) \neq 0 und
βr12 mit β : =n2MDF(x^)1 \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 (xk)kN \left(x^{k}\right)_{k \in \mathbb{N}} definiert durch das Newton-Verfahren für beliebiges x0K x^{0} \in \mathcal{K} , d.h. alle Matrizen DF(xk) D F\left(x^{k}\right) sind regulär. Die Folge konvergiert gegen x^ \hat{x} und es gilt
xk+1x^βxkx^212xkx^. \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 DRn D \subset \mathbb{R}^{n} offen und konvex sowie F : DRn F: D \rightarrow \mathbb{R}^{n} eine glatte Funktion (FC1) \left(F \in C^{1}\right) . Für einen Startwert x0D x^{0} \in D sei detDF(x0)0 \operatorname{det} D F\left(x^{0}\right) \neq 0 . Konstanten α,β,γ0 \alpha, \beta, \gamma \geq 0 sollen existieren mit
(i) DF(x0)1F(x0)α \left\|D F\left(x^{0}\right)^{-1} F\left(x^{0}\right)\right\| \leq \alpha
(ii) DF(x0)1β \left\|D F\left(x^{0}\right)^{-1}\right\| \leq \beta
(iii) DF(x)DF(y)γxy \|D F(x)-D F(y)\| \leq \gamma\|x-y\| für alle x,yD x, y \in D .
in einer beliebigen Vektornorm und korrespondierender Matrixnorm. Wir definieren die Werte
h : =αβγ,ρ1,2 : =αh(112h) h:=\alpha \beta \gamma, \quad \rho_{1,2}:=\frac{\alpha}{h}(1 \mp \sqrt{1-2 h})
und Mengen
Sρ1/2(x0) : ={xRn : xx0<ρ1/2}. S_{\rho_{1 / 2}}\left(x^{0}\right):=\left\{x \in \mathbb{R}^{n}:\left\|x-x^{0}\right\|<\rho_{1 / 2}\right\} .
Wenn h12 h \leq \frac{1}{2} und Sρ1(x0)D \overline{S_{\rho_{1}}\left(x^{0}\right)} \subset D gilt, dann existiert die Folge (xk)kN \left(x^{k}\right)_{k \in \mathbb{N}} aus dem Newton-Verfahren (alle Matrizen DF (xk) \left(x^{k}\right) sind regulär). Die Folge ist in Sρ1(x0) S_{\rho_{1}}\left(x^{0}\right) enthalten und konvergiert gegen eine Nullstelle von F F . Diese Nullstelle ist eindeutig in der Menge DSρ2(x0) 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 x^ \hat{x} eine Nullstelle von f : RR f: \mathbb{R} \rightarrow \mathbb{R} mit f(x)=1x3127 f(x) = \frac{1}{x^3} - \frac{1}{27} , und es gelte fC2(R) f \in C^2(\mathbb{R}) . Bezüglich der Maximumnorm sei

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

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

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

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

βr12 \beta r \leq \frac{1}{2}

mit

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

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

xk+1x^βxkx^212xkx^ \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 Φ(x)\Phi(x) und Ψ(x)\Psi(x) an der Stelle x^=3\hat{x}=3 (da x^=3\hat{x}=3 die eindeutige Lösung der Gleichung f(x)=0f(x) = 0 ist):

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

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

Setzen wir x=x^=3x=\hat{x}=3 ein:

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

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

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

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

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

Setzen wir x=x^=3x=\hat{x}=3 ein:

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

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






Ich glaube das ist richtig oder?

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

Wie sieht dein Ψ(x)\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 x^\hat x eingesetzt?

Ich habeden Startwert x0 = 2 eingesetzt

Ich komme auch auf

Ψ(x) = x - f(x)/f'(2) = x + 16/(3·x3) - 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.IMG_1202.PNG

IMG_1203.PNG

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

2 Antworten

0 Daumen
 
Beste Antwort

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)=43x181x4T(x)=\frac{4}{3}x-\frac{1}{81}x^4

Mit Ideen aus Deinen anderen Posts:

xk+13=T(xk)3=T(3)+T(3)(xk3)+12T(s)(xk3)2=12T(s)(xk3)2|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 xkx^k und 3. Mit der Vorgabe aus der Aufgabe lässt sich auf U abschätzen:

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

Also geht C=32/27C=32/27

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

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

Avatar von 14 k

Danke erstmal für deine Antwort

Woher hast du das? T(x)=43x181x4 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:

IMG_7209.jpeg


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!! :)

IMG_7211.jpeg

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

Das ist doch offenbar Quatsch

mit δ<1\delta<1 tritt offenbar ein, wennCδ<1, also δ<27/32C \delta<1, \text{ also }\delta<27/32

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

0 Daumen

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

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

Avatar von 11 k

Ehrlich gesagt keine Ahnung..

x^=3 \hat{x}=3

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

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

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

M=max{12x5 : x[2,4]}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=2x = 2: f(2)=1225=316|f''(2)| = \frac{12}{2^5} = \frac{3}{16}
2. Für x=4x = 4: f(4)=1245=3512|f''(4)| = \frac{12}{4^5} = \frac{3}{512}

M=316M = \frac{3}{16}.


β : =M1f(x^)=3161127=31627=8116 \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}

βr12 \beta r \leq \frac{1}{2}

8116r12 \frac{81}{16} \cdot r \leq \frac{1}{2}

r121681 r \leq \frac{1}{2} \cdot \frac{16}{81}

r881 r \leq \frac{8}{81}

K={xR : x3r} \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 K\cal K, mit seinem rr. Danach(!) kannst Du auch erst MM bestimmen. Passe entsprechend an und teile dann mit, ob der Satz schon das gewünschte liefert oder was noch nötig ist.

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

K : ={xR : x3r} \mathcal{K}:=\left\{x \in \mathbb{R}:\|x-3\| \leq r\right\}
ein kompaktes Intervall um 3, und M M sei definiert als
M : =max{12x5 : x[2,4]} M:=\max \left\{\left|\frac{12}{x^{5}}\right|: x \in [2,4]\right\} = 316 \frac{3}{16}
Wenn f(x^)0 f^{\prime}(\hat{x}) \neq 0 und
βr12 \beta r \leq \frac{1}{2} ==>r881 ==> r \leq \frac{8}{81}
mit
β : =M1f(x^) \beta:=M\left|\frac{1}{f^{\prime}(\hat{x})}\right| = 8116 \frac{81}{16}
gilt, dann existiert die Folge (xk)kN \left(x^{k}\right)_{k \in \mathbb{N}} definiert durch das Newton-Verfahren für beliebiges x0K x^{0} \in \mathcal{K} . Die Folge konvergiert gegen x^ \hat{x} und es gilt
xk+138116xk3212xk3 \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 K\cal K, mit seinem rr. Danach(!) kannst Du auch erst MM 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-ge…

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

xk+1=xkf(xk)f(xk) 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 : RR f: \mathbb{R} \rightarrow \mathbb{R} eine zweimal stetig differenzierbare Funktion mit einer eindeutigen Nullstelle x^ \hat{x} für die f(x^)0 f^{\prime}(\hat{x}) \neq 0 gilt. Die Iteration des gewöhnlichen Newton-Verfahrens lautet

xk+1=xkf(xk)f(xk) 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 : RR f: \mathbb{R} \rightarrow \mathbb{R} eine zweimal stetig differenzierbare Funktion mit einer eindeutigen Nullstelle x^ \hat{x} für die f(x^)0 f^{\prime}(\hat{x}) \neq 0 gilt. Die Iteration des gewöhnlichen Newton-Verfahrens lautetxk+1=xkf(xk)f(xk) 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-quadrati…

Ein anderes Problem?

Stell deine Frage