Präkonditionierung

22.09.2009, 02:43

tigerbine

Präkonditionierung

Folgende Frage beschäftigt mich:

Anstatt des LGS Ax=b (i) soll das Präkonditionierte LGS PAx=Pb (ii) gelöst werden.

Wenn man nun auf diese Idee kommt, vor dem Hintergrund, dass die Kondition ein Verstärkungsfaktor des relativen Fehlers der Eingaben (A,b) ist, so muss ich doch von der Matrix PA aus (ii) erwarten können, dass sie eine kleine Kondition hat als A. Dann müßte ich doch wie folgt abschätzen (submultiplikative Matrixnorm)

$\begin{eqnarray*} \|PA\| \|(PA)^{-1}\| \leq \|A\|\|A^{-1}\| \cdot \|P\|\|P^{-1}\| \end{eqnarray*}$

Damit müßte man fordern, dass P die Kondition 1 hat, oder?

Ziemlich harte Forderung und ich sehe nicht, wie diese bei dem Jacobi Verfahren oder dem Gauß-Seidel-Verfahren allgemein zu erfüllen wäre. verwirrt

22.09.2009, 20:40

Mathespezialschüler

Auf diesen Beitrag antworten »

Hallo tigerbine.
Was du dort stehen hast, ist eine Ungleichung, die ja im Allgemeinen von Gleichheit weit entfernt sein kann. Sie ist von der Form $\begin{eqnarray*} a\leq bc \end{eqnarray*}$ , wobei du ja eigentlich $\begin{eqnarray*} a\leq b \end{eqnarray*}$ haben willst. Aber nur weil du weißt, dass $\begin{eqnarray*} a\leq bc \end{eqnarray*}$ ist und $\begin{eqnarray*} c \end{eqnarray*}$ nicht kleiner als Eins werden kann, heißt das ja lange noch nicht, dass nicht trotzdem $\begin{eqnarray*} a\leq b \end{eqnarray*}$ gelten kann. Oder anders: Aus den Ungleichungen $\begin{eqnarray*} a\leq bc \end{eqnarray*}$ und $\begin{eqnarray*} b\leq bc \end{eqnarray*}$ lässt sich einfach nichts über die Relation von $\begin{eqnarray*} a \end{eqnarray*}$ zu $\begin{eqnarray*} b \end{eqnarray*}$ aussagen. Mache dir das an einem einfachen Zahlenbeispiel klar.

Man sucht nunmal bei der Vorkonditionierung eine Matrix $\begin{eqnarray*} P \end{eqnarray*}$ so, dass die Kondition von $\begin{eqnarray*} PA \end{eqnarray*}$ möglichst klein wird. Dass die Kondition nicht immer größer werden kann (was ja auch klar ist), sieht man auch an folgender Dualitätsbetrachtung: Angenommen, die Kondition von $\begin{eqnarray*} PA \end{eqnarray*}$ ist größer als die von $\begin{eqnarray*} A \end{eqnarray*}$ . Jetzt stelle dir vor, dein ursprüngliches GLS war nicht $\begin{eqnarray*} Ax=b \end{eqnarray*}$ , sondern $\begin{eqnarray*} Bx=c \end{eqnarray*}$ mit $\begin{eqnarray*} B=PA \end{eqnarray*}$ und $\begin{eqnarray*} c=Pb \end{eqnarray*}$ (also einfach $\begin{eqnarray*} PAx=Pb \end{eqnarray*}$ ). Die Matrix $\begin{eqnarray*} B \end{eqnarray*}$ lässt sich dann mit $\begin{eqnarray*} P^{-1} \end{eqnarray*}$ vorkonditionieren, und zwar in diesem Fall wirklich so, dass die Kondition kleiner wird. Es kann natürlich auch der umgekehrte Fall auftreten, dass die erste Vorkonditionierung wirklich besser ist. Ich will dir damit nur verdeutlichen, dass das Problem symmetrisch ist und dass deine Herangehensweise nur darauf beruht, dass du $\begin{eqnarray*} PA \end{eqnarray*}$ nur als dieses Produkt gegeben hast und die Abschätzung mit dieser Produktdarstellung aber einfach keine Aussage liefert (du kannst sie ja ebenso für das Produkt $\begin{eqnarray*} P^{-1}(PA) \end{eqnarray*}$ hinschreiben).

22.09.2009, 20:47

tigerbine

Auf diesen Beitrag antworten »

Hallo MSS,

wie geht man dann an die Sache ran? Mein Problem ist gerade der didaktische Aufbau diverser Literatur auf meinem Tisch.

*Into: GS, Matrix, Kondition

*Idee: Äquivalentes, aber besser konditioniertes LGS

*Angabe eines Vorkonditionieres

Was fehlt ist eine Erläuterung, der Bezug auf den Konditionsbegriff nimmt und nun zeigt, dass man wirklich besser ist mit dieser Idee.

