Singuläres GS lösen < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:36 So 24.07.2011 | | Autor: | lorenz74 |
| Aufgabe | Bei der Berechnung von B-Spline Kurven ergibt sich folgendes mathematisches Problem:
[mm] D_{c} [/mm] = [mm] \summe_{i=0}^{n}B_{i}^{k}(s_{c})*q_{i} [/mm] (1)
wobei k die Ordnung, B die jweilige Basisfunktion, [mm] s_{c} [/mm] die entsprechenden Parameter (0 [mm] \le s_{c} \le [/mm] 1) (0 [mm] \le [/mm] c [mm] \le [/mm] n) und q die Kontrollpunkte der B-Spline Kurve sind. [mm] D_{c} [/mm] sind die fertig interpolierten Werte. Die Basisfunktionen sind wie folgt definiert:
[mm] B_{i}^{0}(s_{c})=\begin{cases} 1, & \mbox{falls } u_{i}\le s_{c} \le u_{i+1} \\ 0, & \mbox{sonst}\end{cases}
[/mm]
[mm] B_{i}^{k}(s_{c})=\bruch{s_{c}-u_{i}}{u_{i+k}-u_{i}}*B_{i}^{k-1}(s_{c})+\bruch{u_{i+k+1}-s_{c}}{u_{i+k+1}-u_{i+1}}*B_{i+1}^{k-1}(s_{c})
[/mm]
u ist hierbei der sog. Knotenvektor der B-Spline Kurve. Man löse das Gleichungssystem nach q auf. D, u und k seien gegeben. Das hier beschriebene Problem wird auch als sog. "curve fitting" beschrieben. Näheres dazu gibt es im folgenden PDF: http://www.comp.leeds.ac.uk/yisong/archives/YiSong_PhDThesis.pdf
Einleitung zur Thematik ab Seite 68 (Seite 83 im PDF File).
Gleichungen und oben genanntes Problem ab Seite 85 (Seite 100 im PDF File) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Meine Idee:
Gleichung (1) lässt sich auch als Matrix darstellen:
[mm] \vektor{D_{0} \\ D_{1} \\ \vdots \\ D_{n}} [/mm] = [mm] \pmat{B_{0}^{k}(s_{0}) & B_{1}^{k}(s_{0}) & \ldots & B_{n}^{k}(s_{0}) \\ B_{0}^{k}(s_{1}) & B_{1}^{k}(s_{1}) & \ldots & B_{n}^{k}(s_{1}) \\ \vdots & \vdots & \ddots & \vdots \\ B_{0}^{k}(s_{n}) & B_{1}^{k}(s_{n}) & \ldots & B_{n}^{k}(s_{n})}*\vektor{q_{0} \\ q_{1} \\ \vdots \\ q_{n}} [/mm] (2)
Kürzer:
D=B*q (3)
Zuerst wollte ich einfach die Inverse von der Matrix bilden und dann damit (von links) multiplizieren:
[mm] B^{-1}*D=q
[/mm]
Leider habe ich dann rausbekommen, dass A singulär ist, da ihre Determinante gleich 0 ist. Das bedeutet, dass A nicht invertierbar ist.
Weiterhin hatte ich überlegt eine LU Zerlegung durchzuführen. Diese funktioniert aber nur wenn die Matrix regülär bzw. invertierbar ist.
Meine Frage ist nun, ob jemand weiß wie ich eine singuläres Gleichungssystem löse.
Ich habe den im PDF File beschriebenen Algorithmus bereits implementiert, bekomme aufgrund der Nichtinvertierbarkeit von B aber entweder 0 oder falsche Ergebnisse raus. Vielleicht habe ich die Problematik jetzt ein wenig zu ausführlich beschrieben, da ich ja eigentlich nur wissen will wie ich ein singuläres GS lösen kann. Ich hoffe trotzdem, dass mir jemand einen guten Tipp geben kann.
Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:59 Mo 25.07.2011 | | Autor: | Stoecki |
ich kenne mich nicht wirklich mit b-splines aus, aber es gibt einige andere numerische verfahren, in denen bestimmte parameter einfach gesetzt werden. zum beispiel bei einigen quadraturverfahren ist das der fall. üblicherweise hat man einen allgemein gültigen matrixrang gegeben, weswegen man den freiheitsgrad kennt.
in deinem fall bin ich mir aber gerade gar nicht sicher, ob die matrix wirklich nicht invertierbar ist. für k=0 ist es eine obere dreiecksmatrix, deren diagonaleinträge immer 1 sind. diese wäre also in jedem fall invertierbar. das würde ich im zweifel noch mal prüfen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:57 Mo 25.07.2011 | | Autor: | lorenz74 |
hi,
erstmal danke für deine Antwort. Ich lasse mir momentan die Basismatrix B für k=3 mittels einem Algorithmus in C++ berechnen. Den Algo habe ich selber geschrieben und ich bin mir recht sicher, dass dieser richtig implementiert ist. Danach trage ich die Ergebnisse in eine OpenCV-Matrix B ein. Zur Invertierung benutze ich die Funktion cvInvert(B). Die Determinante lasse ich mir über die Funktion determinant(B^-1) ausrechnen. Es kann natürlich sein, dass entweder die Basismatrix falsch ist oder die OpenCV Funktionen cvInvert() bzw. determinant(...) falsche Ergebnisse liefern. Ich werde mir zur Determinante nochmal Gedanken machen.
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:19 Sa 30.07.2011 | | Autor: | lorenz74 |
Hi Leute,
mein Problem hat sich zum Glück von selbst gelöst. Das GS ist garnicht singulär. Für Leute die trotzdem ein singuläres GS lösen wollen, empfiehlt sich die sog. Pseudoinverse. Diese lässt bsp. mit Lapackpp über die SVD (Singualr Value Decomposition) errechnen.
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:33 Sa 30.07.2011 | | Autor: | felixf |
Moin,
> mein Problem hat sich zum Glück von selbst gelöst. Das GS
> ist garnicht singulär.
ja, das wollte ich auch gerade mal nachpruefen, als ich dann sah dass du das bereits geloest hast :)
Ich hab die Frage mal auf "reagiert" gesetzt.
LG Felix
|
|
|
|
