Jacobi-/Gauß-Seidel Verfahren < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:29 Di 04.08.2009 | | Autor: | tynia |
| Aufgabe | Gegeben sei ein lineares Gleichungssystem Ax = b. Zeigen Sie:
A= [mm] \begin{matrix}
2 & 1 & 4 \\
1 & 2 & -4 \\
4 & 4 & 1
\end{matrix}
[/mm]
konvergiert das Gesamtschrittverfahren und nicht das
Einzelschrittverfahren. |
Hallo. kann mir jemand sagen, woher ich weiß, dass ich den Spektralradius bestimmen muss? ich habe das nämlich so gemacht, dass ich die Jacobi- und Gauß-SeidelMatrix bestimmt habe und dann [mm] ||M||_{\infty} [/mm] bestimmt habe. Wenn dann ein Wert unter 1 rauskommt, konvergiert das Verfahren? Oder sagt mir das nur, welches Verfahren schneller konvergiert? ich versteh das nicht so ganz
Bei mir kam aber bei beiden Verfahren ein Wert über 1 raus. Ich wüsste nur einfach gerne, wann ich was machen muss.
Danke schonmal.
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:21 Mi 05.08.2009 | | Autor: | Andrey |
> ich habe das nämlich so
> gemacht, dass ich die Jacobi- und Gauß-SeidelMatrix
> bestimmt habe
Okay, ich bezeichne diese Matrix im Folgenden einfach als T
> und dann [mm]||M||_{\infty}[/mm] bestimmt habe. Wenn
> dann ein Wert unter 1 rauskommt, konvergiert das Verfahren?
Ja, wenn da für irgendeine mit einer Vektornorm verträglichen Matrixnorm etwas <1 rauskommt, dann hat garantiert kein Startvert irgendeine chance in irgendeine richtung "abzuhauen", das Verfahren konvergiert nach dem Banach'schen Fixpunktsatz. Wenn da aber etwas >= 1 rauskommt, sagt das bei der [mm] $||\cdot||_\infty$-Norm [/mm] leider erstmal gar nichts.
Betrachte dazu folgendes kleines Beispiel:
Sei einfachheitshalber $b=0$ und [mm] $T=\pmat{0.1 & 2\\0 & 0.1}$.
[/mm]
Was ist die Zeilensummennorm von T? Offenbar 2.1, jedenfalls irgendwas wesentlich größer 1.
Heißt es jetzt, dass es irgendein x gibt, für das die Iteration [mm] $x^{k+1}=Tx$ [/mm] nicht konvergiert? Nein.
Es ist ja:
[mm] $Tx=\vektor{0.1\\0}x_1+\vektor{2 \\ 0.1}x_2$
[/mm]
Die zweite Komponente wird zwar anfangs sehr stark gestreckt, aber dafür landet [mm] $\vektor{2,0.1}x_2$ [/mm] nach einer Iteration fast auf der [mm] x_1-Achse. [/mm] Das heißt dieser furchtbar stark gestreckter Vektor wird so verdreht, dass er fast in einem Unterraum landet, der bei jeder nächster Iteration um Faktor 0.1 kontrahiert. Das heißt, die Spuren der starken Streckung bei der ersten Iteration werden bereits nach der zweiten Iteration im [mm] x_1-Unterraum [/mm] plattgemacht, und alles konvergiert letztendlich gegen 0, obwohl der Fehler bei der erster Iteration mindestens verdoppelt wurde.
Dass alles "früher oder später" gegen 0 konvergiert, sieht man erst am Spektralradius, dieser ist nämlich 0.1<1.
Dem $T$ sieht man eben nicht an, dass es eine Kontraktion ist, wenn man nur die Zeilensummenorm anguggt.
Man kann sich aber mit der Jordan'schen Normalform alles so zurechttransformieren, dass man eine mit Vektornorm verträgliche Matrixnorm erhält, die beliebig nah am Spektralradius ist. Ist der Spektralradius kleiner 1, so schnappt man sich so eine passende Norm, sodass $||T||<1$ gilt, und freut sich, dass nach dem Banch'schen Fixpunktsatz wieder alles konvergiert.
Ist der Spektralradius aber >=1, so kann man schnell aus dem dazugehörigen Eigenvektor einen Startwert basteln, für den das Verfahren garantiert nicht konvergiert. Das heißt der Spektralradius ist gewissermaßen der endgültige Richter über konvergenz oder nicht konvergenz.
Der ist halt bisschen schwer zu berechnen... Daher greift man gerne auf einfachere Normen zurück, die man schnell ausrechnen kann: wenn man glück hat, und mit einer einfachen Norm etwas <1 rausbekommt, dann reicht's ja schon.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:12 Mi 05.08.2009 | | Autor: | tynia |
Ich danke dir.
|
|
|
|
