0 Daumen
769 Aufrufe

Aufgabe

Screenshot 2022-10-31 163837.png

Text erkannt:

Man betrachte die nachfolgend gegebene Iterationsvorschrift
\( x^{(k+1)}=\left(\begin{array}{ccc} 0 & -\frac{1}{2} & -\frac{1}{4} \\ -\frac{1}{2} & 0 & 0 \\ 0 & -\frac{1}{2} & 0 \end{array}\right) x^{(k)}+\left(\begin{array}{c} \frac{3}{4} \\ -2 \\ -\frac{1}{2} \end{array}\right) \)
für \( k \geq 0 \) und mit
\( x^{(k)}=\left(\begin{array}{c} x_{1}^{(k)} \\ x_{2}^{(k)} \\ x_{3}^{(k)} \end{array}\right) . \)


Problem/Ansatz:

Hier soll der Fixpunkt der Iterationsvorschrift mithilfe des Banch'schen Fixpunktsatzes bewiesen und ermittelt werden. Leider ist mir nicht klar, wie das bei dieser Iterationsvorschrift funktioniert, da man dazu nicht mal etwas im Skript findet :/

Zudem soll abgeschätzt werden, nach wie vielen Iterationen eine Genauigkeit von 10^-14 vorliegt, sowie die Konvergenzordnung.

Ich habe leider keine Ansätze, nur durch die geforderte Umsetzung in MatLab ist der Fixpunkt (2; 1; -3) bekannt

Avatar von

Wie habt Ihr denn den Banach Fixpunktdatz formuliert? Habt Ihr über den Fall einer affinen Abbildung gesprochen? Ist der Vegriff Matrxnorm bekannt....

Über Vieles wurde kaum gesprochen, zudem ist die Numerik-Veranstaltung für zwei Zielgruppen ausgelegt (Informatiker <6KP>, wie ich selbst und Mathematiker <9KP>). Das Skript ist ein Folienskript und häufig werden reine Mathematik-Module vorausgesetzt, die man als B.Sc. Inf. gar nicht belegt.

Affine Abbildungen wurden nicht behandelt.

Banach ist wie folgt definiert

blob.png

Text erkannt:

Satz 1.13 (Banachscher Fixpunktsatz)
Sei \( \mathcal{M} \subset \mathbb{R}^{N} \) eine abgeschlossene Teilmenge, und die Abbildung \( \Phi: \mathcal{M} \rightarrow \mathcal{M} \) bezüglich einer Vektornorm \( \|\cdot\|: \mathbb{R}^{N} \rightarrow \mathbb{R} \) eine Kontraktion, d.h. für ein \( 0<L<1 \) gilt
\( \|\Phi(x)-\Phi(y)\| \leq L\|x-y\|, \quad \forall x, y \in \mathcal{M} . \)
Dann gilt folgendes:
(a) \( \Phi \) besitzt genau einen Fixpunkt \( x^{*} \in \mathcal{M} \);
(b) Für jeden Startwert \( x^{(0)} \in \mathcal{M} \) liefert die Fixpunktiteration (1.5) eine gegen \( x^{*} \) konvergierende Folge und es gilt
\( \left\|x^{*}-x^{(n)}\right\| \leq \frac{L}{1-L}\left\|x^{(n)}-x^{(n-1)}\right\| \leq \frac{L^{n}}{1-L}\left\|x^{(1)}-x^{(0)}\right\| . \)

Matrixnormen wurden erst teilweise behandelt.

Ok, wir nehmen für M den ganzen R^3.

Wie ist dann Phi(x) definiert? .Was ist die Differenz Phi(y)-Phi(x)?

Allerdings komme ich nicht mit dem von Dir angegebenen Fixpunkt klar. Müsste dann nicht die 2. Zeile lauten:

1=-0.5*2-2?

Da ich gerade versuche Iterationen in GeoGebra zu bauen, kommt mir das Beispiel gerade recht und komme ich mit einer Folge von 15 Schritten auf

            \(\scriptsize \left(\begin{array}{r}0\\0\\0\\\end{array}\right), \left(\begin{array}{r}0.75\\-2\\-0.5\\\end{array}\right), \left(\begin{array}{r}1.875\\-2.375\\0.5\\\end{array}\right), \left(\begin{array}{r}1.8125\\-2.9375\\0.6875\\\end{array}\right), \left(\begin{array}{r}2.04688\\-2.90625\\0.96875\\\end{array}\right),\)

