CG-Verfahren < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:04 So 01.03.2009 | | Autor: | Pacapear |
Hallo zusammen!
Da ich ja schon tierische Probleme mit dem normalen Gradientenverfahren habe, wirds beim CG-Verfahren nicht besser.
Ich lese in meiner Aufzeichnung, in 2 Büchern und im Netz, aber ich verstehe nur Bahnhof ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
Das einzige, was ich bisher mitbekommen habe, ist, dass man eine bessere Abstiegsrichtung sucht, die schneller ist als beim Gradientenverfahren. Die soll dann irgendwie nur noch von im Verfahren berechneten Werten abhängen oder so (also nicht mehr von [mm]\ A[/mm] und [mm]\ b[/mm] aus dem LGS [mm]\ Ax=b[/mm] glaub ich).
Ja, und dann gehts wohl noch um Orthogonalität und irgendwelche Unterräume...
Kann mir vielleicht jemand einen Crash-Kurs zu diesem Thema geben? Hab bald Vordiploms-Prüfung und würd gern ein bisschen was zu dem Thema sagen können.
LG, Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:41 So 05.04.2009 | | Autor: | Infinit |
Hallo Nadine,
einen schönen Einführungsartikel habe ich ![[]](/images/popup.gif) hier gefunden.
Viel erfolg beim Durcharbeiten,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:21 So 05.04.2009 | | Autor: | Pacapear |
Vielen Dank, den werde ich mir mal zu Gemüte führen  .
LG, Nadine
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:31 Fr 15.05.2009 | | Autor: | Pacapear |
Hallo zusammen!
Ich hab jetzt ein bisschen mit diesem Thema pausiert, weil ich überhaupt nicht weitergekommen bin, aber jetzt lässt es sich nicht mehr länger rausschieben...
Ich habe mir jetzt auch mal diesen Einführungsartikel durchgelesen, aber auch der hilft mir nicht weiter, ich verstehe bei diesem Thema echt nur Bahnhof ![[haee]](/images/smileys/haee.gif "[haee]")
Im Moment weiß ich soviel:
Ich brauche irgendwelche Unterräume [mm] U_k [/mm] mit irgendwelchen Basisvektoren [mm] p_k, [/mm] und mit diesen Basisvektoren kann ich dann wohl irgendwie mein neues [mm] x^k [/mm] ausrechnen. Und diese Basisvektoren sind A-konjugiert (also jeweils zwei Basisvektoren stehen bzgl. einer Norm zueinander senkrecht, oder?).
Zu diesem Unterräumen mit den Basisvektoren hab ich schonmal tausend Fragen. Ich fang einfach mal an:
1) Diese Unterräume, welche Dimension haben die? Zum Beispiel treten ja in der Berechnung von [mm] x^k [/mm] die [mm] p^k [/mm] auf, und da muss ja dann die Dimension gleich sein, sonst gehts ja nicht. Ich kann ja nicht Vektoren mit unterschiedlicher Komponentenanzahl miteinander verrechnen. Also müssen diese Unterräume [mm] U_k [/mm] auch Dimension n haben?
2) Ich habe in meinem Buch einen Satz, der sagt, dass die Dimension von [mm] U_k [/mm] nicht n ist. Da steht: " [mm] U_k [/mm] ist k-dimensionaler Teilraum von [mm] \IR^n [/mm] mit A-orthogonaler Basis [mm] p^0,p^1,...,p^{k-1}. [/mm] Sei [mm] v\in\IR^n [/mm] , dann gilt für [mm] u^k\in{U_k} [/mm] : [mm] ||u^k-v||_A=min_{u\in{U_k}}||u-v||_A \gdw... [/mm] ."
Ich versteh überhaupt nicht, wie das gehen soll. Wenn k sagen wir mal 2 ist, dann ist [mm] U_2 [/mm] 2-dimensional, [mm] u^2 [/mm] ist Element von [mm] U_2, [/mm] also hat zwei Komponenten. Wie soll ich dann diese Norm berechnen, ich kann doch nicht die Differenz von einem Zwei-Komponenten-Vektor mit einem n-Komponenten-Vektor bilden...
Kann es vielleicht sein, dass ich ein völlig falsches Verständnis von Dimension hab? Ich dachte immer, Dimension (bei Vektorräumen) ist gleich der Anzahl der Komponenten der Vektoren in diesem Vektorraum.
Oh man, ich versteh echt überhaupt nix... Ich bin echt für jede noch so kleine Hilfe dankbar, damit ich nur ein kleines bisschen mehr verstehe *verzweifel*
Vielen Dank schonmal für eure Mühe!
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:50 Fr 15.05.2009 | | Autor: | Marcel |
Hallo Nadine,
> Kann es vielleicht sein, dass ich ein völlig falsches
> Verständnis von Dimension hab? Ich dachte immer, Dimension
> (bei Vektorräumen) ist gleich der Anzahl der Komponenten
> der Vektoren in diesem Vektorraum.
ja, Du hast ein völlig falsches Verständnis dieses Begriffes. Die Dimension eines Raumes ist (in endlichdimensionalen Räumen) gerade gleich der maximalen Anzahl linear unabhängiger Vektoren dieses Raumes, was hier das gleiche ist wie die minimale Anzahl von den Raum aufspannenden Vektoren.
Das ist etwas völlig anderes. (Jedenfalls, wenn man nicht aufpasst, dass sich die Koordinatenabbildungen, wenn man mit diesen Dimensionen eines Raumes feststellen will, bzgl. des jeweils betrachteten (Unter-)Raumes aufzufassen sind. Dazu siehe z.B. [mm] $(\star)$, [/mm] unten.)
Z.B.:
Für
[mm] $$\left\{\vektor{x_1\\x_2\\x_3} \in \IR^3:\;x_3=0,\;x_1,x_2 \in \IR \right\}$$
[/mm]
als [mm] $\IR$-Vektorraum [/mm] kann man die Basis [mm] $\left\{\vektor{1\\0\\0},\;\vektor{0\\1\\0}\right\}$ [/mm] wählen (ebenso ginge auch [mm] $\left\{\vektor{1\\0\\0},\;\vektor{1\\1\\0}\right\}$; [/mm] Basen sind nicht eindeutig!).
Somit ist [mm] $\dim\left\{\vektor{x_1\\x_2\\x_3}:\;x_3=0,\;x_1,x_2 \in \IR \right\}=2\,,$ [/mm] aber jeder Vektor aus [mm] $\left\{\vektor{x_1\\x_2\\x_3}:\;x_3=0,\;x_1,x_2 \in \IR \right\}$ [/mm] hat, als Vektor des [mm] $\IR^3$, [/mm] 3 Komponenten. Das liegt daran, dass [mm] $\left\{\vektor{x_1\\x_2\\x_3}:\;x_3=0,\;x_1,x_2 \in \IR \right\}$ [/mm] ein Teilraum des [mm] $\IR$-Vektorraums $\IR^3$ [/mm] ist.
[mm] ($(\star)$ [/mm] Vielleicht war das, was Du meintest, eine 'Verwechslung':
Denn bzgl. einer Basis von [mm] $\left\{\vektor{x_1\\x_2\\x_3}:\;x_3=0,\;x_1,x_2 \in \IR \right\}$ [/mm] kann man diesen Unterraum zwar auch wieder mit einer Koordinatenabbildung versehen, wobei die Koordinaten dann durch [mm] $2\,$ [/mm] Komponenten versehen wären.
Aber:
Ein Element des Raumes [mm] $\left\{\vektor{x_1\\x_2\\x_3}:\;x_3=0,\;x_1,x_2 \in \IR \right\}$ [/mm] ist ein "Vektor mit [mm] $3\,$ [/mm] Komponenten", da ja [mm] $\left\{\vektor{x_1\\x_2\\x_3}:\;x_3=0,\;x_1,x_2 \in \IR \right\} \subset \IR^3\,.$ [/mm]
Beachte bitte den Unterschied!)
Nur mal als Beispiel:
Nehmen wir einfach mal die Vektoren [mm] $(2,0,0)^T,\;(0,3,0)^T,\;(0,0,1)^T \in \IR^3\,.$
[/mm]
Schau' Dir einfach mal folgende Matrizen an:
[mm] $$M_1=\pmat{2\\0\\0}\,,$$
[/mm]
[mm] $$M_2=\pmat{2 & 0 \\0 & 3\\0&0}\,,$$
[/mm]
und
[mm] $$M_3=\pmat{2 & 0 & 0\\0 & 3 & 0\\0&0 &1}\,.$$
[/mm]
Mit [mm] $f_j: \IR^j \to \IR^3,\;f_j(x)=M_j*x$ [/mm] ($x [mm] \in \IR^j$) [/mm] ist jeweils eine lineare Abbildung gegeben. Weil die Spalten der Matrix [mm] $M_j$ [/mm] jeweils offensichtlich linear unabhängig sind, ist [mm] $\dim(Bild(f_j))=j\,.$
[/mm]
Beim CG-Verfahren benutzt man genau solche Überlegungen, nur dass man die lineare Unabhängigkeit der Spalten der dort jeweils auftauchenden Matrizen [mm] $M_k$, [/mm] wobei
[mm] $$M_k=(p^0,\,\ldots,\,p^{k-1}) \in \IR^{n \times k}\;\;\; \text{(d.h. für } [/mm] j [mm] \le [/mm] k-1 [mm] \text{ ist die } j+1\,\text{-te Spalte von } M_k \text{ gerade der Vektor } p^j \in \IR^n=\IR^{n \times 1}\text{ )}$$
[/mm]
mit der [mm] $A\,$-Orthogonalität [/mm] begründet.
Und ein Vektor $u [mm] \in U_k \subset \IR^n$ [/mm] ist natürlich ein Vektor des [mm] $\IR^n\,,$ [/mm] so dass [mm] $\|u-v\|_A$ [/mm] auch Sinn macht:
Berechne für [mm] $u,\,v \in \IR^n$ [/mm] zunächst $d:=u-v [mm] \in \IR^n$ [/mm] (das geht, weil [mm] $\IR^n$ [/mm] ja Vektorraum) und bilde dann für $d [mm] \in \IR^n$ [/mm] die Norm [mm] $\|d\|_A$.
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:52 So 17.05.2009 | | Autor: | Pacapear |
Hallo Marcel.
Huiuiui, das ist ja alles ganz schön kompliziert....
Also ich versuch dass jetzt nochmal zusammenzufassen, mal gucken, ob ich es verstanden habe:
1) Also die Dimension eines Raumes ist immer gleich der Anzahl der maximal linear unabhängigen Vektoren in diesem Raum. Diese spannen den Raum dann auf.
2) Die Dimension eines (Vektor-)Raumes ist nicht gleich der Anzahl der Komponenten eines Vektors, mit dem ich in diesem Raum rechne. Sie kann es aber sein.
3) Wenn ein Vektor Element eines Unterraumes ist, dann hat er als Anzahl an Komponenten die Dimension des Oberraumes, weil der Vektor als Element des Unterraumes automatisch auch Element des Oberraumes ist.
4) Das heißt, z.B. in einem Raum der Dimension 5 kann ein Vektor niemals 3 Komponenten haben, auch wenn er nur als Element eines Unterraumes der Dimension 3 ausgewiesen wird? Andersrum kann in einem Raum der Dimension 3 aber mit Vektoren mit 5 Komponenten gerechnet werden, wenn es sich halt um einen Unterraum handelt (vgl. 2/3).
Habe ich das so richtig verstanden?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:36 So 17.05.2009 | | Autor: | Marcel |
Hallo Nadine,
nur kurz hierzu:
> 4) Das heißt, z.B. in einem Raum der Dimension 5 kann ein
> Vektor niemals 3 Komponenten haben, auch wenn er nur als
> Element eines Unterraumes der Dimension 3 ausgewiesen wird?
> Andersrum kann in einem Raum der Dimension 3 aber mit
> Vektoren mit 5 Komponenten gerechnet werden, wenn es sich
> halt um einen Unterraum handelt (vgl. 2/3).
das ist unglücklich ausgedrückt. Du identifizierst hier Vektoren immer mit ihren Koordinaten bzgl. einer (beliebig, aber wenn einmal gewählt, dann festen) Basis , was (sicher jedenfalls in endlichdimensionalen Vektorräumen) geht, weil die Koordinatenabbildung dann bijektiv ist.
Wenn Du einen [mm] $\,5$-dimensionalen $\IK$-Vektorraum $V\,$ [/mm] hast [mm] ($\IK$: [/mm] Körper) und eine Basis [mm] $\mathcal{B}$ [/mm] von diesem kennst, dann kannst Du bzgl. [mm] $\mathcal{B}$ [/mm] jeden Vektor $v [mm] \in [/mm] V$ in eindeutiger Weise mit einem Koordinatenvektor [mm] $(\lambda_1,\,\lambda_2,\lambda_3,\lambda_4,\lambda_5)^T \in \IK^5$ [/mm] identifizieren.
Wenn Du nun einen Unterraum $U [mm] \subset [/mm] V$ hast, der dreidimensional ist, so ist die Koordinatenabbildung, wenn man sie zwischen [mm] $\mathcal{B}$ [/mm] und [mm] $U\,$ [/mm] auffassen wollte, keine Bijektion mehr. Bzgl. einer Basis [mm] $\overline{\mathcal{B}}$ [/mm] von [mm] $U\,$ [/mm] wäre es möglich, eine Koordinatenabbildung auch wieder so aufzufassen, dass diese aus [mm] $3\,$ [/mm] Komponenten bestünde (ein Koordinatenvektor steht ja stellvertretend dafür, wie man mit den Koordinaten den Vektor bzgl. einer festen Basis dann linearkombinieren kann).
Aber diese ganze Problematik taucht bei Dir so eigentlich nicht auf, denn Du betrachtest nur die eine Koordinatenabbildung zwischen [mm] $V\,$ [/mm] und [mm] $\IK^{\dim(V)}$: [/mm]
Ich erkläre es vielleicht der Einfachheit wegen erstmal am [mm] $\IR^n$:
[/mm]
Wenn Du einen Vektor des [mm] $\IR^n$ [/mm] hernimmst, so besteht der (üblicherweise) aus [mm] $n\,$ [/mm] Komponenten; normalerweise betrachtet man ja den [mm] $\IR^n$ [/mm] ausgestattet mit der Standardbasis, so dass der Vektor hier identisch mit seinem Koordinatenvektor ist.
Ein Unterraum [mm] $U\,$ [/mm] des [mm] $\IR^n$ [/mm] ist insbesondere eine Teilmenge des [mm] $\IR^n\,.$ [/mm] Also ist jedes Element $u [mm] \in U\,$ [/mm] auch wieder ein Vektor des [mm] $\IR^n\,,$ [/mm] bzgl. der Standardbasis des [mm] $\IR^n$ [/mm] ist dieser Vektor [mm] $u\,$ [/mm] auch wieder im [mm] $\IR^n$ [/mm] identisch mit seinem Koordinatenvektor. Bzgl. einer Basis [mm] $\overline{\mathcal{B}}$ [/mm] von [mm] $U\,$ [/mm] hätte $u [mm] \in [/mm] U [mm] \subset \IR^n$ [/mm] i.a. einen anderen Koordinatenvektor. Aber man betrachtet ja [mm] $u\,$ [/mm] hier nicht bzgl. einer Basis von [mm] $U\,,$ [/mm] sondern eben bzgl. des Ausgangsraumes [mm] $V=\IR^n\,.$ [/mm]
Also: Die einen Vektor identifizierende Koordinatenabbildung ist bei Deinen Aufgaben stets 'gleichbleibend', es ist die zwischen einer Basis von [mm] $V\,$ [/mm] zu einem Vektor $v [mm] \in V\,,$ [/mm] und für $u [mm] \in [/mm] U [mm] \subset [/mm] V$ identifiziert sich der Vektor [mm] $u\,$ [/mm] dann durch diese Koordinatenabbildung auch in eindeutiger Weise, weil ja insbesondere dann $u [mm] \in [/mm] V$ gilt.
Wenn Du nun sagst, dass ja [mm] $U\,$ [/mm] eine kleinere Dimension hat und dann bzgl. einer Basis von [mm] $U\,$ [/mm] ein Koordinatenvektor i.a. auch weniger Komponenten hätte, dann ist das richtig, aber dann beziehst Du Dich auf eine neue Koordinatenabbildung, die zwischen [mm] $\,U$ [/mm] und dem [mm] $\IK^{\dim(U)}$ [/mm] stattfindet; nicht mehr auf die Ausgangs-Koordinatenabbldung, die sich zwischen $V$ und [mm] $\IK^{\dim(V)}$ [/mm] abspielte.
Wenn Du also mit Koordinatenvektoren hantierst, achte darauf, bzgl. welcher Basis der Koordinatenvektor aufzufassen ist bzw. bzgl. welcher Koordinatenabbildung. Manchmal ist es hilfreich, sich die Basis als Index an den Koordinatenvektor dranzuschreiben, wenn man sonst in Gefahr gerät, den Überblick zu verlieren. Oben war Dein Fehler vermutlich eigentlich, dass Du im Prinzip zwei Koordinatenabbildungen betrachtet hast, aber die Koordinatenschreibweise stets nur bzgl. einer Basis von [mm] $V\,$ [/mm] aufzufassen ist.
P.S.:
Schau' auch ruhig mal hier, S. 64, kurz rein.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:34 Mo 18.05.2009 | | Autor: | Pacapear |
Hallo Marcel!
Puh, deine Antwort bereitet mir ganz schön Kopfzerbrechen.
Diese beiden Begriffe "Koordinatenabbildung" und "Koordinatenvektor" sind bei uns nie gefallen
Wir haben einen Vektor einfach nur eingeführt als ein Element eines Vektorraums, und wenn der Vektor Element des [mm] \IR^n [/mm] war, dann hatte er eben n Komponenten - fertig.
Da muss ich mich mal ganz in Ruhe mit beschäftigen...
Waren denn meine Zusammenfassungen 1) bis 3) bis dahin richtig?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:34 Di 19.05.2009 | | Autor: | Marcel |
Hallo,
> Hallo Marcel!
>
> Puh, deine Antwort bereitet mir ganz schön Kopfzerbrechen.
>
> Diese beiden Begriffe "Koordinatenabbildung" und
> "Koordinatenvektor" sind bei uns nie gefallen
>
> Wir haben einen Vektor einfach nur eingeführt als ein
> Element eines Vektorraums, und wenn der Vektor Element des
> [mm]\IR^n[/mm] war, dann hatte er eben n Komponenten - fertig.
>
> Da muss ich mich mal ganz in Ruhe mit beschäftigen...
>
> Waren denn meine Zusammenfassungen 1) bis 3) bis dahin
> richtig?
1) ist sicherlich (in endlich-dimensionalen VRen) richtig.
Bei 2) und 3) kommt es wieder drauf an, wie Du 'die Komponenten eines Vektors' auffasst. Denn diese Komponenten sind eigentlich nicht 'Komponenten eines Vektors', sondern eines Koordinatenvektors.
Beschränken wir uns aber der Einfachheit wegen nun einfach stets auf den [mm] $\IK^n$ [/mm] (jeder [mm] $n\,$ [/mm] dimensionale [mm] $\IK$-Vektorraum [/mm] kann sowieso mit diesem identifiziert werden; schau' z.B. einfach mal in Bosch, lineare Algebra und suche dort nach dem Begriff Koordinatenspaltenvektor):
Hier hat man also wirklich Vektoren vorliegen, die stets aus Komponenten zusammengesetzt sind. Ein Unterraum $U$ von [mm] $\IK^n$ [/mm] erfüllt insbesondere $U [mm] \subset \IK^n\,,$ [/mm] und enthält damit insbesondere nur Elemente $u [mm] \in [/mm] U$ der Bauart [mm] $u=\vektor{u_1\\.\\.\\.\\u_n}$ [/mm] mit [mm] $u_i \in \IK$ [/mm] für [mm] $i=1,\;\ldots,\;n\,.$
[/mm]
Damit erkennst Du, dass hier Deine Behauptung 3.) stimmt.
Zur Aussage 2.)
Auch das ist richtig, was Du da festgestellt hast. Ein Tipp:
Betrachte mal den [mm] $\IR^5$ [/mm] als [mm] $\IR$-VR [/mm] versehen mit üblicher komponentenweiser Addition und üblicher skalaren Multiplikation [mm] $*\,,$ [/mm] d.h., [mm] $\alpha \in \IR, (x_1,\,\ldots,\,x_5)^T \in \IR^5 \Rightarrow \alpha*(x_1,\,\ldots,\,x_5)^T=(\alpha x_1,\,\ldots,\,\alpha x_5)^T$.
[/mm]
Betrachte nun [mm] $U:=\left\{\alpha*\vektor{1\\0\\0\\0\\0}+\beta*\vektor{1\\1\\0\\0\\0}:\;\alpha,\,\beta \in \IR\right\}\,.$
[/mm]
Überlege Dir:
[mm] $U\,$ [/mm] ist Unterraum des (wie oben erklärten) [mm] $\IR$-Vektorraums $\IR^5$ [/mm] und [mm] $U\,$ [/mm] hat Dimension [mm] $2\,.$ [/mm] Insbesondere siehst Du, dass jedes Element $u [mm] \in [/mm] U$ ein Vektor des [mm] $\IR^5$ [/mm] ist, also aus [mm] $5\,$ [/mm] Komponenten besteht.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:40 Di 19.05.2009 | | Autor: | Pacapear |
Hallo Marcel!
Vielen Dank für deine ausführlichen Antworten.
Ich denke mal, dass meine ursprüngliche Frage damit erstmal als beantwortet betrachtet werden kann, hoffentlich komme ich jetzt ein bisschen weiter im CG-Verfahren.
Diese ganzen LA-Sachen werden ich mir dannach dann nochmal in Ruhe zu Gemüte führen, dann steht nämlich die Vordiplomsprüfung in LA an :-(
LG, Nadine
|
|
|
|
