Eine Gleichung, viele Unbekannte

05.01.2014, 10:27

Ungelehrter

Eine Gleichung, viele Unbekannte

Guten Tag,

vorweg, ich bin kein Mathematiker! Folglich werden Sie viele formale Fehler finden.

Ich habe öfter mit Gleichungen zu tun, welche viele Variablen enthalten, und möchte in der Lage sein, Lösungsmengen zu bilden.

Das Schema einer solchen Gleichung sieht meist so aus:

$\begin{eqnarray*} a_{1}x_{1} + a_{2}x_{2} + ... + a_{n}x_{n} = e \end{eqnarray*}$

$\begin{eqnarray*} x \in \mathbb N _{0} \end{eqnarray*}$

$\begin{eqnarray*} a, e \in \mathbb N \end{eqnarray*}$

Dabei sind alle a und e bekannt, nur die x werden gesucht.

Ich möchte ersteinmal herausfinden, wie viele Lösungsmengen es überhaupt gibt:

$\begin{eqnarray*} |L| = 0 \end{eqnarray*}$ oder $\begin{eqnarray*} |L| = 1 \end{eqnarray*}$ oder $\begin{eqnarray*} |L| > 1 \end{eqnarray*}$

Ich nenne mal ein konkretes Beispiel mit drei Unbekannten:

$\begin{eqnarray*} 5x + 12y + 16z = 79 \end{eqnarray*}$

Eine Lösungsmenge ist hier auf jeden Fall $\begin{eqnarray*} L = \left\{\left(3;4;1\right)\right\} \end{eqnarray*}$

Das habe ich aber nur durch Probieren herausgefunden. Wie gehe ich hier mathematisch vor?

05.01.2014, 10:44

HAL 9000

Auf diesen Beitrag antworten »

Zunächst mal eine sprachliche Korrektur: "Wie viele Lösungsmengen" ist Unsinn, es gibt nur genau eine Lösungsmenge dieser Gleichung. Was du meinst ist, wie viele Lösungen diese Lösungsmenge enthält! Insofern darfst du auch nicht $\begin{eqnarray*} L = \left\{\left(3;4;1\right)\right\} \end{eqnarray*}$ schreiben, wenn es mehr als diese eine Lösung gibt, sondern allenfalls $\begin{eqnarray*} \left(3;4;1\right) \in L \end{eqnarray*}$ .

05.01.2014, 11:12

Leopold

Auf diesen Beitrag antworten »

RE: Eine Gleichung, viele Unbekannte

Zitat:

Original von Ungelehrter
Das habe ich aber nur durch Probieren herausgefunden. Wie gehe ich hier mathematisch vor?

Da wirst du wohl Kongruenzrechnung brauchen. Als weitere Lösungstripel habe ich

$\begin{eqnarray*} (3,0,4), \, (7,1,2), \, (11,2,0) \end{eqnarray*}$

05.01.2014, 11:13

Ungelehrter

Auf diesen Beitrag antworten »

@HAL 9000
Ja, da hast du Recht. Ich schrieb bereits, dass sich Fehler einschleichen werden.

Was den Lösungsweg angeht, denke ich, diesen gefunden zu haben.

Man stellt die Gleichung nach den Unbekannten um, bringt diese in die Dreiecksform und wendet dann ein Eliminierungsverfahren, wie das von Gaus an ...

@Leopold
Kannst du darauf bitte genauer eingehen?

05.01.2014, 12:45

Leopold

Auf diesen Beitrag antworten »

Das kann man nicht in wenigen Worten erklären. Ich versuche, es einmal elementar ohne Kongruenzrechnung aufzuschreiben.

Ich habe die Gleichung $\begin{eqnarray*} 5x+12y+16z=79 \end{eqnarray*}$ modulo $\begin{eqnarray*} 5 \end{eqnarray*}$ betrachtet (weil das der "einfachste" Koeffizient ist). Alle Koeffizienten werden dadurch zu Resten modulo $\begin{eqnarray*} 5 \end{eqnarray*}$ . Aus $\begin{eqnarray*} 5 \end{eqnarray*}$ wird $\begin{eqnarray*} 0 \end{eqnarray*}$ , aus $\begin{eqnarray*} 12 \end{eqnarray*}$ wird $\begin{eqnarray*} 2 \end{eqnarray*}$ , aus $\begin{eqnarray*} 16 \end{eqnarray*}$ wird $\begin{eqnarray*} 1 \end{eqnarray*}$ und aus $\begin{eqnarray*} 79 \end{eqnarray*}$ wird $\begin{eqnarray*} 4 \end{eqnarray*}$ . Das sind die Reste, die beim Dividieren der Zahlen durch $\begin{eqnarray*} 5 \end{eqnarray*}$ übrigbleiben. Man kann das auch so sagen:

$\begin{eqnarray*} 5 = 5 + 0 \end{eqnarray*}$
$\begin{eqnarray*} 12 = 10 + 2 \end{eqnarray*}$
$\begin{eqnarray*} 16 = 15 + 1 \end{eqnarray*}$
$\begin{eqnarray*} 79 = 75 + 4 \end{eqnarray*}$