\(\scriptsize \left(\begin{array}{r}1.96094\\-3.02344\\0.95313\\\end{array}\right), \left(\begin{array}{r}2.02344\\-2.98047\\1.01172\\\end{array}\right), \left(\begin{array}{r}1.9873\\-3.01172\\0.99023\\\end{array}\right), \left(\begin{array}{r}2.0083\\-2.99365\\1.00586\\\end{array}\right), \left(\begin{array}{r}1.99536\\-3.00415\\0.99683\\\end{array}\right),\)

\(\scriptsize \left(\begin{array}{r}2.00287\\-2.99768\\1.00208\\\end{array}\right), \left(\begin{array}{r}1.99832\\-3.00143\\0.99884\\\end{array}\right), \left(\begin{array}{r}2.00101\\-2.99916\\1.00072\\\end{array}\right), \left(\begin{array}{r}1.9994\\-3.0005\\0.99958\\\end{array}\right), \left(\begin{array}{r}2.00036\\-2.9997\\1.00025\\\end{array}\right) \)

das würde jetzt der MatLab-Aussage entgegen stehen?

Das liegt daran, dass bei der Implementierung explizit gefordert wurde, dass x^(0) = (1; 1; 1) ist, daher die anderen Werte, oder ich hab' mich einfach vertippt

Implementieren Sie die Fixpunktiteration (3) mit dem Startwert

\( x^{(0)}=\left(\begin{array}{l} 1 \\ 1 \\ 1 \end{array}\right) . \)
und erstellen Sie einen Konvergenzplot. Bestimmen Sie numerisch die Konvergenzordnung. Entspricht die Iterationszahl für eine vorgegebene Genauigkeit Ihren Erwartungen aus (d)?

OK, danke - dann stimmte meine Iteration, der Start bei (1,1,1) ändert nur ein paar Nachkommastellen

- kommt nach k=0..14 Schritten zu {{2.001163482666}, {-2.9990234375}, {1.000820159912}}...

Interessant! ullim kommt auf denselben Vektor wie ich..

Wenn DU genau hin schaust, dann siehst Du, daß Ullim meine Werte berechnet hat, oder?

x0 → 2

x1 → -3

x2 → 1

Stimmt! Bin heute wohl ein wenig blind

1 Antwort

0 Daumen
 
Beste Antwort

Im Prinzip soll ja hier die Aufgabe $$ x = Ax + b $$ mit \( A=\begin{pmatrix} 0 & -\frac{1}{2} & -\frac{1}{4} \\ -\frac{1}{2} & 0 & 0 \\ 0 & -\frac{1}{2} & 0 \end{pmatrix} \) und   \( b=\begin{pmatrix} \frac{3}{4} \\ -2 \\ -\frac{1}{2} \end{pmatrix} \)  gelöst werden.

Die Lösung ist $$  x = -(A-I)^{-1} b = \begin{pmatrix} 2 \\ -3 \\ 1 \end{pmatrix} $$

Für die Iteration muss ein Startvektor gewählt werden, z.B. \( x_0 = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \)

Dann ergibt sich \( x_1 \) zu

$$ x_1 = A x_0 + b =  \begin{pmatrix} 0 \\ -\frac{5}{2} \\ -1 \end{pmatrix} $$

Das muss jetzt iterativ weiter geführt werden. Das sieht dann z.B. so aus

blob.png

Wie man sieht konvergiert die Iteration gegen die richtige Lösung.

Um die Anzahl der Iterationen anzuschätzen gilt ja die Formel

$$ \| \tilde x - x_n \| \le \frac{L^n}{1-L} \| x_1 - x_0 \|| $$ wenn \( \tilde x \) die exakte Lösung ist. Und das soll kleiner \( \varepsilon = 10^{-14} \) sein.

Daraus folgt $$ n \ge \frac{ \ln \left( \frac{ 1-L }{ \| x_1 - x_0 \| } \varepsilon \right) } { \ln(L) } $$

wobei \( L \) die Lipschitzkonstante ist. Die Lipschitzkonstante ist hier die Matrixnorm.

Somit ist die Schätzung für die Anzahl der Iterationen vom Startvektor und von der Wahl der Matrixnorm abhängig.

Ich habe die Frobeniusnorm gewählt undkomme damit auf \( n \ge 346 \) Für z.B. die Zeilensummennorm bekommt man \( n \ge 121 \).

Avatar von 39 k

Vielen Dank für deine Lösung bzgl. der Iterationsschritte: Der Ansatz wäre mir vermutlich nie eingefallen. Das Iterieren an sich kriege ich hin: Ich fürchte mich eher vor dem Beweisen der Existenz des Fixpunktes, bevor ich das Verfahren anwende.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community