Vorkonditionierer – Wikipedia

In Mathematik, Vorkonditionierung ist die Anwendung einer Transformation, die als Vorkonditionierer, dass ein gegebenes Problem in eine Form gebracht wird, die für numerische Lösungsverfahren besser geeignet ist. Die Vorkonditionierung hängt normalerweise mit der Reduzierung einer Bedingungsnummer des Problems zusammen. Das vorkonditionierte Problem wird dann normalerweise durch eine iterative Methode gelöst.

Vorkonditionierung für lineare Systeme[edit]

In der linearen Algebra und der numerischen Analyse a Vorkonditionierer

${ displaystyle P}$

einer Matrix

${ displaystyle A}$

ist eine Matrix, so dass

${ displaystyle P ^ {- 1} A}$

hat eine kleinere Bedingungsnummer als

${ displaystyle A}$

. Es ist auch üblich anzurufen

${ displaystyle T = P ^ {- 1}}$

der Vorkonditionierer, anstatt

${ displaystyle P}$

, schon seit

${ displaystyle P}$

selbst ist selten explizit verfügbar. In der modernen Vorkonditionierung ist die Anwendung von

${ displaystyle T = P ^ {- 1}}$

dh Multiplikation eines Spaltenvektors oder eines Blocks von Spaltenvektoren mit

${ displaystyle T = P ^ {- 1}}$

wird üblicherweise von ziemlich hoch entwickelten Computer-Softwarepaketen matrixfrei ausgeführt, dh wo beides nicht der Fall ist

${ displaystyle P}$

, Noch

${ displaystyle T = P ^ {- 1}}$

(und oft nicht einmal

${ displaystyle A}$

) sind explizit in einer Matrixform verfügbar.

Vorkonditionierer sind bei iterativen Methoden zur Lösung eines linearen Systems nützlich

${ displaystyle Axe = b}$

zum

${ displaystyle x}$

da die Konvergenzrate für die meisten iterativen linearen Löser zunimmt, weil die Bedingungszahl einer Matrix infolge der Vorkonditionierung abnimmt. Vorkonditionierte iterative Löser übertreffen in der Regel direkte Löser, z. B. die Gaußsche Eliminierung, für große, insbesondere für spärliche Matrizen. Iterative Löser können als matrixfreie Methoden verwendet werden, dh werden die einzige Wahl, wenn die Koeffizientenmatrix

${ displaystyle A}$

wird nicht explizit gespeichert, sondern durch Auswertung von Matrixvektorprodukten aufgerufen.

Beschreibung[edit]

Anstatt das ursprüngliche lineare System oben zu lösen, kann man das richtige vorkonditionierte System lösen:

${ displaystyle AP ^ {- 1} Px = b}$

über das Lösen

${ displaystyle AP ^ {- 1} y = b}$

zum

${ displaystyle y}$

und

${ displaystyle Px = y}$

zum

${ displaystyle x}$

.

Alternativ kann man das linke vorkonditionierte System lösen:

${ displaystyle P ^ {- 1} (Axe-b) = 0.}$

Beide Systeme ergeben die gleiche Lösung wie das ursprüngliche System, solange die Vorkonditionierermatrix vorhanden ist

${ displaystyle P}$

ist nicht singulär. Die linke Vorkonditionierung ist häufiger.

Das Ziel dieses vorkonditionierten Systems ist es, die Bedingungsnummer der linken oder rechten vorkonditionierten Systemmatrix zu reduzieren

${ displaystyle P ^ {- 1} A}$

oder

${ displaystyle AP ^ {- 1},}$

beziehungsweise. Die vorkonditionierte Matrix

${ displaystyle P ^ {- 1} A}$

oder

${ displaystyle AP ^ {- 1}}$

wird fast nie explizit gebildet. Nur die Aktion des Aufbringens des Vorkonditionierers löst den Vorgang

${ displaystyle P ^ {- 1}}$

