Eine NICHT-strikt diag. dominante Matrix und Konvergenz...

[oren78]

hallo ihr lieben,

bekanntlich konvergieren sämtliche iterationsverfahren (die wir behandelt haben wie jacobi, Gauß Seidel und SOR)
"sicher" für eine strikt diag. dominante Matrix....aber gilt auch die umkehrung? also das eine NICHT-strikt diag. dominante Matrix
eben NICHT für die genannten verfahren konvergiert ???

den das widerum konnte ich mir nirgends herleiten

[MisterD123]

gilt ja auch nicht. spektralradius der iterationsmatrix ist konvergenzkriterium.

[oren78]

gilt ja auch nicht. spektralradius der iterationsmatrix ist konvergenzkriterium.

diagonaldominanz ist ebenso ein hinreichendes kriterium für die konvergenz !

außerdem redest du über die 2 norm (spektralradius) ABER zu zeigen ist ja das es MINDESTENS eine norm gibt (egal welche) die eben kleiner als 1 ist, deswegen ja auch die sache mit der strikten diagonal-dominanz (starkes zeilenkriterium = unendlichkeits-Norm)

also daher noch mal die frage, angenommen ich habe eine matrix die NICHT strikt diagonal-dominant ist, so können die iter. Verfahren TROTZDEM dafür konvergieren, sehe ich das richtig??

Beispiel für Nicht-Konvegenz:

\(A = \begin{pmatrix} 1 & 0.25 & 0.25 \\ 0.5 & 1 & -0.5 \\ 0 & 0 & 1 \end{pmatrix}\) da jetzt: \(\Vert A \Vert _\infty = max \lbrace0.5, 1, 0\rbrace = 1 \not< 1\) gilt hier also KEINE konvergenz für A !

[MisterD123]

im script steht, jede norm ist mindestens so groß wie der spektralradius - mit beweis drunter. Folglich konvergiert das verfahren genau dann nicht, wenn der spektralradius nicht kleiner 1 ist. Die Abkürzungen, von den eigenschaften der Gleichungsmatrix A auf eigenschaften der Iterationsmatrix M=(I-B^-1*A) zu schließen um den konvergenzbeweis abzukürzen kannst du nicht einfach umdrehen, die genauen gründe warum es so ist haben wir nicht mal behandelt, die abkürzungen sind uns als definitionen hingestellt. Ohne dass du die schlussfolgerungskette der hin-richtung kennst (von "A hat eigenschaft x" zu "dann konvergiert die iteration über M") kannst du auch keine rückschlüsse ziehen "die iteration über M konvergiert nicht" wenn "A hat eigenschaft y".

Spektralradius von M < 1 ist hinreichendes _und_ notwendiges kriterium. das einzige das wir kennen. (notwendig ist vielleicht sogar nur <=1, weiß ich nicht, aber ist auch egal)

ach und was mir grade noch einfällt: du hast selber gesagt, es muss _eine_ norm geben die kleiner eins ist. Wenn du in einer norm nicht kleiner eins bist heißt das nicht, dass keine andere norm das erfüllt, die aussage hilft dir also garnichts.

[oren78]

also ich bin jetzt irgendwie total verwirrt, (eigentlich hab ich angenommen, ich wäre in diesen themengebiet recht fit...)
dieses merkwürdige skript besagt also folgendes... (seite: 27)


Um die Konvergenzeigenschaften des Verfahrens (3.3) zu untersuchen, ist der Spektralradius der Iterationsmatrix \(I - (B^-^1)A\) entscheidend.

Satz 3.2.3 i) Das Verfahren (3.3) ist genau dann konvergent, wenn gilt: \(p(I - (B^-^1)A) < 1\)

Das Verfahren (3.3) ist insbesondere konvergent, wenn mit einer induzierten Matrixnorm \(\Vert \cdot \Vert\) gilt:\(I - (B^-^1)A < 1\)


Satz 3.2.5
----------------------------------------------------------------------------------------------------------------------------------------------------
i) (Starkes Zeilensummenkriterium). Das Jacobi-Verfahren ist konvergent, wenn A strikt diagonaldominant ist.
ii) (Starkes Spaltensummenkriterium). Das Jacobi-Verfahren ist konvergent, wenn A^T strikt diagonaldominant ist.
iii) Ist A strikt diagonaldominant, dann ist auch das Gauß-Seidel-Verfahren und das SOR-Verfahren für 0 < w <= 1 konvergent.
----------------------------------------------------------------------------------------------------------------------------------------------------

