CG-Verfahren < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:21 Di 19.05.2009 | | Autor: | Pacapear |
Hallo zusammen!
Also ich hab mich heute abend jetzt nochmal durch die Herleitung des CG-Verfahrens gekämpft und es auch so ein bisschen verstanden.
Trotzdem hab ich nochmal ein paar Fragen dazu, ich stelle sie mal alle in eigenen Fragen, damit es übersichtlich bleibt.
Ich hab nochmal eine Frage zu den Unterräumen.
Nämlich: Wozu brauch ich diese Dinger?
Also die sehen ja wie folgt aus: [mm] U_k=span\{p^0,p^1,...,p^{k-2},r^{k-1}\}
[/mm]
Und die Basis davon ist [mm] \{p^0,p^1,...,p^{k-1}\}.
[/mm]
Also ich verstehe absolut nicht, wofür ich diese Unterräume brauche. Ich brauche doch eigentlich nur die Basisvektoren [mm] p^i [/mm] des Unterraums um [mm] x^{k+1} [/mm] zu berechnen. Und für die Berechnung von [mm] p^i [/mm] hab ich eine Formel. Wofür brauch ich diesen ganzen Kram mit dem [mm] span\{...\} [/mm] und was bedeutet das überhaupt? Wenn ich eine Formel für [mm] p^i [/mm] hab, kann es mir doch dann egal sein, wie [mm] U_k [/mm] genau aussieht, oder?
Auch dass ich dann mit jedem Schritt meinen Unterraum erweitere, ich sehe darin überhaupt keinen Sinn ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
Vielleicht kann mir jemand weiter helfen?
LG, Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:55 Mi 20.05.2009 | | Autor: | Marcel |
Hallo Nadine,
> Hallo zusammen!
>
> Also ich hab mich heute abend jetzt nochmal durch die
> Herleitung des CG-Verfahrens gekämpft und es auch so ein
> bisschen verstanden.
>
> Trotzdem hab ich nochmal ein paar Fragen dazu, ich stelle
> sie mal alle in eigenen Fragen, damit es übersichtlich
> bleibt.
>
> Ich hab nochmal eine Frage zu den Unterräumen.
>
> Nämlich: Wozu brauch ich diese Dinger?
>
> Also die sehen ja wie folgt aus:
> [mm]U_k=span\{p^0,p^1,...,p^{k-2},r^{k-1}\}[/mm]
>
> Und die
eine!!! Beachte: Basen sind nicht eindeutig!
> Basis davon ist [mm]\{p^0,p^1,...,p^{k-1}\}.[/mm]
>
> Also ich verstehe absolut nicht, wofür ich diese Unterräume
> brauche. Ich brauche doch eigentlich nur die Basisvektoren
> [mm]p^i[/mm] des Unterraums um [mm]x^{k+1}[/mm] zu berechnen.
Das ist doch genau der theoretische Teil dieses Verfahrens, mit dem man argumentiert. Das CG-Verfahren wird ja angewendet auf ein Problem
[mm] $$(I)\;\;\;Ax=b$$
[/mm]
bzw.
[mm] $$(II)\;\;\;\min\limits_{x \in \IR^n}\;\;\; \frac{1}{2}x^T [/mm] A [mm] x-b^Tx\,,$$
[/mm]
wobei die Matrix [mm] $A\,$ [/mm] positiv definit sei. (Das ist deshalb wichtig, weil dann die beiden Probleme $(I)$ und $(II)$ äquivalent sind, was hier heißt, dass sie die gleiche Lösung [mm] $x\,$ [/mm] haben).
Wenn Du nun die [mm] $p^0,\,\ldots,\,p^{k-1}$ [/mm] in eine Matrix schreibst, ich nenne sie mal [mm] $P_k\,,$ [/mm] so ist [mm] $U_k=\text{span}\{p^0,\,\ldots,\,p^{k-1}\}=\left\{P_k w: w \in \IR^{k}\right\}=\text{Bild}P_k\,.$
[/mm]
(Beachte: [mm] $P_k$ [/mm] ist ja eine (lineare) Abbildung [mm] $\IR^k \to \IR^n\,.$)
[/mm]
Und beim Schritt $k-1 [mm] \mapsto [/mm] k$ hast Du ja für [mm] $x^{k}$ [/mm] sicher eine Formel der Art
[mm] $$x^{k}=x^{k-1}+P_k w^{k-1}\,.$$
[/mm]
Dabei wird [mm] $w^{k-1}$ [/mm] definiert als
[mm] $$w^{k-1}:=\text{argmin}\limits_{w \in \IR^k}\;\;\; \frac{1}{2}(x^{k-1}+P_k w)^T [/mm] A [mm] (x^{k-1}+P_k w)-b^T(x^{k-1}+P_k w)\,.$$
[/mm]
[mm] $\text{(}$Anders [/mm] ausgedrückt:
[mm] $w^{k-1}$ [/mm] ist die Lösung des Minimierungsproblems
[mm] $$\min\limits_{x \in \IR^n}\;\;\;\frac{1}{2}x^T [/mm] A [mm] x-b^T [/mm] x$$
[mm] $$\text{s.t. } x=x^{k-1}+P_k w\;\;\text{ mit einem }w \in \IR^k\text{)}\,.$$
[/mm]
Nach ein paar Umformungen gelangst Du (da Konstanten bei einem Minimierungsproblem vernachlässigbar sind) zu
[mm] $$w^{k-1}:=\text{argmin}\limits_{w \in \IR^k}\;\;\;\frac{1}{2}w^T P_k^T [/mm] A [mm] P_k [/mm] w [mm] +(Ax^{k-1}-b)^T P_k w\,.$$
[/mm]
Und die Lösung [mm] $w^{k-1} \in \IR^k$ [/mm] des Problems
[mm] $$\min\limits_{w \in \IR^k}\;\;\;\frac{1}{2}w^T P_k^T [/mm] A [mm] P_k [/mm] w [mm] +(Ax^{k-1}-b)^T P_k [/mm] w$$
kann man direkt angeben.
(Hinweis dazu:
Welche Eigenschaft hat die Matrix [mm] $\tilde{A}:=P_k^T [/mm] A [mm] P_k \in \IR^{k \times k}\,,$ [/mm] wenn [mm] $A\,$ [/mm] als positiv definit vorausgesetzt wurde?)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:07 Mi 20.05.2009 | | Autor: | Pacapear |
Hallo Marcel!
Vielen Dank für deine Mühe. Leider bereitet mir auch diese Antwort wieder tierisch Kopfzerbrechen, ich komme mit diesem ganzen Verfahren überhaupt nicht zurecht, und schon gar nicht mit der Theorie dahinter...
> Das ist doch genau der theoretische Teil dieses Verfahrens,
> mit dem man argumentiert. Das CG-Verfahren wird ja
> angewendet auf ein Problem
> [mm](I)\;\;\;Ax=b[/mm]
> bzw.
> [mm](II)\;\;\;\min\limits_{x \in \IR^n}\;\;\; \frac{1}{2}x^T A x-b^Tx\,,[/mm]
>
> wobei die Matrix [mm]A\,[/mm] positiv definit sei. (Das ist deshalb
> wichtig, weil dann die beiden Probleme [mm](I)[/mm] und [mm](II)[/mm]
> äquivalent sind, was hier heißt, dass sie die gleiche
> Lösung [mm]x\,[/mm] haben).
OK, das versteh ich.
> Wenn Du nun die [mm]p^0,\,\ldots,\,p^{k-1}[/mm] in eine Matrix
> schreibst, ich nenne sie mal [mm]P_k\,,[/mm] so ist
> [mm]U_k=\text{span}\{p^0,\,\ldots,\,p^{k-1}\}=\left\{P_k w: w \in \IR^{k}\right\}=\text{Bild}P_k\,.[/mm]
>
> (Beachte: [mm]P_k[/mm] ist ja eine (lineare) Abbildung [mm]\IR^k \to \IR^n\,.[/mm])
Ähm, das verstehe ich schon nicht mehr. Also wenn ich das richtig verstanden habe, dann ist doch [mm] \text{span}\{p^0,\,\ldots,\,p^{k-1}\} [/mm] die Menge aller Linearkombinationen von [mm] \{p^0,\,\ldots,\,p^{k-1}\}, [/mm] warum ist das das gleiche wie das Bild der Matrix, wenn ich diese auf einen Vektor anwende? Das ist ja Matrixmultiplikation, die ich da machen würde, der Ergebnisvektor kann doch nicht alle Linearkombinationen der [mm] p^i [/mm] enthalten, oder?
> Und beim Schritt [mm]k-1 \mapsto k[/mm] hast Du ja für [mm]x^{k}[/mm] sicher
> eine Formel der Art
> [mm]x^{k}=x^{k-1}+P_k w^{k-1}\,.[/mm]
Hmm, naja, so ähnlich. Ich hab [mm] x^{k}=x^{k-1}+\alpha_{k-1}*p^{k-1}. [/mm] Dabei ist [mm] \alpha_{k-1} [/mm] die Schrittweite, und [mm] p^{k-1} [/mm] ist die Richtung in die ich laufe. Also hab ich in meiner Formel nur ein [mm] p^i [/mm] und nicht eine ganze Matrix voll mit denen.
> Dabei wird [mm]w^{k-1}[/mm] definiert als
> [mm]w^{k-1}:=\text{argmin}\limits_{w \in \IR^k}\;\;\; \frac{1}{2}(x^{k-1}+P_k w)^T A (x^{k-1}+P_k w)-b^T(x^{k-1}+P_k w)\,.[/mm]
![[haee]](/images/smileys/haee.gif "[haee]")
> [mm]\text{(}[/mm]Anders ausgedrückt:
> [mm]w^{k-1}[/mm] ist die Lösung des Minimierungsproblems
> [mm]\min\limits_{x \in \IR^n}\;\;\;\frac{1}{2}x^T A x-b^T x[/mm]
>
> [mm]\text{s.t. } x=x^{k-1}+P_k w\;\;\text{ mit einem }w \in \IR^k\text{)}\,.[/mm]
Oweh, jetzt hörts leider ganz auf bei mir... Ich dachte, [mm] x^{opt} [/mm] wäre die Lösung des Minimierungsproblems, wobei [mm] x^{opt} [/mm] das [mm] x^k [/mm] ist, für das dann gilt [mm] x^k=x^{k+1}, [/mm] also wo es dann konvergiert...
> Nach ein paar Umformungen gelangst Du (da Konstanten bei
> einem Minimierungsproblem vernachlässigbar sind) zu
> [mm]w^{k-1}:=\text{argmin}\limits_{w \in \IR^k}\;\;\;\frac{1}{2}w^T P_k^T A P_k w +(Ax^{k-1}-b)^T P_k w\,.[/mm]
>
> Und die Lösung [mm]w^{k-1} \in \IR^k[/mm] des Problems
> [mm]\min\limits_{w \in \IR^k}\;\;\;\frac{1}{2}w^T P_k^T A P_k w +(Ax^{k-1}-b)^T P_k w[/mm]
>
> kann man direkt angeben.
> (Hinweis dazu:
> Welche Eigenschaft hat die Matrix [mm]\tilde{A}:=P_k^T A P_k \in \IR^{k \times k}\,,[/mm]
> wenn [mm]A\,[/mm] als positiv definit vorausgesetzt wurde?)
Ich habe ehrlich gesagt nicht die geringste Ahnung
Also mein Problem ist auch, dass so zu diesem ganzen Hintergrund in meiner Vorlesungsmitschrift überhaupt nix steht. Da steht nur, dass wir ne bessere Abstiegsrichtung als beim herkömmlichen Gradientenverfahren suchen, und das wars. Dann kommen nur noch Formeln und Folgerungen, und am Ende steht der Algorithmus, denn man berechnen muss.
Ich hab mir das Ganze jetzt versucht, mit dem Buch von Dahmen/Reusken (siehe anderer Post, wo deine Frage zu meinem Buch war) ein bisschen anzulesen, aber da steht auch eher nur die Herleitung der Formel drin, als ausfühlich was zum Hintergrund. Da steht mal in einem Satz, dass man wiederholt Minimierungen in einem eingeschränkten Unterraum durchführt, aber das wars (glaub ich) auch schon. Also ich hab zumindest nix gefunden, was mir da zum Verständnis weiter hilft.
Oh man, es tut mir ganz schrecklich leid, dass ich auf diesem Gebiet so begriffsstutzig bin und du soviel Mühe mit mir hast...
Könntest du mir vielleicht mal in ein paar mathematik-freien Sätzen versuchen zu erklären, was so grob die theoretische Idee hinter dem Ganzen ist?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:13 Mi 20.05.2009 | | Autor: | Marcel |
Hallo,
> Hallo Marcel!
>
> Vielen Dank für deine Mühe. Leider bereitet mir auch diese
> Antwort wieder tierisch Kopfzerbrechen, ich komme mit
> diesem ganzen Verfahren überhaupt nicht zurecht, und schon
> gar nicht mit der Theorie dahinter...
>
>
>
> > Das ist doch genau der theoretische Teil dieses Verfahrens,
> > mit dem man argumentiert. Das CG-Verfahren wird ja
> > angewendet auf ein Problem
> > [mm](I)\;\;\;Ax=b[/mm]
> > bzw.
> > [mm](II)\;\;\;\min\limits_{x \in \IR^n}\;\;\; \frac{1}{2}x^T A x-b^Tx\,,[/mm]
>
> >
> > wobei die Matrix [mm]A\,[/mm] positiv definit sei. (Das ist deshalb
> > wichtig, weil dann die beiden Probleme [mm](I)[/mm] und [mm](II)[/mm]
> > äquivalent sind, was hier heißt, dass sie die gleiche
> > Lösung [mm]x\,[/mm] haben).
>
> OK, das versteh ich.
>
>
>
> > Wenn Du nun die [mm]p^0,\,\ldots,\,p^{k-1}[/mm] in eine Matrix
> > schreibst, ich nenne sie mal [mm]P_k\,,[/mm] so ist
> > [mm]U_k=\text{span}\{p^0,\,\ldots,\,p^{k-1}\}=\left\{P_k w: w \in \IR^{k}\right\}=\text{Bild}P_k\,.[/mm]
>
> >
> > (Beachte: [mm]P_k[/mm] ist ja eine (lineare) Abbildung [mm]\IR^k \to \IR^n\,.[/mm])
>
> Ähm, das verstehe ich schon nicht mehr. Also wenn ich das
> richtig verstanden habe, dann ist doch
> [mm]\text{span}\{p^0,\,\ldots,\,p^{k-1}\}[/mm] die Menge aller
> Linearkombinationen von [mm]\{p^0,\,\ldots,\,p^{k-1}\},[/mm] warum
> ist das das gleiche wie das Bild der Matrix, wenn ich diese
> auf einen Vektor anwende? Das ist ja Matrixmultiplikation,
> die ich da machen würde, der Ergebnisvektor kann doch nicht
> alle Linearkombinationen der [mm]p^i[/mm] enthalten, oder?
doch, das Bild von [mm] $P_k$ [/mm] ist die Menge aller Linearkombinationen der Spalten von [mm] $P_k\,.$ [/mm] Das ist ein Standardergebnis aus der linearen Algebra, was man eigentlich verinnerlicht haben sollte. Es erklärt sich aus der Definition des Matrix-Vektor-Produktes (![[]](/images/popup.gif) vgl. z.B. hier, Seite 57, wobei Du bitte beachtest, dass ein Spaltenvektor aus [mm] $n\,$ [/mm] Komponenten nichts anderes als eine $n [mm] \times [/mm] 1$-Matrix ist) und wegen der Komponentenweisen Addition.
Mal an einem einfachen Beispiel demonstriert, wieso das so ist:
Es gilt
[mm] $$\text{Bild} \pmat{a_{11} & a_{12} & a_{13} & a_{14}\\a_{21} & a_{22} & a_{23} & a_{24}}=\left\{\pmat{a_{11} & a_{12} & a_{13} & a_{14}\\a_{21} & a_{22} & a_{23} & a_{24}}*\vektor{\lambda_1\\\lambda_2\\\lambda_3\\\lambda_4}:\;\; \lambda_{1},\;\lambda_2,\;\lambda_3,\;\lambda_4 \in \IR\right\}$$
[/mm]
[mm] $$=\left\{\pmat{\lambda_1 a_{11}+ \lambda_2 a_{12} + \lambda_3 a_{13} + \lambda_4 a_{14}\\ \lambda_1 a_{21} +\lambda_2 a_{22} +\lambda_3 a_{23} +\lambda_4a_{24}}:\;\;\lambda_1,\;\lambda_2,\;\lambda_3,\;\lambda_4 \in \IR\right\}$$
[/mm]
[mm] $$=\left\{\lambda_1 \vektor{a_{11}\\a_{21}}+\lambda_2 \vektor{a_{12}\\a_{22}}+\lambda_3 \vektor{a_{13}\\a_{23}}+\lambda_1 \vektor{a_{14}\\a_{24}}:\;\;\;\lambda_1,\;\lambda_2,\;\lambda_3,\;\lambda_4 \in \IR\right\}=\text{span}\left\{\vektor{a_{11}\\a_{21}},\;\vektor{a_{12}\\a_{22}},\;\vektor{a_{13}\\a_{23}},\;\vektor{a_{14}\\a_{24}}\right\}$$
[/mm]
> > Und beim Schritt [mm]k-1 \mapsto k[/mm] hast Du ja für [mm]x^{k}[/mm] sicher
> > eine Formel der Art
> > [mm]x^{k}=x^{k-1}+P_k w^{k-1}\,.[/mm]
>
> Hmm, naja, so ähnlich. Ich hab
> [mm]x^{k}=x^{k-1}+\alpha_{k-1}*p^{k-1}.[/mm] Dabei ist [mm]\alpha_{k-1}[/mm]
> die Schrittweite, und [mm]p^{k-1}[/mm] ist die Richtung in die ich
> laufe. Also hab ich in meiner Formel nur ein [mm]p^i[/mm] und nicht
> eine ganze Matrix voll mit denen.
>
>
>
> > Dabei wird [mm]w^{k-1}[/mm] definiert als
> > [mm]w^{k-1}:=\text{argmin}\limits_{w \in \IR^k}\;\;\; \frac{1}{2}(x^{k-1}+P_k w)^T A (x^{k-1}+P_k w)-b^T(x^{k-1}+P_k w)\,.[/mm]
>
>
Na okay, wenn ihr das CG-Verfahren anders definiert/hergeleitet habt, dann kannst Du das (jedenfalls so auf die Schnelle) nicht verstehen.
>
>
> > [mm]\text{(}[/mm]Anders ausgedrückt:
> > [mm]w^{k-1}[/mm] ist die Lösung des Minimierungsproblems
> > [mm]\min\limits_{x \in \IR^n}\;\;\;\frac{1}{2}x^T A x-b^T x[/mm]
>
> >
> > [mm]\text{s.t. } x=x^{k-1}+P_k w\;\;\text{ mit einem }w \in \IR^k\text{)}\,.[/mm]
>
> Oweh, jetzt hörts leider ganz auf bei mir... Ich dachte,
> [mm]x^{opt}[/mm] wäre die Lösung des Minimierungsproblems, wobei
> [mm]x^{opt}[/mm] das [mm]x^k[/mm] ist, für das dann gilt [mm]x^k=x^{k+1},[/mm] also wo
> es dann konvergiert...
>
>
>
> > Nach ein paar Umformungen gelangst Du (da Konstanten bei
> > einem Minimierungsproblem vernachlässigbar sind) zu
> > [mm]w^{k-1}:=\text{argmin}\limits_{w \in \IR^k}\;\;\;\frac{1}{2}w^T P_k^T A P_k w +(Ax^{k-1}-b)^T P_k w\,.[/mm]
>
> >
> > Und die Lösung [mm]w^{k-1} \in \IR^k[/mm] des Problems
> > [mm]\min\limits_{w \in \IR^k}\;\;\;\frac{1}{2}w^T P_k^T A P_k w +(Ax^{k-1}-b)^T P_k w[/mm]
>
> >
> > kann man direkt angeben.
>
>
>
>
>
> > (Hinweis dazu:
> > Welche Eigenschaft hat die Matrix [mm]\tilde{A}:=P_k^T A P_k \in \IR^{k \times k}\,,[/mm]
> > wenn [mm]A\,[/mm] als positiv definit vorausgesetzt wurde?)
>
> Ich habe ehrlich gesagt nicht die geringste Ahnung
>
Die ist dann auch positiv definit. Das ergibt sich sofort so:
Für beliebiges $y [mm] \in \IR^k \setminus \{0\}$ [/mm] gilt
[mm] $$y^T \tilde{A}y=y^T P_k^T [/mm] A [mm] \underbrace{P_k y}_{=:x \in \IR^n}=(P_k y)^T [/mm] A [mm] (P_k y)=x^T [/mm] A x > [mm] 0\,,$$
[/mm]
da $A$ nach Voraussetzung positiv definit ist; zudem ist zu beachten, dass [mm] $x=P_k [/mm] y [mm] \not=0$ [/mm] ist. Kannst Du das begründen (also, dass [mm] $x=P_k [/mm] y [mm] \not=0$ [/mm] ist)? Beachte dazu:
Es war $y [mm] \in \IR^k \setminus \{0\}$ [/mm] und [mm] $P_k: \IR^k \to \IR^n$ [/mm] ist injektiv. (Wieso ist [mm] $P_k$ [/mm] injektiv?)
Was bedeutet das für die Hessematrix der Funktion [mm] $\IR^k \to \IR,\;w \mapsto \frac{1}{2}w^T P_k^T [/mm] A [mm] P_k [/mm] w [mm] +(Ax^{k-1}-b)^T P_k [/mm] w$?
Und:
An welcher Stelle verschwindet der Gradient von $w [mm] \mapsto \frac{1}{2}w^T P_k^T [/mm] A [mm] P_k [/mm] w [mm] +(Ax^{k-1}-b)^T P_k [/mm] w$? Was weißt Du damit nun?
> Also mein Problem ist auch, dass so zu diesem ganzen
> Hintergrund in meiner Vorlesungsmitschrift überhaupt nix
> steht. Da steht nur, dass wir ne bessere Abstiegsrichtung
> als beim herkömmlichen Gradientenverfahren suchen, und das
> wars. Dann kommen nur noch Formeln und Folgerungen, und am
> Ende steht der Algorithmus, denn man berechnen muss.
Kannst Du das Skript mal verlinken? Dann können wir (und evtl. auch andere) mal konkreter die Stellen begutachten, die Dir Schwierigkeiten bereiten, insbesondere haben wir die gleichen Grundlagen zur Orientierung.
> Ich hab mir das Ganze jetzt versucht, mit dem Buch von
> Dahmen/Reusken (siehe anderer Post, wo deine Frage zu
> meinem Buch war) ein bisschen anzulesen, aber da steht auch
> eher nur die Herleitung der Formel drin, als ausfühlich was
> zum Hintergrund. Da steht mal in einem Satz, dass man
> wiederholt Minimierungen in einem eingeschränkten Unterraum
> durchführt,
Dann schau' vielleicht nochmal oben die Definition des [mm] $w^{k-1}$ [/mm] an.
> aber das wars (glaub ich) auch schon. Also ich
> hab zumindest nix gefunden, was mir da zum Verständnis
> weiter hilft.
>
> Oh man, es tut mir ganz schrecklich leid, dass ich auf
> diesem Gebiet so begriffsstutzig bin und du soviel Mühe mit
> mir hast...
>
> Könntest du mir vielleicht mal in ein paar
> mathematik-freien Sätzen versuchen zu erklären, was so grob
> die theoretische Idee hinter dem Ganzen ist?
Also erstmal ein Link:
CG-Verfahren, Berlin.
Der ist wirklich ausführlich, natürlich vll. auch entsprechend anstrengend durchzuarbeiten.
Etwas verständlicher ist dann vll. dieser Link, und zur Idee steht bei Wiki: hier etwas. Das in mathematikfreien Sätzen zu formulieren halte ich zum einen für nicht besonders sinnvoll, da es dann sicher schnell zu Missverständnissen kommt, zum anderen auch für so gut wie unmöglich, da man definitiv Begriffe wie 'affiner Raum' oder 'Unterraum' braucht, um eine einigermaßen verständliche Erklärung des Verfahrens zu formulieren.
Empfehlen kann ich Dir dann gerade auch das Buch Numerical Optimizations, von Nocedal/Wright und Numerische Mathematik von Schwarz, Köckler.
Und vielleicht ist das hier ja auch für Dich interessant:
Link 1.
Was man beim CG-Verfahren aber auf jeden Fall wissen sollte:
Es ist eine 3-Term-Rekursion (d.h. man braucht nur 3 Vektoren abzuspeichern), hat also weniger Speicheraufwand als andere Verfahren und es endet, wenn [mm] $A\,$ [/mm] eine (symmetrische, positiv definite) $n [mm] \times [/mm] n$-Matrix ist, nach spätestens [mm] $n\,$ [/mm] Schritten (denn dann bilden [mm] $p^0,\;\ldots,p^{n-1}$ [/mm] eine Basis des [mm] $\IR^n$). [/mm] Wenn Du nochmal drüber nachdenkst, dass der Gaußalgorithmus [mm] $n+n-1+...=n^2/2 [/mm] +(n-1)$ benötigen kann, ist das sicherlich um einiges schneller und effizienter.
Gruß,
Marcel
|
|
|
| |
|
Hallo Marcel!
Puh, ist das alles kompliziert, ich hasse dieses Thema...
> > Also mein Problem ist auch, dass so zu diesem ganzen
> > Hintergrund in meiner Vorlesungsmitschrift überhaupt nix
> > steht. Da steht nur, dass wir ne bessere Abstiegsrichtung
> > als beim herkömmlichen Gradientenverfahren suchen, und das
> > wars. Dann kommen nur noch Formeln und Folgerungen, und am
> > Ende steht der Algorithmus, denn man berechnen muss.
> Kannst Du das Skript mal verlinken? Dann können wir (und
> evtl. auch andere) mal konkreter die Stellen begutachten,
> die Dir Schwierigkeiten bereiten, insbesondere haben wir
> die gleichen Grundlagen zur Orientierung.
Das Skript steht leider nicht online, das gab es nur als Tafelanschrieb.
> > Ich hab mir das Ganze jetzt versucht, mit dem Buch von
> > Dahmen/Reusken (siehe anderer Post, wo deine Frage zu
> > meinem Buch war) ein bisschen anzulesen, aber da steht auch
> > eher nur die Herleitung der Formel drin, als ausfühlich was
> > zum Hintergrund. Da steht mal in einem Satz, dass man
> > wiederholt Minimierungen in einem eingeschränkten Unterraum
> > durchführt,
> Dann schau' vielleicht nochmal oben die Definition des
> [mm]w^{k-1}[/mm] an.
Hmm...
> > Könntest du mir vielleicht mal in ein paar
> > mathematik-freien Sätzen versuchen zu erklären, was so grob
> > die theoretische Idee hinter dem Ganzen ist?
> Also erstmal ein Link:
>
> CG-Verfahren, Berlin.
>
> Etwas verständlicher ist dann vll.
> dieser Link,
> und zur Idee steht
> bei Wiki: hier
> etwas.
> Und vielleicht ist das hier ja auch für Dich interessant:
>
> Link 1.
Also im Moment bin ich so weit:
Diese Iterierten [mm] x_k, [/mm] dass sind immer die Minima des Funktionals f, wenn ich das Minumum von f nicht im ganzen Definitionsraum [mm] \IR^n [/mm] suche, sondern nur in den Unterräumen [mm] U_k. [/mm] Ist das so richtig?
Und wenn diese [mm] x_k [/mm] nicht das Minimum treffen, so sind sie aber die beste Annäherung von meinem Optimum-Minimum-x in diesem Unterraum, richtig (warum?)?
Aber was genau heißt es, eine Funktion in/über einen Unterraum zu minimieren? Heißt dass, ich habe weniger Werte in meinem Definitionsbereich für f, weil die [mm] U_k [/mm] ja immer eine Teilmenge des Definitionsbereichs [mm] \IR^n [/mm] sind?
So, aber irgendwie hab ich trotzdem immer noch ein Problem mit diesen Unterräumen. Warum so komische Formeln? Warum diese Basisvektoren [mm] p^k [/mm] ? Warum sind diese Unterräume dieser Spann? Könnte ich meine Iterierten nicht auch anders finden? Könnte ich das Minimum von f nicht direkt berechnen (1. Ableitung usw.)?
> und zur Idee steht
> bei Wiki: hier
> etwas.
Bei Wiki hab ich mit folgendem Probleme: Dort wird der Unterraum nicht als Spann der Vektoren [mm] p^i [/mm] und r definiert wie bei uns, sondern so seltsam mit [mm] x_0 [/mm] + den Spann der [mm] p^i. [/mm] Ist das das gleiche?
> Was man beim CG-Verfahren aber auf jeden Fall wissen
> sollte:
> Es ist eine 3-Term-Rekursion (d.h. man braucht nur 3
> Vektoren abzuspeichern), hat also weniger Speicheraufwand
> als andere Verfahren und es endet, wenn [mm]A\,[/mm] eine
> (symmetrische, positiv definite) [mm]n \times n[/mm]-Matrix ist,
> nach spätestens [mm]n\,[/mm] Schritten (denn dann bilden
> [mm]p^0,\;\ldots,p^{n-1}[/mm] eine Basis des [mm]\IR^n[/mm]). Wenn Du nochmal
> drüber nachdenkst, dass der Gaußalgorithmus [mm]n+n-1+...=n^2/2 +(n-1)[/mm]
> benötigen kann, ist das sicherlich um einiges schneller und
> effizienter.
Diese drei Vektoren, sind das [mm] x^k, p^k [/mm] und [mm] r^k [/mm] ? Ja, den Rest weiß ich, dass CG-Verfahren konvergiert nach spätestens n Schritten bei (n,n)-Matrizen. Aber der Vorteil bei Gauß ist, dass er auch für nicht spd-Matrizen funktioniert, oder? Cholesky-Zerlegung wäre doch speziell für spd-Matrizen, aber das ist auch langsamer als CG, oder?
LG, Nadine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Mo 22.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hallo Marcel!
Ich arbeite grade das ausführliche Skript durch:
> CG-Verfahren, Berlin.
Zu Formel (5.59) hab ich da mal eine Frage.
Das ist ja einfach nur die Formel aus dem normalen Gradientenverfahren, allerdings komme ich bei der dort verwendeten Notation ziemlich durcheinander.
Ich "übersetze" die Vektorenbenennung mal in meine Benennung, dann lautet die Formel:
[mm] x^1=x^0-\alpha^1*grad(F(x^0))
[/mm]
Da steht also, dass zur Berechnung des x im ersten Schritt das x aus dem vorherigen nullten Schritt verwendet wird, aber das [mm] \alpha [/mm] aus dem aktuellen ersten Schritt.
Irgendwie verwirrt mich das grade, das [mm] \alpha [/mm] aus dem ersten Schritt kenne ich doch noch gar nicht, ich brauche doch erstmal das aus dem nullten Schritt, oder?
Oder steh ich grad völlig auf'm Schlach und seh echt vor lauter Bäumen den Wald nicht mehr?
Dieses Problem tritt auch in den später folgenden Formeln wieder auf, dass zur Berechnung des k-ten Schrittes Werte benutzt werden, die eigentlich auch erst im k-ten Schritt berechnet werden, oder seh ich das grad irgendwie falsch?
Ich geh jetzt nochmal eine Formel weiter, wo ich hänge.
Da steht zu den ersten beiden Formel von (5.61), dass folgende Beziehungen gelten (in meiner Übersetzung):
1) [mm] r^k=A*x^{k-1}+\alpha*A*p^k+b=r^{k-1}+\alpha*A*p^k
[/mm]
2) [mm] r^{k+1}=A*x^k+\alpha*A*p^{k+1}+b=r^k+\alpha*A*p^{k+1}=A*x^{k+1}+b
[/mm]
Die beiden Beziehungen sind analog (steht da).
Jetzt meine Fragen dazu:
a) Warum gelten diese Beziehungen? Wo kommen diese Berechnungsformeln her, wie haben vorher doch nur die für den ersten (aber wie dort gesagt wird) anderen Schritt gegeben.
b) Wieder das Problem wie oben: Zur Berechnung von [mm] r^k [/mm] benutze ich [mm] r^{k-1} [/mm] (also das aus dem Schritt vorher), aber [mm] p^k [/mm] (also das aus dem aktuellen Schritt)?
c) Aus welchen Schritt stammt [mm] \alpha [/mm] ?
d) Wenn [mm] r^{k+1}=A*x^{k+1}+b [/mm] (2), gilt dann bei (1) auch [mm] r^{k}=A*x^{k}+b [/mm] , also normale Berechnung des Gradienten von f?
LG, Nadine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Mo 22.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hallo Marcel, schon wieder ich...
Ich bin im Wiki-Artikel grade über folgenden Satz gestolpert:
Das Verfahren baut sukzessive eine A-orthogonale Basis für den [mm] \mathbb R^m [/mm] auf und minimiert in die jeweilige Richtung bestmöglich.
Was heißt das genau?
Was bedeutet es, in eine Richtung bestmöglichst zu minimieren?
Wie kann man in eine Richtung minimieren?
Heißt das, ich gehe in die Richtung soweit, dass ich nicht zu weit gehe, um möglichst schnell im Minimum zu landen?
Heißt dass, das ich in jede Richtung nur einmal gehe, nämlich in jedem Schritt in die Richtung, dessen Basisvektor ich in diesem Schritt hinzugefügt habe?
UNd wenn ich in n Basisvektoren-Richtungen gegangen bin, dann bin ich in alle aufspannenden Richtungen des [mm] \IR^n [/mm] gegangen, hab n Schritte gemacht, und bin fertig?
Noch eine generelle Frage zu den Richtungen:
Bei Wiki steht ja, dass ich beim CG-Verfahren nicht in die Richtung des Gradienten r gehe, sondern in die Richtung der p-Vektoren. Wofür brauche ich dann überhaupt noch den Gradienten?
LG, Nadine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Mo 22.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
