[Aufgabensammlung] Fragen & Antworten 3

Neue Frage »

07.07.2008, 16:29	tigerbine	Auf diesen Beitrag antworten »
[Aufgabensammlung] Fragen & Antworten 3 Hier gibt es eine weitere kleine Aufgabensammlung in "Frage & Antwort" Form. Themen Banachscher Fixpunktsatz (51, 52, 54, 56, 57, 58, 59, 62, 63) Newton-Verfahren (53, 56, 61) Mehrdimensionale Verfahren (55, 60)
07.07.2008, 16:33	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 51 - Banachscher Fixpunktsatz Definieren Sie eine geeignete Iterationsabbildung G zur Lösung des Systems: $\begin{eqnarray} x_1 + x_2 = 1 - 2 \cdot \varepsilon \cdot x_1^2 \end{eqnarray}$ $\begin{eqnarray} x_1 - x_2 = 1 - 2 \cdot \varepsilon \cdot x_2^2 \end{eqnarray}$ Zeigen Sie mit Hilfe des Banachschen Fixpunktsatzes die Existenz einer Lösung für hinreichend kleines $\begin{eqnarray} \varepsilon \end{eqnarray}$
07.07.2008, 16:47	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 51 Zunächst einmal nimmt man eine optische Überarbeitung durch umstellen vor. $\begin{eqnarray} I.~x_1 = 1 - 2 \cdot \varepsilon \cdot x_2^2 + x_2 \end{eqnarray}$ $\begin{eqnarray} II.~x_2 = 1 - 2 \cdot \varepsilon \cdot x_1^2 - x_1 \end{eqnarray}$ Dann setzt man II in I ein und erhält: $\begin{eqnarray} x_1 &&= 1 - 2 \cdot \varepsilon \cdot x_2^2 + 1 - 2 \cdot \varepsilon \cdot x_1^2 - x_1 \\&& = 2- 2 \cdot \varepsilon \cdot (x_1^2+x_2^2) - x_1 \end{eqnarray}$ $\begin{eqnarray} x_1= 1-\varepsilon\cdot (x_1^2+x_2^2) \end{eqnarray}$ Nun analog für I in II: $\begin{eqnarray} x_2 &&= 1 - 2 \cdot \varepsilon \cdot x_1^2 - 1 + 2 \cdot \varepsilon \cdot x_2^2 - x_2 \\&&= - 2\varepsilon \cdot (x_1^2-x_2^2) - x_2 \end{eqnarray}$ $\begin{eqnarray} x_2 = - \varepsilon(x_1^2-x_2^2) \end{eqnarray}$ Somit können wir eine Iterationsabbildung G wie folgt definieren: ...
07.07.2008, 17:17	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 52 - Banachscher Fixpunktsatz Gegeben sei die Folge: $\begin{eqnarray} x_0 = 4 \end{eqnarray}$ $\begin{eqnarray} x_{n+1} = \frac{1}{2} \cdot \bigl( x_n + \frac{4}{x_n}\bigr) \end{eqnarray}$ Zeigen Sie mit Hilfe des Banachschen Fixpunktsatztes, dass die Folge gegen 2 konvergiert.
07.07.2008, 17:18	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 52 Wir definieren uns die zugehörige Iterationsfunktion: $\begin{eqnarray} g(x):=\frac{1}{2}\cdot (x + \frac{4}{x}) \end{eqnarray}$ Da wir nun schon einen Startwert so wie den zu beweisenden Grenzwert haben, können wir die Betrachtung auf das Intervall X:=[2,4] einschränken. Dies ist sicher eine abschlossene Teilmenge des Banachraums IR. Nun betrachten wir die Ableitung: $\begin{eqnarray} g'(x) = \frac{1}{2}\cdot (1 - \frac{4}{x^2}) \end{eqnarray}$ Auf dem Intervall X ist die Ableitung offensichtlich nicht negativ, die Funktion g ist dort also *monton wachsend. Schauen wir uns die Randwerte der Funktion: $\begin{eqnarray} g(2) = 2,~g(4) = 2.5 \end{eqnarray}$ Damit gilt $\begin{eqnarray} f(X) \subset X \end{eqnarray}$ und es liegt eine Selbstabbildung* vor. Nun untersuchen wir die Ableitung noch etwas genauer. $\begin{eqnarray} g'(2) =0,~g'(4) = \frac{3}{8} \end{eqnarray}$ Für die Ableitung der Funktion g' gilt: $\begin{eqnarray} g''(x) = \frac{1}{2} \cdot \frac{4 \cdot 2}{x^3} = \frac{4}{x^3} \end{eqnarray}$ Diese diese Funktion ist auf X positiv, also ist auch die Ableitung monoton steigend und es gilt die Abschätzung: $\begin{eqnarray} \|g'(x)\| < 1~\forall ~x \in X \end{eqnarray}$ Somit ist g eine Kontraktion. Damit sind alle nötigen Voraussetzung erfüllt. D.h. die Folge konvergiert gegen den eindeutigen Fixpunkt von g, welcher innerhalb [2,4] liegen muss. Nun zeigen wir, dass F(2/2) dieser Fixpunkt ist. Wie oben schon erwähnt ist $\begin{eqnarray} g(2) = 2 \end{eqnarray}$ und damit folgt die Behauptung: $\begin{eqnarray} \lim_{n \to \infty}~x_n = 2 \end{eqnarray}$
07.07.2008, 17:18	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 53 - Newtonverfahren Die Funktion $\begin{eqnarray} \ln(x) \end{eqnarray}$ soll an der Stelle $\begin{eqnarray} x=a>0 \end{eqnarray}$ näherungsweise berechnet werden. Dazu soll das Newton Verfahren auf die Funktion $\begin{eqnarray} f(x)=e^x-a \end{eqnarray}$ angewandt werden. Geben sie die zugehörige Iterationsvorschrift an und zeigen Sie, dass quadratische Konvergenz vorliegt. Kann man sogar die Konvergenzordnung p=3 erwarten?
Anzeige