Heißt das also jetzt das, wenn A gegeben ist, ich ALSO NICHT erst die Iterationsmatrizen berechnen muß sondern DIREKT A auf strikte diag.dominanz untersuchen und dann entscheiden kann, ob sie jetzt konvergiert? Den genau das ist, was in der musterlösung H8 a) geschieht...

falls A eben NICHT strikt diag.dominant ist, was muss ich also noch zeigen um die konvergenz für die verfahren zu bestimmen...? reicht es hier einfach IRGENDEINE norm in betracht zu ziehen? den es gilt ja, es muss mindestens eine norm existieren das kleiner als 1 ist...

falls jetzt weder A noch eine Norm kleiner als 1 ist, kann ich dann endlich behaupten das die verfahren NICHT dafür konvergieren?

[Edoat]

Heißt das also jetzt das, wenn A gegeben ist, ich ALSO NICHT erst die Iterationsmatrizen berechnen muß sondern DIREKT A auf strikte diag.dominanz untersuchen [...] kann

Ja, du musst halt weitere Untersuchungen durchführen, wenn sie nicht strikt diagonaldominant oder irreduzibel-diagonaldominant oder irreduzible M-Matrix ist (je nach dem was du gerade brauchst).

falls A eben NICHT strikt diag.dominant ist, was muss ich also noch zeigen um die konvergenz für die verfahren zu bestimmen...? reicht es hier einfach IRGENDEINE norm in betracht zu ziehen? den es gilt ja, es muss mindestens eine norm existieren das kleiner als 1 ist...

Die Norm muss auf die Iterationsmatrix angewendet werden. Wenn die Norm der Iterationsmatrix >= 1 ist, hast du keine Information gewonnen. Ist sie < 1, weißt du dass das Verfahren konvergiert.

falls jetzt weder A noch eine Norm kleiner als 1 ist, kann ich dann endlich behaupten das die verfahren NICHT dafür konvergieren?

Wenn keines der Kriterien für A passt und keine Norm der Iterationsmatrix kleiner als 1 ist, konvergiert das Verfahren nicht. Da du aber nicht alle Normen, die es gibt, durchprobieren kannst, musst du zeigen, dass der Spektralradius der Iterationsmatrix >= 1 ist.

[marlic]

\(\rho \le 1\) reicht übrigens nicht.

a) Für den Fall \(\rho = 1\) würde der Satz mit echt kleiner ja sogar sagen, dass es nicht konvergieren kann, wäre also ein komplett anderer Satz und nicht bloß ne Erweiterung.

b) Würde dann z.B. \(x_{k+1} = E x_k + B^{-1} b = x_0 + k*B^{-1}b\) konvergieren, was ja ziemlicher Quatsch ist, falls b != 0.

[SebFreutel]

Also ich hab mir während ner Vorlesung neben Satz 3.2.3 i) (der über den Spektralradius) geschrieben: "> 1 ―⁄→ ¬konvergent"
(und wenn ich mir mal was aufschreibe, muss der Prof das ziemlich deutlich gesagt haben )

[oren78]

Also ich hab mir während ner Vorlesung neben Satz 3.2.3 i) (der über den Spektralradius) geschrieben: "> 1 ―⁄→ ¬konvergent"
(und wenn ich mir mal was aufschreibe, muss der Prof das ziemlich deutlich gesagt haben )

danke sebastian, gute info...die LEIDER NICHT im skript steht...aber ich schreib mir das auf jeden fall auf mein zettel

[aldara]

Ich versuche mal, die Verwirrung zu vervollständigen, die wohl daher stammt, dass der Satz nicht mathematisch korrekt im Skript steht:

Ob ein Iterationsverfahren konvergiert hängt in erster Linie vom Startvektor ab. Setzt man z.B. das Ergebnis als Startvektor in das Verfahren ein konvergiert es natürlich - ganz unabhänig von der Iterationsmatrix. Es gibt also für jedes dieser Verfahren Startvektoren, für die es konvergiert. Das interessante ist aber, ob die Konvergenz für jeden Startvekor sichergestellt werden kann.

Nun zum Satz: die korrekte Version dafür lautet in etwa so:
"i) Das Verfahren (3.3) konvergiert für jeden Startvektor genau dann wenn Spektralradius < 1"

Ist der Radius also >= 1 heißt das nur, dass es (mind.) einen Startvektor gibt, für den das Verfahren nicht konvergiert.

[SebFreutel]

Stimmt, so macht das Sinn.

Da sieht man mal wieder schön den Unterschied zwischen Aussagen- und Quantorenlogik...