ganzzahlige Lösung eines LGS < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei [mm] A\in\IZ^{n \times n+1}. [/mm] Gesucht ist [mm] x\in\IZ^{n+1}, [/mm] sodass Ax=0, wobei [mm] x\not=0. [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo zusammen!
Ich grüble schon seit einiger Zeit über ein Problem, das ich zwar theoretisch lösen kann, aber für das ich keinen praktischen Lösungsweg finde.
Ich habe also ein ganzzahliges, unterbestimmtes Lineares Gleichungssystem. Für dieses LGS möchte ich einen ganzzahligen Vektor ungleich dem Nullvektor finden, sodass Ax=0 ist (dass dieser Vektor existieren muss, ergibt sich aus dem Modell, aus dem sich dieses LGS ableitet).
Erschwerend kommt hinzu, dass ich eine Folge von LGS lösen möchte die jedesmal um den Faktor 3 größer werden, ich benötige also eine numerische Lösung.
Ich habe versucht dieses Problem mit Matlab zu lösen, allerdings ist Matlab nicht auf ganzzahliges rechnen ausgelegt. Für die kleineren LGS habe ich in Matlab noch "per Hand" die Lösung bekommen können, aber bei 50x51 Matrizen macht das keinen Spass.
Kennt jemand vielleicht einen Algorithmus, der mir so etwas lösen könnte?
Mir wurde außerdem empfohlen es mit einem Programm names Xpress zu versuchen, das dieses Problem lösen können soll. Kann mir das jemand bestätigen? Ich kenne mich mit Xpress gar nicht aus, und möchte verhindern dass ich mich umsonst darin einarbeite.
Also, falls jemand eine Idee hat wie ich eine Lösung programmieren könnte, gebt mir bitte einen Tip! Ein Stichwort würde mir schon genügen!
Danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:30 Mo 11.10.2010 | | Autor: | rainerS |
Hallo!
Erstmal herzlich ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> Sei [mm]A\in\IZ^{n \times n+1}.[/mm] Gesucht ist [mm]x\in\IZ^{n+1},[/mm]
> sodass Ax=0, wobei [mm]x\not=0.[/mm]
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo zusammen!
>
> Ich grüble schon seit einiger Zeit über ein Problem, das
> ich zwar theoretisch lösen kann, aber für das ich keinen
> praktischen Lösungsweg finde.
>
> Ich habe also ein ganzzahliges, unterbestimmtes Lineares
> Gleichungssystem. Für dieses LGS möchte ich einen
> ganzzahligen Vektor ungleich dem Nullvektor finden, sodass
> Ax=0 ist (dass dieser Vektor existieren muss, ergibt sich
> aus dem Modell, aus dem sich dieses LGS ableitet).
Nur nebenbei: da die Matrix A nur ganzzahlige Einträge hat, muss der Lösungsvektor aus rationalen Zahlen bestehen; und da jeder Lösungsvektor des homogenen Systems nur bis auf einen Faktor bestimmt ist, kannst du daraus immer ein Lösungsvektor mit nur ganzzahligen Einträgen machen.
> Erschwerend kommt hinzu, dass ich eine Folge von LGS lösen
> möchte die jedesmal um den Faktor 3 größer werden, ich
> benötige also eine numerische Lösung.
>
> Ich habe versucht dieses Problem mit Matlab zu lösen,
> allerdings ist Matlab nicht auf ganzzahliges rechnen
> ausgelegt. Für die kleineren LGS habe ich in Matlab noch
> "per Hand" die Lösung bekommen können, aber bei 50x51
> Matrizen macht das keinen Spass.
Nimm doch mal ein richtiges, exakt rechnendes Computeralgebrasystem, z.B. Maxima.
> Kennt jemand vielleicht einen Algorithmus, der mir so etwas
> lösen könnte?
Gauss-Jordan eignet sich sehr gut für ganzzahlige Koeffizientenmatrizen.
Viele Grüße
Rainer
|
|
|
|
