Wie wirken sich Änderungen mit niedrigem Rang auf die Konvergenz der Krylov-Methode aus?

Angenommen, ich habe ein lineares System , das mit einer geeigneten Krylov-Methode (wie CG oder GMRES) für alle schnell konvergiert . Wenn eine Matrix mit niedrigem Rang , konvergiert dieselbe Krylov-Methode auf dem System auch schnell (idealerweise mit einer zusätzlichen Anzahl von Iterationen, die grob nur von abhängt )? $A x = b$ $b$ $B$ $r$ $(A + B) x = b$ $r$

Ein Beispiel für ein solches System wären gut vorkonditionierte Membranelastizität und -biegung sowie nicht vorkonditionierte Luftdruckwerte mit dichter äußerer Produktstruktur.

Man beachte , dass die Frage ist , das gleiche mit oder ohne Vorkonditionierung, da ein Rang Modifikation von . $P(A + B)Q = PAQ + PBQ$ $r$ $PAQ$

krylov-method Geoffrey Irving
quelle

Antworten:

Wenn Ihr Krylov-Unterraum auf Potenzen von basiert , wird die Konvergenz um höchstens eine Reihe von Iterationen verzögert, die dem Rang der Korrektur entsprechen. Wenn es auf Potenzen von basiert $A$ $A^TA$ dann höchstens das Doppelte dieser Zahl.

Ich habe eine solche Aussage in der Literatur nicht gesehen. Aber um die Gültigkeit in dem ersten Fall zu sehen, ist es ausreichend , um zu zeigen , dass die - te Krylovraum der Matrix wobei hat Säulen ohne niederrangigen Korrekturen in dem entsprechenden Raum enthalten ist, aber mit einem entsprechend höherer Index . Dies ist einfach zu überprüfen. $k$ $A+USV^T$ $U,V$ $r$ $k+r$

Arnold Neumaier
quelle

A

$A$

A + B

$A+B$

A

$A$

Egal: Vermutlich meinst du Potenzen der fraglichen Matrix, also

A + B

$A+B$ in diesem Fall.

Geoffrey Irving

Ja. Die Methode hat eine Matrix als Parameter, und diese Matrix wird normalerweise mit bezeichnet

A

$A$ .

Arnold Neumaier

Vielleicht könnten Sie für weiteres Interesse Ihre Gleichung (oder die Lösung) mit einigen Anforderungen an umschreiben

B

$\boldsymbol{B}$ zu

x = (E + \sum_{k = 1}^{\infty} {(A^{- 1} B)}^{k}) A^{- 1} b

$\boldsymbol{x}=\left(\boldsymbol{E}+\sum_{k=1}^\infty\left(\boldsymbol{A}^{-1} \boldsymbol{B}\right)^k\right) \boldsymbol{A}^{-1} \boldsymbol{b}$ Was könnte helfen, wenn

B

$\boldsymbol{B}$ ist nilpotent oder

A^{- 1} B

$\boldsymbol{A}^{-1}\boldsymbol{B}$ von kleiner Norm. Man erkennt auch die Abhängigkeit von der Lösung des undisturbedProblems.

Bastian Ebeling