Algorithmisch saemtliche Werte eines Parameters t finden, so dass eine Matrix nur nichtnegative, ganzzahlige Einträge besitzt

12/09/2009 - 11:36 von Jens Kleinschmidt | Report spam
Hallo NG,

mein aktueles Problem:
Gesucht ist ein Algorithmus, um sàmtliche zulàssige Werte für einen
Parameter t finden, so dass alle Matrixeintràge ganzzahlig und
nichtnegativ sind

Beispiel:
x := matrix([[t], [40-3/2*t], [40-3/2*t], [-10+2*t]])

Lösung:
matrix([[2*t], [40-3*t], [40-3*t], [-10+4*t]])
mit t ganzzahlig aus [3;13]


Meine Vorgehensweise:
Lösung als Parameterdarstellung einer Gerade interpretieren und
Orts- und Richtungsvektor mit ausschließlich ganzzahligen Eintràgen
darstellen.
(hier trivial, da Ortsvektor Bedingung bereits erfüllt und
Richtungsvektor stets nur skaliert werden muss)

Im Beispiel ergibt sich:
x := matrix([[2*t], [40-3*t], [40-3*t], [-10+4*t]])

Dann erhàlt man für jedes t aus Z eine Lösung mit
ausschließlich ganzzahligen EIntràgen.

Jetzt noch das gültige Intervall für t bestimmen, so dass
x[i] >=0, i=1 .. 4 und fertig.

Behauptung: Wenn man darauf achtet, dass der ggT aller Eintràge
des Richtungsvektors 1 lautet, erhàlt man so sàmtliche mögliche
Lösungen.

Fragen:
1. Ist das Verfahren fehlerfrei und liefert es in jedem Fall alle
möglichen Ergebnisse?

2. Wie làsst sich die Fragestellung kürzer und eleganter bearbeiten?


Gruß
Jens
Gruß
Jens
 

Lesen sie die antworten

#1 Markus Wichmann
12/09/2009 - 23:14 | Warnen spam
Jens Kleinschmidt wrote:
Hallo NG,

mein aktueles Problem:
Gesucht ist ein Algorithmus, um sàmtliche zulàssige Werte für einen
Parameter t finden, so dass alle Matrixeintràge ganzzahlig und
nichtnegativ sind

Beispiel:
x := matrix([[t], [40-3/2*t], [40-3/2*t], [-10+2*t]])

Lösung:
matrix([[2*t], [40-3*t], [40-3*t], [-10+4*t]])
mit t ganzzahlig aus [3;13]




Andere Variante: Analyse der einzelnen Zellen:
(Hinweis: Egal welche Interpretation der natürlichen Zahlen nun
vorliegt, im Folgenden gelte
N* = N \cup {0}

x_11 = t. x_11 \in N* <=> t \in N* (trivial)
x_21 = 40-3/2*t. x_21 \in Z <=> t = 2s, s \in Z
Das folgt aus der Abgeschlossenheit der ganzen Zahlen gegen die
Subtraktion. Somit ist nur die Division zu neutralisieren, durch
Multiplikation mit dem Quotienten)
x_21 >= 0 <=> 40-3/2*t >= 0 <=> t <= 80/3
=> t = 2s, s \in Z, s <= 13 ( = floor(80/6))
x_31 = x_21
x_41 = -10+2*t. x41 \in Z <=> t \in Z (nur Operationen, gegen die Z
abgeschlossen ist)
x_41 >= 0 <=> 2*t-10 >= 0 <=> t >= 5

Abschließend:

t \in {t | t = 2s, s \in Z, (ceil(5/2) = ) 3 <= s <= 13}
= {6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26}

Vorteil: Ausgangsmatrix wird nicht veràndert.


Meine Vorgehensweise:
Lösung als Parameterdarstellung einer Gerade interpretieren und
Orts- und Richtungsvektor mit ausschließlich ganzzahligen Eintràgen
darstellen.



Und bei Matrizen mit mehr als einer Spalte?

(hier trivial, da Ortsvektor Bedingung bereits erfüllt und
Richtungsvektor stets nur skaliert werden muss)

Im Beispiel ergibt sich:
x := matrix([[2*t], [40-3*t], [40-3*t], [-10+4*t]])

Dann erhàlt man für jedes t aus Z eine Lösung mit
ausschließlich ganzzahligen EIntràgen.




Das schaffst du, indem du jede Operation, gegen die die ganzen Zahlen
nicht abgeschlossen sind, eliminierst. Da das nur die Division und das
Radizieren sind, hast du nicht so viel zu tun. Aber was tust du, wenn
ein Matrixterm irrationale Funktionen, wie z.B. den Sinus, verwendet?
Oder wenn t im Exponenten einer irrationalen Zahl steht? Ohne dir jetzt
was zu schweres aufbrummen zu wollen: Für welche Werte von t ist

(sqrt(2)-1)^t

ganzzahlig? AFAICS keine, solange t ganz ist. Denn dann gibt es nach
binomischem Satz immer wenigstens einen Term in der Expansion, indem der
erste Summand in ungerader Potenz auftaucht.

Übrigens ist diese Zahl algebraisch. Sie ist die Lösung einer
quadratischen Gleichung mit

-p/2 = -1 => p = 2

und

p^2/4 - q = 2 => q = -1

Also ist sie die Lösung von

x^2 + 2x - 1

Jetzt noch das gültige Intervall für t bestimmen, so dass
x[i] >=0, i=1 .. 4 und fertig.

Behauptung: Wenn man darauf achtet, dass der ggT aller Eintràge
des Richtungsvektors 1 lautet, erhàlt man so sàmtliche mögliche
Lösungen.




Die Matrix ([4], [2]) erfüllt für alle Werte von t die Bedingungen der
Nichtnegativitàt und Ganzzahligkeit, der ggT ist jedoch >1.

Fragen:
1. Ist das Verfahren fehlerfrei und liefert es in jedem Fall alle
möglichen Ergebnisse?




s.o.

2. Wie làsst sich die Fragestellung kürzer und eleganter bearbeiten?




Ganzzahligkeit:
Solange in den Matrixtermen _nur_ und _ausschließlich_ Grundrechenarten
verwendet werden, kannst du einfach t so modifizieren, dass die
Divisionen aufgehoben werden. Gegen alle anderen Grundrechenarten ist Z
abgeschlossen.

Nichtnegativitàt: Am Einfachsten findet man die
a) von Hand: Löse die Ungleichung
x_ij >= 0
b) am Computer: Analytische Ableitung an diversen Stellen vornehmen. Ist
sie kleiner als Null, liegt der nàchste Nullpunkt voraus, ansonsten
vor der untersuchten Stelle.


Gruß
Jens
Gruß
Jens



Du brauchst nicht zweimal zu grüßen...

Tschö,
Markus
GUI - ein Hintergrundbild und zwölf XTerms

vim -c "exec \"norm iwHFG#NABGURE#IVZ#UNPXRE\"|%s/#/ /g|norm g??g~~"

Ähnliche fragen