zu einem bestimmten Vektor müssen in iterativen Methoden berechnet werden.

In der Regel gibt es einen Kompromiss bei der Auswahl von

${ displaystyle P}$

. Da der Betreiber

${ displaystyle P ^ {- 1}}$

muss bei jedem Schritt des iterativen linearen Lösers angewendet werden, es sollte einen geringen Aufwand (Rechenzeit) für das Anwenden des haben

${ displaystyle P ^ {- 1}}$

Betrieb. Der billigste Vorkonditionierer wäre daher

${ displaystyle P = I}$

seit damals

${ displaystyle P ^ {- 1} = I.}$

Dies führt eindeutig zu dem ursprünglichen linearen System und der Vorkonditionierer tut nichts. Im anderen Extrem die Wahl

${ displaystyle P = A}$

gibt

${ displaystyle P ^ {- 1} A = AP ^ {- 1} = I,}$

die die optimale Bedingungsnummer 1 hat und eine einzige Iteration für die Konvergenz erfordert; jedoch in diesem Fall

${ displaystyle P ^ {- 1} = A ^ {- 1},}$

Das Aufbringen des Vorkonditionierers ist ebenso schwierig wie das Lösen des ursprünglichen Systems. Man wählt daher

${ displaystyle P}$

als irgendwo zwischen diesen beiden Extremen, um eine minimale Anzahl linearer Iterationen zu erreichen, während der Operator erhalten bleibt

${ displaystyle P ^ {- 1}}$

so einfach wie möglich. Einige Beispiele für typische Vorkonditionierungsansätze sind nachstehend aufgeführt.

Vorkonditionierte iterative Methoden[edit]

Vorkonditionierte iterative Methoden für

${ displaystyle Axe-b = 0}$

sind in den meisten Fällen mathematisch äquivalent zu iterativen Standardmethoden, die auf das vorkonditionierte System angewendet werden

${ displaystyle P ^ {- 1} (Axe-b) = 0.}$

Zum Beispiel die Standard-Richardson-Iteration zum Lösen

${ displaystyle Axe-b = 0}$

ist

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} (A mathbf {x} _ {n} – mathbf {b}), n geq 0.}$

Auf das vorkonditionierte System angewendet

${ displaystyle P ^ {- 1} (Axe-b) = 0,}$

es wird zu einer vorkonditionierten Methode

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} P ^ {- 1} (A mathbf {x} _ {n} – mathbf {b}), n geq 0.}$

Beispiele für beliebte vorkonditionierte iterative Verfahren für lineare Systeme umfassen das vorkonditionierte konjugierte Gradientenverfahren, das bikonjugierte Gradientenverfahren und das verallgemeinerte Minimalrestverfahren. Iterative Methoden, die Skalarprodukte zur Berechnung der iterativen Parameter verwenden, erfordern entsprechende Änderungen des Skalarprodukts zusammen mit dem Ersetzen

${ displaystyle P ^ {- 1} (Axe-b) = 0}$

zum

${ displaystyle Axe-b = 0.}$

Lineare Vorkonditionierung[edit]

Eine lineare iterative Methode sei durch die Matrixaufteilung gegeben

${ displaystyle A = MN}$

und Iterationsmatrix

${ displaystyle C = IM ^ {- 1} A}$

.

Nehmen Sie Folgendes an

Dann die Reduzierung der Zustandsnummer des Systems

${ displaystyle kappa (M ^ {- 1} A)}$

kann von oben begrenzt werden durch

${ displaystyle kappa (M ^ {- 1} A) leq { frac {1+ rho (C)} {1- rho (C)}} ,.}$

Geometrische Interpretation[edit]

Für eine symmetrische positive definitive Matrix

${ displaystyle A}$

der Vorkonditionierer

${ displaystyle P}$

wird typischerweise auch symmetrisch positiv definit gewählt. Der vorkonditionierte Bediener

