Upload
abdelhamid81
View
581
Download
0
Embed Size (px)
DESCRIPTION
incomplete LU-Decomposition ( by Abdelhamid Barzali )
Citation preview
Iterativer LöserILU-Zerlegung
Abdelhamid BarzaliProf. Dr. Thomas Huckle18.06.07
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
ILU-Zerlegung
Einführung
warum? - was? - wie?
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Lösen des Gleichungssystems A*X=YAls Computerprogramm umgesetzt .
• Lineare Probleme der Technik lassen sich, sofern sie nicht über- oder unterbestimmt sind auf die Lösung eines linearen Gleichungssystems zurückführen.
Ziel :
warum? - was? - wie?
warum? - was? - wie?
Es bieten sich viele Lösungsverfahren an (ZB) :
- Gauss-Alghoritmus
- QR-Zerlegung (varianten)
- Cholesky-Zerlegung
- LU-Zerlegung
…
warum? - was? - wie?
Die Methoden zur Lösung von linearen Gleichungssystemen unterteilt man in zwei klassen :
• direkte Verfahren : Cholesky-Zerlegung,Gauss- Verfahren,LU &-QR-Zerlegung
• iterative Verfahren : Gauß-Seidel- und Jacobi-Verfahren,ILU..
LU-Zerlegung „Dreieckszerlegung “Dies ist eine Zerlegung der regulären Matrix A in das Produkt einer linken unteren Dreiecksmatrix L (links)und einer rechten oberen Dreiecksmatrix U (rechts). Das folgende Beispiel zeigt dies:
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
warum? - was? - wie?
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
warum? - was? - wie?
wie
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
warum? - was? - wie?
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
warum? - was? - wie?
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• A*X=Y => A=U*L => Vorwärtseinsetzen : L*Y= b=> Rückwärtseinsetzen : R*X=Y
• Die Anzahl arithmetischer Operationen für die LU-Zerlegung ist bei einer n *n-Matrix ca. 2/3*(n^3)
• Was ist eine dünnbesetzte Matrix ?
• Was passiert bei der Berechnung von LU bezüglich dünnbesetzten Matrizen ?
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Bei der Berechnung einer normalen LU-Zerlegung einer dünnbesetzten Matrix :
- man kann die Besetzungsstruktur in der Regel nicht ausnutzen
- Es wird daher sehr viel mehr Speicherplatz benötigt als für die ursprüngliche Matrix .
- die Anzahl der notwendigen Rechenoperationen ist nicht geringer als die für eine vollbesetzte Matrix.
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
Beispiel : A*X=Y A
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
Beispiel : A*X=Y U
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
ILU-Zerlegung:auch Unvollständige LU-
Zerlegung ?
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
ILU-Zerlegung „Unvollständige LU-Zerlegung“
bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer n*n-Matrix A in das Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix Ubei der von den Zerlegungsmatrizen L und U nur die Einträge einer vorgegebenen Besetzungsstruktur berechnet werden. Wie ?
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Beispiel : A*X=Y A
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Beispiel : A*X=Y U ( incomplet )
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Beispiel : A*X=Y U ( incomplet ) U (bei LU)
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Präkonditionierer „Vorkonditionerer “
• bezogen auf ein lineares Gleichungssystem A*x=bbedeutet Präkonditioniereung die Umwandlung in ein äqualentes LGS C*y=d,sodass letzteres numerisch einfacher zu lösen ist .
man hauptsächlich iterative
• warum das denn ?
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Die ILU-Zerlegung wird erfolgreich als Vorkonditionerer zur Beschleunigung der iterativen Lösung großer dünnbesetzterlinearer Gleichungssysteme Ax = b mittels Krylow-Unterraum-Verfahren eingesetzt.
• Krylow-Unterraum-Verfahren ?
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
Anwendung
Für die Anwendung als Vorkonditioniererwird das Gleichungssystem Ax = b formal mit (LU)^( 1) multipliziert,Wendet man darauf Krylow-Unterraum-Verfahren an, so konvergieren diese besser, da die Matrix ((LU)^( 1))* A näher an der Einheitsmatrix als A ist
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
For k = 1,...,n 1, doFor i = k + 1,...,n and if , do
mik: = mik / mkkFor j = k + 1,...,n and if ,do
mij: = mij mikmkj
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
• Die Kosten von ILU-Zerlegung im Vergleich zum Verfahren Gauß-Seidel..
• Bezüglich mehreren mit der selben Matrix zu lösenden Systemen .
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
Geschichte & Varianten- ILU(p) Weit verbreitet sind die ILU(p)-Zerlegungen, die
erstmals von Watts 1981 bei der Simulation eines Ölreservoirs betrachtet wurden .
- Die ILUT haben den Nachteil, dass die Nichtnulleinträge nicht aufgrund von Approximationseigenschaften gewählt werden und somit Rechenzeit für Fast-Nulleinträge vergeudet werden kann. (1994 von Yousef Saad vorgeschlagenen ) - ...es gibt auch weitere
Literatur• Andreas Meister: Numerik linearer Gleichungssysteme, 2.
Auflage, Vieweg, Wiesbaden 2005 .
• Gerard Meurant: Computer Solution of Large Linear Systems, Elsevier, 1999
• Yousef Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003,
• A survey of preconditioned iterative methods
• Wikipedia + Vorlesung ( Nummerische Mathematik )
motivation definition vision diskussionProblemstellung Beschreibung Wirkung
ILU-Iterativ 2007 - Prof. Dr. Thomas Huckle
Danke !fürs Zuhören
:)