Ilu Zerlegung

transcript

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?

• 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 :

Es bieten sich viele Lösungsverfahren an (ZB) :

- Gauss-Alghoritmus

- QR-Zerlegung (varianten)

- Cholesky-Zerlegung

- LU-Zerlegung

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:

motivation definition vision diskussionProblemstellung Beschreibung Wirkung

• 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 ?

• 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.

Beispiel : A*X=Y A

Beispiel : A*X=Y U

ILU-Zerlegung:auch Unvollständige LU-

Zerlegung ?

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 ?

• Beispiel : A*X=Y A

• Beispiel : A*X=Y U ( incomplet )

• Beispiel : A*X=Y U ( incomplet ) U (bei LU)

• 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 ?

• 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 ?

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

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

• Die Kosten von ILU-Zerlegung im Vergleich zum Verfahren Gauß-Seidel..

• Bezüglich mehreren mit der selben Matrix zu lösenden Systemen .

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 )

Danke !fürs Zuhören

Ilu Zerlegung

Documents