${ displaystyle P ^ {- 1} A}$

ist dann auch symmetrisch positiv definit, aber in bezug auf die

${ displaystyle P}$

-basiertes Skalarprodukt. In diesem Fall besteht der gewünschte Effekt beim Aufbringen eines Vorkonditionierers darin, die quadratische Form des vorkonditionierten Operators zu erhalten

${ displaystyle P ^ {- 1} A}$

in Bezug auf die

${ displaystyle P}$

-basiertes Skalarprodukt soll nahezu kugelförmig sein.^[1]

Variable und nichtlineare Vorkonditionierung[edit]

Bezeichnen

${ displaystyle T = P ^ {- 1}}$

Wir heben hervor, dass die Vorkonditionierung praktisch als Multiplikation eines Vektors implementiert wird

${ displaystyle r}$

durch

${ displaystyle T}$

dh Berechnen des Produkts

${ displaystyle Tr.}$

In vielen Anwendungen

${ displaystyle T}$

wird nicht als Matrix angegeben, sondern als Operator

${ displaystyle T (r)}$

auf den Vektor einwirken

${ displaystyle r}$

. Einige beliebte Vorkonditionierer ändern sich jedoch mit

${ displaystyle r}$

und die Abhängigkeit von

${ displaystyle r}$

kann nicht linear sein. Typische Beispiele umfassen die Verwendung nichtlinearer iterativer Verfahren, z. B. des konjugierten Gradientenverfahrens, als Teil der Vorkonditionierungskonstruktion. Solche Vorkonditionierer können praktisch sehr effizient sein, ihr Verhalten ist jedoch theoretisch schwer vorherzusagen.

Spektral äquivalente Vorkonditionierung[edit]

Die häufigste Verwendung der Vorkonditionierung ist die iterative Lösung linearer Systeme, die sich aus Approximationen partieller Differentialgleichungen ergibt. Je besser die Approximationsqualität ist, desto größer ist die Matrixgröße. In einem solchen Fall besteht das Ziel einer optimalen Vorkonditionierung einerseits darin, die Spektralbedingungszahl von zu machen

${ displaystyle P ^ {- 1} A}$

von oben durch eine von der Matrixgröße unabhängige Konstante begrenzt werden, die aufgerufen wird spektral äquivalent Vorkonditionierung durch D’yakonov. Auf der anderen Seite sind die Kosten für die Anwendung der

${ displaystyle P ^ {- 1}}$

sollte idealerweise proportional (auch unabhängig von der Matrixgröße) zu den Multiplikationskosten von sein

${ displaystyle A}$

durch einen Vektor.

Beispiele[edit]

Jacobi (oder diagonaler) Vorkonditionierer[edit]

Das Jacobi Vorkonditionierer ist eine der einfachsten Formen der Vorkonditionierung, bei der der Vorkonditionierer als Diagonale der Matrix gewählt wird

${ displaystyle P = mathrm {diag} (A).}$

Vorausgesetzt

${ displaystyle A_ {ii} neq 0, forall i}$

, wir bekommen

${ displaystyle P_ {ij} ^ {- 1} = { frac { delta _ {ij}} {A_ {ij}}}.}$

Es ist effizient für diagonal dominante Matrizen

${ displaystyle A}$

.

SPAI[edit]

Das Sparse Approximate Inverse Vorkonditionierer minimiert

${ displaystyle | AT-I | _ {F},}$

wo

${ displaystyle | cdot | _ {F}}$

ist die Frobenius-Norm und

${ displaystyle T = P ^ {- 1}}$

stammt aus einem geeignet beschränkten Satz von spärlichen Matrizen. Nach der Frobenius-Norm reduziert sich dies auf die Lösung zahlreicher unabhängiger Probleme der kleinsten Quadrate (eines für jede Spalte). Die Einträge in

${ displaystyle T}$