07.07.2008, 18:41	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 53 Zunächst einmal eine kurze Plausibilitätsprüfung und Informationssammlung: $\begin{eqnarray} f\bigl(\ln(a) \bigr) = e^{\ln(a)}-a = a-a=0 \end{eqnarray}$ $\begin{eqnarray} f'(x)=e^x > 0 \quad \forall x \in \mathbb R \end{eqnarray}$ $\begin{eqnarray} f'\bigl(\ln(a) \bigr) = e^{\ln(a)} = a \neq 0 \end{eqnarray}$ Nun machen wir den Ansatz der Iterationsfolge des Newtonverfahrens. Definitionsprobleme sind nicht zu erwarten. Ferner ist die Funktion f unendlich oft stetig differenzierbar und es handelt sich um eine einfache Nullstelle. $\begin{eqnarray} x_{n+1} &&= x_n - \frac{f(x_n)}{f'(x_n)} \\&&= x_n - \frac{e^{x_n} - a}{e^{x_n}} \\&& = x_n - 1 + \frac{a}{e^{x_n}} \end{eqnarray}$ Wir erhalten also die Iterationsfunktion (Fixpunktiteration) mit Fixpunkt x= ln(a) $\begin{eqnarray} g(x)=x - 1 + \frac{a}{e^x} \end{eqnarray}$ Dabei gilt dann: $\begin{eqnarray} g'(x)=1-\frac{a}{e^{x}} \end{eqnarray}$ $\begin{eqnarray} g'(x^)=0 \end{eqnarray}$ Somit liegt also mindestens quadratische Konvergenz vor. Geht es noch besser? Bestimmen wir die nächste Ableitung. $\begin{eqnarray} g''(x)=\frac{a}{e^{x}} \end{eqnarray}$ $\begin{eqnarray} g''(x^)=1 \neq 0 \end{eqnarray}$ Nein*, damit ist also keine Konvergenzordnung p>2 zu erwarten.
07.07.2008, 21:51	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 54 - Banachscher Fixpunktsatz Richtig oder falsch? Die Abbildung $\begin{eqnarray} x \to \ln(2+x^2) \end{eqnarray}$ erfüllt in IR die Voraussetzungen des Banachschen Fixpunktsatzes.
07.07.2008, 22:04	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 54 Gehen wir die Checkliste einmal durch. IR ist ein Banachraum, X=IR ist eine abgeschlossene Teilmenge davon und die Funktion ist surjektiv. Somit liegt eine Selbstabbildung vor. Ferner gilt für die Ableitung: $\begin{eqnarray} f'(x) = \frac{1}{2+x^2} \cdot 2x = \frac{2x}{x^2+2} \end{eqnarray}$ Diese ist betragsmäßig kleiner 1. Somit ist die Behauptung wahr
07.07.2008, 23:29	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 55 - Mehrdimensionales Newton-Verfahren & Kantorovich Führen Sie für das nichtlineare Gleichungssystem $\begin{eqnarray} F(X) = \begin{pmatrix} 2\sin(x_1) + \cos(x_2) - 1.1 \\ \cos(x_1) - 2\sin(x_2)-0.9 \end{pmatrix} = \begin{pmatrix}0 \\ 0 \end{pmatrix} \end{eqnarray}$ einen Schritt $\begin{eqnarray} Y \to Z \end{eqnarray}$ des Newtons-Verfahrens mit Startwert $\begin{eqnarray} Y=(0,0)^T \end{eqnarray}$ durch. Bestimmen Sie eine Lipschitz-Konstante c für F' bezüglich der Maximum-Norm und beweisen Sie die Konvergenz der Newton-Iteration mit dem Kantorovich-Kriterium
08.07.2008, 01:16	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 55 Zunächst bestimmt man die Jacobi-Matrix: $\begin{eqnarray} F'(X) = \begin{pmatrix} 2\cos(x_1) & -\sin(x_2) \\ -\sin(x_1) & -2\cos(x_2) \end{pmatrix} \end{eqnarray}$ Das Newton-Verfahren notiert sich im Mehrdimensionalen-Fall wie folgt: $\begin{eqnarray} x_{n+1} = x_n - (F'(x_n))^{-1} F(x_n) \end{eqnarray}$ Es ist nun $\begin{eqnarray} x_0 = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} F(x_0) = \begin{pmatrix} 1-1.1 \\ 1-0.9 \end{pmatrix}= \begin{pmatrix} -0.1 \\ 0.1 \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} F'(x_0) = \begin{pmatrix} 2 & 0 \\ 0 &-2 \end{pmatrix} \end{eqnarray}$ Aufgrund der einfachen Gestalt, kann die Inverse hier angegeben werden: $\begin{eqnarray} (F'(x_0))^{-1} = \begin{pmatrix} 0.5 & 0 \\ 0 & -0.5 \end{pmatrix} \end{eqnarray}$ Man erhält also im ersten Iterationsschritt: $\begin{eqnarray} x_1 &&= \begin{pmatrix} 0 \\ 0 \end{pmatrix} -\begin{pmatrix} 0.5 & 0 \\ 0 &-0.5 \end{pmatrix}\begin{pmatrix} -0.1 \\ 0.1 \end{pmatrix} \\&& =\begin{pmatrix} 0.05 \\ 0.05 \end{pmatrix} \end{eqnarray}$ Lipschitzstetigkeit der Ableitung $\begin{eqnarray} \\|F'(X) - F'(\hat{X})\\|_{\infty} \leq c \cdot\\|X - \hat{X}\\|_{\infty} \end{eqnarray}$ ... to be discussed...
08.07.2008, 16:31	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 56 - Fixpunktbestimmung & Nullstellenbestimmung Gegeben sei die Funktion $\begin{eqnarray} g(x)=\frac{1}{5} + \frac{1}{4}x^2+\frac{1}{3}x^3 \end{eqnarray}$ Zeigen Sie, dass g im Intervall [0,0.5] genau einen Fixpunkt x* besitzt und dass die Fixpunktiteration $\begin{eqnarray} x_{n+1}=g(x_n) \end{eqnarray}$ für jeden Startwert aus diesem Intervall gegen x* konvergiert. Wie viele Iterationsschritte des Verfahrens müssen ausgehend vom Startwert $\begin{eqnarray} x_0=0 \end{eqnarray}$ durchgeführt werden, um $\begin{eqnarray} \|x_n-x^\| \leq 10^{-4} \end{eqnarray}$ garantieren zu können? Formulieren Sie das Newton-Verfahren zur Berechnung einer Nullstelle von g und berechnen Sie ausgehend vom Startwert $\begin{eqnarray} x_0=-1 \end{eqnarray*}$ einen Newtonschritt.
08.07.2008, 16:55	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 56a Da wir die Möglichkeit haben, plotten wir die Funktion einmal. Da es sich um ein Polynom ungeraden Maximalgrades handelt, ist die Existenz einer reellen Nullstelle gesichert. Wir sehen, dass die Funktion 3 Fixpunkte besitzt, hier soll der Mittlere bestimmt werden. Wieder gilt es die Checkliste des Banachschen Fixpunktsatzes durchzugehen. Mit der Grundmenge IR haben wir einen Banachraum und das angegebene Intervall X:=[0,0.5] bildet eine abgeschlossene Teilmenge. Weiter ist $\begin{eqnarray} g(0) =0.2, \qquad g(0.5) =\frac{1}{5} + \frac{1}{16} + \frac{1}{24} = \frac{584}{1920} < \frac{1}{2} \end{eqnarray}$ $\begin{eqnarray} g'(x)=\frac{1}{2}x + x^2 \geq 0 ~\forall x \in [0,0.5] \end{eqnarray}$ und somit liegt eine Selbstabbildung vor. Schauen wir uns sie Ableitung noch etwas genauer an. Es handelt sich um eine nach oben geöffnete Parabel mit Scheitelpunkt bei x=-0.25. daher gilt $\begin{eqnarray} L:=\max_{x \in [0,0.5]}~\|g'(x)\|=\|g'(0.5)\| = 0.5 < 1 \end{eqnarray}$ und es handelt sich bei g um eine Kontraktion. Damit sind die Voraussetzungen des BSF erfüllt und die Behauptung folgt aus diesem Satz.
08.07.2008, 17:16	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 56b Hier benötigen wir die a-priori Fehlerabschätzung, sie lautet: $\begin{eqnarray} \|x_n-x^\| \leq \frac{L^n}{1-L} \cdot \|x_1-x_0\| \end{eqnarray}$ Nun berechnen wir mal ein paar Größen daraus. $\begin{eqnarray} L=0.5 \end{eqnarray}$ $\begin{eqnarray} x_0=0 \end{eqnarray}$ $\begin{eqnarray} x_1=g(x_0) = 0.2 \end{eqnarray}$ Und erhalten: $\begin{eqnarray} \|x_n-x^\| \leq \frac{(0.5)^n}{0.5} \cdot \|0.2\| =0.2 \cdot 0.5^{n-1} \end{eqnarray}$ Es ergibt sich dann also die Forderung an n: $\begin{eqnarray} 0.2 \cdot 0.5^{n-1} < 10^{-4} \end{eqnarray}$ $\begin{eqnarray} n > 11,97 \end{eqnarray}$ Also müssen n=12 Iterationsschritte durchgeführt werden.
08.07.2008, 17:32	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 56c Nun wollen wir eine Nullstelle von g bestimmen. Dazu schreiben wir einmal die Newton-Installationsvorschrift hin: $\begin{eqnarray} x_{x+1} &&=x_k - \frac{g(x_k)}{g'(x_k)} \\ &&= x_k - \frac{\frac{1}{5} + \frac{1}{4}x_k^2+\frac{1}{3}x_k^3}{\frac{1}{2}x_k + x_k^2} \end{eqnarray}$ Ein Konvergenzbeweis ist in der Aufgabe nicht gefordert, sondern nur die Berechnung eines Schrittes. Es ergibt sich: $\begin{eqnarray} x_1 = -1 - \frac{\frac{1}{5}+\frac{1}{4}-\frac{1}{3}}{\frac{1}{2}} = -\frac{37}{30} \end{eqnarray}$
08.07.2008, 17:39	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 57 - Fixpunktiteration Richtig oder falsch? Eine Fixpunktiteration mit einer kontrahierenden Abbildung konvergiert quadratisch.
08.07.2008, 18:02	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 57 Falsch! Also die Kontraktion ist eine Forderung im Banachschen Fixpunktsatz. Selbst wenn die anderen Bedingungen erfüllt sein sollten, sichert die Abschätzung nur die Lineare Konvergenz. So sollte man versuchen ein Gegenbeispiel zu konstruieren. $\begin{eqnarray} x_{k+1}:= \frac{1}{2}\cdot x_k \end{eqnarray}$ Die zugehörige Iterationsfunktion lautet: $\begin{eqnarray} h(x) = 0.5x \end{eqnarray}$ Der Fixpunkt liegt bei x=0. Somit können wir die Abschätzung vornehmen: $\begin{eqnarray} \|x_{k+1}-x^\|=\|0.5x_k-x^\| = \|0.5x_k\| = 0.5\|x_k-x^\| \end{eqnarray}$ Das Verfahren konvergiert also mindestens linear. Da es aber nicht superlinear konvergiert, konvergiert es auch nicht quadratisch. $\begin{eqnarray} \lim_{k \to \infty}~\frac{\|x_{k+1}-x^\|}{\|x_{k}-x^\|} = 0.5 \neq 0 \end{eqnarray}$
08.07.2008, 20:58	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 58 - Banachscher Fixpunktsatz Für welche der Intervalle $\begin{eqnarray} [1,2],~(1,3),~[2,\infty) \end{eqnarray}$ erfüllt die Abbildung $\begin{eqnarray} g(x)=2+\frac{1}{x^2} \end{eqnarray}$ die Voraussetzungen des BFS? Bestimmen Sie eine möglichst kleine Kontraktionskonstante, und geben Sie eine obere Schranke für die Anzahl der für eine Fehlerrreduktion um $\begin{eqnarray} 10^{-1} \end{eqnarray}$ benötigten Iterationen an.
08.07.2008, 21:26	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 58 Zunächst einmal sind alle Intervalle Teilmengen eines Banachraums. Nun muss geprüft werden, ob sie abgeschlossen sind. Kandidat 1 erhält ein klares ja, Kandidat 2 ein klares nein und Kandidat 3 wieder ein Ja. Nun schauen wir uns die Funktion g an, vielmehr ihr Steigunsverhalten. $\begin{eqnarray} g'(x) = -\frac{1}{x^3} \end{eqnarray}$ Auf den verbleibenden Intervallen ist die Funktion also streng monoton fallend. Zur Beantwortung der Frage nach der Selbstabbildung reicht es also die Intervallgrenzen zu überprüfen. $\begin{eqnarray} g(1) = 3,~g(2)=\frac{9}{4},~\lim_{x\to\infty}~g(x) = 2 \end{eqnarray}$ Somit scheidet an dieser Stelle Intervall 1 aus, nur bei 3 liegt eine Selbstabbildung vor. Bleibt die Frage nach der Kontraktion. die Ableitung ist auf dem Intervall eine streng monoton fallende Funktion, es gilt daher $\begin{eqnarray} \|g'(y)\| \leq \|g'(2)\| = 0.25 \end{eqnarray}$ Somit können wir über den Mittelwertsatz der Differentialrechnung die Kontraktionseigenschaft nachweisen, L=0.25. Nun soll der Anfangsfehler $\begin{eqnarray} \|x_0-x^\| \end{eqnarray}$ um $\begin{eqnarray} 10^{-1} \end{eqnarray}$ zu reduzieren, also $\begin{eqnarray} \|x_n-x^\| \leq 10^{-1} \cdot \|x_1-x^\| \end{eqnarray}$ Wie groß ist die Fehlerreduktion im ersten Schritt? $\begin{eqnarray} \|x_1-x^\| = \|g(x_0) - g(x^)\| \leq \frac{1}{4} \cdot \|x_0-x^\| \end{eqnarray}$ Induktiv folgt dann: $\begin{eqnarray} \|x_n-x^\| = \leq (\frac{1}{4})^n \cdot \|x_0-x^\| \end{eqnarray}$ Somit ergibt sich, dass zur gewünschten Fehlerreduktion höchstens 2 Schritte nötig sind.
08.07.2008, 22:46	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 59 - Banachscher Fixpunktsatz Beweisen Sie mit Hilfe des Banachschen Fixpunktsatzes die Konvergenz der Iteration $\begin{eqnarray} x_{k+1}=\sqrt[3]{8-x_k},~x_0=0 \end{eqnarray}$ Geben Sie eine Schranke für den Fehler von $\begin{eqnarray} x_k \end{eqnarray}$ an.
09.07.2008, 00:03	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 59 Die Iterationsfunktion $\begin{eqnarray} g(x)= \sqrt[3]{8-x} \end{eqnarray}$ ist für alle $\begin{eqnarray} x_ \in (\-\infty,8] \end{eqnarray}$ definiert. Es ist $\begin{eqnarray} g(0) = 2 \end{eqnarray}$ und $\begin{eqnarray} g(2)\approx 1.82 < 2 \end{eqnarray}$ , so dass man ja mal in dem Intervall X:=[0,2] ja mal auf einen Fixpunkt prüfen könnte. Schauen wir uns also noch die Ableitung an: $\begin{eqnarray} g'(x)= - \frac{1}{3(8-x)^{\frac{2}{3}}} <0 \end{eqnarray}$ Das bedeutet, die Funktion ist streng monoton fallend und g ist auf der abgeschlossenen Teilmenge X des Banachraums IR eine Selbstabbildung. Bleibt nur noch zu untersuchen: $\begin{eqnarray} g''(x)=-\frac{2}{9(8-x)^{\frac{5}{3}}} <0 \end{eqnarray}$ somit gilt auf X: $\begin{eqnarray} \|g'(x)\| \leq \|g'(2)\| = \underbrace{\frac{1}{3\cdot 6^{\frac{2}{3}}}}_{=:L} \approx 0.101 < 1 \end{eqnarray}$ Also ist die Funktion g dort auch eine Kontraktion. Die Voraussetzungen des BSF sind also erfüllt, die Iteration konvergiert gegen den eindeutigen Fixpunkt. Es gilt die a-priori Fehlerabschätzung $\begin{eqnarray} \|x_n-x^\| \leq \frac{L^n}{1-L} \cdot \|x_1-x_0\| \end{eqnarray}$ $\begin{eqnarray} x_0=0,~x_1=2 \end{eqnarray}$ $\begin{eqnarray} \|x_n-x^\| \leq \frac{2 \cdot L^n}{1-L} \approx 2,225 \cdot 0.101^n \end{eqnarray}$
09.07.2008, 01:32	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 60 - Mehrdimensionale Fixpunktbestimmung Zeigen Sie mit Hilfe des Banachschen Fixpunktsatzes, dass die Iteration $\begin{eqnarray} x_{k+1} = G(X_k) \end{eqnarray}$ $\begin{eqnarray} G(X)=\begin{pmatrix}10 + \ln(x_2) \\ 20 + \ln(x_2) \end{pmatrix} \end{eqnarray}$ mindestens einen Fixpunkt besitzt.
09.07.2008, 11:52	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 60 Mit dem IR² ist ein Banachraum gegeben. Nun suchen wir dort eine abgeschlossene Teilmenge, auf der G eine kontrahierende Selbstabbildung ist. Zunächst einmal schauen wir uns die Jacobi-Matrix an. $\begin{eqnarray} G'(X) = \begin{pmatrix} 0 & \frac{1}{x_2} \\ \frac{1}{x_1} & 0 \end{pmatrix} \end{eqnarray}$ Damit eine Kontraktion vorliegt muss bzgl. einer Norm gelten: $\begin{eqnarray} \\| G'(X) \\| < 1 \end{eqnarray}$ Wählt man die Maximumsnorm, so ist $\begin{eqnarray} \\| G'(X) \\|_{\infty} = \max\{\frac{1}{x_1},~\frac{1}{x_2}\} \end{eqnarray}$ Somit muss schon einmal gelten: $\begin{eqnarray} x_1, x_2 > 1 \end{eqnarray}$ Wählt man nun die abgeschlossene Teilmenge $\begin{eqnarray} \Omega := [10,~\infty) \times [10,~\infty) \end{eqnarray}$ so gilt: $\begin{eqnarray} G(\Omega) := [10 + \ln(10),~\infty) \times [20 + \ln(10),~\infty) \subset \Omega \end{eqnarray}$ und es liegt eine kontrahierende Selbstabbildung vor. Die Voraussetzung des BSF sind erfüllt und für jeden Startwert aus $\begin{eqnarray} \Omega \end{eqnarray}$ konvergiert G gegen den eindeutigen Fixpunkt.
09.07.2008, 11:55	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 61 - Newton-Verfahren Richtig oder Falsch? Für eine auf IR konvexe Funktion mir nur einer Nullstelle konvergiert das Newton-Verfahren für jeden Startwert.
09.07.2008, 11:59	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 61 Falsch! Eine konvexe Funktion muss nicht differenzierbar sein.
09.07.2008, 12:05	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 62 - Banachscher Fixpunktsatz Beweisen Sie die Konvergenz der Iteration $\begin{eqnarray} x_{k+1} = 1 + \arctan(x_k),~x_0=1 \end{eqnarray}$
09.07.2008, 12:30	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 62 Mit IR liegt ein Banachraum vor. Wir betrachten die Iterationsfunktion $\begin{eqnarray} g(x)=1+\arctan(x) \end{eqnarray}$ Diese ist auf ganz IR definiert und differenzierbar mit $\begin{eqnarray} g'(x)=\frac{1}{1+x^2} > 0 \end{eqnarray}$ und somit monoton wachsend. Wo ist die Funktion nun kontrahierend? $\begin{eqnarray} \frac{1}{1+x^2} < 1 \Leftrightarrow 0 < x^2 \end{eqnarray}$ $\begin{eqnarray} \hat{\Omega_1} =(0,\infty), \hat{\Omega_2} =(-\infty,0) \end{eqnarray}$ Nun muss die Teilmenge aber abgeschlossen sein und den Startwert enthalten. Daher wählt man $\begin{eqnarray} \Omega_1 =[1,\infty) \end{eqnarray}$ Ist die Funktion dort auch eine Selbstabbilung? Ja, denn $\begin{eqnarray} g(1)=1 + \arctan(1) = 1 + \frac{\pi}{4} > 1 \end{eqnarray}$ Nun geben wir noch eine Kontraktionskonstante an. Es gilt $\begin{eqnarray} \forall ~ x\in \Omega:~g'(x) = \frac{1}{1+x^2} < \frac{1}{2} \end{eqnarray}$ Alle Voraussetzungen des BSF sind erfüllt, die Iteration konvergiert.
09.07.2008, 12:32	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 63 - Fixpunktbestimmung Bestimmen Sie die Fixpunkte der Abbildung $\begin{eqnarray} g(x)=\frac{3}{2+x} \end{eqnarray}$ und untersuchen Sie, ob diese anziehend oder abstoßend sind. Für welche Intervalle $\begin{eqnarray} [\alpha,~2],~\alpha \geq 0 \end{eqnarray}$ sind die Voraussetzungen des Banachschen Fixpunktsatzes erfüllt und wie klein kann dafür die Kontraktionskonstante c gewählt werden?
09.07.2008, 12:41	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 63a Es gilt also die Lösungen der Gleichung $\begin{eqnarray} x=\frac{3}{2+x},~x \in \mathbb R \setminus\{-2\} \end{eqnarray}$ zu finden. Dies kann hier einfach auf eine quadratische Gleichung zurückgeführt werden. Die Lösungsformel liefert dann: $\begin{eqnarray} x^2+2x-3 = 0 \end{eqnarray}$ $\begin{eqnarray} \mathbb L = \{-3,1\} \end{eqnarray}$ Nun Berechnen wir die Ableitung der Iterationsfunktion g. $\begin{eqnarray} g'(x)=-\frac{3}{(2+x)^2} \end{eqnarray}$ Es gilt dann für die Fixpunkte: $\begin{eqnarray} \|g'(-3)\| =3 \Rightarrow~\text {abstoßend } \end{eqnarray}$ $\begin{eqnarray} \|g'(1)\| = \frac{1}{3} \Rightarrow~\text {anziehend } \end{eqnarray}$
09.07.2008, 22:52	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 63b Zunächst einmal liegt mit dem allgemeinen Intervall schon einmal eine abgeschlossene Teilmenge einesBanachraums vor. Als nächstes schauen wir, wo es sich um eine Selbstabbildung handelt. Dabei werfen wir nochmal einen Blick auf die in Teilaufgabe a bereits berechnete Ableitung. Daraus ersehen wir, dass die Funktion auf dem Intervall streng monoton fallend ist. Nun gilt wegen $\begin{eqnarray} \alpha \geq 0 \end{eqnarray}$ $\begin{eqnarray} g(\alpha) = \frac{3}{2+\alpha} < 2 \end{eqnarray}$ Nun sollten wir sicherstellen, dass gilt: $\begin{eqnarray} g(2) = \frac{3}{4} \stackrel{!} \geq \alpha \end{eqnarray}$ Bleibt als noch die Kontraktionseigenschaft zu prüfen. Auch die Ableitung ist auf dem Intervall streng monoton fallend ist, ergibt sich für die Kontraktionskonstante die Abschätzung: $\begin{eqnarray} c:=\|g'(\alpha)\| = \frac{3}{(2+\alpha)^2} \leq \frac{3}{4} < 1 \end{eqnarray}$ Somit erfüllen alle Intervalle der Form $\begin{eqnarray} [\alpha,2],~0 \leq \alpha \leq \frac{3}{4} \end{eqnarray}$ die Voraussetzungen des BSF mit der Kontraktionskonstenen $\begin{eqnarray} c= \frac{3}{(2+\alpha)^2} \end{eqnarray}$
01.12.2008, 20:05	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 64 - Fixpuntsatz von Banach Sei $\begin{eqnarray} a>0 \end{eqnarray}$ und $\begin{eqnarray} f(x)=\sin(2x)+a \end{eqnarray}$ , wobei a eine reelle Zahl ist. Zeige, dass für $\begin{eqnarray} a=2 \end{eqnarray}$ genau ein Fixpunkt existiert.
01.12.2008, 20:35	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 64 Original von Leopold (zum Thread) Die Berechnung des Fixpunktes könnte man mit dem Banachschen Fixpunktsatz vornehmen. Sie funktioniert allerdings nicht mit der originalen Funktion, da diese in der Nähe des Fixpunktes zu stark fällt. Aber mit einer kleinen Umformung kommt man hin: $\begin{eqnarray} 2 + \sin{(2x)} = x \ \ \Leftrightarrow \ \ \frac{1}{2} \left( 2 + \sin{(2x)} \right) = \frac{1}{2} \,x \ \ \Leftrightarrow \ \ 1 + \frac{1}{2} \, x + \frac{1}{2} \sin{(2x)} = x \end{eqnarray}$ Wir betrachten daher auf dem Intervall $\begin{eqnarray} I = \left[ \frac{\pi}{3} , \frac{2 \pi}{3} \right] \end{eqnarray}$ die Funktion $\begin{eqnarray} \varphi \end{eqnarray}$ mit $\begin{eqnarray} \varphi(x) = 1 + \frac{1}{2} \, x + \frac{1}{2} \sin{(2x)} \end{eqnarray}$ Im Innern von $\begin{eqnarray} I \end{eqnarray}$ gilt $\begin{eqnarray} \varphi'(x) = \frac{1}{2} + \cos{(2x)} < 0 \end{eqnarray}$ . Daher fällt $\begin{eqnarray} \varphi \end{eqnarray}$ streng monoton. Wegen $\begin{eqnarray} \varphi \left( \frac{\pi}{3} \right) = 1{,}95 \ldots < \frac{2 \pi}{3} \end{eqnarray}$ und $\begin{eqnarray} \varphi \left( \frac{2 \pi}{3} \right) = 1{,}61 \ldots > \frac{\pi}{3} \end{eqnarray}$ ist $\begin{eqnarray} \varphi \end{eqnarray}$ eine Selbstabbildung von $\begin{eqnarray} I \end{eqnarray}$ . Da $\begin{eqnarray} \left\| \varphi'(x) \right\| = - \frac{1}{2} - \cos{(2x)} \leq \frac{1}{2} < 1 \end{eqnarray}$ ist, sind alle Voraussetzungen des Banachschen Fixpunktsatzes erfüllt, und die Existenz genau eines Fixpunktes $\begin{eqnarray} \xi \in I \end{eqnarray}$ ist garantiert. Mit einem beliebigen Startwert $\begin{eqnarray} x_0 \in I \end{eqnarray}$ muß daher die Folge der $\begin{eqnarray} (x_n) \end{eqnarray}$ mit $\begin{eqnarray} x_{n+1} = \varphi \left( x_n \right) \, , \ \ n \geq 0 \end{eqnarray}$ gegen $\begin{eqnarray} \xi \end{eqnarray}$ konvergieren. Allerdings ist in dem konkreten Beispiel die Konvergenzgeschwindigkeit nicht gerade umwerfend. Ich wollte nur einmal zeigen, wie man den Fixpunktsatz, den man ja sonst meist in Funktionenräumen anwendet, auch im trivialen Fall des Banachraumes $\begin{eqnarray} \mathbb{R} \end{eqnarray}$ gebrauchen kann. [attach]5049[/attach]
01.12.2008, 20:55	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 65 Berechnen Sie mit einem geeigneten numerischen Rechnungsverfahren: $\begin{eqnarray} f(x) = cos(x) = x = g(x) \end{eqnarray}$ Wie viele Rechenschritte sind notwendig, damit der Approximationsfehler $\begin{eqnarray} E < 10^{-3} \end{eqnarray}$ ist?
01.12.2008, 20:57	tigerbine	Auf diesen Beitrag antworten »
Aufgabe 65 - Fixpunktsatz von Banach Berechnen Sie mit einem geeigneten numerischen Rechnungsverfahren: $\begin{eqnarray} f(x) = cos(x) = x = g(x) \end{eqnarray}$ Wie viele Rechenschritte sind notwendig, damit der Approximationsfehler $\begin{eqnarray} E < 10^{-3} \end{eqnarray}$ ist?
01.12.2008, 22:53	tigerbine	Auf diesen Beitrag antworten »
Lösung Aufgabe 65 Gesucht ist also der Fixpunkt der Funktion $\begin{eqnarray} f(x)=\cos(x) \end{eqnarray}$ Die Anzahl der Schritte kann man mit der a-priori Abschätzung des Banachschen Fixpunktsatzes bestimmen: $\begin{eqnarray} \text{a priori: } \|\|x_k-x^\|\| \leq \frac{\kappa^k}{1-\kappa}\cdot \|\|x^0-x^1\|\| \end{eqnarray}$ Überprüfen wir also zunächst dessen Anwendbarkeit: $\begin{eqnarray} \mathbb R \end{eqnarray}$ ist ein Banachraumraum. Es dürfte als bekannt vorausgesetzt werden, dass der Cosinus auf dem kompakten* Intervall $\begin{eqnarray} [0,\frac{1}{3}\pi] \end{eqnarray}$ streng monoton fallend ist. Ferner ist der Bildbereich dort $\begin{eqnarray} [0,5,1] \end{eqnarray}$ . Somit liegt auch eine Selbstabbildung vor. Es ist $\begin{eqnarray} -\sin(0)=0,~-\sin(\frac{1}{3}\pi)\approx -0.866 \end{eqnarray}$ , somit können wir schreiben: $\begin{eqnarray} \|\|f(x)-f(y)\|\| \leq 0.87 \cdot \|\|x-y\|\| \end{eqnarray}$ und auch die Kontraktion ist gezeigt. Die Fehlerabschätzung Die Rechenschritte für die geforderte Genauigkeit hängen natürlich vom Startwert ab. Schauen wir uns einmal den Plot an und vergleichen 2 Startwerte: $\begin{eqnarray} x^0=0,~x^1=f(x^0) = 1 \end{eqnarray}$ $\begin{eqnarray} 10^{-3} \leq \frac{0.87^k}{1-0.87}\cdot \|\|0-1\|\| \end{eqnarray}$ $\begin{eqnarray} k > 64 \end{eqnarray}$ $\begin{eqnarray} x^0=0.8,~x^1=f(x^0) = 0.7 \end{eqnarray}$ $\begin{eqnarray} 10^{-3} \leq \frac{0.87^k}{1-0.87}\cdot \|\|0.8-0.7\|\| \end{eqnarray}$ $\begin{eqnarray} k > 47 \end{eqnarray}$

Neue Frage »

Antworten »

[Aufgabensammlung] Fragen & Antworten 3

Verwandte Themen