Jacobi-Verfahren, Numerik.

Question

Es sei jetzt

A = $$\begin{matrix} 4 & -1 & -1 \\ -1 & 3 & -1 \\ -1 & -1 & 3 \end{matrix}$$  , b = $$\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}$$

Geben Sie (mit Begründung) an, wieviele Iterationen beim Jacobi-Verfahren in diesem Fall garantiert ausreichen, um den absoluten Fehler des Startvektors x⁽⁰⁾ bezüglich einer Norm ihrer Wahl zu halbieren.

LG

Comments

Schau mal in deinen Unterlagen nach einer Fehlerabschätzung. Falls du keine findest, schau dir mal deine Fixpunktgleichung an und versuche eine Fehlerabschätzung zum Fixpunktsatz von Banach zu nutzen.

---

Ich habe gar keine Ahnung, wie ich bei dieser Aufgabe vorgehen soll. Kann mir keiner helfen?

---

Wie gesagt, Fehlerabschätzung nutzen. Schau in deinen Unterlagen danach. Falls dazu Fragen sind, stell sie hier. Eigentlich musst du einfach nur in die Abschätzung einsetzen und dann die Anzahl \(n\) der Iterationsschritte so wählen, dass der Fehler kleiner oder gleich \( \frac{1}{2} \) ist.

---

Welche Abschätzung meinst du denn? Die a priori oder a posteriori Abschätzung?

A priori Abschätzung:

| x_n - x* | ≤ (Lⁿ / 1 - L) * | x₁ - x₀ |

Muss ich bei dem L die Matrix A einsetzten?

Ich hab wirklich gar keine Ahnung.

---

Als erstes schreibst du mal die Fixpunktgleichung auf, die du beim Jacobi-Verfahren kriegst. Danach machen wir dann Schritt für Schritt weiter, ok? Du wirst dann sehen, dass für L nicht die Matrix eingesetzt wird, denn L ist die Kontraktionskonstante.

---

x = -D^-1 * (L+U)*x + D^-1 * b

Die hier oder?

---

Joa, auf der linken Seite würde ich \( x_{k+1}\) und auf der rechten \(x_{k} \) schreiben.

Jetzt musst du noch D,L,U im Zusammenhang mit deiner Aufgabe aufschreiben. Die sogenannte Iterationsmatrix ist in dem Fall \( D^{-1} (D-A) \).

---

Ok.

D=$$4\quad 0\quad 0\\ 0\quad 3\quad 0\quad \\ 0\quad 0\quad 3$$

D^-1=$$1/4\quad 0\quad 0\\ 0\quad 1/3\quad 0\quad \\ 0\quad 0\quad 1/3$$

L=$$0\quad 0\quad 0\\ -1\quad 0\quad 0\quad \\ -1\quad -1\quad 0$$

R=$$0\quad 0\quad 0\\ -1\quad 0\quad 0\quad \\ -1\quad -1\quad 0$$

Was mache ich nachdem ich alles eingesetzt habe? Ich kann doch nicht x_k+1 berechnen, da kein x_k vorhanden ist.

---

[...] Fall garantiert ausreichen, um den absoluten Fehler des Startvektors x⁽⁰⁾ [...]

Diesen Vektor setzt du ein und berechnest \( x_1 \). Dann berechnest du den Spektralradius \( \rho \) der Matrix \(A\) und hast dann deine Fehlerabschätzung

$$ \| x_n - x^* \| \leqslant \frac{\rho^n}{1-\rho} \|x_1 - x_0\|. $$

Die rechte Seite setzt du \( = \frac{1}{2} \) und löst dann nach \(n\) auf.

Übrigens ist dein \(L\) oder dein \(R\) (je nach Notation) falsch.

Answer 1

Hi,
wie schon vorher beschrieben ist die Lösung des Gleichungssystems \( Ax = b \) äquivalent zu dem Fixpunktproblem
$$  x = (I - D^{-1}A)x + D^{-1}b $$ wobei \( D \) eine Diagonalmatrix ist die auf der Diagonalen die Diagonalelementen der Matrix \( A \) stehen hat.
Die Iterationsgleichung sieht dann so aus
$$ (1) \quad x^{(k+1)} = (I-D^{-1}A) x^{(k)} + D^{-1}b  $$
Gleichung (1) hat nach dem Banaschen Fixpunktsatz eine eindeutige Lösung, falls \( \| I - D^{-1}A \| < 1 \) gilt. Dazu berechnet man den größten Eigenwerte \( \rho \) von \( I - D^{-1}A  \).

Ist \( \rho < 1 \) gilt auch \( \| I - D^{-1}A \| < 1 \)

Nach dem Banaschen Fixpunktsatz gilt folgende Abschätzung
$$ (2) \quad \left\| x^{(n)} - x \right\| \le \frac{\lambda^n}{1-\lambda} \left\| x^{(1)} - x^{(0)} \right\| $$
mit \( \lambda = \| I - D^{-1}A \| \)

es gilt \(  \left\| x^{(1)} - x^{(0)} \right\| = \left\| -D^{-1}A \left( x^{(0)} - x  \right) \right\| \le \left\|D^{-1}A \right\| \left\|x^{(0)} - x \right\| \) wobei \( x \) die Lösung von \( Ax = b \) ist.

Damit ergibt sich aus (2)
$$ (3) \quad \left\| x^{(n)} - x \right\| \le \frac{\lambda^n}{1-\lambda} \left\| D^{-1}A \right\| \left\|x^{(0)} - x \right\|  $$
Da der Anfangsfehler halbiert werden soll muss folgende Ungleichung für \( n \) gelten
$$ (4) \quad  \frac{\lambda^n}{1-\lambda} \left\| D^{-1}A \right\| \left\|x^{(0)} - x \right\| \le \frac{1}{2} \left\|x^{(0)} - x \right\| $$
Aus (4) folgt
$$ n = \left\lceil \frac{ ln\left( \frac{ \frac{1}{2} (1-\lambda) }{ \|D^{-1}A \| } \right) }{ln(\lambda)} \right\rceil $$
In diesem Fall ergibt sich n der Wert \( n = 5 \) falls man die \( \| \cdot \|_2 \) benutzt.