muss auf ein Sparsity-Muster beschränkt sein, sonst bleibt das Problem so schwierig und zeitaufwändig wie das Finden der genauen Umkehrung von

${ displaystyle A}$

. Die Methode wurde von MJ Grote und T. Huckle zusammen mit einem Ansatz zur Auswahl von Sparsity-Mustern eingeführt.^[2]

Andere Vorkonditionierer[edit]

Externe Links[edit]

Vorkonditionierung für Eigenwertprobleme[edit]

Eigenwertprobleme können auf verschiedene alternative Arten dargestellt werden, die jeweils zu einer eigenen Vorkonditionierung führen. Die traditionelle Vorkonditionierung basiert auf der sogenannten spektrale Transformationen. Wenn man (ungefähr) den angestrebten Eigenwert kennt, kann man den entsprechenden Eigenvektor berechnen, indem man das verwandte homogene lineare System löst, wodurch die Vorkonditionierung für das lineare System verwendet werden kann. Schließlich bringt die Formulierung des Eigenwertproblems als Optimierung des Rayleigh-Quotienten vorkonditionierte Optimierungstechniken in die Szene.^[3]

Spektrale Transformationen[edit]

In Analogie zu linearen Systemen für ein Eigenwertproblem

${ displaystyle Axe = lambda x}$

man könnte versucht sein, die Matrix zu ersetzen

${ displaystyle A}$

mit der Matrix

${ displaystyle P ^ {- 1} A}$

mit einem Vorkonditionierer

${ displaystyle P}$

. Dies ist jedoch nur dann sinnvoll, wenn die suchenden Eigenvektoren von

${ displaystyle A}$

und

${ displaystyle P ^ {- 1} A}$

sind gleich. Dies ist bei spektralen Transformationen der Fall.

Die beliebteste spektrale Transformation ist die sogenannte Shift-and-Invert Transformation, wo für einen gegebenen Skalar

${ displaystyle alpha}$

, genannt die Verschiebung, das ursprüngliche Eigenwertproblem

${ displaystyle Axe = lambda x}$

wird durch das Shift-and-Invert-Problem ersetzt

${ displaystyle (A- alpha I) ^ {- 1} x = mu x}$

. Die Eigenvektoren bleiben erhalten, und man kann das Shift-and-Invert-Problem durch einen iterativen Löser lösen, z. B. die Potenziteration. Dies ergibt die inverse Iteration, die normalerweise gegen den Eigenvektor konvergiert, entsprechend dem Eigenwert, der der Verschiebung am nächsten liegt

${ displaystyle alpha}$

. Die Rayleigh-Quotienteniteration ist eine Shift-and-Invert-Methode mit variabler Verschiebung.

Spektrale Transformationen sind spezifisch für Eigenwertprobleme und haben keine Analoga für lineare Systeme. Sie erfordern eine genaue numerische Berechnung der Transformation, die zum Hauptengpass für große Probleme wird.

Allgemeine Vorkonditionierung[edit]

Um eine enge Verbindung zu linearen Systemen herzustellen, nehmen wir an, dass der angestrebte Eigenwert

${ displaystyle lambda _ { star}}$

ist bekannt (ungefähr). Dann kann man den entsprechenden Eigenvektor aus dem homogenen linearen System berechnen

${ displaystyle (A- lambda _ { star} I) x = 0}$

. Mit dem Konzept der linken Vorkonditionierung für lineare Systeme erhalten wir

${ displaystyle T (A- lambda _ { star} I) x = 0}$

, wo

${ displaystyle T}$

ist der Vorkonditionierer, den wir mit der Richardson-Iteration lösen können

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} T (A- lambda _ { star} I)) mathbf {x} _ {n}, n geq 0.}$

Das Ideal Vorkonditionierung^[3][edit]

Die Moore-Penrose-Pseudoinverse

${ displaystyle T = (A- lambda _ { star} I) ^ {+}}$

