Das Konjugierte-Gradienten-Verfahren mit exakter Arithmetik bei quadratischen Zielfunktionen
1 Einleitung
Das Konjugierte-Gradienten-Verfahren (kurz: cg-Verfahren, cg Abk. für conjugated gradients) ist zunächst ein Abstiegsverfahren zur Minimierung konvexer, quadratischer Funktionen. Dieses zeigt eine deutliche Verbesserung gegenüber dem Gradientenverfahren, weil es, zumindest für quadratische Zielfunktionen, in endlich vielen Schritten zum Minimalpunkt gelangt. Unter zur Hilfenahme von Präkonditionierungstechniken (auch: Vorkonditionierung genannt) ist das cg-Verfahren auch auf dünn besetzte, lineare Gleichungssysteme mit symmetrisch, positiv definiten Matrizen anwendbar. Darauf möchte ich jedoch erst im zweiten Teil der Artikelreihe eingehen. Das cg-Verfahren gehört zur Klasse der Krylow-Unterraum-Verfahren. Es wurde von Hestenes und Stiefel (1952) veröffentlicht. Allerdings ist das Verfahren als direkter Löser aufgrund von Instabilität bei Rundungsfehlern ungeeignet. Anfang der 70er Jahre des letzten Jahrhunderts hat Reid Präkonditionierungstechniken entwickelt, um die Stabilität des Verfahrens zu verbessern, was dazu führte, dass das cg-Verfahren als iteratives Lösungsverfahren wieder interessant wurde.
Ich möchte nicht nur die Theorie mit den entsprechenden Sätzen und Beweisen vorstellen, sondern auch am Ende des Artikels ein Beispiel durchrechnen. Diesbezüglich werde ich insbesondere auf zwei für numerische Rechnungen nützliche Formeln eingehen. Im zweiten Teil der Artikelreihe werde ich dann das Konvergenzverhalten des Verfahrens bei Rundungsfehlern diskutieren und die sog. Präkonditionierungstechniken erläutern.
Die Idee des Verfahrens besteht darin, dass das Optimieren einer quadratischen Funktion äquivalent damit ist, ein lineares Gleichungssystem mit einer symmetrisch, positiv definiten Matrix zu lösen.
Sei f(x) =1/2*x^T*A*x-b*x+c, A \el \IR^(n\cross n) symmetrisch, positiv definit. Der Gradient der partiell differenzierbaren Funktion f ist somit grad(f(x))=A*x-b.
Der Ansatz grad(f(x))=0 zur Bestimmung der Extremstelle führt unmittelbar zu dem LGS A*x=b.
Die konjugierten Richtungen sind entscheidend dafür, dass das cg-Verfahren im Vergleich mit dem Gradientenverfahren nach n Iterationsschritten den Minimalpunkt einer quadratischen Funktion erreicht. Um dies für einen beliebigen Startwert zu erreichen, ist es unabdingbar, dass die konjugierten Richtungen allesamt linear unabhängig sind.
Definieren wir nun zuvor die Eigenschaft zweier Vektoren v und w, welche konjugiert bezüglich einer symmetrisch, positiv definiten Matrix A sind.
\
Definition__:
v,w!=0 \el \IR^n heißen konjugiert bzgl. einer symmetrisch, positiv definiten Matrix A \el \IR^(n\cross n), wenn v^T*A*w=0.
Man nennt dies auch kurz A-konjugiert. Wenn A die Einheitsmatrix ist, spricht man von orthogonalen Vektoren. Insofern liegt hier eine Verallgemeinerung des Begriffs der Orthogonalität vor. Wie bei orthogonalen Vektoren gilt die lineare Unabhängigkeit.
\
Lemma__:
Seien menge(r_0,...,r_k) \el \IR^n, k<=n-1 paarweise A\-konjugiert und A symmetrisch, positiv definit, dann ist menge(r_0,...,r_k) linear unabhängig.
Beweis__:
Aus summe(\a_i*r_i,i=0,k)=0 erhält man für ein beliebiges l mit 0<=l<=k die Gleichung 0=r_l^T*A*summe(\a_i*r_i,i=0,k)=r_l^T*A*\a_l*r_l=\a_l*r_l^T*A*r_l. Da aber r_l^T*A*r_l>0 => \a_l=0. Desweiteren wurde l beliebig gewählt, somit folgt die Behauptung.
Die konjugierten Richtungen, deren Bedeutung erst dann richtig klar wird, wenn wir im folgenden Kapitel den eigentlichen Algorithmus besprechen, werden rekursiv berechnet.
\
Satz__:
Sei f(x) =1/2*x^T*A*x-b*x, A positiv definit und x_(k+1)=x_k+\alpha_k*r_k, wobei \a_k=-(A*x_k-b)^T*r_k/norm(r_(k))_A^2 . Wir setzen norm(r_(k))_A^2 :=r_k^T*A*r_k. Mit dem Startwert r_0:=-grad(f(x_0)) definieren wir rekursiv für k=1,...,n-1 mit r_k := -grad(f(x_k))+\b_(k-1)*r_(k-1), wobei \b_(k-1)=(grad(f(x_k))*A*r_(k-1))/norm(r_(k-1))_A^2 . Dann gilt:
(1) span{ grad(f(x_0)),..., grad(f(x_k)) } = span{ r_0,...,r_k } für k=0,...,n-1.
(2) { r_0,...,r_k } sind paarweise A\-konjugiert.
Beweis__:
Der Beweis erfolgt jeweils durch vollständige Induktion nach k=0,...,n-1.
(1) Es ist offensichtlich span{ grad(f(x_0)) } = span{ r_0 } und somit die Behauptung für k = 0 wahr. Die Behauptung sei wahr für k^\* = 0,...,k. Wir rechnen nach, dass sie dann auch für k^\*= k+1 gilt:
span{ grad(f(x_0)),..., grad(f(x_(k+1))) } = span{ r_0,..., r_k, grad(f(x_(k+1))) }
= span{r_0,...,r_k, -r_(k+1)+\b_k*r_k } = span{r_0,...,r_(k+1) }.
(2) Für k = 0 ist nichts zu zeigen. Seien { r_0,...,r_k } paarweise A\-konjugiert (Induktionsvoraussetzung). Zu zeigen ist: r_(k+1)^T*A*r_j=0 für alle j=0,..,k. Für j=k gilt
r_(k+1)^T*A*r_k=(-grad(f(x_(k+1)))+\b_k*r_k)^T*A*r_k
\ \=-grad(f(x_(k+1)))*A*r_k+\b_k*norm(r_(k-1))_A^2
\ \=-grad(f(x_(k+1)))*A*r_k+grad(f(x_(k+1)))*A*r_k=0.
Für 0<=j
4 Konvergenz des Verfahrens mit exakter Arithmetik
Nun folgt ein wichtiger Satz über das Konvergenzverhalten des cg-Verfahrens. Dieser Satz bildet den Kern des Artikels. Ich möchte im Folgenden auch einen Beweis dazu liefern. Der Satz besagt, dass das Verfahren nach einer endlichen Anzahl von Schritten, nämlich höchstens n, das Minimum einer quadratischen Funktion erreicht. Ich finde das bemerkenswert, dass eine geschickte Anpassung der Richtungen in jedem Schritt genau das bewirkt. Wir haben es also im direkten Vergleich mit dem (Standard-) Gradientenverfahren mit einem exakten Verfahren zu tun, wenn die Arithmetik exakt ist.
\
Satz__:
Sei f(x) =1/2*x^T*A*x-b*x, A \el \IR^(n\cross n) symmetrisch, positiv definit, und menge(r_0,...,r_(n-1)) seien paarweise bezüglich A konjugiert. Sei x_0 der Startpunkt der Iteration
\ \ x_(k+1)=x_k+\alpha_k*r_k, wobei \a_k=-(A*x_k-b)^T*r_k/norm(r_(k))_A^2
\die exakte Schrittweite ist. Dann ist nach n Iterationsschritten der Minimalpunkt x^\* von f erreicht.
Beweis__:
In Kapitel 2 haben wir gezeigt, dass die konjugierten Richtungen r_k linear unabhängig sind. Ein beliebiger Startvektor x_0 kann somit als Linearkombination der Vektoren r_k für k=0,...,n-1 dargestellt werden:
x_0=summe(\gamma_k*r_k,k=0,n-1) mit \gamma_k=x_0^T*A*r_k/norm(r_k)_A^2 und
x_1=x_0+\alpha_0*r_0
x_2=x_1+\alpha_1*r_1=x_0+\alpha_0*r_0+\alpha_1*r_1
...
x_n=x_0+summe(\a_k*r_k,k=0,n-1)=summe((\gamma_k+\a_k)*r_k,k=0,n-1)
Nun setzt man \gamma_k und \alpha_k in die Summe ein:
x_n=summe((x_0^T*A*r_k/norm(r_k)_A^2-(A*x_k-b)^T*r_k/norm(r_(k))_A^2)*r_k,k=0,n-1)
\ =summe(1/norm(r_k)_A^2*(x_0^T*A*r_k-(A*x_k-b)^T*r_k)*r_k,k=0,n-1)
\ =summe(1/norm(r_k)_A^2*(x_0^T*A*r_k-x_k^T*A*r_k+b^T*r_k)*r_k,k=0,n-1)
\ =summe(1/norm(r_k)_A^2*((x_0-x_k)^T*A*r_k+b^T*r_k)*r_k,k=0,n-1)
\ =summe(1/norm(r_k)_A^2*((summe(\a_j*r_j,j=0,k-1))^T*A*r_k+b^T*r_k)*r_k,k=0,n-1)
\ =summe(1/norm(r_k)_A^2*(b^T*r_k)*r_k,k=0,n-1)
Es gilt jedoch A*x^\*=b <=> x^\*^T*A=b^T und somit
\ =summe((x^\*^T*A*r_k)/norm(r_k)_A^2*r_k,k=0,n-1)
(x^\*^T*A*r_k)/norm(r_k)_A^2 sind aber gerade die Koordinaten von x^\* bzgl. der Basis menge(r_k). Daher gilt x_n=x^\*.
Bemerkungen__:
(a) \alpha_k=arg min{ f(x_k+\a*r_k) \|\a \el \IR }
Man zeige, dass r_k^T*grad(f(x_(k+1)))=r_k^T*grad(f(x_k-((A*x_k-b)^T*r_k/norm(r_(k))_A^2)*r_k))=0.
(b) x_(k+1)=arg min{ f(x) \| x \el x_0+span{r_0,...,r_k }}
(c) grad(f(x_(k+1))) \senkrechtauf span{r_0,...,r_k }
Die entsprechenden Beweise bleiben dem Leser überlassen.
An dieser Stelle möchte ich die einzelnen Schritte aufführen, welche zur Berechnung des Minimums einer quadratischen Funktion mithilfe des cg-Verfahrens notwendig sind. Dabei geht es mir darum, einen kompakten und praktikablen Überblick zu liefern und für numerische Rechnungen nützliche Formeln anzugeben.
\
Voraussetzungen__:
Sei f(x)=1/2*x^T*A*x-b*x+c, A \el \IR^(n\cross n) spd und g(x):=A*x-b=grad(f(x)).
Start__:
Wähle x_0 \el \IR^n und setze g_0:=g(x_0), r_0:=-g_0.
(1. Schritt)__:
Falls g_k=g(x_k)=0, STOP: x_k ist Minimum von f.
(2. Schritt)__:
Sonst setze x_(k+1):=x_k+\a_k*r_k, wobei \a_k=norm(grad(f(x_k)))^2/norm(r_(k))_A^2 .
(3. Schritt)__:
Berechne r_(k+1)=-grad(f(x_(k+1)))+\beta_k*r_k, wobei \beta_k=norm(grad(f(x_(k+1))))^2/norm(grad(f(x_k)))^2 .
(4. Schritt)__:
Gehe zu Schritt 1.
Die Umformungen ergeben sich wie folgt:
\
\a_k=-(A*x_k-b)^T*r_k/norm(r_(k))_A^2=-grad(f(x_k)*r_k/norm(r_(k))_A^2=-grad(f(x_k)*(-grad(f(x_k))+\beta_(k-1)*r_(k-1))/norm(r_(k))_A^2=norm(grad(f(x_k)))^2/norm(r_(k))_A^2
\beta_k=(grad(f(x_(k+1)))*A*r_k)/norm(r_k)_A^2=(grad(f(x_(k+1)))*1/\a_k*(grad(f(x_k))-grad(f(x_(k+1)))))/norm(r_k)_A^2=-norm(grad(f(x_(k+1))))^2/(norm(r_(k))_A^2*\a_k)=norm(grad(f(x_(k+1))))^2/norm(grad(f(x_k)))^2
Nun möchte ich ein Beispiel durchrechnen.
\
Sei f(x)=1/2*x^T*(6,1,2;1,1,-2;2,-2,8)*x-(-2,1,2)*x+c und grad(f(x))=(6,1,2;1,1,-2;2,-2,8)*x-(-2;1;2).
A ist offenbar symmetrisch. Es lässt sich leicht nachprüfen, dass A positiv definit ist. Das Minimum liegt bei x^\*=(-7,24,8)^T .
Startwerte__:
x_0=(1,0,0)^T und r_0=-grad(f(x_0))=(-8,0,0)
(1. Iteration (x_1 und r_1))__:
x_1=(1,0,0)^T+\a_0*(-8,0,0)^T, \a_0=64/384=1/6
x_1=(1,0,0)^T+1/6*(-8,0,0)^T=(-1/3 ,0,0)^T
r_1=-(0,-4/3 ,-8/3)^T+\beta_0*(-8,0,0)^T, \beta_0=5/36
r_1=(0, 4/3 , 8/3)^T+5/36*(-8,0,0)^T=(-10/9 , 4/3 , 8/3)^T
(2. Iteration (x_2 und r_2))__:
x_2=(-1/3 ,0,0)^T+\alpha_1*(-10/9 , 4/3 , 8/3)^T, \alpha_1=(80/9)/(1000/27)=6/25
x_2=(-1/3 ,0,0)^T+6/25*(-10/9 , 4/3 , 8/3)^T=(- 3/5, 8/25, 16/25)^T
r_2=-(0, - 64/25, 32/25)^T+\b_1*(-10/9 , 4/3 , 8/3)^T, \b_1=576/625
r_2=(0, 64/25, -32/25)^T+576/625*(-10/9 , 4/3 , 8/3)^T=(- 128/125 , 2368/625 , 736/625)^T
(3. Iteration (x_3 und r_3))__:
x_3=(- 3/5, 8/25, 16/25)^T+\a_2*(- 128/125 , 2368/625 , 736/625)^T, \a_2=25/4
x_3=(- 3/5, 8/25, 16/25)^T+25/4*(- 128/125 , 2368/625 , 736/625)^T=(-7,24,8)^T=x^\*
Da es zum \IR^3 genau 3 linear unabhängige Basisvektoren gibt, ist zu erwarten, dass r_3=0. Die Vektoren r_0 ,r_1 ,r_2 bilden eine A-orthogonale Basis des \IR^3.
r_3=-grad(f(x^\*))+\beta_2*r_2
Da aber \beta_2=norm(grad(f(x_3)))^2/norm(grad(f(x_2)))^2 und grad(f(x_3))=grad(f(x^\*))=0, folgt, dass r_3=0.
Es ist natürlich für eine schriftliche Rechnung geschickter, den Startwert x0=0 zu wählen. Ich wollte demonstrieren, dass man einen beliebigen Startwert wählen kann.
Ich hoffe, dass euch der Artikel gefallen hat. Wie in der Einleitung erwähnt, wird ein zweiter Teil folgen. Ich werde dann den Satz über die Konvergenzgeschwindigkeit des Verfahrens beweisen. Man führt das Verfahren bei Rundungsfehlern über n hinaus durch. Es ist interessant zu untersuchen, wie schnell sich dann das Verfahren der Lösung nähert. Der Beweis hätte den von mir angestrebten Rahmen des Artikels gesprengt, da dieser relativ kompliziert ist und ausführlich vorgestellt werden sollte. Ich werde auch insbesondere auf den Einsatz der Verfahrens beim Lösen von linearen Gleichungssystemen eingehen. Wie ihr wisst, lieben Numeriker lineare Gleichungssysteme... :-)
Über konstruktive Kritik freue ich mich jederzeit. Falls ihr Fehler findet oder Verbesserungsvorschläge habt, korrigiere ich das bzw. setze das gerne um.
Quellen:
(1) Prof. Bachmann, Prof. Kruse, Prof. Walden - Vorlesungsskript: Optimierung
(2) Stoer/Bulirsch - Numerische Mathematik 2
(3) Jarre/Stoer - Optimierung
(4) wikipedia.de
Einen ganz herzlichen Dank an die kompetenten und hilfsbereiten Korrekturleser: Gockel, Marco_D und rlk! Die Grafik in der Einleitung stammt, wie man das natürlich vermuten würde, von viertel. Vielen Dank an dieser Stelle auch an dich!
Beste Grüße
Marc
Das Konjugierte-Gradienten-Verfahren
mit exakter Arithmetikbei quadratischen Zielfunktionen
1 Einleitung
Das Konjugierte-Gradienten-Verfahren (kurz: cg-Verfahren, cg Abk. für conjugated gradients) ist zunächst ein Abstiegsverfahren zur Minimierung konvexer, quadratischer Funktionen. Die
\(\begingroup\)Um die Inkonsistenzen beim Transponieren werde ich mich noch kümmern. ;) Marco hat eine pdf-Version mit Latex gebaut. Ich werde diese alsbald hochladen.
Grüße, Marc \(\endgroup\)
\(\begingroup\)Hallo,
das soll keine Kritik sein, aber ich sehe den Vorteil irgendwo noch nicht. Die Probleme
I) x^T Ax - bx -> min!
und
II) Löse Ax=b
sind für positiv definites A äquivalent. Man kann das also als eine Methode zur Lösung eines bestimmten Typs linearer GLS ansehen. Ist der Algorithmus denn irgendwie besser als andere vergleichbare Algorithmen, zum Beispiel hinsichtlich der Geschwindigkeit? Man hat ja immer noch in jedem Schritt mehrere Matrix-Vektor-Produkte, besonders bei der Bestimmung der Norm von r_k.
Die Erkenntnis allein, dass es Iterationen gibt, die ein nxn-GLS in n Schritten exakt lösen ist noch nicht sonderlich spannend.\(\endgroup\)
\(\begingroup\)So, die pdf-Version (Version 1) steht nun auch. Vielen Dank an Marco! 😄
@Realshaggy: Was meinst du mit "Darunter auch welche, die aus einer dünnbesetzten Matrix plötzlich eine voll besetzte machen..." ?
Ansonsten wollte ich auf deine Fragestellungen im nächsten Teil eingehen. Wann lohnt sich das Verfahren? Wie sieht es mit Cholesky-Zerlegung vs. cg-Verfahren aus? usw.
Bei sehr großen dünn besetzten Matrizen, welche spd sind, lohnt sich das schon. 😄
Grüße, Marc\(\endgroup\)
\(\begingroup\)Die Tatsache, dass das cg-Verfahren bei exakter Rechnung nach höchstens n (Dimension) Schritten die eindeutige Lösung findet (also als direktes Verfahren interpretiert werden kann), ist zwar hübsch, aber praktisch bedeutungslos. Wichtig ist, dass das Verfahren nur die Realisierung von Matrix-Vektor-Multiplikation benötigt und meistens in viel weniger als n Schritten gute Näherungen liefert, sich also ideal für große schwach besetzte Systeme eignet. Durch Vorkonditionierung kann die Konvergenz noch entscheidend verbessert werden. Für tieferen Einstieg sei dieses hier empfohlen.
Gruß cth\(\endgroup\)
\(\begingroup\)Hallo clausthaler,
ich habe ja explizit auf die exakte Arithmetik hingewiesen. Das diente lediglich als Einstieg. Vorkonditionierung, Konvergenzverhalten (bei Rundungsfehlern) usw. kommt ja noch und zwar im zweiten Teil.
Grüße gm\(\endgroup\)
\(\begingroup\)Hi,
das soll ebenfalls keine Kritik sein, aber es wäre ganz gut, wenn der Algorithmus nicht nur in Formeln, sondern auch etwas intuitiver erklärt werden würde. Ich habe sehr oft gerade in der angewandten Mathematik den Eindruck, dass die Anschauung hinter den Rechenmethoden zu kurz kommt. Das Verfahren hier würde ich beispielsweise folgendermaßen anschaulich beschreiben:
Abschnitt 3: Die positiv definite Matrix A induziert ein euklidisches Skalarprodukt auf \IR^n . Zwei Vektoren sind A-konjugiert, wenn sie bezüglich diesem Skalarprodukt zueinander orthogonal sind. Nach dem Gram-Schmidt-Verfahren bauen wir uns rekursiv eine Orthogonalbasis menge(r_0,...,r_(n-1)) des \IR^n bezüglich diesem Skalarprodukt zusammen.
Abschnitt 4: Jetzt kommt der eigentliche Algorithmus. Wir wollen das Gleichungssystem Ax = b lösen. Dazu starten wir mit einem beliebigen Vektor x_0. Jetzt konstruieren wir ausgehend von x_0 rekursiv eine Folge (x_0, x_1, ..., x_n) von Vektoren, bei der jeder Vektor x_(k+1) die orthogonale Projektion des vorherigen Vektors x_k auf den affinen Unterraum
A^(-1) b + span(menge(r_(k+1) , r_(k+2) , ... , r_(n-1)))
des \IR^n ist. "Orthogonal" heißt dabei "orthogonal bezüglich des von A induzierten Skalarproduktes". So gesehen ist es völlig klar, warum x_n = A^(-1) b ist. Das einzige, was bei diesem Zugang nicht gleich offensichtlich ist, ist, wie man x_(k+1) aus x_k ausrechnet - aber man weiß ja per Induktion, daß x_k schon in
A^(-1) b + span(menge(r_k, r_(k+1) , r_(k+2) , ... , r_(n-1)))
liegt, weshalb man x_k nur noch "in Richtung r_k " kalibrieren muß, d. h. man kann x_(k+1) = x_k + \alpha_k r_k setzen, und dieses \alpha_k zu berechnen ist eine lineare Gleichung in 1 Variablen. Auflösen ergibt die von gaussmath gegebene Formel.
gaussmath, leider scheinst du dich wirklich mit den Transpositionen vertan zu haben. x^T A x ist (für x Vektor und A Matrix) ein Skalar; da du x^T A x - b * x + c schreibst, muß auch b * x ein Skalar sein, also b ein Kovektor (Zeilenvektor), aber dann macht Ax = b keinen Sinn.
Viele Grüße,
Darij\(\endgroup\)
\(\begingroup\)Hey Darij,
danke für deine Erläuterungen! Mir ist die Anschaulichkeit ebenfalls wichtig. Klar, in meinem Artikel fehlen die geometrischen Interpretationen an vielen Stellen. Ich wollte die von dir erwähnten Punkte so oder ähnlich noch hinzufügen. Aus zeitlichen Gründen musste ich da erstmal passen.
Ich habe den Artikel dennoch "raus gehauen", da das Grundgerüst stand. Die Theorie ist meiner Meinung nach genügend ausführlich formuliert. Mit den Begriffen "Euklidisches Skalarprodukt" und "Gram-Schmidt-Verfahren" wäre ich aber vorsichtig. Die Theorie hinter dem cg-Verfahren baut auf einer Verallgemeinerung dessen auf.
Mir bereitet es Unbehagen, orthogonal und A-orthogonal als dasselbe zu bezeichnen. Rein numerisch besteht da doch schon ein großer Unterschied. Vielleicht fehlt mir einfach dieses generalisierende Denken dafür. 😄
Interessant ist auch grad(f(x_(k+1))) \senkrechtauf span{r_0,...,r_k }. Da sollte man auch mal eine geometrische Interpretation wagen...
Wenn es dir nichts ausmacht, würde ich gerne deine Erläuterungen in den Artikel mit einbauen.
Bitte mehr solcher Kommentare! 😁
Grüße
gaussmath\(\endgroup\)
\(\begingroup\)Hi gaussmath,
Orthogonalität ist in der linearen Algebra immer an ein Skalarprodukt gebunden, und das Skalarprodukt muß nicht das Standardskalarprodukt (<(x_1 , x_2 , ... , x_n),(y_1 , y_2 , ... , y_n)> = summe(x_i y_i,i=1,n)) sein. Notfalls kannst du dich durch Basiswechsel davon überzeugen, daß für alle positiv definiten Matrizen A sich die von A induzierten Skalarprodukte "gleich verhalten".
Die Gleichung grad(f(x_(k+1))) \senkrechtauf span{r_0,...,r_k } \(wobei hier \senkrechtauf Orthogonalität bezüglich Standardskalarprodukt meint\) ist recht klar. In der Tat ist grad(f(x_(k+1))) = Ax_(k+1) - b \(wenn man b als Vektor ansieht; sonst bitte b^T statt b überall in meinen Posts lesen\); damit ist
grad(f(x_(k+1))) \senkrechtauf span{r_0,...,r_k }
äquivalent zu
r_i^T (Ax_(k+1) - b) = 0 für alle i \in {0,1,...,k},
also zu
r_i^T A (x_(k+1) - A^(-1) b) = 0 für alle i \in {0,1,...,k}.
Und dies heißt nichts anderes, als dass der Vektor x_(k+1) - A^(-1) b orthogonal bezüglich dem von A induzierten Skalarprodukt zu allen r_i für alle i \in {0,1,...,k} ist. Was aber sofort aus der Definition von x_(k+1) als orthogonale Projektion von x_k auf den affinen Unterraum
A^(-1) b + span(menge(r_(k+1) , r_(k+2) , ... , r_(n-1)))
folgt, denn dieser Raum ist orthogonal zu allen r_i für alle i \in {0,1,...,k}.
Wohlgemerkt, ich musste erst ein wenig algebraisch umformen, bis ich die geometrische Deutung geben konnte - denn in deiner Behauptung kam eine Orthogonalität bezüglich dem Standardskalarprodukt vor, während mein geometrisches Modell das A-Skalarprodukt benutzt, und geometrisch kann man immer nur ein Skalarprodukt gleichzeitig "sehen". Vermutlich gibt es auch eine geometrische Deutung mit dem Standardskalarprodukt, aber ich fand meine einfacher.
Kannst das gerne alles in deinen Artikel übernehmen. Wie schon gesagt, ich halte die fehlende geometrische Anschauung für ein Problem vieler Numeriktexte.
Grüße,
Darij\(\endgroup\)
\(\begingroup\)Hallo,
das hat clausthaler weiter oben schon empfohlen. Ich habe es heute nur mal quergelesen, und es scheint wirklich ein gutes Skript zu sein, dass ich mir nächste Woche wohl mal genauer durchlesen werde.\(\endgroup\)
\(\begingroup\)Hallo,
die Lektüre ist wirklich sehr gut! Ich kann das nur empfehlen. Es wird auch insbesondere auf den tieferen Zusammenhang mit den Eigenwerten eingegangen. Allerdings braucht man schon ein wenig Zeit dafür.
Grüße
gaussmath \(\endgroup\)
\(\begingroup\)Hi,
erstens wollte ich hier mal posten, das du super Arbeit gemacht hast und das auch sehr gut erklärt hast.
Nun da ich das verstanden habe, wollte ich auch dein Beispiel durchrechnen, um das was ich gelernt habe auch benutzen zu können.
Aber irgendwie komme ich da nicht weiter bei der Berechnung von
"beta 1".
Denn ich habe da ein ganz anderes Ergebnis raus als was du da hast.
Kannst du das nochmal nachrechnen und verifizieren das das Ergebnis von beta 1 doch richtig ist.
Schöne Grüße
simco407\(\endgroup\)
\(\begingroup\)Ich beschäftige ich mich mit finiten Elementen und möchte dazu gern den hier veröffentlichten Algorithmus für das Konjugierte-Gradienten-Verfahren benutzen.
Weil ich mit der Syntax der Matrizenrechnung nicht vertraut bin, habe ich im Abschnitt 5, 3. Schritt, die Formel für den Faktor Beta nicht verstanden:
|| Gradient f(X_k+1) ||²
Beta_k = -------------------------------
|| Gradient f (X_k) ||²
Ich wäre Ihnen sehr dankbar, wenn Sie mir die Ausrechnung dieser Formel, die bei der ersten Iteration Beta_0 = 5/36 ergibt, schrittweise erläutern könnten.
Mit Dank im Voraus für Ihre Mühe und freundlichen Grüßen
Klaus [Nachname verborgen]\(\endgroup\)
\(\begingroup\)Hallo Klaus,
wir bleiben beim Du?! Ich bin mir nicht ganz sicher, was du meinst. Geht es dir um die Herleitung des Quotienten, oder um das konkrete Zahlenbeispiel?
Grüße, Marc\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Dieser Artikel ist im Verzeichnis der 
