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

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

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

Beitrag von 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 :-(
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

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

Beitrag von MisterD123 »

gilt ja auch nicht. spektralradius der iterationsmatrix ist konvergenzkriterium.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

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

Beitrag von oren78 »

MisterD123 hat geschrieben: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 !
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

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

Beitrag von 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.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

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

Beitrag von 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?
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

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

Beitrag von Edoat »

oren78 hat geschrieben: 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).
oren78 hat geschrieben: 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.
oren78 hat geschrieben: 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.

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

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

Beitrag von 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.
"Copy & Passed"

Wahlspruch der Plagiatoren

SebFreutel
Computerversteher
Computerversteher
Beiträge: 317
Registriert: 30. Okt 2006 21:54

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

Beitrag von 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 :D )

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

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

Beitrag von oren78 »

SebFreutel hat geschrieben: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 :D )
danke sebastian, gute info...die LEIDER NICHT im skript steht...aber ich schreib mir das auf jeden fall auf mein zettel ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

aldara
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 17. Sep 2007 12:16

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

Beitrag von 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
Computerversteher
Computerversteher
Beiträge: 317
Registriert: 30. Okt 2006 21:54

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

Beitrag von SebFreutel »

Stimmt, so macht das Sinn.

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

Antworten

Zurück zu „Archiv“