Ausgleichung Gauß/Cholesky < Interpol.+Approx. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Cholesky-Verfahren:
A*x=b
|
Hi Forum,
kann mir jemand vielleicht den Zusammenhang zwischen Gauß und Cholesky erklären?
Oder wie bezeichnet man die einzelnen Vektoren und die Matrix? Etwa so:
A=Normalgleichungsmatrix?
x=Unbekanntenvektor?
b=Beobachtungsvektor?
Wenn A die Normalgleichungsmatrix wäre, dann könnte man die doch anhand von [mm] N^T*N [/mm] (N=Koeffizientenmatrix) bestimmen, oder?
Also falls sich jemand findet, der sich damit auskennt, wäre ich für Hilfe sehr dankbar. In erster Linie würde mir schon mal helfen, ob die Bezeichnungen korrekt sind. Dann ist dort ja auch schon der Zusammenhang zur Ausgleichung mit Gauß.
Lieben Gruß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:42 Mi 20.05.2009 | | Autor: | tony1v |
für Cholesky zerlegung muss dein matrix Symmetrisch [mm] A=A^T [/mm] und positiv definit das heisst x^TAx > 0 oder alle Eigenwerte von A positiv sind
Choleskyzerlegung: A= R^TR = [mm] LL^T [/mm] mit L = [mm] R^T
[/mm]
algoritmus Dazu :
for k =1, .........,n
for i=1, ,k-1
[mm] l_{ki}=(a{ki} -\summe_{j=1}^{i-1} l_{ij}l{kj}
[/mm]
[mm] l_{kk}=( a_{kk} [/mm] - [mm] \summe_{i=1}^{k-1}l^2_{kj})^{1/2}
[/mm]
für n= 4 zum beispiel
k =1 [mm] l_{11} [/mm] = (a{11})^(1/2)
k= 2 i=1 [mm] l_{21} [/mm] = [mm] (a_{21}/l_{11}
[/mm]
[mm] l_{22} =(a_{22} [/mm] - [mm] (l_{21})^2)^{1/2}
[/mm]
k=3 i=1 [mm] l_{31} [/mm] = [mm] a_{31}/l_{11}
[/mm]
i=2 [mm] l_{32} [/mm] = [mm] (a_{32} [/mm] - [mm] l_{21}l_{31})/l_{22}
[/mm]
[mm] l_{33}= [/mm] ( [mm] a_{33} [/mm] - [mm] l_{32}^2 [/mm] - [mm] l_{32}^2)^{1/2} [/mm] ........................
danch löst Ly = b , mit L= [mm] \vmat{ l_{11} & 0&0&0 \\ l_{21} & l_ {22} & 0 &0 \\ l_{31} & l_{32} & l_{33} & 0 \\ l_{41} & l_{42} & l_{43} & l_{44}}
[/mm]
danach Löst [mm] L^T [/mm] x = y und dann hast du die lösung
für die Gauszerlegung gibts zerlegung ohne pivot suche mit pivot suche mit zeilenvertauschung oder auch mit zeilen und spalten vertauschung ich weiss nicht welche zerlegung die du barucht.
ich hoffe dass ich dir helfen konnte.
|
|
|
| |
|
> für Cholesky zerlegung muss dein matrix Symmetrisch [mm]A=A^T[/mm]
> und positiv definit das heisst x^TAx > 0 oder alle
> Eigenwerte von A positiv sind
Ja, genau. Das ist mir bekannt. Deshalb meine Frage, ob in dieser Gleichung [mm]A*x=b[/mm]
[mm]A[/mm] die Normalgleichungsmatrix ist? Die wäre ja symmetrisch. Mir gehts eigentlich nicht darum, wie ich das Auflösen bzw. Rechnen kann, sondern eher, aus was sich die Gleichung zusammen setzt. Aber trotzdem danke.
Die Koeffizientenmatrix ist ja z.B. nicht immer symmetrisch. Deshalb wäre meine Frage, ob ich diese dann benutze, um [mm] A [/mm] zu erhalten. Eben indem ich [mm]A=N^T*N[/mm] rechne.
> für die Gauszerlegung gibts zerlegung ohne pivot suche mit
> pivot suche mit zeilenvertauschung oder auch mit zeilen und
> spalten vertauschung ich weiss nicht welche zerlegung die
> du barucht.
> ich hoffe dass ich dir helfen konnte.
Auch, wenn mir deine Antwort jetzt nicht hilft, trotzdem danke. Vielleicht kannst du mir ja noch helfen 
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:16 Do 21.05.2009 | | Autor: | Blech |
> Auch, wenn mir deine Antwort jetzt nicht hilft, trotzdem
> danke. Vielleicht kannst du mir ja noch helfen
Du machst das Helfen auch nicht gerade leicht, wenn ich das mal so sagen darf. =)
Du willst also für Ax=b was von Gauß und Cholesky und das ist die Normalendings und so und überhaupt.
Was sollen A und b denn sein?
Dem Gerede von einer Normalengleichungsmatrix (es gibt afaik übrigens keine gebräuchlichen Begriffe für die einzelnen Elemente der Normalengleichung, er wäre aber nicht schlecht =) entnehme ich, daß wir ein lineares Ausgleichsproblem der Form
[mm] $\min_x \| [/mm] Cx - [mm] d\|$
[/mm]
haben und entsprechend die Normalengleichungen aufgestellt wurden:
$A=C^tC$, $b=C^td$
aber, was Du jetzt wissen willst, ist nicht ganz klar.
Warum man Cholesky-Zerlegung macht?
Weil $C^tC$ symmetrisch und positiv definit ist (1. wieso? 2. Im Normalfall fordert man vollen Spaltenrang für C und hat damit positive Definitheit; könnte sonst auch pos. semidefinit sein) und Cholesky einen geringeren Aufwand erfordert als Gauß-Elimination.
ciao
Stefan
|
|
|
| |
|
Hi Stefan,
> Du machst das Helfen auch nicht gerade leicht, wenn ich das
> mal so sagen darf. =)
Sorry, ja da hast du wahrscheinlich recht Vielleicht versuche ich es nochmal etwas anders zu erklären. Problem ist eben, dass ich da auch etwas auf dem Schlau stehe...
Ich habe folgende Zielsituation:
v=A*x-l
A: Design-/Koeffizientenmatrix
x: Unbekanntenvektor
l: Beobachtungsvektor
v: Vektor der Verbesserungen
Jetzt frage ich mich, ob man überhaupt von A*x=b dorthin kommen kann. Und ob das auch heißen könnte A*x=l (wie oben)? Oder ob das zwei verschiedene Paar Schuhe sind.
Hab jetzt auch nochmal versucht etwas nachzuforschen und jetzt bin ich auf die beiden nachfolgenden Gleichungen gekommen. Jetzt ist mir natürlich noch nicht ganz klar, wann man welche benutzt, deshalb würde ich gerne wissen wann man
A*x=b
und wann
[mm] A^T*A*x=A^T*b [/mm] (diese ähnelt ja: [mm] x=(A^T*A)^-1*A^T*l)
[/mm]
anwendet. Weiß denn jemand, ob [mm] A^T*A*x=A^T*b [/mm] gleich [mm] x=(A^T*A)^-1*A^T*l) [/mm] ist?
Gruß, Bluemchen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:56 Do 21.05.2009 | | Autor: | Denny22 |
Hallo,
ich muss auch zugeben, dass ich nicht wirklich verstehe worauf Du hinaus möchtest, aber gehen wir es mal an. Ich fasse zusammen:
> Ich habe folgende Zielsituation:
> v=A*x-l
>
> A: Design-/Koeffizientenmatrix
> x: Unbekanntenvektor
> l: Beobachtungsvektor
> v: Vektor der Verbesserungen
>
> Jetzt frage ich mich, ob man überhaupt von A*x=b dorthin
> kommen kann. Und ob das auch heißen könnte A*x=l (wie
> oben)? Oder ob das zwei verschiedene Paar Schuhe sind.
Hier verstehe ich schon einmal etwas nicht. Es ist doch $b=v+l$, denn Deiner Beschreibung nach zufolge gilt:
$v+l=Ax=b$
Dir ist hoffentlich klar, dass, wenn Du den Vektor $x$ mit
$Ax=v+l$
suchst ($v$ und $l$ sind gegeben), Du ein Lineares Gleichungssystem lösen musst. Welches Verfahren dafür am geeignetsten ist, hängt von der Gestalt der Matrix $A$ ab.
> Hab jetzt auch nochmal versucht etwas nachzuforschen und
> jetzt bin ich auf die beiden nachfolgenden Gleichungen
> gekommen. Jetzt ist mir natürlich noch nicht ganz klar,
> wann man welche benutzt, deshalb würde ich gerne wissen
> wann man
>
> A*x=b
>
> und wann
>
> [mm]A^T*A*x=A^T*b[/mm] (diese ähnelt ja: [mm]x=(A^T*A)^-1*A^T*l)[/mm]
>
> anwendet.
Ich weiß nicht was Du möchtest. Erkläre mir erst einmal den von Dir gemeinten Zusammenhang zwischen $b,l$ und $v$.
> Weiß denn jemand, ob [mm]A^T*A*x=A^T*b[/mm] gleich
> [mm]x=(A^T*A)^-1*A^T*l)[/mm] ist?
Es ist nicht gleich! Schon wieder tauchen $l$ und $b$ auf. Im Falle, dass $A$ und [mm] $A^T$ [/mm] invertierbar sind, gilt:
[mm] $A^TAx=A^Tb\;\Longrightarrow\;A^{-1}(A^T)^{-1}A^Tb=\left(A^TA\right)^{-1}A^Tb$
[/mm]
Gruß
|
|
|
| |
|
Hallo Denny,
> ich muss auch zugeben, dass ich nicht wirklich verstehe
> worauf Du hinaus möchtest, aber gehen wir es mal an. Ich
> fasse zusammen:
Ja, es ist nicht leicht für mich zu erklären, weil ich es eben nicht richtig verstehe. Sorry.
Diese nachfolgend aufgeführte Situation ist mir vertraut.
> > Ich habe folgende Zielsituation:
> > v=A*x-l
> >
> > A: Design-/Koeffizientenmatrix
> > x: Unbekanntenvektor
> > l: Beobachtungsvektor
> > v: Vektor der Verbesserungen
Dies ist mir allerdings nicht sonderlich bekannt:
A * x = b
Ich frage mich, ob es zwischen den beiden Gleichungen einen Zusammenhang gibt.
> Hier verstehe ich schon einmal etwas nicht. Es ist doch
> [mm]b=v+l[/mm], denn Deiner Beschreibung nach zufolge gilt:
> [mm]v+l=Ax=b[/mm]
Ja, das ist eben meine Frage: Ist [mm]b=v+l[/mm] und deshalb [mm]v+l=Ax=b[/mm]? Oder nicht?
> Dir ist hoffentlich klar, dass, wenn Du den Vektor [mm]x[/mm] mit
> [mm]Ax=v+l[/mm]
> suchst ([mm]v[/mm] und [mm]l[/mm] sind gegeben), Du ein Lineares
> Gleichungssystem lösen musst. Welches Verfahren dafür am
> geeignetsten ist, hängt von der Gestalt der Matrix [mm]A[/mm] ab.
D.h. wenn A (nxn), dann verwende ich A*x=b und wenn A (nxm) n>m verwende ich [mm] A^T*A*x=A^T*b [/mm] ?
> Ich weiß nicht was Du möchtest. Erkläre mir erst einmal den
> von Dir gemeinten Zusammenhang zwischen [mm]b,l[/mm] und [mm]v[/mm].
v: Verbesserungsvektor
l: Beobachtungsvektor
b: ? (weiß ich ja auch nicht)
> > Weiß denn jemand, ob [mm]A^T*A*x=A^T*b[/mm] gleich
> > [mm]x=(A^T*A)^-1*A^T*l)[/mm] ist?
> Es ist nicht gleich! Schon wieder tauchen [mm]l[/mm] und [mm]b[/mm] auf. Im
> Falle, dass [mm]A[/mm] und [mm]A^T[/mm] invertierbar sind, gilt:
b=l? Keine Ahnung, ob das so gilt.
Lieben Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:33 Fr 22.05.2009 | | Autor: | Karl_Pech |
Hallo Bluemchen09,
Habt ihr denn irgendein Skript/Buch bzw. Lernmaterialen an denen ihr euch orientiert? Dort müßte drinstehen, wie alles definiert ist und miteinander zusammenhängt.
Viele Grüße
Karl
P.S. Falls du noch ein Beispiel zur Cholesky-Zerlegung sehen willst, so sieh dir die Materialienseite zum Numerik-Forum an. Ganz am Schluss des Themas "Cholesky-Zerlegung" wird noch ein Beispiel gerechnet.
|
|
|
| |
|
Hallo Karl,
>
>
> Habt ihr denn irgendein Skript/Buch bzw. Lernmaterialen an
> denen ihr euch orientiert? Dort müßte drinstehen, wie alles
> definiert ist und miteinander zusammenhängt.
Nee, leider zu dem A*x=b habe ich nichts weiter und das was ich habe, dort steht leider nicht, was die einzelnen Matrizen/Vektoren aussagen.
Aber ich hab im I-Net ne Seite gefunden, leider weiß ich nicht so ganz, ob ich das richtig verstehe.
http://people.inf.ethz.ch/arbenz/MatlabKurs/node41.html
Ich verstehe es ja so, dass ich [mm] A^T*A*x=A^T*b [/mm] verwende, wenn ich mehr Gleichungen als Unbekannte habe, also n>m. Und A*x=b wenn ich genauso viele Gleichungen wie Unbekannte habe. Wäre das korrekt, dann wäre ich ja schon mal einen Schritt weiter...
LG
|
|
|
| |
|
> http://people.inf.ethz.ch/arbenz/MatlabKurs/node41.html
>
> Ich verstehe es ja so, dass ich [mm]A^T*A*x=A^T*b[/mm] verwende,
> wenn ich mehr Gleichungen als Unbekannte habe, also n>m.
Mir scheint, es funktioniert nur für [mm]m > n\![/mm], denn [mm]n>m\![/mm] wäre "mehr Unbekannte als Gleichungen"; Das aber scheitert an der Multiplikation mit [mm]b\![/mm]. Z.B. sei [mm]A:=(1,2)\![/mm]. D.h. [mm]A^T = \left(\begin{smallmatrix}1\\2\end{smallmatrix}\right)[/mm]. Man kann zwar [mm]A^TA = \left(\begin{smallmatrix}1&2\\2&4\end{smallmatrix}\right)[/mm] berechnen, aber die Multiplikation [mm]A^Tb = \left(\begin{smallmatrix}1\\2\end{smallmatrix}\right)\left(\begin{smallmatrix}b_1\\b_2\end{smallmatrix}\right)[/mm] ist nicht definiert. Andersrum für [mm]A := \left(\begin{smallmatrix}1\\2\end{smallmatrix}\right)[/mm] funktioniert es.
> Und A*x=b wenn ich genauso viele Gleichungen wie Unbekannte
Ja, richtig. Da mußt du an den Matrixdimensionen nichts mehr ändern. Aber die Methode der kleinsten Quadrate ist ja auch nur für überbestimmte Gleichungssysteme gedacht.
Viele Grüße
Karl
|
|
|
| |
|
Hi,
> Mir scheint, es funktioniert nur für [mm]m > n\![/mm], denn [mm]n>m\![/mm]
> wäre "mehr Unbekannte als Gleichungen"; Das aber scheitert
> an der Multiplikation mit [mm]b\![/mm]. Z.B. sei [mm]A:=(1,2)\![/mm]. D.h.
> [mm]A^T = \left(\begin{smallmatrix}1\\2\end{smallmatrix}\right)[/mm].
> Man kann zwar [mm]A^TA = \left(\begin{smallmatrix}1&2\\2&4\end{smallmatrix}\right)[/mm]
> berechnen, aber die Multiplikation [mm]A^Tb = \left(\begin{smallmatrix}1\\2\end{smallmatrix}\right)\left(\begin{smallmatrix}b_1\\b_2\end{smallmatrix}\right)[/mm]
> ist nicht definiert. Andersrum für [mm]A := \left(\begin{smallmatrix}1\\2\end{smallmatrix}\right)[/mm]
> funktioniert es.
Ja stimmt, meinte ich eigentlich auch.
> > Und A*x=b wenn ich genauso viele Gleichungen wie Unbekannte
>
> Ja, richtig. Da mußt du an den Matrixdimensionen nichts
> mehr ändern. Aber die Methode der kleinsten Quadrate ist ja
> auch nur für überbestimmte Gleichungssysteme gedacht.
Ich versuch einfach nur folgende Seite zu verstehen, da sie in englisch geschrieben ist, habe ich da so manche Problemchen:
http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/CURVE-APP-global.html
Am Ende bekommt man dort die Matrizen/Vektoren: [mm] (N^T*N)*P=Q
[/mm]
Ich vermute diese bedeuten: A*x=b
Und wie gesagt, die mir bekannte Formel lautet: v=A*x-l
Jetzt versuche ich eben, den zusammenhang zwischen diesen heraus zu bekommen. Vielleicht gibt es ja auch keinen.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Di 26.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:20 So 24.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
