Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Iterationsschritte CG-Verfahren

Iterationsschritte CG-Verfahren

Universität / Fachhochschule

Sonstiges

Tags: Sonstig

Euler03 aktiv_icon

21:12 Uhr, 09.03.2024

Betrachtet wird das CG-Verfahren zur iterativen Lösung des Gleichungssystem A x=b mit einer positiv definiten und symmetrischen Matrix

A \in ℝ^{n \times n}

und

b \in ℝ^{n}

. Zeigen Sie, dass zur Reduzierung des Anfangsfehlers um den Faktor

ε

höchstens

t (ε) \leq \frac{1}{2} \sqrt{κ} \log (2 / ε) + 1

viele Iterationsschritte erforderlich sind. Hierbei ist

κ

die Spektralkonditionszahl von A.

Mit der gegeben Aufgabe habe ich noch etwas Probleme:

Wenn ich das richtig verstehe hat das CG-Verfahren die Eigenschaft, dass der Fehler nach t Iterationen orthogonal zum anfänglichen Residuum in der A-Norm ist (

g^{t} = A (x^{*} - x^{t})

), wobei

x^{*}

die exakte Lösung,

x^{t}

die Näherungslösung nach

t

Iterationen und

g^{t}

das Residuum nach t Iterationen ist.

Die A-Norm eines Vektors v ist definiert als

∥ v ∥_{A} = \sqrt{v^{T} A v}

--> Fehler nach t Iterationen in Bezug auf die A-Norm:

{∥ x^{*} - x^{t} ∥}_{A} = {∥ g^{t} ∥}_{A}

Nach t Iterationen wird der Fehler ja um einen Faktor von mindestens

{(\frac{2}{1 + \sqrt{κ}})}^{t}

reduziert:

{∥ x^{*} - x^{t} ∥}_{A} \leq \frac{2}{(1 + \sqrt{κ})^{t}} {∥ x^{*} - x^{0} ∥}_{A}

Muss ich jetzt diese Ungleichung einfach auf

ε

setzten und nach t auflösen?

ε \geq \frac{2}{(1 + \sqrt{κ})^{t}}

t (ε) \leq \frac{1}{2} \sqrt{κ} \log (\frac{2}{ε}) + 1

.

Das wäre jetzt meine Beweis Idee - kann ich hierbei so vorgehen bzw. wie müsste man vorgehen?
Vielen Dank im Voraus!
LG Euler

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Euler03 aktiv_icon

22:15 Uhr, 11.03.2024

????

1583524

1583434

	Status: nicht eingeloggt	Noch nicht registriert?