Man zerlegt also die Zahlen in die nächstkleinere Fünferzahl und ihren Rest. Die Gleichung lautet jetzt

$\begin{eqnarray*} 5x + (10+2)y + (15+1)z = 75 + 4 \end{eqnarray*}$

Jetzt multipliziert man aus und faßt alle Fünferbestandteile zusammen:

$\begin{eqnarray*} 5x + 10y + 15z + 2y + z = 75 + 4 \end{eqnarray*}$

$\begin{eqnarray*} z = 4 - 2y + 5 \cdot (15-x-2y-3z) \end{eqnarray*}$

Mit der Abkürzung $\begin{eqnarray*} k = 15-x-2y-3z \end{eqnarray*}$ wird das zu

$\begin{eqnarray*} z = 4 - 2y + 5k \end{eqnarray*}$

Jetzt gibt man sich irgendwelche ganzen Zahlen $\begin{eqnarray*} y,k \end{eqnarray*}$ vor und berechnet $\begin{eqnarray*} z \end{eqnarray*}$ nach der letzten Gleichung. Dann setzt man in die Ausgangsgleichung ein. Beispiel: $\begin{eqnarray*} y=4,k=3 \end{eqnarray*}$ ergibt $\begin{eqnarray*} z=11 \end{eqnarray*}$ . In die Ausgangsgleichung eingesetzt: $\begin{eqnarray*} 5x + 48 + 176 = 79 \end{eqnarray*}$ ergibt $\begin{eqnarray*} x=-29 \end{eqnarray*}$ . Daß die hier benötigte Division durch $\begin{eqnarray*} 5 \end{eqnarray*}$ aufgeht, ist kein Zufall, sondern Folge unseres Vorgehens modulo $\begin{eqnarray*} 5 \end{eqnarray*}$ . Du kannst ja einmal selbst überlegen, warum das so ist.
So hat man $\begin{eqnarray*} (-29,4,11) \end{eqnarray*}$ als ganzzahliges Lösungstripel. Und alle weiteren ganzzahligen Lösungstripel erhält man durch dasselbe Vorgehen: $\begin{eqnarray*} y,k \end{eqnarray*}$ vorgeben und so weiter. Wenn man allgemein rechnet, bekommt man $\begin{eqnarray*} x=3+4y-16k \end{eqnarray*}$

Wenn man zusätzlich $\begin{eqnarray*} x,y,z \geq 0 \end{eqnarray*}$ haben will, führt das auf die Ungleichungen

$\begin{eqnarray*} 3+4y-16k \geq 0 \end{eqnarray*}$

$\begin{eqnarray*} y \geq 0 \end{eqnarray*}$

$\begin{eqnarray*} 4 - 2y + 5k \geq 0 \end{eqnarray*}$

Man faßt $\begin{eqnarray*} y,k \end{eqnarray*}$ nun als reelle Variable eines $\begin{eqnarray*} yk \end{eqnarray*}$ -Koordinatensystems auf. Löst man die erste und dritte Ungleichung nach $\begin{eqnarray*} k \end{eqnarray*}$ auf, so erhält man

$\begin{eqnarray*} k \leq \frac{1}{4} y + \frac{3}{16} \end{eqnarray*}$

$\begin{eqnarray*} k \geq \frac{2}{5} y - \frac{4}{5} \end{eqnarray*}$

Die drei Geraden $\begin{eqnarray*} a,b,c \end{eqnarray*}$ mit den Gleichungen $\begin{eqnarray*} y=0, \, k = \frac{1}{4}y + \frac{3}{16}, \, k = \frac{2}{5}y - \frac{4}{5} \end{eqnarray*}$ begrenzen ein Dreieck. Genau die Punkte des Dreiecks erfüllen die drei Ungleichungen von oben. Und wenn man nur ganzzahlige Lösungen sucht, darf man eben nur die Gitterpunkte im Innern oder auf dem Rand des Dreiecks nehmen.

[attach]32550[/attach]

Als Gitterpunkte $\begin{eqnarray*} (y,k) \end{eqnarray*}$ findet man so $\begin{eqnarray*} (0,0),(1,0),(2,0),(4,1) \end{eqnarray*}$ . Und mit diesen Werten erhält man für $\begin{eqnarray*} (x,y,z) \end{eqnarray*}$ die Lösungen $\begin{eqnarray*} (3,0,4),(7,1,2),(11,2,0),(3,4,1) \end{eqnarray*}$ .

Vielleicht hast du jetzt ein paar Anhaltspunkte, wie du vorzugehen hast. Allerdings werden die Dinge nicht immer so einfach verlaufen wie hier. So brauchen die Ungleichungen keinen endlichen Bereich festzulegen. Auch ließ sich etwa die Gleichung oben ohne Division leicht nach $\begin{eqnarray*} z \end{eqnarray*}$ auflösen. Das dürfte bei anderen Beispielen nicht so ohne weiteres gehen. Dann brauchst du eben doch Kongruenzrechnung. Da mußt du dich dann selber hinein vertiefen.

Neue Frage »

Antworten »

Eine Gleichung, viele Unbekannte

Verwandte Themen