ist der Vorkonditionierer, der die obige Richardson-Iteration in einem Schritt mit konvergieren lässt

${ displaystyle gamma _ {n} = 1}$

, schon seit

${ displaystyle I- (A- lambda _ { star} I) ^ {+} (A- lambda _ { star} I)}$

, bezeichnet durch

${ displaystyle P _ { star}}$

ist der orthogonale Projektor auf dem Eigenraum, entsprechend

${ displaystyle lambda _ { star}}$

. Die Wahl

${ displaystyle T = (A- lambda _ { star} I) ^ {+}}$

ist aus drei unabhängigen Gründen unpraktisch. Zuerst,

${ displaystyle lambda _ { star}}$

ist eigentlich nicht bekannt, obwohl es durch seine Annäherung ersetzt werden kann

${ displaystyle { tilde { lambda}} _ { star}}$

. Zweitens erfordert die genaue Moore-Penrose-Pseudoinverse die Kenntnis des Eigenvektors, den wir zu finden versuchen. Dies kann durch die Verwendung des Jacobi-Davidson-Vorkonditionierers etwas umgangen werden

${ displaystyle T = (I – { tilde {P}} _ { star}) (A – { tilde { lambda}} _ { star} I) ^ {- 1} (I – { tilde {P}} _ { star})}$

, wo

${ displaystyle { tilde {P}} _ { star}}$

ungefähr

${ displaystyle P _ { star}}$

. Last but not least erfordert dieser Ansatz eine genaue numerische Lösung des linearen Systems mit der Systemmatrix

${ displaystyle (A – { tilde { lambda}} _ { star} I)}$

, was für große Probleme genauso teuer wird wie das obige Shift-and-Invert-Verfahren. Wenn die Lösung nicht genau genug ist, ist Schritt zwei möglicherweise redundant.

Praktische Vorkonditionierung[edit]

Ersetzen wir zunächst den theoretischen Wert

${ displaystyle lambda _ { star}}$

in der obigen Richardson-Iteration mit ihrer aktuellen Annäherung

${ displaystyle lambda _ {n}}$

um einen praktischen Algorithmus zu erhalten

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} T (A- lambda _ {n} I) mathbf {x} _ { n}, n geq 0.}$

Eine beliebte Wahl ist

${ displaystyle lambda _ {n} = rho (x_ {n})}$

mit der Rayleigh-Quotientenfunktion

${ displaystyle rho ( cdot)}$

. Praktische Vorkonditionierung kann so trivial sein wie nur die Verwendung

${ displaystyle T = (diag (A)) ^ {- 1}}$

oder

${ displaystyle T = (diag (A- lambda _ {n} I)) ^ {- 1}.}$

Für einige Klassen von Eigenwertproblemen ist die Effizienz von

${ displaystyle T approx A ^ {- 1}}$

wurde sowohl numerisch als auch theoretisch demonstriert. Die Wahl

${ displaystyle T approx A ^ {- 1}}$

ermöglicht es, die Vielzahl von Vorkonditionierern, die für lineare Systeme entwickelt wurden, leicht für Eigenwertprobleme zu nutzen.

Aufgrund des sich ändernden Wertes

${ displaystyle lambda _ {n}}$

Eine umfassende theoretische Konvergenzanalyse ist im Vergleich zum Fall linearer Systeme selbst für die einfachsten Methoden wie die Richardson-Iteration viel schwieriger.

Externe Links[edit]

Vorkonditionierung in der Optimierung[edit]

Bei der Optimierung wird die Vorkonditionierung typischerweise verwendet, um Optimierungsalgorithmen erster Ordnung zu beschleunigen.

Beschreibung[edit]

Zum Beispiel, um ein lokales Minimum einer reellen Funktion zu finden

${ displaystyle F ( mathbf {x})}$

Bei Verwendung des Gradientenabfalls werden Schritte proportional zum Negativ des Gradienten

