Die Videos in den letzten beiden Artikeln zeigten, wie sich die Nullstellenmenge eines quadratischen Polynoms in drei Variablen mit den Koeffizienten ändert. Man kann die Frage, wie man (praktisch) die Koeffizienten aus den Nullstellen berechnet und umgekehrt, natürlich auch schon für Polynome einer Veränderlichen stellen. Einen möglichen Ansatz diskutiert der folgende Beitrag, ebenfalls von Herrn Dr. Grassmann.


(E-Mail: hgrassmann at gmx dot de)

Kommentare (8)

  1. #1 Bjoern
    9. März 2019

    Ganz nett, aber es ist nicht wirklich klar, was man damit machen kann… geht es letztlich (wie am Schluss dann steht) nur darum, ein Verfahren zur Matrixinversion herzuleiten?

    Es fehlt auch eine Angabe der Voraussetzungen. Anscheinend betrachtet man nur Polynome n-ten Grades, die genau n verschiedene Nullstellen haben?

  2. #2 alex
    9. März 2019

    Der Grund dafür, dass alle Koeffizienten des charakteristischen Polynoms von M ganzzahlig sind, ist relativ leicht mit der Leibniz-Formel für die Determinante erkennbar. Seien m_{i,j} die Einträge von M und \delta_{i,j} das Kronecker-Delta. Dann ist

    c_M(x) = \det (x E_n - M) = \sum_{\sigma \in S_n} sign(\sigma) \prod_{i=1}^n (x \delta_{i, \sigma(i)} - m_{i,\sigma(i)})

    Wenn für ein festes i und ein festes σ gilt i = \sigma(i) , dann ist \delta_{i, \sigma(i)} = m_{i,\sigma(i)} = 1 . Andernfalls ist \delta_{i, \sigma(i)} = 0 . Also gilt stets \delta_{i, \sigma(i)} = m_{i,\sigma(i)} \delta_{i, \sigma(i)} , so dass m_{i,\sigma(i)} ausgeklammert werden kann:

    c_M(x) = \sum_{\sigma \in S_n} sign(\sigma) \prod_{i=1}^n m_{i,\sigma(i)} (x \delta_{i, \sigma(i)} - 1)

    Nun ist \prod_{i=1}^n m_{i,\sigma(i)} stets eine ganze Zahl, oder genauer, entweder 1 oder -1, denn die Zähler der Faktoren dieses Produkts sind (bis auf das Vorzeichen) die Zahlen 1 bis n, und die Nenner sind eine Permutation dieser Zahlen. Die restlichen Terme sind ebenfalls alle ganzzahlig, also sind die Koeffizienten des charakteristischen Polynoms ganzzahlig.

  3. #3 KevinFek
    Р РѕСЃСЃРёСЏ
    9. März 2019

    Confirm that you are not a robot, and There is a goodoffers for your team. http://bit.ly/2EOdB98

  4. #4 Laie
    9. März 2019

    @Bjoern, #1
    Das Stichwort ‘(mathematische) Verfahren’ ist interessant, wenn es um die möglichst berechnungsfehlerfreie Umsetzung in Algorithmen geht. Mir scheint, dies ist die Herausforderung hier. Oft liefern schöne oder effektive Verfahren aus der Mathematik durch 1:1 Umsetzung in Software ungenaue Ergebnisse, es geht wohl auch etwas in Richtung Numerik (in Algorithmen)?

  5. #5 Grassmann
    Mühlenbeck
    9. März 2019

    zu Bjoern: Es ist nirgendwo vorausgesetzt, daß die Nullstellen verschieden sind. Die üblichen Verfahren zur Matrixinversion nutzen den Gaußschen Algorithmus oder die (untaugliche) explizite Formel, die Minoren verwendet. Die Newtonschen Formeln sind sehr leicht zu implementieren. Ich habe das jedenfalls bei der Berechnung quadratischen bzw. kubischen Flächen verwendet (das klappte, obwohl mit Gleitkommazahlen gerechnet wurde). Den Gaußschen Algorithmus in Povray zu implementieren erschien mir zu umständlich.

  6. #6 Bjoern
    10. März 2019

    @Grassmann: Ok, das Ziel ist letztlich also ein einfach zu implementierendes Verfahren zur Matrix-Inversion.

    Der Algorithmus ist mir aber noch nicht ganz klar. Die b_i werden rekursiv mit der Formel aus der Folgerung berechnet? Was ist denn b_0, das steht weiter oben nirgends?

    Und wenn man die b_i dann hat, dann verwendet man letztlich die Formel von Cayley-Hamilton zur Matrix-Inversion?

    Dass die Nullstellen alle verschieden sind, muss man nicht voraussetzen, ok. Aber dass das Polynom n-ten Grades überhaupt n Nullstellen hat, muss man vorausetzen, oder?

  7. #7 alex
    11. März 2019

    @Grassmann:
    Man sollte vielleicht dazu sagen, dass dieser Algorithmus zur Bestimmung der Inversen einer Matrix asymptotisch langsamer ist als der Gauß-Algorithmus. Man benötigt O(n) Matrixmultiplikationen, welche mit dem Standardverfahren jeweils O(n^3), mit alternativen Verfahren im Bereich von O(n^2.4) sind. Zusammen ist das also langsamer als der Gauß-Algorithmus, der ja O(n^3) ist.

    @Bjoern:

    Der Algorithmus ist mir aber noch nicht ganz klar. Die b_i werden rekursiv mit der Formel aus der Folgerung berechnet? […] Und wenn man die b_i dann hat, dann verwendet man letztlich die Formel von Cayley-Hamilton zur Matrix-Inversion?

    So habe ich das auch verstanden. Wenn man beide Schritte kombiniert, bekommt man übrigens den Faddeev-LeVerrier-Algorithmus.

    Was ist denn b_0, das steht weiter oben nirgends?

    Das charakteristische Polynom ist nach Definition normiert, also ist der Leitkoeffizient b_0 = 1. Im Prinzip kann man auch jeden anderen Wert ungleich Null nehmen; dann bekommt man ein entsprechendes Vielfaches des charakteristischen Polynoms und die selbe inverse Matrix.

    Aber dass das Polynom n-ten Grades überhaupt n Nullstellen hat, muss man vorausetzen, oder?

    Im Grunde schon. Aber für reelle oder rationale Matrizen ist das keine Einschränkung. Denn die kann man auch als Matrizen über ℂ betrachten (was sowohl das charakteristische Polynom als auch die Inverse unverändert lässt), und dann greift der Fundamentalsatz der Algebra.

  8. #8 Grassmann
    Mühlenbeck
    11. März 2019

    alex hat ja alles geklärt. Meine Java-Implentation de Gaußschen Algorithmus ist 64 Zeilen lang, für die Newtonschen Formeln brauche ich 22 Zeilen, und bei Povray ist es noch etwas umständlicher. Und was die Komplexität angeht, da muß man sich bei “kleinen” Matrizen wohl noch nicht darum Sorgen machen. Ich glaube, mehr Zeit braucht das Rechnen mit rationalen Zahlen.