22.09.2009, 20:49

Mathespezialschüler

Auf diesen Beitrag antworten »

Man kann natürlich nicht so pauschal sagen, dass man besser ist, da man es durch ein beliebiges $\begin{eqnarray*} P \end{eqnarray*}$ im Allgemeinen auch nicht wird.

Soll heißen: Du musst natürlich einen konkreten Algorithmus haben, der die Matrix $\begin{eqnarray*} P \end{eqnarray*}$ so wählt, dass die Kondition von $\begin{eqnarray*} PA \end{eqnarray*}$ wirklich kleiner wird als die von $\begin{eqnarray*} A \end{eqnarray*}$ .

22.09.2009, 20:53

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Ziemlich harte Forderung und ich sehe nicht, wie diese bei dem Jacobi Verfahren oder dem Gauß-Seidel-Verfahren allgemein zu erfüllen wäre.

nehmen wir mal das Jacobi-Verfahren. P ist dann eine Diagonalmatrix mit den Kehrwerten der Diagonalelemente von A.

22.09.2009, 22:21

awakenings

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
wie geht man dann an die Sache ran?

Naja, zentral ist bezüglich welcher Norm die Konditionszahl optimiert werden soll.
Je nachdem wie diese Matrixnorm berechnet wird ist die Permutationsmatrix zu bestimmen.

Um zu verstehen WIE genau die Permutationsmatrix die Konditionszahl bezüglicher dieser Norm verbessert, muss man halt in die Berechnungsvorschrift dieser Norm schauen.

Also jetzt mal ganz blöd gesagt:
wenn die Konditionszahl bezüglich der Zeilensummennorm optimiert werden soll, dann sorgt eine geeignete Permutationsmatrix dafür, dass die Zeilensummen der Matrix möglichst klein gehalten werden.

Was besseres fält mir dazu nicht ein, sorry wenn ich die Frage generell falsch verstanden hab...=D

22.09.2009, 22:28

tigerbine

Auf diesen Beitrag antworten »

Was mein Problem ist. Big Laugh

Naja, das eben eben salopp gesagt wird

"Du, lass uns anstatt Ax=b doch ein besser konditioniertes Problem lösen."
"Ok"
"Wir wählen folgenden Präkonditionierer, das nennt man dann das Jacobi-Verfahren"
"Ok"
"Das konvergiert, wenn das Strickte Zeilensummenkriterium erfüllt ist"
"Ok"

Es wird aber nirgends gesagt, warum das neue LGS (aus dem man sich dann die Rekursion für das Verfahren holt) besser konditioniert ist, als das Ax=b. Das ist mein Problem.

22.09.2009, 23:39

awakenings

Auf diesen Beitrag antworten »

Hey du postest ja in lichtgeschwindigkeit!!

Da editiert man etwas 10sekunden nach dem Posting weg schon hast du bereits Bezug darauf genommen =D

Also ich hatte das Jacobi-Verfahren leider noch nicht, weiss nur ungefähr worum es dabei geht und sollte mich vermutlich raushalten..

Aber frage mich nun - es müsste doch egal sein ob die Präkonditionierung im Rahmen eines Iterationsverfahrens vorgenommen wird oder bei einem "exakten" Lösungsverfahren oder einfach nur just4fun.

Was spricht gegen die Herangehungsweise, die mir im letzten Posting schon vorgeschwebt ist - einfach gucken bezüglicher welcher Norm die Konditionszahl interessiert und dann schauen warum die Berechnungsvorschrift dieser Norm eine kleinere Zahl verursacht, wenn eine Multiplikation mit dieser ominösen kehrwertigen Diagonalmatrix durchgeführt worden ist =D

Quasi einfach den "Spuren" zu Fuß folgen, das müsste die Antwort liefern oder?

Wie gesagt ist nur eine Idee..Wissen kann ich leider keines vorweisen *g

22.09.2009, 23:49

tigerbine

Auf diesen Beitrag antworten »

Jo, manchmal bin ich fix. Big Laugh

Es ist bei den Verfahren i.A. keine spezielle Norm angegeben. Und meinen Ansatz im ersten Posting, die beiden Normen zu allgemein zu vergleichen, hat MSS ja as ungeschickt gezeigt.

Zitat:

dann sorgt eine geeignete Permutationsmatrix dafür, dass die Zeilensummen der Matrix möglichst klein gehalten werden.

Es spielt aber bei der Kondition auch die Inverse Matrix eine Rolle, so dass die Strategie so nicht ausreicht.

Ich will (im Moment) auch noch kein neues Verfahren entwickeln, sondern einfach nur für die bestehenden Verfahren den Begriff "Vorkonditionierer" rechtfertigen.

Eine Beispielrechnung, so wie ich mir das im Ansatz Vorstelle wäre hier (Beweis feht ja). Das suche ich nun für die klassischen Verfahren Jacobi, Gauß Seidel, etc.

