Konvergenz des cg-Verfahrens gegen die Minimumnormlösung

Question

Aufgabe:

Es sei der Abbruchindex n_Abbruch des cg-Verfahrens (das benutzt wird um die Normalgleichung A*Af=A*g zu lösen) kleiner als unendlich. Zeige dass f_{n_abbruch} = A⁺g + P_N(A)f₀  gilt.

Problem/Ansatz:

A⁺ beschreibe die Moore-Penrose Inverse, d.h es gilt A⁺g=f⁺ ist die Minimumnormlösung.

Den Anteil aus N(A) können wir zunächst vernachlässigen. Außerdem ist mir auch klar, dass f_{n_abbruch} die Normalgleichung erfüllen muss, aber woher wissen wir, dass es die Lösung ist, die die minimale Norm hat?

Kann mir vielleicht jemand weiterhelfen? Vielen Dank im Voraus!

Answer 1

Rechenweg:

Das cg-Verfahren wird auf die Normalgleichung \( A^{*} A f = A^{*} g \) angewendet. Sei \( f_{0} \) der Startvektor. Die allgemeine Lösung der Normalgleichung ist:
\( f = A^{+} g + z \quad \text{mit} \quad z \in N(A) \)
wobei \( A^{+} g \) die Minimumnormlösung ist.

Krylov-Raum und cg-Eigenschaften:

Das cg-Verfahren sucht die Lösung im affinen Raum \( f_{0} + \mathcal{K}_{m}(A^{*} A, r_{0}) \), wobei \( r_{0} = A^{*} g - A^{*} A f_{0} \). Da \( A^{*} A \) symmetrisch positiv semidefinit ist, findet cg die Lösung mit minimaler Norm in diesem Raum.

Projektion des Startvektors:

Zerlege \( f_{0} \) in \( f_{0} = f_{0}^{\parallel} + f_{0}^{\perp} \), wobei \( f_{0}^{\parallel} \in R(A^{*}) \) und \( f_{0}^{\perp} \in N(A) \). Da \( A^{*} A f_{0}^{\perp} = 0 \), beeinflusst \( f_{0}^{\perp} \) die Iteration nicht und bleibt erhalten:
\( f_{n_{\text{Abbruch}}} = A^{+} g + f_{0}^{\perp} = A^{+} g + P_{N(A)} f_{0}. \)

Minimale Norm:

Die cg-Iterierte minimiert \( |f|_{A^{*} A} \) im Lösungsraum. Da \( A^{+} g \) minimale Norm hat, gilt:
\( f_{n_{\text{Abbruch}}} = A^{+} g + P_{N(A)} f_{0}. \)

Begründung:

Der Anteil \( P_{N(A)} f_{0} \) liegt im Nullraum und bleibt unverändert. Das cg-Verfahren findet die minimale Norm-Lösung im Bildraum \( R(A^{*}) \), also \( A^{+} g \).

Endergebnis:
\( f_{n_{\text{Abbruch}}} = A^{+} g + P_{N(A)} f_{0}. \)