Existenz von Nullstellen? < mehrere Veränderl. < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:40 Mo 13.10.2008 | | Autor: | Draugr |
Hallo,
ich muss für einen Algorithmus bestimmen können ob ein Polynom mit 2 Veränderlichen Nullstellen hat. Der Algorithmus kommt aus dem Gebiet der geometrischen Algebra und besteht darin, dass zwei geometrische Körper in eben ein solches Polynom umgeformt wurden (das habe ich nicht selbst gemacht, sondern so von einem Experten auf dem Gebiet geliefert bekommen). Hat das Polynom eine oder mehrere Nullstellen, weiß ich, dass sich die beiden Körper schneiden - genau das brauche ich für meine Implementierung. :)
Hier erstmal das Polynom, es hat die Gestalt:
[mm] f(u,v)=a*u^{2}+b*u+c*v+d*v^{2}+k
[/mm]
wobei zum Beispiel [mm] a=(-0.5*gy^{2}+fz*gz+gx*fx-0.5*gx^{2}+fy*gy-0.5*fx^{2}-0.5*gz^{2}-0.5*fz^^{2}-0.5*fy^{2}), [/mm] die darin vorkommenden Buchstaben sind aber alle keine Veränderlichen, fz ist z.B. die Z-Koordinate des Punktes f des oben erwähnten Körpers.
Meine Fragen sind also:
- Gibt es ein effizientes Verfahren um herauszufinden ob dieses Polynom dann Nullstellen hat? Da der Algorithmus zur Laufzeit eines Programms angewendet werden soll ist es natürlich umso besser je schneller das passiert.
- Kann man irgendwie nachweisen, dass man wirklich alle möglichen Nullstellen abgedeckt hat?
Es tut mir leid falls diese Fragen ziemlich doof sind, aber mein Grundstudium ist doch schon einige Jahre her und da ich das alles nicht mehr verwenden musste in der Zeit ist das Wissen fast komplett wieder verschwunden. :( Mann, komm ich mir blöd vor.
Jede Hilfe oder Erläuterung wäre sehr nett! :)
Viele Grüße
Draugr
edit: Ganz ganz wichtig, ich habe die Konstante in der Funktion vergessen, vielen Dank an Al-Chwarizmi, der das gleich bemerkt hat! Jetzt ist sie hineineditiert, sorry!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:42 Mo 13.10.2008 | | Autor: | Zorba |
Vielleicht mit einem numerischen Verfahren?
Newton-verfahren? CG-Verfahren?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:13 Mo 13.10.2008 | | Autor: | Draugr |
Das wäre für mich aber vermutlich mit Spatzen auf Kanonen geschossen, da diese Verfahren ja das Gleichungssystem lösen, oder? Ich brauche ja aber nicht die Information wo genau irgendwelche Nullstellen liegen, sondern nur die, ob es keine Nullstellen gibt oder mehr als 0 (siehe meine Antwort zu der anderen Antwort). Und dafür wären diese beiden Verfahren overkill oder habe ich die jetzt bei meiner kurzen Netzsuche falsch verstanden?
Danke und Gruß
Chris
|
|
|
| |
|
Hallo Chris,
eine Frage im Voraus:
handelt es sich bei u, v und f(u,v) um reelle Zahlen ?
unter obiger Voraussetzung eine erste Teilantwort:
Wenn a und d entgegengesetzte Vorzeichen haben, d.h.
falls a*d<0 ist, gibt es sicher Nullstellen.
Ist a>0 und b>0, so ist der Graph von f im [mm] \IR^3 [/mm] eine
nach oben geöffnete Fläche (elliptisches Paraboloid) mit
einem absoluten Tiefpunkt. Ist dessen z-Koordinate positiv,
gibt es keine Nullstellen; ist sie null oder negativ, so gibt
es mindestens eine Nullstelle.
Die Nullstellen kann man im Allgemeinen nicht aufzählen,
da es, wenn es überhaupt welche gibt, unendlich viele
geben kann.
LG Al
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:10 Mo 13.10.2008 | | Autor: | Draugr |
Vielen Dank schonmal für deine Antwort :)
Ja, dabei handelt es sich um reelle Zahlen, genauso wie bei den Parametern.
Unter Berücksichtigung deiner Antwort stelle ich meine Frage noch einmal anders: Ist es möglich zu sagen "Wenn ich keine Nullstelle gefunden habe gibt es sicher keine"? Sobald ich eine Nullstelle gefunden habe kann ich abbrechen, da sich die Körper dann schneiden. Wenn n also die Anzahl der Nullstellen ist brauche ich nur die Information "Ist n=0 oder n>0?".
Daher wäre das Newton-Verfahren wenn ich es richtig verstanden habe für mich nicht sinnvoll, da es viel Rechenzeit für die Bestimmung der Nullstellen benötigt - diese genaue Information brauche ich ja aber gar nicht.
Was wohl optimal für meine Bedürfnisse wäre, wäre eine ganze Reihe von zu prüfenden Verhältnissen, wie du sie als Teilantwort vorgeschlagen hast "Wenn a und d entgegengesetzte Vorzeichen haben, d.h. falls a*d<0 ist, gibt es sicher Nullstellen.". Nur das eben so dass ich mir sicher sein kann, dass falls es keine Nullstelle gibt, diese Antwort auch so passt.
Vielen Dank und viele Grüße
Chris
edit: Oh Mist, ich habe das hier als Mitteilung und nicht als Frage ausgewählt, sorry. :(
|
|
|
| |
|
> Unter Berücksichtigung deiner Antwort stelle ich meine
> Frage noch einmal anders: Ist es möglich zu sagen "Wenn ich
> keine Nullstelle gefunden habe gibt es sicher keine"?
Das kann ich nicht beantworten, weil ich dazu
deine Suchmethode kennen müsste...
> Sobald ich eine Nullstelle gefunden habe kann ich
> abbrechen, da sich die Körper dann schneiden. Wenn n also
> die Anzahl der Nullstellen ist brauche ich nur die
> Information "Ist n=0 oder n>0?".
Es macht hier keinen Sinn, von einer Anzahl n
der Nullstellen zu sprechen.
Es gibt entweder genau eine, gar keine oder aber
unendlich viele Nullstellen.
> Daher wäre das Newton-Verfahren wenn ich es richtig
> verstanden habe für mich nicht sinnvoll, da es viel
> Rechenzeit für die Bestimmung der Nullstellen benötigt -
> diese genaue Information brauche ich ja aber gar nicht.
Wenn du die Nullstellen selber gar nicht brauchst,
würde ich nicht empfehlen, mit einem Näherungs-
verfahren herumzusuchen.
> Was wohl optimal für meine Bedürfnisse wäre, wäre eine
> ganze Reihe von zu prüfenden Verhältnissen, wie du sie als
> Teilantwort vorgeschlagen hast "Wenn a und d
> entgegengesetzte Vorzeichen haben, d.h. falls a*d<0 ist,
> gibt es sicher Nullstellen.". Nur das eben so dass ich mir
> sicher sein kann, dass falls es keine Nullstelle gibt,
> diese Antwort auch so passt.
Ich glaube, das kann man hier haben, wenn man
den Zugang via (Differential-)Geometrie wählt.
Sind dir Funktionen f(x,y) und ihre Untersuchung
mittels der partiellen Ableitungen [mm] \bruch{\partial{f}}{\partial{x}}=f_x,
[/mm]
[mm] \bruch{\partial{f}}{\partial{y}}=f_y [/mm] etc. bekannt ?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:47 Mo 13.10.2008 | | Autor: | Draugr |
> Es macht hier keinen Sinn, von einer Anzahl n
> der Nullstellen zu sprechen.
> Es gibt entweder genau eine, gar keine oder aber
> unendlich viele Nullstellen.
Hmm, ich bin mir jetzt gerade unsicher ob ich mein Problem richtig beschrieben habe oder ob mein mathematisches Verständnis nicht ganz ausreicht. Vielleicht nochmal gerade um sicherzugehen, dass ich nicht irgendetwas bei der Beschreibung falsch gemacht oder ausgelassen habe einige Details:
Es geht darum, dass ich in einem Programm eine Kollisionsabfrage zwischen zwei Körpern im [mm] \IR^{3} [/mm] unter Zuhilfenahme von Verfahren der Geometric Algebra vornehmen möchte. Mittels dieser hat mir jemand das so umformen können, dass sich das Problem darauf reduziert herauszufinden ob das bereits genannte Polynom entweder keine Nullstelle hat (kein Kollision) oder eine oder mehr Nullstellen (Kollision). Die Parameter a,b,c,d im Polynom bestimmen sich aus den Koordinaten der zu untersuchenden Körper, sie sind also für die gesamte Dauer einer jeweiligen Untersuchung fest, variabel sind also wirklich nur u und v.
Optimal sind für mich jetzt natürlich Aussagen wie "wenn a und d entgegengesetzte Vorzeichen haben gibt es eine Nullstelle". Das setze ich in meinem Code durch eine sehr schnelle und einfache Abfrage wie "If (signum(a) != signum(d)) kollision=true" um. Nur müsste ich eben irgendwie wissen ob ich wenn ich all diese Verhältnisse überprüft habe auch sicher sein kann ob es keine Nullstelle gibt (und nicht, dass ich einfach nur keine gefunden habe).
Ich müsste also verifizieren können dass:
[mm] \forall_{u}\forall_{v}.f(u,v)\not=0 [/mm] (ich hoffe das ist quantorenlogisch richtig formuliert)
Denn nur dann wüsste ich sicher, dass die beiden Körper nicht kollidieren.
> Ich glaube, das kann man hier haben, wenn man
> den Zugang via (Differential-)Geometrie wählt.
> Sind dir Funktionen f(x,y) und ihre
> Untersuchung
> mittels der partiellen Ableitungen
> [mm]\bruch{\partial{f}}{\partial{x}}=f_x,[/mm]
> [mm]\bruch{\partial{f}}{\partial{y}}=f_y[/mm] etc.
> bekannt ?
Ja, partielle Ableitungen müsste ich noch einigermassen hinbekommen, notfalls muss ich mich halt wieder einlesen. :)
Vielen Dank und Gruß
Chris
|
|
|
| |
|
Etwas Wichtiges ist mir gerade noch aufgefallen:
die Funktion [mm] f(u,v)=a*u^2+b*u+c*v+d*v^2 [/mm] hat natürlich
immer die Nullstelle (u/v)=(0/0) !
Fehlt in der Formel vielleicht noch ein konstanter Summand ?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:29 Mo 13.10.2008 | | Autor: | Draugr |
Oh je, natürlich, da fehlt noch eine konstante, also
$ [mm] f(u,v)=a\cdot{}u^2+b\cdot{}u+c\cdot{}v+d\cdot{}v^2+k [/mm] $
Ich werde das gleich mal in den ursprünglichen Post hineineditieren, entschuldigung!
|
|
|
| |
|
> Oh je, natürlich, da fehlt noch eine konstante, also
>
> [mm]f(u,v)=a\cdot{}u^2+b\cdot{}u+c\cdot{}v+d\cdot{}v^2+k[/mm]
>
Dacht' ich mir's doch ...
Das Polynom ist auch so noch sehr einfach. Also gehen
wir die verschiedenen Fälle nochmal durch:
0.) a*d <0
(d.h. a und d haben entgegengesetzte Vorzeichen)
Der Graph von f ist ein hyperbolisches Paraboloid, das
alle möglichen [mm] z\in \IR [/mm] enthält. Deshalb gibt es
stets auch [mm] (\infty [/mm] viele) Nullstellen.
I.) a>0 und d>0
Der Graph ist ein nach oben geöffnetes ellipt. Paraboloid.
Sein absoluter Tiefpunkt T liegt an der Stelle,
wo [mm] f_x=0 [/mm] und [mm] f_y=0. [/mm] Die entsprechende Rechnung
führt auf [mm] u_T=\bruch{-b}{2a} [/mm] und [mm] v_T=\bruch{-c}{2d}
[/mm]
Der z-Wert von T ist also
[mm] $z_T\ [/mm] =\ [mm] f(\bruch{-b}{2a},\bruch{-c}{2d})\ [/mm] =\ [mm] k-\bruch{1}{4}*(\bruch{b^2}{a}+\bruch{c^2}{d})$
[/mm]
Ist [mm] z_T [/mm] >0, liegt das gesamte Paraboloid oberhalb der
Ebene z=0 , d.h. es kann keine Nullstelle geben.
Im Fall [mm] z_T=0 [/mm] gibt es genau eine Nullstelle (genau in T).
Für das Kollisionsproblem bedeutet dies ev. gerade eine
Berührung in einem Punkt (?).
Falls [mm] z_T<0, [/mm] schneidet das Paraboloid die Ebene z=0 längs
einer Ellipse; f hat unendlich viele Nullstellen.
II.) a<0 und d<0
Ganz analog; Paraboloid nach unten geöffnet mit Hochpunkt H
(für [mm] u_H [/mm] und [mm] v_H [/mm] gelten die gleichen Formeln wie für [mm] u_T [/mm] und [mm] v_T
[/mm]
im Fall I. ).
Durch Multiplikation des Polynoms mit (-1) kann man diesen
Fall auf Fall I. zurückführen.
III.) a=d=0
In diesem Fall haben wir als Graph von f eine Ebene.
Ausser im Falle, wo [mm] k\not= [/mm] 0 und b=c=0 , gibt es stets
Nullstellen.
IV.) a≠0 und d=0
[mm] f(u,v)=a*u^2+b*u+c*v+k
[/mm]
Der Graph ist eine parabolische Zylinderfläche.
Falls [mm] c\not=0, [/mm] gibt es stets zu jedem beliebigen [mm] u\in \IR [/mm] eine Nullstelle.
Falls c=0, bleibt eine einfache Aufgabe zum Thema "quadratische Gleichung" ...
V.) a=0 und d≠0
Analog zu IV. , mit vertauschten Rollen.
Jetzt wird es noch darum gehen, die vielfältigen Fallunter-
scheidungen (auf nicht zu komplizierte Art) in einen
brauchbaren Entscheidungsalgorithmus zu verpacken.
Es kann durchaus sein, dass man dabei noch Vereinfa-
chungsmöglichkeiten entdeckt.
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:13 Mo 13.10.2008 | | Autor: | Draugr |
Ganz herzlichen Dank schonmal, du hast mir sehr weitergeholfen! :)
Kann ich mir bei diesen Möglichkeiten schon sicher sein, dass dies alle Konstellationen abdeckt, d.h. wenn ich all diese Fälle prüfe und sich bei jedem ergibt, dass ich keine Nullstelle habe, ist das dann auch sicher so? Falls ich dafür einen formellen Nachweis führen wollte (nämlich für die ausstehende Dokumentation meines Algorithmus), wie müsste ich das systematisch angehen? Oder ist das direkt ersichtlich, nur eben nicht für mich, der erst langsam wieder in die Analysis hereinfindet? ;)
Danke nochmal!
|
|
|
| |
|
Hallo Chris,
> Kann ich mir bei diesen Möglichkeiten schon sicher sein,
> dass dies alle Konstellationen abdeckt, d.h. wenn ich all
> diese Fälle prüfe und sich bei jedem ergibt, dass ich keine
> Nullstelle habe, ist das dann auch sicher so?
ich habe versucht, die möglichen Fälle abzudecken und
hoffe, dabei keine (wenigstens keine schlimmen) Fehler
gemacht zu haben
vielleicht schaut ja noch jemand alles genau durch...
> Falls ich dafür einen formellen Nachweis führen wollte
> (nämlich für die ausstehende Dokumentation meines
> Algorithmus), wie müsste ich das systematisch angehen?
> Oder ist das direkt ersichtlich, nur eben nicht für mich,
> der erst langsam wieder in die Analysis hereinfindet? 
So schwierig sollte das nicht sein, und jedenfalls zu
empfehlen, wenn du die Ergebnisse dokumentieren
und vertreten musst. Das Thema ist eigentlich
"Flächen zweiter Ordnung", zu dem du im Netz recht
viel Material finden solltest.
Und wenn Probleme auftauchen, dann ist der MatheRaum
sicher wieder für dich da.
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:24 Mo 13.10.2008 | | Autor: | Draugr |
Dann zunächst einfach nochmal ganz vielen Dank und ich schreibe das hier als Mitteilung, damit keine Frage mehr offen ist. :) Jetzt mach ich mich mal an die Implementierung.
Viele Grüße
Chris
|
|
|
|
