spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Meh. Hab nochmal über die Aufgabe nachgedacht. Ich dachte die ganze Zeit, man müsste irgendeinen Trick anwenden, dabei ist die Aufgabenstellung viel einfacher, als ich dachte. Die Lösung ist dadurch natürlich immer noch nicht einfacher. Dein §\left(\lambda_{1}-\lambda\right)^{n_{1}}\ldots\left(\lambda_{k}-\lambda\right)^{n_{k}}§ ist ja einfach nur das charakteristische Polynom in Linearfaktoren zerlegt. Und um die zu bekommen muss man halt die Nullstellen bestimmen (und bestimmen, wie häufig die Nullstellen vorkommen, das sind dann deine Exponenten). In diesem Sinne ist dein ganzes Problem also äquivalent zur Nullstellensuche bei Polynomen. Und die ist schwierig. Du wirst also natürlich bei allen Determinantenregeln auf irgendwelche Summen kommen, die du so erstmal nicht umformen kannst. Wäre es anders, d.h. gäbe es für dein Problem eine einfache Lösung, könnte man damit wohl auch Nullstellen von Polynomen leicht finden.

Wie kann man die Aufgabe jetzt also lösen?
Für kleine Matrizen, gibt es direkte Formeln. Zu finden in den jeweiligen Wikipedia-Artikeln:
Grad 2: https://de.wikipedia.org/wiki/Quadratische_Gleichung
Grad 3: https://de.wikipedia.org/wiki/Kubische_Gleichung
Grad 4: https://de.wikipedia.org/wiki/Quartische_Gleichung
Für alles was größer ist, gibt es keine direkte Formel (und wird sie auch niemals geben, das ist bewiesen). Was 'ganz gut' geht, ist Nullstellen raten und dann Polynomdivision durchzuführen. Sehr hilfreich dabei kann wohl der Satz über rationale Nullstellen sein. In typischen Mathe-Aufgaben hat man ja meist schöne Zahlen, und kommt damit vermutlich schnell auf eine Lösung. Das tut man dann so lange, bis das Polynom einen Grad erreicht hat, den man direkt lösen kann.

Ansonsten hast du hier halt eigentlich ein Eigenwert-Problem. Und dafür gibt es auch viele Algorithmen, aber halt nur numerische (die Analytischen laufen halt alle auf das lösen von Polynomen heraus und das haben wir oben besprochen). Die will man vermutlich nicht per Hand ausrechnen, weil man gegebenenfalls viele Iterationen benötigt. Eine Liste an Möglichkeiten gibt es hier: https://de.wikipedia.org/wiki/Eigenwertproblem#Numerische_Berechnung


Fazit: Dein Problem ist schwer und es gibt keine direkte Lösung.

Ich bin ja immernoch der Auffassung, dass die Nullstellen einfach abgelesen werden können, wenn man die Matrix vorher diagonalisiert, oder habe ich da einen gedanklichen Fehler gemacht?

Natürlich können die Nullstellen nach dem diagonalisieren abgelesen werden. Das Problem ist, dass man sie schon zum diagonalisieren selbst braucht.

Zitat von »birdfreeyahoo«

Ne braucht man nicht, das kann ich einfach durch Gauß-Umformungen machen.

Das würde ich sehr gerne mal sehen. Damit hättest du nämlich eine Möglichkeit gefunden, Nullstellen von Polynomen beliebigen Grades zu finden.

Vermutlich wird hier diagonale Matrix einmal als "alles außer der Diagonale gleich 0" und einmal als "alles unter der Diagonale gleich 0" verstanden.

Wie schon gesagt, es gibt keine direkte Lösung für große Matrizen, nur Annäherungsverfahren (abgesehen von leichteren Spezialfällen).

Zitat von »Jonathan_Klein«

Vermutlich wird hier diagonale Matrix einmal als "alles außer der Diagonale gleich 0" und einmal als "alles unter der Diagonale gleich 0" verstanden.

Das eine ist eine Diagonalmatrix, das andere eine obere Dreiecksmatrix. In beiden Fällen ist die Determinante einfach das ausmultiplizieren der Diagonaleinträge. Mit der Leibniz-Formel sieht man das am einfachsten. Aber natürlich beißt sich die Ratte in den Schwanz, wenn man die Matrix erst diagonalisieren möchte, um die EW abzulesen. Zumal nicht jede Matrix diagonalisierbar ist. (Eine obere Dreickecksmatrix bekommt man hingegen schon hin).

Edit:

Zitat von »birdfreeyahoo«

Ich kann die Matrix per Gaußumformung in eine obere Dreiecksmatrix umwandeln. Dann ergibt sich die Determinante doch aus dem Produkt der Diagonale.

Ja. Aber das bringt einen Qualitativ in diesem Fall glaub ich nicht weiter, da man am Ende auch hier die Nullstellen des Polynoms ermitteln muss. Oder in anderen Worten: Das Nullstellenproblem ist um einiges schwieriger als die Berechnung der Determinante.

Zitat von »birdfreeyahoo«

Dann ergibt sich die Determinante doch aus dem Produkt der Diagonale.

Schon, aber die Determinante bringt dir halt nichts.

Zitat von »GreenPepper«

Das Nullstellenproblem ist um einiges schwieriger als die Berechnung der Determinante.

Genau, und man sollte das sogar noch viel deutlicher sagen. die Determinante kann man mit 'einfachen' Formeln berechnen, mit etwas besseren Formeln kann man sie auch sehr effizient berechnen. Determinantebestimmung ist ein gelöstes Problem, und nichts das irgendwie Schwierigkeiten bereiten würde. Die Nullstellenberechnung hingegen ist ein erwiesenermaßen 'unlösbares' Problem. Es gibt gute Algorithmen, mit denen man die relativ effizient mit einer hohen Genauigkeit ausrechnen kann, aber halt nur in Außnahmesituationen exakt.

Wenn du immernoch eine konkrete Aufgabe zu lösen hast. Du kannst zum Beispiel Python mit Numpy benutzen, was dir viele Werkzeuge zur Hand gibt um Eigenwerte und Nullstellen effizient und einfach zu berechnen. Damit hast du im Grunde eine fertige Implementierung der aktuellen State-of-the-Art Algorithmen