23.09.2009, 00:29

Mathespezialschüler

Auf diesen Beitrag antworten »

Wenn man ein Verfahren angibt (ich kenne das Jacobi-Verfahren auch nicht) und behauptet, dass dieses die Kondition verringert, dann sollte man dafür natürlich auch stichhaltige Argumente haben. In einem guten Buch sollte so etwas auch zu finden sein. Das Verfahren wird ja nicht auf Verdacht angewendet (davon gehe ich zumindest einmal aus). Du müsstest also nur entsprechende Literatur finden, die das behandelt.

23.09.2009, 00:35

awakenings

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Es ist bei den Verfahren i.A. keine spezielle Norm angegeben.

Naja, trotzdem wird eine bestimmte Normenwahl (bzw. eine Operatornorm) für das Problem gebräuchlich und sinnvoll sein.
Leider bin ich mit dem Jacobi nicht vertraut wie ich schon sagte unglücklich

aber im Dahmen+Reusken wird in diesem Zusammenhang immer über K2 gegangen (habs mal als Screen verlinkt).

http://www.myimg.de/?img=1420a9.jpg

Zitat:

Original von tigerbine
Es spielt aber bei der Kondition auch die Inverse Matrix eine Rolle, so dass die Strategie so nicht ausreicht.

Was spricht dagegen die Berechnung der Norm für die Matrix UND für die Inverse zu Betrachten?
(Schon wieder) im D+R wurde dies auch so gemacht, bezüglich der Äquilibrierung, die ich mir auch shcon angeguckt hatte =D (auch mal gescreent)

http://www.myimg.de/?img=205ff6.jpg

Vielleicht helfen dir diese zwei Anmerkungen weiter.
Ich plädiere jedenfalls aufs stärkste darauf, dass du

1. Bezug zur Norm nehmen musst
2. in die Berechnung der Konditionszahl bzgl. dieser Norm reinschauen musst

kann mir nicht vorstellen, wie man ohne diese 2 Informationskanäle irgendetwas darüber erfahren kann^^

Ich werde das morgen jedenfalls mal auf diese Weise ausprobieren, wenn ich irgendwelche Erkenntnisse gewinne poste ich wieder...
falls nicht, verkneife ich mir weitere Postings zu diesem Thema und hoffe, dass sich noch jmd. mit Durchblick meldet....mich interessiert das jetzt auch =D

23.09.2009, 00:40

tigerbine

Auf diesen Beitrag antworten »

Ich lasse euch wissen, wenn ich sie gefunden habe. Augenzwinkern

Einen Nachweis zur "Äquilibirerung" habe ich gefunden, bin aber im Fruststadium Prost

gerade nicht in der Lage folgende Abschätzung nachzuvollziehen: buch

$\begin{eqnarray*} \|C^{-1}\overline{D}^{-1} \|_{\infty} \geq \frac{\|C^{-1}\|_{\infty}}{\|\overline{D}\|_{\infty}} \end{eqnarray*}$

Welche Regel würde da benutzt... verwirrt

23.09.2009, 00:46

awakenings

Auf diesen Beitrag antworten »

Schau in meinen zweiten Link - dort wurden die Zwischenschritte nicht so einfach ausgelassen...

23.09.2009, 00:48

tigerbine

Auf diesen Beitrag antworten »

hab ich gerade gesehen Freude

Mit der Induzierten Matrixnorm-Schreibweise kommt man da mit dem Nachvollziehen besser klar. Somit ist Äquilibrierung nun als Verbesserung (bzgl. einer Bestimmten Norm Augenzwinkern

) nun nachgewiesen.

Ich werde mal schauen, ob ich zu dem Jacobi was finde. Recherche für morgen. Danke euch beiden schon mal, dass ihr mich nicht alleine gelassen hat. Mit Zunge

edit:
Also fündig bin ich nicht geworden, aber vielleicht war das in dem ersten Werk auch nur eine schlechte Einleitung, in dem Sinne, dass der Begriff/die Motivation "Vorkonditionierung" zu eng gefaßt wurde. Wirklich Bezug auf die Konditionszahl nimmt nur das was ich zur Äquilibrierung finde. Fasst man den Begriff weiter und meint damit auch schnelle Konvergenz, so erklärt sich, warum in den Werken "nur" darauf ein Augenmerk gerichtet wird, wenn man die Iterativen Verfahren zu Lösung von LGS betrachtet. Mehr als WS gibt mein "Standardbuch" nicht her und die anderen vertiefenden gehen eben auf die Konvergenzuntersuchung ein, liefern aber am Ende keine Zeile, wo gezeigt wird, dass man bzgl. einer Norm besser Konitioniertes LGS gelöst hat.

Falls dennoch jemand so eine Zeile findet, bitte posten.

Neue Frage »

Antworten »

Präkonditionierung

Verwandte Themen