Was ist die Worst-Case-Komplexität von Conjugate Gradient?

9

Sei , symmetrisch und positiv definit. Angenommen, es sind Arbeitseinheiten erforderlich, um einen Vektor mit zu multiplizieren . Es ist bekannt, dass das Ausführen des CG-Algorithmus für mit der Bedingungsnummer Arbeitseinheiten erfordert . m A A κ O ( m ARn×nmAAκO(mκ)

Als -Anweisung ist dies natürlich eine Obergrenze. Und der CG-Algorithmus kann immer in null Schritten mit einer glücklichen anfänglichen Vermutung enden.O

Wissen wir, ob es eine RHS und eine erste (unglückliche) Vermutung gibt, die Schritte erfordert ? Anders ausgedrückt: Ist die Worst-Case-Arbeitskomplexität von CG wirklich ?Θ(mΘ(κ)Θ(mκ)

Diese Frage stellt sich, als ich feststellen wollte, ob der Nutzen eines Vorkonditionierers (niedriger ) seine Kosten (höher ) überwog . Im Moment arbeite ich mit Spielzeugproblemen und möchte eine bessere Idee haben, bevor ich etwas in einer kompilierten Sprache implementiere.mκm

Fred
quelle
5
Sie könnten vermutlich eine pessimale Anfangsschätzung konstruieren, indem Sie den CG-Algorithmus "rückwärts" ausführen und geeignete Energie in jede der orthogonalen Suchrichtungen einbringen, für die der Algorithmus alle Schritte benötigt. A
Origimbo

Antworten:

9

Die Antwort ist ein klares Ja. Die Konvergenzratengrenze von ist scharf über der Menge symmetrischer positiver bestimmter Matrizen mit der Bedingungsnummerκ. Mit anderen Worten,CGweiß nichts mehr überAals seine Bedingungsnummer und kann wirklich √ nehmen(κ1)/(κ+1)κA Iterationen zu konvergieren. Locker gesagt wird die Obergrenze erreicht, wenn die Eigenwerte vonAinnerhalb eines Intervalls der Bedingungsnummerκgleichmäßig verteilt (dh "gepfeffert") sind.κAκ

Hier ist eine strengere Aussage. Deterministische Versionen sind komplizierter, arbeiten jedoch nach denselben Prinzipien.

Satz (Worst-Case-Wahl von ). Pick jede beliebige orthogonale Matrix U , lassen λ 1 , ... , λ n sein , n reelle Zahlen einheitlich aus dem realen Intervall abgetastet [ 1 , κ ] , und sei b = [ b 1 ; ; b n ] seien n reelle Zahlen, die aus dem Standard-Gaußschen abgetastet wurden. Definiere A = U d i a g ( λ 1 ,AUλ1,,λnn[1,κ]b=[b1;;bn]nDannkonvergieren konjugierte Gradientenin der Grenze n mit der Wahrscheinlichkeit eins zu einer ϵ genauen Lösung von A x = b in nicht weniger als Ω ( √)

A=Udiag(λ1,,λn)UT.
nϵAx=bIterationen.Ω(κlogϵ1)

Beweis. Der Standardbeweis basiert auf optimalen Chebyshev-Polynomnäherungen unter Verwendung von Techniken, die an einer Reihe von Stellen zu finden sind, wie beispielsweise Greenbaums Buch oder Saads Buch .

Richard Zhang
quelle
1
Die Grenze ist nicht scharf, wie die Antwort später erklärt: Wenn die Eigenwerte nicht gleichmäßig verteilt sind, konvergiert cg schneller, da es sich nicht um eine Stationalitätsiteration handelt. Daher müssen wir mehr über die Matrix wissen.
Guido Kanschat
@ GuidoKanschat: Guter Punkt, und ich habe die Aussage korrigiert, um zu verdeutlichen, dass die Schärfe über alle mit der Bedingung κ erreicht wird . Aκ
Richard Zhang
p(A)kp(0)=1Λ ( A ) [ 1 , κ ] minpmaxλΛ(A)|p(λ)|Λ(A)[1,κ]κ
0

Nehmen wir dies als meine ursprüngliche Frage: Wissen wir, ob es eine RHS und eine anfängliche (unglückliche) Vermutung gibt, die Schritte erfordert ?Θ(κ)

Die Antwort auf die Frage lautet "nein". Die Idee zu dieser Antwort stammt aus dem Kommentar von Guido Kanschat.

Behauptung: Für jede gegebene Bedingungsnummer existiert eine Matrix mit dieser Bedingungsnummer, für die der CG-Algorithmus in höchstens zwei Schritten endet (für jede gegebene RHS und anfängliche Schätzung).A.kA

Betrachten Sie wobei . Dann wird die Konditionszahl von ist . Sei die RHS und bezeichne die Eigenwerte von als wobei A = d i a g ( 1 , κ , κ , , κ ) A κ b R n A λ i λ i = { 1 i = 1 κ i 1 .ARn×nA=diag(1,κ,κ,,κ)AκbRnAλi

λi={1i=1κi1.

Wir betrachten zunächst den Fall, in dem , die anfängliche Vermutung, Null ist. Bezeichne als zweite Schätzung von aus dem CG-Algorithmus. Wir zeigen, dass indem wir . In der Tat haben wirx(0)Rnx(2)RnA1bx(2)=A1bx(2)A1b,A(x(2)A1b)=0

x(2)A1b,A(x(2)A1b)=x(2)A1bA2=minppoly1(p(A)A1)bA2=minppoly1i=1n(p(λi)λi1)2λibi2i=1n(p^(λi)λi1)2λibi2=0

Wo wir das Polynom erster Ordnung definiert als . Also haben wir den Fall für bewiesen . p (x)=(1+κ-x)/κx(0)=0p^p^(x)=(1+κx)/κx(0)=0

Wenn , dann ist wobei ist die zweite Schätzung des CG-Algorithmus, wobei durch . Deshalb haben wir diesen Fall auf den vorherigen reduziert. x ( 2 ) = ¯ x ( 2 ) + x ( 0 ) ¯ x ( 2 ) b ¯ b = B - A x ( 0 )x(0)0x(2)=x(2)¯+x(0)x(2)¯bb¯=bAx(0)

Fred
quelle
Wie viel davon ist robust gegenüber endlicher Präzisionsarithmetik?
Origimbo
@origimbo Wenn Ihre Frage an mich gerichtet war, lautet die Antwort: "Ich weiß es nicht."
Fred