Jacobi Verfahren

03.08.2007, 13:33

Chris2005

Jacobi Verfahren

Hallo,

kurze Frage: wieso konvergiert mir das Jacobi Verfahren zum iterativen Lösen linearer Gleichungssysteme nicht immer? ich mein, die herleitung ist ja eher einfach, aber wie kann ich den startvektor wählen, damit ich die konvergenz sicher stelle?

mfg chris

03.08.2007, 15:43

tigerbine

Auf diesen Beitrag antworten »

RE: Jacobi Verfahren
Welche Konvergenzsätze kennst du denn zu dem Verfahren? Generell ist nicht "verwunderlich", dass eine Konstruktive Methode nicht für alle Fälle funktionieren muss.

Mir fällt gerade nur ein Kriterium ein, dass die Matrix A "bewertet"(Diagonaldominanz) und auf dem Fixpunktsatz basiert. Erfüllt A die Bedingung, dann konvergiert das Verfahren für alle Startwerte.

03.08.2007, 16:48

Chris2005

Auf diesen Beitrag antworten »

interessant, diagonaldominanz.... muss ich mal googeln...

leider versteh ich den ersten satz nicht... was bedeutet "die konstruktive methode muss nicht für alle fälle funktionieren" ?

danke, mfg chris

03.08.2007, 16:59

tigerbine

Auf diesen Beitrag antworten »

Damit meinte ich "wie kommt man auf das Jacobi-Verfahren"?

Es wird ja nun erstmal "einfach" eine Iterationsvorschrift gegeben. Da kann man ja i.A. nicht erwarten, dass das Verfahren dann für jedes LGS und jeden Startwert gegen die Lösung x* des LGS (A sei regulär) konvergiert.

23.08.2007, 14:21

tigerbine

Auf diesen Beitrag antworten »

Hier mal der Satz

Zitat:

Für die Matrix A gelte (ebentuell nach Zeilen- Spaltenvertauschung)

$\begin{eqnarray*} \rho:=\max_{i=1,...,n}~\sum_{k=1 \atop k \neq i}^{n}| \frac{a_{ik}}{a_{ii}}|~<1 \end{eqnarray*}$

Eine andere Schreibweise des Kriteriums wäre:

$\begin{eqnarray*} \sum_{k=1 \atop k \neq i}^n~|a_{ik}| < |a_{ii}| \quad \forall~i=1,..,n \end{eqnarray*}$

D.h. die Matrix A ist strikt zeilendiagonal dominant.

Dann gilt:

Das lineare Gleichungssystem Ax=b ist regulär, also eindeutig lösbar.
Die vom GSV und ESV erzeugte folge $\begin{eqnarray*} x^{(k)} \end{eqnarray*}$ konvergiert für jeden Startpunkt $\begin{eqnarray*} x^{(0)} \end{eqnarray*}$ gegen die theoretische Lösung x.
Der Abstand eines Folgengliedes $\begin{eqnarray*} x^{(k)} \end{eqnarray*}$ von der Lösung x ist abschätzbar durch:

$\begin{eqnarray*} \max_{i=1,...,n}|x_i^{(k)}-x| \leq \frac{\rho^k}{1-\rho} \cdot \max_{i=1,...,n} | x_i^{(1)}-x_i^{(0)}| \end{eqnarray*}$

Eine Aussage ob GSV oder ESV schneller konvergiert, läßt sich im Allgemeinen nicht treffen. Die Verfahren konvergieren umso besser, je kleiner (mind. < 1) der Spektralradius der Iterationsmatrix M ist.

23.08.2007, 15:29

swerbe

Auf diesen Beitrag antworten »

...oder alternativ erstmal ein direktes Verfahren (Gauß, Cholesky, QR,...) ansetzen, um eine erste (i.d.R. schlechte) Näherungslösung zu erhalten und dann diese Näherungslösung als Startvektor für das entsprechende iterative Verfahren verwenden.

Ist halt nur eine Frage des Aufwandes Augenzwinkern

26.09.2007, 16:21

Chris2005

Auf diesen Beitrag antworten »

Noch eine Frage:

Um eine a-priori Abschätzung geben zu können, muss ich auf den Banachschen Fixpunktsatz zurückgreifen. Hab schon viel gegoogelt und recherchiert, aber wie berechne ich die Lipschitzkonstante L? ist diese von der verwendeten Norm unabhängig? Verwendet man standardmäßig die Unendlichkeitsnorm?

danke, mfg chris

Neue Frage »

Antworten »

Jacobi Verfahren

Verwandte Themen