${ displaystyle – nabla F ( mathbf {a})}$

(oder des ungefähren Gradienten) der Funktion am aktuellen Punkt:

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} nabla F ( mathbf {x} _ {n}), n geq 0.}$

Der Vorkonditionierer wird auf den Gradienten angewendet:

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} P ^ {- 1} nabla F ( mathbf {x} _ {n} ), n geq 0.}$

Die Vorkonditionierung kann hier als Änderung der Geometrie des Vektorraums mit dem Ziel angesehen werden, dass die Ebenensätze wie Kreise aussehen.^[4] In diesem Fall zielt der vorkonditionierte Gradient näher an den Punkt der Extrema als in der Abbildung, was die Konvergenz beschleunigt.

Anschluss an lineare Systeme[edit]

Das Minimum einer quadratischen Funktion

${ displaystyle F ( mathbf {x}) = { frac {1} {2}} mathbf {x} ^ {T} A mathbf {x} – mathbf {x} ^ {T} mathbf { b}}$

,

wo

${ displaystyle mathbf {x}}$

und

${ displaystyle mathbf {b}}$

sind echte Spaltenvektoren und

${ displaystyle A}$

ist eine reelle symmetrische positiv-definitive Matrix, ist genau die Lösung der linearen Gleichung

${ displaystyle A mathbf {x} = mathbf {b}}$

. Schon seit

${ displaystyle nabla F ( mathbf {x}) = A mathbf {x} – mathbf {b}}$

, das vorkonditionierte Gradientenabstiegsverfahren zur Minimierung

${ displaystyle F ( mathbf {x})}$

ist

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} P ^ {- 1} (A mathbf {x} _ {n} – mathbf {b}), n geq 0.}$

Dies ist die vorkonditionierte Richardson-Iteration zum Lösen eines linearen Gleichungssystems.

Verbindung zu Eigenwertproblemen[edit]

Das Minimum des Rayleigh-Quotienten

${ displaystyle rho ( mathbf {x}) = { frac { mathbf {x} ^ {T} A mathbf {x}} { mathbf {x} ^ {T} mathbf {x}}} ,}$

wo

${ displaystyle mathbf {x}}$

ist ein reeller Spaltenvektor ungleich Null und

${ displaystyle A}$

ist eine reelle symmetrische positiv-definitive Matrix, ist der kleinste Eigenwert von

${ displaystyle A}$

, während der Minimierer der entsprechende Eigenvektor ist. Schon seit

${ displaystyle nabla rho ( mathbf {x})}$

ist proportional zu

${ displaystyle A mathbf {x} – rho ( mathbf {x}) mathbf {x}}$

, das vorkonditionierte Gradientenabstiegsverfahren zur Minimierung

${ displaystyle rho ( mathbf {x})}$

ist

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} P ^ {- 1} (A mathbf {x} _ {n} – rho ( mathbf {x_ {n}}) mathbf {x_ {n}}), n geq 0.}$

Dies ist ein Analogon der vorkonditionierten Richardson-Iteration zur Lösung von Eigenwertproblemen.

Variable Vorkonditionierung[edit]

In vielen Fällen kann es vorteilhaft sein, den Vorkonditionierer bei einigen oder sogar jedem Schritt eines iterativen Algorithmus zu ändern, um einer sich ändernden Form der Pegelsätze Rechnung zu tragen, wie in

${ displaystyle mathbf {x} _ {n + 1} = mathbf {x} _ {n} – gamma _ {n} P_ {n} ^ {- 1} nabla F ( mathbf {x} _ {n}), n geq 0.}$

Man sollte jedoch bedenken, dass der Aufbau eines effizienten Vorkonditionierers sehr oft rechenintensiv ist. Die erhöhten Kosten für die Aktualisierung des Vorkonditionierers können den positiven Effekt einer schnelleren Konvergenz leicht außer Kraft setzen.

Verweise[edit]

Quellen[edit]